ordine di convergenza del metodo di newton

[bord89]

salve. volevo alcune delucidazioni sull'applicazione del metodo di newton per approssimare gli zeri di una funzione, in particolare ho dei dubbi sull'ordine di convergenza di tale metodo.

ad esempio, se ho la funzione \( \displaystyle {f{{\left({x}\right)}}}={{\left({x}-{2}\right)}}^{{2}}{\left({x}-{1}\right)}{\left({x}+{1}\right)} \) le cui radici sono \( \displaystyle \alpha_{{1}}=\alpha_{{2}}={2} \), \( \displaystyle \alpha_{{3}}={1} \), \( \displaystyle \alpha_{{4}}=-{1} \); come faccio a stabilire con quale ordine il metodo converge a ogni radice? se ho capito bene, quando una radice ha molteplicità maggiore di 1, l'ordine di convergenza è pari a 1. nel caso di radici semplici invece l'ordine è sempre pari a 2? o devo andare a vedere come si comportano le derivate della f(x) nell'intorno di tali radici?

grazie per le eventuali risposte

[Blackorgasm]

Ciao Bord, come è?
Nel caso specifico che hai citato l'ordine di convergenza dovrebbe essere proprio 1 in quanto hai una radice con molteplicità >1, però non sono sicuro perché la nostra prof non ci ha mai fatto vedere casi in cui si ha contemporaneamente una radice con molteplicità >1 e radici semplici. Comunque in generale, in presenza di radici semplici la convergenza è sempre quadratica, quando invece hai radici con molteplicità \( \displaystyle \gamma\gt{1} \), per ristabilire la convergenza quadratica devi modificare il metodo facendo \( \displaystyle {x}_{{{n}+{1}}}={x}_{{n}}-\gamma\cdot\frac{{f{{\left({x}_{{n}}\right)}}}}{{{f{'}}{\left({x}_{{n}}\right)}}} \) dove \( \displaystyle \gamma \) è appunto la molteplicità della tua radice.

[canemacchina]

Il metodo converge con ordine 1 in caso di radici multiple, in modo quadratico in caso di radici semplici.

Per "in caso di radici semplici" o "in caso di radici multiple" non dovete intendere che la funzione ha solo radici semplici o multiple.

Se state approssimando una radice di una funzione che è multipla, allora convergerete in modo lineare, viceversa se state approssimando una radice semplice, covergerete quadraticamente.

Nel caso della funzione \( \displaystyle {{\left({x}-{2}\right)}}^{{2}}{\left({x}-{1}\right)}{\left({x}+{1}\right)} \) se approssimi la radice \( \displaystyle {x}={2} \) allora convergi linearmente, se approssimi la radice \( \displaystyle {x}={1} \) o \( \displaystyle {x}=-{1} \) allora convergi quadraticamente.

Come comportarsi in questo caso?
Beh non è semplice. Innanzi tutto il metodo di Newton, potendo convergere solo localmente, necessita di uno studio preliminare (analitco o numerico) per poter essere innescato. Una volta innescato se lo studio ha determinato che la radice che approssimeremo è multipla, allora sappiamo che la convergenza è lineare e possiamo operare qualche modifica per ripristinare la convergenza quadratica (@Blackorgasm: quello non è l'unico modo, è il modo migliore se conosci la molteplicità di quella radice, altrimenti si usa un altro metodo).
Se lo studio ha determinato una radice semplice, allora possiamo andare normalmente con una convergenza quadratica.

Mi sono spiegato bene?

p.s: ovviamente, non è semplice nel caso generale. Nel tuo caso capire quali siano le radici e sapere la loro molteplicità è semplice, quindi se su quella funzione devi fare qualche esempio è facile...

[Blackorgasm]

si infatti io parlavo per il caso in questione, altrimenti c'è il metodo di accelerazione di Aitken se non si conosce la molteplicità.

[orazioster]

Nel caso di radici di molteplicità ignota
si può anche adottare un metodo "modificato", di convergenza quadratica.
Considero la funzione \( \displaystyle {F}=\frac{{f}}{{f{'}}} \) -che ha glistessi zeri di \( \displaystyle {f} \) ma tutti semplici.

E la successione:
\( \displaystyle {x}_{{{n}+{1}}}={x}_{{n}}-\frac{{{F}{\left({x}_{{n}}\right)}}}{{{F}'{\left({x}_{{n}}\right)}}} \)

[canemacchina]

Carino questo, non lo conoscevo! Ha un nome questo metodo??

[orazioster]

Non lo so un suo nome. Nel
testo dove ho studiato, L.Gori "Calcolo Numerico" -un nome
per questo metodo non era scritto.

[canemacchina]

Ok grazie. Volevo saperlo solo per cercare in rete qualche delucidazione, dimostrazioni e teoria al contorno insomma!

[itpareid]

mi permetto di segnalare questo link
http://cdm.unimo.it/home/matematica/fun ... e/cap2.pdf
da pagina 11

[orazioster]

Che \( \displaystyle {F}=\frac{{f}}{{f{'}}} \) abbia gli stessi zeri di \( \displaystyle {f} \), ma tutti semplici
lo si può vedere mediante l'Hospital:
al limite di\( \displaystyle {x}\to{c}{s}{i} \), dove \( \displaystyle {c}{s}{i} \) è lo zero di molteplicità \( \displaystyle {n}{i} \), \( \displaystyle {F}\to\frac{{f{{\left({c}{s}{i}\right)}}}}{{{f{'}}{\left({c}{s}{i}\right)}={{f}}^{{{n}{i}-{1}}}\frac{{{c}{s}{i}}}{{{{f}}^{{{n}{i}}}{\left({c}{s}{i}\right)}={0}\right.}}\right.}} \), nell'
ipotesi \( \displaystyle {f} \) sia derivabile anche in grado \( \displaystyle {n}{i} \).

Per cui hai semplicemente il metodo di Newton applicato alla funzione \( \displaystyle {F} \).