dr inż. Jerzy J. Jasielec

Rozwiązywanie numeryczne układów równań liniowych

PMiKNoM seminaria - zajęcia 4

Wstęp

Zastosowanie układów równań liniowych i metody ich rozwiązywania.

Metoda Gaussa

Zadania

Rozwiąż metodą Gauss'a następujące równania liniowe:

a) $$ \left[ \begin{array}{ccc|c} 2&2&1&1 \\ 1&3&2&2 \\ 2&4&2&2 \\ \end{array} \right] = $$

b) $$ \left[ \begin{array}{ccc|c} 2&3&4&2 \\ 4&5&6&3 \\ 3&2&3&5 \\ \end{array} \right] = $$

c) $$ \left[ \begin{array}{ccc|c} 2&2&2&2 \\ 21&2&2&2 \\ 2&22&2&2 \\ \end{array} \right] = $$

d) $$ \left[ \begin{array}{ccc|c} 2&4&0&2 \\ 1&4&1&2 \\ 0&1&1&3 \\ \end{array} \right] = $$

e) $$ \left[ \begin{array}{cccc|c} 2&3&0&0&1 \\ 1&2&1&0&2 \\ 0&3&2&4&5 \\ 0&0&1&3&4 \\ \end{array} \right] = $$

Macierz trójdiagonalna

Równanie ogólne macierzy trójdiagonalnej:

$$ \left\{ \begin{array}{l} d_1 x_1 + c_1 x_2 = b_1 \\ a_{i-1} x_{i-1} + d_i x_i + c_i x_{i+1} = b_i \text{, dla } i=2..n-1\\ a_{n-1} x_{n-1} + d_n x_n = b_n \end{array} \right. $$

$$ \left[ \begin{array}{ccccccccc|c} d_1 & c_1 & 0 & 0 & \cdots & 0 & 0 & 0 & 0 & b_1 \\ a_1 & d_2 & c_2 & 0 & \cdots & 0 & 0 & 0 & 0 & b_2 \\ 0 & a_2 & d_3 & c_3 & \cdots & 0 & 0 & 0 & 0 & b_3 \\ 0 & 0 & a_3 & d_4 & \cdots & 0 & 0 & 0 & 0 & b_4 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & d_{n-3} & c_{n-3} & 0 & 0 & b_{n-3} \\ 0 & 0 & 0 & 0 & \cdots & a_{n-3} & d_{n-2} & c_{n-2} & 0 & b_{n-2} \\ 0 & 0 & 0 & 0 & \cdots & 0 & a_{n-2} & d_{n-1} & c_{n-1} & b_{n-1} \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & a_{n-1} & d_n & b_n \\ \end{array} \right] $$

Metoda Thomasa - wyprowadzenie

Rozwiązanie macierzy trójdiagonalnej `n \times n` przedstawione zostanie na przykładzie układu `n=4` równań liniowych:

$$ \left[ \begin{array}{cccc|c} d_1 & c_1 & 0 & 0 & b_1 \\ a_1 & d_2 & c_2 & 0 & b_2 \\ 0 & a_2 & d_3 & c_3 & b_3 \\ 0 & 0 & a_3 & d_4 & b_4 \\ \end{array} \right] $$

Dzielimy wiersz pierwszy przez `d_1`, otrzymując:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ a_1 & d_2 & c_2 & 0 & b_2 \\ 0 & a_2 & d_3 & c_3 & b_3 \\ 0 & 0 & a_3 & d_4 & b_4 \\ \end{array} \right] $$

gdzie:

`\text{nowe } c_1=c_1/d_1 `

`\text{nowe } b_1=b_1/d_1 `

Od wiersza drugiego odejmujemy wiersz pierwszy pomnożony przez `a_1`, otrzymując:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & d_2 & c_2 & 0 & b_2 \\ 0 & a_2 & d_3 & c_3 & b_3 \\ 0 & 0 & a_3 & d_4 & b_4 \\ \end{array} \right] $$

gdzie:

` \text{nowe } d_2=d_2 - c_1 \cdot a_1 `

` \text{nowe } b_2=b_2 - b_1 \cdot a_1 `

W ten sposób, w pierwszej kolumnie otrzymujemy 1 na przekątnej i 0 pod przekątną.

