Metoda LU

Z Wikipedii

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 x = 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}$ .

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 $x$ wynosi $n 2$ , dodawań $n 2 - n$ .

Wyliczanie wyznacznika macierzy A. Korzystając z twierdzenia Cauchy'ego:

$\mathbf{det(A \cdot \mathbf B)}=\mathbf{det(A)} \cdot \mathbf{det(B)}$

Oraz, z faktu, ze wyznacznik macierzy trójkątnej jest iloczynem elementów na przekątnej, otrzymujemy:

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

Zalety metody:

bardzo oszczędna gospodarka pamięcią - całość obliczeń jest wykonywana w tych samych tablicach i wektorach, w których zostały sformułowane wyjściowe równania;
wymaga najmniejszej liczby operacji w porównaniu z innymi metodami dokładnymi (nie biorąc pod uwagę procedur specjalnych).

Spis treści

1 Rozkład LU
2 Metoda Doolittle'a
- 2.1 Przykład (macierz 3x3)
3 Zobacz też

[edytuj] 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 eliminacji Gaussa
Metody Crout'a (opisana niżej)

Obie metody nie są niezawodne, tzn. podczas obliczeń może wystąpić dzielenie przez zero. Istnieją ich modyfikacje pozbawione tej wady, nazywane odpowiednio metodą Gaussa-Crouta i Doolittle-Crouta, w których 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ń. Metody Gaussa i Doolittle'a wybierają element podstawowy zawsze z przekątnej głównej i jeśli $a k k$ jest równe zero obie zawodzą.

W metodach zmodyfikowanych wybierany jest ten element z danej $k - t e j$ 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, tutaj nie odgrywa roli.

[edytuj] Metoda Doolittle'a

W metodzie tej równość $A = L U$ traktuje się jako układ $n 2$ równań z $n 2$ niewiadomymi. Te niewiadome to elementy $l i j$ dla $i < j$ (elementy poniżej przekątnej), oraz $u i j$ dla $i \ge j$ (elementy na i powyżej przekątnej), przy założeniu, że na diagonali macierzy $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 $L$ i $U$ robi się naprzemiennie, tj. raz wyznacza wiersz macierzy $U$ , raz kolumnę macierzy $L$ .

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

dla wszystkich $i=1,2,\ldots, n$ :

$u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik} u_{kj}$ dla $j=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=i+1,i+2\ldots, n$

Z ostatniego równania wynika, że metoda nie zadziała, gdy $u i i = 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$ .

[edytuj] 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}$