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
Mi sfugge una cosa....cosa centra la somma con la parte di sotto?
Comunque in generale il condizionamento si misura con i coefficienti di amplificazione dell'errore. Dovresti calcolarli per le due funzioni $Phi$ che hai scritto ed essendo funzioni della x andrebbero discusse delle argomentazioni che provano che il primo coefficiente è minore dell'altro.
Os. Ma questa compressione della $Phi$ che hai scritto non è a occhio e croce il emtodo di Aitken per l'accelerazione di convergenza?
Comunque in generale il condizionamento si misura con i coefficienti di amplificazione dell'errore. Dovresti calcolarli per le due funzioni $Phi$ che hai scritto ed essendo funzioni della x andrebbero discusse delle argomentazioni che provano che il primo coefficiente è minore dell'altro.
Os. Ma questa compressione della $Phi$ che hai scritto non è a occhio e croce il emtodo di Aitken per l'accelerazione di convergenza?
Guarda, la questione è molto più terra-terra di come l'ho fatta sembrare.
La dispensa che sto leggendo (quella di cui parlavamo qui per il fatto dei rapporti incrementali) dice:
(dopo aver definito $Phi(x)=x-f(x)(x-c)/(f(x)-f(c))=(cf(x)-xf(c))/(f(x)-f(c))$)
"la prima forma è preferibile alla seconda in quanto in quest'ultima potrebbe verificarsi una perdita di cifre significative per differenze di quantità tra loro vicine; ciò non sussiste nella prima in quanto il termine $f(x)(x-c)/(f(x)-f(c))$ è piccolo in confronto a $x$".
Come fa a dire questa cosa?
E inoltre: questa "perdita di cifre significative" che tipo di errore è? Non capisco se sia un errore inerente (cioè dovuto al condizionamento del problema di risolvere una equazione non lineare) o algoritmico. Presumo che sia un errore algoritmico...no?
La dispensa che sto leggendo (quella di cui parlavamo qui per il fatto dei rapporti incrementali) dice:
(dopo aver definito $Phi(x)=x-f(x)(x-c)/(f(x)-f(c))=(cf(x)-xf(c))/(f(x)-f(c))$)
"la prima forma è preferibile alla seconda in quanto in quest'ultima potrebbe verificarsi una perdita di cifre significative per differenze di quantità tra loro vicine; ciò non sussiste nella prima in quanto il termine $f(x)(x-c)/(f(x)-f(c))$ è piccolo in confronto a $x$".
Come fa a dire questa cosa?
E inoltre: questa "perdita di cifre significative" che tipo di errore è? Non capisco se sia un errore inerente (cioè dovuto al condizionamento del problema di risolvere una equazione non lineare) o algoritmico. Presumo che sia un errore algoritmico...no?
Allora, innanzitutto chiariamo una cosa: quando si parla di condizionamento di un problema o di un algoritmo in generale si fa riferimento all'errore inerente. Se si parla di errore algoritmico ciò che stai studiando non è il condizionamento ma la stabilità dell'algoritmo.
Ciò detto, se ho capito cosa vuole dire, la risposta al tuo quesito la puoi vedere bene scrivendo i coefficienti di amplificazione degli errori relativi ai due algoritmi e se vuoi svolgendo l'analisi dell'errore al passo.
Il punto è che il coefficiente di amplificazione dell'errore nella differenza di due numeri è $(x1)/(x1-x2)$ per il pirmo addendo e $-(x2)/(x1-x2)$ per il secondo addendo. Se i due addendi sono molto vicini l'errore può esplodere. Ora in generale questa cosa non ti dice molto, ma prova a confrontare le differenze che vengono effettuate nei due algoritmi. Nel primo fai x meno una cosa molto piccola. Quindi il denominatore del coefficiente di amplificazione sarà un numero molto vicino a x. Nel secondo invece perdi questo vantaggio. Prova a vedere se ciò che ti ho detto ti basta altrimenti proverò a mostrarti i calcoli. Ripeto, credo che facendo una banale analisi in avanti la cosa emerga chiaramente.
Ciò detto, se ho capito cosa vuole dire, la risposta al tuo quesito la puoi vedere bene scrivendo i coefficienti di amplificazione degli errori relativi ai due algoritmi e se vuoi svolgendo l'analisi dell'errore al passo.
Il punto è che il coefficiente di amplificazione dell'errore nella differenza di due numeri è $(x1)/(x1-x2)$ per il pirmo addendo e $-(x2)/(x1-x2)$ per il secondo addendo. Se i due addendi sono molto vicini l'errore può esplodere. Ora in generale questa cosa non ti dice molto, ma prova a confrontare le differenze che vengono effettuate nei due algoritmi. Nel primo fai x meno una cosa molto piccola. Quindi il denominatore del coefficiente di amplificazione sarà un numero molto vicino a x. Nel secondo invece perdi questo vantaggio. Prova a vedere se ciò che ti ho detto ti basta altrimenti proverò a mostrarti i calcoli. Ripeto, credo che facendo una banale analisi in avanti la cosa emerga chiaramente.
Mah, io su questo argomento (analisi degli errori) ho le idee parecchio confuse purtroppo.
Studiando i metodi iterativi in generale ero arrivato a questo risultato: se $Phi$ è (almeno) localmente Lipschitziana con costante di Lipschitz minore di 1, detta $Phi^(**)$ la funzione effettivamente calcolata ad ogni passo, e detto $epsilon$ l'errore massimo ad ogni passo $|Phi(x)-Phi^(**)(x)|
Ma allora perché devo scegliere una espressione invece di un'altra? Quando scelgo la forma "sbagliata", quella con la differenza di quantità vicine, ho capito dal tuo ragionamento che sto introducendo una amplificazione degli errori. Quindi, scegliendo la forma "sbagliata" aumento l'errore trasmesso. Giusto? Ma non avevamo chiuso l'analisi dell'errore trasmesso?
O forse, scegliendo la forma "sbagliata", aumento quell'$epsilon$ di cui sopra?
Studiando i metodi iterativi in generale ero arrivato a questo risultato: se $Phi$ è (almeno) localmente Lipschitziana con costante di Lipschitz minore di 1, detta $Phi^(**)$ la funzione effettivamente calcolata ad ogni passo, e detto $epsilon$ l'errore massimo ad ogni passo $|Phi(x)-Phi^(**)(x)|
Ma allora perché devo scegliere una espressione invece di un'altra? Quando scelgo la forma "sbagliata", quella con la differenza di quantità vicine, ho capito dal tuo ragionamento che sto introducendo una amplificazione degli errori. Quindi, scegliendo la forma "sbagliata" aumento l'errore trasmesso. Giusto? Ma non avevamo chiuso l'analisi dell'errore trasmesso?
O forse, scegliendo la forma "sbagliata", aumento quell'$epsilon$ di cui sopra?
Semplicemente stai parlando di errore algoritmico e non di errore inerente.
Quello che, secondo me, rende una forma preferibile all'altra è il condizionamento quindi l'errore inerente= quanto influisce l'errore del dato iniziale sul risultato.
Il discorso che hai fatto tu risponde invece alla domanda quanto influisce il fatto che il computer fa i conti approssimati sul risultato=errore algoritmico. Mi sono spiegato?
Quello che, secondo me, rende una forma preferibile all'altra è il condizionamento quindi l'errore inerente= quanto influisce l'errore del dato iniziale sul risultato.
Il discorso che hai fatto tu risponde invece alla domanda quanto influisce il fatto che il computer fa i conti approssimati sul risultato=errore algoritmico. Mi sono spiegato?
Vediamo se ho capito. Per un metodo iterativo abbiamo tre errori:
1)inerente ovvero quanto si propaga l'errore sul dato iniziale, si misura con una analisi in avanti;
2)algoritmico ovvero quanto cambia il risultato visto che ad ogni passo l'algortimo introduce errori di calcolo, si misura con una analisi all'indietro;
2)analitico ovvero quanto sbagliamo approssimando un limite di successione con un termine della successione stessa.
Quella che ho fatto prima con $x_n^(**)$ e $Phi^(**)$ è una misura dell'errore algoritmico (analisi all'indietro?).
Quella che viene influenzata dallo scegliere una espressione o l'altra per $Phi$ è la misura dell'errore inerente. Per averne una espressione esplicita dovrei fare una analisi in avanti. (ma in questo caso il dato iniziale qual'è? la funzione $f$ e il punto iniziale $x_0$ suppongo).
Infine, il discorso sul rapporto incrementale che abbiamo fatto l'altra volta serviva in fin dei conti a stimare l'errore analitico.
Noi vogliamo che gli altri errori siano trascurabili in confronto a quest'ultimo. In questo caso diremo che il metodo è stabile.
Ci sono?
1)inerente ovvero quanto si propaga l'errore sul dato iniziale, si misura con una analisi in avanti;
2)algoritmico ovvero quanto cambia il risultato visto che ad ogni passo l'algortimo introduce errori di calcolo, si misura con una analisi all'indietro;
2)analitico ovvero quanto sbagliamo approssimando un limite di successione con un termine della successione stessa.
Quella che ho fatto prima con $x_n^(**)$ e $Phi^(**)$ è una misura dell'errore algoritmico (analisi all'indietro?).
Quella che viene influenzata dallo scegliere una espressione o l'altra per $Phi$ è la misura dell'errore inerente. Per averne una espressione esplicita dovrei fare una analisi in avanti. (ma in questo caso il dato iniziale qual'è? la funzione $f$ e il punto iniziale $x_0$ suppongo).
Infine, il discorso sul rapporto incrementale che abbiamo fatto l'altra volta serviva in fin dei conti a stimare l'errore analitico.
Noi vogliamo che gli altri errori siano trascurabili in confronto a quest'ultimo. In questo caso diremo che il metodo è stabile.
Ci sono?
Ci sei e non ci sei.
Vediamo se riesco a metterla in modo semplice. In caso contrario non farti problemi e chiedi pure.
Innanzitutto le definizioni di errori inerente, algoritmico ed analitico si riferiscono al calcolo di funzioni (o composizioni di funzioni) da parte del calcolatore. Per riferirle ad un algoritmo bisogna fare un po' di considerazioni.
Facciamo un passo indietro e vediamo le definizioni. Supponiamo di voler calcolare una generica funzione $f:RR^n to RR$
Ciò che la nostra macchinetta calcolerà in corrispondenza del dato $(x_1,...,x_n)$ può essere affetto dai seguenti errori:
Errore inerente: E' l'errore generato dalla rappresentazione dei dati $x_1,...,x_n$ come numeri di macchina.
Errore algoritmico: E' l'errore generato dal fatto che le operazioni sono effettuate in aritmetica finita.
Errore analitico: E' l'errore generato dall'approssimazione di f con una funzione razionale.
L'errore analitico subentra solo se la funzione che vogliamo calcolare non è razionale e come vedi non è il tuo caso, dunque non lo considero in quanto segue. Ad esempio se vuoi calcolare la funzione seno con la calcolatrice, la calcolatrice nei suoi chip ha impostato lo sviluppo in serie della funzione seno troncata ad un certo ordine e quello che ti restituisce non è il valore esatto ma un valore affetto da un errore (analitico) più piccolo della precisione di macchina (che in quel caso puoi considerare come il numero di cifre del display della calcolatrice). In altri termini se la calcolatrice visualizza 10 cifre decimali ti fornirà un risultato che dista dal valore esatto di al più $10^(-11)$ e quindi per te non fa alcuna differenza perchè le cifre "sbagliate" non le vedi proprio.
Chiamiamo $barx=(barx_1,...,barx_n)$ il vettore dei dati effettivamente memorizzati in memoria.
Ora l'errore inerente si definisce come $epsilon_(\i\n)=(f(barx)-f(x))/(f(x))$ e si dimostra che vale $epsilon_(\i\n)=sum_{i=1}^nx_i/f(x)epsilon_i(delf(x))/(delx_i)$ con $epsilon_i=(barx_i-x_i)/x_i$. Quindi chiamiamo coefficiente di amplificazione (della funzione f) dell'errore sulla componente i-esima il numero $c_i=x_i/f(x)(delf(x))/(delx_i)$.
Questo è quello che ti interessa per capire l'affermazione che trovi sulla dispensa. Tra poco vediamo perchè.
L'errore algoritmico invece si definisce come $epsilon_(alg)=(psi(barx)-f(barx))/f(barx)$ dove $psi$ è la funzione effettivamente calcolata dalla macchina al posto di f (sempre di funzioni razionali si parla!!!).
Si dimostra che al prim'ordine vale la relazioni $epsilon_(\t\ot)=epsilon_(alg)+epsilon_(\i\n)$.
Allora se vuoi giudicare la bontà di una !!funzione!! numericamente calcolerai l'errore totale, lo dividerai in errore inerente (quello che contiene gli $epsilon_i$) ed errore algoritmico (quello che non li contiene). Se il primo è piccolo/grande in modulo l'algoritmo si dice bencondizionato/malcondizionato, se il secondo è piccolo/grande in modulo l'algoritmo si dice stabile/instabile.
E fin qui niente di complicato.
Ora se scriviamo un algoritmo che consiste in più passi ciascuno corrispondente alla valutazione di una funzione sui dati iniziali e/o sui risultati parziali ottenuti ai passi precedenti la faccenda si fa un po' complicata.
Dovrai fare un'analisi in avanti che credo tu sappia fare.
Ciò che puoi fare nel caso delle tue due "forme" con l'analisi in avanti è stimare l'errore inerente e algoritmico che viene generato ad ogni passo. Ovvero consideri come dati i numeri x,c,f(x),f(c), che saranno affetti da errori che consideri errori iniziali. Fai l'analisi in avanti seguendo i vari passaggi che ti servono a calcolare da questi dati il risultato, cioè il valore dell'iterata in quel passo. Otterrai le indicazioni di errore algoritmico ed errore inerente generati in una generica iterazione.
Se confronti i due errori algoritmici ti accorgerai che uno riesci sempre a limitarlo in modulo con una cosa relativamente piccola. L'altro non riuscirai a limitarlo nel caso che le due quantità di cui si parlava siano molto vicine.
Analisi differente è se vuoi stimare l'errore prodotto da tutto il metodo iterativo.
In tal caso ti conviene usare l'analisi all'indietro. Ma occhio: l'analisi all'indietro è più comoda in questo caso ma ha il difetto che non distingue tra errori algoritmici ed errori inerenti per sua stessa natura: fare l'analisi all'indietro vuol dire partire dal risultato approssimato e tentare di costruire (appunto all'indietro) un dato iniziale (affetto da errore) che usato in aritmetica esatta produrrebbe il risultato di partenza. Ossia tratta l'errore algoritmico come se fosse inerente scaricando le "colpe" della funzione in aritmetica di macchina sui dati iniziali.
La cosa divertente di questa faccenda è che in realtà l'analisi che si fa su un metodo iterativo è completamente differente da quella che si fa per metodi diretti. In realtà tutte queste considerazioni non valgono un ciufolo per il tipo di algoritmo iterativo che stai discutendo. Se vuoi poi ti faccio vedere perchè, ora non voglio mettere troppa carne al fuoco.
Vedi un po' se sono stato abbastanza chiaro e nel caso dimmi cosa non va.
Vediamo se riesco a metterla in modo semplice. In caso contrario non farti problemi e chiedi pure.
Innanzitutto le definizioni di errori inerente, algoritmico ed analitico si riferiscono al calcolo di funzioni (o composizioni di funzioni) da parte del calcolatore. Per riferirle ad un algoritmo bisogna fare un po' di considerazioni.
Facciamo un passo indietro e vediamo le definizioni. Supponiamo di voler calcolare una generica funzione $f:RR^n to RR$
Ciò che la nostra macchinetta calcolerà in corrispondenza del dato $(x_1,...,x_n)$ può essere affetto dai seguenti errori:
Errore inerente: E' l'errore generato dalla rappresentazione dei dati $x_1,...,x_n$ come numeri di macchina.
Errore algoritmico: E' l'errore generato dal fatto che le operazioni sono effettuate in aritmetica finita.
Errore analitico: E' l'errore generato dall'approssimazione di f con una funzione razionale.
L'errore analitico subentra solo se la funzione che vogliamo calcolare non è razionale e come vedi non è il tuo caso, dunque non lo considero in quanto segue. Ad esempio se vuoi calcolare la funzione seno con la calcolatrice, la calcolatrice nei suoi chip ha impostato lo sviluppo in serie della funzione seno troncata ad un certo ordine e quello che ti restituisce non è il valore esatto ma un valore affetto da un errore (analitico) più piccolo della precisione di macchina (che in quel caso puoi considerare come il numero di cifre del display della calcolatrice). In altri termini se la calcolatrice visualizza 10 cifre decimali ti fornirà un risultato che dista dal valore esatto di al più $10^(-11)$ e quindi per te non fa alcuna differenza perchè le cifre "sbagliate" non le vedi proprio.
Chiamiamo $barx=(barx_1,...,barx_n)$ il vettore dei dati effettivamente memorizzati in memoria.
Ora l'errore inerente si definisce come $epsilon_(\i\n)=(f(barx)-f(x))/(f(x))$ e si dimostra che vale $epsilon_(\i\n)=sum_{i=1}^nx_i/f(x)epsilon_i(delf(x))/(delx_i)$ con $epsilon_i=(barx_i-x_i)/x_i$. Quindi chiamiamo coefficiente di amplificazione (della funzione f) dell'errore sulla componente i-esima il numero $c_i=x_i/f(x)(delf(x))/(delx_i)$.
Questo è quello che ti interessa per capire l'affermazione che trovi sulla dispensa. Tra poco vediamo perchè.
L'errore algoritmico invece si definisce come $epsilon_(alg)=(psi(barx)-f(barx))/f(barx)$ dove $psi$ è la funzione effettivamente calcolata dalla macchina al posto di f (sempre di funzioni razionali si parla!!!).
Si dimostra che al prim'ordine vale la relazioni $epsilon_(\t\ot)=epsilon_(alg)+epsilon_(\i\n)$.
Allora se vuoi giudicare la bontà di una !!funzione!! numericamente calcolerai l'errore totale, lo dividerai in errore inerente (quello che contiene gli $epsilon_i$) ed errore algoritmico (quello che non li contiene). Se il primo è piccolo/grande in modulo l'algoritmo si dice bencondizionato/malcondizionato, se il secondo è piccolo/grande in modulo l'algoritmo si dice stabile/instabile.
E fin qui niente di complicato.
Ora se scriviamo un algoritmo che consiste in più passi ciascuno corrispondente alla valutazione di una funzione sui dati iniziali e/o sui risultati parziali ottenuti ai passi precedenti la faccenda si fa un po' complicata.
Dovrai fare un'analisi in avanti che credo tu sappia fare.
Ciò che puoi fare nel caso delle tue due "forme" con l'analisi in avanti è stimare l'errore inerente e algoritmico che viene generato ad ogni passo. Ovvero consideri come dati i numeri x,c,f(x),f(c), che saranno affetti da errori che consideri errori iniziali. Fai l'analisi in avanti seguendo i vari passaggi che ti servono a calcolare da questi dati il risultato, cioè il valore dell'iterata in quel passo. Otterrai le indicazioni di errore algoritmico ed errore inerente generati in una generica iterazione.
Se confronti i due errori algoritmici ti accorgerai che uno riesci sempre a limitarlo in modulo con una cosa relativamente piccola. L'altro non riuscirai a limitarlo nel caso che le due quantità di cui si parlava siano molto vicine.
Analisi differente è se vuoi stimare l'errore prodotto da tutto il metodo iterativo.
In tal caso ti conviene usare l'analisi all'indietro. Ma occhio: l'analisi all'indietro è più comoda in questo caso ma ha il difetto che non distingue tra errori algoritmici ed errori inerenti per sua stessa natura: fare l'analisi all'indietro vuol dire partire dal risultato approssimato e tentare di costruire (appunto all'indietro) un dato iniziale (affetto da errore) che usato in aritmetica esatta produrrebbe il risultato di partenza. Ossia tratta l'errore algoritmico come se fosse inerente scaricando le "colpe" della funzione in aritmetica di macchina sui dati iniziali.
La cosa divertente di questa faccenda è che in realtà l'analisi che si fa su un metodo iterativo è completamente differente da quella che si fa per metodi diretti. In realtà tutte queste considerazioni non valgono un ciufolo per il tipo di algoritmo iterativo che stai discutendo. Se vuoi poi ti faccio vedere perchè, ora non voglio mettere troppa carne al fuoco.
Vedi un po' se sono stato abbastanza chiaro e nel caso dimmi cosa non va.
Alberto, non vorrei sembrarti tarato ma purtroppo stiamo parlando di argomenti di cui storicamente non ho mai capito una mazza ( ](/datas/uploads/forum/emoji/eusa_wall.gif "Brick wall")
) ! Dunque quello che io sapevo, parlando di condizionamento, è che riguarda un problema teorico, non un algoritmo. E quindi col mio cervellino arrivavo a concludere che un errore inerente riguarda solo il problema e non l'algoritmo usato per risolverlo... E' una pu****ata? Forse non proprio, visto che la tua definizione di errore inerente (a proposito: quello è un errore relativo?) $(f(x^**)-f(x))/(f(x))$ mi pare riguardi solo la funzione teorica $f$ e non quella "effettiva" che tu hai chiamato $psi$. (Domanda collaterale: è giusto dire che $psi$ è la funzione perturbata? O si usa un altro termine?)
Forse tu stai parlando di errore inerente relativo al problema: "valutare la funzione $f$ nel punto $x$"? Quindi in pratica, siccome ad ogni passo del mio algoritmo io devo valutare delle funzioni in alcuni punti, ad ogni passo devo fare un'analisi degli errori di tutte le funzioni da valutare? O mi sto incasinando di nuovo?
) ! Dunque quello che io sapevo, parlando di condizionamento, è che riguarda un problema teorico, non un algoritmo. E quindi col mio cervellino arrivavo a concludere che un errore inerente riguarda solo il problema e non l'algoritmo usato per risolverlo... E' una pu****ata? Forse non proprio, visto che la tua definizione di errore inerente (a proposito: quello è un errore relativo?) $(f(x^**)-f(x))/(f(x))$ mi pare riguardi solo la funzione teorica $f$ e non quella "effettiva" che tu hai chiamato $psi$. (Domanda collaterale: è giusto dire che $psi$ è la funzione perturbata? O si usa un altro termine?) Forse tu stai parlando di errore inerente relativo al problema: "valutare la funzione $f$ nel punto $x$"? Quindi in pratica, siccome ad ogni passo del mio algoritmo io devo valutare delle funzioni in alcuni punti, ad ogni passo devo fare un'analisi degli errori di tutte le funzioni da valutare? O mi sto incasinando di nuovo?
"dissonance":
Alberto, non vorrei sembrarti tarato ma purtroppo stiamo parlando di argomenti di cui storicamente non ho mai capito una mazza (
TRANQUILLO! Azzoppandoci la testa capirai. Anch'io ci ho messo un po'. Cmq...hai rivelato la mia identità...
"dissonance":
Dunque quello che io sapevo, parlando di condizionamento, è che riguarda un problema teorico, non un algoritmo. E quindi col mio cervellino arrivavo a concludere che un errore inerente riguarda solo il problema e non l'algoritmo usato per risolverlo... E' una pu****ata?
Più che puttanata direi che è impreciso. La stessa definizione come ti ho detto si può estendere e contrarre a nostro uso e consumo. La vera puttanata è credere che "la matematica non è un opinione". Ci sono scuole, sottoscuole e controscuole.
Io non so di preciso come abbiano posto la questione nel corso che hai seguito te. Però questo sei in grado di vederlo da te...con un po' di flessibilità. Ora al di là dei nomi, c'è una cosa che io chiamo errore inerente che fa riferimento ad una funzione. E che poi si può estendere alla composizione di funzioni e in particolar modo ad un algoritmo (inteso come sequenza di operazioni che matematicamente modelliziamo come composizione di funzioni). Poi se preferisci lo possiamo anche chiamare "pasquale" però la sostanza è quella. Quando riferisci l'errore inerente e quindi il malcondizionamento ad un problema in realtà stai sottintendendo un algoritmo. Quale sia dipende dal senso comune. Ad esempio se dici che la somma di due numeri è malcondizionata, la somma la puoi fare in tanti modi ma ce n'è uno privilegiato e quindi ti stai riferendo implicitamente a quel metodo/algoritmo - occhio i calcolatori eseguono le operazioni elementari con note operazioni sui bit dell'area di memoria in cui risiede il dato e quindi l'algoritmo che usa un computer è diverso da quello che useresti tu per fare 13246+13453123. Inoltre bisognerebbe chiarire il concetto di problema: il problema di sommare due numeri può sembrare chiaro e l'algoritmo viene fuori naturalmente, ma se ti parlassi del problema di interpolazione polinomiale, l'algoritmo non è più così scontato. E se prendi il primo algoritmo/modello che ti viene da pensare ottieni un sistema lineare con matrice malcondizionata. Devi allora pensare ad un altro algoritmo...eccetera eccetera.
Quindi: condizionamento si riferisce ad un algoritmo che serve per risolvere un problema.
condizionamento riferito ad un problema vuol dire condizionamento riferito ad un algoritmo che risolve quel problema e che nel senso comune è privilegiato per risolverlo.
Inoltre ricordati che tra noi matematici la maggiorparte sono quasi analfabeti o usano la lingua italiana in modo pedestre. Non ti meravigliare se certe espressioni di uso comune vengono compresse o dimenticate.
Da "condizionamento dell'algoritmo x per il problema y" a "condizionamento del problema y" si passa in un lampo.
"dissonance":
Forse non proprio, visto che la tua definizione di errore inerente (a proposito: quello è un errore relativo?)
E' un errore relativo. Se consideri solo il numeratore ottieni l'errore assoluto e la tiritela è la stessa. Tieni presente che in generale tutti questi conti e queste analisi sono più agili considerando l'errore relativo rispetto a quello assoluto.
"dissonance":
$(f(x^**)-f(x))/(f(x))$ mi pare riguardi solo la funzione teorica $f$ e non quella "effettiva" che tu hai chiamato $psi$. (Domanda collaterale: è giusto dire che $psi$ è la funzione perturbata? O si usa un altro termine?)
Non lo so, vedi arringa qualche riga più sopra sull'uso del lessico in matematica.
Di nuovo, devi vedere come la chiama colui che ti dovrà firmare il libretto. Poi la puoi chiamare come vuoi, non ci sono standard internazionali. Comunque per il fatto che riguardi la funzione "teorica" è proprio quello il punto: l'errore inerente non di preoccupa di come viene fatto il calcolo (non direttamente) ma di quanto gli errori iniziali vengono amplificati nel calcolo."dissonance":
Forse tu stai parlando di errore inerente relativo al problema: "valutare la funzione $f$ nel punto $x$"? Quindi in pratica, siccome ad ogni passo del mio algoritmo io devo valutare delle funzioni in alcuni punti, ad ogni passo devo fare un'analisi degli errori di tutte le funzioni da valutare? O mi sto incasinando di nuovo?
Vediamo provo a fartici arrivare passo passo, segui questa ricetta
:INGREDIENTI:
x
c
f(x)
f(c) (che sia fresco!)
PREPARAZIONE:
Considera x,c,f(x),f(c) come dei numeri dati, affetti ciascuno da un errore di rappresentazione dato (diciamo che li chiamiamo $epsilon_x,epsilon_c,...$ eccetera ).
Fai l'analisi in avanti (suggerisco di usare un grafo) dei due algoritmi (le due forme) per il calcolo del passo i-esimo del tuo metodo.
Otterrai un'espressione dell'errore totale in cui alcuni termini conterranno gli epsilon di cui sopra e altri no.
Raggruppa i primi e poi i secondi. I primi ti danno la stima dell'errore inerente. Gli altri dell'errore algoritmico (e li buttiamo via perchè non ci interessano).
Posta i risultati e poi ti dico il prossimo passo.
Scusa se forse non sono bravissimo a spiegare...faccio del mio meglio
scusa il ritardo...
Supponiamo di aver calcolato $x_1, ldots, x_n$ (dati esatti), o meglio $x_1+deltax_1. ldots, x_n+deltax_n$ (dati perturbati). Dobbiamo calcolare $x_{n+1}=Phi(x_n)$ ma in realtà calcoleremo $(Phi+deltaPhi)(x_n+deltax_n)$. Adesso bisogna stimare $(|(Phi+deltaPhi)(x_n+deltax_n)-Phi(x_n)|)/(|Phi(x_n)|)$, giusto? A seconda dell'espressione che scegliamo per la $Phi$ dovrei trovarmi qualcosa di diverso. Ho capito almeno come devo impostare il discorso?
Supponiamo di aver calcolato $x_1, ldots, x_n$ (dati esatti), o meglio $x_1+deltax_1. ldots, x_n+deltax_n$ (dati perturbati). Dobbiamo calcolare $x_{n+1}=Phi(x_n)$ ma in realtà calcoleremo $(Phi+deltaPhi)(x_n+deltax_n)$. Adesso bisogna stimare $(|(Phi+deltaPhi)(x_n+deltax_n)-Phi(x_n)|)/(|Phi(x_n)|)$, giusto? A seconda dell'espressione che scegliamo per la $Phi$ dovrei trovarmi qualcosa di diverso. Ho capito almeno come devo impostare il discorso?
Sì, perfetto.
Il passo successivo sarà separare la componente dell'errore che deriva dal $delta x_n$ (inerente) da quella che deriva dal $delta Phi$ (algoritmico).
Il passo successivo sarà separare la componente dell'errore che deriva dal $delta x_n$ (inerente) da quella che deriva dal $delta Phi$ (algoritmico).
Ora che ci penso allora, visto che mi serve una stima dell'errore inerente, posso anche non fare tutto questo ambaradàn e misurare direttamente $(|Phi(x+dx)-Phi(x)|)/(|Phi(x)|)$. In sostanza dico: vediamo come la mia espressione $Phi$ propaga l'errore di rappresentazione che necessariamente introduco sul suo input ($x+dx$ invece di $x$).
E' corretto fare così? Otterrei:
$(|Phi(x+dx)-Phi(x)|)/(|Phi(x)|)=|f(c)*(-dx*f(x)+dx*f(c)+x*f(x+dx)-f(x+dx)*c-x*f(x)+f(x)*c)/((f(x+dx)-f(c))*(x*f(c)-f(x)*c))|$
e poi applicando il fatto che $f(x+dx)~=f(x)+f'(x)dx$
$|f(c)*dx*(-f(x)+f(c)+x*(f'(x))-c*(f'(x)))/((f(x)+(f'(x))*dx-f(c))*(x*f(c)-f(x)*c))|$ (i conti sono fatti con Maple).
Da qua dovrei trovare il modo di ottenere una relazione tipo $<=|dx|*"qualcosa"$. Ma non so se sto facendo qualcosa di utile o solo conti senza senso...
E' corretto fare così? Otterrei:
$(|Phi(x+dx)-Phi(x)|)/(|Phi(x)|)=|f(c)*(-dx*f(x)+dx*f(c)+x*f(x+dx)-f(x+dx)*c-x*f(x)+f(x)*c)/((f(x+dx)-f(c))*(x*f(c)-f(x)*c))|$
e poi applicando il fatto che $f(x+dx)~=f(x)+f'(x)dx$
$|f(c)*dx*(-f(x)+f(c)+x*(f'(x))-c*(f'(x)))/((f(x)+(f'(x))*dx-f(c))*(x*f(c)-f(x)*c))|$ (i conti sono fatti con Maple).
Da qua dovrei trovare il modo di ottenere una relazione tipo $<=|dx|*"qualcosa"$. Ma non so se sto facendo qualcosa di utile o solo conti senza senso...
Dipende da dove arrivi. L'idea che hai scritto è esattamente il senso di quel "coefficiente di amplificazione".
Occhio che la maggiorazione finale sarà
$<=|dx|*|"qualcosa"|<=u*|"qualcosa"|$ dove u è la precisione di macchina.
Il piccolo problema è che in generale la maggiorazione non è elementare e in un certo senso l'uso dei coefficienti di amplificazione ti dà la via "migliore" per ottenere una maggiorazione utile (non troppo larga).
Occhio che la maggiorazione finale sarà
$<=|dx|*|"qualcosa"|<=u*|"qualcosa"|$ dove u è la precisione di macchina.
Il piccolo problema è che in generale la maggiorazione non è elementare e in un certo senso l'uso dei coefficienti di amplificazione ti dà la via "migliore" per ottenere una maggiorazione utile (non troppo larga).
Tempo fa avevo studiato una cosa che chiamavo "indice di condizionamento" di una funzione... in sostanza data una funzione $f$, con la tecnica che ho scritto sopra si otteneva $K(f(x))=(|xf'(x)|)/(|f(x)|)$ Infatti facendo due conti risultava che l'errore inerente sul calcolo della $f$ ($(|f(x+dx)-f(x)|)/(|f(x)|)$) era approssimativamente $dx*K(f(x))$ e sicuramente $<=$ di $K(f(x))*u$ precisione di macchina. E' questo $K$ quello che tu chiami coefficiente di amplificazione?
Comunque, quando ho tempo mi metto a fare due conti, ma c'è una cosa che ancora non mi è chiara, che è un po' quello che non riesco a capire dall'inizio della discussione. E' corretto analizzare gli errori "un pezzo alla volta"?
Comunque, quando ho tempo mi metto a fare due conti, ma c'è una cosa che ancora non mi è chiara, che è un po' quello che non riesco a capire dall'inizio della discussione. E' corretto analizzare gli errori "un pezzo alla volta"?
Sì si tratta proprio del coefficiente di amplificazione (io non ci metto il modulo perchè è più comodo metterlo alla fine ma la sostanza è quella).
Attenzione che quello che hai scritto è vero se f è una funzione unaria. Nel caso di funzioni di più variabili quel K è un vettore, $(K(f(x_1,...,x_n)))_i=x_i/f(x_1,...,x_n)*(delf)/(delx_i)(x_1,....,x_n)$.
Allora l'errore inerente al primo ordine è $$, ove $x=(x_1,...,x_n)$ $dx=(dx_1,...,dx_n)$ eccetera.
Io ti consiglio di farli due conti, per vedere bene come funziona.
Nota: per dx di intende sempre l'errore RELATIVO sul dato x. Per gli errori assoluti la formula è un tantino diversa e un tantino più complicata.
Che cosa intendi per "un pezzo alla volta"?
Attenzione che quello che hai scritto è vero se f è una funzione unaria. Nel caso di funzioni di più variabili quel K è un vettore, $(K(f(x_1,...,x_n)))_i=x_i/f(x_1,...,x_n)*(delf)/(delx_i)(x_1,....,x_n)$.
Allora l'errore inerente al primo ordine è $
Io ti consiglio di farli due conti, per vedere bene come funziona.
Nota: per dx di intende sempre l'errore RELATIVO sul dato x. Per gli errori assoluti la formula è un tantino diversa e un tantino più complicata.
Che cosa intendi per "un pezzo alla volta"?
Allora forse sto iniziando a capire come funziona l'analisi degli errori...! Facendo due conti sulla $Phi$ di prima, quella che il testo dice essere meglio condizionata, e mi pare che si riesca ad arrivare ad una espressione di tipo $"err. relativo della "Phi<="coefficiente di amplificazione della "f*"qualcosa che non esplode"$. Ora, a parte questo caso specifico, una disuguaglianza del genere già sarebbe soddisfacente, perché ci direbbe che la $Phi$ propaga l'errore inerente più o meno come la $f$. Giusto?
Questo intendo dire per "un errore alla volta": adesso stiamo vedendo come $Phi$ propaga l'errore di rappresentazione, ma mica questa è l'unica sorgente di errore. Però, se vediamo che vale la disuguaglianza di prima, allora possiamo non preoccuparci di questo errore: se cresce, sarà perché stiamo considerando una funzione $f$ mal condizionata. E' questa, più o meno, la logica?
Questo intendo dire per "un errore alla volta": adesso stiamo vedendo come $Phi$ propaga l'errore di rappresentazione, ma mica questa è l'unica sorgente di errore. Però, se vediamo che vale la disuguaglianza di prima, allora possiamo non preoccuparci di questo errore: se cresce, sarà perché stiamo considerando una funzione $f$ mal condizionata. E' questa, più o meno, la logica?
Sì ci siamo. Inoltre a te in questo caso non interessa sapere se quella f è mal condizionata. Perchè se la f è malcondizionata allora necessariamente ogni composizione della f sarà malcondizionata.
Se invece la f è ben condizionata ha senso chiedersi se una sua composizione è meglio di un'altra cioè chiedersi quanto l'una o l'altra sono a loro volta ben/mal condizionate.
Per il fatto di un errore alla volta: un errore e basta. Stiamo trattando solo l'errore inerente.
Ps. Prima ti avevo parlato di errore algoritmico perchè quando fai l'analisi dell'errore in avanti non ottieni uno dei due ma la loro somma inerente+algoritmico, quindi dal risultato dell'analisi in avanti devi separare i due pezzi. Invece come hai fatto tu ottieni direttamente solo l'inerente. L'algoritmico non ti interessa. Per ora.
Se invece la f è ben condizionata ha senso chiedersi se una sua composizione è meglio di un'altra cioè chiedersi quanto l'una o l'altra sono a loro volta ben/mal condizionate.
Per il fatto di un errore alla volta: un errore e basta. Stiamo trattando solo l'errore inerente.
Ps. Prima ti avevo parlato di errore algoritmico perchè quando fai l'analisi dell'errore in avanti non ottieni uno dei due ma la loro somma inerente+algoritmico, quindi dal risultato dell'analisi in avanti devi separare i due pezzi. Invece come hai fatto tu ottieni direttamente solo l'inerente. L'algoritmico non ti interessa. Per ora.
"Megan00b":
L'algoritmico non ti interessa. Per ora.
Questo perché adesso devo solo scegliere tra due espressioni, e non stimare l'errore "totale" del mio metodo, vero?
Inoltre, mi pare di capire che l'analisi dell'errore vada a più livelli. In questo caso, se la funzione da valutare è mal condizionata (quindi se amplifica molto l'errore sui dati) allora è inutile che io proceda col mio metodo: sicuramente non andrà bene, devo riformulare il problema. Oppure, se anche la funzione fosse stata ben condizionata ma io stessi cercando di risolvere un problema mal condizionato (che so, cercare uno zero doppio di una funzione reale, o risolvere un sistema lineare con la matrice di Hilbert come coefficienti), lo stesso starei perdendo tempo, perché devo prima riformulare il problema anche qua. (Con "un errore alla volta" stavo cercando di dire questo). E' giusto ragionare così?
Sì hai afferrato il ker della questione:
In questo caso, se la funzione da valutare è mal condizionata (quindi se amplifica molto l'errore sui dati) allora è inutile che io proceda col mio metodo: sicuramente non andrà bene, devo riformulare il problema.
Alé!!! Finalmente inizio a capirci qualcosa... Ma il fatto che l'espressione più compatta per la $Phi$ dà più problemi dell'altra si può vedere anche a occhio? Perché sicuramente l'autore della mia famosa dispensa intendeva dire questo: non c'è neanche bisogno di dimostrare rigorosamente che un'espressione è migliore dell'altra, si vede subito. E da cosa?
P.S.: le espressioni erano $Phi(x)=x-f(x)(x-c)/(f(x)-f(c))=(cf(x)-xf(c))/(f(x)-f(c))$.
P.S.: le espressioni erano $Phi(x)=x-f(x)(x-c)/(f(x)-f(c))=(cf(x)-xf(c))/(f(x)-f(c))$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo