Jacobiana, metodo di Newton e Hessiana

La matrice Jacobiana

Il gradiente descrive come varia una funzione a valori scalari. Per una funzione a valori vettoriali serve una matrice, la Jacobiana: con essa si linearizza la funzione e il metodo di Newton si estende ai sistemi di equazioni. Applicata al gradiente dà l'Hessiana, cioè le derivate seconde.

Sia $G\colon\mathbb R^n\to\mathbb R^m$. Ha $m$ componenti $G_i\colon\mathbb R^n\to\mathbb R$, ciascuna una funzione a valori scalari:

$$G(x)=\begin{pmatrix}G_1(x)\\\vdots\\G_m(x)\end{pmatrix}$$

Se esistono i gradienti $\nabla G_i(x)\in\mathbb R^n$, si usano tutti insieme in una matrice. Si dispongono per righe, trasposti, e si ottiene la matrice Jacobiana di $G$ in $x$:

$$J(x)=\begin{pmatrix}\nabla G_1(x)^\top\\\vdots\\\nabla G_m(x)^\top\end{pmatrix}\in\mathbb R^{m\times n}$$

L'elemento $(i,j)$ è $\partial G_i(x)/\partial x_j$. Le righe sono tante quante le funzioni, le colonne tante quante le variabili.

Esempio. Per $G\colon\mathbb R^2\to\mathbb R^3$, con $G_1=x_1^2x_2^2$, $G_2=x_1+x_2$ e $G_3=x_1^3-2x_2^2$, la Jacobiana ha 3 righe e 2 colonne (una costante sommata a una componente non la cambia). I gradienti sono

$$\begin{gathered} \nabla G_1(x)=\begin{pmatrix}2x_1x_2^2\\2x_1^2x_2\end{pmatrix}\\[0.4em] \nabla G_2(x)=\begin{pmatrix}1\\1\end{pmatrix}\\[0.4em] \nabla G_3(x)=\begin{pmatrix}3x_1^2\\-4x_2\end{pmatrix} \end{gathered}$$

e, messi per righe,

$$J(x)=\begin{pmatrix}2x_1x_2^2&2x_1^2x_2\\1&1\\3x_1^2&-4x_2\end{pmatrix}$$

Linearizzazione di una funzione vettoriale

Come per le funzioni scalari, vicino a $x$ la funzione si approssima con una parte lineare più un resto. Per ogni spostamento $d\in\mathbb R^n$:

$$\begin{gathered} G(x+d)=G(x)+J(x)\,d+\gamma(x,d)\\[0.6em] \lim_{d\to0}\frac{\|\gamma(x,d)\|}{\|d\|}=0 \end{gathered}$$

La parte lineare è $J(x)\,d$. Con $J(x)\in\mathbb R^{m\times n}$ e $d\in\mathbb R^n$ il prodotto sta in $\mathbb R^m$, come $G$. Il resto $\gamma(x,d)$ è un vettore di $\mathbb R^m$ che va a zero più in fretta di $\|d\|$. Per $m=1$, con $G=f$ a valori scalari, la Jacobiana è $\nabla f(x)^\top$ e si ritrova la formula delle funzioni scalari.

Differenziabilità. $G$ è differenziabile in $x$ se vale la linearizzazione con una matrice $A\in\mathbb R^{m\times n}$ al posto di $J(x)$. Se $G$ è differenziabile, la Jacobiana esiste e $A=J(x)$: è la condizione necessaria. Se la Jacobiana esiste ed è continua, $G$ è differenziabile: è la condizione sufficiente. Sono i risultati delle funzioni scalari, con la Jacobiana al posto del gradiente, enunciati senza dimostrazione.

Il metodo di Newton per i sistemi

In una variabile, per trovare uno zero di $f$ si sostituisce $f$ con la sua approssimazione lineare in $x_0$ e si prende il punto che la annulla: $x_1=x_0-f(x_0)/f'(x_0)$, con $f'(x_0)\neq0$.

