Metoda LU

Metoda LU jest metodą rozwiązywania układu równań liniowych postaci:

$\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}$

W zapisie macierzowym $\mathbf{A} \cdot \mathbf{x} = \mathbf{y}$, gdzie $\mathbf{A}$ - macierz współczynników, $\mathbf{x}$ - wektor niewiadomych, $\mathbf{y}$ - wektor danych.

Pozwala także na szybkie wyliczenie wyznacznika macierzy $\mathbf{A}$.

Metoda LU

W metodzie LU macierz współczynników zapisywana jest jako iloczyn dwóch macierzy trójkątnych: dolnej (ang. lower - $\mathbf{L}$) i górnej (ang. upper - $\mathbf{U}$), tj. z elementami zerowymi - odpowiednio - powyżej i poniżej przekątnej macierzy:

$\mathbf{A} = \mathbf{L} \cdot \mathbf{U}$
$\$
$\mathbf{L} = \begin{bmatrix} l_{11} & 0 & \cdots & 0 \\ l_{21} & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & 0 \\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{bmatrix} \ \ \ \ \ \ \mathbf{U} = \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{bmatrix}$

Układ równań przyjmuje wówczas postać

$\mathbf{L} \cdot \mathbf{U} \cdot \mathbf{x} = \mathbf{y},$

a jego rozwiązanie sprowadza się do rozwiązania dwóch układów równań z macierzami trójkątnymi, które z kolei rozwiązuje się bardzo prosto:

$\mathbf{L} \cdot \mathbf{z} = \mathbf{y},$
$\mathbf{U} \cdot \mathbf{x} = \mathbf{z}.$

Ostatecznie liczba mnożeń, potrzebnych do wyznaczenia wektora $\mathbf{x}\,$, wynosi $n^2\,$, dodawań $n^2 - n\,$.

Wyznacznik macierzy $\mathbf{A}\,$ tej postaci można obliczyć korzystając z twierdzenia Cauchy'ego:

$\mathbf{det(L \cdot \mathbf U)}=\mathbf{det(L)} \cdot \mathbf{det(U)},$

oraz z faktu, że wyznacznik macierzy trójkątnej jest iloczynem elementów na przekątnej. Otrzymujemy wówczas:

$\mathbf{det(A)} = \mathbf{det(L \cdot U)} = \mathbf{det(L)} \cdot \mathbf{det(U)} = l_{11} \cdot l_{22} \cdot \cdots \cdot l_{nn} \cdot u_{11} \cdot u_{22} \cdot \cdots \cdot u_{nn}.$

Ponadto przeważnie przy rozkładzie LU na przekątnej jednej z macierzy znajdują się jedynki – wtedy wyznacznik macierzy $\mathbf{A}\,$ jest równy wyznacznikowi albo macierzy $\mathbf{L}\,$, albo $\mathbf{U}\,$, którego obliczenie wymaga wykonania $n-1\,$ mnożeń (zamiast $2n-1\,$).

Zalety metody:

• bardzo oszczędna gospodarka pamięcią;
• wymaga najmniejszej liczby operacji w porównaniu z innymi metodami dokładnymi (nie biorąc pod uwagę procedur specjalnych).

Rozkład LU

Podstawowym problemem numerycznym w tej metodzie jest dokonanie rozkładu LU macierzy współczynników. Żeby ten rozkład macierzy był jednoznaczny zakłada się, że elementy na głównej przekątnej jednej z macierzy, $\mathbf{L}$ albo $\mathbf{U}$, są równe 1.

Rozkład LU jest wyznaczany za pomocą metody Doolittle'a (opisana niżej).

Ta metoda nie jest niezawodna, tzn. podczas obliczeń może wystąpić dzielenie przez zero. Istnieje jej modyfikacja pozbawiona tej wady, nazywana metodą Doolittle-Crouta, w której wykorzystuje się częściowy wybór elementu podstawowego.

Element podstawowy to taki element w macierzy $A$, który jest używany do rugowania zmiennych (czyli zerowania odpowiadających im współczynników) z kolejnych równań. Przy stosowaniu metody Doolittle'a wybiera się element podstawowy zawsze z przekątnej głównej i jeśli $a_{kk}$ jest równe zero, metoda zawodzi.

W metodach zmodyfikowanych wybierany jest ten element z danej $k$-tej kolumny, który ma największy moduł. Następnie wiersz, w którym znajduje się wybrany element, zamieniany jest z $k$-tym wierszem, co powoduje, że element podstawowy pojawia się na przekątnej głównej. To gwarantuje, że podczas obliczeń nie wystąpi dzielenie przez zero.

