Strona główna » Algorytmy » Artykuły » Macierze Trójkątne
 

Macierze Trójkątne

https://mattomatti.com/a0105

Wstęp

Macierz Trójkątna to taka macierz, która powyżej diagonali, albo pod ma tylko wartości 0. Równania z tego typu macierzami rozwiązuje się szybciej dzięki ich właściwościom. W tym artykule zostanie wyjaśniony algorytm rozwiązywania układów równań z macierzę górnotrójkątną.

Macierz Górnotrójkątna

Ogólna postać macierzy górnotrójkątnej wygląda następująco:

Taką postać można otrzymać w wyniku przeprowadzenia eliminacji Gaussa. Jej zaletą jest fakt, że wyznacznik wynosi tyle co iloczyn wartości na diagonali tj. det(U) = U11 + U22 + .. + Unn. Przypuśćmy, że do rozwiązania jest układ Ux = b, gdzie szukany jest wektor x. Wtedy można skorzystać z następujących wzorów:

Wyliczanie kolejnych elementów zaczyna się od n-tego rzędu, ponieważ wszystkie poprzednie wyrazy zostaną wyliczone na podstawie następnych. Podczas rozwiązywania układu równań dla macierzy dolnotrójkątnej należałoby wyliczać od pierwszego rzędu do ostatniego używają bardzo podobnych wzorów.

Przykład

Dane jest następujące równanie:

Kolejno zostaną wykonane następujące działania:

Podsumowując rozwiązaniem podanego na początku przykładu równanie Ux = b ma rozwiązanie x = [0; -4; 3].

Implementacja

Napisana ponizej funkcja korzysta z biblioteki matrix.h, aby wczytać / wyświetlić dane w macierzy. Ponizej została przedstawiona funkcja rozwiazGora(), która dla danej macierz U oraz wektora b wyznaczy i zwróci x w równaniu Ux = b.

  1. Matrix* rozwiazGora(Matrix* A, Matrix* b) {
  2.   if (A->n != b->n)
  3.     return NULL;
  4.   int n = A->n;
  5.   Matrix* x = createMatrix(n, 1);
  6.   for (int i = n - 1; i >= 0; i--) {
  7.     x->data[i][0] = b->data[i][0] / A->data[i][i];
  8.     for (int j = 0; j < i; j++) {
  9.       b->data[j][0] -= x->data[i][0] * A->data[j][i];
  10.     }
  11.   }
  12.   return x;
  13. }

(2.) Sprawdź czy wektor b i macierz A mają tyle samo wierszy i jeśli nie to (3.) zwróć NULL. Następnie (4.) pobierz rozmiar macierzy A. (5.) Dla każdego wiersza: (6. - 9.) oblicz xi.

Testowanie funkcji

W celu przetestowania napisanej funkcji wystarczy poniższy fragment kodu, który wczyta od użytkownika odpowiednie dane, a następnie wyświetli rozwiązanie.

  1. int main () {
  2.   Matrix* A = readMatrixSquare();
  3.   cout << "Podaj wektor b:\n";
  4.   Matrix* b = readMatrix(A->n, 1);
  5.   Matrix* x = rozwiazGora(A, b);
  6.   if (x == NULL) {
  7.     cout << "Wprowadzono nieprawidlowa macierz!";
  8.   } else {
  9.     cout << "Rozwiazaniem dla x jest:\n";
  10.     writeMatrix(x);
  11.   }
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Napisz funkcję rozwiazDol(), która rozwiąże układ równań Lx = b, gdzie L jest macierzą dolnotrójkątną. Przetestuj działanie napisanego programu.