Prosta metoda iteracyjna rozwiązywania układów równań liniowych (slough). Numeryczne rozwiązywanie układów liniowych równań algebraicznych

Prosta metoda iteracyjna polega na zastąpieniu pierwotnego równania równaniem równoważnym:

Niech będzie znane początkowe przybliżenie pierwiastka x = x 0. Podstawiając go do prawej strony równania (2.7) otrzymujemy nowe przybliżenie , to w podobny sposób otrzymujemy itp.:

. (2.8)

Nie we wszystkich warunkach proces iteracyjny zbiega się do pierwiastka równania X. Przyjrzyjmy się bliżej temu procesowi. Rysunek 2.6 przedstawia graficzną interpretację jednokierunkowego procesu zbieżnego i rozbieżnego. Rysunek 2.7 przedstawia dwukierunkowe procesy zbieżne i rozbieżne. Proces rozbieżny charakteryzuje się szybkim wzrostem wartości argumentu i funkcji oraz nieprawidłowym zakończeniem odpowiedniego programu.

W procesie dwukierunkowym możliwa jest cykliczność, czyli nieskończone powtarzanie tej samej funkcji i wartości argumentów. Pętla oddziela proces rozbieżny od zbieżnego.

Z wykresów jasno wynika, że ​​zarówno w przypadku procesów jednostronnych, jak i dwustronnych o zbieżności do pierwiastka decyduje nachylenie krzywej w pobliżu pierwiastka. Im mniejsze nachylenie, tym lepsza zbieżność. Jak wiadomo, tangens nachylenia krzywej jest równy pochodnej krzywej w danym punkcie.

Dlatego im mniejsza liczba w pobliżu pierwiastka, tym szybciej proces jest zbieżny.

Aby proces iteracji był zbieżny, w pobliżu pierwiastka musi być spełniona nierówność:

Przejście z równania (2.1) do równania (2.7) można przeprowadzić na różne sposoby w zależności od rodzaju funkcji f(x). W takim przejściu należy tak skonstruować funkcję, aby spełniony był warunek zbieżności (2.9).

Rozważmy jeden z ogólnych algorytmów przejścia od równania (2.1) do równania (2.7).

Pomnóżmy lewą i prawą stronę równania (2.1) przez dowolną stałą B i dodaj niewiadomą do obu części X. W tym przypadku pierwiastki pierwotnego równania nie ulegną zmianie:

Wprowadźmy notację i przejdźmy od zależności (2.10) do równania (2.8).

Dowolny wybór stałej B zapewni spełnienie warunku zbieżności (2.9). Kryterium zakończenia procesu iteracyjnego będzie warunek (2.2). Rysunek 2.8 przedstawia graficzną interpretację metody prostych iteracji z wykorzystaniem opisanego sposobu reprezentacji (skale wzdłuż osi X i Y są różne).

Jeśli wybrano funkcję w postaci , to pochodną tej funkcji będzie . Największa prędkość zbieżności będzie wtedy a wzór iteracyjny (2.11) przechodzi do wzoru Newtona. Tym samym metoda Newtona charakteryzuje się najwyższym stopniem zbieżności ze wszystkich procesów iteracyjnych.

Implementacja programowa prostej metody iteracyjnej odbywa się w formie podprogramu Iteras(PROGRAM 2.1).

Cała procedura składa się praktycznie z jednego cyklu Powtórz…Do, realizując formułę (2.11) uwzględniającą warunek zatrzymania procesu iteracyjnego (wzór (2.2)).

Procedura ma wbudowaną ochronę pętli poprzez zliczanie liczby pętli za pomocą zmiennej Niter. Na zajęciach praktycznych należy się upewnić uruchamiając program jak wpływa na to wybór współczynnika B i wstępne przybliżenie w procesie poszukiwania pierwiastka. Przy zmianie współczynnika B zmienia się charakter procesu iteracyjnego dla badanej funkcji. Najpierw staje się dwustronny, a następnie pętle (ryc. 2.9). Skale osi X I Y są różne. Jeszcze większa wartość modułu b prowadzi do procesu rozbieżnego.

Porównanie metod przybliżonego rozwiązywania równań

Porównanie opisanych powyżej metod numerycznego rozwiązywania równań przeprowadzono przy pomocy programu umożliwiającego obserwację procesu znajdowania pierwiastka w formie graficznej na ekranie komputera PC. Procedury zawarte w tym programie i wdrażające porównywane metody podano poniżej (PROGRAM 2.1).

Ryż. 2.3-2.5, 2.8, 2.9 to kopie ekranu komputera PC na koniec procesu iteracji.

We wszystkich przypadkach za badaną funkcję przyjęto równanie kwadratowe x 2 -x-6 = 0, mające rozwiązanie analityczne x 1 = -2 i x 2 = 3. Założono, że błąd i przybliżenia początkowe są równe dla wszystkich metod. Wyniki wyszukiwania rootów x= 3, przedstawione na rysunkach, są następujące. Najwolniej zbiega się metoda dychotomiczna – 22 iteracje, najszybsza jest prosta metoda iteracyjna z b = -0,2 – 5 iteracji. Nie ma tu sprzeczności ze stwierdzeniem, że metoda Newtona jest najszybsza.

Pochodna badanej funkcji w punkcie X= 3 jest równe -0,2, czyli obliczenia w tym przypadku przeprowadzono praktycznie metodą Newtona z wartością pochodnej w punkcie pierwiastka równania. Przy zmianie współczynnika B tempo konwergencji maleje, a proces stopniowej konwergencji najpierw przebiega cyklicznie, a następnie staje się rozbieżny.

Wykład Iteracyjne metody rozwiązywania układów algebraicznych równań liniowych.

Warunek zbieżności procesu iteracyjnego. Metoda Jacobiego

Prosta metoda iteracyjna

Rozważany jest układ liniowych równań algebraicznych

Aby zastosować metody iteracyjne, system należy sprowadzić do postaci równoważnej

Następnie wybiera się wstępne przybliżenie rozwiązania układu równań i znajduje ciąg przybliżeń do pierwiastka.

Aby proces iteracyjny był zbieżny wystarczy, że warunek będzie spełniony
(norma matrycowa). Kryterium zakończenia iteracji zależy od zastosowanej metody iteracyjnej.

Metoda Jacobiego .

Najprostszy sposób doprowadzenia systemu do formy wygodnej do iteracji jest następujący:

Z pierwszego równania układu wyrażamy niewiadomą X 1, z drugiego równania układu, który wyrażamy X 2 itd.

W efekcie otrzymujemy układ równań z macierzą B, w którym na głównej przekątnej znajdują się elementy zerowe, a pozostałe elementy obliczamy korzystając ze wzorów:

Składniki wektora d obliczamy korzystając ze wzorów:

Wzór obliczeniowy dla prostej metody iteracyjnej jest następujący:

lub w zapisie współrzędnych wygląda to tak:

Kryterium zakończenia iteracji w metodzie Jacobiego ma postać:

Jeśli
, wówczas możemy zastosować prostsze kryterium zakończenia iteracji

Przykład 1. Rozwiązywanie układu równań liniowych metodą Jacobiego.

Niech będzie dany układ równań:

Wymagane jest znalezienie rozwiązania systemu z dokładnością

Sprowadźmy system do postaci wygodnej do iteracji:

Wybierzmy przybliżenie początkowe, np.

- wektor prawej strony.

Następnie pierwsza iteracja wygląda następująco:

W podobny sposób uzyskuje się następujące przybliżenia rozwiązania.

Znajdźmy normę macierzy B.

Będziemy korzystać z normy

Ponieważ suma modułów elementów w każdym rzędzie wynosi 0,2, zatem
, więc kryterium zakończenia iteracji w tym problemie wynosi

Obliczmy normy różnic wektorowych:

Ponieważ
wymaganą dokładność uzyskano w czwartej iteracji.

Odpowiedź: X 1 = 1.102, X 2 = 0.991, X 3 = 1.0 1 1

Metoda Seidla .

Metodę można uznać za modyfikację metody Jacobiego. Główną ideą jest to, że przy obliczaniu następnego (n+1)- podejście do nieznanego X I Na ja >1 użycie już znalezione (n+1)- zbliżamy się do nieznanego X 1 ,X 2 , ...,X ja - 1 i nie N przybliżeniu, jak w metodzie Jacobiego.

Wzór obliczeniowy metody w zapisie współrzędnych wygląda następująco:

Warunki zbieżności i kryterium zakończenia iteracji można przyjąć tak samo, jak w metodzie Jacobiego.

Przykład 2. Rozwiązywanie układów równań liniowych metodą Seidla.

Rozważmy równolegle rozwiązanie 3 układów równań:

Sprowadźmy systemy do postaci wygodnej dla iteracji:

Należy pamiętać, że warunek zbieżności
wykonano tylko dla pierwszego systemu. W każdym przypadku obliczmy 3 pierwsze przybliżenia rozwiązania.

Pierwszy system:

Dokładnym rozwiązaniem będą następujące wartości: X 1 = 1.4, X 2 = 0.2 . Proces iteracyjny jest zbieżny.

Drugi system:

Można zauważyć, że proces iteracji jest rozbieżny.

Dokładne rozwiązanie X 1 = 1, X 2 = 0.2 .

Trzeci system:

Można zauważyć, że proces iteracji przebiegał cyklicznie.

Dokładne rozwiązanie X 1 = 1, X 2 = 2 .

Niech macierz układu równań A będzie symetryczna i dodatnio określona. Następnie dla dowolnego wyboru przybliżenia początkowego metoda Seidla jest zbieżna. Na małość normy określonej matrycy nie nakłada się żadnych dodatkowych warunków.

Prosta metoda iteracyjna.

Jeśli A jest macierzą symetryczną i dodatnio określoną, wówczas układ równań często sprowadza się do równoważnej postaci:

X=X-τ (A X- b), τ – parametr iteracji.

Wzór obliczeniowy prostej metody iteracyjnej ma w tym przypadku postać:

X (n+1) =X N- τ (A X (N) - B).

a parametr τ > 0 dobiera się tak, aby w miarę możliwości minimalizować jego wartość

Niech λ min i λ max będą minimalnymi i maksymalnymi wartościami własnymi macierzy A. Optymalny wybór parametru to

W tym przypadku
przyjmuje minimalną wartość równą:

Przykład 3. Rozwiązywanie układów równań liniowych prostą metodą iteracyjną. (w MathCAD)

Niech będzie dany układ równań Ax = b

Aby skonstruować proces iteracyjny, znajdujemy wartości własne macierzy A:

- wykorzystuje wbudowaną funkcję do znajdowania wartości własnych.

Obliczmy parametr iteracji i sprawdźmy warunek zbieżności

Warunek zbieżności jest spełniony.

Weźmy przybliżenie początkowe - wektor x0, ustawmy dokładność na 0,001 i znajdźmy przybliżenia początkowe korzystając z poniższego programu:

Dokładne rozwiązanie

Komentarz. Jeśli program zwróci macierz rez, możesz wyświetlić wszystkie znalezione iteracje.

Zaletą metod iteracyjnych jest ich możliwość zastosowania do systemów źle uwarunkowanych i systemów wyższego rzędu, ich samokorekta i łatwość implementacji na komputerze PC. Aby rozpocząć obliczenia, metody iteracyjne wymagają określenia wstępnego przybliżenia pożądanego rozwiązania.

Należy zauważyć, że warunki i szybkość zbieżności procesu iteracyjnego w istotny sposób zależą od właściwości macierzy A układu oraz od wyboru przybliżeń początkowych.

Aby zastosować metodę iteracji, oryginalny układ (2.1) lub (2.2) należy sprowadzić do postaci

po czym przeprowadzany jest proces iteracyjny według powtarzalnych wzorów

, k = 0, 1, 2, ... . (2.26A)

Matryca G i wektor otrzymujemy w wyniku transformacji układu (2.1).

Dla zbieżności (2.26 A) jest konieczne i wystarczające, aby |l I(G)| < 1, где lI(G) – wszystkie wartości własne macierzy G. Konwergencja nastąpi również, jeśli || G|| < 1, так как |lI(G)| < " ||G||, gdzie „ jest dowolnym.

Symbol || ... || oznacza normę macierzy. Określając jego wartość, najczęściej poprzestają na sprawdzeniu dwóch warunków:

||G|| = lub || G|| = , (2.27)

Gdzie . Zbieżność jest również gwarantowana w przypadku macierzy oryginalnej A ma dominację diagonalną, tj.

. (2.28)

Jeżeli spełnione jest (2.27) lub (2.28), metoda iteracyjna jest zbieżna dla dowolnego przybliżenia początkowego. Najczęściej wektor przyjmuje się zero lub jednostkę, lub sam wektor jest pobierany z (2.26).

Istnieje wiele podejść do przekształcania pierwotnego układu (2.2) za pomocą macierzy A aby zapewnić postać (2.26) lub spełnić warunki zbieżności (2.27) i (2.28).

Na przykład (2.26) można otrzymać w następujący sposób.

Pozwalać A = W+ Z, det W#0; Następnie ( B+ Z)= Þ B= −C+ Þ Þ B –1 B= −B –1 C+ B–1, skąd= − B –1 C+ B –1 .

Układanie - B –1 C = G, B–1 = , otrzymujemy (2.26).

Z warunków zbieżności (2.27) i (2.28) wynika, że ​​reprezentacja A = W+ Z nie może być dowolne.

Jeśli macierz A spełnia warunki (2.28), to jako macierz W możesz wybrać dolny trójkątny:

, ii ¹ 0.

; Þ ; Þ ; Þ

Wybierając parametr a, możemy mieć pewność, że || G|| = ||mi+a A|| < 1.

Jeżeli przeważa (2.28), wówczas transformację do (2.26) można przeprowadzić rozwiązując każdy z nich I równanie układu (2.1) w odniesieniu do x ja według następujących powtarzających się wzorów:

(2.28A)

Jeśli w matrixie A nie ma dominacji diagonalnej; należy to osiągnąć za pomocą przekształceń liniowych, które nie naruszają ich równoważności.

Jako przykład rozważmy system

(2.29)

Jak widać w równaniach (1) i (2) nie ma przewagi diagonalnej, natomiast w (3) jest, więc pozostawiamy to bez zmian.

Osiągnijmy dominację diagonalną w równaniu (1). Pomnóżmy (1) przez a, (2) przez b, dodajmy oba równania i w otrzymanym równaniu wybierzmy aib tak, aby była dominacja diagonalna:

(2a + 3b) X 1 + (–1,8a + 2b) X 2 +(0,4a – 1,1b) X 3 = a.

Biorąc a = b = 5, otrzymujemy 25 X 1 + X 2 – 3,5X 3 = 5.

Aby przekształcić równanie (2) z przewagą (1), pomnóż przez g, (2) pomnóż przez d i odejmij (1) od (2). Dostajemy

(3d – 2g) X 1 + (2d + 1,8g) X 2 +(–1,1d – 0,4g) X 3 = − rz.

Wstawiając d = 2, g = 3, otrzymujemy 0 X 1 + 9,4 X 2 – 3,4 X 3 = -3. W rezultacie otrzymujemy system

(2.30)

Technikę tę można zastosować do znalezienia rozwiązań szerokiej klasy macierzy.

Lub

Przyjmując wektor = (0,2; –0,32; 0) jako wstępne przybliżenie T, rozwiążemy ten układ za pomocą technologii (2.26 A):

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

Proces obliczeniowy zatrzymuje się, gdy dwa sąsiednie przybliżenia wektora rozwiązania pokrywają się pod względem dokładności, tj.

.

Technologia iteracyjnego rozwiązywania postaci (2.26 A) o imieniu prosta metoda iteracyjna .

Oszacowanie błędu bezwzględnego dla prostej metody iteracyjnej:

gdzie jest symbol || ... || znaczy normalne.

Przykład 2.1. Stosując prostą metodę iteracyjną z dokładnością e = 0,001 rozwiąż układ równań liniowych:

Z zależności można wyznaczyć liczbę kroków dających odpowiedź z dokładnością do e = 0,001

0,001 GBP.

Oszacujmy zbieżność korzystając ze wzoru (2.27). Tutaj || G|| = = maks. (0,56; 0,61; 0,35; 0,61) = 0,61< 1; = 2,15. Значит, сходимость обеспечена.

Jako wstępne przybliżenie przyjmujemy wektor wyrazów wolnych, tj. = (2,15; –0,83; 1,16; 0,44) T. Zastąpmy wartości wektorów w (2.26 A):

Kontynuując obliczenia, wyniki wprowadzamy do tabeli:

