2.2 Richardsonova metoda

2 Itera£ní metody pro °e²ení soustav lineárních rovnic s SPD maticí

2.1 Prostá itera£ní metoda

Metoda daná p°edpisem

ui+1=ui+ (b−Aui). Chyba po(i+ 1). iteraci:

e_i+1 = u_i+1−u^∗=u_i+b−A·u_i−u^∗=u_i+A·u^∗−A·u_i−u^∗=e_i−A·e_i=

= (I−A)·ei= (I−A)ⁱ⁺¹·eo

P°íklad 2.1.

2 −1

−1 2

· u₁

u₂

= 0

1

λ−2 −1

−1 λ−2

= (λ−2)²−1⇒λ₁= 3, λ₂= 1

Vlastní £ísla zadané matice jsou kladná, matice je tedy symetrická a pozitivn¥

denitní. Její normované vlastní vektory ozna£mev1,v2, (kvik= 1).

e0=

2

X

k=1

αkvk

ei = (I−A)ⁱ·e0= (I−A)ⁱ·

2

X

k=1

αkvk=

2

X

k=1

αk·(I−A)ⁱ·vk=

2

X

k=1

αk·(1−λk)ⁱ·vk

keik=

" ₂ X

k=1

α²_k·(1−λk)²ⁱ

#^1/2

→0

a tedy dostáváme podmínku konvergence (1−λ_k)ⁱ → 0. Metoda je tedy kon- vergentní, pokud λ_k ∈ (0,2), coº nenastane ve vý²e uvedeném p°ípad¥. Pomocí m·ºe být jednoduché ²kálování pomocíω >0:

A·u=b → ω·A·u=ω·b (²kálovaná soustava), A·v=λ·v → ω·A·v=ω·λ·v

ui+1=ui+ (ω·b−ω·A·ui) =ui+ω(b−A·ui)

Nap°íklad volbouω= ¹₃ dostaneme maticiωA, jejíº vlastní £ísla jsou men²í neº 2 a máme zaru£enu konvergenci. Získáváme tak Richardsonovu metodu. 4

2.2 Richardsonova metoda

Richardsonova metoda je dána itera£ním p°edpisem ui+1=ui+ω(b−Aui), kdeω je vhodná konstanta.

Algoritmus 1 Richardsonova metoda u₀←−

for i= 0,1, . . . r_i =b−A·u_i u_i+i=u_i+ω·r_i end

2.2.1 Konvergence itera£ní metody

Richardsonova metoda pat°í mezi itera£ní metody minimalizující eukleidovskou normu chyby.

V¥ta 2.1. Nech´ Aje SPD,ω je vhodná konstanta, p°esn¥ji0< ω <2/λmax(A). Potom Richadsonova metoda daná p°edpisemu_i+1=u_i+ω(b−Au_i)konverguje, p°esn¥ji

kei+1k_(m)=kui+1−u^∗k_(m)≤qⁱ· ku0−u^∗k_(m) kde q= max

k |1−ωλ_k|<1, m= 0,1, . . .

D·kaz. Vyjád°íme po£áte£ní chybue0 v bázi vlastních vektor· matice A a dosa- díme do vzorce pro výpo£et chyby(i−1). iterace.

e0=X αkvk

ei= (I−ωA)ⁱe0= (I−ωA)ⁱ·X

αkvk =X

αk·(1−ωλk)ⁱ·vk

keik²_(m) =

Xαk·(1−ωλk)ⁱ·vk

2 (m)=

= X

αk·λ^m_k ·(1−ωλk)ⁱ·vk,X

αk·(1−ωλk)ⁱ·vk

=

= X

k

X

l

α_k·λ^m_k (1−ωλ_k)ⁱ·α_l·(1−ωλ_l)ⁱ·(v_k, v_l) =

= X

α_k²·λ^m_k (1−ωλ_k)²ⁱ ≤

≤ max

k |1−ωλ_k|²ⁱ·X

λ^m_kα²_k= max

k |1−ωλ_k|²ⁱ· ke₀k²_(m)=

= max

k

P_i^R(λk)

2· ke0k²_(m)≤q²ⁱ· ke0k²_(m), P_i^R(λ) = (1−ωλ)ⁱ(1)

