Postupná metoda přílišné relaxace
V numerické analýze je metoda postupné overrelaxace (anglicky: Successive Overrelaxation Method, zkráceně SOR) variantou Gauss-Seidelovy metody pro řešení soustavy lineárních rovnic . Konvergence tohoto algoritmu je obecně rychlejší. Podobný přístup lze použít u mnoha iteračních metod .
Tuto metodu objevili současně David M. Young, Jr. (in) a Stan Frankel v roce 1950 za účelem automatického řešení lineárních systémů pomocí počítačů . Metody nadměrné relaxace byly použity dříve. Uvedeme metodu Lewise Fryho Richardsona a metodu
RV Southwella . Tyto metody byly navrženy pro lidské bytosti a pro zajištění konvergence vyžadovaly určitou odbornost . Tyto metody nelze přepsat na počítači. Tato omezení byla diskutována v práci Davida Younga
Formulace
Uvažujeme lineární systém n rovnic s n neznámými známkami x (což je vektor ):
NAX=b{\ displaystyle A \ mathbf {x} = \ mathbf {b}}![A {\ mathbf x} = {\ mathbf b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45d894430af69e29d6dda5aacbf4bb19336226a0)
nebo:
NA=[na11na12⋯na1nena21na22⋯na2ne⋮⋮⋱⋮nane1nane2⋯nanene],X=[X1X2⋮Xne],b=[b1b2⋮bne].{\ displaystyle A = {\ begin {bmatrix} a_ {11} & a_ {12} & \ cdots & a_ {1n} \\ a_ {21} & a_ {22} & \ cdots & a_ {2n} \\\ vdots & \ vdots & \ ddots & \ vdots \\ a_ {n1} & a_ {n2} & \ cdots & a_ {nn} \ end {bmatrix}}, \ qquad \ mathbf {x} = {\ begin {bmatrix} x_ {1} \\ x_ {2} \\\ vdots \\ x_ {n} \ end {bmatrix}}, \ qquad \ mathbf {b} = {\ begin {bmatrix} b_ {1} \\ b_ {2 } \\\ vdots \ \ b_ {n} \ end {bmatrix}}.}![A = {\ begin {bmatrix} a _ {{11}} & a _ {{12}} & \ cdots & a _ {{1n}} \\ a _ {{21}} & a {{22} } & \ cdots & a _ {{2n}} \\\ vdots & \ vdots & \ ddots & \ vdots \\ a _ {{n1}} & a _ {{n2}} & \ cdots & a _ {{ nn}} \ end {bmatrix}}, \ qquad {\ mathbf {x}} = {\ begin {bmatrix} x _ {{1}} \\ x_ {2} \\\ vdots \\ x_ {n} \ konec {bmatrix}}, \ qquad {\ mathbf {b}} = {\ begin {bmatrix} b _ {{1}} \\ b_ {2} \\\ vdots \\ b_ {n} \ end {bmatrix} }.](https://wikimedia.org/api/rest_v1/media/math/render/svg/98608e9e95d5acad149813eca75c8108acec308a)
A je součtem diagonální matice zaznamenané D a dvou trojúhelníkových matic (dolní a horní), zaznamenaných L a U :
NA=D+L+UsD=[na110⋯00na22⋯0⋮⋮⋱⋮00⋯nanene],L=[00⋯0na210⋯0⋮⋮⋱⋮nane1nane2⋯0],U=[0na12⋯na1ne00⋯na2ne⋮⋮⋱⋮00⋯0],{\ displaystyle A = D + L + U \ qquad {\ text {with}} \ quad D = {\ begin {bmatrix} a_ {11} & 0 & \ cdots & 0 \\ 0 & a_ {22} & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & a_ {nn} \ end {bmatrix}}, \ quad L = {\ begin {bmatrix} 0 & 0 & \ cdots & 0 \\ a_ {21} & 0 & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ a_ {n1} & a_ {n2} & \ cdots & 0 \ end {bmatrix }}, \ quad U = {\ begin {bmatrix} 0 & a_ {12} & \ cdots & a_ {1n} \\ 0 & 0 & \ cdots & a_ {2n} \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & 0 \ end {bmatrix}},}![A = D + L + U \ qquad {\ text {with}} \ quad D = {\ begin {bmatrix} a _ {{11}} & 0 & \ cdots & 0 \\ 0 & a _ {{22} } & \ cdots & 0 \\ \ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & a _ {{nn}} \ end {bmatrix}}, \ quad L = {\ begin { bmatrix} 0 a 0 & \ cdots & 0 \\ a _ {{21}} & 0 & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ a _ {{n1}} & a _ {{n2}} & \ cdots & 0 \ end {bmatrix}}, \ quad U = {\ begin {bmatrix} 0 & a _ {{12}} & \ cdots & a _ {{1n}} \\ 0 & 0 & \ cdots & a _ {{2n}} \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & 0 \ end {bmatrix}},](https://wikimedia.org/api/rest_v1/media/math/render/svg/a212111236f45fae22c7bddfd3fc51552eeb3325)
systém lineárních rovnic lze přeformulovat pomocí:
(D+ωL)X=ωb-[ωU+(ω-1)D]X{\ displaystyle (D + \ omega L) \ mathbf {x} = \ omega \ mathbf {b} - [\ omega U + (\ omega -1) D] \ mathbf {x}}![(D + \ omega L) {\ mathbf {x}} = \ omega {\ mathbf {b}} - [\ omega U + (\ omega -1) D] {\ mathbf {x}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e83bbf90bf4402a87819cdff801fb3c075eeb46)
pro všechny ω > 0.
Postupná metoda overrelaxation je iterační metoda inicializovaná výběrem libovolné a kde každá iterace spočívá v určení použití podle následujícího vzorce:
X0{\ displaystyle x_ {0}}
Xk+1{\ displaystyle x_ {k + 1}}
Xk{\ displaystyle x_ {k}}![x_k](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d2b88c64c76a03611549fb9b4cf4ed060b56002)
(D+ωL)Xk+1=ωb-[ωU+(ω-1)D]Xk{\ displaystyle (D + \ omega L) \ mathbf {x_ {k + 1}} = \ omega \ mathbf {b} - [\ omega U + (\ omega -1) D] \ mathbf {x_ {k}} }![{\ displaystyle (D + \ omega L) \ mathbf {x_ {k + 1}} = \ omega \ mathbf {b} - [\ omega U + (\ omega -1) D] \ mathbf {x_ {k}} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7f23710771c25705979ca3b39ac1194da114e6e)
Levá matice ( D + ωL ) je trojúhelníková, lze ji snadno vypočítat pomocí:
Xk+1{\ displaystyle x_ {k + 1}}![x_ {k + 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a54ef7b7d84549c053b24d7aa478bcde15f31056)
Xi(k+1)=(1-ω)Xi(k)+ωnaii(bi-∑j>inaijXj(k)-∑j<inaijXj(k+1)),i=1,2,...,ne.{\ displaystyle x_ {i} ^ {(k + 1)} = (1- \ omega) x_ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} \ vlevo ( b_ {i} - \ sum _ {j> i} a_ {ij} x_ {j} ^ {(k)} - \ sum _ {j <i} a_ {ij} x_ {j} ^ {(k + 1 )} \ vpravo), \ quad i = 1,2, \ ldots, n.}![{\ displaystyle x_ {i} ^ {(k + 1)} = (1- \ omega) x_ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} \ vlevo ( b_ {i} - \ sum _ {j> i} a_ {ij} x_ {j} ^ {(k)} - \ sum _ {j <i} a_ {ij} x_ {j} ^ {(k + 1 )} \ vpravo), \ quad i = 1,2, \ ldots, n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a051df613a664c268d57dfe12e20ac2f0c527b8a)
Volba relaxačního faktoru není triviální a závisí na koeficientech matice. Pro pozitivní určitou matici můžeme ukázat, že algoritmus je konvergentní pro všechno . Chceme však konvergenci co nejrychleji. Všimněte si, že pro relaxační faktor 1 narazíme na Gauss-Seidelovu metoduω∈]0,2[{\ displaystyle \ omega \ in] 0,2 [}
Algoritmus
Vstup: A , b , ω
Výstup:ϕ{\ displaystyle \ phi}
Zvolili jsme počáteční libovolné řešení .
Opakujte až do konvergence
ϕ(0){\ displaystyle \ phi ^ {(0)}}![\ phi ^ {{(0)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20a822287cb90192df8ccd40c57bb82eeb4cc463)
Smyčka i od 1 do n
σ←0{\ displaystyle \ sigma \ leftarrow 0}![\ sigma \ leftarrow 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/920f73bc0bba40e42b7eb17f84f31444dafc1e64)
Smyčka j od 1 do i - 1
σ←σ+naijϕj(k+1){\ displaystyle \ sigma \ leftarrow \ sigma + a_ {ij} \ phi _ {j} ^ {(k + 1)}}![\ sigma \ leftarrow \ sigma + a _ {{ij}} \ phi _ {j} ^ {{(k + 1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1aa628be5adb6691850bee24c3749ff4e9cdf49d)
Konec (smyčka j )
Smyčka j od i + 1 do n
σ←σ+naijϕj(k){\ displaystyle \ sigma \ leftarrow \ sigma + a_ {ij} \ phi _ {j} ^ {(k)}}![\ sigma \ leftarrow \ sigma + a _ {{ij}} \ phi _ {j} ^ {{(k)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7b7fc5ea6c033fb7356b623c0e9d2d3d1404521)
Konec (smyčka j )
ϕi(k+1)←(1-ω)ϕi(k)+ωnaii(bi-σ){\ displaystyle \ phi _ {i} ^ {(k + 1)} \ leftarrow (1- \ omega) \ phi _ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii} }} (b_ {i} - \ sigma)}![\ phi _ {i} ^ {{(k + 1)}} \ leftarrow (1- \ omega) \ phi _ {i} ^ {{(k)}} + {\ frac {\ omega} {a _ { {ii}}}} (b_ {i} - \ sigma)](https://wikimedia.org/api/rest_v1/media/math/render/svg/57acc10b2d40c697c9b6dc2b97ef2320117b3f39)
Konec (smyčka i )
Zkontrolujte konvergenci.
Konec (opakování smyčky)
Poznámka: lze také psát . To ušetří násobení na každé iteraci.
(1-ω)ϕi(k)+ωnaii(bi-σ){\ displaystyle (1- \ omega) \ phi _ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} (b_ {i} - \ sigma)}
ϕi(k)+ω(bi-σnaii-ϕi(k)){\ displaystyle \ phi _ {i} ^ {(k)} + \ omega \ left ({\ frac {b_ {i} - \ sigma} {a_ {ii}}} - \ phi _ {i} ^ {( k)} \ vpravo)}![\ phi _ {i} ^ {{(k)}} + \ omega \ left ({\ frac {b_ {i} - \ sigma} {a _ {{ii}}}} - \ phi _ {i} ^ {{(k)}} \ vpravo)](https://wikimedia.org/api/rest_v1/media/math/render/svg/81b22ca37b678342cc39c4fad915f9344f223906)
Další aplikace metody
Podobnou techniku lze použít pro jakoukoli iterační metodu. Předpokládá se, že iteraci lze zapsat ve tvaru:
Xne+1=F(Xne){\ displaystyle x_ {n + 1} = f (x_ {n})}
pak se upravená metoda stane:
Xne+1SÓR=(1-ω)XneSÓR+ωF(XneSÓR){\ displaystyle x_ {n + 1} ^ {\ mathrm {SOR}} = (1- \ omega) x_ {n} ^ {\ mathrm {SOR}} + \ omega f (x_ {n} ^ {\ mathrm { SOR}})}
nebo ekvivalent:
Xne=ωXne-1+(1-ω)Xne-2{\ displaystyle x_ {n} = \ omega x_ {n-1} + (1- \ omega) x_ {n-2}}
ω<1{\ displaystyle \ omega <1}
V praxi se volba používá k urychlení konvergence, zatímco volba se často používá ke konvergenci odlišného procesu.
ω>1{\ displaystyle \ omega> 1}
ω<1{\ displaystyle \ omega <1}![\ omega <1](https://wikimedia.org/api/rest_v1/media/math/render/svg/15318c387700b36db75e6abed614ea134435a96d)
Existuje mnoho způsobů, jak se na základě chování algoritmu rozhodnout, jakou hodnotu má parametr dát . V zásadě tyto metody umožňují v mnoha případech superlineární konvergenci, ale v některých případech mohou selhat.
ω{\ displaystyle \ omega}![\ omega](https://wikimedia.org/api/rest_v1/media/math/render/svg/48eff443f9de7a985bb94ca3bde20813ea737be8)
Podívejte se také
Poznámky
-
David M. Young , Iterační metody pro řešení parciálních diferenciálních rovnic eliptického typu , sv. Disertační práce, Harvardská univerzita,1 st 05. 1950( číst online )
Reference
Externí odkaz
(en) Modul pro metodu SOR
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">