k	X 1	X 2	X 3	X 4
	2,15	–0,83	1,16	0,44
	2,9719	–1,0775	1,5093	–0,4326
	3,3555	–1,0721	1,5075	–0,7317
	3,5017	–1,0106	1,5015	–0,8111
	3,5511	–0,9277	1,4944	–0,8321
	3,5637	–0,9563	1,4834	–0,8298
	3,5678	–0,9566	1,4890	–0,8332
	3,5760	–0,9575	1,4889	–0,8356
	3,5709	–0,9573	1,4890	–0,8362
	3,5712	–0,9571	1,4889	–0,8364
	3,5713	–0,9570	1,4890	–0,8364

Zbieżność w tysięcznych występuje już w 10. kroku.

Odpowiedź: X 1 » 3,571; X 2 "-0,957; X 3 » 1,489; X 4" -0,836.

Rozwiązanie to można również otrzymać korzystając ze wzorów (2.28 A).

Przykład 2.2. Aby zilustrować algorytm za pomocą wzorów (2.28 A) rozważ rozwiązanie układu (tylko dwie iteracje):

; . (2.31)

Przekształćmy układ do postaci (2.26) zgodnie z (2.28 A):

Þ (2.32)

Weźmy początkowe przybliżenie = (0; 0; 0) T. Potem dla k= 0 oczywiste jest, że wartość = (0,5; 0,8; 1,5) T. Podstawmy te wartości do (2.32), czyli kiedy k= 1 otrzymujemy = (1,075; 1,3; 1,175) T.

Błąd e 2 = = maks. (0,575; 0,5; 0,325) = 0,575.

Schemat blokowy algorytmu znajdowania rozwiązania SLAE metodą prostych iteracji według wzorów roboczych (2.28 A) pokazano na ryc. 2.4.

Szczególną cechą schematu blokowego jest obecność następujących bloków:

– blok 13 – jego przeznaczenie omówiono poniżej;

– blok 21 – wyświetlenie wyników na ekranie;

– blok 22 – sprawdzenie (wskaźnik) zbieżności.

Przeanalizujmy proponowany schemat na przykładzie układu (2.31) ( N= 3, w = 1, e = 0,001):

= ; .

Blok 1. Wprowadź dane początkowe A, ,My, N: N= 3, w = 1, e = 0,001.

Cykl I. Ustaw początkowe wartości wektorów X 0I I x ja (I = 1, 2, 3).

Blok 5. Zresetuj licznik liczby iteracji.

Blok 6. Zresetuj bieżący licznik błędów do zera.

W cyklu II następuje zmiana numeracji wierszy macierzy A i wektor.

Cykl II:I = 1: S = B 1 = 2 (blok 8).

Przejdź do zagnieżdżonej pętli III, blok 9 – licznik liczb kolumn macierzy A: J = 1.

Blok 10: J = I dlatego wracamy do bloku 9 i zwiększamy J za sztukę: J = 2.

W bloku 10 J ¹ I(2 ¹ 1) – przechodzimy do bloku 11.

Blok 11: S= 2 – (–1) × X 0 2 = 2 – (–1) × 0 = 2, przejdź do bloku 9, w którym J zwiększyć o jeden: J = 3.

W bloku 10 warunek J ¹ I jest spełniony, więc przejdźmy do bloku 11.

Blok 11: S= 2 – (–1) × X 0 3 = 2 – (–1) × 0 = 2, po czym przechodzimy do bloku 9, w którym J zwiększyć o jeden ( J= 4). Oznaczający J więcej N (N= 3) – kończymy cykl i przechodzimy do bloku 12.

Blok 12: S = S / A 11 = 2 / 4 = 0,5.

Blok 13: w = 1; S = S + 0 = 0,5.

Blok 14: D = | x ja – S | = | 1 – 0,5 | = 0,5.

Blok 15: x ja = 0,5 (I = 1).

Blok 16. Sprawdzenie stanu D > de: 0,5 > 0 zatem przejdź do bloku 17, w którym przypisujemy de= 0,5 i wróć korzystając z linku „ A» do kolejnego etapu cyklu II – do bloku 7, w którym I zwiększyć o jeden.

Cykl II: I = 2: S = B 2 = 4 (blok 8).

J = 1.

Przez blok 10 J ¹ I(1 ¹ 2) – przechodzimy do bloku 11.

Blok 11: S= 4 – 1 × 0 = 4, przejdź do bloku 9, w którym J zwiększyć o jeden: J = 2.

