Principio di induzione - stima errore calcolo radice quadrata
Considerando l'algoritmo di Erone per calcolare la $sqrt(x)$
abbiamo: $ a_(n+1)=1/2(a_n+x/a_n)$
$a_n>sqrt(x)$
$x/a_n
ESPRESSIONE 1 $ a_(n+1)=1/2(a_n+x/a_n)<1/2(a_n+sqrt(x))$
ESPRESSIONE 2 $ a_(n+1)-sqrt(x)<1/2(a_n-sqrt(x))$
STIMA dell'errore: la differenza $a_(n+1)-sqrt(x)$ si stima con l'errore iniziale $a_1-sqrt(x)$ nel modo seguente:
$ a_(n+1)-sqrt(x)<1/2^n(a_1-sqrt(x))$
DIMOSTRAZIONE basata sul principio di induzione:
il testo in mio possesso dice:
ponendo $n=1$ la tesi (cioè l'espr.2) è verificata poiché coincide con l'espr. 1, quando nella espr. 1 si sia posto $n=1$.
Domanda 1: non dovrebbe essere "quando nella espr. 2 si sia posto $n=1$" ? E' forse uno sbaglio di stampa?
Poi si dice di prendere l'espr. 2 come ipotesi (quindi immagino supposta vera per un certo $n$)
Prosegue dicendo: per l'espr 1 sostituendo con $n+1$ al posto di $n$ si ha:
$ a_(n+2)-sqrt(x)<1/2(a_(n+1)-sqrt(x))<1/2*1/2^n(a_1-sqrt(x))=1/2^(n+1)(a_1-sqrt(x))$
Domanda 2: non capisco come dimostrare questa disuguaglianza:
$1/2(a_(n+1)-sqrt(x))<1/2*1/2^n(a_1-sqrt(x))$
cioè come si fa a dire che il secondo membro è più grande del primo. Capisco che $a1>a_(n+1)$ ma c'e' in gioco anche $2^n$ che mi mette in confusione e non mi permette di valutare la disuguaglianza.
Grazie
abbiamo: $ a_(n+1)=1/2(a_n+x/a_n)$
$a_n>sqrt(x)$
$x/a_n
ESPRESSIONE 1 $ a_(n+1)=1/2(a_n+x/a_n)<1/2(a_n+sqrt(x))$
ESPRESSIONE 2 $ a_(n+1)-sqrt(x)<1/2(a_n-sqrt(x))$
STIMA dell'errore: la differenza $a_(n+1)-sqrt(x)$ si stima con l'errore iniziale $a_1-sqrt(x)$ nel modo seguente:
$ a_(n+1)-sqrt(x)<1/2^n(a_1-sqrt(x))$
DIMOSTRAZIONE basata sul principio di induzione:
il testo in mio possesso dice:
ponendo $n=1$ la tesi (cioè l'espr.2) è verificata poiché coincide con l'espr. 1, quando nella espr. 1 si sia posto $n=1$.
Domanda 1: non dovrebbe essere "quando nella espr. 2 si sia posto $n=1$" ? E' forse uno sbaglio di stampa?
Poi si dice di prendere l'espr. 2 come ipotesi (quindi immagino supposta vera per un certo $n$)
Prosegue dicendo: per l'espr 1 sostituendo con $n+1$ al posto di $n$ si ha:
$ a_(n+2)-sqrt(x)<1/2(a_(n+1)-sqrt(x))<1/2*1/2^n(a_1-sqrt(x))=1/2^(n+1)(a_1-sqrt(x))$
Domanda 2: non capisco come dimostrare questa disuguaglianza:
$1/2(a_(n+1)-sqrt(x))<1/2*1/2^n(a_1-sqrt(x))$
cioè come si fa a dire che il secondo membro è più grande del primo. Capisco che $a1>a_(n+1)$ ma c'e' in gioco anche $2^n$ che mi mette in confusione e non mi permette di valutare la disuguaglianza.
Grazie
Risposte
Inserisco la seguente immagine:
dalla quale si evince che $[a_(n+1)-sqrt(2)<1/2(a_n-sqrt(2))]$
Ebbene, si deve dimostrare che $[a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))]$
Ponendo $n=1$ si ottiene $[a_2-sqrt(2)<1/2(a_1-sqrt(2))]$ che coincide con $[a_(n+1)-sqrt(2)<1/2(a_n-sqrt(2))]$ per $n=1$
Non rimane che dimostrare $[a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))] rarr [a_(n+2)-sqrt(2)<1/2^(n+1)(a_1-sqrt(2))]$
Ponendo $n=n+1$ in $[a_(n+1)-sqrt(2)<1/2(a_n-sqrt(2))]$ si ottiene $[a_(n+2)-sqrt(2)<1/2(a_(n+1)-sqrt(2))]$
Quindi: $\{(a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))),(a_(n+2)-sqrt(2)<1/2(a_(n+1)-sqrt(2))):} rarr a_(n+2)-sqrt(2)<1/2*1/2^n(a_1-sqrt(2))=1/2^(n+1)(a_1-sqrt(2))$
dalla quale si evince che $[a_(n+1)-sqrt(2)<1/2(a_n-sqrt(2))]$
Ebbene, si deve dimostrare che $[a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))]$
Ponendo $n=1$ si ottiene $[a_2-sqrt(2)<1/2(a_1-sqrt(2))]$ che coincide con $[a_(n+1)-sqrt(2)<1/2(a_n-sqrt(2))]$ per $n=1$
Non rimane che dimostrare $[a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))] rarr [a_(n+2)-sqrt(2)<1/2^(n+1)(a_1-sqrt(2))]$
Ponendo $n=n+1$ in $[a_(n+1)-sqrt(2)<1/2(a_n-sqrt(2))]$ si ottiene $[a_(n+2)-sqrt(2)<1/2(a_(n+1)-sqrt(2))]$
Quindi: $\{(a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))),(a_(n+2)-sqrt(2)<1/2(a_(n+1)-sqrt(2))):} rarr a_(n+2)-sqrt(2)<1/2*1/2^n(a_1-sqrt(2))=1/2^(n+1)(a_1-sqrt(2))$
"anonymous_0b37e9":
Quindi: $ \{(a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))),(a_(n+2)-sqrt(2)<1/2(a_(n+1)-sqrt(2))):} rarr a_(n+2)-sqrt(2)<1/2*1/2^n(a_1-sqrt(2)) $
Sicuramente per voi sarà banale ma purtroppo non ho ancora chiaro il passaggio evidenziato.
La prima disuguaglianza tra parentesi graffe rappresenta l'uguaglianza da dimostrare mentre la seconda quella ottenuta sostituendo ad $n=n+1$
Non capisco i criteri che portano a generare la disuguaglianza a destra della freccetta, cioè il simbolo "implica"...
Assolutamente no. La prima disuguaglianza:
$a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))$
è vera per ipotesi (principio di induzione). La seconda disuguaglianza:
$a_(n+2)-sqrt(2)<1/2(a_(n+1)-sqrt(2))$
è vera perchè dimostrata nell'immagine inserita con $n$ sostituito da $n+1$.
$a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))$
è vera per ipotesi (principio di induzione). La seconda disuguaglianza:
$a_(n+2)-sqrt(2)<1/2(a_(n+1)-sqrt(2))$
è vera perchè dimostrata nell'immagine inserita con $n$ sostituito da $n+1$.
Perfettamente d'accordo su come si arriva alle due diseguaglianze prima citate (che sono raccolte nelle graffe) niente da eccepire. Mi sono espresso male ma ciò che non capisco è come si arriva dalle due espressioni alla seguente:
$rarr a_(n+2)−sqrt(2)<1/2*1/2^n(a1−sqrt(2))$
Cioè come si fa a dire che $a_(n+2)−sqrt(2)$ è minore di quella quantità ?!
$rarr a_(n+2)−sqrt(2)<1/2*1/2^n(a1−sqrt(2))$
Cioè come si fa a dire che $a_(n+2)−sqrt(2)$ è minore di quella quantità ?!
Poichè:
$a_(n+2)-sqrt(2)<1/2(a_(n+1)-sqrt(2))$
e, a sua volta:
$a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))$
sostituendo la seconda nella prima, a maggior ragione non può che essere:
$a_(n+2)-sqrt(2)<1/2*1/2^n(a_1-sqrt(2))$
$a_(n+2)-sqrt(2)<1/2(a_(n+1)-sqrt(2))$
e, a sua volta:
$a_(n+1)-sqrt(2)<1/2^n(a_1-sqrt(2))$
sostituendo la seconda nella prima, a maggior ragione non può che essere:
$a_(n+2)-sqrt(2)<1/2*1/2^n(a_1-sqrt(2))$
A volte abbiamo formule così banali davanti gli occhi ma non ne cogliamo il senso e rimaniamo ciechi.
di nuovo grazie per la disponibilità e pazienza
di nuovo grazie per la disponibilità e pazienza
Capita a tutti. Ad ogni modo, il tuo voler comprendere la dimostrazione è la cosa più importante. 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo