Algoritmo di bisezione

Il teorema degli zeri garantisce che una soluzione esiste, ma non dove: gli algoritmi numerici la trovano per approssimazioni successive. La bisezione dimezza l’intervallo a ogni passo (robusta ma lenta); il metodo di Newton-Raphson usa la derivata per convergere molto più in fretta (veloce ma delicato).

• Algoritmo di bisezione
• Il metodo di Newton-Raphson
• Calcolo di radici con Newton
• Newton contro bisezione e casi di fallimento

The zero theorem guarantees that a solution exists, but not where: numerical algorithms find it by successive approximations. Bisection halves the interval at each step (robust but slow); the Newton-Raphson method uses the derivative to converge much faster (fast but delicate).

• Bisection algorithm
• The Newton-Raphson method
• Computing roots with Newton
• Newton versus bisection and cases of failure

Il teorema degli zeri non dice dove sta lo zero, solo che esiste. L’algoritmo di bisezione lo trova per approssimazioni successive, dimezzando l’intervallo a ogni passo.

In sintesi — Procedimento

1. Partire da $[a,b]$ con $f(a)\cdot f(b)<0$.
2. Calcolare il punto medio $m = \dfrac{a+b}{2}$ e il segno di $f(m)$.
3. Se $f(a)\cdot f(m) < 0$: lo zero sta in $[a,m]$, pongo $b=m$. Altrimenti sta in $[m,b]$, pongo $a=m$.
4. Ripetere dal passo 2 finché $|b-a|<\varepsilon$ (la precisione desiderata).

A ogni passo l’intervallo si dimezza: dopo $n$ passi l’errore è $\le\dfrac{b-a}{2^n}$.

Esempio — Bisezione applicata a $\ln(x+3)-3x+0{,}1=0$

Sia $f(x) = \ln(x+3)-3x+0{,}1$. Cerchiamo uno zero.

$f(0) = \ln 3 + 0{,}1 \approx 1{,}2 > 0$; $\quad f(1) = \ln 4 - 3 + 0{,}1 \approx -1{,}5 < 0$. Segni opposti: c’è uno zero in $[0,1]$.

Passo	$a$	$b$	$m$	$f(m)$
1	$0$	$1$	$0{,}5$	$f(0{,}5)\approx -0{,}15 < 0$
2	$0$	$0{,}5$	$0{,}25$	$f(0{,}25)\approx 0{,}43 > 0$
3	$0{,}25$	$0{,}5$	$0{,}375$	$f(0{,}375)\approx 0{,}12 > 0$
4	$0{,}375$	$0{,}5$	$0{,}4375$	$f(0{,}4375)\approx -0{,}02 < 0$
5	$0{,}375$	$0{,}4375$	$0{,}406$	$f(0{,}406)\approx 0{,}05 > 0$

Dopo 5 passi lo zero è in $[0{,}406;\ 0{,}4375]$, con errore $<0{,}032$. Valore approssimato: $x\approx 0{,}42$.

La forza della bisezione è la sua robustezza: richiede solo di saper valutare $f$ e riconoscere il suo segno, e converge sempre (purché si parta da un cambio di segno). Il prezzo è la lentezza: guadagna circa una cifra decimale ogni $3{,}3$ iterazioni.

Collegamenti

Argomenti: Continuita
Concetti: Algoritmo di bisezione · Teorema degli zeri
Competenze: Stimare · Usare formule

The zero theorem does not say where the zero is, only that it exists. The bisection algorithm finds it by successive approximations, halving the interval at each step.

In brief — Procedure

1. Start from $[a,b]$ with $f(a)\cdot f(b)<0$.
2. Compute the midpoint $m = \dfrac{a+b}{2}$ and the sign of $f(m)$.
3. If $f(a)\cdot f(m) < 0$: the zero is in $[a,m]$, set $b=m$. Otherwise it is in $[m,b]$, set $a=m$.
4. Repeat from step 2 until $|b-a|<\varepsilon$ (the desired precision).

At each step the interval halves: after $n$ steps the error is $\le\dfrac{b-a}{2^n}$.

Example — Bisection applied to $\ln(x+3)-3x+0{,}1=0$

Let $f(x) = \ln(x+3)-3x+0{,}1$. Let us look for a zero.

$f(0) = \ln 3 + 0{,}1 \approx 1{,}2 > 0$; $\quad f(1) = \ln 4 - 3 + 0{,}1 \approx -1{,}5 < 0$. Opposite signs: there is a zero in $[0,1]$.

Step	$a$	$b$	$m$	$f(m)$
1	$0$	$1$	$0{,}5$	$f(0{,}5)\approx -0{,}15 < 0$
2	$0$	$0{,}5$	$0{,}25$	$f(0{,}25)\approx 0{,}43 > 0$
3	$0{,}25$	$0{,}5$	$0{,}375$	$f(0{,}375)\approx 0{,}12 > 0$
4	$0{,}375$	$0{,}5$	$0{,}4375$	$f(0{,}4375)\approx -0{,}02 < 0$
5	$0{,}375$	$0{,}4375$	$0{,}406$	$f(0{,}406)\approx 0{,}05 > 0$