Jednocześnie te zmodyfikowane metody nie zawsze dają rozkład LU macierzy $\mathbf{A}$. Może się zdarzyć, że otrzymany rozkład LU dotyczy macierzy $\mathbf{A}$, w której dokonano takich samych przestawień wierszy, jak podczas eliminacji zmiennych. Jednak ma to znaczenie (i komplikuje obliczenia) tylko wtedy, gdy rozkład LU służy do wyznaczenia macierzy odwrotnej; w innych zadaniach nie odgrywa roli.

Metoda Doolittle'a

W metodzie tej równość $\mathbf{A} = \mathbf{L U}$ traktuje się jako układ $n^2$ równań z $n^2$ niewiadomymi. Te niewiadome to elementy $l_{ij}$ dla $i > j$ (elementy poniżej przekątnej), oraz $u_{ij}$ dla $j \geqslant i$ (elementy na i powyżej przekątnej), przy założeniu, że na diagonali macierzy $\mathbf{L}$ znajdują się 1:

$\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ l_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & 0 \\ l_{n1} & l_{n2} & \cdots & 1 \end{bmatrix} \cdot \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{bmatrix}$

Wyznaczanie kolejnych elementów macierzy $\mathbf{L}\,$ i $\mathbf{U}\,$ robi się naprzemiennie, tj. raz wyznacza wiersz macierzy $\mathbf{U}\,$, raz kolumnę macierzy $\mathbf{L}\,$.

Wzory ogólne na poszczególne elementy macierzy rozkładu przedstawiają się następująco:

dla wszystkich $i\in\{1,2,\ldots, n\}:$

$u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik} u_{kj}$ dla $j\in\{i,\ i+1,\ \ldots,\ n\};$

$l_{ji} = \frac{1}{u_{ii}} \left(a_{ji} - \sum_{k=1}^{i-1} l_{jk} u_{ki} \right)$ dla $j\in\{i+1,\ i+2,\ \ldots,\ n\}.$

Z ostatniego równania wynika, że metoda nie zadziała, gdy $u_{ii} = 0.\,$

Liczba działań potrzebna do rozkładu:

• mnożenia: $\frac{1}{3} n^3 - \frac{1}{3} n ,$
• dodawania: $\frac{1}{3} n^3 - \frac{1}{2} n^2 + \frac{1}{6} n.$

Przykład (macierz 3x3)

$\begin{bmatrix}5 & 3 & 2 \\ 1 & 2 & 0 \\ 3 & 0 & 4\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix}$

Pierwszy wiersz macierzy U:

$5 = 1 \cdot u_{11} + 0 \cdot 0 + 0 \cdot 0 \rightarrow u_{11} = 5$

$3 = 1 \cdot u_{12} + 0 \cdot u_{22} + 0 \cdot 0 \rightarrow u_{12} = 3$

$2 = 1 \cdot u_{13} + 0 \cdot u_{23} + 0 \cdot u_{33} \rightarrow u_{13} = 2$

$\begin{bmatrix}5 & 3 & 2 \\ 1 & 2 & 0 \\ 3 & 0 & 4\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix} \begin{bmatrix} 5 & 3 & 2 \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix}$

Pierwsza kolumna macierzy L:

$1 = l_{21} \cdot 5 + 1 \cdot 0 + 0 \cdot 0 \rightarrow l_{21} = \frac{1}{5}$

$3 = l_{31} \cdot 5 + l_{32} \cdot 0 + 1 \cdot 0 \rightarrow l_{31} = \frac{3}{5}$

$\begin{bmatrix}5 & 3 & 2 \\ 1 & 2 & 0 \\ 3 & 0 & 4\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \frac{1}{5} & 1 & 0 \\ \frac{3}{5} & l_{32} & 1 \end{bmatrix} \begin{bmatrix} 5 & 3 & 2 \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix}$

Drugi wiersz macierzy U:

$2 = \frac{1}{5} \cdot 3 + 1 \cdot u_{22} + 0 \cdot 0 \rightarrow u_{22} = \frac{7}{5}$

$0 = \frac{1}{5} \cdot 2 + 1 \cdot u_{23} + 0 \cdot u_{33} \rightarrow u_{23} = -\frac{2}{5}$

