Strona główna » Algorytmy » Artykuły » Rozkład LU eliminacją Gaussa
 

Rozkład LU eliminacją Gaussa

https://mattomatti.com/a0100

Wstęp

Rozkład LU to rozkład pewnej macierzy A na macierz dolnotrójkątną L oraz górnotrójkątną U tak, że A = LU. Wyznaczenie obydwu macierzy jest możliwe przy pomocy metody eliminacji Gaussa. W tym artykule zostanie przedstawione krok po kroku jak należy to obliczyć.

Algorytm

Poszukujemy rozkładu pewnej macierzy A o wymiarach n×n na macierze L i U. Przykładowo dla n = 3 równanie miałoby postać:

W wyniku eliminacji Gaussa zostanie uzyskana macierz górnotrójkątna. Z kolei macierz dolnotrójkątną należy wyznaczyć w następujący sposób. Pierwszy krok eliminacji Gaussa polega na wyzerowaniu kolumny poniżej elementu a11. Zerując i-tym wierszem j-ty wiersz należy wpisać na pozycji Lji współczynnik przez który został pomnożony wiersz i-ty. Ponadto macierz dolnotrójkątna ma zawsze na diagonali wartości 1. Po wykonaniu eliminacji Gaussa zostaną uzyskane dwie macierze L i U.

Przykład

W wyniku eliminacji Gaussa zostanie uzyskana macierz górnotrójkątna. Z kolei macierz dolnotrójkątną należy wyznaczyć w następujący sposób. Pierwszy krok eliminacji Gaussa polega na wyzerowaniu kolumny poniżej elementu a11. Zerując i-tym wierszem j-ty wiersz należy wpisać na pozycji Lji współczynnik przez który został pomnożony wiersz i-ty. Ponadto macierz dolnotrójkątna ma zawsze na diagonali wartości 1. Po wykonaniu eliminacji Gaussa zostaną uzyskane dwie macierze L i U.

Rozpoczynamy elementu a11. Wyzerowane zostaną wartości a21 i a31 poprzez odjęcie odpowiednią ilość razy pierwszego wiersza od drugiego oraz trzeciego.

W ten sposób zostały otrzymane wartości L21 = 2 i L31 = 3, które jak było wspominane oznaczają ile razy został odjęty pierwszy wiersz od kolejno drugiego i trzeciego. Pozostało teraz jeszcze wybrać pozycją a22 i wyzerować wszystko poniżej:

Od ostatnieg wiersza odjęto dwa razy drugi, więc L32 = 2. Eliminacja Gaussa została zakończona. Uzyskana macierz końcowa to poszukiwana macierz górnotrójkątna. Druga macierz L dolnotrójkątna będzie miała następującą postać:

W ramach sprawdzenia należałoby pomnożyć macierze L oraz U, aby sprawdzić czy faktycznie A = LU.

Zadanie

Napisz program, która dla podanej macierzy A zwróci rozkład LU zapisany w postaci jednej macierzy. Taki zapis jest możliwy, ponieważ wiadomo, że macierz dolnotrójkątna ma zawsze 1 na diagonali, więc pomija się je i obie macierze można zapisać w jednej. Oto przykład:

Sprawdź poprawność napisanego rozwiązania. Do wykonywania podstawowych operacji na macierzach można skorzystać z biblioteki matrix.h.

Rozwiązanie

Poniższy kod funkcji rozkladLUGauss() przyjmuje jeden argument A - macierz dla której ma zostać wyznaczony rozkład LU. Wynikiem działania funkcji jest zwrócenie połączonej macierzy L i U.

  1. Matrix* rozkladLUGauss(Matrix* A) {
  2.   if (A->m != A->n) return NULL;
  3.   int n = A->n;
  4.   Matrix* M = createMatrix(n, n);
  5.   for (int i = 0; i < n; i++) {
  6.     for (int j = 0; j <= i; j++)
  7.       M->data[j][i] = A->data[j][i];
  8.     for (int j = i + 1; j < n; j++) {
  9.       double w = A->data[j][i]/A->data[i][i];
  10.       M->data[j][i] = w;
  11.       for (int k = 0; k < n; k++)
  12.         A->data[j][k] -= w*A->data[i][k];
  13.     }
  14.   }
  15.   return M;

(2.) Sprawdź czy macierz jest kwadratowa. Jeśli tak to (3.) pobierz jej rozmiar i (4.) utwórz nową macierz. Następnie (5.) dla każdego wiersza: (6. - 7.) przepisz elementy z A, które należą do U, a potem (8.) rozpocznij zerowania danej kolumny poniżej elementu z diagonali. (9.) Oblicz współczynnik, który (10.) należy wpisać do macierzy wynikowej oraz (11. - 12.) przeprowadź odejmowanie dwóch wierszy.

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika macierz, a następnie wypisuje dla niej połączony rozkład LU uzyskany metodą eliminacji Gaussa.

  1. int main () {
  2.   Matrix* A = readMatrix();
  3.   Matrix* M = rozkladLUGauss(A);
  4.   if (M == NULL) {
  5.     cout << "Wprowadzono nieprawidlowa macierz!";
  6.   } else {
  7.     cout << "Polaczona macierz LU to:\n";
  8.     writeMatrix(M);
  9.   }
  10.   system("pause");
  11.   return 0;
  12. }

Zadania

Zadanie 1

Napisz funkcję rozlozMacierzLU(), która wypisz oddzielnie macierz L oraz U na podstawie macierzy zwracanej przez funkcję rozkladLUGauss() z omówionego wcześniej zadania.

Przykładowo dla macierzy:

program ma wypisać:

  1. L =
  2. 1   0   0
  3. 2   1   0
  4. 3   2   1
  5. U =
  6. 1   2   3
  7. 0   4   5
  8. 0   0   6