~~NOCACHE~~
~~REVEAL theme=simple&size=1024x800~~

====== Lab. 11 Rozwiązywanie układów równań liniowych c. d.======

===== Układ równań ====
Poszukujemy wektora $\mathbf{x}$ który spełnia 

$$\mathbf{A} \mathbf{x}=\mathbf{b}$$

$$\left[\begin{array}{cccc}
a_{11} & a_{12} & \ldots & a_{1 n} \\
a_{21} & a_{22} & \ldots & a_{2 n} \\
\ldots & \ldots & \ldots & \ldots \\
a_{n 1} & a_{n 2} & \ldots & a_{n n}
\end{array}\right] \cdot\left[\begin{array}{l}
x_{1} \\
x_{2} \\
\ldots \\
x_{n}
\end{array}\right]=\left[\begin{array}{l}
b_{1} \\
b_{2} \\
\ldots \\
b_{n}
\end{array}\right]$$

===== Metody =====

  * Dokładne:
    * wyznaczniki Cramera
    * Eliminacja Gaussa
    * Metoda Gaussa-Jordana
    * **Metoda Doolittle'a** (rozkład LU)
    * Metoda Choleskiego
  * Iteracyjne (przybliżone):
    * Metoda Jacobiego
    * Metoda Gausa-Seidla

===== Rozkład LU =====

$$ \mathbf{A}\mathbf{x} = \mathbf{b}$$
$$ \mathbf{LU}\mathbf{x} = \mathbf{b}$$

Rozwiązanie dwóch prostszych problemów 
$$ \mathbf{L}\mathbf{y} = \mathbf{b}$$
$$ \mathbf{U}\mathbf{x} = \mathbf{y}$$
gdzie
$$\mathbf{L}=\left[\begin{array}{cccc}
1 & 0 & . . & 0 \\
l_{21} & 1 & . . & 0 \\
. . & . . & . . & . . \\
l_{n 1} & l_{n 2} & . . & 1
\end{array}\right] \quad \mathbf{U}=\left[\begin{array}{cccc}
u_{11} & u_{12} & . . & u_{1 n} \\
0 & u_{22} & . . & u_{2 n} \\
. . & . . & . . & . . \\
0 & . . & 0 & u_{n n}
\end{array}\right]$$

Tadeusz Banachiewicz 1938

===== =====

