Metody iteracyjne rozwiązywania liniowych układów równań

1. Normy wektorów i macierzy

    Niech Rn będzie przestrzenią liniową wektorów n-wymiarowych

        xT=(x1,…,xn) i xjR j=1(1)n.

     Natomiast Rn´m będzie przestrzenią liniową macierzy

        A=(aij)i=1(1)n,j=1(1)m  aijR i =1(1)n, j=1(1)m

     W Rn wyróżniamy normy

1.    

2.    

3.    

     W Rn´n wyróżniamy normy wektora

               - normy indukowane przez normę wektora, tzn.:

                  

              Przykłady norm indukowanych

                   ·   

                   ·      

                   ·   

               - normy zgodne z normą wektora, tzn.:

                  

                 Normy indukowane podane wyżej są zgodne z normami wektorów.

2. Metody iteracyjne dla Ax=b. Warunki zbieżności

    Jedną z najprostszych metod iteracyjnych jest metoda iteracji prostej. Polega ona na przejściu od danego układu równań liniowych

                

    do równoważnego (tzn. mającego te same rozwiązania) układu

             

    Znając postać układu równoważnego wyznaczamy ciąg {xi} przybliżeń rozwiązania α=A-1b ze wzoru:

                 i=0,1,…

    Zanim rozpatrzymy konkretne warianty metody iteracyjnej prostej, definiowane różnymi sposobami przejścia od układu Ax=b do układu     równoważnego x=Bx+c, zajmijmy się zbadaniem warunków zbieżności ciągu {xi}.

    Zakładamy, że układy są równoważne, zatem jeżeli Aα=b, to

             

    Odejmując to równanie stronami od równania z równania definiującego ciąg {xi} otrzymujemy

               

    a stąd

             

    Przechodząc do norm otrzymujemy oszacowania

             

    

   Z nierówności tych wynika

Lemat

Dla zbieżności ciągu {xi} zdefiniowanego wzorem  wystarcza, aby dowolna norma macierzy B zgodna z jakąkolwiek z norm wektorowych była mniejsza od jedności.

   Dla wielu norm sprawdzenie nierówności  jest łatwe. Niestety na ogół trudniejsze jest stwierdzić czy spełniony jest warunek konieczny i dostateczny zbieżności iteracji prostej. Zachodzi bowiem

Twierdzenie

Zależność  określa ciąg {xi} zbieżny do rozwiązania α przy dowolnym przybliżeniu początkowym x0 wtedy i tylko wtedy, gdy ρ(B)<1

gdzie  nazywamy promieniem spektralnym macierzy B

Przejdźmy teraz do wybranego wariantu metody iteracji prostej, tj. do metody Gaussa-Seidla. Przedstawmy macierz wyjściowego układu w postaci

             

gdzie  D=diag(aii) jest macierzą diagonalną, zaś L=(aij)i>j i U=(aij)i<j są macierzami dolną i górną trójkątną o zerowych elementach diagonalnych. Rozwiązywany układ Ax=b możemy zapisać jako

             

a stąd

             

Jeśli macierz L+D jest nieosobliwa, to możemy przejść do układu równoważnego

               

gdzie

             

Przykłady rozwiązywania układów metodą Gaussa-Seidla

Algorytm numeryczny

 

 

Strona główna