De Gauss-Seidel metode er en iterativ prosedyre for å finne omtrentlige løsninger på et system med lineære algebraiske ligninger med vilkårlig valgt presisjon. Metoden brukes på firkantede matriser med ikke-null-elementer i diagonalene, og konvergens er garantert hvis matrisen er diagonalt dominerende.
Den ble opprettet av Carl Friedrich Gauss (1777-1855), som ga en privat demonstrasjon til en av studentene sine i 1823. Den ble senere formelt utgitt av Philipp Ludwig von Seidel (1821-1896) i 1874, derav navnet på begge matematikerne..
For en fullstendig forståelse av metoden er det nødvendig å vite at en matrise er diagonalt dominerende når den absolutte verdien av det diagonale elementet i hver rad er større enn eller lik summen av de absolutte verdiene til de andre elementene av den samme raden..
Matematisk uttrykkes det slik:
Artikkelindeks
For å illustrere hva Gauss-Seidel-metoden består av, tar vi et enkelt tilfelle der verdiene til X og Y kan bli funnet i 2 × 2-systemet med lineære ligninger vist nedenfor:
5X + 2Y = 1
X - 4Y = 0
1- For det første er det nødvendig å avgjøre om konvergensen er trygg. Det observeres umiddelbart at det faktisk er et diagonalt dominerende system, siden i første rad har den første koeffisienten høyere absoluttverdi enn de andre i første rad:
| 5 |> | 2 |
På samme måte er den andre koeffisienten i andre rad også diagonalt dominerende:
| -4 |> | 1 |
to- Variablene X og Y er løst:
X = (1 - 2Y) / 5
Y = X / 4
3- En vilkårlig startverdi blir plassert, kalt "seed": Xo = 1, I = 2.
4-Iterasjonen begynner: for å oppnå den første tilnærmingen X1, Y1, blir frøet erstattet i den første ligningen i trinn 2 og resultatet i den andre ligningen i trinn 2:
X1 = (1-2 I) / 5 = (1-2 × 2) / 5 = -3/5
Y1 = X1 / 4 = (-3/5) / 4 = -3/20
5- Vi fortsetter på en lignende måte for å oppnå den andre tilnærmingen av løsningen av ligningssystemet:
X2 = (1-2 Y1) / 5 = (1 - 2x (-3/20)) / 5 = 13/50
Y2 = X2 / 4 = (13/50) / 4 = 13/200
6- Tredje iterasjon:
X3 = (1-2 Y2) / 5 = (1-2 (13/200)) / 5 = 87/500
Y3 = X3 / 4 = (87/500) / 4 = 87/2000
7- Fjerde iterasjon, som den siste iterasjonen av denne illustrative saken:
X4 = (1-2 Y3) / 5 = (1-2 (87/2000)) / 5 = 913/5000
Y4 = X4 / 4 = (913/5000) / 4 = 913/20000
Disse verdiene stemmer ganske godt overens med løsningen som finnes av andre oppløsningsmetoder. Leseren kan raskt sjekke det ved hjelp av et online matematisk program.
Som det kan sees, i Gauss-Seidel-metoden, må de omtrentlige verdiene som er oppnådd for den forrige variabelen i det samme trinnet erstattes i den følgende variabelen. Dette skiller den fra andre iterative metoder som Jacobi's, der hvert trinn krever tilnærminger fra forrige trinn..
Gauss-Seidel-metoden er ikke en parallell prosedyre, mens Gauss-Jordan-metoden er det. Det er også grunnen til at Gauss-Seidel-metoden har en raskere konvergens - i færre trinn - enn Jordan-metoden..
Når det gjelder den diagonalt dominerende matrisetilstanden, oppfylles ikke alltid dette. Imidlertid er det i de fleste tilfeller bare tilstrekkelig å bytte radene fra det opprinnelige systemet for at betingelsen skal oppfylles. Videre konvergerer metoden nesten alltid, selv når den diagonale dominansbetingelsen ikke er oppfylt..
Det forrige resultatet, oppnådd ved fire iterasjoner av Gauss-Seidel-metoden, kan skrives i desimalform:
X4 = 0,1826
Y4 = 0,04565
Den eksakte løsningen på det foreslåtte ligningssystemet er:
X = 2/11 = 0,1818
Y = 1/22 = 0,04545.
Så med bare 4 iterasjoner får du et resultat med en tusendel presisjon (0,001).
Figur 1 illustrerer hvordan påfølgende iterasjoner raskt konvergerer til den nøyaktige løsningen.
Gauss-Seidel-metoden er ikke bare begrenset til et 2 × 2-system med lineære ligninger. Ovennevnte prosedyre kan generaliseres for å løse et lineært system av n ligninger med n ukjente, som er representert i en matrise som denne:
TIL X = b
Hvor TIL er en matrise n x n, Samtidig som X er vektorn n-komponentene til n-variablene som skal beregnes; Y b er en vektor som inneholder verdiene til de uavhengige begrepene.
For å generalisere rekkefølgen av iterasjoner som i det illustrative tilfellet er brukt på et n x n-system, hvorfra variabelen skal beregnes Xi, følgende formel vil bli brukt:
I denne ligningen:
- k er indeksen for verdien oppnådd i iterasjonen k.
-k + 1 angir den nye verdien i det følgende.
Det endelige antall iterasjoner bestemmes når verdien oppnådd i iterasjonen k + 1 skiller seg fra den som ble oppnådd umiddelbart før, med en mengde ε som er nøyaktig ønsket presisjon.
Skriv en generell algoritme for å beregne vektoren til omtrentlige løsninger X av et lineært ligningssystem nxn, gitt koeffisientmatrisen TIL, vektoren av uavhengige termer b, antall iterasjoner (iter) og begynnelses- eller "frø" -verdien til vektoren X.
Algoritmen består av to "Til" -sykluser, en for antall iterasjoner og den andre for antall variabler. Det vil være som følger:
For k ∊ [1… iter]
For i ∊ [1… n]
X [i]: = (1 / A [i, i]) * (b [i] - ∑j = 1n(A [i, j] * X [j]) + A [i, i] * X [i])
Sjekk driften av den forrige algoritmen ved å bruke den i matematisk programvare SMath Studio gratis å bruke, tilgjengelig for Windows og Android. Ta som eksempel tilfellet med 2 × 2-matrisen som hjalp oss med å illustrere Gauss-Seidel-metoden.
Bruk Gauss-Seidel-algoritmen for følgende 3 × 3 ligningssystem, som tidligere er ordnet på en slik måte at koeffisientene til diagonalen er dominerende (det vil si større absoluttverdi enn koeffisientens absolutte verdier av samme rad):
9 X1 + 2 X2 - X3 = -2
7 X1 + 8 X2 + 5 X3 = 3
3 X1 + 4 X2 - 10 X3 = 6
Bruk nullvektoren som et frø og vurder fem iterasjoner. Kommenter resultatet.
For det samme systemet med 10 iterasjoner i stedet for 5, oppnås følgende resultater: X1 = -0.485; X2 = 1,0123; X3 = -0,3406
Dette forteller oss at fem iterasjoner er nok til å oppnå tre desimaler med presisjon, og at metoden raskt konvergerer til løsningen.
Bruk Gauss-Seidel-algoritmen gitt ovenfor, finn løsningen på 4 × 4 ligningssystem gitt nedenfor:
10 x1 - x2 + 2 x3 + 0 x4 = 6
-1 x1 + 11 x2 - 1 x3 + 3 x4 = 25
2 x1 - 1 x2 + 10 x3 - 1 x4 = -11
0 x1 + 3 x2 - 1 x3 + 8 x4 = 15
For å starte metoden, bruk dette frøet:
x1 = 0, x2 = 0, x3 = 0 og x4 = 0
Tenk på 10 iterasjoner og estimer feilen i resultatet, sammenlignet med iterasjon nummer 11.
Når man sammenligner med neste iterasjon (nummer 11), blir resultatet identisk. De største forskjellene mellom de to gjentakelsene er i størrelsesorden 2 × 10-8, som betyr at løsningen som vises har en presisjon på minst syv desimaler.
Ingen har kommentert denne artikkelen ennå.