Edytuj stronę Odnośniki Fold/unfold all ODT export Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić. ~~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 <code 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(); } } </code> ===== ===== Wypisywanie zawartości macierzy <code C> #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"); } } </code> ===== Fragment eliminacji ===== <code C> k = 0; // numer kroku (eliminacja pierwszej kolumny) i = k + 1; // numer wiersza z eliminowanym elementem for(j=k+1; j<nk; j++) { A[i][j] = A[i][j] - A[i][k] * A[k][j] / A[k][k]; } A[i][k] = 0.0; // znamy wynik, wiec nie obliczamy A[i][k] </code> 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.