Indice - Politecnico di Milano

Politecnico di Milano. Scuola di Ingegneria Industriale e dell’Informazione.
Corso di Analisi e Geometria 1
7. Il metodo di Newton-Fourier o delle tangenti
(Docente: Federico Lastaria)
Novembre 2014
Indice
1 Metodo di Newton-Fourier o delle tangenti
2
1.1
Il metodo dellle tangenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2
Dimostrazione della convergenza quadratica . . . . . . . . . . . . . . . . . . . . .
√
Un esempio: calcolo di 2 con l’algoritmo di Erone . . . . . . . . . . . . . . . . .
4
1.3
1
4
1
Metodo di Newton-Fourier o delle tangenti
1.1
Il metodo dellle tangenti
Il metodo di Newton, detto anche di Newton-Fourier o delle tangenti, `e un metodo iterativo per
calcolare gli zeri di una funzione.
f
Sia [a, b] −→ R una funzione di classe C 2 [a, b], vale a dire derivabile due volte su [a, b], con
derivata seconda continua. Facciamo le ipotesi seguenti:
1. f (a) > 0, f (b) < 0 .
2. f 0 (x) < 0 per ogni x in [a, b].
3. f 00 (x) > 0 .
La prima ipotesi implica, per il teorema degli zeri, l’esistenza di almeno un punto c in (a, b) nel
quale f (c) = 0. Per la seconda ipotesi, la funzione f `e strettamente decrescente. Quindi il punto
c in cui la funzione f si annulla `e unico. Infine la terza ipotesi dice che la funzione f `e convessa.
Questo significa che il grafico di f sta tutto al di sopra di ogni retta tangente al grafico stesso.
Vogliamo trovare il valore c. L’idea del metodo `e la seguente. Partiamo dal valore x0 = a e
consideriamo la retta tangente al grafico di f nel punto di ascissa x0 :
y − f (x0 ) = f 0 (x0 )(x − x0 )
Denotiamo con x1 l’ascissa del punto in cui tale retta tangente interseca l’asse delle x. Ponendo
y = 0 nell’equazione della retta tangente scritta sopra, si ricava:
x1 = x0 −
f (x0 )
f 0 (x0 )
Adesso iteriamo il procedimento: per ogni n = 1, 2, 3, ... chiamiamo xn+1 l’ascissa del punto in
cui la tangente al grafico di f nel punto di ascissa xn interseca l’asse delle x. Si ottiene in questo
modo la successione ricorsiva:

= a
 x0
f (xn )
(1.1)
n = 1, 2, ...
 xn+1 = xn − 0
f (xn )
Dimostriamo che la successione (1.1) converge allo zero c di f .
2
f (x0 )
f (x1 )
x0 = a
x1
f (x2 )
c
x2
b
Anzitutto dimostriamo che la successione (1.1) `e crescente e superiormente limitata dal numero
c:
x0 < x1 < x2 < x3 < · · · < xn < xn+1 < · · · < c
(1.2)
Per cominciare, si ha
x0 < x1 < c
Infatti il punto
x1 = x0 −
f (x0 )
f 0 (x0 )
sta alla destra di x0 , perch´e il rapporto f (x0 )/f 0 (x0 ) `e negativo. (Per ipotesi, f (x0 ) e f 0 (x0 )
hanno segni opposti). D’altra parte si ha x1 < c. Infatti, poich´e f `e convessa, il suo grafico sta
tutto al di sopra della retta tangente (chiamiamola T0 ) nel punto di ascissa x0 . In particolare,
l’ordinata f (x1 ) - calcolata al di sopra del punto x1 sul grafico di f - `e maggiore del valore
dell’ordinata calcolata, in corrispondenza di x1 , sulla retta tangente T0 , valore che `e uguale a
zero. Dunque f (x1 ) > 0. Siccome f `e decrescente, f (x1 ) > 0 e f (c) = 0, si deve avere x1 < c.
In modo simile si prova che ogni termine della successsione xn+1 `e maggiore di xn e minore di
c. Dunque la 1.2 `e dimostrata. Siccome in R le successioni crescenti e limitate convergono1 , si
ha che la successione (xn ) tende a un limite, che chiameremo c∗ . In
xn+1 = xn −
f (xn )
f 0 (xn )
facciamo tendere n a +∞. Poich´e f e f 0 sono continue e f 0 (x) `e diverso da zero (per ipotesi `e
negativo), si ottiene
f (c∗ )
c∗ = c∗ − 0 ∗
f (c )
1
Si tratta di una propriet`
a equivalente all’assioma di completezza di R.
3
Dunque f (c∗ ) = 0. Ma l’unico zero di f `e c, quindi c∗ = c. Abbiamo allora dimostrato che la
successione (1.1) converge allo zero c della funzione f .
1.2
Dimostrazione della convergenza quadratica
Da
xn+1 = xn −
segue, sottraendo c,
xn+1 − c = −
f (xn )
f 0 (xn )
f (xn ) + f 0 (xn )(c − xn )
f 0 (xn )
(1.3)
Applicando la formula di Taylor, con centro nel punto xn e con il resto nella forma di Lagrange,
si ottiene:
f 00 (η)
f (c) = f (xn ) + f 0 (xn )(c − xn ) +
(c − xn )2
(1.4)
2
dove η `e un punto opportuno compreso tra xn e c. Siccome f (c) = 0, si ha
f (xn ) + f 0 (xn )(c − xn ) = −
f 00 (η)
(c − xn )2
2
Sostituendo in 1.6, si ha
xn+1 − c =
f 00 (η) (c − xn )2
f 0 (xn )
2
(1.5)
Se m `e il minimo di |f 0 | su [a, b] e M `e il massimo di f 00 su [a, b], si ottiene la maggiorazione
|xn+1 − c| ≤
M (c − xn )2
m
2
(1.6)
(Sicuramente m 6= 0. Infatti, per il teorema di Weierstrass, si ha m = |f 0 (p)| per un p opportuno
e f 0 (p) < 0 per l’ipotesi su f 0 ). Questa disuguaglianza dice che l’errore al passo (n + 1)-esimo
`e maggiorato dal quadrato dell’errore commesso al passo precedente. Il procedimento dunque
converge molto rapidamente non appena si abbia |c − xn | < 1.
1.3
Un esempio: calcolo di
√
2 con l’algoritmo di Erone
√
Il numero 2 `e la radice positiva dell’equazione x2 − 2 = 0. Applichiamo allora il metodo
di Newton-Fourier
delle tangenti alla funzione f (x) = x2 − 2 in un intervallo che contenga il
√
numero 2, ad esempio l’intervallo [1, 2]. In questo caso, la funzione f `e crescente e convessa
sull’intervallo [1, 2]. Poich´e f (xn ) = x2n − 2 e f 0 (xn ) = 2xn , la formula ricorsiva, partendo da
x0 = 2, `e la seguente:

= 2
 x0
f (xn )
1
2
(1.7)
=
n = 1, 2, ...
xn +
 xn+1 = xn − 0
f (xn )
2
xn
Questa formula coincide con la formula iterativa dell’algoritmo del matematico alessandrino
Erone.
4

Download Report