W bloku 10 warunek nie jest spełniony, zatem przechodzimy do bloku 9, w którym J zwiększyć o jeden: J= 3. Analogicznie przechodzimy do bloku 11.

Blok 11: S= 4 – (–2) × 0 = 4, po czym kończymy cykl III i przechodzimy do bloku 12.

Blok 12: S = S/ A 22 = 4 / 5 = 0,8.

Blok 13: w = 1; S = S + 0 = 0,8.

Blok 14: D = | 1 – 0,8 | = 0,2.

Blok 15: x ja = 0,8 (I = 2).

Blok 16. Sprawdzenie stanu D > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «A» do kolejnego etapu cyklu II – do bloku 7.

Cykl II: I = 3: S = B 3 = 6 (blok 8).

Przejdź do zagnieżdżonej pętli III, blok 9: J = 1.

Blok 11: S= 6 – 1 × 0 = 6, przejdź do bloku 9: J = 2.

Korzystając z bloku 10 przechodzimy do bloku 11.

Blok 11: S= 6 – 1 × 0 = 6. Kończymy cykl III i przechodzimy do bloku 12.

Blok 12: S = S/ A 33 = 6 / 4 = 1,5.

Blok 13: S = 1,5.

Blok 14: D = | 1 – 1,5 | = 0,5.

Blok 15: x ja = 1,5 (I = 3).

