Iterazione di Newton per il reciproco

Testo

Mostrare che il metodo di Newton applicato a $f(x)=\dfrac{1}{x}-a$ produce l’iterazione $x_{n+1}=x_n(2-ax_n),$ un algoritmo per il reciproco $1/a$ che non usa divisioni (era impiegato dai vecchi calcolatori).

Soluzione

La funzione $f(x)=\dfrac{1}{x}-a$ ha derivata $f'(x)=-\dfrac{1}{x^2}$. L’iterazione di Newton è $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{\frac{1}{x_n}-a}{-\frac{1}{x_n^2}}.$ Il quoziente si semplifica moltiplicando numeratore e denominatore per $-x_n^2$: $x_{n+1} = x_n + x_n^2\!\left(\frac{1}{x_n}-a\right) = x_n + x_n - a x_n^2 = \boxed{x_n(2-ax_n)}.$ Lo zero di $f$ è $x=1/a$, quindi l’iterazione converge al reciproco di $a$. La formula usa solo moltiplicazioni e una sottrazione: nessuna divisione, motivo per cui veniva usata nell’hardware che non disponeva di un’unità di divisione.

Collegamenti

Argomenti: Continuita
Concetti: Metodo di newton raphson
Metodi: Newton raphson
Competenze: Dimostrare · Usare formule
Tipo di esercizio: Dimostrazione