Gauss-Seidel yöntemi
Yöntem Gauss - Seidel bir olan yinelemeli bir yöntem , bir çözme lineer sistem formunun (sonlu boyutlu) bir dizisini oluşturur araçlar, bu bir tanesidir bir ve yakınsama koşullarına sahiptir Bu denklemin bir çözeltisine, doğru olan yakınsak memnun (örneğin simetrik pozitif tanımlı olduğunda ). Algoritma, köşegeninin sıfır olmayan öğelerden oluştuğunu varsayar .
ATx=b{\ displaystyle Ax = b}AT{\ displaystyle A}AT{\ displaystyle A}
Yöntem "blok" versiyonunda mevcuttur.
Yöntemin prensibi, doğrusal olmayan denklem sistemlerinin çözümüne ve optimizasyona kadar genişletilebilir , ancak daha az net verimlilik koşulları ile. Optimizasyonda, bu yaklaşımın faydası büyük ölçüde problemin yapısına bağlı olacaktır. Gauss-Seidelien ilkesi, diğer algoritmaları yorumlamayı da mümkün kılar.
Algoritma
Prensip
Dır-dir
ATx=b{\ displaystyle Ax = b}
Çözülecek lineer sistem, ve ile matris şeklinde yazıldığını varsayarsak , bu da matris çarpımının eşit olacağı şekilde arandığı anlamına gelir .
AT∈Rdeğil×değil{\ displaystyle A \ in \ mathbb {R} ^ {n \ times n}}b∈Rdeğil{\ displaystyle b \ in \ mathbb {R} ^ {n}}x∈Rdeğil{\ displaystyle x \ in \ mathbb {R} ^ {n}}ATx{\ displaystyle Baltası}b{\ displaystyle b}
Biz dikkat unsurlarını ve bu :
-debenj{\ displaystyle a_ {ij}}AT{\ displaystyle A}bben{\ displaystyle b_ {i}}b{\ displaystyle b}
AT=(-de11-de12⋯-de1değil-de21-de22⋯-de2değil⋮⋮⋱⋮-dedeğil1-dedeğil2⋯-dedeğildeğil)veb=(b1b2⋮bdeğil).{\ displaystyle A = {\ begin {pmatrix} 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 {pmatrix}} \ qquad {\ mbox {ve}} \ qquad b = {\ başlayın {pmatrix} b_ {1} \\ b_ {2} \\\ vdots \\ b_ {n} \ end {pmatrix}}.}
Gauss-Seidel lineer sistem çözer şekilde yinelemeli bu vektörler bir dizi oluşturur, bu araçların, için, . Örneğin , tekrarlanan akımın bir çözüme yeterince yakın olduğuna karar verildiğinde, örneğin kalıntı küçük olduğu için , dizinin hesaplanması kesintiye uğrar .
ATx=b{\ displaystyle Ax = b}xk∈Rdeğil{\ displaystyle x ^ {k} \ in \ mathbb {R} ^ {n}}k=0,1,2,...{\ displaystyle k = 0,1,2, \ noktalar}xk{\ displaystyle x ^ {k}} ATxk-b{\ displaystyle Baltası ^ {k} -b}
Ya mevcut yineleme. Sonraki yineleme , aşağıdaki gibi adımlarla hesaplanır .
xk=(x1k,...,xdeğilk)∈Rdeğil{\ displaystyle x ^ {k} = (x_ {1} ^ {k}, \ ldots, x_ {n} ^ {k}) \ in \ mathbb {R} ^ {n}}xk+1=(x1k+1,...,xdeğilk+1)∈Rdeğil{\ displaystyle x ^ {k + 1} = (x_ {1} ^ {k + 1}, \ ldots, x_ {n} ^ {k + 1}) \ in \ mathbb {R} ^ {n}}değil{\ displaystyle n}
-
1. Adım . Bunu varsayarsak ve bilirsek , lineer sistemin ilk denklemi ile hesaplayabiliriz . Daha doğrusu, bir çözüm olarak alınır.-de11≠0{\ displaystyle a_ {11} \ neq 0}(x2k,...,xdeğilk){\ displaystyle (x_ {2} ^ {k}, \ ldots, x_ {n} ^ {k})}x1k+1{\ displaystyle x_ {1} ^ {k + 1}}ATx=b{\ displaystyle Ax = b}x1k+1{\ displaystyle x_ {1} ^ {k + 1}}
-de11x1k+1_+-de12x2k+⋯+-de1değilxdeğilk=b1,{\ displaystyle a_ {11} {\ underline {x_ {1} ^ {k + 1}}} + a_ {12} x_ {2} ^ {k} + \ cdots + a_ {1n} x_ {n} ^ { k} = b_ {1},}
bu mümkün olsa da .-de11≠0{\ displaystyle a_ {11} \ neq 0}
-
2. Adım . Bunu varsayarsak ve bilirsek , lineer sistemin ikinci denklemi ile hesaplayabiliriz . Daha doğrusu, bir çözüm olarak alınır.-de22≠0{\ displaystyle a_ {22} \ neq 0}(x1k+1,x3k,...,xdeğilk){\ displaystyle (x_ {1} ^ {k + 1}, x_ {3} ^ {k}, \ ldots, x_ {n} ^ {k})}x2k+1{\ displaystyle x_ {2} ^ {k + 1}}ATx=b{\ displaystyle Ax = b}x2k+1{\ displaystyle x_ {2} ^ {k + 1}}
-de21x1k+1+-de22x2k+1_+-de23x3k+⋯+-de2değilxdeğilk=b2,{\ displaystyle a_ {21} x_ {1} ^ {k + 1} + a_ {22} {\ underline {x_ {2} ^ {k + 1}}} + a_ {23} x_ {3} ^ {k } + \ cdots + a_ {2n} x_ {n} ^ {k} = b_ {2},}
bu mümkün olsa da .-de22≠0{\ displaystyle a_ {22} \ neq 0}
-
Sahneben∈[[1,değil]]{\ displaystyle i \ [\! [1, n] \!]} (genel durum). Biz o varsayarsak ve bilerek , biz hesaplayabilirsiniz vasıtasıyla doğrusal bir sistemin -th denklemi . Daha doğrusu, bir çözüm olarak alınır.-debenben≠0{\ displaystyle a_ {ii} \ neq 0}(x1k+1,...,xben-1k+1,xben+1k,...,xdeğilk){\ displaystyle (x_ {1} ^ {k + 1}, \ ldots, x_ {i-1} ^ {k + 1}, x_ {i + 1} ^ {k}, \ ldots, x_ {n} ^ {k})}xbenk+1{\ displaystyle x_ {i} ^ {k + 1}}ben{\ displaystyle i}ATx=b{\ displaystyle Ax = b}xbenk+1{\ displaystyle x_ {i} ^ {k + 1}}
-deben1x1k+1+⋯+-deben,ben-1xben-1k+1+-debenbenxbenk+1_+-deben,ben+1xben+1k+⋯+-debendeğilxdeğilk=bben,{\ displaystyle a_ {i1} x_ {1} ^ {k + 1} + \ cdots + a_ {i, i-1} x_ {i-1} ^ {k + 1} + a_ {ii} {\ underline { x_ {i} ^ {k + 1}}} + a_ {i, i + 1} x_ {i + 1} ^ {k} + \ cdots + a_ {in} x_ {n} ^ {k} = b_ { ben},}
bu mümkün olsa da .-debenben≠0{\ displaystyle a_ {ii} \ neq 0}
Diyagonal elemanlarının Özetle, Resim sıfırdan farklı bileşenler hesaplanır tarafından için sıralı tarafından
AT{\ displaystyle A}xbenk+1{\ displaystyle x_ {i} ^ {k + 1}}xk+1{\ displaystyle x ^ {k + 1}}ben=1,...,değil{\ displaystyle i = 1, \ ldots, n}
xbenk+1=1-debenben(bben-∑j=1ben-1-debenjxjk+1-∑j=ben+1değil-debenjxjk).{\ displaystyle x_ {i} ^ {k + 1} = {\ frac {1} {a_ {ii}}} \ left (b_ {i} - \ sum _ {j = 1} ^ {i-1} a_ {ij} x_ {j} ^ {k + 1} - \ sum _ {j = i + 1} ^ {n} a_ {ij} x_ {j} ^ {k} \ sağ).}
Formül, önceki adımlarda hesaplanan öğeleri ( ) içerir .
xjk+1{\ displaystyle x_ {j} ^ {k + 1}}j=1,...,ben-1{\ displaystyle j = 1, \ noktalar, i-1}
Matris ifadesi
Algoritmanın matris ifadesi, matrisin aşağıdaki gibi parçalandığını
varsayarAT{\ displaystyle A}
AT=L+D+U,{\ displaystyle A = L + D + U,}
burada bir diyagonal parça arasında , (için daha düşük ) olan katı alt üçgen kısmı ve (için , üst , sıkı bir üst üçgen kısım).
D{\ displaystyle D}AT{\ displaystyle A}L{\ displaystyle L}U{\ displaystyle U}
'Den' e geçen Gauss-Seidel yönteminin bir yinelemesi , daha sonra alttaki üçgen sistemi çözmekten ibarettir.
xk{\ displaystyle x ^ {k}}xk+1{\ displaystyle x ^ {k + 1}}
(L+D)xk+1=b-Uxk,{\ displaystyle (L + D) x ^ {k + 1} = b-Ux ^ {k},}
"yukarıdan aşağıya", yani ardışık olarak belirleyerek , ..., .
x1k+1{\ displaystyle x_ {1} ^ {k + 1}}x2k+1{\ displaystyle x_ {2} ^ {k + 1}}xdeğilk+1{\ displaystyle x_ {n} ^ {k + 1}}
Yakınsama
Gauss-Seidel yönteminde yinelemeleri güncelleme formülü , bunların uygulamanın
sabit bir noktasının hesaplanması için ardışık yaklaşımlar olduğunu gösterir.
x↦(L+D)-1(b-Ux).{\ displaystyle x \ mapsto (L + D) ^ {- 1} (b-Ux).}
Yöntemin yakınsama özellikleri bu nedenle matrisin spektrumuna bağlı olacaktır .
(L+D)-1U{\ displaystyle (L + D) ^ {- 1} U}
Aşağıdaki durumlarda vektör ve başlangıç noktası ne olursa olsun Gauss-Seidel yönteminin yakınsadığını biliyoruz :
b{\ displaystyle b}x0{\ displaystyle x ^ {0}}
Tartışma
Tek bir vektördür ardışık yineler ezberlemek yeterli: adımında , bu elemanlar daha önce hesaplanan ezberlemek yeterli , yani için de, ve unsurları , yani, yine de yararlı için de, . Bu düşük bellek alanı gereksinimi, belirli durumlarda bir avantaj olabilir.
v∈Rdeğil{\ displaystyle v \ in \ mathbb {R} ^ {n}}ben{\ displaystyle i}xk+1{\ displaystyle x ^ {k + 1}}xjk+1{\ displaystyle x_ {j} ^ {k + 1}}j=1,...,ben-1{\ displaystyle j = 1, \ ldots, i-1}v1:ben-1{\ displaystyle v_ {1: i-1}}xk{\ displaystyle x ^ {k}}xjk{\ displaystyle x_ {j} ^ {k}}j=ben+1,...,değil{\ displaystyle j = i + 1, \ ldots, n}vben+1:değil{\ displaystyle v_ {i + 1: n}}
Jacobi yönteminin aksine, algoritma esasen sıralıdır ve bu nedenle paralel hesaplama için uygun değildir.
Genellemeler
Engelleme yöntemi
Gauss-Seidel yönteminin blok versiyonu, eleman yöntemine benzer bir şekilde ilerler, ancak burada bloklar olarak adlandırılan alt matrislerin elemanlarının kullanımı değiştirilir .
AT{\ displaystyle A}AT{\ displaystyle A}
Endeks kümesinin alt aralıklara bölündüğünü varsayıyoruz (boş olmayan ve ikiye iki ayrık):
[[1,değil]]{\ displaystyle [\! [1, n] \!]}p{\ displaystyle p}
[[1,değil]]=ben1∪ben2∪⋯∪benp.{\ displaystyle [\! [1, n] \!] = I_ {1} \ cup I_ {2} \ cup \ cdots \ cup I_ {p}.}
Matris ve vektör daha sonra aşağıdaki gibi ayrıştırılır
AT{\ displaystyle A}b{\ displaystyle b}
AT=(ATben1ben1ATben1ben2⋯ATben1benpATben2ben1ATben2ben2⋯ATben2benp⋮⋮⋱⋮ATbenpben1ATbenpben2⋯ATbenpbenp)veb=(bben1bben2⋮bbenp),{\ displaystyle A = {\ begin {pmatrix} A_ {I_ {1} I_ {1}} & A_ {I_ {1} I_ {2}} & \ cdots & A_ {I_ {1} I_ {p}} \ \ A_ {I_ {2} I_ {1}} & A_ {I_ {2} I_ {2}} & \ cdots & A_ {I_ {2} I_ {p}} \\\ vdots & \ vdots & \ ddots & \ vdots \\ A_ {I_ {p} I_ {1}} & A_ {I_ {p} I_ {2}} & \ cdots & A_ {I_ {p} I_ {p}} \ end {pmatrix}} \ qquad {\ mbox {ve}} \ qquad b = {\ begin {pmatrix} b_ {I_ {1}} \\ b_ {I_ {2}} \\\ vdots \\ b_ {I_ {p}} \ end {pmatrix }},}
burada alt olan vektör ile elemanlarının seçerek elde satır indeksleri ve sütun indeksleri ise, alt vektörüdür indisler sahip elemanlar seçilerek elde .
ATbenJ{\ displaystyle A_ {IJ}}AT{\ displaystyle A}ben{\ displaystyle I}J{\ displaystyle J}bben{\ displaystyle b_ {I}}b{\ displaystyle b}ben{\ displaystyle I}
Gauss-Seidel blok yöntemi , ile ana alt matrislerin tersinir olduğunu varsayar .ATbenbenbenben{\ displaystyle A_ {I_ {i} I_ {i}}}ben∈[[1,p]]{\ displaystyle i \ [\! [1, p] \!]}
Gauss-Seidel yönteminin , 'den' e geçen bloklar tarafından yinelenmesi, öğeye göre yöntem öğesi ile aynı şekilde yazılır, yani
xk{\ displaystyle x ^ {k}}xk+1{\ displaystyle x ^ {k + 1}}
(L+D)xk+1=b-Uxk,{\ displaystyle (L + D) x ^ {k + 1} = b-Ux ^ {k},}
ancak , ve için farklı tanımlarla :
L{\ displaystyle L}D{\ displaystyle D}U{\ displaystyle U}
L=(0⋯⋯0ATben2ben1⋱⋮⋮⋱⋱⋮ATbenpben1⋯ATbenpbenp-10),D=(ATben1ben10⋯00ATben2ben2⋱⋮⋮⋱⋱00⋯0ATbenpbenp)veU=AT-L-D.{\ displaystyle L = {\ begin {pmatrix} 0 & \ cdots & \ cdots & 0 \\ A_ {I_ {2} I_ {1}} & \ ddots && \ vdots \\\ vdots & \ ddots & \ ddots & \ vdots \\ A_ {I_ {p} I_ {1}} & \ cdots & A_ {I_ {p} I_ {p-1}} & 0 \ end {pmatrix}}, \ quad D = {\ begin {pmatrix } A_ {I_ {1} I_ {1}} & 0 & \ cdots & 0 \\ 0 & A_ {I_ {2} I_ {2}} & \ ddots & \ vdots \\\ vdots & \ ddots & \ ddots & 0 \\ 0 & \ cdots & 0 & A_ {I_ {p} I_ {p}} \ end {pmatrix}} \ quad {\ mbox {ve}} \ quad U = ALD.}
Yukarıdaki üçgen sistem bloğunun çözünürlüğü de bir "yukarıdan aşağıya" dır, yani ardışık olarak ..., belirleyerek .
xben1k+1{\ displaystyle x_ {I_ {1}} ^ {k + 1}}xben2k+1{\ displaystyle x_ {I_ {2}} ^ {k + 1}}xbenpk+1{\ displaystyle x_ {I_ {p}} ^ {k + 1}}
Doğrusal olmayan denklem sistemleri
Gauss-Seidel Yöntemin ilkesi, aynı zamanda doğrusal olmayan denklem sisteminin çözeltisine uygulanabilir burada, . Bu nedenle bu sistem, bilinmeyenlerle doğrusal olmayan denklemler şeklinde yazılmıştır :
F(x)=0{\ displaystyle F (x) = 0}F:Rdeğil→Rdeğil{\ displaystyle F: \ mathbb {R} ^ {n} \ - \ mathbb {R} ^ {n}}değil{\ displaystyle n}değil{\ displaystyle n}
{F1(x1,x2,...,xdeğil)=0F2(x1,x2,...,xdeğil)=0⋯Fdeğil(x1,x2,...,xdeğil)=0.{\ displaystyle \ sol \ {{\ başlar {dizi} {l} F_ {1} (x_ {1}, x_ {2}, \ ldots, x_ {n}) = 0 \\ F_ {2} (x_ { 1}, x_ {2}, \ ldots, x_ {n}) = 0 \\\ cdots \\ F_ {n} (x_ {1}, x_ {2}, \ ldots, x_ {n}) = 0. \ end {dizi}} \ sağ.}
Gauss-Seidel Dolayısıyla bu yöntem bir dizi vektör üreten iteratif bu sistemi çözer için, . Örneğin, kalıntı küçük olduğu için , mevcut yineleme, bir çözüme yeterince yakın olduğuna karar verildiğinde, dizinin hesaplanması kesintiye uğrar .
xk∈Rdeğil{\ displaystyle x ^ {k} \ in \ mathbb {R} ^ {n}}k=0,1,2,...{\ displaystyle k = 0,1,2, \ noktalar}xk{\ displaystyle x ^ {k}} F(xk){\ displaystyle F (x ^ {k})}
Ya mevcut yineleme. Sonraki yineleme , aşağıdaki gibi adımlarla hesaplanır .
xk=(x1k,...,xdeğilk)∈Rdeğil{\ displaystyle x ^ {k} = (x_ {1} ^ {k}, \ ldots, x_ {n} ^ {k}) \ in \ mathbb {R} ^ {n}}xk+1=(x1k+1,...,xdeğilk+1)∈Rdeğil{\ displaystyle x ^ {k + 1} = (x_ {1} ^ {k + 1}, \ ldots, x_ {n} ^ {k + 1}) \ in \ mathbb {R} ^ {n}}değil{\ displaystyle n}
-
1. Adım . Bilerek , doğrusal olmayan denklemin bir çözümü olarak hesaplıyoruz (var olması gerekiyordu):(x2k,...,xdeğilk){\ displaystyle (x_ {2} ^ {k}, \ ldots, x_ {n} ^ {k})}x1k+1{\ displaystyle x_ {1} ^ {k + 1}}
F1(x1k+1_,x2k,...,xdeğilk)=0.{\ displaystyle F_ {1} ({\ altı çizili {x_ {1} ^ {k + 1}}}, x_ {2} ^ {k}, \ ldots, x_ {n} ^ {k}) = 0.}
-
2. Adım . Bilerek , doğrusal olmayan denklemin bir çözümü olarak hesaplıyoruz (var olması gerekiyordu):(x1k+1,x3k,...,xdeğilk){\ displaystyle (x_ {1} ^ {k + 1}, x_ {3} ^ {k}, \ ldots, x_ {n} ^ {k})}x2k+1{\ displaystyle x_ {2} ^ {k + 1}}
F2(x1k+1,x2k+1_,x3k,...,xdeğilk)=0.{\ displaystyle F_ {2} (x_ {1} ^ {k + 1}, {\ underline {x_ {2} ^ {k + 1}}}, x_ {3} ^ {k}, \ ldots, x_ { n} ^ {k}) = 0.}
-
Sahneben∈[[1,değil]]{\ displaystyle i \ [\! [1, n] \!]} (genel durum). Bilerek , doğrusal olmayan denklemin bir çözümü olarak hesaplıyoruz (var olması gerekiyordu):(x1k+1,...,xben-1k+1,xben+1k,...,xdeğilk){\ displaystyle (x_ {1} ^ {k + 1}, \ ldots, x_ {i-1} ^ {k + 1}, x_ {i + 1} ^ {k}, \ ldots, x_ {n} ^ {k})}xbenk+1{\ displaystyle x_ {i} ^ {k + 1}}
Fben(x1k+1,...,xben-1k+1,xbenk+1_,xben+1k,...,xdeğilk)=0.{\ displaystyle F_ {i} (x_ {1} ^ {k + 1}, \ ldots, x_ {i-1} ^ {k + 1}, {\ underline {x_ {i} ^ {k + 1}} }, x_ {i + 1} ^ {k}, \ ldots, x_ {n} ^ {k}) = 0.}
Blok versiyonu , yukarıdaki gibi denklem ve bilinmeyenleri tek tek ele almak yerine, denklem grupları ve bilinmeyenler dikkate alınarak kolayca tanımlanabilir.
Optimizasyon
Bir önceki bölümde açıklanan Gauss-Seidel yönteminin prensibi doğal olarak doğrusal olmayan
optimizasyon problemi için de geçerlidir.
infx∈Xf(x),{\ displaystyle \ inf _ {x \ X içinde} \; f (x),}
burada bir işlevi bir alt kümesine göre en aza indiririz . Blok sayısı düşük olduğunda (genellikle ) en yararlı olan "blok" versiyonunun hemen altında sunuyoruz . Gauss-Seidel yöntemi , bu durumda verimlilik eksikliğinden dolayı, gerçekten büyük olduğunda alaka düzeyini kaybeder . "Eleman eleman" versiyonu , kardinal 1'in blokları alınarak elde edilen blok versiyonunun özel bir durumu olarak görülebilir .
f:Rdeğil→R{\ displaystyle f: \ mathbb {R} ^ {n} \ - \ mathbb {R}}X{\ displaystyle X}Rdeğil{\ displaystyle \ mathbb {R} ^ {n}}p{\ displaystyle p}p=2{\ displaystyle p = 2}p{\ displaystyle p}değil{\ displaystyle n}
Nedenle, endekslerin grubu varsayılır paylaştırıldı içine , bloklar
p{\ displaystyle p}
[[1,değil]]=ben1∪ben2∪⋯∪benp,{\ displaystyle [\! [1, n] \!] = I_ {1} \ fincan I_ {2} \ fincan \ cdots \ fincan I_ {p},}
ve kabul edilebilir kümenin, kümelerin Kartezyen çarpımı olduğunu ,
p{\ displaystyle p}
X=X1×X2×⋯×Xp,{\ displaystyle X = X_ {1} \ times X_ {2} \ times \ cdots \ times X_ {p},}
buradaki her bir a, dışbükey bir . Değişken aşağıdaki gibi ayrışacaktır
Xben{\ displaystyle X_ {i}}R|benben|{\ displaystyle \ mathbb {R} ^ {| I_ {i} |}}x∈Rdeğil{\ displaystyle x \ in \ mathbb {R} ^ {n}}
x=(xben1,xben2,...,xbenp).{\ displaystyle x = (x_ {I_ {1}}, x_ {I_ {2}}, \ ldots, x_ {I_ {p}}).}
Tüm bu türevlenebilir ve biz yöntemi uygulayarak bir Gauss-Seidel yöntemi elde edebilir Önceki bölümde için birinci dereceden eniyileme durumda , yani, bu kısıtsız optimizasyon sorununun
f{\ displaystyle f}X=Rdeğil{\ displaystyle X = \ mathbb {R} ^ {n}}
∇f(x)=0,{\ displaystyle \ nabla f (x) = 0,}
bilinmeyenlerle doğrusal olmayan denklemler sistemidir . Ancak, aşağıdaki gibi, sıralı olarak, blok blok en aza indirerek optimizasyon alanında kalmayı tercih edebiliriz . Bu seçenek, kısıtlamaları hesaba katma, yani değişkenleri kabul edilebilir küme ile sınırlama avantajına sahiptir .
değil{\ displaystyle n}değil{\ displaystyle n}x=(x1,...,xdeğil){\ displaystyle x = (x_ {1}, \ ldots, x_ {n})}f{\ displaystyle f}X{\ displaystyle X}
Gauss-Seidel metodu , böylece bir dizi üreten iteratif yukarıda optimizasyon sorunu çözer . Algoritma , bir defada bir değişken bloğunu sırayla en aza indirerek yinelemeden diğerine geçer . Örneğin, yansıtılan gradyanın normu yeterince küçük olduğu için, mevcut yineleme, bir çözüme yeterince yakın olduğuna karar verildiğinde, dizinin hesaplanması kesintiye uğrar .
{xk}⊂Rdeğil{\ displaystyle \ {x ^ {k} \} \ alt küme \ mathbb {R} ^ {n}}xk{\ displaystyle x ^ {k}}xk+1{\ displaystyle x ^ {k + 1}}f{\ displaystyle f}xk{\ displaystyle x ^ {k}} ‖gP(xk)‖{\ displaystyle \ | g ^ {\ rm {\ scriptscriptstyle P}} (x ^ {k}) \ |}
Optimizasyon Gauss-Seidel algoritması - bir yineleme mevcut yineleme geçer sonraki iterasyon için
de endeksli ardışık adımlarla :
xk∈X{\ displaystyle x ^ {k} \ X içinde}xk+1∈XX'te {\ displaystyle x ^ {k + 1} \}p{\ displaystyle p}ben=1,...,p{\ displaystyle i = 1, \ ldots, p}
xbenbenk+1∈-dergmbendeğilxbenben∈Xbenf(xben1k+1,...,xbenben-1k+1,xbenben,xbenben+1k,...,xbenpk).{\ displaystyle x_ {I_ {i}} ^ {k + 1} \ in \ operatorname {arg \, min} _ {x_ {I_ {i}} \ in X_ {i}} \, f (x_ {I_ { 1}} ^ {k + 1}, \ ldots, x_ {I_ {i-1}} ^ {k + 1}, x_ {I_ {i}}, x_ {I_ {i + 1}} ^ {k} , \ ldots, x_ {I_ {p}} ^ {k}).}
Öğe sürümüne göre öğe , kardinal 1'in blokları dikkate alınarak ve bileşen bileşen en aza indirilerek kolayca tanımlanır .
benben{\ displaystyle I_ {i}}f{\ displaystyle f}
Aşağıdaki sonuç, sınıf , zorlayıcı ve tamamen dışbükey olduğunda Gauss-Seidel yönteminin yakınsamasını gösterir .
f{\ displaystyle f}VS1{\ displaystyle C ^ {1}}
Optimizasyon Gauss-Seidel algoritmasının Yakınsama - Eğer her biri için , kapalı boş olmayan dışbükey olup ve eğer olduğunu zorlayıcı üzerinde kesinlikle üzerinde dışbükey ve sınıf bir mahallede , sonra
ben∈[[1,p]]{\ displaystyle i \ [\! [1, p] \!]}Xben{\ displaystyle X_ {i}}R|benben|{\ displaystyle \ mathbb {R} ^ {| I_ {i} |}}f{\ displaystyle f}X{\ displaystyle X}X{\ displaystyle X}VS1{\ displaystyle C ^ {1}}X{\ displaystyle X}
- yukarıdaki sorunun benzersiz bir çözümü var ,x¯{\ displaystyle {\ çubuğu {x}}}
- algoritma iyi tanımlanmıştır ve ilk yineleme ne olursa olsun , algoritma yakınsayan bir dizi oluşturur .x0∈X{\ displaystyle x ^ {0} \ X içinde}{xk}⊂X{\ displaystyle \ {x ^ {k} \} \ alt küme X}x¯{\ displaystyle {\ çubuğu {x}}}
Uyarılar
- Bir durumda, bu sonuç geçerli olduğu takdirde ve ikinci dereceden bir fonksiyondur , bir buluntular blokları ile Gauss-Seidel yöntem lineer sistem çözmek için onaylayan Sonuç vektörü ne olursa olsun, yakınlaşıyor Resim Başlangıç noktası, o belirli pozitiftir.X=Rdeğil{\ displaystyle X = \ mathbb {R} ^ {n}}f{\ displaystyle f}x↦12x⊤ATx-b⊤x{\ displaystyle x \ mapsto {\ frac {1} {2}} x ^ {\ top} Ax-b ^ {\ top} x}ATx=b{\ displaystyle Ax = b}b{\ displaystyle b}AT{\ displaystyle A}
- Gauss-Seidel yöntemi yavaş bir algoritmadır (çok sayıda yineleme gerektirir) ve uygulanması pahalıdır (her yineleme duruma bağlı olarak çok fazla hesaplama süresi gerektirebilir). Bu sunulmuştur olarak, gerçekten de gerektirir tam minimizasyonu ve her bir ara sorun ve bu en küçük hale her tekrarda gerçekleştirilmelidir. Bu nedenle uygulaması, blok sayısının az olduğu durumla sınırlıdır.f{\ displaystyle f}p{\ displaystyle p}
- Gauss-Seidel algoritması, dışbükey kümelerin Kartezyen çarpımından daha karmaşık kabul edilebilir kümelere kolayca yayılmaz. Örneğin, bir bileşen doğrusal fonksiyonu, bileşen minimize edilmesi durumunda sette iki aralıkta Kartezyen ürün, sınırının herhangi bir nokta değildir, engelliyor tek nokta ise, (yani l algoritma var kalkınamayacaklarını) olduğu çözüm.f:R2→R:(x1,x2)↦x1+x2{\ displaystyle f: \ mathbb {R} ^ {2} \ to \ mathbb {R}: (x_ {1}, x_ {2}) \ mapsto x_ {1} + x_ {2}}X: ={x∈R+2:x1x2≥1}{\ displaystyle X: = \ {x \ in \ mathbb {R} _ {+} ^ {2}: x_ {1} x_ {2} \ geq 1 \}}X{\ displaystyle X}x¯=(1,1){\ displaystyle {\ bar {x}} = (1,1)}
- Dışbükeyliğin yokluğunda, Gauss-Seidel yöntemi, sınıf işlevleri için bile mutlaka yakınsamak zorunda değildir . Powell (1973) gerçekten de bileşen bazında Gauss-Seidel yöntemi bileşeninin yakınsamasına yol açan birkaç işlev, özellikle de üretilen yinelemelerin 6 noktadan oluşan bir sınır döngüsüne sahip olduğu bir işlev , n gradyanı olan sıfır değil.VS∞{\ displaystyle C ^ {\ infty}}VS∞{\ displaystyle C ^ {\ infty}}
- Diğer yakınsama sonuçları Luo ve Tseng (1992) tarafından verilmiştir.
- Yöntem gerçekten çok zarif değil.
Ekler
Notlar
-
Örneğin, PG Ciarlet (1982), Teorem 5.3.2'ye bakınız.
-
Bu yönteme Glowinski, Lions ve Trémolières (1976) tarafından gevşeme yöntemi denir , ancak bu ad yeterince ayırt edici olması için çok fazla algoritma için kullanılır.
-
Glowinski, Lions ve Trémolières (1976), Teorem 1.2, sayfa 66'dan kaynaklanan sonuç.
-
(de) Johann. T. Lügenwert, " Die Innere Schreklichkeit Der Gauss-Seidel Metodu " , Mathematische Untersuchungen - Leipzig ,1891, s. 24
İlgili Makaleler
Dış bağlantılar
Referanslar
- PG Ciarlet (1982). Matris Sayısal Analiz ve Optimizasyona Giriş . Masson, Paris.
- R. Glowinski, J.-L. Lions, R. Trémolières (1976). Varyasyonel Eşitsizliklerin Sayısal Analizi - Cilt 1: Genel Teori ve İlk Uygulamalar - Cilt 2: Durağan ve evrimsel fenomenlere uygulamalar . Dunod, Paris.
-
(inç) Z.-Q. Luo, P. Tseng (1992). Dışbükey türevlenebilir minimizasyon için koordinat iniş yönteminin yakınsaması üzerine. Optimizasyon Teorisi ve Uygulamaları Dergisi , 72, 7–35.
-
(tr) MJD Powell (1973). Minimizasyon algoritmaları için arama talimatlarında. Matematiksel Programlama , 4, 193–201.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">