Método de excesso de relaxamento sucessivo
Na análise numérica , o método de superelaxamento sucessivo (em inglês: Successive Overrelaxation Method, abreviado como SOR) é uma variante do método de Gauss-Seidel para resolver um sistema de equações lineares . A convergência desse algoritmo é geralmente mais rápida. Uma abordagem semelhante pode ser aplicada a muitos métodos iterativos .
Este método foi descoberto simultaneamente por David M. Young, Jr. (in) e Stan Frankel em 1950 para resolver automaticamente sistemas lineares com computadores . Os métodos de excesso de relaxamento já foram usados antes. Citaremos o método de Lewis Fry Richardson e o método de
RV Southwell . Esses métodos foram projetados para seres humanos e exigiam um certo conhecimento para garantir a convergência . Esses métodos não puderam ser transcritos em um computador. Essas limitações foram discutidas na tese de David Young
Formulação
Consideramos um sistema linear de n equações com n incógnitas notadas x (que é um vetor ):
NOx=b{\ displaystyle A \ mathbf {x} = \ mathbf {b}}![A {\ mathbf x} = {\ mathbf b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45d894430af69e29d6dda5aacbf4bb19336226a0)
ou :
NO=[no11no12⋯no1nãono21no22⋯no2não⋮⋮⋱⋮nonão1nonão2⋯nonãonão],x=[x1x2⋮xnão],b=[b1b2⋮bnão].{\ 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} \ 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)
A sendo a soma de uma matriz diagonal observada D e duas matrizes triangulares (inferior e superior, respectivamente) observadas L e U :
NO=D+eu+vocêcomD=[no110⋯00no22⋯0⋮⋮⋱⋮00⋯nonãonão],eu=[00⋯0no210⋯0⋮⋮⋱⋮nonão1nonão2⋯0],você=[0no12⋯no1não00⋯no2não⋮⋮⋱⋮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 {com}} \ 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 & 0 & \ cdots & 0 \ end {bmatrix}},](https://wikimedia.org/api/rest_v1/media/math/render/svg/a212111236f45fae22c7bddfd3fc51552eeb3325)
o sistema de equações lineares pode ser reformulado por:
(D+ωeu)x=ωb-[ωvocê+(ω-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)
para todos os ω > 0.
O método de superelaxação sucessiva é um método iterativo inicializado pela escolha de um arbitrário, e onde cada iteração consiste em determinar o uso de acordo com a seguinte fórmula:
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+ωeu)xk+1=ωb-[ωvocê+(ω-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 matriz esquerda ( D + ωL ) sendo triangular, é fácil de calcular por:
xk+1{\ displaystyle x_ {k + 1}}![x_ {k + 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a54ef7b7d84549c053b24d7aa478bcde15f31056)
xeu(k+1)=(1-ω)xeu(k)+ωnoeueu(beu-∑j>eunoeujxj(k)-∑j<eunoeujxj(k+1)),eu=1,2,...,não.{\ displaystyle x_ {i} ^ {(k + 1)} = (1- \ omega) x_ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} \ left ( b_ {i} - \ sum _ {j> i} a_ {ij} x_ {j} ^ {(k)} - \ sum _ {j <i} a_ {ij} x_ {j} ^ {(k + 1 )} \ right), \ quad i = 1,2, \ ldots, n.}![{\ displaystyle x_ {i} ^ {(k + 1)} = (1- \ omega) x_ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} \ left ( b_ {i} - \ sum _ {j> i} a_ {ij} x_ {j} ^ {(k)} - \ sum _ {j <i} a_ {ij} x_ {j} ^ {(k + 1 )} \ right), \ quad i = 1,2, \ ldots, n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a051df613a664c268d57dfe12e20ac2f0c527b8a)
A escolha do fator de relaxação não é trivial e depende dos coeficientes da matriz. Para uma matriz definida positiva , podemos mostrar que o algoritmo é convergente para tudo . No entanto, queremos convergência o mais rápido possível. Observe que para um fator de relaxamento de 1, encontramos o método de Gauss-Seidelω∈]0,2[{\ displaystyle \ omega \ in] 0,2 [}
Algoritmo
Entrada: A , b , ω
Saída:ϕ{\ displaystyle \ phi}
Escolhemos uma solução inicial arbitrária .
Repita até a convergência
ϕ(0){\ displaystyle \ phi ^ {(0)}}![\ phi ^ {{(0)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20a822287cb90192df8ccd40c57bb82eeb4cc463)
Loop i de 1 a n
σ←0{\ displaystyle \ sigma \ leftarrow 0}![\ sigma \ leftarrow 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/920f73bc0bba40e42b7eb17f84f31444dafc1e64)
Loop j de 1 para i - 1
σ←σ+noeujϕ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)
Fim (loop j )
Loop j de i + 1 para n
σ←σ+noeujϕ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)
Fim (loop j )
ϕeu(k+1)←(1-ω)ϕeu(k)+ωnoeueu(beu-σ){\ 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)
Fim (laço i )
Verifique a convergência.
Fim (repetir loop)
Nota: também pode ser escrito . Isso salva uma multiplicação em cada iteração.
(1-ω)ϕeu(k)+ωnoeueu(beu-σ){\ displaystyle (1- \ omega) \ phi _ {i} ^ {(k)} + {\ frac {\ omega} {a_ {ii}}} (b_ {i} - \ sigma)}
ϕeu(k)+ω(beu-σnoeueu-ϕeu(k)){\ displaystyle \ phi _ {i} ^ {(k)} + \ omega \ left ({\ frac {b_ {i} - \ sigma} {a_ {ii}}} - \ phi _ {i} ^ {( k)} \ right)}![\ phi _ {i} ^ {{(k)}} + \ omega \ left ({\ frac {b_ {i} - \ sigma} {a _ {{ii}}}} - \ phi _ {i} ^ {{(k)}} \ right)](https://wikimedia.org/api/rest_v1/media/math/render/svg/81b22ca37b678342cc39c4fad915f9344f223906)
Outras aplicações do método
Uma técnica semelhante pode ser usada para qualquer método iterativo. Presume-se que a iteração pode ser escrita na forma:
xnão+1=f(xnão){\ displaystyle x_ {n + 1} = f (x_ {n})}
então o método modificado se torna:
xnão+1SOR=(1-ω)xnãoSOR+ωf(xnãoSOR){\ displaystyle x_ {n + 1} ^ {\ mathrm {SOR}} = (1- \ omega) x_ {n} ^ {\ mathrm {SOR}} + \ omega f (x_ {n} ^ {\ mathrm { SOR}})}
ou equivalente:
xnão=ωxnão-1+(1-ω)xnão-2{\ displaystyle x_ {n} = \ omega x_ {n-1} + (1- \ omega) x_ {n-2}}
ω<1{\ displaystyle \ omega <1}
Na prática, a escolha é usada para acelerar a convergência, enquanto a escolha é freqüentemente usada para convergir um processo divergente.
ω>1{\ displaystyle \ omega> 1}
ω<1{\ displaystyle \ omega <1}![\ omega <1](https://wikimedia.org/api/rest_v1/media/math/render/svg/15318c387700b36db75e6abed614ea134435a96d)
Existem muitas maneiras de decidir qual valor dar ao parâmetro , com base no comportamento do algoritmo. Em princípio, esses métodos permitem uma convergência superlinear em muitos casos, mas podem falhar em alguns casos.
ω{\ displaystyle \ omega}![\ómega](https://wikimedia.org/api/rest_v1/media/math/render/svg/48eff443f9de7a985bb94ca3bde20813ea737be8)
Veja também
Notas
-
David M. Young , Métodos iterativos para resolver equações de diferenças parciais de tipo elíptico , vol. Tese de doutorado, Harvard University,1 ° de maio de 1950( leia online )
Referências
Link externo
(en) Módulo para o Método SOR
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">