Con più variabili si vuole risolvere un sistema di $n$ equazioni non lineari in $n$ incognite. Data $G\colon\mathbb R^n\to\mathbb R^n$, con tante componenti quante le variabili, si cerca $\bar x\in\mathbb R^n$ tale che $G(\bar x)=0$.

Il procedimento è lo stesso. Da $x_0$ si sostituisce $G$ con la sua approssimazione lineare, in cui $J(x_0)$ prende il posto di $f'(x_0)$:

$$\hat G(x)=G(x_0)+J(x_0)(x-x_0)$$

È lineare in $x$, quindi annullarla è risolvere un sistema lineare. Il nuovo punto $x_1$ è quello che la annulla:

$$G(x_0)+J(x_0)(x_1-x_0)=0$$

All'ipotesi $f'(x_0)\neq0$ corrisponde l'invertibilità di $J(x_0)$. Serve una matrice quadrata, cioè $m=n$: con $m\neq n$ l'inversa non esiste. Dunque

$$x_1=x_0-J(x_0)^{-1}G(x_0)$$

e, ripetendo da ogni punto ottenuto,

$$x_{k+1}=x_k-J(x_k)^{-1}G(x_k),\qquad k=0,1,2,\dots$$

Con $n=1$ è il metodo di una variabile, perché $J=f'$.

Nel piano ogni equazione $G_i(x)=0$ è una curva, e la sua approssimazione lineare in $x_0$ è una retta. Il punto $x_1$ è dove le due rette si incontrano. Nella figura, poiché $x_k$ indica l'iterato $k$, le componenti di $x$ si scrivono $x^{(1)},x^{(2)}$, e le due equazioni sono $\|x\|^2=4$ e $x^{(1)}x^{(2)}=1$.

Un passo di Newton su due equazioni

$x_0$$x_1$$\bar{x}$$x^{(1)}$$x^{(2)}$

• approssimazione lineare della prima
• approssimazione lineare della seconda
• $\Vert x{\Vert }^2=4$
• $x^{(1)}{x}^{(2)}=1$

$x_0^{(1)}$

2,4

$x_0^{(2)}$

1

Convergenza e criterio d'arresto

Convergenza locale. Se $G(\bar x)=0$ e $J(\bar x)$ è invertibile, un punto iniziale $x_0$ abbastanza vicino a $\bar x$ genera una successione che converge a $\bar x$. L'invertibilità serve in $\bar x$ perché il metodo inverte la Jacobiana lungo tutta la successione, che si avvicina a $\bar x$. Il risultato è locale: da un punto qualsiasi la convergenza non è garantita.

Arresto. $\bar x$ non è noto, e in aritmetica finita non si ottiene mai $G=0$ esattamente. Il criterio naturale è fermarsi quando il residuo è sotto una tolleranza $\varepsilon$, per esempio $10^{-9}$:

$$\|G(x_k)\|\le\varepsilon$$

Il risultato asintotico garantisce che il criterio sia soddisfatto dopo un numero finito di iterazioni, perché $G(x_k)\to G(\bar x)=0$. Un altro criterio è $\|x_{k+1}-x_k\|\le\varepsilon$. Un residuo piccolo non dice da solo quanto si è vicini a uno zero: con la precisione finita della macchina se ne occupa l'analisi numerica.

Punto iniziale. Quanto debba essere vicino $x_0$ non si sa, perché saperlo vorrebbe dire conoscere $\bar x$. Si usa una strategia multistart: tanti punti iniziali sparsi a caso nello spazio, nella speranza che da uno il metodo converga.

Costo. Con centinaia di migliaia di variabili, calcolare e invertire $J$ a ogni iterazione è costoso. Si può tenere la stessa matrice per alcune iterazioni e ricalcolarla, per esempio, ogni 5, come fa il metodo di Shamanskii. Ogni iterazione costa meno, ma si perde rapidità di convergenza, perché la matrice usata è vicina alla Jacobiana nel punto corrente senza coincidere con essa.

La matrice Hessiana