Z pierwszego układu $ \mathbf{L}\mathbf{y} = \mathbf{b}$ otrzymujemy wektor $\mathbf{y}$
$$\left\{\begin{array}{l}
y_{1}=b_{1} \\
y_{i}=b_{i}-\sum_{k=1}^{i-1} l_{i k} y_{k} \quad i=2,3, \ldots, n
\end{array}\right.$$

z drugiego $ \mathbf{U}\mathbf{x} = \mathbf{y}$ rozwiązanie $\mathbf{x}$
$$\left\{\begin{array}{l}
x_{n}=\frac{y_{n}}{u_{n n}} \\
x_{i}=\frac{y_{i}-\sum_{k=i+1}^{n} u_{i k} x_{k}}{u_{i i}} \quad i=n-1, n-2, \ldots, 1
\end{array}\right.$$

===== Metoda Doolitle'a =====

$$\mathbf{A}=\left[\begin{array}{llll}
a_{11} & a_{12} & a_{13} & a_{14} \\
a_{21} & a_{22} & a_{23} & a_{24} \\
a_{31} & a_{32} & a_{33} & a_{34} \\
a_{41} & a_{42} & a_{43} & a_{44}
\end{array}\right]=\left[\begin{array}{cccc}
1 & 0 & 0 & 0 \\
l_{21} & 1 & 0 & 0 \\
l_{31} & l_{32} & 1 & 0 \\
l_{41} & l_{42} & l_{43} & 1
\end{array}\right]\left[\begin{array}{rrrr}
u_{11} & u_{12} & u_{13} & u_{14} \\
0 & u_{22} & u_{23} & u_{24} \\
0 & 0 & u_{33} & u_{34} \\
0 & 0 & 0 & u_{44}
\end{array}\right]$$

$$=\left[\begin{array}{llll}
u_{11} & u_{12} & u_{13} & u_{14} \\
l_{21} u_{11} & l_{21} u_{12}+u_{22} & l_{21} u_{13}+u_{23} & l_{21} u_{14}+u_{24} \\
l_{31} u_{11} & l_{31} u_{12}+l_{32} u_{22} & l_{31} u_{13}+l_{32} u_{23}+u_{33} & l_{31} u_{14}+l_{32} u_{24}+u_{34} \\
l_{41} u_{11} & l_{41} u_{12}+l_{42} u_{22} & l_{41} u_{13}+l_{42} u_{23}+l_{43} u_{33} & l_{41} u_{14}+l_{42} u_{24}+l_{43} u_{34}+u_{44}
\end{array}\right]$$

===== =====

{{  zajecia:mn1_2021_2:lu_step1.png?800  |}}

wiersz 1  $$u_{11}=a_{11} \quad u_{12}=a_{12}  \quad u_{13}=a_{13} \quad u_{14}=a_{14}$$ 
kolumna 1 $$l_{21}=\frac{a_{21}}{u_{11}} \quad l_{31}=\frac{a_{31}}{u_{11}} \quad l_{41}=\frac{a_{41}}{u_{11}}$$

===== =====

{{  zajecia:mn1_2021_2:lu_step3.png?800  |}}

wiersz 2
$$u_{22}=a_{22}-l_{21} u_{12} \quad u_{23}=a_{23}-l_{21} u_{13} \quad u_{24}=a_{24}-l_{21} u_{14}$$

kolumna 2 
$$l_{32}=\left(a_{32}-l_{31} u_{12}\right) / u_{22} \quad l_{42}=\left(a_{42}-l_{41} u_{12}\right) / u_{22}$$

wiersz 3
$$u_{33}=a_{33}-l_{31} u_{13}-l_{32} u_{23} \quad u_{34}=a_{34}-l_{31} u_{14}-l_{32} u_{24}$$

kolumna 3
$$l_{43}=\left(a_{43}-l_{41} u_{13}-l_{42} u_{23}\right) / u_{33}$$

wiersz 4
$$u_{44}=a_{44}-l_{41} u_{14}-l_{42} u_{24}-l_{43} u_{34}$$

===== Algorytm rozkładu LU =====

  * Dla $i = 1, \ldots, n$
    * $ u_{ij}=0, \, l_{ji}=0, \qquad j = 1, \ldots, i-1$
    * $l_{ii} = 1 $
    * $u_{ij}=a_{ij}-\sum_{k=1}^{i-1} l_{ik} u_{kj}, \qquad j = i, \ldots, n$
    * $l_{ji}=\frac{a_{j i}-\sum_{k=1}^{i-1} l_{j k} u_{k i}}{u_{i i}}, \qquad j = i+1, \ldots, n$

Każdy element $a_{ij}$ wykorzystywany jest tylko raz, więc można wykorzystać miejsce w macierzy $\mathbf{A}$ do przechowania wartości $l_{ij}$ i $u_{ij}$

===== Zadanie =====

Napisz program, który korzystając z metody Doolittle'a rozkładu LU rozwiąże układ równań $\mathbf{A}\mathbf{x} = \mathbf{b}$, gdzie

$$\mathbf{A}=\left[\begin{array}{rrr}
1 & 4 & 1 \\
1 & 6 & -1 \\
2 & -1 & 2
\end{array}\right] \quad \mathbf{b}=\left[\begin{array}{r}
7 \\
13 \\
5
\end{array}\right]$$

Wypisz uzyskany wynik $\mathbf{x}$ oraz macierze $\mathbf{L}$ oraz $\mathbf{U}$. \\ 
Wyznacz wyznacznik macierzy $\mathbf{A}$, gdzie
$$\operatorname{det}(\mathbf{A})=\operatorname{det}(\mathbf{L} \mathbf{U})=\operatorname{det}(\mathbf{L}) \operatorname{det}(\mathbf{U})=\operatorname{det}(\mathbf{U}) = \prod_{i=1}^{n} u_{ii}$$

===== Dodatkowe ćwiczenia =====


**Ćw. 1**