$\begin{bmatrix}5 & 3 & 2 \\ 1 & 2 & 0 \\ 3 & 0 & 4\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \frac{1}{5} & 1 & 0 \\ \frac{3}{5} & l_{32} & 1 \end{bmatrix} \begin{bmatrix} 5 & 3 & 2 \\ 0 & \frac{7}{5} & -\frac{2}{5} \\ 0 & 0 & u_{33} \\ \end{bmatrix}$

Druga kolumna macierzy L:

$0 = \frac{3}{5} \cdot 3 + l_{32} \cdot \frac{7}{5} + 1 \cdot 0 \rightarrow l_{32} = -\frac{9}{7}$

$\begin{bmatrix}5 & 3 & 2 \\ 1 & 2 & 0 \\ 3 & 0 & 4\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \frac{1}{5} & 1 & 0 \\ \frac{3}{5} & -\frac{9}{7} & 1 \end{bmatrix} \begin{bmatrix} 5 & 3 & 2 \\ 0 & \frac{7}{5} & -\frac{2}{5} \\ 0 & 0 & u_{33} \\ \end{bmatrix}$

Trzeci wiersz macierzy U:

$4 = \frac{3}{5} \cdot 2 + \frac{9}{7} \cdot \frac{2}{5} + 1 \cdot u_{33} \rightarrow u_{33} = \frac{16}{7}$

$\begin{bmatrix}5 & 3 & 2 \\ 1 & 2 & 0 \\ 3 & 0 & 4\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \frac{1}{5} & 1 & 0 \\ \frac{3}{5} & -\frac{9}{7} & 1 \end{bmatrix} \begin{bmatrix} 5 & 3 & 2 \\ 0 & \frac{7}{5} & -\frac{2}{5} \\ 0 & 0 & \frac{16}{7} \\ \end{bmatrix}$

Metoda Gaussa

Wersja pamięciożerna

Do macierzy której rozkładu dokonujemy dopisujemy lewostronnie macierz jednostkową Na prawym bloku macierzy wykonujemy operacje elementarne takie jak w metodzie Gaussa (odejmowanie mnożenie) W lewym bloku macierzy zapisujemy współczynniki użyte do eliminacji

$\begin{bmatrix}5 & 3 & 2 \\ 1 & 2 & 0 \\ 3 & 0 & 4\end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 5 & 3 & 2 \\ 0 & 1 & 0 & 1 & 2 & 0\\ 0 & 0 & 1 & 3 & 0 & 4 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 5 & 3 & 2 \\ \frac{1}{5} & 1 & 0 & 0 & \frac{7}{5} & -\frac{2}{5}\\ \frac{3}{5} & 0 & 1 & 0 & -\frac{9}{5} & \frac{14}{5} \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 5 & 3 & 2 \\ \frac{1}{5} & 1 & 0 & 0 & \frac{7}{5} & -\frac{2}{5}\\ \frac{3}{5} & -\frac{9}{7} & 1 & 0 & 0 & \frac{16}{7} \end{bmatrix}$

Wersja wymagająca mniej pamięci

Przepisujemy wiersz bez zmian a elementy w kolumnie poniżej głównej przekątnej dzielimy przez element znajdujący się na głównej przekątnej Dla pozostałej części macierzy obliczamy uzupełnienie Schura

$a_{ij}=a_{ij}-a_{ik}a_{kj}$

Powyższe kroki wykonujemy dla k=1 ,...,n-1

Gdy któryś z elementów na głównej przekątnej wynosi zero to rozkład LU=A nie istnieje ale można spróbować dokonać rozkładu LU dla pewnej permutacji wierszy macierzy A. Dla każdej nieosobliwej macierzy kwadratowej A można dokonać rozkładu LU macierzy powstałej z pewnej permutacji wierszy macierzy A.

Metoda Crouta

Metoda ta jest analogiczną do metody Doolittle'a, różnica polega na tym, że diagonala macierzy U jest wypełniona liczbami 1.

$\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} = \begin{bmatrix} l_{11} & 0 & \cdots & 0 \\ l_{21} & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & 0 \\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{bmatrix} \cdot \begin{bmatrix} 1 & u_{12} & \cdots & u_{1n} \\ 0 & 1 & \cdots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}$

Przykład rozwiązania układu równań

Zostanie użyta ta sama macierz współczynników, jak w przykładzie dla metody Doolittle'a:

$\begin{bmatrix}5 & 3 & 2 \\ 1 & 2 & 0 \\ 3 & 0 & 4\end{bmatrix} \cdot \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}10 \\ 5 \\ -2\end{bmatrix}$

Teraz zostaną zapisane dwa układy równań z macierzami trójkątnymi $\mathbf{L}$ i $\mathbf{U}$:

