Calcolo numerico/Radici di sistemi non lineari

Adattamento del metodo di Newton

Problema: data la funzione $f\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}$, trovare $x_{\ast }$ tale che $f(x_{\ast })=0$.

Consideriamo un sottoinsieme $D\subset \mathbb {R} ^{n}$ in cui $f$ sia di classe $C^{1}$. Consideriamo la matrice jacobiana. Trovare gli zeri della funzione applicando il metodo di Newton equivale a risolvere l'equazione:

${\begin{cases}f(x)=f(x_{k})+J_{f}(x_{k})*(x-x_{k})\\f(x)=0\end{cases}}$

Quindi

$0=f(x_{k})+J_{f}(x_{k})*(x_{k+1}-x_{k})$

$(x_{k+1}-x_{k})=-J_{f}^{-1}(x_{k})*f(x_{k})\quad {\hbox{metodo di Newton}}$

Per evitare di invertire la matrice sul calcolatore, risolviamo il sistema lineare

$J_{f}(x_{k})(x_{k+1}-x_{k})=-f(x_{k})$

Supponiamo di essere al $k$-esimo passo di Newton, allora poniamo

$K=x_{k+1}-x_{k}$

Risolviamo

$J_{f}(x_{k})*K=-f(x_{k})$

Poniamo

$x_{k+1}=x_{k}+K$

Come nel caso scalare, la convergenza del metodo di Newton è quadratica, se è sufficientemente vicino alla radice.

Lo jacobiano è non singolare se la radice è semplice.

Costo computazionale nella risoluzione del sistema

Pensiamo di risolvere il sistema lineare usando una fattorizzazione. Questo comporta un grande aumento del costo computazionale. Allora per risparmiare operazioni, si aggiorna lo jacobiano di $f$ solo periodicamente, per sfruttare la fattorizzazione di $J_{f}(x_{k})$ più volte. Questo rallenta la convergenza.

Pensando invece di usare metodi iterativi, consideriamo un ciclo di Newton con le iterazioni (outer iteration), e all'interno, nel passo in cui bisogna risolvere il sistema con la jacobiana, si inserisce un altro metodo iterativo (inner iteration).

Siccome l'obiettivo è quello di convergere alla radice, nelle prime iterazioni del metodo di Newton la soluzione non viene calcolata esattamente (si fissa un numero di iterazioni $n_{max}$ basso per il metodo iterativo). Si è interessati a risolvere il sistema in modo più preciso tanto più si pensa di essere vicino alla radice.