Corrected exercises: bisection, Newton's method and fixed-point iteration (201-SN2-RE)

$f(x)=x^{3}+x^{2}-3$, $f(1)=-1<0<f(2)=9$. Midpoint $1.5$: $f(1.5)=2.625>0$, keep $[1, 1.5]$. Midpoint $1.25$: $f(1.25)\approx 0.516>0$, keep $[1, 1.25]$. Midpoint $1.125$: $f(1.125)\approx-0.311<0$, keep $[1.125, 1.25]$. The midpoint of this last interval is $1.1875$. Pitfall: giving the last midpoint TESTED, $1.125$, instead of the midpoint of the interval obtained.

$f(x)=e^{x}+x-2$, $f(0)=-1<0<f(1)=e-1$. $f(0.5)\approx 0.149>0$: $[0, 0.5]$. $f(0.25)\approx-0.466<0$: $[0.25, 0.5]$. $f(0.375)\approx-0.170<0$: $[0.375, 0.5]$. Midpoint: $0.4375$. Pitfall: bisecting $e^{x}$ and $2-x$ separately; only the sign of their DIFFERENCE tells you which side the root is on.

$f(x)=x^{2}-7$, $f'(x)=2x$, so $x_{n+1}=x_{n}-\frac{x_{n}^{2}-7}{2x_{n}}$. $x_{1}=3-\frac{2}{6}=\frac{8}{3}\approx 2.666667$, then $x_{2}=\frac{8}{3}-\frac{\frac{64}{9}-7}{\frac{16}{3}}=\frac{8}{3}-\frac{1}{48}=\frac{127}{48}\approx 2.646$.

$f(x)=x^{3}-10$, $f'(x)=3x^{2}$. $x_{1}=2-\frac{8-10}{12}=\frac{13}{6}\approx 2.166667$. $f(x_{1})\approx 0.171296$ and $f'(x_{1})\approx 14.083333$, so $x_{2}\approx 2.166667-0.012163\approx 2.155$.

$f(x)=x^{3}-2x-5$, $f'(x)=3x^{2}-2$. $x_{1}=2-\frac{-1}{10}=2.1$. $f(2.1)=9.261-4.2-5=0.061$ and $f'(2.1)=11.23$, so $x_{2}=2.1-\frac{0.061}{11.23}\approx 2.094568\approx 2.095$.

$f(x)=x^{4}+x-3$, $f'(x)=4x^{3}+1$. $x_{1}=1-\frac{-1}{5}=1.2$. $f(1.2)=2.0736+1.2-3=0.2736$ and $f'(1.2)=7.912$, so $x_{2}=1.2-\frac{0.2736}{7.912}\approx 1.165$.

$f(x)=\sin x-\frac{x}{2}$, $f'(x)=\cos x-\frac{1}{2}$. $f(2)\approx-0.090703$ and $f'(2)\approx-0.916147$, so $x_{1}\approx 1.900996$. Then $f(x_{1})\approx-0.004520$ and $f'(x_{1})\approx-0.824232$, so $x_{2}\approx 1.895512\approx 1.896$. Pitfall: a calculator in degree mode gives $f(2)\approx-0.965$ and a sequence that no longer has anything to do with the equation.

$f(x)=\ln x+x-2$, $f'(x)=\frac{1}{x}+1$. $f(1.5)\approx-0.094535$ and $f'(1.5)\approx 1.666667$, so $x_{1}\approx 1.556721$. Then $f(x_{1})\approx-0.000697$ and $f'(x_{1})\approx 1.642376$, so $x_{2}\approx 1.557146\approx 1.557$.

$f(x)=e^{x}-4x$, $f'(x)=e^{x}-4$. $f(0)=1$ and $f'(0)=-3$, so $x_{1}=0-\frac{1}{-3}=\frac{1}{3}$. Then $f\left(\frac{1}{3}\right)\approx 0.062279$ and $f'\left(\frac{1}{3}\right)\approx-2.604388$, so $x_{2}\approx 0.333333+0.023913\approx 0.357$. Pitfall: the negative derivative; minus times minus, you MOVE to the right.

The minimum is where $f'$ vanishes: apply Newton's method to $g=f'$, that is $g(x)=4x^{3}+6x-5$ and $g'(x)=f''(x)=12x^{2}+6$. $x_{1}=1-\frac{5}{18}=\frac{13}{18}\approx 0.722222$. Then $g(x_{1})\approx 0.840192$ and $g'(x_{1})\approx 12.259259$, so $x_{2}\approx 0.722222-0.068535\approx 0.654$. Pitfall: writing $x_{1}=x_{0}-\frac{f(x_{0})}{f'(x_{0})}$, which looks for a zero of $f$ and not for its minimum.

