Metodo Gauss-Seidel Spiegazione, applicazioni, esempi

Lui Metodo Gauss-Seidel È una procedura iterativa trovare soluzioni approssimative a un sistema di equazioni algebriche lineari con precisione arbitrariamente scelta. Il metodo si applica alle matrici quadrate con elementi non null nelle sue diagonali e la convergenza è garantito se la matrice è diagonale dominante.

Fu creato da Carl Friedrich Gauss (1777-1855), che fece una dimostrazione privata a uno dei suoi studenti nel 1823. Successivamente fu pubblicato formalmente da Philipp Ludwig von Seidel (1821-1896) nel 1874, da cui il nome di entrambi i matematici.

Figura 1. Il metodo di Gauss-Seidel converge rapidamente per ottenere un sistema di equazioni. Fonte: f. Zapata.

Per una piena comprensione del metodo, è necessario sapere che una matrice è diagonale dominante quando il valore assoluto dell'elemento diagonale di ciascuna riga è maggiore o uguale alla somma dei valori assoluti degli altri elementi della stessa fila.

Matematicamente è espresso come segue:

[TOC]

Spiegazione attraverso un semplice caso

Per illustrare ciò che il metodo Gauss-Seidel richiederà un semplice caso, in cui è possibile trovare i valori di X e Y nel sistema di equazioni lineari 2 × 2 mostrate di seguito:

5x + 2y = 1

X - 4y = 0

Passi da seguire

1- Prima di tutto devi determinare se la convergenza è sicura. Si osserva immediatamente che, in effetti, è un sistema diagonale dominante, poiché nella prima riga il primo coefficiente ha un valore assoluto maggiore rispetto agli altri della prima fila:

| 5 |> | 2 |

Allo stesso modo, il secondo coefficiente della seconda riga è anche diagonale dominante:

| -4 |> | 1 |

2- Le variabili xey sono chiare: 

X = (1 - 2y)/5

Y = x/4

3- Viene posizionato un valore arbitrario iniziale, chiamato "seme": xo = 1, me = 2.

4

Può servirti: stima per intervalli

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

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

5- Procedere in modo simile per ottenere la seconda approssimazione della soluzione del sistema di equazioni:

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

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

6- Terza iterazione:

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

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

7- Quarta iterazione, come iterazione finale di questo caso illustrativo:

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

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

Questi valori coincidono abbastanza bene con la soluzione trovata attraverso altri metodi di risoluzione. Il lettore può verificarlo rapidamente con l'aiuto di un programma matematico online.

Analisi del metodo

Come si può vedere, nel metodo Gauss-Seidel, i valori approssimativi ottenuti per la variabile precedente nello stesso passaggio devono essere sostituiti nella seguente variabile. Questo lo differenzia da altri metodi iterativi come Jacobi, in cui ogni fase richiede gli approcci alla fase precedente. 

Il metodo di Gauss-Seidel non è una procedura parallela, mentre Gauss-Jordan è. È anche il motivo per cui il metodo Gauss-Seidel ha un passo più rapido senza convergenza, con il metodo di Jordan.

Per quanto riguarda la condizione di matrice diagonale dominante, questo non è sempre soddisfatto. Tuttavia, nella maggior parte dei casi è sufficiente scambiare i ranghi del sistema originale per soddisfare la condizione. Inoltre, il metodo converge quasi sempre, anche quando la condizione di dominanza diagonale non viene soddisfatta.

Il risultato precedente, ottenuto da quattro iterazioni del metodo Gauss-Seidel, può essere scritto in modo decimale:

Può servirti: quanti assi di simmetria hanno un cerchio?

X4 = 0,1826

Y4 = 0,04565

La soluzione esatta al sistema di equazioni sollevate è:

X = 2/11 = 0,1818

Y = 1/22 = 0,04545.

Quindi solo con 4 iterazioni un risultato si ottiene con un millesimo di precisione (0,001).

La Figura 1 illustra come le iterazioni successive convergono rapidamente alla soluzione esatta.

Applicazioni

Il metodo Gauss-Seidel non è limitato solo al sistema di equazioni lineari 2 × 2. La procedura di cui sopra può essere generalizzata per risolvere un sistema lineare di N equazioni con N incognite, che è rappresentata da matrice come questo:

