~~NOCACHE~~
~~REVEAL theme=simple&size=1024x800~~
====== Lab. 10 Rozwiązywanie układów równań liniowych ======
===== Układ równań ====
$$
\left\{
\begin{array}{c}
2 x+y-z=8 \\
-3 x-y+2 z=-11 \\
-2 x+y+2 z=-3
\end{array}
\right.$$
Zapis macierzowy $$\mathbf{Ax}=\mathbf{b}$$ gdzie
$$
\mathbf{A}=\left(\begin{array}{ccc}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{array}\right) \quad \mathbf{x}=\left(\begin{array}{l}
x \\
y \\
z
\end{array}\right) \quad \mathbf{b}=\left(\begin{array}{c}
8 \\
-11 \\
-3
\end{array}\right)
$$
===== =====
Poszukujemy $\mathbf{x}$ rozwiązując $n$ równań z $n$ niewiadomymi
$$\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 Choleskiego
* Iteracyjne (przybliżone):
* Metoda Jacobiego
* Metoda Gausa-Seidla
===== Eliminacja Gaussa =====
Metoda eliminacji Gaussa polega na sprowadzeniu układu równań do postaci zawierającej mnożenie macierzy trójkątnej
$$
\begin{array}{r}
x_{1}+x_{2}-x_{3}+4 x_{4}=8 \\
-2 x_{2}-3 x_{3}+x_{4}=5 \\
2 x_{3}-3 x_{4}=0 \\
2 x_{4}=4
\end{array}$$
wówczas $x_4 = \frac{4}{2}\qquad x_3 = \frac{3 x_4}{2} \ldots $ \\
ogólnie $x_{n}=\frac{b_{n}}{a_{n n}}$ oraz $x_{i}=\frac{b_{i}-\sum_{j=i+1}^{j=n} a_{i j} x_{j}}{a_{i i}}$ dla $i = n-1, n-2, \ldots, 1$
===== =====
Sprowadzenie macierzy $A$ do postaci trójkątnej - eliminacja kolumn.
$$\begin{array}{cccccccccc}
a_{11}^{(1)} x_{1} & + & a_{12}^{(1)} x_{2} & + & a_{13}^{(1)} x_{3} & + & \cdots & + & a_{1 n}^{(1)} x_{n} & = & b_{1}^{(1)} \\
a_{21}^{(1)} x_{1} & + & a_{22}^{(1)} x_{2} & + & a_{23}^{(1)} x_{3} & + & \cdots & + & a_{2 n}^{(1)} x_{n} & = & b_{2}^{(1)} \\
a_{31}^{(1)} x_{1} & + & a_{32}^{(1)} x_{2} & + & a_{33}^{(1)} x_{3} & + & \cdots & + & a_{3 n}^{(1)} x_{n} & = & b_{3}^{(1)} \\
\vdots & & \vdots & & \vdots & & \ddots & & \vdots & & \vdots \\
a_{n 1}^{(1)} x_{1} & + & a_{n 2}^{(1)} x_{2} & + & a_{n 3}^{(1)} x_{3} & + & \cdots & + & a_{m n}^{(1)} x_{n} & = & b_{n}^{(1)}
\end{array}$$
Mnożymy pierwsze równanie przez $\frac{a_{i 1}^{(1)}}{a_{11}^{(1)}}$ i odejmujemy od $i$-tego równania
===== =====
Po wyeliminowaniu pierwszej kolumny
$$
\begin{aligned}
a_{11}^{(1)} x_{1}+a_{12}^{(1)} x_{2}+a_{13}^{(1)} x_{3}+\cdots+a_{1 n}^{(1)} x_{n} & =b_{1}^{(1)} \\
a_{22}^{(2)} x_{2}+a_{23}^{(2)} x_{3}+\cdots+a_{2 n}^{(2)} x_{n} & =b_{2}^{(2)} \\
a_{32}^{(2)} x_{2}+a_{33}^{(2)} x_{3}+\cdots+a_{3 n}^{(2)} x_{n} & =b_{3}^{(2)} \\
& \vdots \\
a_{n 2}^{(2)} x_{2} +a_{n 3}^{(2)} x_{3}+\cdots+ a_{n n}^{(2)} x_{n} &= b_{n}^{(2)}
\end{aligned}$$
gdzie
$$a_{i j}^{(2)}=a_{i j}^{(1)}-\frac{a_{i 1}^{(1)} a_{1 j}^{(1)}}{a_{11}^{(1)}}, \quad b_{i}^{(2)}=b_{i}^{(1)}-\frac{a_{i 1}^{(1)} b_{1}^{(1)}}{a_{11}^{(1)}} \quad(i, j=2,3, \ldots, n)$$
===== =====
Po $n-1$ krokach eliminujących kolejne kolumny
$$\begin{aligned}
a_{11}^{(1)} x_{1}+a_{12}^{(1)} x_{2}+a_{13}^{(1)} x_{3}+\cdots+a_{1 n}^{(1)} x_{n} & =b_{1}^{(1)} \\
a_{22}^{(2)} x_{2}+a_{23}^{(2)} x_{3}+\cdots+a_{2 n}^{(2)} x_{n} & =b_{2}^{(2)} \\
a_{33}^{(3)} x_{3}+\cdots+a_{3 n}^{(3)} x_{n} & =b_{3}^{(3)} \\
& \vdots \\
a_{n n}^{(n)} x_{n} & =b_{n}^{(n)}
\end{aligned}$$
===== Ogólny schemat =====
Wektor $\mathbf{b}$ dla wygody dołączamy jako $n+1$ kolumnę do macierzy $\mathbf{A}$, tj. $a_{i, n+1} = b_i$
$$\left[\begin{array}{ccccc|c}
a_{11} & a_{12} & a_{13} & \cdots & a_{1 n} & b_{1} \\
0 & a_{22} & a_{23} & \cdots & a_{2 n} & b_{2} \\
0 & 0 & a_{33} & \cdots & a_{3 n} & b_{3} \\
\vdots & \vdots & \vdots & & \vdots & \vdots \\
0 & 0 & 0 & \cdots & a_{n n} & b_{n}
\end{array}\right]$$
===== =====
Eliminacja $k$-tej kolumny (gdzie $k = 1, 2, \ldots, n-1$)
$$a_{i j}{ }^{(k)}=a_{i j}{ }^{(k-1)}-\frac{a_{i k}{ }^{(k-1)}}{a_{k k}{ }^{(k-1)}} a_{k j}{ }^{(k-1)} \qquad
\begin{array}{l}
i = k+1, \ldots, n \\
j = k+1, \ldots, n+ 1 \\
\end{array}
$$
Rozwiązanie
$$x_{i}=\frac{1}{a_{ii}}\left(a_{i, n+1}-\sum_{j=i+1}^{n} a_{ij} \cdot x_{j}\right) \qquad i=n, n-1, \ldots, 1$$
===== Macierze w C =====
Macierze w języku C
// deklaracja tablicy 2-wymiarowej
double A[4][3];
for(int i=0; i<4; i++)
{
for(int j=0; j<3; j++)
{
A[i][j] = rand();
}
}
===== =====
Wypisywanie zawartości macierzy
#define MAX 100
typedef double matrix[MAX][MAX];
void print_matrix(matrix A, int w, int k)
{
printf("\nMacierz %dx%x\n", w, k);
for(int i=0; i< w;i++)
{
for(int j=0; j< k; j++)
printf(" %5.1lf", A[i][j]);
printf("\n");
}
}
===== Fragment eliminacji =====
k = 0; // numer kroku (eliminacja pierwszej kolumny)
i = k + 1; // numer wiersza z eliminowanym elementem
for(j=k+1; j
Przykładowy kod {{zajecia:mn1_2021_2:gauss_elim.c|}}
===== Pivoting =====
W eliminacji Gaussa musimy zapewnić aby
$$a_{k k}{ }^{(k-1)} \neq 0$$
Również gdy $a_{k k}{ }^{(k-1)} \approx 0 $ to mogą pojawić się istotne błędy numeryczne
**Wybór elementu głównego** (pivoting): w $k$-tym kroku wybieramy element $|a_{ij}|$ dla $i,j=k+1, k+2, \ldots, n$ i zamieniamy kolumnę w której on występuje z kolumną $k$ oraz wiersz w którym on występuje z wierszem $k$.
Po czym kontynuujemy eliminację kolejnej kolumny.
===== =====
{{zajecia:mn1_2021_2:elim_gauss_pivoting.png?500|}}
===== Zadanie 9 =====
Treść zadania znajduje się w Moodle pod adresem [[https://moodle.umk.pl/WFAIIS/mod/assign/view.php?id=4837|Zadanie 9]]
===== Dodatkowe ćwiczenia =====
**Ćw. 1**
Wiedząc, że $\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}$ napisz program, który wykorzystując eliminację Gaussa wyznaczy macierz odwrotną $\mathbf{A}^{-1}$
dowolnej (podanej przez użytkownika) macierzy kwadratowej $\mathbf{A}$. Rozwiązanie zadania sprowadza się do rozwiązanie $k$ układów równań, gdzie wektorem wyrazów wolnych jest wektor posiadający $1$ na $k$-tej pozycji (kolumna macierzy jednostkowej) a rozwiązaniem jest $k$-ta kolumna macierzy odwrotnej.