Metodi del gradiente

Metodi del gradiente per sistemi lineari §

Vediamo ora come utilizzare i Gradient Methods per risolvere sistemi lineari con matrici simmetriche definite positive, associando ad essi una forma quadratica da minimizzare.

Assumiamo che il sistema da risolvere $Ax=b$ sia reale.

Forma quadratica associata §

Consideriamo la funzione quadratica $\Phi :{\mathbb{R}}^n\mapsto \mathbb{R}$:

$$\Phi (x)=\frac{1}{2}{x}^{T}Ax-x^{T}b$$

dove $A\in {\mathbb{R}}^{n\times n}$ è una matrice simmetrica e definita positiva. Scelta in maniera tale che il suo gradiente:

$$\nabla \Phi (x)=Ax-b=-r(x)$$

dove $r(x)$ è il residuo del sistema assegnato. L’ipotesi sulla matrice $A$ garantiscono il punto $x^{\ast }\in {\mathbb{R}}^n$ tale che $\nabla \Phi (x^{\ast })=0$ risulta essere un minimo globale di $\Phi$, infatti:

$$\Phi (y)=\Phi (x+(y-x))=\frac{1}{2}{x}^{T}Ax+\frac{1}{2}(y-x{)}^{T}A(y-x)+\frac{1}{2}{x}^{T}A(y-x)+\frac{1}{2}(y-x{)}^{T}Ax-x^{T}b-(y-x{)}^{T}b$$ $$=\frac{1}{2}{x}^{T}Ax+\frac{1}{2}(y-x{)}^{T}A(y-x)\ge \frac{1}{2}{x}^{T}Ax$$

se la matrice $A$ è definita positiva.

La precedente relazione si può esprimre in termini della norma dell’energia:

$$\frac{1}{2}\Vert y-x{\Vert }_A^2=\Phi (y)-\Phi (x)$$

Scelta ottimale del passo §

In generale usare Minimization rule non è fattible, in quanto si deve risolvere un altro problema di minimizzazzione unidimensionale. Tuttavia, ora siamo nel caso particolare di funzione obbiettivo quadratica, il che consente di calcolare analiticamente l’${\alpha }_k$ ottimale.

Proposizione Al $k-$passo di un metodo del gradiente, applicato ad una funzione quadratica definita positiva, il passo ottimale, ovvero che soddisfa la minimization rule:

$${\alpha }_k=argmi{n}_{\alpha }\Phi (x^k+\alpha p^k)$$

è dato da:

$${\alpha }_k=\frac{{r^k}^T{p}^k}{{p^k}^{T}A{p}^k}$$

inoltre, se $p^k$ è una direzione di decrescita, ovvero ${p^k}^T\nabla \Phi (x^k)<0$, si ha che ${\alpha }_k>0$.

Dimostrazione Risolviamo il problema di ottimizzazzione unidimensionale lungo la retta $y(\alpha )=x^k+\alpha P^k$:

$$\frac{\partial \Phi (y(\alpha ))}{\partial \alpha }=\sum _{i=1}^n\frac{\partial \Phi }{\partial y_i}\frac{d{y}_i}{d\alpha }=\nabla \Phi (y(\alpha ){)}^T{y}^{\prime }(\alpha )=(Ay(\alpha )-b{)}^T{p}^k$$ $$x^T{A}^T{p}^k+\alpha p^T{A}^T{p}^k-b^T{p}^k=0$$ $$\alpha =\frac{b^T{p}^k-x^T{A}^T{p}^k}{p^T{A}^T{p}^k}=\frac{(b^T-x^{T}A)p^k}{{p^k}^{T}A{p}^k}=\frac{{r^k}^T{p}^k}{{p^k}^{T}A{p}^k}$$

dove abbiamo usato la simmetria di $A$ nell’ultimo uguaglianza. Se $p^k$ è direzione di discesa,Il numeratore è positivo, anche il denomitatore essendo $A$ definita positiva, dunque ${\alpha }_k>0$. $\square$

Vale la seguente caratterizzazione legata alla norma dell’energia.