• $\begin{bmatrix} 1 & 0 & 0 \\ \frac{1}{5} & 1 & 0 \\ \frac{3}{5} & -\frac{9}{7} & 1 \end{bmatrix} \cdot \begin{bmatrix}z_1 \\ z_2 \\ z_3\end{bmatrix} = \begin{bmatrix}10 \\ 5 \\ -2\end{bmatrix}$

• $\begin{bmatrix} 5 & 3 & 2 \\ 0 & \frac{7}{5} & -\frac{2}{5} \\ 0 & 0 & \frac{16}{7} \\ \end{bmatrix} \cdot \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}z_1 \\ z_2 \\ z_3\end{bmatrix}$

Najpierw zostanie wyznaczony wektor $\mathbf{z}$ z pierwszego układu równań $\mathbf{L z} = \mathbf{y}$. Rozwiązanie układu równań z macierzą trójkątną jest bardzo proste: wyznaczane są kolejno elementy wektora niewiadomych $z_1$, następnie, gdy znane jest $z_1$, można wyznaczyć $z_2$, a na końcu $z_3$, ponieważ znane są $z_1$ i $z_2$:

1. $1 \cdot {\color{blue}z_1} = 10 \rightarrow z_1 = 10$
2. $\frac{1}{5} \cdot z_1 + 1 \cdot {\color{blue}z_2} = \frac{1}{5} \cdot 10 + z_2 = 5 \rightarrow z_2 = 5 - 2 = 3$
3. $\frac{3}{5} \cdot z_1 -\frac{9}{7} \cdot z_2 + {\color{blue}z_3} = \frac{3}{5} \cdot 10 - \frac{9}{7} \cdot 3 + z_3 = -2 \rightarrow z_3 = -2 - 6 + \frac{27}{7} = -\frac{29}{7}$

Teraz drugi układ równań przyjmuje postać:

$\begin{bmatrix} 5 & 3 & 2 \\ 0 & \frac{7}{5} & -\frac{2}{5} \\ 0 & 0 & \frac{16}{7} \\ \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}10 \\ 3 \\ -\frac{29}{7}\end{bmatrix}$

Sposób rozwiązywania jest analogiczny jak dla pierwszego układu, z tym że elementy wektora $\mathbf{x}$ są wyznaczane "od końca":

1. $\frac{16}{7} \cdot {\color{blue}x_3} = -\frac{29}{7} \rightarrow x_3 = -\frac{29}{16}$
2. $\frac{7}{5} \cdot {\color{blue}x_2} - \frac{2}{5} \cdot x_3 = \frac{7}{5} \cdot x_2 + \frac{29}{40} = 3 \rightarrow x_2 = \frac{3 - \frac{29}{40}}{\frac{7}{5}} = \frac{13}{8}$
3. $5 \cdot {\color{blue}x_1} + 3 \cdot x_2 + 2 \cdot x_3 = 5 \cdot x_1 + 3 \cdot \frac{13}{8} - 2 \cdot \frac{29}{16} = 10 \rightarrow x_1 = \frac{10 - \frac{39}{8} + \frac{29}{8}}{5} = \frac{7}{4}$

Ostatecznie wynikiem jest wektor $\mathbf{x} = \left[\frac{7}{4}, \frac{13}{8}, -\frac{29}{16}\right]$.

Przykład obliczania wyznacznika

Ponownie wykorzystane zostaną wyniki z przykładu dla metody Doolittle'a:

$\det\left(\begin{bmatrix}5 & 3 & 2 \\ 1 & 2 & 0 \\ 3 & 0 & 4\end{bmatrix}\right) = \det\left(\begin{bmatrix} 1 & 0 & 0 \\ \frac{1}{5} & 1 & 0 \\ \frac{3}{5} & -\frac{9}{7} & 1 \end{bmatrix}\right) \cdot \det\left(\begin{bmatrix} {\color{blue}5} & 3 & 2 \\ 0 & {\color{blue}\frac{7}{5}} & -\frac{2}{5} \\ 0 & 0 & {\color{blue}\frac{16}{7}} \\ \end{bmatrix}\right)$

Ponieważ na przekątnej macierzy $\mathbf{L}$ są jedynki, dlatego wyznacznik macierzy $\mathbf{\det(A)} = \mathbf{\det(U)} = 5 \cdot \frac{7}{5} \cdot \frac{16}{7} = 16$.

Zobacz też

• rozkład macierzy
• rozkład Choleskiego