04.2 Metodo di Gauss-Seidel

Metodo di Gauss-Seidel

Siano

A \in R^{n \times n} B \in R^{n} C \in R^{n \times n} Q \in R^{n}

Data un sistema

A X = B

riscrivibile nella forma

X = C X + Q

Riscrivo $A$ come somma di tre matrici:

A = D + L + U

dove

D = [\begin{matrix} a_{11} & 0 & \dots & 0 \\ 0 & a_{22} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & 0 \\ 0 & 0 & \dots & a_{n n} \end{matrix}] L = [\begin{matrix} 0 & 0 & \dots & 0 \\ a_{21} & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & 0 \end{matrix}] U = [\begin{matrix} 0 & a_{12} & \dots & a_{1 n} \\ 0 & 0 & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 0 \end{matrix}]

Sostituendo questa scomposizione nel problema, troviamo

\begin{aligned} A X = (D + L + U) X & = B \\ (D + L) X + U X & = B \\ (D + L) X & = B - U X \\ X & = \underset{\overset{△}{=} C_{G S}}{\underset{⏟}{- (D + L)^{- 1} U}} X + \underset{\overset{△}{=} Q_{G S}}{\underset{⏟}{(D + L)^{- 1} B}} \end{aligned}

Il metodo di Gauss-Seidel consiste quindi nel risolvere

X = C_{G S} X + Q_{G S}

Scritta in forma estesa, $C_{G S}$ e $Q_{G S}$ diventano:

ipotesi

Elencare le ipotesi del metodo

Lo schema iterativo è costituito da

X^{(k + 1)} = C_{G S} X^{(k)} + Q_{G S}

Facendo anche per le altre righe, possiamo riassumere e compattare con la scrittura:

x_{i}^{(k + 1)} = \frac{1}{a_{i j}} (\sum_{j = 1, j \neq i}^{i - 1} (a_{i j} x_{j}^{(k + 1)}) + \sum_{j = i + 1, j \neq i}^{n} (a_{i j} x_{j}^{(k)}) + b_{i}) 1 \leq i \leq n; k \geq 0

Valutazione degli errori

La convergenza è garantita secondo le condizioni della convergenza per sistemi lineari condizioni della convergenza per sistemi lineari:

\begin{aligned} CS: & | | C_{G S} | | & < 1 \\ CN: & lim_{k \to \infty} X^{(k)} & = \overset{―}{X} \\ CNS: & ρ (C_{G S}) & < 1 \end{aligned}

matrici diagonalmente dominanti

allora

il metodo di Gasuss-Seidel converge.

teorema

Il metodo converge se $A$ è una [[02. Richiami di algebra lineare#Matrice definita positiva]]

Fornire, se possibile, un modo di stimare le iterazioni necessarie

Fornire dei criteri di arresto, se pertinente

Copiare il codice di implementazione in Matlab