Domande su convergenza di Newton-Raphson
Salve a tutti, Buon Natale (per il passato) e BuonAnno (per il futuro)
Ho da porvi qualche quesito...
1) Iniziando a studiare per un esame di Calcolo Numerico, proprio all'inizio c'è il ripasso di Newton-Raphson (tangente variabile). Viene dimostrato che la derivata della funzione di approssimazione della soluzione deve essere $<1$ affinchè il metodo converga, quindi:
$x_(n+1)=x_n-(f(x_n))/(f'(x_n))$ ---> Newton-Raphson
$g(x)=x-(f(x))/(f'(x))$ ---> generalizzazione
$|g'(x)|=|1-(f'(x))/(f'(x))+(f(x)*f''(x))/(f'(x)^2)|=|(f(x)*f''(x))/(f'(x)^2)|<1$ ---> condizione di convergenza
Dunque per la convergenza alla soluzione $x=alpha$ non ci sono problemi in un intorno della soluzione perchè la soluzione stessa è $f(alpha)=0$ che verifca la disuguaglianza.
Ma nel caso in cui $f'(alpha)=0$ (quindi un punto di radice multipla) si crea un problema evidente! Analiticamente risulta palese che il problema c'è, ma pensandoci graficamente non ho capito dove il problema sussista...infatti se si pensa ad esempio a una parabola il cui vertice tocca l'asse delle $x$, per questa risulterà $f(x)=0$ e $f'(x)=0$ nel vertice stesso, ma partendo da un punto lì vicino (o per la parabola in particolare, anche lontano) mi pare che il metodo converga, e pure piuttosto bene, all'avvicinarsi della soluzione. Invece la costante di convergenza del metodo iterativo (che lega le grandezze di 2 errori consecutivi) risulta:
$(f''(alpha))/(2f'(alpha))$
che in questo caso è infinita, rendendo infinito l'errore al passo successivo...invece a me verrebbe da dire che converge guardando il grafico.
2) Il secondo problema mi nasce nel momento in cui si ipotizza che la soluzione sia un flesso non orizzontale, dunque:
$f(alpha)=0$
$f'(alpha) ne 0$
$f''(alpha)=0$
infatti risulta che il metodo converge a maggior ragione secondo la condizione di convergenza, e la costante di convergenza dice che l'errore si annulla in un colpo solo (mmmmhhhhh :-S) ma sarebbe facilissimo fare un esempio grafico che dimostra la non convergenza di una situazione del genere con N-R...basta fare proprio un flesso non orizzontale sull'asse con la curvatura che gira normalmente in senso opposto ed è difficile far arrivare N-R alla soluzione!!
Cosa mi sfugge tra teoria e grafica?????
Ho da porvi qualche quesito...
1) Iniziando a studiare per un esame di Calcolo Numerico, proprio all'inizio c'è il ripasso di Newton-Raphson (tangente variabile). Viene dimostrato che la derivata della funzione di approssimazione della soluzione deve essere $<1$ affinchè il metodo converga, quindi:
$x_(n+1)=x_n-(f(x_n))/(f'(x_n))$ ---> Newton-Raphson
$g(x)=x-(f(x))/(f'(x))$ ---> generalizzazione
$|g'(x)|=|1-(f'(x))/(f'(x))+(f(x)*f''(x))/(f'(x)^2)|=|(f(x)*f''(x))/(f'(x)^2)|<1$ ---> condizione di convergenza
Dunque per la convergenza alla soluzione $x=alpha$ non ci sono problemi in un intorno della soluzione perchè la soluzione stessa è $f(alpha)=0$ che verifca la disuguaglianza.
Ma nel caso in cui $f'(alpha)=0$ (quindi un punto di radice multipla) si crea un problema evidente! Analiticamente risulta palese che il problema c'è, ma pensandoci graficamente non ho capito dove il problema sussista...infatti se si pensa ad esempio a una parabola il cui vertice tocca l'asse delle $x$, per questa risulterà $f(x)=0$ e $f'(x)=0$ nel vertice stesso, ma partendo da un punto lì vicino (o per la parabola in particolare, anche lontano) mi pare che il metodo converga, e pure piuttosto bene, all'avvicinarsi della soluzione. Invece la costante di convergenza del metodo iterativo (che lega le grandezze di 2 errori consecutivi) risulta:
$(f''(alpha))/(2f'(alpha))$
che in questo caso è infinita, rendendo infinito l'errore al passo successivo...invece a me verrebbe da dire che converge guardando il grafico.
2) Il secondo problema mi nasce nel momento in cui si ipotizza che la soluzione sia un flesso non orizzontale, dunque:
$f(alpha)=0$
$f'(alpha) ne 0$
$f''(alpha)=0$
infatti risulta che il metodo converge a maggior ragione secondo la condizione di convergenza, e la costante di convergenza dice che l'errore si annulla in un colpo solo (mmmmhhhhh :-S) ma sarebbe facilissimo fare un esempio grafico che dimostra la non convergenza di una situazione del genere con N-R...basta fare proprio un flesso non orizzontale sull'asse con la curvatura che gira normalmente in senso opposto ed è difficile far arrivare N-R alla soluzione!!
Cosa mi sfugge tra teoria e grafica?????
Risposte
"pizzaf40":
Dunque per la convergenza alla soluzione $x=alpha$ non ci sono problemi in un intorno della soluzione perchè la soluzione stessa è $f(alpha)=0$ che verifca la disuguaglianza.
Mi pare di capire che tu sia ben consapevole che questo discorso è "a spanne". Da quello che avviene in $\alpha$ ti serve dedurre cosa avviene in un intervallo che contenga questo punto (cui applicherai il teorema delle contrazioni).
"pizzaf40":
Ma nel caso in cui $f'(alpha)=0$ (quindi un punto di radice multipla) si crea un problema evidente! Analiticamente risulta palese che il problema c'è, ma pensandoci graficamente non ho capito dove il problema sussista...infatti se si pensa ad esempio a una parabola il cui vertice tocca l'asse delle $x$, per questa risulterà $f(x)=0$ e $f'(x)=0$ nel vertice stesso, ma partendo da un punto lì vicino (o per la parabola in particolare, anche lontano) mi pare che il metodo converga, e pure piuttosto bene, all'avvicinarsi della soluzione. Invece la costante di convergenza del metodo iterativo (che lega le grandezze di 2 errori consecutivi) risulta:
$(f''(alpha))/(2f'(alpha))$
che in questo caso è infinita, rendendo infinito l'errore al passo successivo...invece a me verrebbe da dire che converge guardando il grafico.
Non vedo il problema. La stima su Newton vale sotto certe condizioni. Se queste sono violate, non hai a disposizione la garanzia della convergenza, la stima sull'errore..., ma mica è detto che il metodo debba per forza divergere!
"pizzaf40":
2) Il secondo problema mi nasce nel momento in cui si ipotizza che la soluzione sia un flesso non orizzontale, dunque:
$f(alpha)=0$
$f'(alpha) ne 0$
$f''(alpha)=0$
infatti risulta che il metodo converge a maggior ragione secondo la condizione di convergenza, e la costante di convergenza dice che l'errore si annulla in un colpo solo (mmmmhhhhh :-S) ma sarebbe facilissimo fare un esempio grafico che dimostra la non convergenza di una situazione del genere con N-R...basta fare proprio un flesso non orizzontale sull'asse con la curvatura che gira normalmente in senso opposto ed è difficile far arrivare N-R alla soluzione!!
Cosa mi sfugge tra teoria e grafica?????
Mi pare il problema sia quello evidenziato nella prima parte della mia risposta. Per avere la stima, a te serve lavorare su un intervallo contenente $\alpha$, mica solo nel punto $\alpha$.
Ciao, scusa il ritardo, ma non ho internet a casa e mi collego quando posso.
Comunque il discorso sì, era fatto a spanne perchè così c'era stato presentato. Solo che...
...non sono riuscito a capirlo con sicurezza. Non son cosa sia il teorema delle contrazioni (e quindi neanche la sua utilità).
Ah ok, giusto...non avevo pensato al fatto che la convergenza non è negata...è solo non garantita! Però ho bisogno di una delucidazione...che condizioni vengono imposte per le condizioni di convergenza? Era quello che mi ha fregato...non ho trovato le condizioni nel testo e non ci sono state dette a lezione, e stupidamente non mi sono chiesto come mai mancavano condizioni di validità in una cosa del genere. Probabilmente ci sono state saltate apposta per semplificazione, visto che facciamo ing e lo scopo dell'esame è capire gli elementi finti e il metodo del gradinte coniugato, però mi piacerebbe capire lo stesso questo argomento...
Questo non l'ho capito...se $f''(x)=0$ la convergenza dovrebbe essere assicurata (a meno che non mi sfugga ancora qualche condizione di validità), invece nell'esempio che ti ho fatto la convergenza non avviene...non solo in $alpha$, ma neanche in un suo intorno...
Comunque il discorso sì, era fatto a spanne perchè così c'era stato presentato. Solo che...
Da quello che avviene in $alpha$ ti serve dedurre cosa avviene in un intervallo che contenga questo punto (cui applicherai il teorema delle contrazioni)
...non sono riuscito a capirlo con sicurezza. Non son cosa sia il teorema delle contrazioni (e quindi neanche la sua utilità).
Non vedo il problema. La stima su Newton vale sotto certe condizioni. Se queste sono violate, non hai a disposizione la garanzia della convergenza, la stima sull'errore..., ma mica è detto che il metodo debba per forza divergere!
Ah ok, giusto...non avevo pensato al fatto che la convergenza non è negata...è solo non garantita! Però ho bisogno di una delucidazione...che condizioni vengono imposte per le condizioni di convergenza? Era quello che mi ha fregato...non ho trovato le condizioni nel testo e non ci sono state dette a lezione, e stupidamente non mi sono chiesto come mai mancavano condizioni di validità in una cosa del genere. Probabilmente ci sono state saltate apposta per semplificazione, visto che facciamo ing e lo scopo dell'esame è capire gli elementi finti e il metodo del gradinte coniugato, però mi piacerebbe capire lo stesso questo argomento...
Mi pare il problema sia quello evidenziato nella prima parte della mia risposta. Per avere la stima, a te serve lavorare su un intervallo contenente $alpha$, mica solo nel punto $alpha$.
Questo non l'ho capito...se $f''(x)=0$ la convergenza dovrebbe essere assicurata (a meno che non mi sfugga ancora qualche condizione di validità), invece nell'esempio che ti ho fatto la convergenza non avviene...non solo in $alpha$, ma neanche in un suo intorno...
Help Fioravante (or someone else)...help 
Provo a risponderti io su cosa sia il teorema delle contrazioni.
Prima alcune definizioni:
Sia $(X,d)$ uno spazio metrico, sia $F:X->X$ una applicazione da $X$ in se medesimo, diremo che $F$ è una contrazione se per ogni $x_1,x_2$ appartenente a $X$ esiste $rho$ reale appartenente a $[0,1)$ tale che $d(F(x_1),F(x_2))<=rhod(x_1,x_2)$.
Sia $f:A->A$ una applicazione chiameremo punto fisso di $f$ ogni $a$ di $A$ tale che $f(a)=a$.
Teo di Banach Caccioppoli o elle contrazioni:
Sia $(X,d)$ uno spazio metrico completo, sia $F:X->X$ una contrazione in $(X,d)$, allora esiste uno ed un solo $y$ di $X$ tale che $F(y)=y$.
La dimostrazione si fa in due passi distinti, prima si prova l'esistenza del punto fisso, mostrando che la successione definita per ricorrenza: $x_0$ di $X$, $x_(n+1)=F(x_n)$ è di Cauchy, dunque per la completezza dello spazio metrico, che è assunta come ipotesi, tale successione converge ad un elemento di $X$, e si mostra che tale elemento è un punto fisso, poi si procede per assurdo e si mostra che se esistessero due distinti elementi di $X$ che fossero punti fissi per la contrazione ciò porterebbe ad una contraddizione.
Prima alcune definizioni:
Sia $(X,d)$ uno spazio metrico, sia $F:X->X$ una applicazione da $X$ in se medesimo, diremo che $F$ è una contrazione se per ogni $x_1,x_2$ appartenente a $X$ esiste $rho$ reale appartenente a $[0,1)$ tale che $d(F(x_1),F(x_2))<=rhod(x_1,x_2)$.
Sia $f:A->A$ una applicazione chiameremo punto fisso di $f$ ogni $a$ di $A$ tale che $f(a)=a$.
Teo di Banach Caccioppoli o elle contrazioni:
Sia $(X,d)$ uno spazio metrico completo, sia $F:X->X$ una contrazione in $(X,d)$, allora esiste uno ed un solo $y$ di $X$ tale che $F(y)=y$.
La dimostrazione si fa in due passi distinti, prima si prova l'esistenza del punto fisso, mostrando che la successione definita per ricorrenza: $x_0$ di $X$, $x_(n+1)=F(x_n)$ è di Cauchy, dunque per la completezza dello spazio metrico, che è assunta come ipotesi, tale successione converge ad un elemento di $X$, e si mostra che tale elemento è un punto fisso, poi si procede per assurdo e si mostra che se esistessero due distinti elementi di $X$ che fossero punti fissi per la contrazione ciò porterebbe ad una contraddizione.
Non posso fare molto di più che ribadire quello che avevo detto.
Sperando che, nel frattempo, il contributo del nostro chimico ti sia servito.
Un collegamento diretto fa contrazioni e metodo di Newton lo dovresti trovare su ogni testo decente di analisi numerica.
In rete ho trovato questo:
http://www.mat.uniroma3.it/users/ferretti/corso.pdf
vedi teorema 1.13 a pag. 28
Il punto chiave sta nelle prime tre righe della dimostrazione.
Vedi anche il successivo teorema 1.14
Puoi anche vedere:
http://profs.sci.univr.it/~demarchi/CN2 ... ioBook.pdf
da pag. 34
Se non basta, ci "risentiamo"
Sperando che, nel frattempo, il contributo del nostro chimico ti sia servito.
Un collegamento diretto fa contrazioni e metodo di Newton lo dovresti trovare su ogni testo decente di analisi numerica.
In rete ho trovato questo:
http://www.mat.uniroma3.it/users/ferretti/corso.pdf
vedi teorema 1.13 a pag. 28
Il punto chiave sta nelle prime tre righe della dimostrazione.
Vedi anche il successivo teorema 1.14
Puoi anche vedere:
http://profs.sci.univr.it/~demarchi/CN2 ... ioBook.pdf
da pag. 34
Se non basta, ci "risentiamo"
Sì, Giovanni mi è stato molto utile, ma mi rimane ancora il dubbio sul caso di $f''(alpha)=0$...tuttavia è una cosa assolutamente non necessaria per l'esame, e ora che il tempo stringe non mi resta che ringraziarvi, augurarvi buon anno, e andare a dormire rimandando il discorso a tempi più adatti!
In culo alla balena per i vostri esami (dicono che "in culo alla balena" funzioni a meraviglia
)
Ciau!!
In culo alla balena per i vostri esami (dicono che "in culo alla balena" funzioni a meraviglia
)Ciau!!
"pizzaf40":
In culo alla balena per i vostri esami (dicono che "in culo alla balena" funzioni a meraviglia
Speriamo!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo