Sor metod - Vikipedi
İçeriğe atla
Ana menü
Gezinti
  • Anasayfa
  • Hakkımızda
  • İçindekiler
  • Rastgele madde
  • Seçkin içerik
  • Yakınımdakiler
Katılım
  • Deneme tahtası
  • Köy çeşmesi
  • Son değişiklikler
  • Dosya yükle
  • Topluluk portalı
  • Wikimedia dükkânı
  • Yardım
  • Özel sayfalar
Vikipedi Özgür Ansiklopedi
Ara
  • Bağış yapın
  • Hesap oluştur
  • Oturum aç
  • Bağış yapın
  • Hesap oluştur
  • Oturum aç

İçindekiler

  • Giriş
  • 1 Formülleme
  • 2 Algoritma
  • 3 Simetrik successive over-relaxation
  • 4 diğer uygulama alanları
  • 5 Ayrıca bakınız
  • 6 Notlar
  • 7 Kaynakça
  • 8 Dış bağlantılar

Sor metod

Bağlantı ekle
  • Madde
  • Tartışma
  • Oku
  • Değiştir
  • Kaynağı değiştir
  • Geçmişi gör
Araçlar
Eylemler
  • Oku
  • Değiştir
  • Kaynağı değiştir
  • Geçmişi gör
Genel
  • Sayfaya bağlantılar
  • İlgili değişiklikler
  • Kalıcı bağlantı
  • Sayfa bilgisi
  • Bu sayfayı kaynak göster
  • Kısaltılmış URL'yi al
  • Karekodu indir
Yazdır/dışa aktar
  • Bir kitap oluştur
  • PDF olarak indir
  • Basılmaya uygun görünüm
Diğer projelerde
  • Vikiveri ögesi
Görünüm
Vikipedi, özgür ansiklopedi
Bu madde, Vikipedi biçem el kitabına uygun değildir. Maddeyi, Vikipedi standartlarına uygun biçimde düzenleyerek Vikipedi'ye katkıda bulunabilirsiniz. Gerekli düzenleme yapılmadan bu şablon kaldırılmamalıdır. (Nisan 2017)

Successive Over-Relaxation (SOR) lineer denklem sistemlerini çözmek ve sonuca daha hızlı yakınsamak için sayısal lineer cebirde kullanılan bir çeşit Gauss-Seidel metodudur. Daha yavaş yakınsamalar içinse benzer bir metot olan iterative metot kullanılır.

David M. Young, Jr. ve H.Frankel tarafından 1950 yılında lineer sistemlerini otomatik olarak bilgisayar yardımıyla bulunması amacıyla eş zamanlı olarak ortaya konulmuştur.Over-Relaxation Young ve Frankel öncesinde de kullanılıyordu. Lewis Fry Richardson ve R. V. Southwell tarafından ayrı ayrı bulunan metotlar bunlara örnek verilebilir.Ama, bu metotlar beşeri hesaplamalar için tasarlanmıştı ve onları bilgisayar programlamada uygulanamaz hale getiren bazı uzmanlıklar gereklidir. David M. Young, Jr. tezinde metotlara bu yönden yaklaşmıştır.[1]

Formülleme

[değiştir | kaynağı değiştir]

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

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

Olmak üzere:

A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ] , x = [ x 1 x 2 ⋮ x n ] , b = [ b 1 b 2 ⋮ b n ] . {\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}}.} {\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:

A = D + L + U , {\displaystyle A=D+L+U,} {\displaystyle A=D+L+U,}
D = [ a 11 0 ⋯ 0 0 a 22 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ a n n ] , L = [ 0 0 ⋯ 0 a 21 0 ⋯ 0 ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ 0 ] , U = [ 0 a 12 ⋯ a 1 n 0 0 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ 0 ] . {\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}}.} {\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,

( D + ω L ) x = ω b − [ ω U + ( ω − 1 ) D ] x {\displaystyle (D+\omega L)\mathbf {x} =\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x} } {\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;
x ( k + 1 ) = ( D + ω L ) − 1 ( ω b − [ ω U + ( ω − 1 ) D ] x ( k ) ) = L w x ( k ) + c . {\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} .} {\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.

x i ( k + 1 ) = ( 1 − ω ) x i ( k ) + ω a i i ( b i − ∑ j < i a i j x j ( k + 1 ) − ∑ j > i a i j x j ( k ) ) , i = 1 , 2 , … , 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+1)}-\sum _{j>i}a_{ij}x_{j}^{(k)}\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+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 A {\displaystyle A} {\displaystyle A} matrisini simetrik ve pozitif tanımlamış olursa ρ ( L ω ) < 1 {\displaystyle \rho (L_{\omega })<1} {\displaystyle \rho (L_{\omega })<1} için 0 < ω < 2 {\displaystyle 0<\omega <2} {\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.

Algoritma

[değiştir | kaynağı değiştir]

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 }

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