A X = B

Dove A È una matrice n x n, Mentre X Sono i componenti vector N delle variabili da calcolare; E B È un vettore che contiene i valori di termini indipendenti.

Per generalizzare la sequenza di iterazioni applicate nel caso illustrativo a un sistema N X N, che desidera calcolare la variabile Xi, Si applicherà la seguente formula:

In questa equazione:

- K È l'indice per il valore ottenuto nell'iterazione K.

-K+1 Indica il nuovo valore nel seguente.

Il numero finale di iterazioni viene determinato quando il valore ottenuto nell'iterazione K+1 differisce da quello ottenuto immediatamente prima, in un importo ε che è proprio la precisione desiderata.

Esempi del metodo Gauss-Seidel

- Esempio 1

Scrivi un algoritmo generale che consente di calcolare il vettore di soluzione approssimativo X di un sistema lineare di equazioni NXN, data la matrice del coefficiente A, Il vettore di termini indipendenti B, Il numero di iterazioni (iter) e il iniziale o "seme" del vettore X.

Soluzione

L'algoritmo è costituito da due cicli "per", uno per il numero di iterazioni e l'altra per il numero di variabili. Sarebbe il seguente:

Per k ∊ [1 ... ITER]

Per i ∊ [1… n]

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

Può servirti: notazione decimale

- Esempio 2

Controlla il funzionamento dell'algoritmo precedente applicando al software matematico Smath Studio gratuito e gratuito, disponibile per Windows e Android. Prendi come esempio il caso della matrice 2 × 2 che ci ha servito per illustrare il metodo Gauss-Seidel.

Soluzione

figura 2. Sistema di equazioni dell'esempio 2 x 2, utilizzando il software Smath Studio. Fonte: f. Zapata.

- Esempio 3

Applicare l'algoritmo Gauss-Seidel per il seguente sistema di equazioni 3 × 3, che è stato precedentemente ordinato in modo tale che i coefficienti diagonali siano dominanti (cioè di valore assoluto maggiore rispetto ai valori assoluti dei coefficienti dei coefficienti della stessa riga):

9 x1 + 2 x2 - x3 = -2

7 x1 + 8 x2 + 5 x3 = 3

3 x1 + 4 x2 - 10 x3 = 6

Usa il vettore nullo come seme e considera cinque iterazioni. Commenta il risultato.

Soluzione

Figura 3. Soluzione del sistema di equazioni dell'esempio risolto 3, usando Smath Studio. Fonte: f. Zapata.

Per lo stesso sistema con 10 iterazioni invece di 5 si ottengono i seguenti risultati: x1 = -0.485; X2 = 1.0123; X3 = -0.3406

Ciò indica che è sufficiente con cinque iterazioni per ottenere tre decimali di precisione e che il metodo trasmette rapidamente alla soluzione.

- Esempio 4

Per mezzo dell'algoritmo Gauss-Seidel indicato, trova la soluzione del sistema di equazioni 4 × 4 che si verifica di seguito:

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

Per iniziare il metodo, utilizzare questo seme:

x1 = 0, x2 = 0, x3 = 0 e x4 = 0

Considera 10 iterazioni e stima l'errore del risultato, confrontando con l'iterazione numero 11.

Soluzione

Figura 4. Soluzione del sistema di equazioni dell'esempio risolto 4, usando Smath Studio. Fonte: f. Zapata.

Quando si confronta con la seguente iterazione (numero 11), il risultato è identico. Le maggiori differenze tra le due iterazioni sono dell'ordine di 2 × 10^-8, Ciò significa che la soluzione mostrata ha una precisione di almeno sette decimali.

Riferimenti

1. Metodi di soluzione iterativa. Gauss-Seidel. Recuperato da: cimat.MX
2. Metodi numerici. Gauss-Seidel. Recuperato da: test.CUA.Uam.MX
3. Numerico: metodo Gauss-Seidel. Recuperato da: impara in linea.Voi.Edu.co
4. Wikipedia. Metodo Gauss-Seidel. Recuperato da: in. Wikipedia.com
5. Wikipedia. Metodo Gauss-Seidel. Recuperato da: è.Wikipedia.com