3.5.1.1 Convergenza del metodo

Al passo $k$-esimo l'errore a questa iterazione ?

$$\bgroup\color{darkgreen} e^{(k)} = \tilde{x} - x^{(k)} \egroup$$

risulta chiaro quindi che

$$\bgroup\color{darkgreen} \lim_{k\to \infty}x^{(k)} = \tilde{x} \Leftrightarrow \lim_{k\to \infty}e^{(k)} = 0 \egroup$$

Infine sottraendo la (3.7) dalla (3.6), allora

$$\bgroup\color{darkgreen} D\underbrace{(\tilde{x}-x^{(k+1)})}... ...U)\underbrace{(\tilde{x}-x^{(k)})}_{e^{(k)}} + (b - b) \egroup$$

e pertanto

$$\bgroup\color{darkgreen} e^{(k+1)}=\underbrace{D^{-1}(L+U)}_{B_j}e^{(k)} \Rightarrow e^{(k)}=(B_j)^{k}e^{(0)} \egroup$$

dove $(B_j)^{k}$ ? la matrice di Jacobi alla $k$-esima iterazione.
La dimostrazione dell'implicazione precedente si fa per induzione su $k$. Perci? fissato all'inizio il valore di $e^{(0)}$ otteniamo che

$$\bgroup\color{darkgreen} \lim_{k\to \infty}e^{(k)} = 0 \Leftrightarrow (B_j)^{k} \rightarrow 0_{n \times n} \egroup$$

cio? l'errore sulle soluzioni via via approssimate tende a zero, per $k \to \infty$, se la matrice di Jacobi al passo $k$-esimo converge alla matrice quadrata nulla di dimensione $n$

Definizione 3.24   Una matrice si dice convergente se e solo se il suo raggio spettrale^3.8 ? minore di uno

Consideriamo ora $B_j = V^{-1}\Lambda V$, cio? la sua scomposizione in forma canonica di Jordan , con $\Lambda$ che ? cos? strutturata:

$$\bgroup\color{darkgreen} \Lambda = \left( \begin{array}{ccc... ...\\ &\ddots & \\ & &\lambda_n \end{array} \right) \egroup$$

mentre con $V$ si indica la matrice le cui colonne sono gli autovettori corrispondenti agli autovalori di $\Lambda$.
Quindi $B_j^k= V^{-1}\Lambda^k V$ converge a zero se e soltanto se $\Lambda^k$ converge a zero, poich? ? l'unica matrice che dipende da $k$. Si noti per? che il calcolo del raggio spettrale di una matrice ha un costo estremamente superiore alla risoluzione del sistema lineare con un metodo diretto; quindi si cercheranno maggiorazioni facilmente calcolabili e che siano minori di uno.
Una di queste possibili maggiorazioni ci viene fornita considerando la definizione di matrice a diagonale dominante. Verificare che una matrice ? di questo tipo ? un calcolo semplice, ha un costo relativamente basso e si pu? quindi sfruttare nella seguente proposizione:

Proposizione 3.25   Se $A$ ? a diagonale dominante in senso forte per righe e/o per colonne allora $\rho(B_j) < 1$

DIMOSTRAZIONE:
Nel caso in cui $A$ sia a diagonale dominante in senso forte per righe allora

$$\bgroup\color{darkgreen} \vert\vert B_j\vert\vert _{\infty} < 1 \egroup$$

e questa maggiorazione ? sufficiente perch? $\rho(B_j)$ ? sempre pi? piccolo di una qualsiasi norma di $B_j$(vedi teorema 2.11):

$$\bgroup\color{darkgreen} \rho(B_j) \leq \vert\vert B_j\vert\... ...vert\vert \quad \forall \lambda_i \in \mathcal{P}(B_j) \egroup$$

dove si ricordi che, dato $v$ autovettore corrispondente a $\lambda$

$$\bgroup\color{darkgreen} \vert\vert B_j\vert\vert = \sup_{v ... ...rac{\vert\vert B_jv\vert\vert}{\vert\vert v\vert\vert} \egroup$$

$$\bgroup\color{darkgreen} \frac{\vert\vert B_jv\vert\vert}{\v... ...rt\vert}=\vert\lambda\vert \leq \vert\vert B\vert\vert \egroup$$

Dato che $B_j = D^{-1}(L+U)$, cio?

$$\bgroup\color{darkgreen} B_j=\left( \begin{array}{ccccc} 0... ...-\frac{a_{n1}}{a_{nn}} & & & & 0 \end{array} \right) \egroup$$

quindi

$$\bgroup\color{darkgreen} \vert\vert B_j\vert\vert _{\infty} ... ..._{j=1}^{n}\left\vert\frac{a_{ij}}{a_{ii}}\right\vert<1 \egroup$$

Se invece $A$ ? a diagonale dominante in senso forte per colonne, abbiamo che ? simile^3.9 a .
Quindi

$$\bgroup\color{darkgreen} \vert\vert B_j\vert\vert _1 = \max_... ..._{i\neq j}\left\vert\frac{a_{ij}}{a_{jj}}\right\vert<1 \egroup$$

$\Box$
Analizziamo adesso i dettagli implementativi di questo metodo:

1. Come criterio d'arresto potremo fissare una tolleranza $toll>\vert e^{(k)}\vert$, ma questo non ? possibile poich? non si conoscono le soluzioni esatte. Utilizziamo pertanto una tolleranza in base al residuo
   
   $$\vert\vert r^{(k)}\vert\vert<toll$$
   
   
   dove per residuo si intende la quantit?
   
   $$r^{(k)}=A\cdot e^{(k)}=b-Ax^{(k)}$$
   
   

2. Un primo algoritmo per la risoluzione del sistema pu? essere espresso in questo pseudo-codice:
   

   	$Dx^{(k)}=(L+U)x^{(k-1)}+b$
   	$r^{(k)}=Ax^{(k)}-b$
   	se $\vert\vert r^{(k)}\vert\vert<toll$ stop
   	altrimenti $Dx^{(k+1)}=(L+U)x^{(k)}+b$

   Tuttavia questo modo di procedere non sfrutta al massimo i calcoli gi? eseguiti, ? pi? conveniente il seguente
   

   	$Dx^{(k)}=(L+U)x^{(k-1)}+b$
   	$r^{(k)}=b-Ax^{(k)}$
   	se $\vert\vert r^{(k)}\vert\vert<toll$ stop
   	altrimenti $x^{(k+1)}=x^{(k)}+D^{-1}r^{(k)}$

   Infatti:
   

   $$x^{(k+1)} = x^{(k)}+D^{-1}r^{(k)}=x^{(k)}+D^{-1}(b-Ax^{(k)})=$$

   $$= x^{(k)}+D^{-1}b-D^{-1}(D-L-U)x^{(k)}=$$

   $$= x^{(k)}+D^{-1}b-x^{(k)}+D^{-1}(L+U)x^{(k)}=$$

   $$= D^{-1}(L+U)x^{(k)} + D^{-1}b$$

   
   

[caption=Risolvi sistema lineare con metodo di Jacobi, label=codici/risolvi_jacobi.m, showstringspaces=false, frame=tRBl, extendedchars=true, basicstyle=pcrm, numbers=left, commentstyle= , frameround=fttt, stepnumber=1, numberstyle=, keywordstyle= , language=Matlab]codici/risolvi_jacobi.m

Esempi di risolvi_jacobi da pag.