Politecnico di Milano Corso di Analisi e Geometria 1
Federico Lastaria federico.lastaria@polimi.it
Il Metodo di Newton, o delle Tangenti 6 Novembre 2016
Indice
1 Metodo di Newton, o delle tangenti 2
1.1 Il metodo dellle tangenti . . . 2 1.2 Un esempio: calcolo di√2 con l’algoritmo di Erone. . . 5
1
Metodo di Newton, o delle tangenti
`
E spesso utile trovare il valore approssimato, con un alto grado di precisione, di una soluzione di un’equazione. In genere, il metodo di bisezione converge alla soluzione in modo piuttosto lento. Un metodo iterativo che converge in modo molto pi`u rapido si basa sull’idea geometrica di approssimare, a ogni passo, il grafico della funzione per mezzo della retta tangente.
1.1 Il metodo dellle tangenti
Il metodo di Newton – detto anche delle tangenti, di Newton-Fourier, o di Newton-Raphson – `e un metodo iterativo per calcolare gli zeri di una funzione.
Teorema 1.1 (Metodo di Newton, o delle tangenti) Sia [a, b]−→ R una funzione di clas-f se C2[a, b] (vale a dire, derivabile due volte su [a, b], con derivata seconda continua su [a, b]). Facciamo le ipotesi seguenti:
(1) f (a) > 0, f (b) < 0 .
(2) f0(x) < 0 per ogni x in [a, b]. (3) f00(x) > 0 per ogni x in [a, b]. Allora:
(a) Esiste un unico punto x∗∈ (a, b) in cui la funzione f si annulla. (b) La successione x0 = a xn+1 = xn− f (xn) f0(x n) n = 1, 2, ... (1.1) converge al punto x∗.
(c) Esiste una costante K > 0 per la quale si ha, per ogni n ∈ N,
|xn+1− x∗| < K|xn− x∗|2 (1.2) Dimostrazione
(a) (Esistenza e unicit`a della soluzione)
La prima ipotesi (f (a) > 0, f (b) < 0) implica, per il teorema degli zeri, che esiste almeno un punto x∗ in (a, b) per il quale f (x∗) = 0. Per la seconda ipotesi (f0 < 0), la funzione f `e strettamente decrescente. Quindi il punto x∗ in cui la funzione f si annulla `e unico.
(b) (Il metodo iterativo)
Approssimiamo ora il valore x∗. 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:
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) f0(x
0)
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:
x0 = a xn+1 = xn− f (xn) f0(x n) n = 1, 2, ... (1.3)
Dimostriamo che la successione (1.3) converge allo zero x∗ di f .
x0 = a x1 x2 f (x0) f (x1) f (x2) x∗ b
Anzitutto dimostriamo che la successione (1.3) `e crescente e superiormente limitata dal numero x∗: x0< x1< x2 < x3 < · · · < xn< xn+1< · · · < x∗ (1.4) Per cominciare, si ha x0 < x1< x∗ Infatti il punto x1 = x0− f (x0) f0(x 0)
sta alla destra di x0, perch´e il rapporto f (x0)/f0(x0) `e negativo. (Per ipotesi, f (x0) = f (a) > 0 e f0(x0) = f0(a) < 0). D’altra parte si ha x1< x∗. Infatti, poich´e, per l’ipotesi (3) (cio`e, f00> 0) 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. Ora, poich´e
f `e decrescente, f (x1) > 0 e f (x∗) = 0,
si deve avere necessariamente x1 < x∗. In modo simile si prova che ogni termine della successsione xn+1`e maggiore di xne minore di x∗. Dunque la (1.4) `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) f0(x
n)
facciamo tendere n a +∞. Poich´e f e f0 sono continue e f0(x) `e diverso da zero (per ipotesi `e negativo), si ottiene
c∗ = c∗− f (c ∗) f0(c∗)
Dunque f (c∗) = 0. Ma l’unico zero di f `e x∗, quindi c∗= x∗. Abbiamo allora dimostrato che la successione (1.3) converge all’unico zero x∗ della funzione f .
(c) (Dimostrazione della convergenza quadratica) Da xn+1= xn− f (xn) f0(xn) segue, sottraendo x∗, xn+1− x∗= − f (xn) + f0(xn)(x∗− xn) f0(x n) (1.5) Applicando la formula di Taylor sull’intervallo [xn, x∗], con il resto nella forma di Lagrange, si ottiene: 0 = f (x∗) = f (xn) + f0(xn)(x∗− xn) + f00(cn) 2 (x ∗− x n)2 (1.6)
dove cn `e un punto opportuno compreso tra xn e x∗. Da (1.6), si ricava f (xn) + f0(xn)(x∗− xn) = − f00(cn) 2 (x ∗− x n)2 Sostituendo in (1.5), si ha xn+1− x∗ = f00(cn) f0(x n) (x∗− xn)2 2 (1.7)
Se m `e il minimo di |f0| su [a, b] e M `e il massimo di f00 su [a, b], si ottiene la maggiorazione |xn+1− x∗| ≤
M m
|x∗− xn|2
2 (1.8)
(Sicuramente m 6= 0. Infatti, per il teorema di Weierstrass, si ha m = |f0(p)| per un p opportuno in [a, b] e f0(p) < 0, perch´e f0(x) < 0 per ogni x ∈ [a, b]). La disuguaglianza (1.8) dice che l’errore al passo (n + 1)-esimo `e maggiorato dal prodotto di una costante per il quadrato dell’errore
1
commesso al passo precedente. Il procedimento dunque converge molto rapidamente non appena
si abbia |x∗− xn| < 1. 2
Osservazione. (Altre condizioni che garantiscono la validit`a del Metodo di Newton.)
Abbiamo dimostrato la validit`a del metodo delle tangenti di Newton-Fourier nel caso di fun-zioni di classe C2[a, b], con f0 < 0, con f (a) > 0 e f (b) < 0 (e quindi con un unico zero in (a, b)) e con f00> 0. Sostanzialmente nello stesso modo, si dimostra la validit`a del metodo di Newton anche per funzioni di classe C2[a, b] soddisfacenti la condizione f (a)f (b) < 0 (che garantisce l’esistenza di uno zero tra a e b), con f0 < 0 e f00< 0, oppure con f0 > 0 e f00> 0, oppure con f0 > 0 e f00 < 0.
1.2 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 delle tangenti di Newton-Fourier alla funzione f (x) = x2 − 2, ristretta a un intervallo che contenga la radice
√
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 f0(xn) = 2xn, la formula ricorsiva, partendo da x0= 2, `e la seguente: x0 = 2 xn+1 = xn− f (xn) f0(xn) = 1 2 xn+ 2 xn (per n intero ≥ 1.) (1.9) Questa formula coincide, sostanzialmente, con la formula iterativa dell’algoritmo per il calcolo della radice quadrata, attribuito al matematico alessandrino Erone.
