Numerikus módszerek 1

Numerikus módszerek 1. 9. előadás: Paraméteres iterációk, relaxációs módszerek

Lócsi Levente ELTE IK

Tartalomjegyzék

1 A Richardson-iteráció

2 Relaxált Jacobi-iteráció

3 Relaxált Gauss–Seidel-iteráció

Emlékeztető: Iterációs módszerek

Az Ax = b LER megoldása érdekében alakítsuk azt át x = Bx + c alakúra, és valamely x (0) kezdőpontból végezzük az x (k+1) = B · x (k) + c

(k ∈ N0 )

iterációt. Ez a vektorsorozat bizonyos feltételek mellett konvergál a LER megoldásához. (Ekvivalens feltétel: ̺(B) < 1.) Volt: Banach-féle fixponttétel, Jacobi-, Gauss–Seidel-iterációk. Megjegyzés: • 2–3 változó: felesleges → megértés • sok változó (100, 1000): használják

Tartalomjegyzék




Richardson-iteráció Tekintsük az Ax = b LER-t, ahol A szimmetrikus, pozitív definit mátrix (azaz minden sajátértéke valós, sőt pozitív), és p :∈ R. Ax = b p · Ax = p · b 0 = −pAx + pb x = x − pAx + pb = (I − pA)x + pb Ezek alapján az iteráció a következő.

Definíció: Richardson-iteráció p paraméterrel – R(p) x (k+1) = (I − pA) ·x (k) + pb = BR(p) · x (k) + cR(p) |

{z

BR(p)

}

|{z} cR(p)

Richardson-iteráció

Példa Vizsgáljuk meg a Richardson-iterációt néhány p ∈ R paraméter mellett a következő egyenletrendszer esetén. Ax = b,

!

3 −1 ·x = −1 3

!

1 . 5

A mátrix szimm., poz. def., a megoldás pedig x =

!

1 . 2

Richardson-iteráció Tétel: A Richardson-iteráció konvergenciája Ha az A ∈ Rn×n mátrix szimmetrikus, pozitív definit és sajátértékeire m = λ1 ≤ · · · ≤ λn = M teljesül, akkor R(p) (azaz egy A mátrixú LER-re felírt p ∈ R paraméterű Richardson-iteráció) konvergens, ha 2 , p ∈ 0, M az optimális paraméter és a hozzá kapcsolódó kontrakciós együttható pedig: popt =

2 , M +m

̺opt := ̺(BR(popt ) ) =

M −m . M +m

Richardson-iteráció Bizonyítás: 1

BR(p) sajátértékei: λi (p) = 1 − p · λi , hiszen Av = λi v

⇒

(I−pA)v = v −pAv = v −pλi v = (1−pλi )v .

Vagyis: λ1 (p) = 1 − p · λ1 = 1 − pm, λ2 (p) = 1 − p · λ2 , .. . λn (p) = 1 − p · λn = 1 − pM.

2

n

BR(p) spektrálsugara így ̺(BR(p) ) = max |1 − p · λi |. i=1

Richardson-iteráció 3

Ábrázoljuk az |1 − p · λi | függvényeket (i = 1, 2, . . . , n)! (Ezek p-től függenek.) 1 − p · λi = 0

̺(BR(p) )

⇐⇒

p=

|1 − pM|

1 λi |1 − pm|

1 ̺opt 1 popt M

2 M

1 m

p

Richardson-iteráció 4

5

2 . R(p) konvergens, ha ̺(BR(p) ) < 1, azaz ha p ∈ 0, M Ezek az |1 − pM| = 1 egyenlet megoldásai. Továbbá az optimális paramétert az |1 − pM| = |1 − pm| egyenlet megoldása adja. (Nem a 0, hanem a másik.) −1 + pM = 1 − pm pM + pm = 2 p(M + m) = 2

6

=⇒

popt =

2 M +m

Ekkor ̺(BR(popt ) ) = 1 − popt · m =

2m M −m M +m − = . M +m M +m M +m

Richardson-iteráció

Példa Adjuk meg, hogy a Richardson-iteráció mely p ∈ R paraméterek mellett konvergens a következő egyenletrendszer esetén – mely ugyanaz, mint az imént. Mi az optimális paraméter és a hozzá tartozó „átmenetmátrix” spektrálsugara? Ax = b, A mátrix sajátértékei 2 és 4.

!

3 −1 ·x = −1 3

!

1 . 5

Tartalomjegyzék




Relaxáció A relaxáció, avagy csillapítás, avagy tompítás alapötlete: x (k+1)

helyett

(1 − ω) · x (k) + ω · x (k+1)

x (k)

x (k+1)

