Ordine di convergenza del metodo di newton
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 $f(x)=(x-2)^2(x-1)(x+1)$ le cui radici sono $\alpha_1=\alpha_2=2$, $\alpha_3=1$, $\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
ad esempio, se ho la funzione $f(x)=(x-2)^2(x-1)(x+1)$ le cui radici sono $\alpha_1=\alpha_2=2$, $\alpha_3=1$, $\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
Risposte
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à $gamma>1$, per ristabilire la convergenza quadratica devi modificare il metodo facendo $x_(n+1)=x_n-gamma*f(x_n)/(f'(x_n))$ dove $gamma$ è appunto la molteplicità della tua radice.
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à $gamma>1$, per ristabilire la convergenza quadratica devi modificare il metodo facendo $x_(n+1)=x_n-gamma*f(x_n)/(f'(x_n))$ dove $gamma$ è appunto la molteplicità della tua radice.
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 $(x-2)^2(x-1)(x+1)$ se approssimi la radice $x=2$ allora convergi linearmente, se approssimi la radice $x=1$ o $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...
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 $(x-2)^2(x-1)(x+1)$ se approssimi la radice $x=2$ allora convergi linearmente, se approssimi la radice $x=1$ o $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...
si infatti io parlavo per il caso in questione, altrimenti c'è il metodo di accelerazione di Aitken se non si conosce la molteplicità.
Nel caso di radici di molteplicità ignota
si può anche adottare un metodo "modificato", di convergenza quadratica.
Considero la funzione $F=f/f'$ -che ha glistessi zeri di $f$ ma tutti semplici.
E la successione:
$x_(n+1)=x_n -(F(x_n))/(F'(x_n))$
si può anche adottare un metodo "modificato", di convergenza quadratica.
Considero la funzione $F=f/f'$ -che ha glistessi zeri di $f$ ma tutti semplici.
E la successione:
$x_(n+1)=x_n -(F(x_n))/(F'(x_n))$
Carino questo, non lo conoscevo! Ha un nome questo metodo??
Non lo so un suo nome. Nel
testo dove ho studiato, L.Gori "Calcolo Numerico" -un nome
per questo metodo non era scritto.
testo dove ho studiato, L.Gori "Calcolo Numerico" -un nome
per questo metodo non era scritto.
Ok grazie. Volevo saperlo solo per cercare in rete qualche delucidazione, dimostrazioni e teoria al contorno insomma!
mi permetto di segnalare questo link
http://cdm.unimo.it/home/matematica/fun ... e/cap2.pdf
da pagina 11
http://cdm.unimo.it/home/matematica/fun ... e/cap2.pdf
da pagina 11
Che $F=f/f'$ abbia gli stessi zeri di $f$, ma tutti semplici
lo si può vedere mediante l'Hospital:
al limite di$x->\csi$, dove $\csi$ è lo zero di molteplicità $\ni$, $F->f(\csi)/(f'(csi)=f^(\ni-1)(\csi)/(f^(\ni)(\csi)=0$, nell'
ipotesi $f$ sia derivabile anche in grado $\ni$.
Per cui hai semplicemente il metodo di Newton applicato alla funzione $F$.
lo si può vedere mediante l'Hospital:
al limite di$x->\csi$, dove $\csi$ è lo zero di molteplicità $\ni$, $F->f(\csi)/(f'(csi)=f^(\ni-1)(\csi)/(f^(\ni)(\csi)=0$, nell'
ipotesi $f$ sia derivabile anche in grado $\ni$.
Per cui hai semplicemente il metodo di Newton applicato alla funzione $F$.
Mi interessavano un po' di dimostrazioni sull'ordine di convergenza, per dire... Ci provo da solo ora! 
Ciao a tutti,
scusate l'intromissione, ma a questo proposito avrei un ulteriore quesito sulla convergenza del metodo di Newton.
La nostra prof ci ha detto che può essere considerato come un metodo di punto fisso, quindi vale anche per Newton la condizione che dice che se esiste una funzione g tale che g(x*)=x* e |g'(x*)|<1 allora il metodo converge linearmente e se |g'(x*)|=0 ha invece convergenza quadratica?
Inoltre, come si può determinare la cosiddetta regione di convergenza?
Inoltre
|g'(x*)|<1 deve essere strettamente minore di 1 o può essere anche uguale? Nel caso sia "strettamente", se quel modulo è =1 cosa implica?
scusate l'intromissione, ma a questo proposito avrei un ulteriore quesito sulla convergenza del metodo di Newton.
La nostra prof ci ha detto che può essere considerato come un metodo di punto fisso, quindi vale anche per Newton la condizione che dice che se esiste una funzione g tale che g(x*)=x* e |g'(x*)|<1 allora il metodo converge linearmente e se |g'(x*)|=0 ha invece convergenza quadratica?
Inoltre, come si può determinare la cosiddetta regione di convergenza?
Inoltre
|g'(x*)|<1 deve essere strettamente minore di 1 o può essere anche uguale? Nel caso sia "strettamente", se quel modulo è =1 cosa implica?
"*martiki*":
La nostra prof ci ha detto che può essere considerato come un metodo di punto fisso, quindi vale anche per Newton la condizione che dice che se esiste una funzione g tale che g(x*)=x* e |g(x*)|<1 allora il metodo converge linearmente e se |g(x*)|=0 ha invece convergenza quadratica?
Certo, il metodo di Newton utilizza l'iterazione di puntofisso $x_(k+1)=x_k - f(x_k)/(f'(x_k))$. Quindi la funzione di iterazione di punto fisso in questo caso è $g(x)=x - f(x)/(f'(x))$.
Se provi a fare $g'(x*)$, vedi subito che risulta $0$. Quindi sicuramente tale condizione è soddisfatta.
Questo credo che però non ci dica nulla sull'ordine di convergenza ( se quadratico o lineare). Per dimostrare che l'ordine di convergenza è quadratico si considera il limite $ lim_(k -> infty) |e_(k+1)/(e_k)^p| $[nota]$e_k $ indica l'errore al passo k-esimo[/nota] , e si dimostra che per $p=2$, nel caso di zeri non multipli, la convergenza è quadratica.
"*martiki*":
|g(x*)|<1 deve essere strettamente minore di 1 o può essere anche uguale? Nel caso sia "strettamente", se quel modulo è =1 cosa implica?
Deve essere strettamente minore. Se fosse uguale a $1$, la convergenza non è assicurata. Potrebbe convergere come no.
"*martiki*":A parte che manca qualche segno di derivazione, non è nemmeno esattamente così: dato un punto unito \(\xi\) e la funzione d'iterazione \(g\) (i.e. \(\xi=g(\xi)\)), se \(g'(\xi)=0\), lo schema iterativo ha convergenza almeno quadratica.
quindi vale anche per Newton la condizione che dice che se esiste una funzione g tale che g(x*)=x* e |g(x*)|<1 allora il metodo converge linearmente e se |g(x*)|=0 ha invece convergenza quadratica?
"*martiki*":Sia \(I=[a,b]\) un intervallo tale che \(C^1(I)\ni g\) sia una contrazione, allora il punto fisso \(\xi\) è un attrattore se \(|g'(x)|<1,\>\forall x\in I\). Localmente ti è sufficiente la condizione \(|g'(\xi)|<1\) e scegliere il punto iniziale \(x_0\) in un opportuno intorno di \(\xi\) ove, cioè, la funzione \(|g'|\) mantenga il proprio segno.
come si può determinare la cosiddetta regione di convergenza?
Soddisfatte queste condizioni è assicurata la convergenza, ma non significa che si abbia ordine di convergenza lineare (come dici nella prima parte).
Grazie per la spiegazione 
ora ho corretto anche i segni di derivata che mi erano sfuggiti!
ora ho corretto anche i segni di derivata che mi erano sfuggiti!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo