04.1 Metodo di Jacobi

Metodo di Jacobi

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 X + (L + U) X & = B \\ D X & = - (L + U) X + B \\ D^{- 1} D X & = - D^{- 1} [(L + U) X + B] \\ X & = - D^{- 1} [(L + U) X + B] \\ X & = \underset{\overset{△}{=} C_{J}}{\underset{⏟}{- D^{- 1} (L + U)}} X + \underset{\overset{△}{=} Q_{J}}{\underset{⏟}{D^{- 1} B}} \end{aligned}

Il metodo di Jacobi consiste quindi nel risolvere

X = C_{J} X + Q_{J}

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

C_{J} = [\begin{matrix} 0 & - \frac{a_{12}}{a_{11}} & \dots & - \frac{a_{1 n}}{a_{11}} \\ - \frac{a_{21}}{a_{22}} & 0 & \dots & - \frac{a_{2 n}}{a_{22}} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ - \frac{a_{n 1}}{a_{n n}} & - \frac{a_{n 2}}{a_{n n}} & \dots & 0 \end{matrix}] Q_{J} = [\begin{matrix} \frac{b_{1}}{a_{11}} & 0 & \dots & 0 \\ 0 & \frac{b_{2}}{a_{22}} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & \frac{b_{n}}{a_{n n}} \end{matrix}]

ipotesi

Elencare le ipotesi del metodo
❗❗❗❗❗❗❗❗❗❗❗
❗❗❗COMPLETARE❗❗❗
❗❗❗❗❗❗❗❗❗❗❗

Lo schema iterativo è costituito da

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

Scrivendolo in forma esplicita diventa:

[\begin{matrix} x_{1}^{(k + 1)} \\ x_{2}^{(k + 1)} \\ ⋮ \\ x_{n}^{(k + 1)} \end{matrix}] = [\begin{matrix} 0 & - \frac{a_{12}}{a_{11}} & \dots & - \frac{a_{1 n}}{a_{11}} \\ - \frac{a_{21}}{a_{22}} & 0 & \dots & - \frac{a_{2 n}}{a_{22}} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ - \frac{a_{n 1}}{a_{n n}} & - \frac{a_{n 2}}{a_{n n}} & \dots & 0 \end{matrix}] [\begin{matrix} x_{1}^{(k)} \\ x_{2}^{(k)} \\ ⋮ \\ x_{n}^{(k)} \end{matrix}] + [\begin{matrix} \frac{b_{1}}{a_{11}} & 0 & \dots & 0 \\ 0 & \frac{b_{2}}{a_{22}} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & \frac{b_{n}}{a_{n n}} \end{matrix}]

Questo diventa

\begin{aligned} x_{1}^{(k + 1)} & = - \frac{a_{12}}{a_{11}} x_{2}^{(k)} - - \frac{a_{13}}{a_{11}} x_{3}^{(k)} - \dots - \frac{a_{1 n}}{a_{11}} x_{n}^{(k)} - \frac{b_{1}}{a_{11}} = \frac{1}{a_{11}} (\sum_{j = 1, j \neq 1}^{n} (a_{1 j} x_{j}^{(k)}) + b_{1}) \end{aligned}

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}^{n} (a_{i j} x_{j}^{(k)}) + b_{i}) 1 \leq i \leq n

Valutazione degli errori

❗❗❗❗❗❗❗❗❗❗❗
❗❗❗COMPLETARE❗❗❗
❗❗❗❗❗❗❗❗❗❗❗

❗❗❗❗❗❗❗❗❗❗❗
❗❗❗COMPLETARE❗❗❗
❗❗❗❗❗❗❗❗❗❗❗

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

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

(cs) - matrici diagonalmente dominanti

allora

il metodo di Jacobi Converge.

teorema

Il metodo converge se $A$ è una 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