Megj.: • alulrelaxálás (0 < ω < 1), túlrelaxálás (ω > 1) • ω = 1 az eredeti módszert adja

Relaxált Jacobi-módszer Induljunk a Jacobi-módszerből és a „helyben hagyásból”: x x

= −D −1 (L + U) · x + D −1 b = x

/·ω / · (1 − ω)

A kettő súlyozott összege: x

=

(1 − ω)I − ωD −1 (L + U) · x + ωD −1 b

Ezek alapján az iteráció a következő.

Definíció: relaxált Jacobi-iteráció ω paraméterrel – J (ω) h

i

−1 x (k+1) = (1 − ω)I − ωD −1 (L + U) ·x (k) + ωD | {z b}

|

{z

BJ(ω)

}

cJ(ω)

Relaxált Jacobi-módszer Írjuk fel koordinátánként!

Állítás: J (ω) komponensenkénti alakja (k+1)

xi

(k)

= (1 − ω) · xi

(k+1)

+ ω · xi,J(1) ,

(k+1)

ahol xi,J(1) a hagyományos Jacobi-módszer (J(1)) által adott, azaz (k+1)

xi,J(1) =



n X



−1  (k) ai,j xj − bi  . ai,i j=1, j6=i

Biz.: Házi feladat meggondolni. Nem nehéz.

Relaxált Jacobi-módszer

Tétel: a relaxált Jacobi-módszer konvergenciájáról Ha egy mátrixra a J(1) módszer konvergens, akkor 0 < ω < 1 esetén a J(ω) módszer is konvergens. (Az ω = 0 esetben nem.) Biz.: Rövid, táblán. Meggondoltuk. Megj.: A relaxált Jacobi-módszert nem szokták alkalmazni. . .

Tartalomjegyzék




Relaxált Gauss–Seidel-iteráció Induljunk a Seidel-iteráció következő alakjából: (L + D) · x D·x

= −U · x + b = D·x

/·ω / · (1 − ω)

A kettő súlyozott összege: (D + ωL) · x

= [(1 − ω)D − ωU] · x + ωb

Ezek alapján az iteráció a következő.

Definíció: relaxált Seidel-iteráció ω paraméterrel – S(ω)

x (k+1) = (D + ωL)−1 [(1 − ω)D − ωU] ·x (k) + ω(D + ωL)−1 b |

{z

BS(ω)

}

|

{z

cS(ω)

}

Relaxált Gauss–Seidel-iteráció Írjuk fel koordinátánként! (Kiderül, hogy „helyben” számolható.)

Állítás: S(ω) komponensenkénti alakja (k+1)

xi

(k)

= (1 − ω) · xi

(k+1)

+ ω · xi,S(1) ,

(k+1)

ahol xi,S(1) a hagyományos Seidel-módszer (S(1)) által adott, azaz (k+1) xi,S(1)





i−1 n X −1 X (k+1) (k) ai,j xj + ai,j xj − bi  . = ai,i j=1 j=i+1

Minden k lépés az i = 1, 2, . . . , n sorrendben számolandó.

Relaxált Gauss–Seidel-iteráció

Biz.: Alakítsunk át, majd gondoljunk bele a mátrixszorzásba. (D + ωL)x (k+1) = (1 − ω)Dx (k) − ωUx (k) + ωb Dx (k+1) = (1 − ω)Dx (k) − ωLx (k+1) − ωUx (k) + ωb

x (k+1) = (1 − ω)x (k) − ω D −1 Lx (k+1) + Ux (k) − b |

{z

Lásd S(1)-nél.

(k+1)

Megj.: Vigyázat! x (k+1) = (1 − ω) · x (k) + ω · xS(1) (tehát az egész vektorra); csak komponensenként.

nem igaz

}


Tétel: a relaxált Seidel-módszer konvergenciájáról Ha egy mátrixra az S(ω) módszer konvergens, akkor 0 < ω < 2.

Lemma det B =

n Q

λi (B)

i=1

Biz.: Előbb a lemma, azután a tétel. Táblán. Meggondoltuk. Megjegyzés: • Ha ω ∈ / (0, 2), akkor általában nem konvergál. • A relaxált Seidel-módszert gyakran alkalmazzák. . .


Tétel: a relaxált Seidel-módszer konvergenciájáról Ha az egyenletrendszer mátrixa szimmetrikus, pozitív definit és ω ∈ (0, 2), akkor az S(ω) módszer konvergens. Biz.: nélkül.

Példák Matlab-ban

1

A Richardson-iteráció viselkedésének vizsgálata különböző paraméterek mellett.

Numerikus módszerek 1

Recommend Documents