Eliminacja Gaussa-Jordana w porównaniu z dekompozycją LU

Question

W "czarnej księdze", w wydaniu numerycznym, wydanie trzecie, podano algorytm Gaussa-Jordana dla rozwiązania układu równań liniowych. Bezpośrednio potem jest rozdział dotyczący obliczania dekompozycji LU, a następnie wykorzystywany do rozwiązania układu równań liniowych (patrz LUdcmp :: rozwiązać na str. 53). Niestety, książka nie wyjaśnia, dlaczego ktoś wolałby jedną metodę od drugiej. Czy oba podejścia są równoważne, czy też istnieją powody, aby preferować jedną metodę w stosunku do drugiej w konkretnej sytuacji?

Answer 1

Zaletami dekompozycji LU może być ponowne wykorzystanie do obliczenia wielu rozwiązań.

Na przykład, jeśli chcesz rozwiązać równanie

Ax = b 

dla stałej A i wielu różnych b s potem wystarczy tylko obliczyć metoda lu z A raz i może być ponownie użyty do każdego b. Jednak w przypadku eliminacji Gaussa-Jordana konieczne będzie ponowne wykonanie wszystkich operacji dla każdego z nich. Przyczyna tego jest szybsza, ponieważ eliminacja Gaussa-Jordana skaluje się jako O (n^3), ale etap podstawienia dekompozycji LU metoda skaluje się tylko jako O (n^2). Dlatego w przypadku LU wystarczy wykonać tylko jeden kosztowny krok O (n^3) dla każdego b.

Rozsądny zestaw notatek na dokładnie ten temat można znaleźć here