Analisi numerica: condizionamento della somma
In analisi numerica il problema di sommare due numeri reali o complessi può non essere ben condizionato. In particolare se la somma è prossima allo zero, si possono verificare errori catastrofici. Su questo non ci piove.
Invece piove sulle tecniche usate per aggirare il problema. Faccio direttamente un esempietto facile facile col metodo iterativo della "falsa posizione" per equazioni non lineari. Se l'equazione è $f(x)=0$, dopo qualche considerazione geometrica arriviamo a dire che la funzione iteratrice del metodo è $Phi(x)=x-f(x)(x-c)/(f(x)-f(c))$. Se facciamo i conti possiamo anche dire che $Phi(x)=(cf(x)-xf(c))/(f(x)-f(c))$, con cui faremmo ad ogni passo un'operazione in meno. Però la prima forma è preferibile alla seconda per questioni di condizionamento. Perché?
Invece piove sulle tecniche usate per aggirare il problema. Faccio direttamente un esempietto facile facile col metodo iterativo della "falsa posizione" per equazioni non lineari. Se l'equazione è $f(x)=0$, dopo qualche considerazione geometrica arriviamo a dire che la funzione iteratrice del metodo è $Phi(x)=x-f(x)(x-c)/(f(x)-f(c))$. Se facciamo i conti possiamo anche dire che $Phi(x)=(cf(x)-xf(c))/(f(x)-f(c))$, con cui faremmo ad ogni passo un'operazione in meno. Però la prima forma è preferibile alla seconda per questioni di condizionamento. Perché?
Risposte
Dimmi esattamente chi sono x,c,f(x),f(c) così te lo dico per bene.
Ps. Comunque il succo della questione starà nel fatto che il coefficiente di amplificazione di una differenza ha al denominatore la differenza. Nella prima forma fai x meno una cosa piccola. Quindi avrai un denominatore non troppo piccolo. Nella seconda invece i coefficienti potrebbero esplodere.
Ps. Comunque il succo della questione starà nel fatto che il coefficiente di amplificazione di una differenza ha al denominatore la differenza. Nella prima forma fai x meno una cosa piccola. Quindi avrai un denominatore non troppo piccolo. Nella seconda invece i coefficienti potrebbero esplodere.
"Megan00b":
Ps. Comunque il succo della questione starà nel fatto che il coefficiente di amplificazione di una differenza ha al denominatore la differenza.
Se ho capito bene la tua spiegazione dovrebbe essere proprio il vettore $((1)/(|x-y|), (1)/(|x-y|))$.
"Megan00b":
Nella prima forma fai x meno una cosa piccola. Quindi avrai un denominatore non troppo piccolo. Nella seconda invece i coefficienti potrebbero esplodere.
Aspetta, aspetta, forse ho capito... Fai x meno una cosa piccola perché quell'$f(x)$, man mano che vai avanti col procedimento, diventa sempre più piccolo in quanto stai approssimando la sua radice (e abbiamo delle ipotesi che garantiscono la convergenza). Quindi è quell'$f(x)$ che ammazza gli errori che ti escono dalla differenza... Invece nella seconda forma non hai questa distinzione.
"dissonance":
Se ho capito bene la tua spiegazione dovrebbe essere proprio il vettore $((1)/(|x-y|), (1)/(|x-y|))$.
Sì!
"dissonance":
Aspetta, aspetta, forse ho capito... Fai x meno una cosa piccola perché quell'$f(x)$, man mano che vai avanti col procedimento, diventa sempre più piccolo in quanto stai approssimando la sua radice (e abbiamo delle ipotesi che garantiscono la convergenza). Quindi è quell'$f(x)$ che ammazza gli errori che ti escono dalla differenza... Invece nella seconda forma non hai questa distinzione.
Questa è un'ottima motivazione. Ci sono delle altre considerazioni che si possono fare. Non so ora quali siano state fatte dall'autore della dispensa perchè non conosco chi siano x,c e f.
Se hai voglia di metterci le mani...
(Metodo regula falsi-falsa posizione): Abbiamo un'equazione $f(x)=0$, $f:I\toRR$, supponiamo che $f$ abbia un solo zero semplice in $I$. $c$ e $x_0$ sono punti di $I$ scelti in maniera tale da garantire la convergenza della successione delle iterate della $Phi$. (Per esempio si può supporre che $f''$ sia a segno costante, e che $f(x_0)f(c)>0$; ma ci sono altre condizioni sufficienti).
Comunque se hai tempo e voglia di continuare ad aiutarmi (hai già fatto parecchio! Adesso mi è molto più chiara la logica da seguire in queste cose!
)potresti spiegarmi questo: a questo punto noi non abbiamo finito con l'analisi degli errori, o mi sbaglio? Abbiamo detto che una delle due espressioni propaga l'errore inerente in una maniera accettabile ma ancora non ci sono dei bound validi per l'errore totale. In pratica, se volessi scrivere una function Matlab che implementa il metodo, come faccio a sapere che errore sto commettendo?
(Magari lascia perdere questo metodo che non è molto significativo, e se vuoi fare esempi usa un metodo con cui stai più comodo, per esempio Newton-Raphson).
(Metodo regula falsi-falsa posizione): Abbiamo un'equazione $f(x)=0$, $f:I\toRR$, supponiamo che $f$ abbia un solo zero semplice in $I$. $c$ e $x_0$ sono punti di $I$ scelti in maniera tale da garantire la convergenza della successione delle iterate della $Phi$. (Per esempio si può supporre che $f''$ sia a segno costante, e che $f(x_0)f(c)>0$; ma ci sono altre condizioni sufficienti).
Comunque se hai tempo e voglia di continuare ad aiutarmi (hai già fatto parecchio! Adesso mi è molto più chiara la logica da seguire in queste cose!
)potresti spiegarmi questo: a questo punto noi non abbiamo finito con l'analisi degli errori, o mi sbaglio? Abbiamo detto che una delle due espressioni propaga l'errore inerente in una maniera accettabile ma ancora non ci sono dei bound validi per l'errore totale. In pratica, se volessi scrivere una function Matlab che implementa il metodo, come faccio a sapere che errore sto commettendo? (Magari lascia perdere questo metodo che non è molto significativo, e se vuoi fare esempi usa un metodo con cui stai più comodo, per esempio Newton-Raphson).
Devo darti una delusione o forse no....
Come ti avevo accennato prima tutto questo sistema di analisi degli errori <> per i metodi iterativi. Nel senso che teoricamente funziona, ma i metodi iterativi hanno una proprietà particolare: usare un metodo iterativo vuol dire sostanzialmente calcolare i termini di una successione e sfruttare il fatto che questa ha come limite lo zero che si vuole calcolare.
Se ${x_0,x_1,x_2,....}$ è la successione delle iterate del nostro metodo anche la successione ${x_1,x_2,....}$ converge allo stesso zero. Dunque per farla breve l'analisi dell'errore algoritmico con il metodo generale dice poco riguardo un metodo iterativo perchè è come se ad ogni passo cominci da capo. Invece con altri metodi l'errore algoritmico finale è il risultato di tutti gli errori ai passi intermedi almplificati man mano. Insomma se tu facessi l'analisi (in avanti o all'indietro) dell'errore algoritmico al passo k non sapresti come usarla nell'analisi al passo k+1. Perchè la successione punta sempre alla soluzione. (questo ovviamente nel caso che la successione non finisca in zone repulsive per la soluzione-caso patologico difficile da ottenere)
Allora come fare? Si usano dei risultati diversi, ad esempio:
Teorema
Sia g di classe C1 su un intorno $I=[alpha-rho,alpha+rho]$ della soluzione $alpha=g(alpha)$. Sia $lambda=max_{|x-alpha|<=rho}|g'(x)|<1$. Siano $delta_i$ gli errori assoluti introdotti nel calcolo effettivo dell'i-esima iterazione cioè $barx_i=g(barx_{i-1})+delta_i$. Supponiamo che esista $delta$ tale che $AAi\ |delta_i|<=delta$. Posto $sigma=delta/(1-lambda)$, se $sigma
[La dimostrazione è per induzione su i.]
Questo teorema ti dice che se g è sufficientemente regolare gli errori che otterrai faranno sì che la soluzione effettivamente calcolata non sia la soluzione corretta ma che cada in un intorno relativamente piccolo della soluzione corretta. Io avevo trovato questa immagine per chiarirlo: immagina di tirare una freccia con un arco infallibile che centra sempre il centro del bersaglio. Però una folata di vento la devia e la fa finire in un intorno del bersaglio. Quanto è piccolo l'intorno? Si tratta di misurare che velocità che aveva il vento-per noi la stabilità dell'algoritmo. Dipende da vari aspetti.
Si vede meglio se passiamo agli errori relativi:
Se chiamiamo $epsilon_i$ l'errore relativo indotto al passo i (quindi $delta_i=g(barx_i)epsilon_i$) e supponiamo che sia $AAi\ |epsilon_i|<=epsilon$ e $max_{|x-alpha|<=rho}|g(x)|=M$ allora posto $delta=epsilonM$ dal teorema si ha:
$|barx_i-alpha|/|alpha|<=sigma/|alpha|+lambda^i(rho/|alpha|-sigma/|alpha|).$
Se osservi bene vedi che la quantità $sigma/|alpha|=(epsilonM)/(|alpha|(1-lambda))$ dà una stima dell'incertezza con cui è possibile determinare la soluzione per effetto degli errori di arrotondamento.
Anche di questo teorema puoi dare una versione con ipotesi lievemente più deboli.
Quindi in generale per l'errore algoritmico di un metodo iterativo non fai l'analisi dell'errore al passo ma cerchi di dare una stima su quanto gli errori a ogni passo influenzano il limite della successione effettivamente calcolata.
o forse no....Come ti avevo accennato prima tutto questo sistema di analisi degli errori <
Se ${x_0,x_1,x_2,....}$ è la successione delle iterate del nostro metodo anche la successione ${x_1,x_2,....}$ converge allo stesso zero. Dunque per farla breve l'analisi dell'errore algoritmico con il metodo generale dice poco riguardo un metodo iterativo perchè è come se ad ogni passo cominci da capo. Invece con altri metodi l'errore algoritmico finale è il risultato di tutti gli errori ai passi intermedi almplificati man mano. Insomma se tu facessi l'analisi (in avanti o all'indietro) dell'errore algoritmico al passo k non sapresti come usarla nell'analisi al passo k+1. Perchè la successione punta sempre alla soluzione. (questo ovviamente nel caso che la successione non finisca in zone repulsive per la soluzione-caso patologico difficile da ottenere)
Allora come fare? Si usano dei risultati diversi, ad esempio:
Teorema
Sia g di classe C1 su un intorno $I=[alpha-rho,alpha+rho]$ della soluzione $alpha=g(alpha)$. Sia $lambda=max_{|x-alpha|<=rho}|g'(x)|<1$. Siano $delta_i$ gli errori assoluti introdotti nel calcolo effettivo dell'i-esima iterazione cioè $barx_i=g(barx_{i-1})+delta_i$. Supponiamo che esista $delta$ tale che $AAi\ |delta_i|<=delta$. Posto $sigma=delta/(1-lambda)$, se $sigma
[La dimostrazione è per induzione su i.]
Questo teorema ti dice che se g è sufficientemente regolare gli errori che otterrai faranno sì che la soluzione effettivamente calcolata non sia la soluzione corretta ma che cada in un intorno relativamente piccolo della soluzione corretta. Io avevo trovato questa immagine per chiarirlo: immagina di tirare una freccia con un arco infallibile che centra sempre il centro del bersaglio. Però una folata di vento la devia e la fa finire in un intorno del bersaglio. Quanto è piccolo l'intorno? Si tratta di misurare che velocità che aveva il vento-per noi la stabilità dell'algoritmo. Dipende da vari aspetti.
Si vede meglio se passiamo agli errori relativi:
Se chiamiamo $epsilon_i$ l'errore relativo indotto al passo i (quindi $delta_i=g(barx_i)epsilon_i$) e supponiamo che sia $AAi\ |epsilon_i|<=epsilon$ e $max_{|x-alpha|<=rho}|g(x)|=M$ allora posto $delta=epsilonM$ dal teorema si ha:
$|barx_i-alpha|/|alpha|<=sigma/|alpha|+lambda^i(rho/|alpha|-sigma/|alpha|).$
Se osservi bene vedi che la quantità $sigma/|alpha|=(epsilonM)/(|alpha|(1-lambda))$ dà una stima dell'incertezza con cui è possibile determinare la soluzione per effetto degli errori di arrotondamento.
Anche di questo teorema puoi dare una versione con ipotesi lievemente più deboli.
Quindi in generale per l'errore algoritmico di un metodo iterativo non fai l'analisi dell'errore al passo ma cerchi di dare una stima su quanto gli errori a ogni passo influenzano il limite della successione effettivamente calcolata.
"Megan00b":
Quindi in generale per l'errore algoritmico di un metodo iterativo non fai l'analisi dell'errore al passo ma cerchi di dare una stima su quanto gli errori a ogni passo influenzano il limite della successione effettivamente calcolata.
E a quel punto l'errore che resta da controllare è solo quello di troncamento, giusto?
Cioè: abbiamo una successione $x_n$ convergente ad $alpha$ (l'arco infallibile)
ma gli errori di arrotondamento faranno sì che calcoleremo una successione $\bar{x_n}$ convergente ad $\bar{alpha}$ (dopo la folata di vento).
Come se non bastasse, noi non calcoleremo effettivamente $\bar{alpha}$ ma una sua approssimazione, diciamo $\bar{x_{N}}$. Su questa approssimazione commettiamo un errore di troncamento che supponiamo di saper stimare. Allora quale sarà l'errore totale? La somma dell'errore di troncamento e di $|alpha-\bar{alpha}|$?
Sì.
Però in generale l'errore di troncamento non si considera come un vero e proprio errore. Nel senso che inerente e algoritmico sono errori che dipendono dal problema e diciamo che non puoi farci niente. L'arciere non può farci niente se arriva la folata di vento o se l'arco è difettoso.
Invece l'errore di troncamento lo possiamo scegliere noi, in modo che sia più piccolo della precisione di macchina e quindi capisci che ha una natura diversa. Però insomma questa è una sottigliezza.
Invece l'errore di troncamento lo possiamo scegliere noi, in modo che sia più piccolo della precisione di macchina e quindi capisci che ha una natura diversa. Però insomma questa è una sottigliezza.
io doverei saperlo esempio 76=7*10+6*1=76
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo