Peräkkäinen ylirelaxointimenetelmä
On numeerinen analyysi , menetelmää peräkkäisten overrelaxation (in Englanti: perättäiset Overrelaxation menetelmä, lyhennetty SOR) on muunnos Gaussin-Seidel menetelmä ratkaista järjestelmän lineaarisen yhtälöryhmän . Tämän algoritmin lähentyminen on yleensä nopeampaa. Samanlaista lähestymistapaa voidaan soveltaa moniin iteratiivisiin menetelmiin .
Tämän menetelmän löysivät samanaikaisesti David M. Young, Jr (vuonna) ja Stan Frankel vuonna 1950 lineaaristen järjestelmien automaattisen ratkaisemiseksi tietokoneilla . Yli rentoutumismenetelmiä on käytetty aiemmin. Mainitsemme Lewis Fry Richardsonin menetelmän ja RV Southwellin menetelmän
. Nämä menetelmät on suunniteltu ihmisille ja vaativat tiettyä asiantuntemusta lähentymisen varmistamiseksi . Näitä menetelmiä ei voitu kirjoittaa tietokoneella. Näitä rajoituksia käsiteltiin David Youngin opinnäytetyössä
Formulaatio
Tarkastellaan lineaarista n yhtälön järjestelmää, jossa on n tuntematonta x: tä (joka on vektori ):
ATx=b{\ displaystyle A \ mathbf {x} = \ mathbf {b}}![A {\ mathbf x} = {\ mathbf b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45d894430af69e29d6dda5aacbf4bb19336226a0)
tai:
AT=[klo11klo12⋯klo1eiklo21klo22⋯klo2ei⋮⋮⋱⋮kloei1kloei2⋯kloeiei],x=[x1x2⋮xei],b=[b1b2⋮bei].{\ 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 = {\ aloita {bmatrix} a _ {{11}} & a _ {{12}} & \ cdots & a {{1n}} \\ a _ {{21}} ja a {{22} } & \ cdots & a _ {{2n}} \\\ vdots & \ vdots & \ ddots & \ vdots \\ a _ {{n1}} ja 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)
On summa a diagonaalinen matriisi huomattava D ja kaksi kolmion matriisit (alempi ja ylempi vastaavasti) huomattava L ja U :
AT=D.+L+UkanssaD.=[klo110⋯00klo22⋯0⋮⋮⋱⋮00⋯kloeiei],L=[00⋯0klo210⋯0⋮⋮⋱⋮kloei1kloei2⋯0],U=[0klo12⋯klo1ei00⋯klo2ei⋮⋮⋱⋮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 & 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)
lineaaristen yhtälöiden järjestelmä voidaan muotoilla uudelleen:
(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)
kaikille ω > 0.
Peräkkäinen ylirelaksointimenetelmä on iteratiivinen menetelmä, joka alustetaan valitsemalla mielivaltainen, ja jossa kukin iterointi koostuu määrittämisestä käyttäen seuraavaa kaavaa:
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)
Vasen matriisi ( D + ωL ) on kolmiomainen, joten se on helppo laskea :
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)+ωkloii(bi-∑j>ikloijxj(k)-∑j<ikloijxj(k+1)),i=1,2,...,ei.{\ displaystyle x_ {i} ^ {(k + 1)} = (1- \ omega) x_ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} \ vasen ( b_ {i} - \ summa _ {j> i} a_ {ij} x_ {j} ^ {(k)} - \ summa _ {j <i} a_ {ij} x_ {j} ^ {(k + 1 )} \ oikea), \ quad i = 1,2, \ ldots, n.}![{\ displaystyle x_ {i} ^ {(k + 1)} = (1- \ omega) x_ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} \ vasen ( b_ {i} - \ summa _ {j> i} a_ {ij} x_ {j} ^ {(k)} - \ summa _ {j <i} a_ {ij} x_ {j} ^ {(k + 1 )} \ oikea), \ quad i = 1,2, \ ldots, n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a051df613a664c268d57dfe12e20ac2f0c527b8a)
Rentoutumistekijän valinta ei ole triviaali ja riippuu matriisin kertoimista. Saat positiividefiniitti matriisi , voimme osoittaa, että algoritmi on yhtenevä kaikesta . Haluamme kuitenkin lähentymisen mahdollisimman nopeasti. Huomaa, että kun relaksaatiokerroin on 1, kohtaamme Gauss-Seidel-menetelmänω∈]0,2[{\ displaystyle \ omega \ in] 0,2 [}
Algoritmi
Tulo: A , b , ω
Lähtö:ϕ{\ displaystyle \ phi}
Valitsemme ensimmäisen mielivaltaisen ratkaisun .
Toista kunnes lähentyminen
ϕ(0){\ displaystyle \ phi ^ {(0)}}![\ phi ^ {{(0)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20a822287cb90192df8ccd40c57bb82eeb4cc463)
Silmukka i välillä 1 - n
σ←0{\ displaystyle \ sigma \ vasen nuoli 0}![\ sigma \ vasen nuoli 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/920f73bc0bba40e42b7eb17f84f31444dafc1e64)
Silmukka j välillä 1 - i - 1
σ←σ+kloijϕj(k+1){\ displaystyle \ sigma \ vasen nuoli \ sigma + a_ {ij} \ phi _ {j} ^ {(k + 1)}}![\ sigma \ vasen nuoli \ sigma + a _ {{ij}} \ phi _ {j} ^ {{(k + 1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1aa628be5adb6691850bee24c3749ff4e9cdf49d)
Loppu (silmukka j )
Silmukka j välillä i + 1 - n
σ←σ+kloijϕj(k){\ displaystyle \ sigma \ vasen nuoli \ sigma + a_ {ij} \ phi _ {j} ^ {(k)}}![\ sigma \ vasen nuoli \ sigma + a _ {{ij}} \ phi _ {j} ^ {{(k)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7b7fc5ea6c033fb7356b623c0e9d2d3d1404521)
Loppu (silmukka j )
ϕi(k+1)←(1-ω)ϕi(k)+ωkloii(bi-σ){\ displaystyle \ phi _ {i} ^ {(k + 1)} \ vasen nuoli (1- \ omega) \ phi _ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii} }} (b_ {i} - \ sigma)}![\ phi _ {i} ^ {{(k + 1)}} \ vasen nuoli (1- \ omega) \ phi _ {i} ^ {{(k)}} + {\ frac {\ omega} {a _ { {ii}}}} (b_ {i} - \ sigma)](https://wikimedia.org/api/rest_v1/media/math/render/svg/57acc10b2d40c697c9b6dc2b97ef2320117b3f39)
Loppu (silmukka i )
Tarkista lähentyminen.
Loppu (toista silmukka)
Huomaa: voidaan myös kirjoittaa . Tämä säästää jokaisen iteraation kertoimen.
(1-ω)ϕi(k)+ωkloii(bi-σ){\ displaystyle (1- \ omega) \ phi _ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} (b_ {i} - \ sigma)}
ϕi(k)+ω(bi-σkloii-ϕi(k)){\ displaystyle \ phi _ {i} ^ {(k)} + \ omega \ left ({\ frac {b_ {i} - \ sigma} {a_ {ii}}} - \ phi _ {i} ^ {( k)} \ oikea)}![\ phi _ {i} ^ {{(k)}} + \ omega \ vasen ({\ frac {b_ {i} - \ sigma} {a _ {{ii}}}} - \ phi _ {i} ^ {{(k)}} \ oikea)](https://wikimedia.org/api/rest_v1/media/math/render/svg/81b22ca37b678342cc39c4fad915f9344f223906)
Menetelmän muut sovellukset
Samanlaista tekniikkaa voidaan käyttää mihin tahansa iteratiiviseen menetelmään. Oletetaan, että iteraatio voidaan kirjoittaa muodossa:
xei+1=f(xei){\ displaystyle x_ {n + 1} = f (x_ {n})}
sitten muunnetusta menetelmästä tulee:
xei+1SOR=(1-ω)xeiSOR+ωf(xeiSOR){\ displaystyle x_ {n + 1} ^ {\ mathrm {SOR}} = (1- \ omega) x_ {n} ^ {\ mathrm {SOR}} + \ omega f (x_ {n} ^ {\ mathrm { SOR}})}
Tai vastaava:
xei=ωxei-1+(1-ω)xei-2{\ displaystyle x_ {n} = \ omega x_ {n-1} + (1- \ omega) x_ {n-2}}
ω<1{\ displaystyle \ omega <1}
Käytännössä valintaa käytetään lähentymisen nopeuttamiseen, kun taas valintaa käytetään usein erilaisten prosessien lähentämiseen.
ω>1{\ displaystyle \ omega> 1}
ω<1{\ displaystyle \ omega <1}![\ omega <1](https://wikimedia.org/api/rest_v1/media/math/render/svg/15318c387700b36db75e6abed614ea134435a96d)
On monia tapoja päättää, mikä arvo annetaan parametrille algoritmin käyttäytymisen perusteella. Periaatteessa nämä menetelmät mahdollistavat superlineaarisen lähentymisen monissa tapauksissa, mutta joissakin tapauksissa ne voivat epäonnistua.
ω{\ displaystyle \ omega}![\ omega](https://wikimedia.org/api/rest_v1/media/math/render/svg/48eff443f9de7a985bb94ca3bde20813ea737be8)
Katso myös
Huomautuksia
-
David M. Young , Iteratiiviset menetelmät elliptisen tyypin osittaisten erotusyhtälöiden ratkaisemiseksi , vol. Väitöskirja, Harvardin yliopisto,1. st toukokuu 1950( lue verkossa )
Viitteet
Ulkoinen linkki
(en) SOR-menetelmän moduuli
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">