Poznámka 2.1. Polynom

P_i^R(λ) =P_i^R,ω(λ) = (I−ωλ)ⁱ, (2) který se objevuje v (1), nazveme itera£ním polynomem Richardsonovy metody.

Redukce chyby souvisí s hodnotami tohoto polynomu v prvcíchλ_k ∈σ(A). 2.2.2 Volba optimálního faktoru

Konstantuωse snaºíme zvolit tak, aby norma rezidua klesala co nejrychleji. Nej- lep²í z takových konstant nazýváme optimálním faktorem a zna£ímeω_opt.

Konvergen£ní faktor q = max|1−ωλk| musí být nutn¥ men²í neº1 a ideáln¥

co nejmen²í. Hledáme tedy takovou hodnotu ω, pro kterou je max|1−ωλk| co nejmen²í, viz. obrázek 1.

Obrázek 1: Optimální faktor

ω_optλn−1 = 1−ωoptλ1=⇒ω_opt= 2

λn+λ1 (3)

q_opt= 1− 2 λn+λ1

λ₁= λ_n−λ₁ λn+λ1

=

λ_n λ₁ −1

λ_n

λ₁ + 1 =κ(A)−1

κ(A) + 1 (4) Optimální faktor m·ºeme vyjád°it také pomocí itera£ního polynomu. Minima- lizací polynomu (2) získáme práv¥ vý²e odvozený optimální faktorω_opt, tedy

ω_opt=argmin

ω

i=1,...,nmax

P_ω^R(λi) = 2

λ₁+λ_n.

Problém je ale v tom, ºe vlastní £ísla matice Av¥t²inou neznáme a ur£it je by bylo sloºit¥j²í neº °e²it p·vodní úlohu. Obvykle je tedy nahrazujeme jejich odhady, m·ºeme pouºít nap°. Ger²gorinovu v¥tu. Pokudλje odhad nejmen²ího vlastního

£ísla(0≤λ≤λ₁)a λje odhad nejv¥t²ího vlastního £ísla λ≥λ_n, zvolíme kvazi optimální faktor

ωkopt= 2 λ+λ.

Pro konvergen£ní faktor dostaneme odhad

q= 1− 2

λ+λ·λ1=λ+λ−2·λ1

λ+λ ≤λ−λ

λ+λ = c−1 c+ 1,

kdec=^λ_λ ≥κ(A). Neznáme-li proλ1 lep²í odhad neº hodnotu0, pouºijeme ω= 2

λ.

Pokud zvolímeωmimo interval(0,2/λmax), budou n¥které sloºky chyby nar·s- tat. Pokud zvolímeω z uvedeného intervalu, budou v²echny sloºky klesat, nejvíce ty, pro které je λk blízko 1/ω. Vhodnou volbou ω tak lze dosáhnout toho, ºe budou dob°e redukovány sloºky odpovídající velkým vlastním £ísl·m, opa£n¥ to nelze. Pomocí Richardsovy metody lze dosáhnout rychlé redukce oscilujících slo- ºek (sloºek odpovídajících oscilujícím vlastním vektor·m), velmi efektivní metodu dostaneme, kdyº zbývající sloºky (odpovídající men¥ oscilujícím, hladkým vlastní vektor·m) redukujeme jinou technikou - nap°. korekcí vypo£tenou pomocí hrub²í diskretizace, viz [Multigrid].

2.2.3 Ukon£ení iterací

ˆ sledovat rozdíl iteracíδi+1=ui+1−ui=ωri

ˆ sledovat reziduumri=b−A·ui −→ukon£ovací podmínkakrik ≤· kr0k Kolik iterací je pot°eba pro dosaºení dané p°esnosti ε:

qⁱ ≤ ε

i·lnq ≤ lnε (q, ε <1) i ≥ lnε

lnq Výhody a nevýhody metody:

1. jednoduché operace, moºná paralelizace 2. pomalá konvergence

3. nutnost odhadnout parametrω Zrychlení metody:

ˆ volba r·zných parametr·ω=ω_i pro jednotlivé iterace (vede na ƒeby²evovu metodu)

ˆ pro opravu vylep²it sm¥r rezidua (vede na metodu sdruºených gradient·)