Metody numeryczne

LABORATORIUM 3
Grupa NP, wtorek 19.03.2024, godz 12:15

Metody numeryczne - laboratorium 3

Napisz skrypt, który, korzystając z metody Gaussa, dokona redukcji poniższego układu:

\(9 x_1 + 8 x_2 - 2 x_3 + 2 x_4 - 2 x_5 = 21\\ 7 x_1 - 3 x_2 - 2 x_3 + 7 x_4 + 2 x_5 = 11\\ 2 x_1 - 2 x_2 + 2 x_3 - 7 x_4 + 6 x_5=-4\\ 4 x_1 + 8 x_2 - 3x_3 + 3 x_4 - x_5 = 16\\ 2 x_1 + 2 x_2 - x_3 + x_4 + 4 x_5 = 9 \)

do postaci z macierzą trójkątną górną.

Wymagania odnośnie zadania (w nawiasach podana punktacja):

  1. Skrypt ma przekształcić układ do postaci, w której możliwe będzie rozwiązanie równań rekurencyjnie, tzn. lewa strona równań, tworząca macierz współczynników, będzie macierzą trójkątną górną. Do redukcji układu należy użyć metody eliminacji Gaussa opisanej na Wykładzie nr 3 na slajdach od 17 do 24. [1p]

  2. Algorytm powinien być napisany na tyle elastycznie, by działał poprawnie także dla macierzy o innych wymiarach niż ta z treści zadania (pomocna będzie metoda shape). Elastyczność oznacza także, że program musi zostać zapisany w postaci zestawu pętli automatyzujących proces redukcji, przy czym preferowane są dwie zagnieżdżone pętle, a zamiast trzeciej program powinien korzystać z z możliwości odwołania sie do całego wiersza jednocześnie. Wynikiem działania skryptu ma być wyświetlenie na ekranie (w czytelny sposób) macierzy współczynników macierzy trójkątnej górnej i nowego wektora wyrazów wolnych po zakończeniu eliminacji. [2p.]

  3. Po rozwiązaniu powyższego zadania należy rozwiązac układ z macierzą trójkątną górną za pomocą algorytmu przedstawionego na stronie 14 oraz poniżej. [1p.]

  4. Należy sprawdzić poprawność rozwiązania układu równan, gdzie $\mathbf{A}$ to macierz współczynników a $\mathbf{b}$ to kolumnowy wektor wyrazów wolnych, korzystając z funkcji np.linalg.solve(A, b).[1p.]

ALGORYTM SPROWADZANIA DO MACIERZY TRÓJKĄTNEJ GÓRNEJ

Dany jest układ równań \(\mathbf{A}^{(1)}\mathbf{x} = \mathbf{b}^{(1)}\), tzn:

\(a_{11}^{(1)}x_1 + a_{12}^{(1)}x_2 + \ldots a_{1n}^{(1)}x_n = b_1^{(1)}\\ a_{21}^{(1)}x_1 + a_{22}^{(1)}x_2 + \ldots + a_{2n}^{(1)}x_n = b_2^{(1)}\\ \ldots\\ a_{n1}^{(1)}x_1 + a_{n2}^{(1)}x_2 + \ldots + a_{nn}^{(1)}x_n = b_n^{(1)} \)

Po odjęciu od \(i\)-tego wiersza (\(i = 2, 3, \ldots,n\)) wiersza pierwszego, pomonożonego przez

\(m_{i1} = \frac{a_{i1}^{(1)}}{a_{11}^{(1)}}\)

otrzymujemy układ równań \(\mathbf{A}^{(2)}\mathbf{x} = \mathbf{b}^{(2)}\):

\(a_{11}^{(2)}x_1 + a_{12}^{(2)}x_2 + \ldots a_{1n}^{(2)}x_n = b_1^{(2)}\\ 0 \cdot x_1 + a_{22}^{(2)}x_2 + \ldots + a_{2n}^{(2)}x_n = b_2^{(2)}\\ \ldots\\ 0 \cdot x_1 + a_{n2}^{(2)}x_2 + \ldots + a_{nn}^{(2)}x_n = b_n^{(2)} \)

Podobnie w następnym kroku odejmujemy od \(i\)-tego wiersza (\(i = 3, 4, \ldots,n\)) wiersz drugi, pomonożony przez

\(m_{i2} = \frac{a_{i2}^{(2)}}{a_{22}^{(2)}}\)

W efekcie otrzymujemy kolejne układy równań \(\mathbf{A}^{(3)}\mathbf{x} = \mathbf{b}^{(4)}\), \(\mathbf{A}^{(4)}\mathbf{x} = \mathbf{b}^{(4)}\) etc i po \(n-1\) eliminacjach uzyskujemy trójkatny układ równań \(\mathbf{A}^{(n)}\mathbf{x} = \mathbf{b}^{(n)}\) postaci

\(a_{11}^{(n)}x_1 + a_{12}^{(n)}x_2 + \ldots a_{1n}^{(n)}x_n = b_1^{(n)}\\ 0 \cdot x_1 + a_{22}^{(n)}x_2 + \ldots a_{2n}^{(n)}x_n = b_2^{(n)}\\ 0 \cdot x_1 + 0 \cdot x_2 + \ldots a_{3n}^{(n)}x_n = b_3^{(n)}\\ \ldots\\ 0 \cdot x_1 + \ldots + 0 \cdot x_{n-1} + a_{nn}^{(n)}x_n = b_n^{(n)} \)

ALGORYTM ROZWIĄZANIA RÓWNANIA Z MACIERZĄ TRÓJKĄTNĄ GÓRNĄ
$x_n = \frac{b_n}{a_{nn}}$
$x_{i} = \frac{b_i - \sum\limits_{j=i+1}^{j=n}a_{ij}x_j}{a_{ii}}$   dla $i=n-1,n-2,...,1$