Metodo di Newton, metodo delle secanti e ordine di convergenza

In questa pagina 5

Prerequisiti: Metodo di bisezione e iterazioni di punto fisso (iterazioni $x_{k+1} = g(x_k)$ e convergenza lineare), Formula di Taylor con resto di Lagrange, Derivata - definizione e significato (retta tangente).

La bisezione converge sempre, ma lentamente (un bit per passo). Per avere molte cifre in poche iterazioni si sfrutta la forma della funzione vicino alla radice: la sua derivata.

Ordine di convergenza

Sia $x_k \to \alpha$ e $e_k = x_k - \alpha$ .

Definizione (ordine di convergenza). La successione converge con ordine $p \ge 1$ e costante asintotica $C$ se $\lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^p} = C, \qquad 0 < C < \infty \quad(\text{con } C<1 \text{ se } p=1).$

$p = 1$ : convergenza lineare (tasso $C$ ): l'errore si moltiplica per $C$ a ogni passo (bisezione: $C=\frac12$ ; punto fisso: $C = |g'(\alpha)|$ ).

$p = 2$ : convergenza quadratica. Se $|e_k| \approx 10^{-s}$ allora $|e_{k+1}| \approx C\,10^{-2s}$ : il numero di cifre corrette raddoppia a ogni iterazione.

$1<p<2$ : convergenza superlineare.

Perché conta: da un errore di $10^{-1}$ per arrivare a $10^{-16}$ servono circa $16$ iterazioni lineari con tasso $0{,}1$ , ma solo $4$ iterazioni quadratiche ( $10^{-1} \to 10^{-2} \to 10^{-4} \to 10^{-8} \to 10^{-16}$ ).

Stima numerica dell'ordine. Da $|e_{k+1}| \approx C|e_k|^p$ e $|e_k| \approx C|e_{k-1}|^p$ , dividendo, $p \approx \frac{\ln\left(|e_{k+1}|/|e_k|\right)}{\ln\left(|e_k|/|e_{k-1}|\right)}.$ Se $\alpha$ non è noto si usano gli incrementi $|x_{k+1}-x_k|$ al posto degli errori (per un metodo superlineare l'incremento $|x_{k+1}-x_k| \approx |e_k|$ ).

Il metodo di Newton

Idea. In $x_k$ si sostituisce $f$ con la sua retta tangente $y = f(x_k) + f'(x_k)(x - x_k)$ e si prende come nuova approssimazione lo zero della tangente: $0 = f(x_k) + f'(x_k)(x_{k+1} - x_k) \quad\Longrightarrow\quad \boxed{x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}}$ È un'iterazione di punto fisso con $g(x) = x - \frac{f(x)}{f'(x)}$ (richiede $f'(x_k) \ne 0$ ).

Grafico interattivo: Newton per f(x) = x² − 2 da x₀ = 2: la tangente in x₀ taglia l'asse in x₁ = 1,5, quella in x₁ in x₂ = 1,4167

Teorema (convergenza locale quadratica). Sia $f \in C^2$ in un intorno di $\alpha$ , con $f(\alpha) = 0$ e $f'(\alpha) \ne 0$ (radice semplice). Allora esiste $\delta > 0$ tale che per ogni $x_0$ con $|x_0 - \alpha| < \delta$ il metodo di Newton converge ad $\alpha$ e $\lim_{k\to\infty}\frac{e_{k+1}}{e_k^2} = \frac{f''(\alpha)}{2f'(\alpha)}.$ L'ordine è $2$ se $f''(\alpha) \ne 0$ (se $f''(\alpha) = 0$ l'ordine è maggiore).