Zgodnie z blokiem 16 (wraz z odniesieniami „ A" I " Z") wychodzimy z cyklu II i przechodzimy do bloku 18.

Blok 18. Zwiększanie liczby iteracji To = To + 1 = 0 + 1 = 1.

W blokach 19 i 20 cyklu IV zastępujemy wartości początkowe X 0I uzyskane wartości x ja (I = 1, 2, 3).

Blok 21. Wypisujemy wartości pośrednie bieżącej iteracji, w tym przypadku: = (0,5; 0,8; 1,5) T, To = 1; de = 0,5.

Przechodzimy do cyklu II do bloku 7 i wykonujemy rozważane obliczenia z nowymi wartościami początkowymi X 0I (I = 1, 2, 3).

Po czym otrzymujemy X 1 = 1,075; X 2 = 1,3; X 3 = 1,175.

Tutaj zatem metoda Seidla jest zbieżna.

Według wzorów (2.33)

k	X 1	X 2	X 3
	0,19	0,97	–0,14
	0,2207	1,0703	–0,1915
	0,2354	1,0988	–0,2118
	0,2424	1,1088	–0,2196
	0,2454	1,1124	–0,2226
	0,2467	1,1135	–0,2237
	0,2472	1,1143	–0,2241
	0,2474	1,1145	–0,2243
	0,2475	1,1145	–0,2243

Odpowiedź: X 1 = 0,248; X 2 = 1,115; X 3 = –0,224.

Komentarz. Jeśli prosta iteracja i metody Seidla są zbieżne dla tego samego systemu, wówczas preferowana jest metoda Seidla. Jednak w praktyce obszary zbieżności tych metod mogą być różne, tj. prosta metoda iteracyjna jest zbieżna, ale metoda Seidla jest rozbieżna i odwrotnie. Dla obu metod, jeśli || G|| blisko jednostka, prędkość zbieżności jest bardzo niska.

Aby przyspieszyć konwergencję, stosuje się sztuczną technikę – tzw metoda relaksacyjna . Jego istotą jest to, że kolejna wartość uzyskiwana jest metodą iteracyjną x ja (k) oblicza się ponownie przy użyciu wzoru

gdzie w zwykle zmienia się w zakresie od 0 do 2 (0< w £ 2) с каким-либо шагом (H= 0,1 lub 0,2). Parametr w dobiera się tak, aby zbieżność metody została osiągnięta w minimalnej liczbie iteracji.

Relaks– stopniowe osłabienie dowolnego stanu organizmu po ustaniu czynników wywołujących ten stan (inżynieria fizyczna).

Przykład 2.4. Rozważmy wynik piątej iteracji, korzystając ze wzoru relaksacyjnego. Weźmy w = 1,5:

Jak widać uzyskano wynik niemalże siódmej iteracji.

Prosta metoda iteracyjna, zwana także metodą kolejnych aproksymacji, jest matematycznym algorytmem znajdowania wartości nieznanej wielkości poprzez jej stopniowe udoskonalanie. Istota tej metody polega na tym, że jak sama nazwa wskazuje, stopniowo wyrażając kolejne z początkowego przybliżenia, uzyskuje się coraz bardziej dopracowane wyniki. Metodę tę stosuje się do znajdowania wartości zmiennej w danej funkcji, a także do rozwiązywania układów równań, zarówno liniowych, jak i nieliniowych.

Zastanówmy się, jak ta metoda jest wdrażana przy rozwiązywaniu SLAE. Prosta metoda iteracyjna ma następujący algorytm:

1. Sprawdzenie spełnienia warunku zbieżności w macierzy pierwotnej. Twierdzenie o zbieżności: jeśli pierwotna macierz układu ma dominację diagonalną (tj. w każdym wierszu elementy głównej przekątnej muszą być większe w wartości bezwzględnej niż suma elementów przekątnych drugorzędnych w wartości bezwzględnej), to proste metoda iteracyjna jest zbieżna.

2. Macierz pierwotnego układu nie zawsze ma przewagę diagonalną. W takich przypadkach istnieje możliwość konwersji systemu. Równania spełniające warunek zbieżności pozostawiamy bez zmian i tworzymy kombinacje liniowe z równaniami, które tego nie spełniają, tj. mnożyć, odejmować, dodawać do siebie równania, aż do uzyskania pożądanego wyniku.

Jeżeli w powstałym układzie na głównej przekątnej znajdują się niewygodne współczynniki, wówczas do obu stron takiego równania dodawane są wyrazy postaci z i * x i, których znaki muszą pokrywać się ze znakami elementów przekątnych.

3. Transformacja powstałego układu do postaci normalnej:

x - =β - +α*x -

Można to zrobić na wiele sposobów, na przykład w ten sposób: z pierwszego równania wyraź x 1 w kategoriach innych niewiadomych, z drugiego - x 2, z trzeciego - x 3 itd. W tym przypadku korzystamy ze wzorów:

α ij = -(a ij / a ii)

ja = b ja /a ii
Należy ponownie upewnić się, że powstały układ postaci normalnej spełnia warunek zbieżności:

∑ (j=1) |α ij |≤ 1, podczas gdy i= 1,2,...n

4. Zaczynamy właściwie stosować samą metodę kolejnych przybliżeń.

x (0) jest przybliżeniem początkowym, przez nie wyrazimy x (1), a następnie wyrazimy x (2) do x (1). Ogólny wzór w postaci macierzowej wygląda następująco:

x (n) = β - +α*x (n-1)

Obliczamy, aż osiągniemy wymaganą dokładność:

max |x i (k)-x i (k+1) ≤ ε

Zastosujmy więc prostą metodę iteracji w praktyce. Przykład:
Rozwiąż SLAE:

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 z dokładnością ε=10 -3

Zobaczmy, czy elementy diagonalne dominują w module.

Widzimy, że tylko trzecie równanie spełnia warunek zbieżności. Przekształcamy pierwsze i drugie i dodajemy drugie do pierwszego równania:

7,6x1+0,6x2+2,4x3=3

Od trzeciego odejmujemy pierwszy:

2,7x1+4,2x2+1,2x3=2

Przekształciliśmy oryginalny system na równoważny:

7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1,8x1+2,5x2+4,7x3=4

Teraz przywróćmy system do normalnej postaci:

x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3= 0,8511-0,383x1-0,5319x2

Sprawdzamy zbieżność procesu iteracyjnego:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, tj. warunek jest spełniony.

0,3947
Wstępne założenie x(0) = 0,4762
0,8511

Podstawiając te wartości do równania postaci normalnej, otrzymujemy następujące wartości:

0,08835
x(1) = 0,486793
0,446639

Podstawiając nowe wartości otrzymujemy:

0,215243
x(2) = 0,405396
0,558336

Kontynuujemy obliczenia, aż dotrzemy do wartości spełniających zadany warunek.

x (7) = 0,441091

Sprawdźmy poprawność uzyskanych wyników:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

Wyniki uzyskane poprzez podstawienie znalezionych wartości do oryginalnych równań w pełni spełniają warunki równania.

Jak widać, prosta metoda iteracyjna daje dość dokładne wyniki, jednak aby rozwiązać to równanie, musieliśmy poświęcić dużo czasu i wykonać żmudne obliczenia.