METODY ITERACYJNE

METODY ITERACYJNE - polegają na iteracyjnym ulepszaniu przybliżonego rozwiązania do momentu osiągnięcia zadowalającej dokładności.


METODA GAUSSA-SEIDLA
Minimalizacja funkcji f(x) wzdłuż ortogonalnej bazy x1, x2,...,xn. Jest to minimalizacja funkcji w kierunku.
Zbieżność metody:
Jeżeli funkcja celu f(x) ma postać f(x) = 1/2 x^T A x to metoda Gaussa-Seidela jest zbieżna do punktu ekstremalnego x wtedy i tylko wtedy, gdy macierz A jest dodatnio określona.
      Gradient funkcji:     grad f = A x , stąd przesunięcie punktu w i-tej iteracji wynosi na podstawie warunku koniecznego na istnienie ekstremum w kierunku :

Z równania tego otrzymuje się l_i minimalizujące funkcję f(x) w kierunku xi:

aⁱ   - i-ty wiersz macierzy A,    a_ii   - odpowiedni element tej macierzy.
Wartość funkcji celu w punkcie wynosi:
,    a po podstawieniu poprzedniego równania:

Oznacza to, że wartość funkcji celu będzie malała w kolejnych iteracjach, gdyż a_ii > 0 dla A dodatnio określonej.
a) informacje wejściowe:
xo - punkt startowy
x1, x2,...,xn - baza wektorów ortogonalnych
eo - początkowa długość kroku
e_j - wymagana dokładność obliczeń minimum w j-tym kierunku
e_o - wymagana dokładność obliczeń globalnego minimum
n - liczba zmiennych niezależnych

b) algorytm obliczeń

1. dla j = 1, 2,...,n oblicz l_j minimalizujące
   oraz współrzędne nowego punktu
2. jeżeli kryterium zbieżności nie zostało spełnione podstaw x_j w miejsce x_o i wróć do (1).

METODA ITERACJI
W przypadku gdy liczba niewiadomych układu równań jest duża, rozwiązanie takiego układu metodami dokładnymi (np. metodą eliminacji Gaussa) staje się skomplikowane.  W takim razie dogodniejsze staje się wykorzystanie do obliczeń metod przybliżonych. Jedną z takich metod jest metoda iteracji. Pod względem czasu obliczeń metody iteracyjne mogą być lepsze od dokładnych dla macierzy rzadkich .

Dany jest układ równań

  

                                               

                                                                                     

                                            

                                            

po wprowadzeniu macierzy

                    ,              ,                ,

układ równań  można zapisać w postaci równania macierzowego

                                                                 Ax=b                                                          

Rozwiązujemy pierwsze równanie układu   względem x₁, drugie równanie względem  x₂  itd.  Zakładamy przy tym, że elementy na głównej przekątnej  a_ii0 (i=1, 2, ..., n). Otrzymujemy układ równoważny

                                             ,

                                            ,                               

                                               ,

                                           ,

gdzie

                                  ,              ,                dla      

oraz

                                           dla            i=j               i, j = 1, 2, ..., n .

Po wprowadzeniu macierzy

                                       oraz    

układ  równań (1.50) możemy zapisać w postaci

                                                                                                               

Aby rozwiązać układ równań, za przybliżenie zerowe przyjmujemy kolumnę wyrazów wolnych, czyli  bierzemy

                                                               

Tworzymy następnie macierze kolumnowe

                  

                                                                        - pierwsze przybliżenie

                                                         

                                                                        - przybliżenie drugie  i.t.d

                                                                  

Dowolne   (k+1)- sze przybliżenie obliczamy według wzoru

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

Iterację kończymy gdy  spełniony jest warunek

                                           ,          gdzie    oznacza zadaną dokładność.

Jeżeli ciąg przybliżeń   x⁽⁰⁾,  x⁽¹⁾, ..., x^(k), ...   ma granicę    , to granica ta jest rozwiązaniem układu równań .  

Ogólnie dla układu równań określonego wzorem

                                                        ,                       i = 1, 2, ..., n

można przyjąć   ,   gdzie  ,    ( i = 1, 2, ..., n ). Wówczas dany układ równoważny jest układowi

                                                        ,         i = 1, 2, ..., n ,

gdzie

          ,                  ,                   dla   .

Warunek dostateczny zbieżności.

Jeżeli dla układu równań sprowadzonego do postaci zachodzi co najmniej jeden z warunków:

 

                                                           i = 1, 2, ..., n ,

lub

                                                            j = 1, 2, ..., n ,

to proces iteracyjny      k = 0, 1, 2, ...   jest zbieżny do jednoznacznego rozwiązania, niezależnie od tego, jaki wybierzemy wektor początkowy. Zatem metoda iteracji jest zbieżna dla układu     i = 1, 2, ..., n,  jeżeli zachodzą następujące nierówności:  

  

                                                 i = 1, 2, ..., n,

czyli wtedy, gdy wartości bezwzględne współczynników na głównych przekątnych są dla każdego równania układu większe od sumy wartości bezwzględnych pozostałych współczynników tego równania (nie licząc wyrazów wolnych).