Dimostrazione. Per Taylor con resto di Lagrange (Formula di Taylor con resto di Lagrange) centrato in $x_k$ : $0 = f(\alpha) = f(x_k) + f'(x_k)(\alpha - x_k) + \frac{f''(\xi_k)}{2}(\alpha - x_k)^2,\quad \xi_k \text{ tra } x_k \text{ e } \alpha.$ Dividendo per $f'(x_k)$ e portando i primi due termini a sinistra: $\underbrace{x_k - \frac{f(x_k)}{f'(x_k)}}_{x_{k+1}} - \alpha = \frac{f''(\xi_k)}{2f'(x_k)}(x_k - \alpha)^2 \quad\Longrightarrow\quad e_{k+1} = \frac{f''(\xi_k)}{2f'(x_k)}\,e_k^2.$ Poiché $f'(\alpha) \ne 0$ e $f'$ è continua, in un intorno $|f'| \ge m > 0$ e $|f''| \le M$ , quindi $|e_{k+1}| \le \frac{M}{2m}e_k^2$ . Se $|e_0| < \delta := \min\{\text{raggio dell'intorno},\ \frac{m}{M}\}$ allora $|e_1| \le \frac{M}{2m}|e_0|\cdot|e_0| < \frac12|e_0|$ e per induzione l'errore tende a zero (superlinearmente). Passando al limite ( $\xi_k \to \alpha$ , $x_k\to\alpha$ ) si ottiene la costante ∎.

Si vede anche da $g(x) = x - \frac{f}{f'}$ : $g' = \frac{f f''}{f'^2}$ e $g'(\alpha) = 0$ , quindi il tasso lineare è nullo (vedi la nota sul punto fisso) e la convergenza è più che lineare.

Esempio 1: radice di $2$ (metodo di Erone)

$f(x) = x^2 - 2$ , $f' = 2x$ : $x_{k+1} = x_k - \frac{x_k^2 - 2}{2x_k} = \dfrac12\left(x_k + \dfrac{2}{x_k}\right)$ . Da $x_0 = 1$ : la costante attesa è $\frac{f''}{2f'} = \frac{2}{2\cdot 2\sqrt2} = \frac{1}{2\sqrt2} = 0{,}35355$ .

$k$	$x_k$	$e_k = x_k - \sqrt2$	$e_k / e_{k-1}^2$
$0$	$1$	$-4{,}14\cdot 10^{-1}$
$1$	$\frac32 = 1{,}5$	$+8{,}58\cdot 10^{-2}$	$0{,}5000$
$2$	$\frac{17}{12} = 1{,}416667$	$+2{,}45\cdot 10^{-3}$	$0{,}3333$
$3$	$\frac{577}{408} = 1{,}414215686$	$+2{,}12\cdot 10^{-6}$	$0{,}3529$
$4$	$1{,}414213562375$	$+1{,}60\cdot 10^{-12}$	$0{,}3535$

(Ad esempio $x_1 = \frac12(1 + 2) = 1{,}5$ e $x_2 = \frac12\left(1{,}5 + \frac{2}{1{,}5}\right) = \frac12(1{,}5 + 1{,}3333) = 1{,}41667$ .) Le cifre corrette passano da $0$ a $1$ , $2$ , $5$ , $11$ : raddoppiano. Il rapporto $e_k/e_{k-1}^2$ tende a $0{,}3535$ . Stima dell'ordine con $e_1, e_2, e_3, e_4$ : $p \approx \frac{\ln(e_4/e_3)}{\ln(e_3/e_2)} = \frac{\ln(7{,}5\cdot 10^{-7})}{\ln(8{,}66\cdot 10^{-4})} = \frac{-14{,}10}{-7{,}05} = 2{,}00$ .

Esempio 2: $x^3 - x - 2 = 0$ da $x_0 = 1{,}5$

$f' = 3x^2 - 1$ . Costante attesa: $\frac{f''(\alpha)}{2f'(\alpha)} = \frac{6\alpha}{2(3\alpha^2 - 1)} = \frac{9{,}1283}{11{,}8876} = 0{,}7679$ .

$k$	$x_k$	$f(x_k)$	$f'(x_k)$	$e_k$	$e_k/e_{k-1}^2$
$0$	$1{,}5$	$-0{,}1250$	$5{,}7500$	$-2{,}14\cdot 10^{-2}$
$1$	$1{,}5217391$	$+2{,}137\cdot 10^{-3}$	$5{,}9471$	$+3{,}59\cdot 10^{-4}$	$0{,}786$
$2$	$1{,}52137981$	$+5{,}89\cdot 10^{-7}$	$5{,}9438$	$+9{,}92\cdot 10^{-8}$	$0{,}768$
$3$	$1{,}5213797068$	$+4{,}5\cdot 10^{-14}$	$5{,}9438$	$+7{,}6\cdot 10^{-15}$	$0{,}768$

Per esempio $x_1 = 1{,}5 - \frac{-0{,}125}{5{,}75} = 1{,}5 + 0{,}0217391 = 1{,}5217391$ . Confronto: per $x^3 - x - 2$ con precisione $10^{-10}$ servono $33$ passi di bisezione, $11$ di punto fisso con $\sqrt[3]{x+2}$ e $4$ di Newton.

Criteri di arresto

Dato che $e_{k+1} \ll e_k$ , si ha $|x_{k+1} - x_k| \approx |e_k|$ : l'incremento è una buona stima dell'errore del passo precedente, e l'errore di $x_{k+1}$ è molto più piccolo. Un criterio tipico è $|x_{k+1} - x_k| \le \text{tol}\,\max(1,|x_{k+1}|)$ più un numero massimo di iterazioni.

Quando Newton fallisce o rallenta

$f'(x_k) = 0$ o molto piccola: la tangente è orizzontale e il passo è enorme o indefinito.
$x_0$ lontano da $\alpha$ : la convergenza è solo locale. Per $f(x) = x^3 - 2x + 2$ da $x_0 = 0$ : $f(0) = 2$ , $f'(0) = -2$ , $x_1 = 0 + 1 = 1$ ; $f(1) = 1$ , $f'(1) = 1$ , $x_2 = 0$ . L'iterazione cicla $0 \to 1 \to 0 \to \ldots$ senza mai arrivare alla radice $\alpha \approx -1{,}77$ . Per $f(x) = \arctan x$ (radice $0$ ) da $x_0 = 1{,}5$ : $x_1 = -1{,}694$ , $x_2 = 2{,}321$ , $x_3 = -5{,}114$ , $x_4 = 32{,}3\ldots$ diverge, mentre da $x_0 = 1{,}3$ converge ( $-1{,}16;\ 0{,}859;\ -0{,}374;\ 0{,}034;\ -2{,}6\cdot 10^{-5}$ ). Rimedio pratico: partire da un'approssimazione ottenuta con qualche passo di bisezione.
Radici multiple: se $f(\alpha) = f'(\alpha) = 0$ il teorema non vale.

Radici multiple

Se $\alpha$ ha molteplicità $m \ge 2$ , cioè $f(x) = (x-\alpha)^m h(x)$ con $h(\alpha) \ne 0$ , Newton converge ma solo linearmente, con tasso $\frac{m-1}{m}$ .

Verifica per $f(x) = (x-1)^m$ : $\frac{f}{f'} = \frac{x-1}{m}$ , quindi $e_{k+1} = e_k - \frac{e_k}{m} = \frac{m-1}{m}e_k$ .

Esempio. $f(x) = (x-1)^2(x+2)$ ha una radice doppia in $1$ . Da $x_0 = 2$ Newton dà $x_1 = 2 - \frac{f(2)}{f'(2)} = 2 - \frac49 = 1{,}5556$ ( $f(2) = 4$ , $f'(2) = 2\cdot1\cdot 4 + 1 = 9$ ), poi $1{,}2979,\ 1{,}1554,\ 1{,}0796,\ 1{,}0403,\ 1{,}0203,\ 1{,}0102$ , con errori $0{,}556,\ 0{,}298,\ 0{,}155,\ 0{,}080,\ 0{,}040,\ 0{,}020,\ 0{,}010$ e rapporto $e_{k}/e_{k-1} \to 0{,}5 = \frac{2-1}{2}$ .

Newton modificato: se si conosce $m$ , $x_{k+1} = x_k - m\dfrac{f(x_k)}{f'(x_k)}$ ripristina la convergenza quadratica. Per l'esempio con $m = 2$ : $x_1 = 2 - 2\cdot\frac49 = 1{,}1111$ , $x_2 = 1{,}0019493$ , $x_3 = 1{,}0000006327$ , $x_4 = 1{,}0000000000$ (errori $0{,}111,\ 1{,}95\cdot10^{-3},\ 6{,}3\cdot10^{-7},\ 6{,}7\cdot10^{-14}$ ). Una radice multipla è anche mal condizionata (vedi Condizionamento di un problema e stabilità di un algoritmo): oltre una certa precisione contano solo gli arrotondamenti.

Il metodo delle secanti

Newton richiede $f'$ , che può essere costosa o non disponibile. Si sostituisce $f'(x_k)$ con il rapporto incrementale sugli ultimi due punti: $\boxed{x_{k+1} = x_k - f(x_k)\,\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}}$ Geometricamente $x_{k+1}$ è lo zero della secante per $(x_{k-1}, f(x_{k-1}))$ e $(x_k, f(x_k))$ (la retta che interpola $f$ in due punti, vedi Interpolazione polinomiale - forma di Lagrange, differenze divise ed errore). Servono due valori iniziali $x_0, x_1$ e una sola valutazione di $f$ per passo.

Ordine. L'errore di interpolazione fornisce $e_{k+1} \approx \frac{f''(\alpha)}{2f'(\alpha)}\,e_k\,e_{k-1}.$ (Il prodotto $e_ke_{k-1}$ è l'errore del polinomio di interpolazione in $\alpha$ : $\omega(\alpha) = (\alpha-x_k)(\alpha-x_{k-1})$ .) Se $|e_{k+1}| \approx A|e_k|^p$ , allora $|e_{k-1}| \approx (|e_k|/A)^{1/p}$ e la relazione diventa $A|e_k|^p \approx C|e_k|^{1+1/p}\,A^{-1/p}$ , quindi $p = 1 + \frac1p \iff p^2 - p - 1 = 0 \iff p = \frac{1+\sqrt5}{2} \approx 1{,}618,$ il rapporto aureo. Convergenza superlineare ma non quadratica.

Dalla stessa relazione si ricava anche la costante asintotica nel senso della definizione: uguagliando i coefficienti, $A = C\,A^{-1/p}$ , cioè $A^{1+1/p} = A^{p} = C$ (perché $1 + \frac1p = p$ ), quindi $\lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^{1{,}618}} = A = \left|\frac{f''(\alpha)}{2f'(\alpha)}\right|^{1/p} = \left|\frac{f''(\alpha)}{2f'(\alpha)}\right|^{0{,}618}.$ Attenzione a non confondere le due costanti: $C = \left|\frac{f''}{2f'}\right|$ è quella del prodotto $e_ke_{k-1}$ , $A = C^{0{,}618}$ è quella rispetto a $|e_k|^{p}$ .

Efficienza. Per valutazione di $f$ (supponendo $f'$ costosa quanto $f$ ): Newton usa $2$ valutazioni per passo e ordine $2$ , cioè $2^{1/2} = 1{,}41$ "ordine per valutazione"; le secanti $1$ valutazione e ordine $1{,}618$ , cioè $1{,}618$ . Quando $f'$ è costosa conviene la secante.

Esempio svolto: $x^3 - x - 2 = 0$ con $x_0 = 1$ , $x_1 = 2$ . $f(1) = -2$ , $f(2) = 4$ .

$x_2 = 2 - 4\cdot\frac{2-1}{4-(-2)} = 2 - \frac46 = 1{,}33333$ .
$f(x_2) = 2{,}37037 - 1{,}33333 - 2 = -0{,}96296$ .
$x_3 = x_2 - f(x_2)\,\dfrac{x_2 - x_1}{f(x_2) - f(x_1)}$ . Il rapporto vale $\dfrac{1{,}33333 - 2}{-0{,}96296 - 4} = \dfrac{-0{,}66667}{-4{,}96296} = 0{,}134328$ , e quindi $x_3 = 1{,}33333 - (-0{,}96296)(0{,}134328) = 1{,}33333 + 0{,}12935 = 1{,}46269$ .

$k$	$x_k$	$e_k$
$0$	$1$	$-5{,}21\cdot 10^{-1}$
$1$	$2$	$+4{,}79\cdot 10^{-1}$
$2$	$1{,}3333333$	$-1{,}88\cdot 10^{-1}$
$3$	$1{,}4626866$	$-5{,}87\cdot 10^{-2}$
$4$	$1{,}5311694$	$+9{,}79\cdot 10^{-3}$
$5$	$1{,}5209264$	$-4{,}53\cdot 10^{-4}$
$6$	$1{,}5213763$	$-3{,}39\cdot 10^{-6}$
$7$	$1{,}5213797080$	$+1{,}18\cdot 10^{-9}$
$8$	$1{,}5213797068$	$-3{,}1\cdot 10^{-15}$

La costante $\frac{e_{k+1}}{e_ke_{k-1}}$ si stabilizza attorno a $0{,}76$ (teorica $0{,}7679$ ), e gli ordini stimati sono $1{,}5$ – $1{,}7$ , compatibili con $1{,}618$ . Il rapporto $\frac{|e_{k+1}|}{|e_k|^{1{,}618}}$ oscilla invece tra $0{,}81$ e $0{,}87$ , attorno al valore teorico $A = 0{,}7679^{0{,}618} = 0{,}849$ . Servono $8$ passi (8 valutazioni di $f$ oltre alle due iniziali) contro i $4$ passi di Newton (4 valutazioni di $f$ più 4 di $f'$ ).

Codice

python

import math

def newton(f, df, x0, tol=1e-12, nmax=50):
    x = x0
    for k in range(1, nmax + 1):
        dx = f(x) / df(x)
        x -= dx
        if abs(dx) <= tol * max(1.0, abs(x)):
            return x, k
    return x, nmax

def secanti(f, x0, x1, tol=1e-12, nmax=50):
    for k in range(1, nmax + 1):
        x2 = x1 - f(x1) * (x1 - x0) / (f(x1) - f(x0))
        if abs(x2 - x1) <= tol * max(1.0, abs(x2)):
            return x2, k
        x0, x1 = x1, x2
    return x1, nmax

f = lambda x: x**3 - x - 2
df = lambda x: 3 * x**2 - 1
print(newton(f, df, 1.5))
print(secanti(f, 1.0, 2.0))

x, e = 1.0, []                         # radice di 2 con Newton: x -> (x + 2/x)/2
for _ in range(4):
    x = (x + 2 / x) / 2
    e.append(abs(x - math.sqrt(2)))
for k in range(1, 4):
    print(k, e[k] / e[k-1]**2)         # e_{k+1}/e_k^2 -> 1/(2 sqrt 2) = 0.3535...
print(math.log(e[3] / e[2]) / math.log(e[2] / e[1]))   # ordine stimato

Output:

(1.5213797068045676, 4)
(1.5213797068045676, 8)
1 0.33333333333330084
2 0.35294117643144196
3 0.35352238456116425
1.999766671041752

In MATLAB: fzero(@(x) x^3-x-2, 1.5) combina bisezione, secanti e interpolazione inversa; il metodo di Newton si scrive in un ciclo con la derivata analitica; fsolve per sistemi.

Errori tipici

Dimenticare di verificare $f'(\alpha) \neq 0$ : con radici multiple il metodo è lineare, non quadratico.
Applicare la costante $\frac{f''}{2f'}$ con i valori in $x_k$ invece che in $\alpha$ , o scambiarla con $|g'(\alpha)|$ (che è nullo).
Dire che "Newton converge sempre": è un metodo locale; $x_0$ va scelto vicino alla radice.
Calcolare l'ordine delle secanti come $2$ : è $1{,}618$ .
Usare un incremento piccolo come criterio senza controllare $|f'|$ nella zona (radici quasi multiple).

Domande d'esame

Definire l'ordine di convergenza di un metodo iterativo. Risposta: $p$ tale che $|e_{k+1}|/|e_k|^p \to C \in\,]0,\infty[$ .
Dimostrare che Newton ha ordine $2$ per una radice semplice. Risposta: Taylor di $f$ centrato in $x_k$ calcolata in $\alpha$ , dividere per $f'(x_k)$ : $e_{k+1} = \frac{f''(\xi_k)}{2f'(x_k)}e_k^2$ .
Cosa succede a Newton con una radice di molteplicità $m$ ? Risposta: convergenza lineare con tasso $\frac{m-1}{m}$ ; con $x - m f/f'$ torna quadratica.
Perché le secanti hanno ordine $\frac{1+\sqrt5}{2}$ ? Risposta: $e_{k+1} \approx C e_ke_{k-1}$ implica $p = 1 + \frac1p$ .

Versione ripasso

Ordine $p$ : $\frac{|e_{k+1}|}{|e_k|^p}\to C$ ; $p=1$ lineare (tasso $C<1$ ), $p=2$ quadratica (cifre corrette raddoppiano), $1<p<2$ superlineare. Stima: $p\approx\frac{\ln(|e_{k+1}|/|e_k|)}{\ln(|e_k|/|e_{k-1}|)}$ , con gli incrementi se $\alpha$ è ignoto.

Newton: $x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$ (zero della tangente; punto fisso con $g=x-\frac f{f'}$ , $g'(\alpha)=\frac{ff''}{f'^2}=0$ ).

Teorema: $f\in C^2$ , $f(\alpha)=0$ , $f'(\alpha)\ne0$ $\Rightarrow$ convergenza locale, $\frac{e_{k+1}}{e_k^2}\to\frac{f''(\alpha)}{2f'(\alpha)}$ (Formula di Taylor con resto di Lagrange).
Dimostrazione: $0=f(x_k)+f'(x_k)(\alpha-x_k)+\frac{f''(\xi)}2(\alpha-x_k)^2$ , si divide per $f'(x_k)$ : $e_{k+1}=\frac{f''(\xi_k)}{2f'(x_k)}e_k^2$ ; $|e_{k+1}|\le\frac M{2m}e_k^2$ con $\delta=\min\{\cdot,\frac mM\}$ .
$\sqrt2$ (Erone $x\to\frac12(x+\frac2x)$ ) da $1$ : $1,\ \frac32,\ \frac{17}{12},\ \frac{577}{408}$ ; errori $-0{,}414,\ 8{,}6\cdot10^{-2},\ 2{,}5\cdot10^{-3},\ 2{,}1\cdot10^{-6},\ 1{,}6\cdot10^{-12}$ ; $\frac{e_k}{e_{k-1}^2}=0{,}500,\ 0{,}333,\ 0{,}353,\ 0{,}3535\to\frac1{2\sqrt2}$ ; $p\approx2{,}00$ .
$x^3-x-2$ da $1{,}5$ : $x_1=1{,}5+\frac{0{,}125}{5{,}75}=1{,}5217391$ , errori $-2{,}1\cdot10^{-2},\ 3{,}6\cdot10^{-4},\ 9{,}9\cdot10^{-8},\ 7{,}6\cdot10^{-15}$ , costante $\frac{6\alpha}{2(3\alpha^2-1)}=0{,}7679$ ; $4$ passi contro $11$ (punto fisso) e $33$ (bisezione) per $10^{-10}$ .
Arresto: $|x_{k+1}-x_k|\approx|e_k|$ (metodo superlineare).

Fallimenti: $f'(x_k)=0$ ; $x_0$ lontano: $x^3-2x+2$ da $0$ cicla $0\to1\to0$ ; $\arctan x$ da $1{,}5$ diverge ( $-1{,}694,\ 2{,}321,\ -5{,}114,\ 32{,}3$ ), da $1{,}3$ converge.

Radici multiple ( $f=(x-\alpha)^mh$ ): Newton lineare con tasso $\frac{m-1}m$ (per $(x-1)^m$ : $e_{k+1}=\frac{m-1}me_k$ ). $(x-1)^2(x+2)$ da $2$ : $1{,}5556,\ 1{,}2979,\ 1{,}1554,\ \dots$ , rapporto $\to0{,}5$ . Modificato $x-m\frac f{f'}$ ( $m=2$ ): $1{,}1111,\ 1{,}0019493,\ 1{,}0000006327$ (quadratico). Radici multiple mal condizionate.

Secanti: $x_{k+1}=x_k-f(x_k)\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}$ (zero della retta per due punti, Interpolazione polinomiale - forma di Lagrange, differenze divise ed errore); $e_{k+1}\approx\frac{f''}{2f'}e_ke_{k-1}$ , quindi $p=1+\frac1p$ , $p=\frac{1+\sqrt5}2=1{,}618$ , con costante asintotica $\frac{|e_{k+1}|}{|e_k|^p}\to\left|\frac{f''}{2f'}\right|^{1/p}$ ( $0{,}849$ per $x^3-x-2$ ); una valutazione di $f$ per passo (efficienza $1{,}618$ contro $\sqrt2=1{,}41$ di Newton).

$x^3-x-2$ con $x_0=1$ , $x_1=2$ : $x_2=2-\frac46=1{,}33333$ , $f(x_2)=-0{,}96296$ , $x_3=1{,}46269$ , $1{,}53117,\ 1{,}52093,\ 1{,}521376,\ 1{,}52137971$ ; $8$ passi; $\frac{e_{k+1}}{e_ke_{k-1}}\approx0{,}76$ (teorica $0{,}7679$ ).
MATLAB: fzero, fsolve.

Passaggi principali.

Perché le cifre raddoppiano: $|e_k|\approx10^{-s}\Rightarrow|e_{k+1}|\approx C\,10^{-2s}$ ; da $10^{-1}$ a $10^{-16}$ servono $4$ passi quadratici ( $10^{-1},10^{-2},10^{-4},10^{-8},10^{-16}$ ) contro $16$ lineari con tasso $0{,}1$ .
Costante di Newton per $x^2-2$ : $\frac{f''}{2f'}=\frac{2}{2\cdot2\sqrt2}=0{,}35355$ ; per $x^3-x-2$ : $\frac{6\alpha}{2(3\alpha^2-1)}=\frac{9{,}1283}{11{,}8876}=0{,}7679$ .
Primo passo di Erone: $x_1=\frac12(1+2)=1{,}5$ , $x_2=\frac12(1{,}5+\frac2{1{,}5})=\frac12(1{,}5+1{,}3333)=1{,}41667$ .
Secanti, relazione tra gli ordini: $|e_{k-1}|\approx(|e_k|/A)^{1/p}$ inserito in $A|e_k|^p\approx C|e_k||e_{k-1}|$ dà l'esponente $1+\frac1p$ , cioè $p^2-p-1=0$ .
Il prodotto $e_ke_{k-1}$ viene dall'errore di interpolazione lineare in $\alpha$ , $\omega(\alpha)=(\alpha-x_k)(\alpha-x_{k-1})$ .
Secanti sul cubico: errori $-0{,}521,\ +0{,}479,\ -0{,}188,\ -5{,}87\cdot10^{-2},\ +9{,}79\cdot10^{-3},\ -4{,}53\cdot10^{-4},\ -3{,}39\cdot10^{-6},\ +1{,}18\cdot10^{-9}$ .
Criterio d'arresto per Newton: $|x_{k+1}-x_k|\le\text{tol}\,\max(1,|x_{k+1}|)$ più un numero massimo di iterazioni.

Errori tipici: supporre $f'(\alpha)\ne0$ senza controllare; confondere $C$ con $|g'(\alpha)|$ (nullo); "Newton converge sempre"; ordine delle secanti $2$ .

Esercizi su questo argomento

Teoria collegata

Metodo di bisezione e iterazioni di punto fisso