Il gradiente di una funzione scalare $f\colon\mathbb R^n\to\mathbb R$ è a sua volta una funzione a valori vettoriali, $\nabla f\colon\mathbb R^n\to\mathbb R^n$. Se ne può calcolare la Jacobiana, e si chiama matrice Hessiana: $\nabla^2 f(x)$. Ha tante righe quante le componenti di $\nabla f$ e tante colonne quante le variabili, quindi è $n\times n$. Qui $x_1,\dots,x_n$ sono di nuovo le componenti di $x$, come per il gradiente:

$$\nabla^2 f(x)=\begin{pmatrix} \dfrac{\partial^2 f(x)}{\partial x_1^2}&\cdots&\dfrac{\partial^2 f(x)}{\partial x_1\partial x_n}\\ \vdots&&\vdots\\ \dfrac{\partial^2 f(x)}{\partial x_n\partial x_1}&\cdots&\dfrac{\partial^2 f(x)}{\partial x_n^2} \end{pmatrix}$$

La riga $i$ è il gradiente di $\partial f/\partial x_i$: si deriva $\partial f/\partial x_i$ rispetto a ogni variabile. Sulla diagonale stanno le derivate seconde pure, fuori le derivate miste.

Esempio in due variabili. Se $f(x)=x_1^2x_2^3$, il gradiente è $\nabla f(x)=(2x_1x_2^3,\ 3x_1^2x_2^2)^\top$. Derivando ogni componente rispetto a $x_1$ e a $x_2$:

$$\nabla^2 f(x)=\begin{pmatrix}2x_2^3&6x_1x_2^2\\6x_1x_2^2&6x_1^2x_2\end{pmatrix}$$

Esempio in tre variabili. Se $f(x)=x_1^4-2x_2x_3+x_3^2$:

$$\nabla f(x)=\begin{pmatrix}4x_1^3\\-2x_3\\-2x_2+2x_3\end{pmatrix}$$

e l'Hessiana, $3\times3$, è

$$\nabla^2 f(x)=\begin{pmatrix}12x_1^2&0&0\\0&0&-2\\0&-2&2\end{pmatrix}$$

In entrambi gli esempi è simmetrica, e non per caso: vale per ogni funzione due volte differenziabile.

Approssimazione quadratica

Se $f$ è due volte differenziabile, vicino a $x$ si approssima con una funzione quadratica: alla parte lineare si aggiunge un termine con l'Hessiana.

$$\begin{aligned} f(x+d)&=f(x)+\nabla f(x)^\top d\\ &\quad+\tfrac12\,d^\top\nabla^2 f(x)\,d+r(x,d) \end{aligned}$$ $$\lim_{d\to0}\frac{|r(x,d)|}{\|d\|^2}=0$$

Il resto va a zero più in fretta di $\|d\|^2$, non solo di $\|d\|$. Per questo l'approssimazione quadratica è migliore di quella lineare. Con $n=1$ l'Hessiana è $f''$:

$$\begin{aligned} f(x_0+d)&=f(x_0)+f'(x_0)\,d\\ &\quad+\tfrac12f''(x_0)\,d^2+r(x_0,d) \end{aligned}$$

Approssimazione lineare e quadratica

$x$

• $f(x)=\sin x$
• approssimazione lineare
• approssimazione quadratica

$x_0$

1,2

Condizioni. Come per il gradiente e per la Jacobiana: se $f$ è due volte differenziabile, il gradiente esiste ed è continuo e l'Hessiana esiste ed è simmetrica: è la condizione necessaria. Se l'Hessiana esiste ed è continua, $f$ è due volte differenziabile: è la condizione sufficiente.

Le classi $C^0$, $C^1$, $C^2$

Su un dominio $D$ aperto:

• $f\in C^0(D)$: $f$ è continua su $D$;
• $f\in C^1(D)$: il gradiente esiste ed è continuo su $D$;
• $f\in C^2(D)$: esistono e sono continue anche le derivate seconde, cioè l'Hessiana esiste ed è continua su $D$.