$f(1)=1+3-5=-1<0$ and $f(2)=8+6-5=9>0$ ✓, and $f$ is continuous since it is a polynomial. Algorithm: compute the midpoint $m$ of the interval, evaluate $f(m)$, then keep the half whose endpoints give opposite signs. Repeat. At every step, the interval still contains a root and its width is halved.

$m_{1}=1.5$: $f(1.5)=3.375+4.5-5=2.875>0$, so keep $[1, 1.5]$. $m_{2}=1.25$: $f(1.25)=1.953125+3.75-5=0.703125>0$, keep $[1, 1.25]$. $m_{3}=1.125$: $f(1.125)=1.423828+3.375-5=-0.201172<0$, this time keep the RIGHT half, $[1.125, 1.25]$. Width reached: $0.125$, and the root is inside.

The width after $n$ iterations is $\frac{2-1}{2^{n}}=2^{-n}$. To guarantee $2^{-n}\leq 10^{-6}$, you need $n\geq\frac{6\ln 10}{\ln 2}\approx 19.93$, so $n=20$ iterations. This number is known IN ADVANCE, independently of the function: that is the great strength of the method, you can promise the accuracy before you even start.

Gaining one decimal place means dividing the error by 10. Since each iteration divides it by 2, you need $n$ such that $2^{n}\geq 10$, that is $n\geq\frac{\ln 10}{\ln 2}\approx 3.32$: so it takes between 3 and 4 iterations per decimal place. This steady pace is characteristic of linear convergence, and it should be compared with Newton's method, which DOUBLES the number of correct decimals at every step.

The GUARANTEE. If the sign changes at the endpoints and the function is continuous, bisection always converges, whatever the function, and the maximum error is known at every step. Newton's method is much faster but may diverge, cycle, or converge to a root other than the one you were aiming for. That is why serious numerical libraries combine the two: bisection to get close without risk, then Newton's method to finish fast.

The tangent line at $x_{n}$ is $y=f(x_{n})+f'(x_{n})(x-x_{n})$. It crosses the axis when $y=0$, that is $x=x_{n}-\frac{f(x_{n})}{f'(x_{n})}$, provided $f'(x_{n})\neq 0$. So set $x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}$: this is Newton's formula. There is nothing mysterious about it, it is the equation of a line, solved.

$f(2)=2$ and $f'(2)=4$, so $x_{1}=2-\frac{2}{4}=1.5$ ✓. Then $f(1.5)=0.25$ and $f'(1.5)=3$, so $x_{2}=1.5-\frac{0.25}{3}=1.4166667$ ✓. One more iteration gives $x_{3}=1.4142157$, to compare with $\sqrt{2}=1.4142136$: three iterations from a mediocre starting point are enough for five correct decimals.

$f'(x)=2x$, so $x_{n+1}=x_{n}-\frac{x_{n}^{2}-a}{2x_{n}}=\frac{2x_{n}^{2}-x_{n}^{2}+a}{2x_{n}}=\frac{x_{n}^{2}+a}{2x_{n}}=\frac{1}{2}\left(x_{n}+\frac{a}{x_{n}}\right)$. It is the AVERAGE of $x_{n}$ and $\frac{a}{x_{n}}$. The interpretation is a nice one: if $x_{n}$ is too small to be $\sqrt{a}$, then $\frac{a}{x_{n}}$ is too large, and the true root lies between the two. This formula was already known to the Babylonians, long before Newton gave the general justification.

$f'(x)=3x^{2}+3$. $f(1)=-1$ and $f'(1)=6$, so $x_{1}=1+\frac{1}{6}=1.1666667$. Then $f(x_{1})=0.0879630$ and $f'(x_{1})=7.0833333$, so $x_{2}=1.1666667-0.0124183=1.1542484$. Finally $f(x_{2})=0.0005378$ and $f'(x_{2})=6.9969$, so $x_{3}=1.1541715$. The exact root is $1.1541715$: seven decimals in three steps.

After three iterations, bisection had given the bracket $[1.125, 1.25]$, an error that could be as large as $0.125$. After three iterations, Newton's method gives an error below $10^{-7}$. The ratio is about one million, and it stays enormous even though each Newton step costs two evaluations, of the function and of its derivative, against one for bisection. What changes is the price to pay: Newton's method requires knowing $f'$ and a reasonable starting point, bisection only needs a sign change.

