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ść.

C++C#
Python
  1. def RozkladDoolittle(macierz):
  2.   n = len(macierz)
  3.   gorna = [[0]*n for x in range(n)]
  4.   dolna = [[0]*n for x in range(n)]
  6.   for i in range(n):
  7.     for k in range(i, n):
  8.       suma = sum([dolna[i][j] * gorna[j][k] for j in range(i)])
  9.       gorna[i][k] = macierz[i][k] - suma
  11.     for k in range(i, n):
  12.       if i == k:
  13.         dolna[i][i] = 1
  14.         continue
  15.       suma = sum([dolna[k][j] * gorna[j][i] for j in range(i)])
  16.       dolna[k][i] = (macierz[k][i] - suma) / gorna[i][i]
  18.   return gorna, dolna

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:

C++C#
Python
  1. n = int(input("Podaj rozmiar macierzy\n n = "))
  2. macierz = []
  3. for i in range(n):
  4. tmp = [int(x) for x in input().split()]
  5. macierz.append(tmp)
  6. gorna, dolna = RozkladDoolittle(macierz)
  7. print("Górna U:")
  8. WypiszTablice(gorna)
  9. print("Dolna U:")
  10. WypiszTablice(dolna)

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

C++C#
Python
  1. def WypiszTablice(macierz):
  2.   n = len(macierz)
  3.   for i in range(n):
  4.     print('\t'.join([str(x) for x in macierz[i]]))