for i from 1 until n do
σ ← 0 {\displaystyle \sigma \leftarrow 0} {\displaystyle \sigma \leftarrow 0}
for j from 1 until n do
if j ≠ i then
σ ← σ + a i j ϕ j {\displaystyle \sigma \leftarrow \sigma +a_{ij}\phi _{j}} {\displaystyle \sigma \leftarrow \sigma +a_{ij}\phi _{j}}
end if
end (j-loop)
ϕ i ← ( 1 − ω ) ϕ i + ω a i i ( b i − σ ) {\displaystyle \phi _{i}\leftarrow (1-\omega )\phi _{i}+{\frac {\omega }{a_{ii}}}(b_{i}-\sigma )} {\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:
( 1 − ω ) ϕ i + ω a i i ( b i − σ ) {\displaystyle (1-\omega )\phi _{i}+{\frac {\omega }{a_{ii}}}(b_{i}-\sigma )} {\displaystyle (1-\omega )\phi _{i}+{\frac {\omega }{a_{ii}}}(b_{i}-\sigma )} işlemi ϕ i + ω ( b i − σ a i i − ϕ i ) {\displaystyle \phi _{i}+\omega \left({\frac {b_{i}-\sigma }{a_{ii}}}-\phi _{i}\right)} {\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.

Simetrik successive over-relaxation

[değiştir | kaynağı değiştir]

A simetrik matrisinin bir versiyonudur,

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

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

P = ( D ω + L ) 1 2 − ω D − 1 ( D ω + U ) {\displaystyle P=\left({\frac {D}{\omega }}+L\right){\frac {1}{2-\omega }}D^{-1}\left({\frac {D}{\omega }}+U\right)} {\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;

x k + 1 = x k − γ k P − 1 ( A x k − b ) ,   k ≥ 0. {\displaystyle \mathbf {x} ^{k+1}=\mathbf {x} ^{k}-\gamma ^{k}P^{-1}(A\mathbf {x} ^{k}-\mathbf {b} ),\ k\geq 0.} {\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.

diğer uygulama alanları

[değiştir | kaynağı değiştir]
Ana madde: Richardson extrapolation

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

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

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

x n + 1 S O R = ( 1 − ω ) x n S O R + ω f ( x n S O R ) . {\displaystyle x_{n+1}^{\mathrm {SOR} }=(1-\omega )x_{n}^{\mathrm {SOR} }+\omega f(x_{n}^{\mathrm {SOR} }).} {\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;

x ( k + 1 ) = ( 1 − ω ) x ( k ) + ω L ∗ − 1 ( b − U x ( k ) ) . {\displaystyle \mathbf {x} ^{(k+1)}=(1-\omega )\mathbf {x} ^{(k)}+\omega L_{*}^{-1}(\mathbf {b} -U\mathbf {x} ^{(k)}).} {\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 
  
    
      
        ω
        >
        1
      
    
    {\displaystyle \omega >1}
  
{\displaystyle \omega >1} değeri kullanılır eğer değer 
  
    
      
        ω
        <
        1
      
    
    {\displaystyle \omega <1}
  
{\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 } {\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.

Ayrıca bakınız

[değiştir | kaynağı değiştir]
  • Jacobi method
  • Gaussian Belief Propagation
  • Matrix splitting

Notlar

[değiştir | kaynağı değiştir]
  1. ^ Young, David M. (1 Mayıs 1950), Iterative methods for solving partial difference equations of elliptical type (PDF), PhD thesis, Harvard University, 7 Haziran 2011 tarihinde kaynağından arşivlendi (PDF)15 Haziran 2009 

Kaynakça

[değiştir | kaynağı değiştir]
  • Ş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 23 Aralık 2014 tarihinde Wayback Machine sitesinde arşivlendi., 1st edition, PWS, 1996.
  • Netlib 4 Mart 2016 tarihinde Wayback Machine sitesinde arşivlendi.'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)

Dış bağlantılar

[değiştir | kaynağı değiştir]
  • Module for the SOR Method
  • Tridiagonal linear system solver based on SOR, in C++
"https://tr.wikipedia.org/w/index.php?title=Sor_metod&oldid=33124607" sayfasından alınmıştır
Kategori:
  • Lineer cebir
Gizli kategoriler:
  • Düzenlenmesi gereken maddeler Nisan 2017
  • Kırmızı bağlantıya sahip ana madde şablonu içeren maddeler
  • Webarşiv şablonu wayback bağlantıları
  • ISBN sihirli bağlantısını kullanan sayfalar
  • Sayfa en son 22.27, 12 Haziran 2024 tarihinde değiştirildi.
  • Metin Creative Commons Atıf-AynıLisanslaPaylaş Lisansı altındadır ve ek koşullar uygulanabilir. Bu siteyi kullanarak Kullanım Şartlarını ve Gizlilik Politikasını kabul etmiş olursunuz.
    Vikipedi® (ve Wikipedia®) kâr amacı gütmeyen kuruluş olan Wikimedia Foundation, Inc. tescilli markasıdır.
  • Gizlilik politikası
  • Vikipedi hakkında
  • Sorumluluk reddi
  • Davranış Kuralları
  • Geliştiriciler
  • İstatistikler
  • Çerez politikası
  • Mobil görünüm
  • Wikimedia Foundation
  • Powered by MediaWiki
Sor metod
Konu ekle