5.1 Roots of Equations and Rates of Convergence
Bisection, regula falsi, fixed-point iteration, Newton–Raphson and the secant method: when each one converges, how fast — linear, superlinear with order $\tfrac{1+\sqrt5}{2}$, quadratic — and what goes wrong at multiple roots and far from the root.
Very few equations can be solved by a formula. There is no formula for the root of $x=\cos x$, of Kepler's equation $E-e\sin E=M$ that locates a planet or a satellite on its orbit, of the equation that gives the interest rate hidden in a loan's monthly instalment, or of a general polynomial equation of degree five. What we can always do is iterate: start from a guess $x_0$ and improve it by a rule $x_{n+1}=\Phi(x_n)$ (or $\Phi(x_n,x_{n-1})$) until the answer is good enough. Babylonian scribes had $\sqrt2$ to about six significant figures nearly four thousand years ago, a value this kind of iteration produces; Newton described his tangent method in 1669 on the cubic $x^3-2x-5=0$; and every calculator, every finite-element code and every orbit-determination program still does it today.
Two questions decide whether an iteration is any good. Does it converge — from which starting values, and to which root? And how fast — does each step add a fixed number of correct digits (linear convergence) or double the number of correct digits (quadratic convergence)? This section answers both for the standard methods: bracketing methods (bisection, regula falsi) that can never fail but are slow; fixed-point iteration, governed by the single number $|g'(\alpha)|$; Newton–Raphson, quadratically convergent at simple roots but only linearly at multiple roots; and the secant method, whose order is the golden ratio. CSIR NET asks for exactly these facts — the number of bisection steps for a given accuracy, which rearrangement $x=g(x)$ converges, the order of Newton's method at a double root, the order of the secant method — and its Part C options are built from the counterexamples collected in the ⚠️ box below.
Iterations and the Speed of Convergence
Throughout, $f$ is a real function, $\alpha$ is a root ($f(\alpha)=0$) and $x_0,x_1,x_2,\dots$ are the approximations produced by a method. The error of $x_n$ is $e_n=x_n-\alpha$. To compare methods we need a precise notion of speed.
Let $x_n\to\alpha$ with $x_n\ne\alpha$ for all $n$. The convergence has order $p\ge1$ with asymptotic error constant $C$ if
$$\lim_{n\to\infty}\frac{|x_{n+1}-\alpha|}{|x_n-\alpha|^{p}}=C,\qquad 0\lt C\lt\infty,$$where for $p=1$ we require in addition $C\lt1$. The convergence is
Some authors call an iteration "of order at least $p$" when only $|e_{n+1}|\le K|e_n|^p$ is known; we shall say so explicitly when we mean that.
(a) A convergent sequence has at most one order $p$ in the sense of Definition 5.1. (b) Let $d_n=-\log_{10}|e_n|$ be the number of correct decimal digits of $x_n$ (roughly). If the convergence has order $p$ with constant $C$, then
$$d_{n+1}=p\,d_n-\log_{10}C+o(1)\qquad(n\to\infty).$$So linear convergence adds about $\log_{10}(1/C)$ correct digits per step, while convergence of order $p\gt1$ multiplies the number of correct digits by about $p$ per step.
Proof. (a) Suppose the limits in Definition 5.1 exist for $p$ with constant $C\in(0,\infty)$ and for $q\gt p$ with constant $C'$. Then $$\frac{|e_{n+1}|}{|e_n|^{q}}=\frac{|e_{n+1}|}{|e_n|^{p}}\cdot|e_n|^{p-q}\longrightarrow C\cdot\infty=\infty,$$ because $e_n\to0$ and $p-q\lt0$; this contradicts $C'\lt\infty$. (b) Take $\log_{10}$ of $|e_{n+1}|=|e_n|^{p}\,\big(C+o(1)\big)$: $-d_{n+1}=-p\,d_n+\log_{10}\big(C+o(1)\big)$, and $\log_{10}(C+o(1))=\log_{10}C+o(1)$ since $C\gt0$. ∎
The practical meaning is dramatic. With $C=\tfrac12$ (bisection-like speed) one gains $\log_{10}2\approx0.3$ digits per step, so $16$ digits cost about $53$ steps. With quadratic convergence the digits go $1,2,4,8,16$: five steps. The constant $C$ matters only for linear convergence; for $p\gt1$ it shifts the digit count by a fixed amount.
Bracketing Methods: Bisection and Regula Falsi
If $f$ is continuous on $[a,b]$ and $f(a)$, $f(b)$ have opposite signs, the intermediate value theorem (in the CSIR NET Unit 1 course) guarantees a root in $(a,b)$. A bracketing method keeps an interval with this sign property at every step and shrinks it.
Let $f\in C[a,b]$ with $f(a)f(b)\lt0$. Put $a_0=a$, $b_0=b$ and, for $n=1,2,\dots$,
$$c_n=\frac{a_{n-1}+b_{n-1}}{2},\qquad [a_n,b_n]=\begin{cases}[a_{n-1},c_n],&f(a_{n-1})f(c_n)\lt0,\\[2pt] [c_n,b_{n-1}],&f(a_{n-1})f(c_n)\gt0,\end{cases}$$stopping if $f(c_n)=0$. The midpoints $c_n$ are the approximations; each step costs one evaluation of $f$.
Let $f\in C[a,b]$ with $f(a)f(b)\lt0$. If the method does not stop, the endpoints $a_n$ and $b_n$ converge to a common limit $\alpha\in(a,b)$ with $f(\alpha)=0$, and for every $n\ge1$
$$|c_n-\alpha|\le\frac{b-a}{2^{n}}.$$Consequently $|c_n-\alpha|\le\varepsilon$ is guaranteed as soon as $n\ge\log_2\!\big((b-a)/\varepsilon\big)$.
Proof. By induction, $f(a_n)f(b_n)\lt0$ for all $n$ (the rule keeps the half on which the sign changes) and $b_n-a_n=(b-a)/2^n$. The sequence $(a_n)$ is non-decreasing and $(b_n)$ is non-increasing, both bounded, so they converge; their difference tends to $0$, so they have a common limit $\alpha$, and $a_n\le\alpha\le b_n$ for every $n$. By continuity $f(a_n)f(b_n)\to f(\alpha)^2$, and a limit of negative numbers is $\le0$; hence $f(\alpha)^2\le0$, i.e. $f(\alpha)=0$. Finally $\alpha\in[a_{n-1},b_{n-1}]$ and $c_n$ is the midpoint of this interval of length $(b-a)/2^{n-1}$, so $|c_n-\alpha|\le(b-a)/2^n$. The last statement is $(b-a)/2^n\le\varepsilon\iff 2^n\ge(b-a)/\varepsilon$. ∎
Bisection needs only continuity and a sign change, never fails, and its error bound is known in advance — but it ignores the size of $f(c_n)$ and gains only one binary digit per step. The bound $(b-a)/2^n$ halves at every step, yet the actual error $|c_n-\alpha|$ need not decrease at every step (Example 1), so bisection does not converge "linearly with $C=\tfrac12$" in the sense of Definition 5.1; one says its error is bounded by a linearly convergent sequence.
Let $f\in C[a,b]$ with $f(a)f(b)\lt0$. Starting from $[a_0,b_0]=[a,b]$, replace the midpoint of bisection by the point where the chord through $(a_{n-1},f(a_{n-1}))$ and $(b_{n-1},f(b_{n-1}))$ meets the $x$-axis:
$$c_n=b_{n-1}-f(b_{n-1})\,\frac{b_{n-1}-a_{n-1}}{f(b_{n-1})-f(a_{n-1})}=\frac{a_{n-1}f(b_{n-1})-b_{n-1}f(a_{n-1})}{f(b_{n-1})-f(a_{n-1})},$$and keep the subinterval $[a_{n-1},c_n]$ or $[c_n,b_{n-1}]$ on which $f$ changes sign, exactly as in bisection.
Regula falsi uses the values of $f$, so it is usually faster than bisection at the start. But the interval need not shrink to zero: when $f$ is convex or concave on $[a,b]$, one endpoint never moves.
Let $f\in C^2[a,b]$ with $f(a)f(b)\lt0$ and $f''\ne0$ on $[a,b]$ (so $f''$ has constant sign). Let $\beta\in\{a,b\}$ be the endpoint with $f(\beta)f''(\beta)\gt0$. Then $\beta$ is never replaced, the approximations $c_n$ converge monotonically to the unique root $\alpha$ in $(a,b)$, and the convergence is linear:
$$\lim_{n\to\infty}\frac{c_{n+1}-\alpha}{c_n-\alpha}=C=1-\frac{f'(\alpha)\,(\beta-\alpha)}{f(\beta)},\qquad 0\lt C\lt1.$$Proof. Replacing $f$ by $-f$ and/or $x$ by $a+b-x$ we may assume $f''\gt0$ on $[a,b]$, $f(a)\lt0\lt f(b)$, so $\beta=b$. There is exactly one root $\alpha$ in $(a,b)$: if $a\lt\alpha_1\lt\alpha_2\lt b$ were two roots, write $\alpha_1=\lambda a+(1-\lambda)\alpha_2$ with $\lambda\in(0,1)$; convexity gives $0=f(\alpha_1)$ $\le\lambda f(a)+(1-\lambda)f(\alpha_2)$ $=\lambda f(a)\lt0$, a contradiction. Suppose $a_{n-1}\lt\alpha$ and $b_{n-1}=b$. On $[a_{n-1},b]$ the convex graph lies below its chord, and the chord vanishes at $c_n$; therefore $f(c_n)\le0$, i.e. $c_n\le\alpha$, and $c_n\gt a_{n-1}$ because $f(a_{n-1})\lt0$. So the new interval is $[c_n,b]$: the endpoint $b$ stays, and $a_{n-1}\lt c_n\le\alpha$. The increasing bounded sequence $c_n$ has a limit $L\le\alpha$, and letting $n\to\infty$ in $c_{n+1}=c_n-f(c_n)(b-c_n)/(f(b)-f(c_n))$ gives $f(L)(b-L)=0$, so $f(L)=0$ and $L=\alpha$.
For the rate, $c_{n+1}=\varphi(c_n)$ with $\varphi(x)=x-f(x)\,\dfrac{b-x}{f(b)-f(x)}$, a $C^1$ function near $\alpha$ with $\varphi(\alpha)=\alpha$. Differentiating and using $f(\alpha)=0$, $$\varphi'(\alpha)=1-\frac{f'(\alpha)(b-\alpha)}{f(b)}.$$ By the mean value theorem $c_{n+1}-\alpha=\varphi'(\xi_n)(c_n-\alpha)$ with $\xi_n\to\alpha$, so the ratio tends to $C=\varphi'(\alpha)$. Finally $f'(\alpha)\gt0$ (the convex function is increasing at its root since $f(a)\lt0$) and strict convexity gives $f(b)\gt f(\alpha)+f'(\alpha)(b-\alpha)$ $=f'(\alpha)(b-\alpha)\gt0$; hence $0\lt f'(\alpha)(b-\alpha)/f(b)\lt1$ and $0\lt C\lt1$. ∎
The fixed endpoint is the weakness of regula falsi: $C$ can be very close to $1$. The Illinois modification (halve the stored value $f(\beta)$ whenever the same endpoint survives twice) removes it and gives superlinear convergence while keeping the bracket.
| $n$ | $c_n$ | sign $f(c_n)$ | new interval | $|c_n-\alpha|$ |
|---|---|---|---|---|
| 1 | 1.5 | $+$ | [1, 1.5] | 0.1753 |
| 2 | 1.25 | $-$ | [1.25, 1.5] | 0.0747 |
| 3 | 1.375 | $+$ | [1.25, 1.375] | 0.0503 |
| 4 | 1.3125 | $-$ | [1.3125, 1.375] | 0.0122 |
| 5 | 1.34375 | $+$ | [1.3125, 1.34375] | 0.0190 |
| 6 | 1.328125 | $+$ | [1.3125, 1.328125] | 0.0034 |
| 7 | 1.3203125 | $-$ | [1.3203125, 1.328125] | 0.0044 |
Fixed-Point Iteration
Write the equation $f(x)=0$ in the form $x=g(x)$ — there are always many ways, e.g. $g(x)=x-\lambda f(x)$ for any $\lambda\ne0$ — and iterate $x_{n+1}=g(x_n)$. If the iterates converge to $\alpha$ and $g$ is continuous, then $\alpha=\lim x_{n+1}=g(\lim x_n)=g(\alpha)$, so the limit is a root. Everything depends on the choice of $g$.
A fixed point of $g$ is a number $\alpha$ with $g(\alpha)=\alpha$. The fixed-point iteration for $g$ is $x_{n+1}=g(x_n)$, $n\ge0$. A map $g:I\to\mathbb{R}$ on an interval $I$ is a contraction if there is a constant $L\lt1$ with
$$|g(x)-g(y)|\le L\,|x-y|\qquad\text{for all }x,y\in I.$$If $g$ is differentiable on $I$ with $|g'(x)|\le L\lt1$ for all $x\in I$, then $g$ is a contraction on $I$ with constant $L$, by the mean value theorem.
Let $g:[a,b]\to[a,b]$ be continuous. Then:
- $g$ has at least one fixed point in $[a,b]$;
- if, in addition, $g$ is a contraction on $[a,b]$ with constant $L\lt1$, the fixed point $\alpha$ is unique, the iteration $x_{n+1}=g(x_n)$ converges to $\alpha$ for every $x_0\in[a,b]$, and
Proof. (1) Let $h(x)=g(x)-x$. Since $g(a)\ge a$ and $g(b)\le b$, $h(a)\ge0\ge h(b)$, and the intermediate value theorem gives $\alpha$ with $h(\alpha)=0$.
(2) If $\alpha,\beta$ are fixed points, $|\alpha-\beta|=|g(\alpha)-g(\beta)|\le L|\alpha-\beta|$, which forces $|\alpha-\beta|=0$ because $L\lt1$. Since $g$ maps $[a,b]$ into itself, all $x_n$ lie in $[a,b]$, and $$|x_n-\alpha|=|g(x_{n-1})-g(\alpha)|\le L|x_{n-1}-\alpha|\le\dots\le L^n|x_0-\alpha|\to0.$$ For the computable bounds, the triangle inequality gives $|x_0-\alpha|\le|x_0-x_1|+|x_1-\alpha|$ $\le|x_1-x_0|+L|x_0-\alpha|$, hence $|x_0-\alpha|\le|x_1-x_0|/(1-L)$. Applied with $x_{n-1}$ as the starting point, the same inequality reads $|x_{n-1}-\alpha|\le|x_n-x_{n-1}|/(1-L)$, and then $|x_n-\alpha|\le L|x_{n-1}-\alpha|\le\tfrac{L}{1-L}|x_n-x_{n-1}|$. ∎
This is the one-dimensional case of the Banach fixed-point theorem (Unit 1 course), the same principle that drives the Picard iterates of §1.1 Existence and Uniqueness of Solutions. Both hypotheses matter: $g$ must map the interval into itself, and the interval must be closed (see the ⚠️ box). In practice one rarely knows a suitable interval in advance, and the following local theorem is what is used.
Let $g$ be $C^1$ on an open interval containing a fixed point $\alpha$.
- Attracting: if $|g'(\alpha)|\lt1$, there is $\delta\gt0$ such that for every $x_0\in[\alpha-\delta,\alpha+\delta]$ the iterates stay in this interval and converge to $\alpha$; moreover $e_{n+1}/e_n\to g'(\alpha)$ (when no $e_n$ is $0$). So the convergence is linear with rate $|g'(\alpha)|$ if $g'(\alpha)\ne0$, and superlinear if $g'(\alpha)=0$. It is monotone if $g'(\alpha)\gt0$ and oscillates about $\alpha$ if $g'(\alpha)\lt0$.
- Repelling: if $|g'(\alpha)|\gt1$, no sequence of iterates converges to $\alpha$, unless some $x_n$ equals $\alpha$ exactly.
- Higher order: if $g\in C^p$ for some $p\ge2$, $g'(\alpha)=\dots=g^{(p-1)}(\alpha)=0$ and $g^{(p)}(\alpha)\ne0$, then for $x_0$ near $\alpha$ the convergence has order exactly $p$ and $$\lim_{n\to\infty}\frac{e_{n+1}}{e_n^{\,p}}=\frac{g^{(p)}(\alpha)}{p!}.$$
If $|g'(\alpha)|=1$ the test is inconclusive.
Proof. (1) Put $L=\tfrac12(1+|g'(\alpha)|)\lt1$. By continuity of $g'$ there is $\delta\gt0$ with $|g'(x)|\le L$ on $I=[\alpha-\delta,\alpha+\delta]$. For $x\in I$ the mean value theorem gives $|g(x)-\alpha|=|g(x)-g(\alpha)|$ $=|g'(\xi)|\,|x-\alpha|\le L\delta\lt\delta$, so $g(I)\subseteq I$ and $g$ is a contraction on $I$; Theorem 5.4 gives convergence. Writing $e_{n+1}=g(x_n)-g(\alpha)=g'(\xi_n)e_n$ with $\xi_n$ between $x_n$ and $\alpha$, we get $e_{n+1}/e_n=g'(\xi_n)\to g'(\alpha)$. If $g'(\alpha)\gt0$ then $g'(\xi_n)\gt0$ for large $n$, so $e_{n+1}$ and $e_n$ have the same sign; if $g'(\alpha)\lt0$ the signs alternate.
(2) Choose $\delta$ with $|g'(x)|\ge K\gt1$ on $[\alpha-\delta,\alpha+\delta]$. If $x_n\to\alpha$ with all $x_n\ne\alpha$, then for $n\ge N$ the points lie in this interval and $|e_{n+1}|=|g'(\xi_n)|\,|e_n|\ge K|e_n|$, so $|e_n|\ge K^{n-N}|e_N|\to\infty$ — impossible.
(3) Since $g'(\alpha)=0$, part (1) gives convergence. Taylor's theorem with Lagrange remainder about $\alpha$ gives $g(x_n)=\alpha+\tfrac{1}{p!}g^{(p)}(\xi_n)e_n^{\,p}$, i.e. $e_{n+1}/e_n^{\,p}=g^{(p)}(\xi_n)/p!\to g^{(p)}(\alpha)/p!\ne0$. ∎
| $g$ | $g'(\alpha)$ | prediction; iterates from $x_0=1.5$ |
|---|---|---|
| $x^3-1$ | $\approx5.26$ | repels, monotone 2.375, 12.40, 1904, … |
| $(x+1)^{1/3}$ | $\approx0.190$ | linear, monotone 1.3572, 1.3309, 1.3259, … |
| $\sqrt{1+1/x}$ | $\approx-0.215$ | linear, oscillating 1.2910, 1.3321, 1.3231, … |
| $1/x+1/x^2$ | $\approx-1.430$ | repels, oscillating 1.1111, 1.71, 0.9268, 2.243, … |
The Newton–Raphson Method
Replace $f$ near the current guess $x_n$ by its tangent line $y=f(x_n)+f'(x_n)(x-x_n)$ and take the zero of the tangent as the next guess. Equivalently, choose the rearrangement $g(x)=x-f(x)/f'(x)$, for which $g'(\alpha)=f(\alpha)f''(\alpha)/f'(\alpha)^2=0$ at a simple root — the best possible value in Theorem 5.5.
For differentiable $f$ and a starting value $x_0$, the Newton–Raphson iteration is
$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)},\qquad n=0,1,2,\dots,$$defined as long as $f'(x_n)\ne0$; each step costs one evaluation of $f$ and one of $f'$. A root $\alpha$ of $f$ has multiplicity $m\in\mathbb{N}$ if $f(x)=(x-\alpha)^m h(x)$ with $h$ continuous at $\alpha$ and $h(\alpha)\ne0$; for $f\in C^m$ this means $f(\alpha)=f'(\alpha)=\dots=f^{(m-1)}(\alpha)$ $=0\ne f^{(m)}(\alpha)$. A root of multiplicity $1$ (i.e. $f'(\alpha)\ne0$) is simple; $m\ge2$ gives a multiple root.
Let $f$ be $C^2$ on an open interval containing a simple root $\alpha$ ($f(\alpha)=0\ne f'(\alpha)$). Then there is $\delta\gt0$ such that for every $x_0\in[\alpha-\delta,\alpha+\delta]$ the Newton iterates are defined, stay in this interval, converge to $\alpha$, and satisfy
$$|e_{n+1}|\le M\,|e_n|^2,\qquad \lim_{n\to\infty}\frac{e_{n+1}}{e_n^{\,2}}=\frac{f''(\alpha)}{2f'(\alpha)},$$where $M=\max|f''|\,/\,(2\min|f'|)$ over the interval. The convergence has order exactly $2$ if $f''(\alpha)\ne0$, and order at least $3$ if $f''(\alpha)=0$ (and $f\in C^3$).
Proof. Choose $\delta_0\gt0$ so that $|f'(x)|\ge m\gt0$ on $I_0=[\alpha-\delta_0,\alpha+\delta_0]$ (continuity of $f'$), put $M=\max_{I_0}|f''|/(2m)$ and $\delta=\min(\delta_0,\,1/(2M))$ (any $\delta\le\delta_0$ if $M=0$). Suppose $x_n\in I=[\alpha-\delta,\alpha+\delta]$. Taylor's theorem about $x_n$, evaluated at $\alpha$, gives $$0=f(\alpha)=f(x_n)+f'(x_n)(\alpha-x_n)+\tfrac12f''(\xi_n)(\alpha-x_n)^2$$ with $\xi_n$ between $x_n$ and $\alpha$. Divide by $f'(x_n)\ne0$ and use $x_{n+1}=x_n-f(x_n)/f'(x_n)$: $$x_{n+1}-\alpha=\frac{f''(\xi_n)}{2f'(x_n)}\,(x_n-\alpha)^2,\qquad\text{i.e.}\qquad e_{n+1}=\frac{f''(\xi_n)}{2f'(x_n)}\,e_n^{\,2}.$$ Hence $|e_{n+1}|\le M|e_n|^2\le M\delta|e_n|\le\tfrac12|e_n|$, so $x_{n+1}\in I$; by induction all iterates lie in $I$ and $|e_n|\le2^{-n}|e_0|\to0$. Since $x_n\to\alpha$ and $\xi_n\to\alpha$, the factor $f''(\xi_n)/(2f'(x_n))$ tends to $f''(\alpha)/(2f'(\alpha))$. If this is nonzero the order is exactly $2$ by Definition 5.1. If $f''(\alpha)=0$ and $f\in C^3$, expand one term further (Exercise III.7): $e_{n+1}/e_n^{\,3}\to f'''(\alpha)/(3f'(\alpha))$. ∎
The theorem is local: it promises convergence only from "close enough" starting values and says nothing about how close. The next result is a classical global condition (often attributed to Fourier) that is easy to check on an interval.
Let $f\in C^2[a,b]$ with $f(a)f(b)\lt0$, $f'\ne0$ on $[a,b]$, and $f''\ge0$ on $[a,b]$ or $f''\le0$ on $[a,b]$. If $x_0\in[a,b]$ satisfies $f(x_0)f''(x_0)\gt0$, then the Newton iterates stay in $[a,b]$ and converge monotonically to the unique root $\alpha\in(a,b)$ (and quadratically by Theorem 5.6).
Proof. The cases reduce to one by replacing $f$ by $-f$ and/or $x$ by $-x$; assume $f'\gt0$ and $f''\ge0$ on $[a,b]$. Then $f$ is strictly increasing, so it has exactly one root $\alpha$, and $f(x_0)f''(x_0)\gt0$ forces $f(x_0)\gt0$, i.e. $x_0\gt\alpha$. Suppose $\alpha\le x_n\le x_0$. Then $f(x_n)\ge0$, so $x_{n+1}=x_n-f(x_n)/f'(x_n)\le x_n$. By Taylor's theorem, $$f(x_{n+1})=f(x_n)+f'(x_n)(x_{n+1}-x_n)+\tfrac12f''(\xi)(x_{n+1}-x_n)^2=\tfrac12f''(\xi)(x_{n+1}-x_n)^2\ge0,$$ because the first two terms cancel by the definition of $x_{n+1}$. As $f$ is increasing, $x_{n+1}\ge\alpha$. So $(x_n)$ is non-increasing and bounded below by $\alpha$; its limit $L\in[\alpha,x_0]\subseteq[a,b]$ satisfies $L=L-f(L)/f'(L)$, i.e. $f(L)=0$, so $L=\alpha$. ∎
Geometrically: on the convex side of the root the tangent lies below the graph, so its zero never overshoots the root. Starting on the other side ($f(x_0)f''(x_0)\lt0$) the first step overshoots — and may leave $[a,b]$ — after which the theorem applies from $x_1$ if $x_1$ is still in $[a,b]$. A consequence used in Example 5(c): if $f'\gt0$ and $f''\gt0$ on all of $\mathbb{R}$ and $f$ has a root, Newton's method converges from every $x_0$.
Let $f(x)=(x-\alpha)^m h(x)$ with $m\ge2$, $h\in C^1$ near $\alpha$ and $h(\alpha)\ne0$.
- Newton's method converges to $\alpha$ from all $x_0$ close enough to $\alpha$, but only linearly: $\displaystyle\frac{e_{n+1}}{e_n}\to1-\frac1m$.
- The modified Newton method $\displaystyle x_{n+1}=x_n-m\,\frac{f(x_n)}{f'(x_n)}$ converges at least quadratically (for $x_0$ near $\alpha$).
- If $m$ is unknown, $u=f/f'$ has a simple root at $\alpha$; Newton's method applied to $u$, $\ x_{n+1}=x_n-\dfrac{f f'}{f'^2-ff''}(x_n)$, is quadratically convergent when $h$ is smooth enough.
Proof. For $x\ne\alpha$ near $\alpha$, $f'(x)=(x-\alpha)^{m-1}\big[m\,h(x)+(x-\alpha)h'(x)\big]$, so for the iteration $x\mapsto x-k\,f(x)/f'(x)$ (with $k=1$ for Newton, $k=m$ for the modified method) $$\frac{x-k\frac{f(x)}{f'(x)}-\alpha}{x-\alpha}=1-\frac{k\,h(x)}{m\,h(x)+(x-\alpha)h'(x)}=:\rho_k(x).$$ (1) For $k=1$: $\rho_1(x)\to1-\tfrac1m\in[\tfrac12,1)$ as $x\to\alpha$. Hence $|\rho_1(x)|\le L\lt1$ on some interval $|x-\alpha|\le\delta$, so $|e_{n+1}|\le L|e_n|$: the iterates stay in the interval and converge, and $e_{n+1}/e_n=\rho_1(x_n)\to1-\tfrac1m$. (2) For $k=m$: $\rho_m(x)=\dfrac{(x-\alpha)h'(x)}{m\,h(x)+(x-\alpha)h'(x)}$, so $|e_{n+1}|=|\rho_m(x_n)|\,|e_n|\le K|e_n|^2$ with $K$ a bound for $|h'|/\big(\tfrac{m}{2}|h(\alpha)|\big)$ near $\alpha$; this gives convergence for $|e_0|\lt1/K$ and then order at least $2$. (3) $u(x)=\dfrac{(x-\alpha)h(x)}{m\,h(x)+(x-\alpha)h'(x)}$, so $u(\alpha)=0$ and $u(x)/(x-\alpha)\to1/m\ne0$: $\alpha$ is a simple root of $u$, and Theorem 5.6 applies to $u$; a short computation gives $u/u'=ff'/(f'^2-ff'')$. ∎
So the hallmark of a multiple root is linear convergence of Newton's method with ratio $\tfrac12$ (double root), $\tfrac23$ (triple root), …; conversely, observing a ratio $e_{n+1}/e_n\approx1-\tfrac1m$ reveals the multiplicity. Near a multiple root $f$ is also very flat, so $\alpha$ is ill-conditioned: a perturbation of size $\varepsilon$ in $f$ moves a root of multiplicity $m$ by about $\varepsilon^{1/m}$.
The Secant Method, Efficiency, and Newton's Method for Systems
Newton's method needs $f'$, which may be expensive or unavailable (when $f$ is the output of a simulation, say). Replacing $f'(x_n)$ by the slope of the chord through the last two iterates gives a derivative-free method that is still superlinear.
Given two starting values $x_0\ne x_1$, the secant method is
$$x_{n+1}=x_n-f(x_n)\,\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})},\qquad n\ge1.$$Unlike regula falsi it always uses the two latest points, whether or not they bracket a root; each step costs one new evaluation of $f$. If a method has order $p$ and costs $w$ function evaluations (counting $f$ and $f'$ alike) per step, its efficiency index is $p^{1/w}$: the factor by which the number of correct digits grows per evaluation.
Let $f$ be $C^2$ near a simple root $\alpha$ with $f''(\alpha)\ne0$. If $x_0,x_1$ are close enough to $\alpha$, the secant iterates converge to $\alpha$ with order
$$p=\frac{1+\sqrt5}{2}\approx1.618,\qquad \lim_{n\to\infty}\frac{|e_{n+1}|}{|e_n|^{p}}=\left|\frac{f''(\alpha)}{2f'(\alpha)}\right|^{p-1}.$$Hence the efficiency index is $1.618$ for the secant method and $\sqrt2\approx1.414$ for Newton's method: per function evaluation, the secant method is faster when $f'$ costs as much as $f$.
Proof (careful sketch). Step 1: an exact error formula. With the divided differences $f[u,v]=\dfrac{f(u)-f(v)}{u-v}$ and $f[u,v,w]=\dfrac{f[u,v]-f[v,w]}{u-w}$ (studied in §5.3 Finite Differences and Interpolation), $f(x_n)=f(x_n)-f(\alpha)=f[x_n,\alpha]\,e_n$, and the method reads $x_{n+1}=x_n-f(x_n)/f[x_{n-1},x_n]$. Therefore $$e_{n+1}=e_n\left(1-\frac{f[x_n,\alpha]}{f[x_{n-1},x_n]}\right)=\frac{f[x_{n-1},x_n]-f[x_n,\alpha]}{f[x_{n-1},x_n]}\,e_n=\frac{f[x_{n-1},x_n,\alpha]}{f[x_{n-1},x_n]}\,e_n\,e_{n-1}.$$ By the mean value theorem $f[x_{n-1},x_n]=f'(\eta_n)$ and $f[x_{n-1},x_n,\alpha]=\tfrac12f''(\zeta_n)$ with $\eta_n,\zeta_n$ in the smallest interval containing $x_{n-1},x_n,\alpha$. So $$e_{n+1}=c_n\,e_n\,e_{n-1},\qquad c_n=\frac{f''(\zeta_n)}{2f'(\eta_n)}.$$
Step 2: convergence. Near $\alpha$, $|c_n|\le K$. If $|e_0|,|e_1|\le\delta$ with $K\delta\le\tfrac12$, then $|e_2|\le K\delta|e_1|\le\tfrac12|e_1|$, and inductively $|e_{n+1}|\le\tfrac12|e_n|$, so $e_n\to0$ and $c_n\to C=f''(\alpha)/(2f'(\alpha))\ne0$.
Step 3: the order. Put $\varepsilon_n=|C\,e_n|$; then $\varepsilon_{n+1}=\dfrac{|c_n|}{|C|}\,\varepsilon_n\varepsilon_{n-1}$ with $|c_n|/|C|\to1$, so $y_n=-\log\varepsilon_n$ satisfies $y_{n+1}=y_n+y_{n-1}+o(1)$, a perturbed Fibonacci recursion. Its solutions grow like $A\,p^n$ where $p$ is the larger root of $t^2=t+1$, i.e. $p=\tfrac{1+\sqrt5}2$. Precisely, $z_n=y_{n+1}-p\,y_n$ satisfies $z_n=-z_{n-1}/p+o(1)$ (use $1-p=-1/p$), and since $1/p\lt1$ this forces $z_n\to0$, which is the statement $\varepsilon_{n+1}/\varepsilon_n^{\,p}\to1$. Unwinding, $|e_{n+1}|/|e_n|^p\to|C|^{p-1}$. The same answer comes from the ansatz $|e_{n+1}|\approx A|e_n|^p$: substituting into $|e_{n+1}|\approx|C|\,|e_n|\,|e_{n-1}|$ (where $|e_{n-1}|$ is approximately $(|e_n|/A)^{1/p}$) forces $p=1+\tfrac1p$ and $A=|C|^{1/p}=|C|^{p-1}$.
Step 4: efficiency. Secant: $p=1.618$, $w=1$. Newton: $p=2$, $w=2$, so $2^{1/2}\approx1.414$. ∎
| step | regula falsi $c_n$ | error |
|---|---|---|
| 1 | 0.685073357 | $-5.4\times10^{-2}$ |
| 2 | 0.736298998 | $-2.8\times10^{-3}$ |
| 3 | 0.738945356 | $-1.4\times10^{-4}$ |
| 4 | 0.739078131 | $-7.0\times10^{-6}$ |
| 5 | 0.739084782 | $-3.5\times10^{-7}$ |
| step | secant $x_{n+1}$ | error |
|---|---|---|
| 1 | 0.685073357 | $-5.4\times10^{-2}$ |
| 2 | 0.736298998 | $-2.8\times10^{-3}$ |
| 3 | 0.739119362 | $+3.4\times10^{-5}$ |
| 4 | 0.739085112 | $-2.1\times10^{-8}$ |
| 5 | 0.739085133215 | $-1.6\times10^{-13}$ |
Newton's idea extends verbatim to systems: linearise, then solve the linear system for the correction. For two equations $f(x,y)=0$, $g(x,y)=0$ this is the form usually examined.
Let $F=(F_1,\dots,F_k):\mathbb{R}^k\to\mathbb{R}^k$ be differentiable with Jacobian matrix $J(\mathbf{x})=\big(\partial F_i/\partial x_j\big)$. Newton's method is
$$J(\mathbf{x}^{(n)})\,\mathbf{d}^{(n)}=-F(\mathbf{x}^{(n)}),\qquad \mathbf{x}^{(n+1)}=\mathbf{x}^{(n)}+\mathbf{d}^{(n)}.$$For $k=2$, with $F=(f,g)$ and $D=f_xg_y-f_yg_x$ evaluated at $(x_n,y_n)$, Cramer's rule gives
$$x_{n+1}=x_n-\frac{f\,g_y-g\,f_y}{D},\qquad y_{n+1}=y_n-\frac{g\,f_x-f\,g_x}{D}.$$One never forms $J^{-1}$: each step solves one linear system (by the Gauss elimination of §5.2).
Proof (sketch). Taylor's theorem in several variables gives $0=F(\mathbf{x}^*)$ $=F(\mathbf{x}^{(n)})+J(\mathbf{x}^{(n)})(\mathbf{x}^*-\mathbf{x}^{(n)})+R_n$ with $\|R_n\|\le c\|\mathbf{e}^{(n)}\|^2$. Multiplying by $J(\mathbf{x}^{(n)})^{-1}$, whose norm is bounded near $\mathbf{x}^*$ because $J$ is continuous and $J(\mathbf{x}^*)$ is invertible, gives $\mathbf{e}^{(n+1)}=J(\mathbf{x}^{(n)})^{-1}R_n$, hence $\|\mathbf{e}^{(n+1)}\|\le M\|\mathbf{e}^{(n)}\|^2$; the induction is as in Theorem 5.6. ∎
- Locate first. Tabulate signs or sketch to isolate each root in an interval $[a,b]$ with $f(a)f(b)\lt0$; count real roots with $f'$ (monotonic pieces).
- Need a guarantee? Bisection: $n=\lceil\log_2((b-a)/\varepsilon)\rceil$ steps, whatever $f$ is (continuous). Exam questions on "number of iterations" are always about this bound.
- Fixed-point form $x=g(x)$? Compute $g'(\alpha)$ (use the equation to simplify). $|g'(\alpha)|\lt1$: converges linearly with rate $|g'(\alpha)|$; $\gt1$: diverges; $=0$: order $\ge2$ — find the first nonzero derivative.
- Newton. Simple root: quadratic, $e_{n+1}\approx\frac{f''}{2f'}e_n^2$. Root of multiplicity $m$: linear with ratio $1-\frac1m$; restore quadratic speed with $x-mf/f'$. For a safe start use Theorem 5.7: $f(x_0)f''(x_0)\gt0$.
- Orders to remember. Bisection $1$ (error bound ratio $\tfrac12$), regula falsi $1$, fixed point $1$ in general, secant $1.618$, Newton $2$, Newton at an $m$-fold root $1$.
- Stopping. Use both $|x_{n+1}-x_n|\lt\varepsilon$ and $|f(x_n)|\lt\eta$; for linear convergence with ratio $L$ the true error can be $\tfrac{L}{1-L}$ times the last step (Theorem 5.4).
- $|g'|\lt1$ pointwise is not enough. $g(x)=\sqrt{1+x^2}$ satisfies $|g'(x)|\lt1$ everywhere and has no fixed point; a uniform bound $|g'|\le L\lt1$ is needed.
- The interval must be closed and mapped into itself. $g(x)=x/2$ is a contraction of $(0,1]$ into itself with no fixed point in $(0,1]$; $g(x)=x^2$ on $[0,2]$ has $g([0,2])=[0,4]\not\subseteq[0,2]$, and iterates from $1.5$ escape.
- Bisection's error is not monotone. For $x^3-x-1$ on $[1,2]$: $|c_4-\alpha|=0.0122$ but $|c_5-\alpha|=0.0190$. Only the bound $(b-a)/2^n$ halves.
- A sign change need not mean a root, and no sign change need not mean no root. $f(x)=1/x$ on $[-1,1]$ changes sign and bisection converges to the pole $0$ (continuity fails); $f(x)=x^2-\tfrac14$ on $[-1,1]$ has two roots and $f(-1)f(1)\gt0$; a double root such as $(x-1)^2$ is never bracketed.
- Newton can cycle. For $f(x)=x^3-2x+2$ and $x_0=0$: $x_1=1$, $x_2=0$, $x_3=1,\dots$ forever, although $f$ has a real root near $-1.77$.
- Newton can diverge. For $f(x)=x^{1/3}$, $x_{n+1}=-2x_n$ from every $x_0\ne0$ ($f'$ is unbounded at the root). For $f(x)=\arctan x$, it diverges from every $|x_0|\gt1.3917$.
- Breakdown at a horizontal tangent. If $f'(x_n)=0$ the step is undefined, and if $f'(x_n)$ is merely small the next iterate is thrown far away.
- Quadratic convergence is local. For $f(x)=x^{10}-1$ from $x_0=0.5$, $x_1=51.65$, and then each step only multiplies $x_n$ by about $0.9$: $43$ steps are needed to reach $10^{-10}$ accuracy.
- Multiple roots slow Newton down. At a root of multiplicity $m$ the convergence is linear with ratio $1-\tfrac1m$. Using the modified method with the wrong $m$ can destroy convergence: $x-2f/f'$ at a simple root has $g'(\alpha)=-1$.
- Regula falsi can be slower than bisection. For $x^{10}-1$ on $[0,1.3]$ the right end stays fixed and $61$ steps are needed for $10^{-6}$, against $21$ for bisection.
- $|g'(\alpha)|=1$: no conclusion. $g(x)=x-x^3$ converges to $0$ from $x_0=0.5$ but sublinearly ($x_n\approx1/\sqrt{2n}$), while $g(x)=x+x^3$ diverges from every $x_0\ne0$.
- Small steps or small residuals do not prove accuracy. For $x_{n+1}=x_n-x_n^3$ the steps $x_n^3$ are tiny long before $x_n$ is small; for a flat function, $|f(x_n)|$ is small far from the root.
Exercises
- 1 Show that $e^x=3x$ has exactly one root in $[0,1]$ and perform four steps of bisection on $[0,1]$.
- 2 How many bisection steps on an interval of length $1$ guarantee an error at most $10^{-8}$?
- 3 Show that $x^5+x-1=0$ has exactly one real root, locate it in $[0,1]$, and perform two steps of regula falsi. Which endpoint stays fixed, and why?
- 4 Let $f(x)=(x-0.1)(x-0.4)(x-0.8)$ on $[0,1]$. Check that $f(0)f(1)\lt0$ and determine which of the three roots bisection converges to.
- 5 Apply regula falsi to $x^2-2$ on $[1,2]$: show that the end $2$ is never replaced, compute $c_1,c_2,c_3$ exactly, and find the limit of $(c_{n+1}-\sqrt2)/(c_n-\sqrt2)$.
- 6 Apply the secant method to $x^2-2$ with $x_0=1$, $x_1=2$ and compute $x_2,x_3,x_4$ as fractions. Compare with Exercise 5.
- 7 Explain why bisection cannot be used to find the root of $(x-1)^2$ but can be used for $(x-1)^3$. What is the convergence of Newton's method for $(x-1)^3$?
- 8 Give a function $f$ on $[0,3]$ with $f(0)f(3)\lt0$ for which bisection converges to a point that is not a root. Which hypothesis of Theorem 5.2 fails?
- 1 Show that $g(x)=e^{-x}$ maps $[0.4,0.7]$ into itself and is a contraction there. From $x_0=0.5$, how many iterations does the a priori bound of Theorem 5.4 require for an error $\le10^{-6}$? What is the actual rate of convergence?
- 2 The roots of $x^2-2x-3=0$ are $3$ and $-1$. For each of $g_1(x)=\sqrt{2x+3}$, $g_2(x)=\dfrac{3}{x-2}$, $g_3(x)=\dfrac{x^2-3}{2}$, decide to which root (if any) the iteration converges from nearby starting values.
- 3 (Population model.) For $x_{n+1}=2.5\,x_n(1-x_n)$ find the fixed points and their nature, and describe the iterates from $x_0=0.1$.
- 4 Let $a\gt0$. Show that $x_{n+1}=x_n\big(3-3ax_n+a^2x_n^2\big)$ satisfies $1-ax_{n+1}=(1-ax_n)^3$. Deduce its order, its asymptotic error constant and the set of $x_0$ for which it converges to $1/a$.
- 5 Prove that $x_{n+1}=\cos x_n$ converges to the root $\alpha$ of $x=\cos x$ for every $x_0\in\mathbb{R}$, and find the rate.
- 6 For which $\lambda$ does $x_{n+1}=x_n+\lambda(x_n^2-2)$ converge to $\sqrt2$ at least quadratically? What is then the asymptotic constant, and how is this related to Newton's method?
- 7 Let $g:[a,b]\to[a,b]$ satisfy $|g(x)-g(y)|\lt|x-y|$ for all $x\ne y$. Prove that $g$ has exactly one fixed point. Show by the example $g(x)=x-\tfrac12x^2$ on $[0,1]$ that $g$ need not be a contraction.
- 8 Show that $x_{n+1}=x_n-x_n^3$, $x_0=0.5$, decreases to $0$, that $1/x_{n+1}^2-1/x_n^2\to2$, and hence $x_n\sim1/\sqrt{2n}$. What does this say about the order of convergence?
- 1 Apply Newton's method to $x^3-2x-5=0$ from $x_0=2$ (Newton's own example) and compute $x_1,x_2,x_3$.
- 2 Show that Newton's method for $x^k=a$ ($a\gt0$, $k\ge2$) is $x_{n+1}=\tfrac1k\big((k-1)x_n+a/x_n^{k-1}\big)$, and compute $\sqrt[3]{10}$ from $x_0=2$ in two steps.
- 3 Show that Newton's method for $f(x)=\tfrac1x-a$ ($a\gt0$) is $x_{n+1}=x_n(2-ax_n)$ and that $1-ax_{n+1}=(1-ax_n)^2$. For which $x_0$ does it converge? Compute $1/7$ from $x_0=0.1$.
- 4 For $f(x)=xe^{-x}$ show that Newton's method is $x_{n+1}=\dfrac{x_n^2}{x_n-1}$. Describe the iterates from $x_0=2$ and from $x_0=0.5$.
- 5 Show that Newton's method for $f(x)=\sqrt[3]{x}$ gives $x_{n+1}=-2x_n$. Which hypothesis of Theorem 5.6 fails?
- 6 Find the multiplicity of the root $0$ of $f(x)=x-\sin x$. Predict the behaviour of Newton's method and of the modified Newton method from $x_0=1$, and explain why the modified method is even faster than quadratic here.
- 7 Let $f\in C^3$ near a simple root $\alpha$ with $f''(\alpha)=0$. Prove that $e_{n+1}/e_n^{\,3}\to f'''(\alpha)/(3f'(\alpha))$ for Newton's method, and check it for $f(x)=\sin x$ at $\alpha=\pi$.
- 8 Perform two steps of Newton's method for the system $x^2-y=1$, $x+y^2=3$ from $(1,1)$.
- 1 A method has errors satisfying $e_{n+1}\approx C\,e_n^{\,2}\,e_{n-1}$. Show that its order is $1+\sqrt2$.
- 2 Determine the order (if any) of the sequences of errors (a) $e_n=2^{-2^n}$; (b) $e_n=2^{-n}$; (c) $e_n=1/n!$; (d) $e_n=1/n$.
- 3 Halley's method is $x_{n+1}=x_n-\dfrac{2ff'}{2f'^2-ff''}(x_n)$. Show that for $f(x)=x^2-a$ it becomes $x_{n+1}=\dfrac{x_n(x_n^2+3a)}{3x_n^2+a}$, that $e_{n+1}/e_n^{\,3}\to1/(4a)$, and compute $\sqrt2$ from $x_0=1$ in two steps.
- 4 Steffensen's method $x_{n+1}$ $=x_n-\dfrac{f(x_n)^2}{f(x_n+f(x_n))-f(x_n)}$ uses no derivative. Perform three steps for $x^2-2$ from $x_0=1.5$, estimate the order, and compute its efficiency index.
- 5 (Orbits.) Kepler's equation $E-e\sin E=M$ gives the eccentric anomaly $E$ of a satellite with eccentricity $0\le e\lt1$ at mean anomaly $M$. Show that $E_{n+1}=M+e\sin E_n$ converges for every $E_0$, and for $M=1$, $e=0.5$ compare three steps of it with three Newton steps from $E_0=M$.
- 6 (Finance.) A loan of ₹5,00,000 is repaid in $36$ equal monthly instalments of ₹16,500. The monthly interest rate $i$ satisfies $500000\,i=16500\big(1-(1+i)^{-36}\big)$. Solve by Newton's method from $i_0=0.01$. Why must one not start at $i_0=0$?
- 7 Show that for $f(x)=x^m$ ($m\ge2$) Newton's method gives exactly $x_{n+1}=(1-\tfrac1m)x_n$, while for $f(x)=x^m+x^{m+1}$ the ratio $x_{n+1}/x_n$ only tends to $1-\tfrac1m$.
- 8 (Cayley's problem.) For $f(z)=z^2-1$ in $\mathbb{C}$, Newton's map is $N(z)=\tfrac12(z+1/z)$. Show that $w=\dfrac{z-1}{z+1}$ transforms it into $w\mapsto w^2$, and deduce that the iterates converge to $1$ if $\operatorname{Re}z_0\gt0$, to $-1$ if $\operatorname{Re}z_0\lt0$, and never converge if $z_0\ne0$ is purely imaginary.
E1. CSIR Part B GATE MA Let $f$ be continuous on $[2,3]$ with $f(2)f(3)\lt0$. The smallest $n$ for which the bisection error bound guarantees $|c_n-\alpha|\lt5\times10^{-4}$ for the $n$-th midpoint $c_n$ is (A) $10$; (B) $11$; (C) $12$; (D) $2000$.
E2. CSIR Part B The iteration $x_{n+1}=\dfrac{x_n^2+6}{5}$ with $x_0=2.9$ (A) converges to $3$ quadratically; (B) converges to $2$ linearly, with $\dfrac{x_{n+1}-2}{x_n-2}\to\dfrac45$; (C) converges to $2$ quadratically; (D) diverges to $+\infty$.
E3. CSIR Part B GATE MA Newton's method is applied to $f(x)=(x-2)^3(x+1)$ with $x_0$ close to $2$. Then $\lim\dfrac{x_{n+1}-2}{x_n-2}$ equals (A) $0$; (B) $\tfrac13$; (C) $\tfrac23$; (D) $1$.
E4. CSIR Part C Let $g:\mathbb{R}\to\mathbb{R}$ be differentiable with $|g'(x)|\le\tfrac12$ for all $x$, and $x_{n+1}=g(x_n)$. Which of the following are necessarily true? (One or more options may be correct.) (A) $g$ has exactly one fixed point $\alpha$. (B) $x_n\to\alpha$ for every $x_0$. (C) $|x_n-\alpha|\le2^{-n}|x_1-x_0|$ for all $n$. (D) The convergence is quadratic.
E5. CSIR Part C Newton's method is applied to $f(x)=x^3-5x$. Which of the following are true? (A) From $x_0=1$ the iterates alternate between $-1$ and $1$. (B) From $x_0=2$ they converge to $\sqrt5$. (C) From every $x_0$ with $|x_0|\lt1$ they converge to $0$, with $e_{n+1}\approx-\tfrac25e_n^3$. (D) From every $x_0$ with $1\lt|x_0|\lt\sqrt{5/3}$ they converge to $0$.
E6. CSIR Part C Let $f\in C^2$ near a simple root $\alpha$ with $f''(\alpha)\ne0$. Which of the following are true? (A) The secant method converges locally with order $\tfrac{1+\sqrt5}{2}$. (B) If $f'\gt0$ and $f''\gt0$ on $[a,b]$ with $f(a)\lt0\lt f(b)$, regula falsi never replaces the end point $b$. (C) In bisection, $|c_{n+1}-\alpha|\le|c_n-\alpha|$ for every $n$. (D) If an evaluation of $f'$ costs as much as one of $f$, the secant method has a larger efficiency index than Newton's method.
Suggested plan — 3 lectures × 60 min.
- Speed and bracketing. Definition 5.1 and Theorem 5.1 ("digits added" versus "digits multiplied"); bisection with Theorem 5.2 and Example 1 on the board — stop at step 5 and ask whether the error went down. Regula falsi and Theorem 5.3 with a convex picture showing the frozen end point; Exercise I.5 as a two-minute check.
- Fixed-point iteration. Theorems 5.4 and 5.5 with full proofs. Project Interactive 1: staircase, spiral, divergence, then the Newton map. Example 2 (four rearrangements) live, letting students predict before the widget shows each case. Example 5(a)–(b) as a Part C warm-up.
- Newton and secant. Theorem 5.6 (the error identity is the heart of the lecture), Theorem 5.7, Examples 3–4, Theorem 5.8; Interactive 2 with the double root, then the secant method on $x^3-x-1$ to watch $p_n\to1.618$. Close with Theorem 5.9, the efficiency index, Example 7 and Exam corner E3, E5.
Discussion questions. (1) Newton's method has order $2$ and the secant method order $1.618$; why would a library routine nevertheless often prefer the secant method or a bracketed hybrid (such as Brent's method)? (2) Is quadratic convergence a property of the method, of the equation, or of the root? (3) Every root of $f$ is a fixed point of infinitely many $g$; what makes the Newton choice special, and what does it cost?
Misconceptions to watch for. "Bisection's error halves every step"; "$|g'(x)|\lt1$ for all $x$ guarantees a fixed point"; "Newton always converges if $x_0$ is close to the root" without quantifying "close"; "Newton is quadratic at every root" (multiple roots); "regula falsi is always faster than bisection"; "a small residual $|f(x_n)|$ means a small error"; confusing the order $p$ with the constant $C$.
Suggested homework. I(1, 2, 5, 7), II(1, 2, 4, 6, 8), III(1, 3, 4, 6, 8), IV(1, 2, 5, 6); Exam corner E2, E4, E6.
Research question. A satellite-tracking program must solve Kepler's equation $E-e\sin E=M$ millions of times a day, for eccentricities from nearly circular orbits ($e\approx0$) to highly elliptical ones such as Molniya communication orbits ($e\approx0.74$) and comets ($e$ close to $1$). Which iteration and which starting value give a solver that is both fast and guaranteed to converge for all $M\in(0,\pi]$ and $0\le e\lt1$?
Why it matters. Orbit propagation for GPS and Galileo navigation satellites, conjunction screening between pieces of space debris, and spacecraft mission design all call a Kepler solver in their innermost loop; a solver that is slow for some $(M,e)$, or that occasionally fails to converge, is a genuine engineering hazard.
What to do.
- Implement the fixed-point iteration $E_{n+1}=M+e\sin E_n$ and Newton's method, both with the stopping rule $|E_{n+1}-E_n|\lt10^{-12}$ and a cap of $200$ iterations.
- For $e\in\{0.1,0.5,0.9,0.99,0.999\}$ and $400$ equally spaced values of $M\in(0,\pi]$, record the maximum number of iterations of: the fixed-point iteration from $E_0=M$; Newton from $E_0=M$; Newton from $E_0=\pi$.
- Explain the fixed-point counts using the contraction constant $e$ (Theorem 5.4) and the Newton counts using Theorems 5.6 and 5.7 (where is $f(E)=E-e\sin E-M$ convex?).
- Find a pair $(M,e)$ for which Newton from $E_0=M$ fails, and draw the first few tangent lines to see why.
Tools: Python or a spreadsheet; Interactive 2 for intuition about tangent lines.
Hand in: A table of maximum iteration counts, a one-paragraph recommendation for a flight-software team, and the failing example with a sketch.
Going further. Read about starting values built from series in $e$ and about higher-order (Halley-type) Kepler solvers; investigate how much the starter, rather than the iteration, controls the cost.
🧪 Self-check quiz
Q1. Newton's method is applied near a double root $\alpha$ of a smooth function. The convergence is
Q2. Let $g\in C^1$ with fixed point $\alpha$. The iteration $x_{n+1}=g(x_n)$ converges to $\alpha$ for all $x_0$ near $\alpha$ provided
Q3. The order of convergence of the secant method at a simple root (with $f''(\alpha)\ne0$) is
Q4. The minimum number of bisection steps on $[0,1]$ that guarantees an error at most $10^{-6}$ is
Q5. For Newton's method on $f(x)=x^2-a$ ($a\gt0$, $x_0\gt0$), $\lim e_{n+1}/e_n^2$ equals