After 5 steps the zero is in $[0{,}406;\ 0{,}4375]$, with error $<0{,}032$. Approximate value: $x\approx 0{,}42$.

The strength of bisection is its robustness: it requires only being able to evaluate $f$ and recognise its sign, and it always converges (provided one starts from a change of sign). The price is its slowness: it gains about one decimal digit every $3{,}3$ iterations.

Links

Topics: Continuita
Concepts: Algoritmo di bisezione · Teorema degli zeri
Skills: Stimare · Usare formule

L’algoritmo di bisezione è robusto ma lento: dimezza l’errore a ogni passo, quindi guadagna circa una cifra decimale ogni $3{,}3$ iterazioni. Se conosciamo la derivata di $f$ possiamo costruire un algoritmo molto più rapido: il metodo di Newton-Raphson.

Proprietà — Iterazione di Newton

Sia $f$ derivabile con derivata $f'$, e sia $x_0$ una stima iniziale di uno zero. La successione $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ converge (sotto ipotesi ragionevoli) a uno zero di $f$. Geometricamente: si traccia la tangente al grafico di $f$ nel punto $(x_n,f(x_n))$ e si prende come $x_{n+1}$ l’intersezione della tangente con l’asse $x$.

Metodo di Newton per $f(x)=x^2-2$: dalla stima $x_0$ la tangente incontra l’asse $x$ in $x_1$, più vicino alla radice $\sqrt{2}$; ripetendo, ci si avvicina rapidamente.

Collegamenti

Argomenti: Continuita
Concetti: Algoritmo di bisezione · Derivata · Metodo di newton raphson · Retta · Retta tangente
Metodi: Newton raphson
Competenze: Interpretare grafico · Usare formule

The bisection algorithm is robust but slow: it halves the error at each step, so it gains about one decimal digit every $3{,}3$ iterations. If we know the derivative of $f$ we can build a much faster algorithm: the Newton-Raphson method.

Property — Newton's iteration

Let $f$ be differentiable with derivative $f'$, and let $x_0$ be an initial estimate of a zero. The sequence $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ converges (under reasonable hypotheses) to a zero of $f$. Geometrically: one draws the tangent to the graph of $f$ at the point $(x_n,f(x_n))$ and takes as $x_{n+1}$ the intersection of the tangent with the $x$-axis.

Newton’s method for $f(x)=x^2-2$: from the estimate $x_0$ the tangent meets the $x$-axis at $x_1$, closer to the root $\sqrt{2}$; repeating, one approaches it rapidly.

Links

Topics: Continuita
Concepts: Algoritmo di bisezione · Derivata · Metodo di newton raphson · Retta · Retta tangente
Methods: Newton raphson
Skills: Interpretare grafico · Usare formule

Applicare Newton all’estrazione di radice porta a una formula antichissima, e mostra quanto sia rapida la sua convergenza.

Esempio — Calcolo di $\sqrt{2}$ con Newton

Sia $f(x)=x^2-2$, $f'(x)=2x$. L’iterazione diventa $x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} = \frac{1}{2}\left(x_n+\frac{2}{x_n}\right).$ Partendo da $x_0=2$:

| $n$ | $x_n$ | $|x_n-\sqrt{2}|$ | |:---:|:---:|:---:| | $0$ | $2$ | $0{,}585\ldots$ | | $1$ | $1{,}5$ | $0{,}0858\ldots$ | | $2$ | $1{,}41\overline{6}$ | $0{,}0024\ldots$ | | $3$ | $1{,}41421568\ldots$ | $2{,}1\cdot 10^{-6}$ | | $4$ | $1{,}41421356\ldots$ | $\le 10^{-12}$ |

A ogni passo raddoppiano le cifre decimali corrette: la convergenza è quadratica, nel senso che $|x_{n+1}-\alpha|\le C\,|x_n-\alpha|^2$ in un intorno della radice $\alpha$ (Esty, 2014). È il celebre algoritmo babilonese-eroniano per il calcolo della radice, attribuito a Erone d’Alessandria ($\approx 60$ d.C.; Boyer, 2011).

La formula $x_{n+1} = \tfrac{1}{2}\left(x_n+\tfrac{2}{x_n}\right)$ ha una lettura intuitiva: se $x_n$ è una stima per eccesso di $\sqrt{2}$, allora $2/x_n$ lo è per difetto, e la loro media è una stima migliore. Questa idea di “media tra eccesso e difetto” è proprio il metodo antico, e la convergenza quadratica spiega perché bastino pochissimi passi per ottenere moltissime cifre.

Collegamenti

Argomenti: Continuita
Concetti: Convergenza quadratica · Metodo di newton raphson
Metodi: Newton raphson
Competenze: Calcolare · Usare formule
Persone: Erone

