Calcolo dell'ordine di convergenza di metodi iterativi
Come da titolo, qualcuno può spiegarmi come si calcola l'ordine di convergenza di metodi iterativi per la ricerca di radici di funzioni?
Allora, chiamiamo:
- [tex]e_i[/tex] l'errore commesso al passo [tex]i[/tex];
- [tex]\overline{x}[/tex] la radice esatta della funzione [tex]f[/tex] (che il metodo iterativo vuol trovare).
Allora, posto che da definizione:
diciamo che un metodo ha ordine di convergenza [tex]p[/tex] se [tex]p[/tex] è il più grande reale [tex]k \; t.c. \;lim_{i\rightarrow\infty}\dfrac{|e_{i+1}|}{|e_i|^p} = c < \infty[/tex]
è chiaro che non posso trovare [tex]p[/tex] facendo il limite prima per [tex]p=1[/tex], poi per [tex]p=2[/tex], ecc ecc fino a che non trovo il primo limite infinito.
Prendendo "spunto" (passatemi il termine) dalle dimostrazioni dell'ordine di convergenza per il metodo di Newton, la "tecnica" che mi sembra che vada (generalmente? sempre?) usata è quella di sviluppare con Taylor la funzione [tex]\Phi(\overline{x})[/tex] di iterazione e "ricavare" il rapporto [tex]\dfrac{|e_{i+1}|}{|e_i|^p}[/tex], in modo da poi effettuare solo quel limite e concludere che l'ordine di convergenza è [tex]p[/tex].
Ora mi chiedo due cose:
1) è questa la "tecnica" che va usata ogni volta?
2) se si, in che modo stabilisco quando fermare lo sviluppo con Taylor? A occhio? Perché chiaramente più vado avanti con lo sviluppo e più termini della forma [tex](\overline{x} - x_n)^i[/tex] trovo, termine che mi serve poi per ottenere il rapporto degli errori e fare il limite.
Faccio un esempio:
in un esercizio in preparazione del compito mi viene chiesto di determinare l'ordine di convergenza del metodo [tex]x_0 = 0, \;x_{k+1} = \cos(x_k)[/tex] per il calcolo della radice di [tex]f(x) = x-\cos(x)[/tex].
Per farlo ho sviluppato con Taylor [tex]\Phi(\overline{x})[/tex] in [tex]x_k[/tex] ottenendo alla fine (salto i passaggi intermedi per brevità, se qualcosa non torna ditemelo che li scrivo):
[tex]\dfrac{|e_{k+1}|}{|e_k|} = 1-\dfrac{1}{2}\sin(\xi)[/tex], con [tex]\xi[/tex] in un intorno di [tex]\overline{x}[/tex].
A questo punto passando ai limiti: [tex]lim_{k\rightarrow\infty}\dfrac{|e_{k+1}|}{|e_k|} = 1-\dfrac{1}{2}\sin(\xi)<\infty[/tex] e direi (credo) di aver dimostrato che l'ordine è lineare.
Ora, nei passaggi dello sviluppo di Taylor (che ho omesso) mi sono fermato ad uno sviluppo al primo ordine, in quando già così avevo "notato la possibilità" di ottenere un rapporto tra errori da un lato dell'equazione e un numero finito dall'altro, per cui ho pensato che se mi fossi fermato, passando ai limiti avrei ottenuto un limite finito e concluso una convergenza lineare. Ma in che modo (rigoroso, intendo), dovrei "capire" che non serve sviluppare fino ad ordini maggiori?
Teoricamente potrei provare a sviluppare fino, per es, al secondo ordine, e se nuovamente "mi accorgo" che ottengo un rapporto di errori da un lato dell'equazione e un numero finito dall'altro, so che passando ai limiti potrei concludere una convergenza quadratica.
In sostanza il mio problema è capire (sempre che lo sviluppo della funzione con Taylor sia il metodo sempre da applicare) quando fermare questo sviluppo.
Piccola parentesi:
In questo esercizio specifico per fortuna sono riuscito a darmi (successivamente) una conferma della validità della mia dimostrazione di convergenza lineare, perché operando alcuni conti è possibile vedere che la funzione di iterazione [tex]x_0 = 0, \;x_{k+1} = \cos(x_k)[/tex] non è altro che un caso particolare di metodo delle corde applicato alla funzione [tex]f(x) = x-\cos(x)[/tex], e per il metodo delle corde so già che la convergenza è lineare, quindi so di averlo fatto bene.
Il punto è che non vorrei limitarmi a "passare l'esame", ovvero fermarmi a dire "è perfettamente lecito pensare che ogni esercizio che ci presenterà il professore non sarà altro che l'applicazione di newton, corde, o secanti ad una funzione specifica, quindi mi basta ricostruire i suoi passaggi per capire quale metodo sia e tirare le conclusioni" (per esempio mostrando che è un caso particolare di un metodo noto e quindi spiattello ciò che c'è scritto sul libro, oppure fare lo sviluppo sapendo che devo ottenere una convergenza lineare, quadratica, ecc), ma vorrei capire a fondo in che modo si calcola l'ordine di convergenza di un metodo...
Grazie a tutti (in anticipo) e scusate per il post enorme (eh si, io chiacchiero troppo!
)
Allora, chiamiamo:
- [tex]e_i[/tex] l'errore commesso al passo [tex]i[/tex];
- [tex]\overline{x}[/tex] la radice esatta della funzione [tex]f[/tex] (che il metodo iterativo vuol trovare).
Allora, posto che da definizione:
diciamo che un metodo ha ordine di convergenza [tex]p[/tex] se [tex]p[/tex] è il più grande reale [tex]k \; t.c. \;lim_{i\rightarrow\infty}\dfrac{|e_{i+1}|}{|e_i|^p} = c < \infty[/tex]
è chiaro che non posso trovare [tex]p[/tex] facendo il limite prima per [tex]p=1[/tex], poi per [tex]p=2[/tex], ecc ecc fino a che non trovo il primo limite infinito.
Prendendo "spunto" (passatemi il termine) dalle dimostrazioni dell'ordine di convergenza per il metodo di Newton, la "tecnica" che mi sembra che vada (generalmente? sempre?) usata è quella di sviluppare con Taylor la funzione [tex]\Phi(\overline{x})[/tex] di iterazione e "ricavare" il rapporto [tex]\dfrac{|e_{i+1}|}{|e_i|^p}[/tex], in modo da poi effettuare solo quel limite e concludere che l'ordine di convergenza è [tex]p[/tex].
Ora mi chiedo due cose:
1) è questa la "tecnica" che va usata ogni volta?
2) se si, in che modo stabilisco quando fermare lo sviluppo con Taylor? A occhio? Perché chiaramente più vado avanti con lo sviluppo e più termini della forma [tex](\overline{x} - x_n)^i[/tex] trovo, termine che mi serve poi per ottenere il rapporto degli errori e fare il limite.
Faccio un esempio:
in un esercizio in preparazione del compito mi viene chiesto di determinare l'ordine di convergenza del metodo [tex]x_0 = 0, \;x_{k+1} = \cos(x_k)[/tex] per il calcolo della radice di [tex]f(x) = x-\cos(x)[/tex].
Per farlo ho sviluppato con Taylor [tex]\Phi(\overline{x})[/tex] in [tex]x_k[/tex] ottenendo alla fine (salto i passaggi intermedi per brevità, se qualcosa non torna ditemelo che li scrivo):
[tex]\dfrac{|e_{k+1}|}{|e_k|} = 1-\dfrac{1}{2}\sin(\xi)[/tex], con [tex]\xi[/tex] in un intorno di [tex]\overline{x}[/tex].
A questo punto passando ai limiti: [tex]lim_{k\rightarrow\infty}\dfrac{|e_{k+1}|}{|e_k|} = 1-\dfrac{1}{2}\sin(\xi)<\infty[/tex] e direi (credo) di aver dimostrato che l'ordine è lineare.
Ora, nei passaggi dello sviluppo di Taylor (che ho omesso) mi sono fermato ad uno sviluppo al primo ordine, in quando già così avevo "notato la possibilità" di ottenere un rapporto tra errori da un lato dell'equazione e un numero finito dall'altro, per cui ho pensato che se mi fossi fermato, passando ai limiti avrei ottenuto un limite finito e concluso una convergenza lineare. Ma in che modo (rigoroso, intendo), dovrei "capire" che non serve sviluppare fino ad ordini maggiori?
Teoricamente potrei provare a sviluppare fino, per es, al secondo ordine, e se nuovamente "mi accorgo" che ottengo un rapporto di errori da un lato dell'equazione e un numero finito dall'altro, so che passando ai limiti potrei concludere una convergenza quadratica.
In sostanza il mio problema è capire (sempre che lo sviluppo della funzione con Taylor sia il metodo sempre da applicare) quando fermare questo sviluppo.
Piccola parentesi:
In questo esercizio specifico per fortuna sono riuscito a darmi (successivamente) una conferma della validità della mia dimostrazione di convergenza lineare, perché operando alcuni conti è possibile vedere che la funzione di iterazione [tex]x_0 = 0, \;x_{k+1} = \cos(x_k)[/tex] non è altro che un caso particolare di metodo delle corde applicato alla funzione [tex]f(x) = x-\cos(x)[/tex], e per il metodo delle corde so già che la convergenza è lineare, quindi so di averlo fatto bene.
Il punto è che non vorrei limitarmi a "passare l'esame", ovvero fermarmi a dire "è perfettamente lecito pensare che ogni esercizio che ci presenterà il professore non sarà altro che l'applicazione di newton, corde, o secanti ad una funzione specifica, quindi mi basta ricostruire i suoi passaggi per capire quale metodo sia e tirare le conclusioni" (per esempio mostrando che è un caso particolare di un metodo noto e quindi spiattello ciò che c'è scritto sul libro, oppure fare lo sviluppo sapendo che devo ottenere una convergenza lineare, quadratica, ecc), ma vorrei capire a fondo in che modo si calcola l'ordine di convergenza di un metodo...
Grazie a tutti (in anticipo) e scusate per il post enorme (eh si, io chiacchiero troppo!
)
Risposte
Non ho l'esperienza per dirti "sì, il metodo dello sviluppo di taylor è generale"...di sicuro posso dirti che con quel metodo si possono dimostrare tutti i metodi iterativi che mi sono capitati:
- secante fissa;
- tangente fissa;
- secante variabile (regula falsi) con qualche attenzione finale...interessante se la trovi...è l'unica che si discosta un po' dallo standard degli altri, ma solo sul finale;
- tangente variabile (newton-raphson);
- estensioni multivariabile dei metodi suddetti;
- altri metodi di convergenza multivariabile.
Quindi penso di non poterti assicurare la generalità, ma di sicuro penso che sia più che adatto per i livelli di studio di un esame di calcolo e credo acnhe successivi
Per quanto riguarda l'ordine dello sviluppo di Taylor, basta fermarsi al primo ordine utile non nullo...gli altri li si considerano O piccoli trascurabili. Dimostrazione è il fatto che anche in N-R se ti fermi al termine precedente rimani con un pugno di mosche stecchite. Se vai oltre diventa irrisolvibile.
Se vuoi capire la cosa, esempio dill'ordine al quale fermarsi è il caso di radice multipla per N-R, cioè il caso in cui non si ha solo $f(xi)=0$ ma anche $f'(xi)=0$ con $xi$ soluzione. Alternativa sempre interessante per capire la cosa è il caso N-R con soluzione $f(xi)=0$ e $f''(xi)=0$.
Non è difficile svilupparli se vuoi provare...anche perchè facendo le semplificazioni ti accorgi subito se sei arrivato al termine giusto con taylor, se sei andato corto o lungo. Nel dubbio metti sempre un termine in più sviluppando la definizione...poi quando hai tutto al numeratore e denominatore ti rendi conto di come non far annullare il numeratore mantenendolo semplice, e come ottenere lo stesso risultato col denominatore...ovviamente il termine di Taylor richiesto da al num e denom non è per forza lo stesso.
Se vuoi fare i test detti per ultimi, quelli con le radici multiple su N-R, nota che $p$ non è più 2.
- secante fissa;
- tangente fissa;
- secante variabile (regula falsi) con qualche attenzione finale...interessante se la trovi...è l'unica che si discosta un po' dallo standard degli altri, ma solo sul finale;
- tangente variabile (newton-raphson);
- estensioni multivariabile dei metodi suddetti;
- altri metodi di convergenza multivariabile.
Quindi penso di non poterti assicurare la generalità, ma di sicuro penso che sia più che adatto per i livelli di studio di un esame di calcolo e credo acnhe successivi
Per quanto riguarda l'ordine dello sviluppo di Taylor, basta fermarsi al primo ordine utile non nullo...gli altri li si considerano O piccoli trascurabili. Dimostrazione è il fatto che anche in N-R se ti fermi al termine precedente rimani con un pugno di mosche stecchite. Se vai oltre diventa irrisolvibile.
Se vuoi capire la cosa, esempio dill'ordine al quale fermarsi è il caso di radice multipla per N-R, cioè il caso in cui non si ha solo $f(xi)=0$ ma anche $f'(xi)=0$ con $xi$ soluzione. Alternativa sempre interessante per capire la cosa è il caso N-R con soluzione $f(xi)=0$ e $f''(xi)=0$.
Non è difficile svilupparli se vuoi provare...anche perchè facendo le semplificazioni ti accorgi subito se sei arrivato al termine giusto con taylor, se sei andato corto o lungo. Nel dubbio metti sempre un termine in più sviluppando la definizione...poi quando hai tutto al numeratore e denominatore ti rendi conto di come non far annullare il numeratore mantenendolo semplice, e come ottenere lo stesso risultato col denominatore...ovviamente il termine di Taylor richiesto da al num e denom non è per forza lo stesso.
Se vuoi fare i test detti per ultimi, quelli con le radici multiple su N-R, nota che $p$ non è più 2.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo