Gauss-seidel-methode Verklaring, toepassingen, voorbeelden

Hij Gauss-seidel-methode Het is een iteratieve procedure om bij benadering oplossingen te vinden voor een systeem van lineaire algebraïsche vergelijkingen met willekeurig gekozen precisie. De methode is van toepassing op vierkante matrices met niet -nul -elementen in zijn diagonalen en convergentie is gegarandeerd als de matrix diagonaal dominant is.

Het is gemaakt door Carl Friedrich Gauss (1777-1855), die in 1823 een privé-demonstratie aan een van zijn studenten maakte. Vervolgens werd het formeel gepubliceerd door Philipp Ludwig von Seidel (1821-1896) in 1874, vandaar de naam van beide wiskundigen.

Figuur 1. De methode van Gauss-Seidel komt snel samen om een ​​vergelijkingssysteem te verkrijgen. Bron: f. Zapata.

Voor een volledig begrip van de methode is het noodzakelijk om te weten dat een matrix diagonaal dominant is wanneer de absolute waarde van het diagonale element van elke rij groter is dan of gelijk is aan de som van de absolute waarden van de andere elementen van diezelfde rij.

Wiskundig wordt het als volgt uitgedrukt:

[TOC]

Verklaring door een eenvoudig geval

Om te illustreren wat de Gauss-Seidel-methode een eenvoudig geval zal nemen, waarin u de waarden van X en Y kunt vinden in het hieronder getoonde 2 × 2 lineaire vergelijkingssysteem:

5x + 2y = 1

X - 4y = 0

Stappen om te volgen

1- Allereerst moet u bepalen of de convergentie veilig is. Er wordt onmiddellijk opgemerkt dat het in feite een diagonaal dominant systeem is, omdat in de eerste rij de eerste coëfficiënt een grotere absolute waarde heeft dan de andere van de voorste rij:

| 5 |> | 2 |

Evenzo is de tweede coëfficiënt van de tweede rij ook diagonaal dominant:

| -4 |> | 1 |

2- De variabelen x en y zijn duidelijk: 

X = (1 - 2y)/5

Y = x/4

3- Een initiële willekeurige waarde wordt geplaatst, "zaad" genoemd: xo = 1, Me = 2.

4

Het kan u van dienst zijn: schatting per intervallen

X1 = (1 - 2 me)/5 = (1 - 2 × 2)/5 = -3/5 

Y1 = x1 / 4 = (-3/5) / 4 = -3/20 

5- Ga op een vergelijkbare manier verder om de tweede benadering van de oplossing van het vergelijkingssysteem te verkrijgen:

X2 = (1 - 2 y1)/5 = (1 - 2x (-3/20))/5 = 13/50 

Y2 = x2/4 = (13/50)/4 = 13/200

6- Derde iteratie:

X3 = (1 - 2 y2)/5 = (1 - 2 (13/200))/5 = 87/500

Y3 = x3/4 = (87/500)/4 = 87/2000

7- Vierde iteratie, als de laatste iteratie van dit illustratieve geval:

X4 = (1 - 2 y3)/5 = (1 - 2 (87/2000)))/5 = 913/5000

Y4 = x4/4 = (913/5000)/4 = 913/20000

Deze waarden vallen vrij goed samen met de oplossing gevonden via andere resolutiemethoden. De lezer kan het snel controleren met behulp van een online wiskundig programma.

Methode -analyse

Zoals te zien is, moeten in de Gauss-Seidel-methode de geschatte waarden verkregen voor de vorige variabele in dezelfde stap worden vervangen in de volgende variabele. Dit onderscheidt het van andere iteratieve methoden zoals Jacobi, waarin elke stap de benaderingen van de vorige fase vereist. 

De methode van Gauss-seidel is geen parallelle procedure, terwijl Gauss-Jordan is. Het is ook de reden dat de methode Gauss-seidel een snellere stappen zonder convergentie heeft-dan de methode van Jordanië.

Wat betreft de diagonaal dominante matrixconditie, dit is niet altijd tevreden. In de meeste gevallen is het echter voldoende om de gelederen van het oorspronkelijke systeem uit te wisselen om aan de voorwaarde te voldoen. Bovendien convergeert de methode bijna altijd, zelfs wanneer de diagonale dominantieconditie niet wordt voldaan.

Het vorige resultaat, verkregen door vier iteraties van de Gauss-seidel-methode, kan op een decimale manier worden geschreven:

Kan u van dienst zijn: hoeveel symmetrie -assen heeft een cirkel?

X4 = 0.1826

Y4 = 0.04565

De exacte oplossing voor het verhoogde systeem van vergelijkingen is:

X = 2/11 = 0.1818

Y = 1/22 = 0.04545.

Dus alleen met 4 iteraties wordt een resultaat verkregen met duizendste precisie (0,001).

Figuur 1 illustreert hoe opeenvolgende iteraties snel samenkomen naar de exacte oplossing.

Toepassingen