Proposizione Minimizzare la funzione energia $\Phi$ lungo la retta $y(\alpha )=x^k+\alpha p^k$ equivale a minimizzare la norma dell’energia dell’errore $e^{k+1}=x-x^{k+1}$, dove $x$ è la solizione del sistema.

Dimostrazione scriviamo esplicitamente cosa stiamo minimizzando:

$$\Phi (y(\alpha ))=\frac{1}{2}y(\alpha {)}^{T}Ay(\alpha )+y(\alpha {)}^{T}Ax$$

dove ho usato il fatto che $b=Ax$. Scriviamo esplicitamente la norma dell’energia dell’errore:

$$\Vert e^{k+1}{\Vert }_A^2=(x-x^{k+1}{)}^{T}A(x-x^{k+1})$$ $$(x-y(\alpha ){)}^{T}A(x-y(\alpha ))=x^{T}Ax-x^{T}Ay(\alpha )-y(\alpha )Ax+y({\alpha }^T)Ay(\alpha )=x^{T}Ax-2y(\alpha {)}^{T}Ax+y(\alpha {)}^{T}Ay(\alpha )$$

dove abbiamo usato il fatto che $A$ è hermitiana essendo simmetrica. Apparte il primo termine, il resto si può riscrivere come:

$$\Vert e^{k+1}{\Vert }_A^2=x^{T}Ax+2\Phi (y(\alpha ))$$

apparte il primo termine costante, noto che minimizzare $\Phi (y(\alpha ))$ è equivalente a minimizzare la norma dell’energia dell’errore. $\square$

Lemma di ortogonalità Vale il seguente risultato di ortogonalità tra i residui: ${r^{k+1}}^T{p}^k=0$, ovvero il residuo al passo $k+1$ di un metodo del gradiente è ortogonale alla direzione $p^k$.

Dimostrazione

$${r^{(k+1)}}^T{p}^k=(b-A{x}^{k+1}{)}^T{p}^k=(b-A(x^k+{\alpha }_k{p}^k){)}^T{p}^k=b^T{p}^k-x{A}^T{p}^k-{\alpha }_k{p^k}^T{A}^T{p}^k$$

usando ${\alpha }_k$ ottimale:

$$b^T{p}^k-x{A}^T{p}^k-\left(\frac{{r^k}^T{p}^k}{{p^k}^{T}A{p}^k}\right){p^k}^T{A}^T{p}^k=0$$

$\square$.

Steepest descent (SD) §

La scelta più ovvia per la direzione di discesa è proprio il residuo $r^k$, che è proprio meno il gradiente:

$$p^k=r^k$$

da cui il passo ottimo:

$${\alpha }_k=\frac{{r^k}^T{r}^k}{{r^k}^{T}A{r}^k}$$

si tratta dunque di un metodo di Richardson non stazionario e non precondizionato. Ovviamente continua a valere il lemma di ortogonalità, in questo caso le direzioni sono tutte ortogonali tra loro.

Errore §

Si può effettuare un bound sull’errore ad ogni passo, in termini del numero di condizionamento di $A$:

$$\Vert e^{(k+1)}{\Vert }_A\le \frac{K_2(A)-1}{K_2(A)+1}\Vert e^k\Vert \le {\left(\frac{K_2(A)-1}{K_2(A)+1}\right)}^{k+1}\Vert e^0\Vert$$

Dimostrazione Sia $x^k$ la soluzione generata al passo $k$ dal metodo del gradiente e ${x_R}^{k+1}$ il vettore generato da un passo del Metodo di Richardson stazionario non precondizionato (pongo $P=I$) a parametro ottimale, ovvero ${x_R}^{k+1}=x^k+{\alpha }_{opt}{r}^k$. Ma per definizione abbiamo scelto un ${\alpha }_k$ che minimizza la $A$-norma dell’energia al passo $k$, dunque:

$$\Vert e^{k+1}{\Vert }_A\le \Vert e_R^{k+1}{\Vert }_A$$

e la tesi segue. $\square$