De Gauss-Seidel-metoden är en iterativ procedur för att hitta ungefärliga lösningar på ett system av linjära algebraiska ekvationer med godtyckligt vald precision. Metoden tillämpas på fyrkantiga matriser med element som inte är noll i diagonalerna och konvergens garanteras om matrisen är diagonalt dominerande.
Den skapades av Carl Friedrich Gauss (1777-1855), som gav en privat demonstration till en av sina studenter 1823. Den publicerades senare formellt av Philipp Ludwig von Seidel (1821-1896) 1874, därav namnet på båda matematikerna..
För en fullständig förståelse av metoden är det nödvändigt att veta att en matris är diagonalt dominerande när det absoluta värdet av det diagonala elementet i varje rad är större än eller lika med summan av de absoluta värdena för de andra elementen av samma rad..
Matematiskt uttrycks det så här:
Artikelindex
För att illustrera vad Gauss-Seidel-metoden består av, tar vi ett enkelt fall där värdena X och Y kan hittas i 2 × 2-systemet med linjära ekvationer som visas nedan:
5X + 2Y = 1
X - 4Y = 0
1- För det första är det nödvändigt att avgöra om konvergensen är säker. Det observeras omedelbart att det i själva verket är ett diagonalt dominerande system, eftersom i den första raden har den första koefficienten ett högre absolutvärde än de andra i den första raden:
| 5 |> | 2 |
På samma sätt är den andra koefficienten i andra raden också diagonalt dominerande:
| -4 |> | 1 |
två- Variablerna X och Y är lösta:
X = (1 - 2Y) / 5
Y = X / 4
3- Ett godtyckligt initialvärde placeras, kallat "seed": Xo = 1, I = 2.
4-Iterationen börjar: för att erhålla den första approximationen X1, Y1 ersätts fröet i den första ekvationen i steg 2 och resultatet i den andra ekvationen i steg 2:
X1 = (1-2 I) / 5 = (1-2 × 2) / 5 = -3/5
Y1 = X1 / 4 = (-3/5) / 4 = -3/20
5- Vi fortsätter på ett liknande sätt för att få den andra approximationen av lösningen av ekvationssystemet:
X2 = (1-2 Yl) / 5 = (1 - 2x (-3/20)) / 5 = 13/50
Y2 = X2 / 4 = (13/50) / 4 = 13/200
6- Tredje iteration:
X3 = (1-2 Y2) / 5 = (1-2 (13/200)) / 5 = 87/500
Y3 = X3 / 4 = (87/500) / 4 = 87/2000
7- Fjärde iteration, som den slutliga iterationen av detta illustrativa fall:
X4 = (1-2 Y3) / 5 = (1-2 (87/2000)) / 5 = 913/5000
Y4 = X4 / 4 = (913/5000) / 4 = 913/20000
Dessa värden överensstämmer ganska bra med lösningen som hittats av andra upplösningsmetoder. Läsaren kan snabbt kontrollera det med hjälp av ett matematiskt program online.
Som framgår måste Gauss-Seidel-metoden de ungefärliga värdena som erhållits för den föregående variabeln i samma steg ersättas med följande variabel. Detta skiljer det från andra iterativa metoder som Jacobis, där varje steg kräver approximationer av föregående steg..
Gauss-Seidel-metoden är inte ett parallellt förfarande, medan Gauss-Jordan-metoden är. Det är också anledningen till att Gauss-Seidel-metoden har en snabbare konvergens - i färre steg - än Jordan-metoden..
När det gäller det diagonalt dominerande matrisvillkoret är detta inte alltid uppfyllt. I de flesta fall är det dock tillräckligt att byta rader från det ursprungliga systemet för att villkoret ska vara uppfyllt. Dessutom konvergerar metoden nästan alltid, även om det diagonala dominansvillkoret inte är uppfyllt..
Det tidigare resultatet, erhållet genom fyra iterationer av Gauss-Seidel-metoden, kan skrivas i decimalform:
X4 = 0,1826
Y4 = 0,04565
Den exakta lösningen på det föreslagna ekvationssystemet är:
X = 2/11 = 0,1818
Y = 1/22 = 0,04545.
Så med bara fyra iterationer får du ett resultat med en tusendel av precision (0,001).
Figur 1 illustrerar hur successiva iterationer snabbt konvergerar till den exakta lösningen.
Gauss-Seidel-metoden är inte bara begränsad till ett 2 × 2-system av linjära ekvationer. Ovanstående procedur kan generaliseras för att lösa ett linjärt system av n ekvationer med n okända, som representeras i en matris så här:
TILL X = b
Var TILL är en matris n x n, Medan X är vektorn n-komponenterna i de n variabler som ska beräknas; Y b är en vektor som innehåller värdena för de oberoende termerna.
För att generalisera sekvensen av iterationer som tillämpas i det illustrativa fallet på ett n x n-system, från vilket variabeln ska beräknas Xi, följande formel kommer att tillämpas:
I denna ekvation:
- k är index för det värde som erhålls i iterationen k.
-k + 1 anger det nya värdet i det följande.
Det slutliga antalet iterationer bestäms när värdet erhålls i iterationen k + 1 skiljer sig från den som erhölls omedelbart tidigare, med en mängd ε som är exakt den önskade precisionen.
Skriv en allmän algoritm för att beräkna vektorn för ungefärliga lösningar X av ett linjärt ekvationssystem nxn, med tanke på koefficientmatrisen TILL, vektorn av oberoende termer b, antalet iterationer (iter) och det ursprungliga eller "frö" -värdet för vektorn X.
Algoritmen består av två "Till" -cykler, en för antalet iterationer och den andra för antalet variabler. Det skulle vara som följer:
För k ∊ [1… iter]
För i ∊ [1… n]
X [i]: = (1 / A [i, i]) * (b [i] - ∑j = 1n(A [i, j] * X [j]) + A [i, i] * X [i])
Kontrollera funktionen hos den tidigare algoritmen genom att använda den i matematisk programvara SMath Studio gratis att använda, tillgänglig för Windows och Android. Ta exempel på fallet med 2 × 2-matrisen som hjälpte oss att illustrera Gauss-Seidel-metoden.
Använd Gauss-Seidel-algoritmen för följande 3 × 3-ekvationssystem, som tidigare har ordnats på ett sådant sätt att koefficienterna för diagonalen är dominerande (det vill säga större absolutvärde än koefficienternas absoluta värden av samma rad):
9 X1 + 2 X2 - X3 = -2
7 X1 + 8 X2 + 5 X3 = 3
3 X1 + 4 X2 - 10 X3 = 6
Använd nollvektorn som ett frö och överväga fem iterationer. Kommentera resultatet.
För samma system med 10 iterationer istället för 5 erhålls följande resultat: X1 = -0,485; X2 = 1,0123; X3 = -0,3406
Detta berättar att fem iterationer räcker för att få tre decimaler av precision och att metoden snabbt konvergerar till lösningen.
Med hjälp av Gauss-Seidel-algoritmen ovan, hitta lösningen på 4 × 4 ekvationssystemet nedan:
10 x1 - x2 + 2 x3 + 0 x4 = 6
-1 x1 + 11 x2 - 1 x3 + 3 x 4 = 25
2 x1 - 1 x2 + 10 x3 - 1 x4 = -11
0 x1 + 3 x2 - 1 x3 + 8 x4 = 15
För att starta metoden, använd detta frö:
x1 = 0, x2 = 0, x3 = 0 och x4 = 0
Överväg tio iterationer och uppskatta felet i resultatet, jämfört med iteration nummer 11.
När man jämför med nästa iteration (nummer 11) är resultatet identiskt. De största skillnaderna mellan de två iterationerna är i storleksordningen 2 × 10-8, vilket innebär att den visade lösningen har en precision på minst sju decimaler.
Ingen har kommenterat den här artikeln än.