Applying Newton to the extraction of a root leads to a very ancient formula, and shows how fast its convergence is.

Example — Computing $\sqrt{2}$ with Newton

Let $f(x)=x^2-2$, $f'(x)=2x$. The iteration becomes $x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} = \frac{1}{2}\left(x_n+\frac{2}{x_n}\right).$ Starting from $x_0=2$:

| $n$ | $x_n$ | $|x_n-\sqrt{2}|$ | |:---:|:---:|:---:| | $0$ | $2$ | $0{,}585\ldots$ | | $1$ | $1{,}5$ | $0{,}0858\ldots$ | | $2$ | $1{,}41\overline{6}$ | $0{,}0024\ldots$ | | $3$ | $1{,}41421568\ldots$ | $2{,}1\cdot 10^{-6}$ | | $4$ | $1{,}41421356\ldots$ | $\le 10^{-12}$ |

At each step the number of correct decimal digits doubles: the convergence is quadratic, in the sense that $|x_{n+1}-\alpha|\le C\,|x_n-\alpha|^2$ in a neighbourhood of the root $\alpha$ (Esty, 2014). It is the famous Babylonian-Heronian algorithm for computing the root, attributed to Hero of Alexandria ($\approx 60$ AD; Boyer, 2011).

The formula $x_{n+1} = \tfrac{1}{2}\left(x_n+\tfrac{2}{x_n}\right)$ has an intuitive reading: if $x_n$ is an overestimate of $\sqrt{2}$, then $2/x_n$ is an underestimate, and their average is a better estimate. This idea of the “average between overestimate and underestimate” is precisely the ancient method, and the quadratic convergence explains why very few steps are enough to obtain a great many digits.

Links

Topics: Continuita
Concepts: Convergenza quadratica · Metodo di newton raphson
Methods: Newton raphson
Skills: Calcolare · Usare formule
People: Erone

Newton è molto più veloce della bisezione, ma paga questa velocità con una minore robustezza: può non convergere se le condizioni iniziali sono sfavorevoli.

Esempio — Confronto con la bisezione

La bisezione applicata a $x^2-2=0$ su $[1,2]$ dà errore $<10^{-6}$ dopo circa $20$ iterazioni; Newton lo fa in $4$. Trade-off: la bisezione richiede solo $f$ (e un cambio di segno); Newton richiede $f'$ e una stima iniziale “abbastanza vicina”.

Attenzione — Quando Newton fallisce

La convergenza non è garantita in tutti i casi:

• Se $f'(x_n)=0$ in qualche punto $\to$ divisione per zero, divergenza.
• Se $x_0$ è scelto male, l’iterazione può “saltare” fuori e oscillare (per esempio $f(x)=x^3-2x+2$ a partire da $x_0=0$ produce un ciclo $0,1,0,1,\ldots$).
• Vicino a zeri multipli la convergenza è solo lineare, non più quadratica.

La strategia comune è ibrida: prima un paio di passi di bisezione per “avvicinarsi”, poi Newton per affinare rapidamente.

In sintesi: la bisezione è la scelta sicura ma lenta; Newton è la scelta veloce ma delicata. Nella pratica numerica si combinano i due, sfruttando la robustezza dell’una per garantire una buona stima iniziale e la rapidità dell’altra per la precisione finale.

Collegamenti

Argomenti: Continuita
Concetti: Algoritmo di bisezione · Convergenza quadratica · Metodo di newton raphson
Metodi: Newton raphson
Competenze: Analisi casi limite · Ragionare per casi

Newton’s method is much faster than bisection, but it pays for this speed with lower robustness: it may fail to converge if the initial conditions are unfavourable.

Example — Comparison with bisection

Bisection applied to $x^2-2=0$ on $[1,2]$ gives an error $<10^{-6}$ after about $20$ iterations; Newton does it in $4$. Trade-off: bisection requires only $f$ (and a sign change); Newton requires $f'$ and an initial estimate that is “close enough”.

Warning — When Newton fails

Convergence is not guaranteed in every case:

• If $f'(x_n)=0$ at some point $\to$ division by zero, divergence.
• If $x_0$ is chosen badly, the iteration may “jump” away and oscillate (for example $f(x)=x^3-2x+2$ starting from $x_0=0$ produces a cycle $0,1,0,1,\ldots$).
• Near multiple zeros convergence is only linear, no longer quadratic.

The common strategy is hybrid: first a couple of bisection steps to “get close”, then Newton to refine quickly.

In summary: bisection is the safe but slow choice; Newton is the fast but delicate choice. In numerical practice the two are combined, exploiting the robustness of the one to guarantee a good initial estimate and the speed of the other for the final precision.

Links

Topics: Continuity
Concepts: Bisection algorithm · Quadratic convergence · Newton-Raphson method
Methods: Newton-Raphson
Skills: Analysis of limiting cases · Reasoning by cases