Strona główna » Algorytmy » Artykuły » Metoda Doolittle'a
 

Metoda Doolittle'a

https://mattomatti.com/a0308

Cel

Metoda Doolittle'a służy do wyznaczania rozkładu LU dowolnej macierzy nieosobliwej. Po znalezieniu takiej macierzy można bardzo szybko rozwiązywać układy równań. Rozkład na macierz górnotrójkątną i dolnotrójkątną został wprowadzony przez Tadeusza Banachiewicza w 1938 r.

Opis Metody

Przygotowywujemy dwie macierze o takim samym rozmiarze jak rozkładana macierz. Bardzo ważne, aby była ona nieosobliwa. Początkowo wszystkie elementy powinny zostać ustawione na 0. Macierz górnotrójkątną U wypełniamy poniższym wzorem:

Z kolei macierz dolnotrójkątną przy pomocy tego wzoru:

Przykład

Weźmy przykładowo poniższą macierz:

Po rozkładzie na macierze L i U otrzymujemy następujące wyniki:

Przy macierzy dolnotrójkątnej na przekątnych zawsze znajdą się wartości 1. Tam gdzie występują wartości 0 to nie wykonujemy jakichkolwiek obliczeń (zgodnie ze wzorem).

Implementacja

Jak można zauważyć obliczenia obydwu macierzy trójkątnych można wykonać równocześnie, ponieważ obie używaja indeksu i w tym samym zakresie. Poniższa funkcja RozkladDoolittle() wykorzystuje tę zależność.

  1. void RozkladDoolittle(int** macierz, int n, int** gorna, int** dolna)
  2. {
  3.   for (int i = 0; i < n; i++) {
  4.     for (int k = i; k < n; k++) {
  5.       int sum = 0;
  6.       for (int j = 0; j < i; j++) {
  7.         sum += (dolna[i][j] * gorna[j][k]);
  8.       }
  9.       gorna[i][k] = macierz[i][k] - sum;
  10.     }
  12.     for (int k = i; k < n; k++) {
  13.       if (i == k) {
  14.         dolna[i][i] = 1;
  15.       } else {
  16.         int suma = 0;
  17.         for (int j = 0; j < i; j++) {
  18.           suma += (dolna[k][j] * gorna[j][i]);
  19.         }
  20.         dolna[k][i] = (macierz[k][i] - suma) / gorna[i][i];
  21.       }
  22.     }
  23.   }
  24. }

Każda z macierzy jest początkowo zainicjalizowana przy użyciu zer. Następnie elementy macierzy są wyliczane według wzoru podanego wyżej.

Testowanie funkcji

Program można przetestować poniższym fragmentem programu:

  1. int main() {
  2.   int n;
  3.   cout << "Podaj rozmiar macierzy\n n = ";
  4.   cin >> n;
  5.   cout << "Podaj macierz:" << endl;
  6.   int** macierz = new int*[n];
  7.   for (int i = 0; i < n; i++) {
  8.     macierz[i] = new int[n];
  9.     for (int j = 0; j < n; j++) {
  10.       cin >> macierz[i][j];
  11.     }
  12.   }
  13.   int** gorna = UtworzTablice(n);
  14.   int** dolna = UtworzTablice(n);
  15.   RozkladDoolittle(macierz, n, gorna, dolna);
  16.   cout << "Gorna U:" << endl;
  17.   WypiszTablice(gorna, n);
  18.   cout << "Dolna L:" << endl;
  19.   WypiszTablice(dolna, n);
  20.   system("pause");
  21.   return 0;
  22. }

W program zostały wykorzystane następujące funkcje pomocnicze:

  1. int** UtworzTablice(int n) {
  2.   int** tab = new int*[n];
  3.   for (int i = 0; i < n; i++) {
  4.     tab[i] = new int[n];
  5.     for (int j = 0; j < n; j++) {
  6.       tab[i][j] = 0;
  7.     }
  8.   }
  9.   return tab;
  10. }
  12. void WypiszTablice(int** macierz, int n) {
  13.   for (int i = 0; i < n; i++) {
  14.     for (int j = 0; j < n; j++) {
  15.       cout << macierz[i][j] << "\t";
  16.     }
  17.     cout << endl;
  18.   }
  19. }