iteracja

Metoda iteracji.

W przepadku 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ń

^an*i^+au*a+ ⁺<V»=4_ ^ai iXi+a₂₂x₂+.. +a„x, = b₂

^a,i^xi+^a,i^xi + +a„x, =b, po wprowadzeniu macierzy

	'au	an .	• V				'K
A =	<h\	^a22 ■	• <*2«	x=	^2	B =	b2
	_^a*\	^a»2 •	■	5		5	A.

gdzie Pi = —

** = Pi ⁺'L^aa^xj

3-1

gd^ńtPi = \ *> = -%■ *S ⁼

^aii .

Warunek dostateczny zbieżności.

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

ZKK i=l>2,...,n,

J-l lub »

ZkK j⁼ 1= 2,..., n,

to proces iteracyiny    = P +&■ xS"\ k = 0. 1. 2. ...

jest zbieżny do jednoznacznego rozwiązania, niezależnie od tego jaki wybierzemy wektor początkowy. Zatem metoda iteracji

s

jest zbieżna dla układu J^a_{;x,- = b_it i= 1,2,..., n, jeżeli

i-i    ||

zachodzą następujące nierówności: l>ZkM=l_: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).

dla i*j.

Przykład Rozwiązywanie układów' równań metodą iteracji. Rozwiązać układ równań stosując metodę iteracji z dokładnością do 0.01.    4 X!+ 0,24x₂-0,08x₃= $

0,09 xj+ 3 x₂ - 0,15 x₃ = 9>

0,04 x\ + 0.08 x₂ +    4 x₃ = 2Q

Dzielimy każde równanie układu przez współczynniki a^_: i=l, 2,..., n ( współczynniki leżące na przekątnej głównej).

4 xj + 0,24 x₂ - 0,08 x₃ = 8    |: 4

0,09 xj+ 3 x₂-0,15x₃= ⁹    |:3

0,04 Xi + 0.08 x₂ +    4 x₃ = 20    |: 4

Układ zapisujemy w postaci x₁ = 2-0,06x₂ + 0,02j?

x₂ = 3 - 0,03 X\ + 0,05 x>

x₃ = 5-0,01x₁ + 0,02xj

Na podstawie wzoru x = p + a - x możemy zapisać w postaci macierzowej

		2"		0	-0,06	0.02"
*2	=	3	+	-0,03	0	0,05		^2
_*3_		_5_		-0,01	0,02	0 ^

Przybliżenia pierwiastków' układu przyjmujemy na podstawie wzoru ^ _ Ą

4^1!=5.04

4^1!=3.19

4^I!=5.04 .

4^1!=3.19

4^2! =5.0446

A2) _

(2) _

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

Rozwiązujemy pierwsze równanie układu względem xj, drugie równanie w^rzględem x₂ itd. Zakładamy przy tym, że elementy na głównej przekątnej a_n?t O (/= 1, 2,..., ń). Otrzymujemy układ równoważny x₁ = P₁ + a₁₂x₂+a_ux₃+...+a_]xx»

+ ..	^+chA .
+...
^a»
__v_	dla
^aii	a

oraz ^. = 0 dla i=J Uj = 1,2,n.

układ równań możemy zapisać w postaci x = P + a ■ x

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

= 0

Tworzymy następnie macierze kolumnowe *0) = Q + a ■ x⁽⁰¹ " pierwsze przybliżenie

x^{2) = P + a- x^{1) - przybliżenie drugie i.t.d

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

x<^M) = ,e + a '    ifc=0.1.2....

Iterację kończymy gdy spełniony jest warunek

|x/^Ał -x|*“^1J| <£ gdzie £ oznacza zadaną dokładność.

Jeżeli ciąg przybliżeń x^K jkW........ ma granice

x x^K to granica ta jest rozwiązaniem układu równań

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

Z^ai!^xj=^bi i — 1,2,n

■    ^?"¹ ■ ' a -aM+a™ a- a * 0

można przyjąć ^au ~ ^au ^^an , gdzie

( i = 1,2,n ). Wówczas dany układ równoważny jest

układowi

v — l-t J- >    <"/ -T

i = 1,2,n ,

L

a™

<*u

czyli za przybliżenie początkowe układu przyjmujemy kolumnę wyrazów' wolnych : *!°^J = 2 _# x^<2 ^> = 3 _s x^^0J = 5 gdzie indeks górny oznacza numer przybliżenia.

Podstawiamy te wartości do prawych stron układu

4‘^{l =} 2-0.06 * 3 + 0.02 * 51

4” = 3 - 0.03 * 2 + 0.05 * sy

4^1! = 5 - 0.01 * 2 + 0.02 * 3 Po obliczeniu otrzymujemy pierwsze przybliżenie

4-= 1.92

Wartości te podstawiamy do układu 4^2! = 2 - 0.06 * 3.19 + 0.02 * 5.04

4^2! = 3 - 0.03 * 1.92 + 0.05 * 5.04 4^2!= 5-0.01 * 1.92 + 0,02 *3.19 Po obliczeniu otrzymujemy pierwsze przybliżenie pierwiastków;

4¹’ = 1.92

Wartości te podstawiamy do układu

4^2!= 2-0.06 * 3.19 + 0,02 *5.04

4^2! = 3 - 0,03 * 1,92 + 0,05 * 5.04

4^2!= 5-0,01 * 1.92 + 0,02 *3.19 Otrzymujemy drugie przybliżenie pierwiastków:

*1= 1.9094 ; 4 =3.1944

Po następnym podstayvieniu otrzymujemy trzecie przybliżenie:

4³⁾ = 1,90923

4^3! = 5.04485

4^S! = 3.19495