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. static void RozkladDoolittle(int[,] macierz, out int[,] gorna, out int[,] dolna)
  2. {
  3.   int n = macierz.GetLength(0);
  4.   gorna = new int[n, n];
  5.   dolna = new int[n, n];
  7.   for (int i = 0; i < n; i++)
  8.   {
  9.     for (int k = i; k < n; k++)
  10.     {
  11.       int sum = 0;
  12.       for (int j = 0; j < i; j++)
  13.       {
  14.         sum += (dolna[i, j] * gorna[j, k]);
  15.       }
  16.       gorna[i, k] = macierz[i, k] - sum;
  17.     }
  19.     for (int k = i; k < n; k++)
  20.     {
  21.       if (i == k)
  22.       {
  23.         dolna[i, i] = 1;
  24.       }
  25.       else
  26.       {
  27.         int suma = 0;
  28.         for (int j = 0; j < i; j++)
  29.         {
  30.           suma += (dolna[k, j] * gorna[j, i]);
  31.         }
  32.         dolna[k, i] = (macierz[k, i] - suma) / gorna[i, i];
  33.       }
  34.     }
  35.   }
  36. }

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. static void Main(string[] args)
  2. {
  3.   Console.WriteLine("Podaj rozmiar macierzy\n n = ");
  4.   int n = Convert.ToInt32(Console.ReadLine());
  5.   Console.WriteLine("Podaj macierz:");
  6.   int[,] macierz = new int[n, n];
  7.   for (int i = 0; i < n; i++)
  8.   {
  9.     string[] data = Console.ReadLine().Split(' ');
  10.     for (int j = 0; j < n; j++)
  11.     {
  12.       macierz[i, j] = Convert.ToInt32(data[j]);
  13.     }
  14.   }
  15.   RozkladDoolittle(macierz, out int[,] gorna, out int[,] dolna);
  16.   Console.WriteLine("Górna U:");
  17.   WypiszTablice(gorna, n);
  18.   Console.WriteLine("Dolna U:");
  19.   WypiszTablice(dolna, n);
  20.   Console.ReadKey();
  21. }

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

  1. static void WypiszTablice(int[,] macierz, int n)
  2. {
  3.   for (int i = 0; i < n; i++)
  4.   {
  5.     for (int j = 0; j < n; j++)
  6.     {
  7.       Console.Write("{0}\t", macierz[i, j]);
  8.     }
  9.     Console.WriteLine();
  10.   }
  11. }