Induzione al contrario (dimostrare per n-1)?
Salve a tutti avrei una piccola domandina, alla quale mi sono parzialmente risposto da solo ma vorrei una conferma.
In una dimostrazione su un libro sto leggendo:
Abbiamo la stima $|\epsilon_{n+1}| <= (1+hL)|\epsilon_n| + 1/2 h^2 M $
e "una semplice induzione mostra che"
$|\epsilon_{n}| <= (1+hL)^n |\epsilon_0| + 1/2 h^2 M \sum_{k=0}^{n-1} (1+hL)^k $
Che è vero "Se vede"
Però mi sfugge il ragionamento rigoroso per arrivarci.
Il principio di induzione l'ho capito, ma io l'ho sempre visto dimostrando la proprietà per n+1 partendo da n
In questo caso è al contrario, partendo da n dimostri n-1 fino a 0.
Mi delucidate su questo argomento per piacere? Grazie!
In una dimostrazione su un libro sto leggendo:
Abbiamo la stima $|\epsilon_{n+1}| <= (1+hL)|\epsilon_n| + 1/2 h^2 M $
e "una semplice induzione mostra che"
$|\epsilon_{n}| <= (1+hL)^n |\epsilon_0| + 1/2 h^2 M \sum_{k=0}^{n-1} (1+hL)^k $
Che è vero "Se vede"
Però mi sfugge il ragionamento rigoroso per arrivarci.
Il principio di induzione l'ho capito, ma io l'ho sempre visto dimostrando la proprietà per n+1 partendo da n
In questo caso è al contrario, partendo da n dimostri n-1 fino a 0.
Mi delucidate su questo argomento per piacere? Grazie!
Risposte
Che io sappia esistono solo 2 modi in cui si fa l'induzione:
- [*:2dsncpqx]\(\displaystyle n \) implica \(\displaystyle n+1 \),[/*:m:2dsncpqx][*:2dsncpqx]\(\displaystyle 1,\dotsc, n-1 \) implica \(\displaystyle n \)[/*:m:2dsncpqx][/list:u:2dsncpqx]
Anche perché entrambi permettono di aumentare il numero di valori che soddisfano la condizione all'infinito. Per quanto riguarda invece il caso \(\displaystyle n \) implica \(\displaystyle n-1 \) l'unica cosa che riesci a dimostrare è che esiste se esiste un \(\displaystyle n \) per cui vale allora vale anche per ogni numero inferiore.
Certo magari unito a qualche proprietà asintotica potrebbe funzionare ma non sono convinto. Per comprendere mi sa che devi mettere un po' più contesto e qualche riga in più.
oh pardon mi ero dimenticato il modulo a $\epsilon_{n-1}$ e a $\epsilon_{n}$
ho editato il primo post.
No guarda, il contesto non c'entra: Tutto quello che basta per la domanda è in quello che ho scritto.
Il contesto è la stima di un resto di un metodo numerico per un'equazione differenziale.
ho editato il primo post.
No guarda, il contesto non c'entra: Tutto quello che basta per la domanda è in quello che ho scritto.
Il contesto è la stima di un resto di un metodo numerico per un'equazione differenziale.
Non è affatto vero che il contesto non conta; anche se conta di più il fatto che la relazione era tra \(\displaystyle \epsilon \) consecutivi. In ogni caso non è a rigore una dimostrazione per induzione. Nel senso che tu semplicemente dici che vale una formula ricorsiva e quindi sostituisci in modo da trovare una formula che dipenda solo da \(\displaystyle \epsilon_0 \). Dopo di che usi eventualmente una dimostrazione per induzione per dimostrare l'equivalenza di quest'ultimo con un'altra.
Come dice bene vict, dipende dal contesto, e su che basi poggi la tua "induzione al contrario".
Se intendi la classica induzione matematica, che si insegna in ogni dove, non ci son altri punti di vista oltre quelli elencati. Ci sono parecchie altre forme di induzione che si basano su particolari insiemi, assiomi od altro, perciò se la tua domanda va fuori l'induzione classica (sui numeri naturali, per intenderci), sii più chiaro.
Se intendi la classica induzione matematica, che si insegna in ogni dove, non ci son altri punti di vista oltre quelli elencati. Ci sono parecchie altre forme di induzione che si basano su particolari insiemi, assiomi od altro, perciò se la tua domanda va fuori l'induzione classica (sui numeri naturali, per intenderci), sii più chiaro.
ok, aggiungo dettagli.
Riporto pari pari quello che dice il libro.
Però non inizio dall'inizio della dimostrazione perchè sarebbe un po' lungo da scrivere.
$\epsilon_n$ indica l'errore globale al passo n del metodo numerico per risolvere l'ODE.
Arriviamo a dire che
$\epsilon_{n+1} = \epsilon_n + h(f(x_n , y(x_n)) - f(x_n , y_n)) +1/2 h^2 y''(\xi)$
"Assumiamo che f soddisfi la condizione di Lipschitz con la costante di Lipschitz $L$ e che esista una costante $M < \infty$ tale che $|y''(x)|<= M$ per ogni x nell'intervallo dove vogliamo cercare la soluzione dell'ODE.
Allora possiamo stimare
$|\epsilon_{n+1}| <= (1+hL)|\epsilon_n| + 1/2 h^2 M $
E una semplice induzione mostra che
$|\epsilon_{n}| <= (1+hL)^n |\epsilon_0| + 1/2 h^2 M \sum_{k=0}^{n-1} (1+hL)^k $
Eccetera eccetera...
è più chiaro?
Ripeto... che è giusto si vede... ma quello che mi interesserebbe è come ci si arriva in modo rigoroso.
Riporto pari pari quello che dice il libro.
Però non inizio dall'inizio della dimostrazione perchè sarebbe un po' lungo da scrivere.
$\epsilon_n$ indica l'errore globale al passo n del metodo numerico per risolvere l'ODE.
Arriviamo a dire che
$\epsilon_{n+1} = \epsilon_n + h(f(x_n , y(x_n)) - f(x_n , y_n)) +1/2 h^2 y''(\xi)$
"Assumiamo che f soddisfi la condizione di Lipschitz con la costante di Lipschitz $L$ e che esista una costante $M < \infty$ tale che $|y''(x)|<= M$ per ogni x nell'intervallo dove vogliamo cercare la soluzione dell'ODE.
Allora possiamo stimare
$|\epsilon_{n+1}| <= (1+hL)|\epsilon_n| + 1/2 h^2 M $
E una semplice induzione mostra che
$|\epsilon_{n}| <= (1+hL)^n |\epsilon_0| + 1/2 h^2 M \sum_{k=0}^{n-1} (1+hL)^k $
Eccetera eccetera...
è più chiaro?
Ripeto... che è giusto si vede... ma quello che mi interesserebbe è come ci si arriva in modo rigoroso.
"boulayo":
Salve a tutti avrei una piccola domandina, alla quale mi sono parzialmente risposto da solo ma vorrei una conferma.
In una dimostrazione su un libro sto leggendo:
Abbiamo la stima $|\epsilon_{n+1}| <= (1+hL)|\epsilon_n| + 1/2 h^2 M $
e "una semplice induzione mostra che"
$|\epsilon_{n}| <= (1+hL)^n |\epsilon_0| + 1/2 h^2 M \sum_{k=0}^{n-1} (1+hL)^k $
Che è vero "Se vede"
Però mi sfugge il ragionamento rigoroso per arrivarci.
Il principio di induzione l'ho capito, ma io l'ho sempre visto dimostrando la proprietà per n+1 partendo da n
In questo caso è al contrario, partendo da n dimostri n-1 fino a 0.
Ma quale "induzione al contrario"?!?
L'induzione si usa sempre allo stesso modo (i.e. \(\mathcal{P} (n)\Rightarrow \mathcal{P} (n+1)\) oppure \(\mathcal{P} (1),\ldots ,\mathcal{P} (n-1)\Rightarrow \mathcal{P} (n)\)).
Tuttavia la dimostrazione per induzione ha il grave difetto di non essere costruttiva, nel senso che per dimostrare induttivamente una formula \(\mathcal{P} (n)\), beh, quella stessa formula la si deve già avere sotto mano.
Il più delle volte, la formula \(\mathcal{P} (n)\) da dimostrare per induzione si ricava con altri metodi.
In questo caso, si ragiona "ad occhio" andando all'indietro.
Si ha:
\[
\tag{1} |\varepsilon_{n+1}| \leq (1+h\ L)|\varepsilon_n| + \frac{1}{2} h^2\ M
\]
e, sostituendo \(n-1\) al posto di \(n\) in (1), risulta pure:
\[
\tag{2} |\varepsilon_n| \leq (1+h\ L)|\varepsilon_{n-1}| + \frac{1}{2} h^2\ M \; ;
\]
infilando (2) in (1) si trova:
\[
\tag{3} \begin{split}
|\varepsilon_{n+1}| &\leq (1+h\ L) \left( (1+h\ L)|\varepsilon_{n-1}| + \frac{1}{2} h^2\ M \right) + \frac{1}{2} h^2\ M \\
&= (1+h\ L)^2\ |\varepsilon_{n-1}| + \left( (1+h\ L) +1\right)\ \frac{1}{2}\ h^2\ M\; .
\end{split}
\]
Riscrivendo (1) con \(n-2\) al posto di \(n\), si trova:
\[
\tag{4} |\varepsilon_{n-1}|\leq (1+h\ L)|\varepsilon_{n-2}| + \frac{1}{2} h^2\ M
\]
ed infilando (4) nell'ultimo membro di (3) si trova:
\[
\tag{5} \begin{split}
|\varepsilon_{n+1}| &\leq (1+h\ L)^2\ \left( (1+h\ L)|\varepsilon_{n-2}| + \frac{1}{2} h^2\ M \right) + \left( (1+h\ L) +1\right)\ \frac{1}{2}\ h^2\ M\\
&= (1+h\ L)^3 |\varepsilon_{n-2}| + \left( (1+h\ L)^2 +(1+h\ L)+1\right)\ \frac{1}{2}\ h^2\ M
\end{split}
\]
Guarda ora la (1), la (3) e la (5): nota che:
[*:1k0y2yt8] la somma degli esponenti delle potenze di \(1+h\ L\) e degli indici di \(\varepsilon\) che figurano come primi addendi negli ultimi membri delle tre relazioni forniscono esattamente \(n+1\) (infatti essi sono, nell'ordine, \(1,\ n\), \(2,\ n-1\) e \(3,\ n-2\));
[/*:m:1k0y2yt8]
[*:1k0y2yt8] l'indice di \(\varepsilon\) negli ultimi membri decresce di un'unità ad ogni iterazione;
[/*:m:1k0y2yt8]
[*:1k0y2yt8] il numero di potenze successive di \(1+h\ L\) che figurano nei secondi addendi degli ultimi membri delle tre relazioni cresce di un'unità ad ogni iterazione è esattamente uguale al sottraendo nell'indice del \(\varepsilon\) che figura al primo addendo.[/*:m:1k0y2yt8][/list:u:1k0y2yt8]
Per la seconda osservazione è chiaro che dopo \(n\) iterazioni del metodo, nel maggiorante figurerà il valore \(\varepsilon_0\); ma allora per le rimanenti due osservazioni si trova che l'esponente della potenza di \(1+h\ L\) che moltiplica \(\varepsilon_0\) sarà \(n+1\) e che al secondo addendo figureranno tutte le potenze successive di \(1+h\ L\) fino a quella 'esponente uguale ad \(n\) (poiché \(0=n-n\)). Quindi:
\[
|\varepsilon_{n+1}|\leq (1+h\ L)^{n+1} |\varepsilon_0| + \frac{1}{2}\ h^2\ M\ \sum_{i=0}^n (1+h\ L)^i
\]
è la tua \(\mathcal{P} (n)\).
Ora devi dimostrare che \(\mathcal{P} (n)\) è effettivamente valida per ogni \(n\) e ciò si fa per induzione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo