Analisi all'indietro
Ciao a tutti. Perdonate l'ignoranza in materia, ma ci sono metodi generali per fare l'analisi all'indietro di un algoritmo definito "per ricorrenza"?
Chiaro, se si ha un'espressione chiusa l'analisi è estremamente facile, ma in un'espressione del tipo
$f_(k+1) = x_(k+1)f_kg_k$
$g_(k+1) = (f_(k+1)^2 - g_k ^2)/(y_(k+1))$
con $f_0 = g_0 = 1$ (i numeri $x_i$ sono considerati già numeri di macchina per semplicità) trovare un'espressione chiusa è pesante e temo sia inutile.
Se scrivessi un algoritmo che calcola la coppia $(f_n, g_n)$ proprio brutalmente copiando la definizione, come posso fare l'analisi all'indietro? In generale ci sono metodi furbi anche per altri casi?
Mi scuso ancora per l'incapacità!
Chiaro, se si ha un'espressione chiusa l'analisi è estremamente facile, ma in un'espressione del tipo
$f_(k+1) = x_(k+1)f_kg_k$
$g_(k+1) = (f_(k+1)^2 - g_k ^2)/(y_(k+1))$
con $f_0 = g_0 = 1$ (i numeri $x_i$ sono considerati già numeri di macchina per semplicità) trovare un'espressione chiusa è pesante e temo sia inutile.
Se scrivessi un algoritmo che calcola la coppia $(f_n, g_n)$ proprio brutalmente copiando la definizione, come posso fare l'analisi all'indietro? In generale ci sono metodi furbi anche per altri casi?
Mi scuso ancora per l'incapacità!
Risposte
Ciao,
definiscimi "analisi all'indietro".
cosa troveresti alla fine di questa analisi? un'equazione di ricorrenza, una stima asintotica? è questione di terminologia
definiscimi "analisi all'indietro".
cosa troveresti alla fine di questa analisi? un'equazione di ricorrenza, una stima asintotica? è questione di terminologia
Pardon effettivamente sono stato poco chiaro. Intendevo fare un analisi all'indietro dell'ERRORE algoritmico: voglio trovare i dati iniziali a partire dai quali, in aritmetica esatta, si giungerebbe ai risultati effettivamente calcolati con quell'algoritmo (che sono quindi affetti da errori di sorta).
Specifico meglio i dati: si hanno $f_k = f_k(x_1, ..., x_k, y_1, ..., y_(k-1))$ e $g_k = g_k(x_1, ..., x_k, y_1, ..., y_k)$ dove gli $x_i$ e gli $y_i$ sono numeri di macchina che sono i nostri dati. Siccome l'algoritmo calcolerà, per esempio al posto di $f_k$, effettivamente una funzione "perturbata" $\phi_k (x_1, ... , x_k, y_1, ..., y_(k-1))$, voglio trovare di quanto si discostano al massimo degli ipotetici dati iniziali $X_1, ..., X_k, Y_1, ..., Y_(k-1)$ tali che $\phi_k (x_1, ... , x_k, y_1, ..., y_(k-1)) = f_k(X_1, ..., X_k, Y_1, ..., Y_(k-1))$, dai dati iniziali effettivi $x_i$, per ogni $k$.
Spero di essere stato più chiaro!
Specifico meglio i dati: si hanno $f_k = f_k(x_1, ..., x_k, y_1, ..., y_(k-1))$ e $g_k = g_k(x_1, ..., x_k, y_1, ..., y_k)$ dove gli $x_i$ e gli $y_i$ sono numeri di macchina che sono i nostri dati. Siccome l'algoritmo calcolerà, per esempio al posto di $f_k$, effettivamente una funzione "perturbata" $\phi_k (x_1, ... , x_k, y_1, ..., y_(k-1))$, voglio trovare di quanto si discostano al massimo degli ipotetici dati iniziali $X_1, ..., X_k, Y_1, ..., Y_(k-1)$ tali che $\phi_k (x_1, ... , x_k, y_1, ..., y_(k-1)) = f_k(X_1, ..., X_k, Y_1, ..., Y_(k-1))$, dai dati iniziali effettivi $x_i$, per ogni $k$.
Spero di essere stato più chiaro!
intuitivamente ho capito cosa cerchi di fare.
Una cosa che di sicuro ti serve sapere è l'algoritmo che utilizzi.
Non puoi risalire ai tuoi dati di input dall'output se non conosci che modifiche sono state fatte ai dati.
Un esempio sono le black box crittografiche, dall'output non puoi risalire all'input.
E' questo che intendi?
Una cosa che di sicuro ti serve sapere è l'algoritmo che utilizzi.
Non puoi risalire ai tuoi dati di input dall'output se non conosci che modifiche sono state fatte ai dati.
Un esempio sono le black box crittografiche, dall'output non puoi risalire all'input.
E' questo che intendi?
Non ho capito una cosa: tu conosci la $f_k$ o no?
@Hamming_Burst: Certamente bisogna conoscere l'algoritmo... infatti io ho scritto che voglio farlo "brutalmente copiando la definizione" e forse non sono stato molto chiaro:
$f_0 = g_0 = 1$,
poi si calcola $f_1 = x_1 f_0 g_0 = x_1$ poi si calcola $g_1 = (f_1^2 - g_0 ^2)/(y_1) = (x_1^2 - 1)/(y_1)$ in cui si intende che si fanno prima gli elevamenti a potenza, poi la sottrazione, poi la divisione (ma se volete usare un altro algoritmo siete liberi di farlo ovviamente, l'analisi all'indietro risulterà diversa ma questo non è importante: ho bisogno di un aiuto su uno qualsiasi degli algoritmi); poi si calcola $f_2$, poi $g_2$ eccetera... fino ad arrivare a $f_n$ e $g_n$
@Deckard: f_k è definita per ricorrenza a partire dalle f più basse, quindi a rigore sì, la conosco. Non conosco un'espressione chiusa per essa, ed è proprio questo il problema: se la conoscessi, la mia analisi all'indietro dell'errore algoritmico sarebbe facile. Io sto chiedendo se qualcuno conosce un metodo per fare questa analisi semplicemente conoscendo la relazione ricorsiva.
$f_0 = g_0 = 1$,
poi si calcola $f_1 = x_1 f_0 g_0 = x_1$ poi si calcola $g_1 = (f_1^2 - g_0 ^2)/(y_1) = (x_1^2 - 1)/(y_1)$ in cui si intende che si fanno prima gli elevamenti a potenza, poi la sottrazione, poi la divisione (ma se volete usare un altro algoritmo siete liberi di farlo ovviamente, l'analisi all'indietro risulterà diversa ma questo non è importante: ho bisogno di un aiuto su uno qualsiasi degli algoritmi); poi si calcola $f_2$, poi $g_2$ eccetera... fino ad arrivare a $f_n$ e $g_n$
@Deckard: f_k è definita per ricorrenza a partire dalle f più basse, quindi a rigore sì, la conosco. Non conosco un'espressione chiusa per essa, ed è proprio questo il problema: se la conoscessi, la mia analisi all'indietro dell'errore algoritmico sarebbe facile. Io sto chiedendo se qualcuno conosce un metodo per fare questa analisi semplicemente conoscendo la relazione ricorsiva.
Esempio chiarificatore: se volessi fermarmi a n=1 farei
$f_1 = x_1$ non è affetto da errori algoritmici.
$g_1 = (((x_1)^2 (1+\delta_1) - 1)(1+\delta_2))/(y_1) (1+\delta_3) = ([x_1(1+1/2 \delta_1)]^2 - 1)/(y_1(1-\delta_2-\delta_3))$, i vari $\delta$ sono gli errori locali delle varie operazioni, e l'uguaglianza è un'uguaglianza al prim'ordine.
Ottengo così una $g_1(X_1, Y_1)$ dove $X_1 = x_1(1+1/2 \delta_1)$ e $Y_1 = y_1(1-\delta_1 - \delta_2)$, quindi la perturbazione del dato iniziale $x_1$ è in modulo minore o uguale a $1/2 u$, dove u è la precisione di macchina, mentre la perturbazione del dato iniziale $y_1$ è in modulo minore o uguale a $2u$.
Spero che ora sia chiaro!
$f_1 = x_1$ non è affetto da errori algoritmici.
$g_1 = (((x_1)^2 (1+\delta_1) - 1)(1+\delta_2))/(y_1) (1+\delta_3) = ([x_1(1+1/2 \delta_1)]^2 - 1)/(y_1(1-\delta_2-\delta_3))$, i vari $\delta$ sono gli errori locali delle varie operazioni, e l'uguaglianza è un'uguaglianza al prim'ordine.
Ottengo così una $g_1(X_1, Y_1)$ dove $X_1 = x_1(1+1/2 \delta_1)$ e $Y_1 = y_1(1-\delta_1 - \delta_2)$, quindi la perturbazione del dato iniziale $x_1$ è in modulo minore o uguale a $1/2 u$, dove u è la precisione di macchina, mentre la perturbazione del dato iniziale $y_1$ è in modulo minore o uguale a $2u$.
Spero che ora sia chiaro!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo