Metody iteracyjne.docx

                                                                                                               11.06.2012 r.
 

Politechnika Rzeszowska
Ignacego Łukasiewicza
Wydział Budowy Maszyn i Lotnictwa

Katedra Samolotów i Silników Lotniczych

Metody numeryczne w budowie i eksploatacji konstrukcji lotniczych

Metoda Jacobiego i Gaussa-Seidla

Jacek Kaczmarek

              Katarzyna Kozendra

              Łukasz Krawczyk

Tomasz Miziniak

Kamil Piotrowski

Łukasz Rupar

I MDLiK-B

1.     Wstęp teoretyczny

Zarówno metoda Jacobiego, jak i metoda Gaussa-Seidla są metodami iteracyjnymi pozwalającymi obliczyć układ n równań z n niewiadomymi Ax = b. Wektor x0 będący początkowym przybliżeniem rozwiązania układu będzie dany (zwykle przyjmuje się go jako wektor złożony z samych zer). By zastosować tą metodę należy najpierw tak zamienić kolejność równań układu, aby na głównej przekątnej były elementy różne od zera.

Na początku macierz współczynników A rozłożymy na sumę trzech macierzy A = L + D + U, gdzie L jest macierzą w której znajdują się elementy których numer wiersza jest większy od numeru kolumny, D to macierz diagonalna z elementami tylko na głównej przekątnej, a U to macierz, w której znajdują się elementy których numery wiersza są mniejsze od numerów kolumny. Można to zapisać następująco:

A = L + D + U                                                                             

Różnice między metodami:

Głowna różnica pomiędzy tymi metodami polega na zastosowaniu innego wzoru służącego do obliczania kolejnych przybliżeń:

·         metoda Jacobiego- kolejne przybliżenia oblicza się z następującego wzoru:

xn+1=Mxn+Nb

gdzie:

M = I – NA

N - pewna macierz kwadratowa

I - macierz jednostkowa

W metodzie Jacobiego przyjmujemy, że N=D-1, to wówczas M = -D-1(L+U). By zastosować tą metodę należy najpierw tak zamienić kolejność równań układu, aby na głównej przekątnej były elementy różne od zera. Macierz D-1 otrzymamy po podniesieniu do potęgi „-1” wszystkich wartości na głównej przekątnej macierzy D. Metoda ta jest zbieżna dla dowolnego przybliżenia początkowego rozwiązania x0, jeśli promil spektralny –D-1(L+U) jest mniejszy od jeden (promień spektralny to największa wartość bezwzględna z wartości własnej macierzy). W przeciwnym wypadku nie dla każdego przybliżenia początkowego otrzymamy rozwiązanie układu.

·         metoda Gaussa-Seidla- kolejne przybliżenia oblicza się z następującego wzoru:

xn+1=D-1b-D-1Lxn+1-D-1Uxn

Metoda Gaussa-Seidla bazuje na metodzie Jacobiego, w której krok iteracyjny zmieniono w ten sposób, by każda modyfikacja rozwiązania próbnego korzystała ze wszystkich aktualnie dostępnych przybliżonych składowych rozwiązania. Pozwala to zaoszczędzić połowę pamięci operacyjnej i w większości zastosowań praktycznych zmniejsza ok. dwukrotnie liczbę obliczeń niezbędnych do osiągnięcia zadanej dokładności rozwiązania.

Przykład:
Obliczymy następujący układ równań:

4x1-x2-0,2x3+2x4=30-1x1+5x2-2x4=00,2x1+x2+10x3-x4=-10-2x2-x3+4x4=5

Zapiszmy go teraz w postaci Ax=b:

4-1-0,22-150-20,2110-10-2-14x1x2x3x4=300-105

Podzielmy teraz macierz A na sumę macierzy L+D+U:

4-1-0,22-150-20,2110-10-2-14=0000-10000,21000-2-10+40000500001000004+0-1-0,22000-2000-10000

Obliczmy teraz macierz N=D-1:

40000500001000004=0,2500000,200000,100000,25-1

Do tego momentu obie metody się nie różnią.

·         Metoda Gaussa-Seidla:

Wyznaczamy kolejno D-1b, D-1L, D-1U:

7,50-11,25  0000-0,20000,020,1000-0,5-0,250  0-0,25-0,050,5000-0,4000-0,10000

Rozpoczynamy od zerowego przybliżenia czyli:

x10=0, x20=0, x30=0, x40=0

Obliczmy pierwszą iterację metody, według przytoczonego na początku wzoru:

x11=7,5+0,25x20+0,05x30-0,5x40x11=7,5x21=0+0,2x11+0,4x40x21=1,5x31=-1-0,2x11-0,1x21+0,1x40x...