Sor metod

Bilinmeyen x olmak üzere, n bilinmeyenli bir kare matris veriliyor:

${\displaystyle A\mathbf {x} =\mathbf {b} }$

Olmak üzere:

${\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 3 farklı kısma ayrılabilir.Bunlar: Köşegen Kısmı = D, and Alt üçgensel ve üst üçgensel kısım = L ve U:

${\displaystyle A=D+L+U,}$

${\displaystyle 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}}.}$

Lineer denklem sistemini tekrar yazarsak,

${\displaystyle (D+\omega L)\mathbf {x} =\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x} }$

ω > 1'den olmak üzere, w relaxation factordür.

successive over-relaxation bir iterative metot olarak sağ tarafta bulunan eski x değerini kullanarak sol taraftaki yeni x değerini bulmaya yardımcı olur.Analitik olarak, tekrar gösterirsek;

${\displaystyle \mathbf {x} ^{(k+1)}=(D+\omega L)^{-1}{\big (}\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x} ^{(k)}{\big )}=L_{w}\mathbf {x} ^{(k)}+\mathbf {c} .}$

Fakat,(D+ωL) üçgensel formundan yararlanılarak, x^(k+1)'in elementleri forward substitution yöntemiyle bulunabilir.

${\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+1)}-\sum _{j>i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n.}$

Relaxation faktörün ω seçilimi o kadar da kolay değildir, ve katsayılar matrisinin özelliklerine bağlıdır.1947'de, eğer Ostrowski ${\displaystyle A}$ matrisini simetrik ve pozitif tanımlamış olursa ${\displaystyle \rho (L_{\omega })<1}$ için ${\displaystyle 0<\omega <2}$ olduğu kanıtlanmış olur. Böylece iterasyon işleminin yakınsaması doğru olur, fakat biz yakınsamadan daha çok, hızlı yakınsama konusuyla ilgileniyoruz.

Sadece bir depolama vektörüne ihtiyaç duyulur ve endeksleme vektörü ihmal edilir çünkü bu algoritmayla hesaplanan değerler, elementlerin üzerine yazılır:

Girdiler: A, b, ω
Çıktılar: ${\displaystyle \phi }$

${\displaystyle \phi }$ başlangıç tahmini olarak alırsak
tekrar et yakınsayana kadar.

for i from 1 until n do

${\displaystyle \sigma \leftarrow 0}$

for j from 1 until n do

if j ≠ i then

${\displaystyle \sigma \leftarrow \sigma +a_{ij}\phi _{j}}$

end if

end (j-loop)

${\displaystyle \phi _{i}\leftarrow (1-\omega )\phi _{i}+{\frac {\omega }{a_{ii}}}(b_{i}-\sigma )}$

end (i-loop)

yakınsamaya ulaşınca kontrol et.

end (repeat)

Not:
${\displaystyle (1-\omega )\phi _{i}+{\frac {\omega }{a_{ii}}}(b_{i}-\sigma )}$ işlemi ${\displaystyle \phi _{i}+\omega \left({\frac {b_{i}-\sigma }{a_{ii}}}-\phi _{i}\right)}$ şeklinde yazılır, Bu da her dış for döngüsünün iterasyonu için bir çarpım işleminden kurtarır.

A simetrik matrisinin bir versiyonudur,

${\displaystyle U=L^{T},\,}$

Bu da Symmetric Successive Over-Relaxation, veya (SSOR) adını alır.

${\displaystyle P=\left({\frac {D}{\omega }}+L\right){\frac {1}{2-\omega }}D^{-1}\left({\frac {D}{\omega }}+U\right)}$,

iterasyon metodu da şu şekildedir;

${\displaystyle \mathbf {x} ^{k+1}=\mathbf {x} ^{k}-\gamma ^{k}P^{-1}(A\mathbf {x} ^{k}-\mathbf {b} ),\ k\geq 0.}$

SOR ve SSOR metotları David M. Young, Jr.. tarafından bulunmuştur.

Iterasyon metodunda da benzer teknik kullanılabilir. Eğer orijinal iterasyon aşağıdaki şu forma sahipse,

${\displaystyle x_{n+1}=f(x_{n})}$

değiştirilmiş versiyonunda ise aşağıdaki form kullanılır,

${\displaystyle x_{n+1}^{\mathrm {SOR} }=(1-\omega )x_{n}^{\mathrm {SOR} }+\omega f(x_{n}^{\mathrm {SOR} }).}$

Lineer denklem sistemlerini çözmek için yukarıda gösterilen formül,x’in tam vektör olması koşuluyla gerçekleşir. Eğer bu formül hesaplama da kullanılırsa, bir dahaki vektörün hesaplanması şu şekilde olur;

${\displaystyle \mathbf {x} ^{(k+1)}=(1-\omega )\mathbf {x} ^{(k)}+\omega L_{*}^{-1}(\mathbf {b} -U\mathbf {x} ^{(k)}).}$

  Yavaş yaklaşım işlemini hızlandırmak için ${\displaystyle \omega >1}$ değeri kullanılır eğer değer ${\displaystyle \omega <1}$  aralığındaysa ?  değeri sapma iterasyon işleminin yakınsamasında veya overshooting işlemindeki yakınsamanın hızlanmasında kullanılır.

Yakınsama işlemlerinin davranışlarına bağlı kalarak uyarlanılabilir relaxation parametresini ${\displaystyle \omega }$ bulunabilecek çeşitli metotlar vardır. Bulunan parametreler sadece süper-lineer yakınsamalarda bazı problemler için kullanılır, geri kalan içinse değiştirilmesi gerekir.

• Jacobi method
• Gaussian Belief Propagation
• Matrix splitting

• Şablon:CFDWiki
• Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. ISBN 0-89871-321-8.
• Black, Noel and Moore, Shirley, Successive Overrelaxation Method (MathWorld)
• Yousef Saad, Iterative Methods for Sparse Linear Systems, 1st edition, PWS, 1996.
• Netlib's copy of "Templates for the Solution of Linear Systems", by Barrett et al.
• Richard S. Varga 2002 Matrix Iterative Analysis, Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
• David M. Young, Jr. Iterative Solution of Large Linear Systems, Academic Press, 1971. (reprinted by Dover, 2003)

• Module for the SOR Method
• Tridiagonal linear system solver based on SOR, in C++