Analogicznie postępujemy dla drugiej kolumny otrzymując:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & d_3 & c_3 & b_3 \\ 0 & 0 & a_3 & d_4 & b_4 \\ \end{array} \right] $$

gdzie:

` \text{nowe } c_2=c_2/d_2 `

` \text{nowe } b_2=b_2/d_2 `

` \text{nowe } d_3=d_3 - c_2 \cdot a_2 `

` \text{nowe } b_3=b_3 - b_2 \cdot a_2 `

Analogicznie postępujemy dla trzeciej kolumny otrzymując:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & c_3 & b_3 \\ 0 & 0 & 0 & d_4 & b_4 \\ \end{array} \right] $$

gdzie:

` \text{nowe } c_3=c_3/d_3 `

` \text{nowe } b_3=b_3/d_3 `

` \text{nowe } d_4=d_4 - c_3 \cdot a_3 `

` \text{nowe } b_4=b_4 - b_3 \cdot a_3 `

Następnie dzielimy ostatni wiersz przez `d_4`, otrzymując:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & c_3 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$

gdzie:

` \text{nowe } b_4=b_4/d_4 `

Aby wyzerować wartość od trzeciego (przedostatniego) wiersza należy odjąć ostatni pomnożony przez `c_3`, otrzymując:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & 0 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$

gdzie:

` \text{nowe } b_3 = b_3 - c_3 \cdot b_4 `

Analogicznie postępujemy dla pozostałych wierszy, otrzymując:

$$ \left[ \begin{array}{cccc|c} 1 & 0 & 0 & 0 & b_1 \\ 0 & 1 & 0 & 0 & b_2 \\ 0 & 0 & 1 & 0 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$

gdzie:

` \text{nowe } b_2= b_2 - c_2 \cdot b_3`

` \text{nowe } b_1= b_1 - c_1 \cdot b_2`

Metoda Thomasa - podsumowanie

Pierwsza pętla

Po wykonaniu zestawu analogicznych operacji dla wierszy `(i)` od pierwszego `(1)` do przedostatniego `(n-1)` otrzymujemy:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & c_3 & b_3 \\ 0 & 0 & 0 & d_4 & b_4 \\ \end{array} \right] $$

po wykonaniu `i=1` do `n-1` zestawów operacji:

$$ \left\{ \begin{array}{l} c_i=c_i/d_i \\ b_i=b_i/d_i \\ d_{i+1}=d_{i+1} - c_i \cdot a_i \\ b_{i+1}=b_{i+1} - b_i \cdot a_i \end{array} \right. $$

Instrukcja

Następnie ostatni wiersz dzielimy przez `d_n`, otrzymując:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & c_3 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$

po wykonaniu:

` b_n=b_n/d_n `

Druga pętla

Po wykonaniu zestawu analogicznej operacji dla wierszy `(i)` od przedostatniego `(n-1)` pierwszego `(1)` z krokiem `(-1)` otrzymujemy:

$$ \left[ \begin{array}{cccc|c} 1 & 0 & 0 & 0 & b_1 \\ 0 & 1 & 0 & 0 & b_2 \\ 0 & 0 & 1 & 0 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$

po wykonaniu `i=n-1` do `1` (krok `-1`) operacji:

$$ b_i = b_i - c_i \cdot b_{i+1} $$

Metoda Thomasa - algorytm programu

Zadeklaruj stałą `n` oraz tablice `a(1 \text{ to } n-1)`, `d(1 \text{ to } n)`, `c(1 \text{ to } n-1)` oraz `b(1 \text{ to } n)`.
Przypisz wartości z arkusza do wszystkich elementów tablic `a`, `b`, `c` oraz `d`.
Wykonaj pierwszą pętlę (patrz wyprowadzenie).
Wykonaj instrukcję `b(n)=b(n) \text{/} d(n)`.
Wykonaj drugą pętlę (patrz wyprowadzenie).
Wyświetl wyniki.

Dodatkowe materiały:

Skrypt: R. Filipek, K. Szyszkiewicz-Warzecha "Metody Matematyczne dla Ceramików", strony 1-4 oraz 8-10.
Wikipedia - Eliminacja Gaussa