Egymást követő túllazító módszer
A numerikus analízis , a módszer a egymást követő overrelaxation (angolul: Az egymást követő Overrelaxation eljárás, rövidítve SOR) egy változata a Gauss-Seidel módszer megoldására rendszer lineáris egyenletek . Ennek az algoritmusnak a konvergenciája általában gyorsabb. Hasonló megközelítés alkalmazható számos iteratív módszerre .
Ezt a módszert David M. Young, Jr. (in) és Stan Frankel egyidejűleg fedezte fel 1950-ben annak érdekében, hogy a lineáris rendszereket automatikusan megoldják számítógépekkel . A túl relaxációs módszereket korábban is alkalmazták. Idézzük Lewis Fry Richardson és RV Southwell módszerét
. Ezeket a módszereket emberi lények számára tervezték, és bizonyos szakértelemre volt szükségük a konvergencia biztosítása érdekében . Ezeket a módszereket nem lehetett átírni számítógépen. Ezeket a korlátokat David Young tézisei tárgyalták
Megfogalmazás
N egyenlet lineáris rendszerét vesszük figyelembe n ismeretlen ismeretlen x-el (amely vektor ):
NÁL NÉLx=b{\ displaystyle A \ mathbf {x} = \ mathbf {b}}![A {\ mathbf x} = {\ mathbf b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45d894430af69e29d6dda5aacbf4bb19336226a0)
vagy:
NÁL NÉL=[nál nél11.nál nél12.⋯nál nél1nemnál nél21nál nél22.⋯nál nél2nem⋮⋮⋱⋮nál nélnem1nál nélnem2⋯nál nélnemnem],x=[x1x2⋮xnem],b=[b1b2⋮bnem].{\ 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}} és a _ {{12}} & \ cdots és a _ {{1n}} \\ a _ {{21}} és a _ {{22} } & \ cdots & a _ {{2n}} \\\ vdots & \ vdots & \ ddots & \ vdots \\ a _ {{n1}} és 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} }.](https://wikimedia.org/api/rest_v1/media/math/render/svg/98608e9e95d5acad149813eca75c8108acec308a)
Egy , hogy az összeg a diagonális mátrix jegyezni D és két háromszög alakú mátrixok (alsó-felső -kal) Megjegyzendő, L és U :
NÁL NÉL=D+L+Uval velD=[nál nél11.0⋯00nál nél22.⋯0⋮⋮⋱⋮00⋯nál nélnemnem],L=[00⋯0nál nél210⋯0⋮⋮⋱⋮nál nélnem1nál nélnem2⋯0],U=[0nál nél12.⋯nál nél1nem00⋯nál nél2nem⋮⋮⋱⋮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 & 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 és 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)
a lineáris egyenletrendszer a következőképpen alakítható át:
(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)
minden ω > 0 esetén.
Az egymást követő overrelaxation módszer egy iteratív eljárás, inicializálja a választás egy tetszőleges, és ahol minden egyes iteráció meghatározásából áll segítségével az alábbi képlet szerint:
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)
A bal mátrix ( D + ωL ) háromszög alakú, így könnyen kiszámítható :
xk+1{\ displaystyle x_ {k + 1}}![x_ {k + 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a54ef7b7d84549c053b24d7aa478bcde15f31056)
xén(k+1)=(1-ω)xén(k)+ωnál nélénén(bén-∑j>énnál nélénjxj(k)-∑j<énnál nélénjxj(k+1)),én=1,2,...,nem.{\ displaystyle x_ {i} ^ {(k + 1)} = (1- \ omega) x_ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} \ bal ( b_ {i} - \ összeg _ {j> i} a_ {ij} x_ {j} ^ {(k)} - \ összeg _ {j <i} a_ {ij} x_ {j} ^ {(k + 1 )} \ jobbra), \ quad i = 1,2, \ ldots, n.}![{\ displaystyle x_ {i} ^ {(k + 1)} = (1- \ omega) x_ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} \ bal ( b_ {i} - \ összeg _ {j> i} a_ {ij} x_ {j} ^ {(k)} - \ összeg _ {j <i} a_ {ij} x_ {j} ^ {(k + 1 )} \ jobbra), \ quad i = 1,2, \ ldots, n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a051df613a664c268d57dfe12e20ac2f0c527b8a)
A relaxációs faktor megválasztása nem triviális, és a mátrix együtthatóitól függ. Egy pozitív definit mátrix , meg tudjuk mutatni, hogy az algoritmus konvergens mindent . A konvergenciát azonban a lehető leggyorsabban szeretnénk elérni. Megjegyezzük, hogy 1 relaxációs tényező esetén találkozunk a Gauss-Seidel módszerrelω∈]0,2[{\ displaystyle \ omega \ in] 0,2 [}
Algoritmus
Bemenet: A , b , ω
Kimenet:ϕ{\ displaystyle \ phi}
Kezdeti tetszőleges megoldást választunk .
Ismételje meg a konvergenciáig
ϕ(0){\ displaystyle \ phi ^ {(0)}}![\ phi ^ {{(0)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20a822287cb90192df8ccd40c57bb82eeb4cc463)
Hurok i a 1- a n
σ←0{\ displaystyle \ sigma \ leftarrow 0}![\ sigma \ baloldali 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/920f73bc0bba40e42b7eb17f84f31444dafc1e64)
Hurok j a 1 a i - 1
σ←σ+nál nélénjϕ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)
Vége ( j hurok )
Hurok j a i + 1 , hogy N
σ←σ+nál nélénjϕ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)
Vége ( j hurok )
ϕén(k+1)←(1-ω)ϕén(k)+ωnál nélénén(bén-σ){\ 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)
Vége ( i hurok )
Ellenőrizze a konvergenciát.
Vége (ciklus ismétlése)
Megjegyzés: írható is . Ez minden iterációnál szorzást takarít meg.
(1-ω)ϕén(k)+ωnál nélénén(bén-σ){\ displaystyle (1- \ omega) \ phi _ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} (b_ {i} - \ sigma)}
ϕén(k)+ω(bén-σnál nélénén-ϕén(k)){\ displaystyle \ phi _ {i} ^ {(k)} + \ omega \ left ({\ frac {b_ {i} - \ sigma} {a_ {ii}}} - \ phi _ {i} ^ {( k)} \ jobbra)}![\ phi _ {i} ^ {{(k)}} + \ omega \ left ({\ frac {b_ {i} - \ sigma} {a _ {{ii}}}} - \ phi _ {i} ^ {{(k)}} \ jobbra)](https://wikimedia.org/api/rest_v1/media/math/render/svg/81b22ca37b678342cc39c4fad915f9344f223906)
A módszer egyéb alkalmazásai
Hasonló technika bármely iteratív módszerhez alkalmazható. Feltételezzük, hogy az iteráció a következő formában írható:
xnem+1=f(xnem){\ displaystyle x_ {n + 1} = f (x_ {n})}
akkor a módosított módszer:
xnem+1SOR=(1-ω)xnemSOR+ωf(xnemSOR){\ displaystyle x_ {n + 1} ^ {\ mathrm {SOR}} = (1- \ omega) x_ {n} ^ {\ mathrm {SOR}} + \ omega f (x_ {n} ^ {\ mathrm { SOR}})}
vagy azonos:
xnem=ωxnem-1+(1-ω)xnem-2{\ displaystyle x_ {n} = \ omega x_ {n-1} + (1- \ omega) x_ {n-2}}
ω<1{\ displaystyle \ omega <1}
A gyakorlatban a választást a konvergencia felgyorsítására használják, míg a választást a divergens folyamat konvergálására használják.
ω>1{\ displaystyle \ omega> 1}
ω<1{\ displaystyle \ omega <1}![\ omega <1](https://wikimedia.org/api/rest_v1/media/math/render/svg/15318c387700b36db75e6abed614ea134435a96d)
Az algoritmus viselkedése alapján sokféleképpen lehet eldönteni, hogy milyen értéket adjunk a paraméternek . Elvileg ezek a módszerek sok esetben lehetővé teszik a szuperlineáris konvergenciát, de egyes esetekben kudarcot vallanak.
ω{\ displaystyle \ omega}![\omega](https://wikimedia.org/api/rest_v1/media/math/render/svg/48eff443f9de7a985bb94ca3bde20813ea737be8)
Lásd is
Megjegyzések
-
David M. Young , Iteratív módszerek elliptikus típusú parciális differenciálegyenletek megoldására , vol. PhD értekezés tétele, Harvard University,1 st május 1950( online olvasás )
Hivatkozások
Külső hivatkozás
(en) Modul a SOR módszerhez
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">