Gauss-Seidel Yöntemi
Sayısal lineer cebirde, tekrarlanan yöntemlerden biri olan, Liebmann yöntemi veya
ardışık yer değiştirme yöntemi olarak da bilinen Gauss –Seidel yöntemi, lineer
denklem sistemlerini çözmek için kullanılır. İsmini Alman matematikçiler Carl
Friedrich Gauss ve Philipp Ludvig von Seidel’in soyadlarından almıştır ve de Jacobi
yöntemiyle benzerdir. Gauss-Seidel yöntemi köşegenlerinde sıfır elemanı içermeyen
matrislere uygulanabilse de, yakınsaklık yalnızca, eğer matris hem
köşegenleştirilebilir hem de simetrik ve pozitif tanımlı ise sağlanır. Bundan yalnızca
1823 yılında Gauss’un öğrencisi Gerling’e olan mektubunda söz edilmişti. [1]. 1874
yılına kadar Seidel yöntemiyle ilgili bir açıklama gerçekleşmedi.
TANIM
Gauss- Seidel yöntemi, x bilinmeyenli nxn lineer denklem sistemlerini çözmek için
tekrarlanan bir tekniktir:
Alt üçgen matris bileşeni
ve üst üçgen matris bileşeni U’ya ayrılan A matrisi:
Ax=b denkleminde yerine konulursa,
Gauss-Seidel şu şekilde
. tanımlanabilir.
Daha ayrıntılı olarak A, x ve b bileşenleriyle yazılabilir.
,
,
.
Ayrıca A’nın alt üçgen matris bileşeni ve üst üçgen matris bileşeni
,
,
İle verilir.
Lineer denklem sistemleri tekrar
şeklinde yazılabilir.
O halde, Gauss-Seidel yöntemi sağ taraftaki x’in bir önceki değeri için sol taraftaki x’i
çözer. Çözüm olarak;
yazılabilir.
’in üçgen şeklinin avantajıyla birlikte,
’in elementleri sıralı olarak ileri ikame
ile hesaplanabilir.
Yineleme ile yapılan değişiklikler aynı tolerans altında olana kadar yani yeterince
küçük hataya ulaşana dek prosedür genellikle devam ettirilir.
TARTIŞMA
Gauss-Seidel yönteminin çapraz eleman formülü Jacobi yöntemininkiyle fazlasıyla
benzerdir.
’in hesaplanmasında yalnızca daha önce hesaplanmış olan
’in
elemanları ve (k+1). adım için henüz geliştirilmemiş olan x(k)’ nın elemanları
kullanılır. Jacobi yönteminin tersine Gauss-Seidel’de yalnızca bir depo vektör
gereklidir çünkü hesaplanan değerler üzerine yazılabilir, bu da çok büyük problemler
için bir avantaj anlamına gelebilir.
Bununla birlikte, Jacobi yönteminin tersine, her bir eleman için hesaplamalar paralel
olarak yapılamaz. Ayrıca, her adımdaki değerler orijinal denklemin sırasına bağlıdır.
Gauss-Seidel
ile alındığında SOR (Successive Over- Relaxation / ardışık
aşırı-gevşeme) ile aynı olur.
YAKINSAMA
Gauss-Seidel metodunun yakınsama özellikleri A matrisine bağlıdır. Yani, iki
maddeden biri sağlanırsa yakınsak olduğu bilinir.
A matrisi pozitif tanımlıdır
A matrisi kesin veya indirgenemez bir biçimde köşegen olarak baskındır.
Bu koşullar sağlanmasa da Gauss-Seidel metodu bazen yakınsaktır.
ALGORİTMA
Bu algoritmada elemanlar hesaplanmış olarak üzerine yazılabilir olduğundan, sadece
bir depolama vektör gereklidir ve vektör indisleme ihmal edilir. Algoritma aşağıdaki
gibidir:
Girdiler: A, b
Çıktılar:
Çözüme yakın bir başlangıç tahmini
seç
yakınsayana kadar tekrarla
for 1 den i ye kadar n kez
for 1 den j ye kadar n kez
if j ≠ i then
end if
end (j-döngüsü)
End (i-döngüsü)
yakınsamaya ulaşıldığında kontrol et
end repeat
Matris versiyonu için bir örnek :
denklemini sağlayan
ve
olarak verilmiştir.
ve
olarak verilsin.
denklemini
formunda
kullanacağız.
A matrisini , alt üçgen matris
toplamı
ve mutlak üst üçgen matris
‘nun
şeklinde ayrıştıracağız.
ve
‘nin tersi ise :
olarak bulunur.
Bulduğumuz değerler:
ve
elde
yi bulduğumuza göre bu değerleri kullanarak
edeceğiz.
vektörlerini iteratif olarak
Öncelikle başlangıç vektörünü yani
’ı seçmeliyiz. En iyi tahmin bizi en
hızlı algoritmaya götürecek.
Farzedelim ki;
Artık hesaplayabiliriz:
Tahmin edildiği gibi, bulduğumuz algoritma gerçek sonuca yakınsadı:
Aslında, A matrisi çapraz olarak baskındır.(Ama pozitif tanımlı değildir.)
Matris versiyonu için başka bir örnek :
Başka bir lineer sistem olan
denklemini sağlayan:
ve
olarak verilmiştir.
ve
olarak verilsin.
denklemini
formunda
kullanacağız.
A matrisini , alt üçgen matris
toplamı
şeklinde ayrıştıracağız.
ve
‘nin tersi ise :
Bulduğumuz değerler:
ve mutlak üst üçgen matris
‘nun
ve
elde
yi bulduğumuza göre bu değerleri kullanarak
vektörlerini iteratif olarak
edeceğiz.
Öncelikle başlangıç vektörünü yani
’ı seçmeliyiz. En iyi tahmin bizi en hızlı
algoritmaya götürecek.
Farzedelim ki;
Artık hesaplayabiliriz:
Yakınsama için test edersek , algoritmanın ıraksadığını bulacağız. Aslında , A matrisi
ne çapraz olarak baskındır ne de pozitif tanımlıdır.
O zaman gerçek değere yakınsarsak;
olur.
Bu durumda sonucun garanti olmadığı ve gerçekleşmeyeceği görülür .
Denklem uygulaması için bir örnek :
Başlangıç vektörü x0 ve diğer vektörleri xn şeklinde olan bir k denkleminin verildiğini
farzedelim.
İlk denklem
' in terimleri içindeki x1 için çözülür.
Bir sonraki denklem için xs. 'nin bir önceki değerleri kullanılır.
Daha iyi netleştirmek için şu örneği dikkate alalım:
,
,
ve
ün çözümü şu şekilde verilsin :
İlk olarak başlangıç yaklaşımını (0, 0, 0, 0) olarak seçtiğimizi varsayalım. O zaman ilk
yaklaşık çözüm;
ile verilir.
Elde edilen yaklaşımları kullanarak, istenilen hata mertebesine ulaşana dek iteratif
yöntem devam eder. 4 adımdan sonraki yaklaşık çözümler aşağıdaki gibidir.
Sistemin kesin çözümü (1,2,-1,1) şeklindedir.
Python 3 ve Numpy kullanımı için uygulama :
Aşağıdaki sayısal işlem çözüm vektörünü üretmek için basitçe yinelenir.
import numpy as np
ITERATION_LIMIT = 1000
# initialize the matrix
A = np.array([[10., -1., 2., 0.],
[-1., 11., -1., 3.],
[2., -1., 10., -1.],
[0.0, 3., -1., 8.]])
# initialize the RHS vector
b = np.array([6., 25., -11., 15.])
# prints the system
print("System:")
for i in range(A.shape[0]):
row = ["{}*x{}".format(A[i, j], j + 1) for j in range(A.shape[1])]
print(" + ".join(row), "=", b[i])
print()
x = np.zeros_like(b)
for it_count in range(ITERATION_LIMIT):
print("Current solution:", x)
x_new = np.zeros_like(x)
for i in range(A.shape[0]):
s1 = np.dot(A[i, :i], x_new[:i])
s2 = np.dot(A[i, i + 1:], x[i + 1:])
x_new[i] = (b[i] - s1 - s2) / A[i, i]
if np.allclose(x, x_new, rtol=1e-8):
break
x = x_new
print("Solution:")
print(x)
error = np.dot(A, x) - b
print("Error:")
print(error)
Elde edilen çıktılar :
System:
10.0*x1 + -1.0*x2 + 2.0*x3 + 0.0*x4 = 6.0
-1.0*x1 + 11.0*x2 + -1.0*x3 + 3.0*x4 = 25.0
2.0*x1 + -1.0*x2 + 10.0*x3 + -1.0*x4 = -11.0
0.0*x1 + 3.0*x2 + -1.0*x3 + 8.0*x4 = 15.0
Current solution:
Current solution:
Current solution:
Current solution:
Current solution:
Current solution:
Current solution:
Current solution:
Current solution:
Current solution:
Solution:
[ 1. 2. -1. 1.]
Error:
[ 2.06480930e-08
[
[
[
[
[
[
[
[
[
[
0. 0. 0.
0.6
1.03018182
1.00658504
1.00086098
1.00009128
1.00000836
1.00000067
1.00000004
1. 2. -1.
0.]
2.32727273
2.03693802
2.00355502
2.00029825
2.00002134
2.00000117
2.00000002
1.99999999
1.]
-1.25551054e-08
-0.98727273
-1.0144562
-1.00252738
-1.00030728
-1.00003115
-1.00000275
-1.00000021
-1.00000001
3.61417563e-11
0.00000000e+00]
Matlab kullanarak keyfi verilen denklemleri çözmek :
Aşağıda verilen kodu ,
formülü ile kullanırız:
0.87886364]
0.98434122]
0.99835095]
0.99984975]
0.9999881 ]
0.99999922]
0.99999996]
1.
]
function [x] = gauss_seidel(A, b, x0, iters)
n = length(A);
x = x0;
for k = 1:iters
for i = 1:n
x(i) = (1/A(i, i))*(b(i) - A(i, 1:n)*x + A(i, i)*x(i));
end
end
end
Download

Gauss-Seidel Yöntemi TANIM