With $\sqrt{2}=1.41421356$: $e_{0}=\left|2-1.41421356\right|=0.58578644$; $e_{1}=\left|1.5-1.41421356\right|=0.08578644$; $e_{2}=\left|1.41666667-1.41421356\right|=0.00245310$; $e_{3}=\left|1.41421569-1.41421356\right|=2.1239\times 10^{-6}$.

$\frac{e_{1}}{e_{0}^{2}}=\frac{0.08578644}{0.34314}=0.25000$; $\frac{e_{2}}{e_{1}^{2}}=\frac{0.00245310}{0.0073593}=0.33333$; $\frac{e_{3}}{e_{2}^{2}}=\frac{2.1239\times 10^{-6}}{6.0177\times 10^{-6}}=0.35294$. The ratios SETTLE around $0.3536\approx\frac{1}{2\sqrt{2}}$. This is the signature of quadratic convergence: the new error is proportional to the square of the old one, with a constant that tends to $\frac{f''(r)}{2f'(r)}=\frac{2}{2\times 2\sqrt{2}}=\frac{1}{2\sqrt{2}}$.

$x_{n+1}-\sqrt{a}=\frac{x_{n}^{2}+a}{2x_{n}}-\sqrt{a}=\frac{x_{n}^{2}+a-2\sqrt{a}\,x_{n}}{2x_{n}}=\frac{\left(x_{n}-\sqrt{a}\right)^{2}}{2x_{n}}=\frac{e_{n}^{2}}{2x_{n}}$. The numerator is a perfect square, which gives TWO pieces of information at once: the convergence is quadratic, and $e_{n+1}$ is always positive, so the sequence approaches the root from above as of the first step, whatever the positive starting point.

If the error goes from $10^{-k}$ to about $C\times 10^{-2k}$, the number of correct decimals DOUBLES at every iteration: 1, 2, 4, 8, 16. Bisection, for its part, gains one every 3.32 iterations. To reach 16 decimals starting from one decimal, Newton's method needs 4 steps, bisection about fifty.

It makes the stopping criterion easy and safe. As soon as two consecutive iterates agree to $k$ decimals, the next one would give about $2k$: the gap $\left|x_{n+1}-x_{n}\right|$ is therefore an excellent estimate of the remaining error, which is not true of linear methods. In practice you stop as soon as this gap falls below the required accuracy, knowing that you actually have much better. This is also why a program that has not converged within about ten iterations will not converge at all: the failure must be detected, not insisted upon.

The formula divides by $f'(x_{n})$: the computation stops on a division by zero. Geometrically, the tangent line is HORIZONTAL and never crosses the axis. Example: $f(x)=x^{2}-1$ with $x_{0}=0$ gives $f'(0)=0$, the method is stuck at the very first step even though the roots $\pm 1$ are very close.

$f(0)=2$ and $f'(x)=3x^{2}-2$, so $f'(0)=-2$ and $x_{1}=0-\frac{2}{-2}=1$. Then $f(1)=1-2+2=1$ and $f'(1)=1$, so $x_{2}=1-\frac{1}{1}=0$. You are back at the starting point: the sequence CYCLES between 0 and 1 forever, without ever approaching the true root, which is about $-1.7693$. The tangent lines at these two points send each other back and forth. No test on $f(x_{n})$ detects this; only an iteration counter does.

$f(x)=x^{1/3}$ gives $f'(x)=\frac{1}{3}x^{-2/3}$, so $x_{n+1}=x_{n}-\frac{x_{n}^{1/3}}{\frac{1}{3}x_{n}^{-2/3}}=x_{n}-3x_{n}=-2x_{n}$. Starting from $x_{0}=1$: $1$, $-2$, $4$, $-8$, $16$, the sequence doubles in absolute value and changes sign at every step. It DIVERGES, even though the root, $x=0$, is the most natural starting point in the world. The reason is that the tangent line is vertical at 0: the curve rises too steeply for its tangent line to bring you back to the root.

$f'(x)=2(x-1)$, so $x_{n+1}=x_{n}-\frac{(x_{n}-1)^{2}}{2(x_{n}-1)}=x_{n}-\frac{x_{n}-1}{2}=\frac{x_{n}+1}{2}$. Starting from 2: $1.5$, $1.25$, $1.125$, $1.0625$. The method does converge to 1, but the error is only HALVED at each step: the convergence has become linear, exactly like bisection. This is the systematic behaviour at a MULTIPLE root, where $f$ and $f'$ vanish together.

One, the tangent line is horizontal and the division is impossible. Two, the sequence cycles between two values. Three, the sequence diverges, in particular when the tangent line is vertical near the root. Four, the convergence degenerates into linear convergence at a multiple root. Protection: cap the number of iterations, check that $\left|f(x_{n})\right|$ really decreases, fall back on bisection when it does not, and detect multiple roots by watching whether $f'$ tends to zero at the same time as $f$.

GUARANTEE: bisection always converges if the sign changes and $f$ is continuous; Newton's method may diverge, cycle or switch roots. SPEED: linear with ratio $\frac{1}{2}$ for bisection, quadratic for Newton's method. INFORMATION: bisection only needs a bracket with opposite signs; Newton's method needs $f'$ and a nearby starting point. COST PER ITERATION: one evaluation of $f$ for bisection, one evaluation of $f$ AND one of $f'$ for Newton's method, about twice as much.

Bisection: the initial width is 1, you need $2^{-n}\leq 10^{-10}$, so $n\geq\frac{10\ln 10}{\ln 2}\approx 33.2$, that is 34 iterations. Newton's method from $x_{0}=1$: the successive errors are about $1.5\times 10^{-1}$, $1.2\times 10^{-2}$, $8\times 10^{-5}$, then $3\times 10^{-9}$ and finally below $10^{-16}$. The fourth iterate is therefore already accurate, and the fifth iteration is the one that confirms it through the stopping criterion, since $\left|x_{5}-x_{4}\right|<10^{-10}$ while $\left|x_{4}-x_{3}\right|\approx 3\times 10^{-9}$: five iterations. Even counting two evaluations per step, Newton's method costs about ten evaluations against thirty-four.

Start with a few bisection steps to bring the iterate into a safe neighbourhood of the root, then switch to Newton's method to finish. If a Newton step leaves the bracketing interval, or if $\left|f\right|$ does not decrease, reject that step and do a bisection step instead. The result combines both advantages: you keep a bracket at all times, hence the guarantee of bisection, AND the final speed of Newton's method. This is the principle behind the methods of Brent and Dekker, found in almost every scientific library.

The equation reads $f(x)=\cos x-x=0$. The derivative $f'(x)=-\sin x-1$ is easy to write, and $f(0)=1>0$ while $f(1)=\cos 1-1\approx-0.4597<0$: you have both the derivative and a good bracket, so Newton's method is the right choice. From $x_{0}=1$: $x_{1}=0.7503639$, $x_{2}=0.7391129$, $x_{3}=0.7390851$. The solution is $0.739085$ to within $10^{-6}$, the famous Dottie number, the only fixed point of the cosine.

Because Cardano's formula, exact as it is, is unusable in practice: it involves cube roots of COMPLEX numbers even when all three roots are real, it loses accuracy through catastrophic cancellation in floating-point arithmetic, and it simply does not exist beyond degree 4, by the Abel-Ruffini theorem. Newton's method needs nothing more than the ability to evaluate $f$ and $f'$, so it applies just as well to a polynomial of degree 30 as to $\cos x-x$. In numerical computing, a general convergent method is almost always better than a fragile closed formula.

Replace $f'(x_{n})$ with $\frac{f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}$, which gives $x_{n+1}=x_{n}-f(x_{n})\cdot\frac{x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}$. Geometrically, you draw the line through the last two points of the curve and take its intersection with the axis. So TWO starting points are needed, against one for Newton's method.

$f(1)=-1$ and $f(2)=2$. $x_{2}=2-2\times\frac{2-1}{2-(-1)}=2-\frac{2}{3}=1.3333333$. Then $f(x_{2})=-0.2222222$, so $x_{3}=1.3333333-(-0.2222222)\times\frac{1.3333333-2}{-0.2222222-2}=1.3333333+0.0666667=1.4$. Finally $f(1.4)=-0.04$ and $x_{4}=1.4+0.04\times\frac{1.4-1.3333333}{-0.04+0.2222222}=1.4146341$. You are closing in on $\sqrt{2}=1.4142136$ without ever having differentiated.

Because it costs only ONE function evaluation per iteration, against two for Newton's method, which must evaluate $f$ and $f'$. For the same budget of $2n$ evaluations, the secant method performs $2n$ steps and gains a factor $\varphi^{2n}$ in the exponent, while Newton's method performs $n$ steps and gains $2^{n}$. Since $\varphi^{2}\approx 2.618>2$, the secant method is faster as soon as evaluating $f'$ costs about as much as evaluating $f$, which is the usual case.