Gauss-seidel-methode is niet alleen beperkt tot 2 × 2 lineaire vergelijkingen System. De bovenstaande procedure kan worden gegeneraliseerd om een ​​lineair systeem van op te lossen N vergelijkingen met N Onbekends, dat matrix zo wordt weergegeven:

NAAR X = B

Waar NAAR Het is een matrix n x n, terwijl X Het zijn de vector n componenten van de te berekenen variabelen; En B Het is een vector die de waarden van onafhankelijke termen bevat.

Om de volgorde van iteraties te generaliseren die in het illustratieve geval worden toegepast op een N x N -systeem, dat de variabele wil berekenen Xi, De volgende formule is van toepassing:

In deze vergelijking:

- k Het is de index voor de waarde verkregen in de iteratie k.

-K+1 Geeft de nieuwe waarde in het volgende aan.

Het uiteindelijke aantal iteraties wordt bepaald wanneer de waarde verkregen in de iteratie K+1 verschilt van de verkregen onmiddellijk vóór, in een hoeveelheid ε die precies de gewenste precisie is.

Voorbeelden van de Gauss-Seidel-methode

- voorbeeld 1

Schrijf een algemeen algoritme waarmee u de geschatte oplossingsvector kunt berekenen X van een lineair systeem van NXN -vergelijkingen, gezien de coëfficiëntmatrix NAAR, De vector van onafhankelijke voorwaarden B, Het aantal iteraties (iter) en de aanvankelijke of "zaad" van de vector X.

Oplossing

Het algoritme bestaat uit twee "voor" cycli, één voor het aantal iteraties en de andere voor het aantal variabelen. Het zou als volgt zijn:

Voor k ∊ [1 ... iter]

Want ik ∊ [1 ... n]

X [i]: = (1/a [i, i])*(b [i] - ∑_{J = 1}^N(A [i, j]*x [j]) + a [i, i]*x [i])

Kan u van dienst zijn: decimale notatie

- Voorbeeld 2

Controleer de werking van het vorige algoritme door zich aan te melden op wiskundige software Smath Studio Gratis en gratis, beschikbaar voor Windows en Android. Neem als voorbeeld het geval van de 2 × 2-matrix die ons diende om de Gauss-Sidel-methode te illustreren.

Oplossing

Figuur 2. Systeem van vergelijkingen van voorbeeld 2 x 2, met behulp van software Smath Studio. Bron: f. Zapata.

- Voorbeeld 3

Pas het Gauss-Seidel-algoritme toe voor het volgende 3 × 3-vergelijkingssysteem, dat eerder zo is besteld dat de diagonale coëfficiënten dominant zijn (dat wil zeggen van grotere absolute waarde dan de absolute waarden van de coëfficiënten van de coëfficiënten van dezelfde rij):

9 x1 + 2 x2 - x3 = -2

7 x1 + 8 x2 + 5 x3 = 3

3 x1 + 4 x2 - 10 x3 = 6

Gebruik de nulvector als zaad en beschouw vijf iteraties. Reageer op het resultaat.

Oplossing

figuur 3. Oplossing van het systeem van vergelijkingen van het opgeloste voorbeeld 3, met behulp van Smath Studio. Bron: f. Zapata.

Voor hetzelfde systeem met 10 iteraties in plaats van 5 worden de volgende resultaten verkregen: x1 = -0.485; X2 = 1.0123; X3 = -0.3406

Dit geeft aan dat het voldoende is met vijf iteraties om drie precisie -decimalen te verkrijgen en dat de methode snel overbrengt naar de oplossing.

- Voorbeeld 4

Zoek door middel van het Gauss-Seidel-algoritme de oplossing van het 4 × 4-vergelijkingssysteem dat hieronder voorkomt:

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

Om de methode te starten, gebruik je van dit zaadje:

x1 = 0, x2 = 0, x3 = 0 en x4 = 0

Overweeg 10 iteraties en schatting de fout van het resultaat, vergeleken met het iteratienummer 11.

Oplossing

Figuur 4. Oplossing van het systeem van vergelijkingen van het opgeloste voorbeeld 4, met behulp van Smath Studio. Bron: f. Zapata.

Bij vergelijking met de volgende iteratie (nummer 11) is het resultaat identiek. De grootste verschillen tussen de twee iteraties zijn in de orde van 2 × 10^-8, Wat betekent dat de getoonde oplossing een nauwkeurigheid heeft van ten minste zeven decimalen.

Referenties

1. Iteratieve oplossingsmethoden. Gauss-Seidel. Hersteld van: cimat.mx
2. Numerieke methodes. Gauss-Seidel. Hersteld van: test.Cua.UAM.mx
3. Numeriek: Gauss-Sidel-methode. Hersteld van: leer in linea.Jij.Edu.co
4. Wikipedia. Gauss-seidel-methode. Opgehaald uit: in. Wikipedia.com
5. Wikipedia. Gauss-seidel-methode. Hersteld van: is.Wikipedia.com