Metody numeryczne - laboratoria 8 (Rozwiązywanie układów równań liniowych - metody przybliżone)

1. Metody dokładne dają bardzo istotne błędy zaokrągleń dla większych macierzy (co czyni je mało użytecznymi dla macierzy większych niż 30, 40 równań) - dlatego wykorzystuje się metody iteracyjne. Czasami też wykorzystuje się iteracyjne poprawianie wyniku uzyskanego metodą Gaussa.

2. Problem - rozwiązać układ równań

3. Układ zapisany w postaci macierzowej:

Ax = b

4. Przypomnienie - metoda iteracyjna - poszukiwania zer funkcji

Równanie f(x) = 0 przekształcamy do x = g(x), i iterujemy aż do osiągnięcia zbieżności:

x^(k+1) = g(x^(k))

x⁽⁰⁾ - punkt początkowy

Uwaga! Metoda zbieżna tylko w niektórych przypadkach (dodatkowe warunki na g - przekształcenie zwężające, spełniające warunek Lipschitza (stała z przedziału (0,1)).

5. Analogicznie - wykorzystanie iteracji prostej dla rozwiązania układu równań liniowych

Ax = b -> x = Bx + c

x⁽⁰⁾ - przybliżenie początkowe

x^(k+1) = Bx^(k) + c

6. Metoda Richardsona (R)

Wyprowadzenie:

Ax = b / p≠0

pAx = pb, x +pAx = x + pb

x = x - pAx + pb, x = (I - pA)x + pb

Czyli

B_R = I - pA, c_r = pb

Dla k = 0, 1, 2....

Dla i = 1,...,n

7. Metoda Jacobiego

A = L + D + U (dolna, diagonalna, górna) D = diag(a_ii)

x = -D^-1(L + U)x + D^-1b

Dla k = 0, 1, 2....

Dla i = 1,...,n

8. Metoda Gaussa-Seidla

A = L + D + U (dolna, diagonalna, górna) D = diag(a_ii)

x = -(L + D)^-1Ux + (L+D)^-1b

Dla k = 0, 1, 2....

Dla i = 1,...,n

9. Metoda SOR (succesive over-relaxation)

A = L + D + U (dolna, diagonalna, górna) D = diag(a_ii)

x = (D+ωL)^-1 ((1-ω)D- ωU)x + ω (D+ ωL)^-1b

0 ≤ ω ≤ 2

dla ω = 1 - metoda Gaussa-Seidla

Dla k = 0, 1, 2....

Dla i = 1,...,n

10. Wartości własne macierzy:

Wartości x, λ dla niezerowego λ tworzą wartość własną i wektor własny macierzy A.

Ax = λx

Tw. Metoda iteracji prostej dla układu x = Bx + c jest zbieżna przy dowolnym x⁽⁰⁾ wtedy i tylko wtedy, gdy ρ(B) < 1, gdzie

- promień spektralny macierzy

11. Szybkość zbieżności

dla dużych k - można przyjąć:

uwaga: szacowanie - „w przybliżeniu mniejsze-równe”

norma 2 wektora - pewna norma dla wektora (maksimum pierwiastków wartości własnych ze spektrum iloczynu macierzy sprzężonej do B i macierzy B)

12. Kryteria stopu

|| x^(k+1) - x^(k)|| < ε, może być mało dokładny w przypadku powolnej zbieżności

wtedy lepszy

13. Zadanie dla studentów:

1. Wygenerowanie układów równań (za pomocą mnożenia macierzy przez wektor)

2. Rozwiązanie układu równań metodami Richardsona i Jacobiego

---