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<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]

Przykładowy kod 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.

Zadanie 9

Treść zadania znajduje się w Moodle pod adresem 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.