Chapter 5 · Numerical Analysis

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.

📘 Definition 5.1 — Order of convergence

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

linearif $p=1$ and $0\lt C\lt1$; the number $C$ is then called the rate (or ratio) of convergence;
superlinearif $|e_{n+1}|/|e_n|\to0$ (every order $p\gt1$ is superlinear);
quadratic / cubicif the order is $p=2$ / $p=3$;
sublinearif $|e_{n+1}|/|e_n|\to1$, as for $e_n=1/n$.

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.

📐 Theorem 5.1 — The order is unique; digits gained per step

(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.

📘 Definition 5.2 — The bisection method

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$.

📐 Theorem 5.2 — Convergence of bisection

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.

📘 Definition 5.3 — Regula falsi (method of false position)

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.

📐 Theorem 5.3 — Regula falsi for convex or concave $f$

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.

✏️ Example 1 — Bisection for $x^3-x-1=0$
Show that $f(x)=x^3-x-1$ has exactly one real root $\alpha$, that $\alpha\in(1,2)$, and perform bisection on $[1,2]$. How many steps guarantee $|c_n-\alpha|\le10^{-4}$? Does the actual error decrease at every step?
One root $f'(x)=3x^2-1$ vanishes at $\pm1/\sqrt3$; the local maximum $f(-1/\sqrt3)=\tfrac{2}{3\sqrt3}-1\lt0$, so $f\lt0$ on $(-\infty,1/\sqrt3]$ and $f$ is increasing after that: exactly one real root. Since $f(1)=-1\lt0\lt5=f(2)$, $\alpha\in(1,2)$.
Steps The signs of $f(c_n)$ decide the half kept:
$n$$c_n$sign $f(c_n)$new interval$|c_n-\alpha|$
11.5$+$[1, 1.5]0.1753
21.25$-$[1.25, 1.5]0.0747
31.375$+$[1.25, 1.375]0.0503
41.3125$-$[1.3125, 1.375]0.0122
51.34375$+$[1.3125, 1.34375]0.0190
61.328125$+$[1.3125, 1.328125]0.0034
71.3203125$-$[1.3203125, 1.328125]0.0044
Accuracy By Theorem 5.2, $|c_n-\alpha|\le2^{-n}$, and $2^{-n}\le10^{-4}\iff n\ge4\log_210\approx13.29$. So $n=14$ steps suffice ($2^{14}=16384$). The root is $\alpha=1.3247179572\ldots$ (the "plastic number").
Not monotone The error went up from step 4 to step 5 ($0.0122\to0.0190$) and from step 6 to step 7. Only the bound halves at each step. This is why exam questions ask for the number of steps that guarantees an accuracy.

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$.

📘 Definition 5.4 — Fixed point, contraction

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.

📐 Theorem 5.4 — Fixed-point theorem on an interval

Let $g:[a,b]\to[a,b]$ be continuous. Then:

  1. $g$ has at least one fixed point in $[a,b]$;
  2. 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
$$|x_n-\alpha|\le L^n|x_0-\alpha|\le\frac{L^n}{1-L}\,|x_1-x_0|\quad\text{(a priori)},$$ $$|x_n-\alpha|\le\frac{L}{1-L}\,|x_n-x_{n-1}|\quad\text{(a posteriori)}.$$

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.

📐 Theorem 5.5 — Local convergence and order of fixed-point iteration

Let $g$ be $C^1$ on an open interval containing a fixed point $\alpha$.

  1. 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$.
  2. Repelling: if $|g'(\alpha)|\gt1$, no sequence of iterates converges to $\alpha$, unless some $x_n$ equals $\alpha$ exactly.
  3. 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$. ∎

✏️ Example 2 — Four rearrangements of $x^3-x-1=0$
For the root $\alpha\approx1.3247$ of $x^3-x-1=0$ consider $g_1(x)=x^3-1$, $g_2(x)=(x+1)^{1/3}$, $g_3(x)=\sqrt{1+1/x}$ and $g_4(x)=\dfrac1x+\dfrac1{x^2}$. Each has $\alpha$ as a fixed point. Predict the behaviour of $x_{n+1}=g_k(x_n)$ near $\alpha$ and check it from $x_0=1.5$.
Fixed points $x=x^3-1$, $x^3=x+1$, $x^2=1+1/x$ (for $x\gt0$) and $x=1/x+1/x^2$ (multiply by $x^2$) are all equivalent to $x^3-x-1=0$ for $x\gt0$.
Derivatives Using $\alpha^3=\alpha+1$:
$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, …
Why For $g_2$: $g_2'(x)=\tfrac13(x+1)^{-2/3}$ and $(\alpha+1)^{2/3}=(\alpha^3)^{2/3}=\alpha^2$. For $g_3$: $g_3'(x)=-\dfrac{1}{2x^2\sqrt{1+1/x}}$ and $\sqrt{1+1/\alpha}=\alpha$, so $g_3'(\alpha)=-\dfrac{1}{2\alpha^3}\approx-0.215$. For $g_4$: $g_4'(\alpha)=-\dfrac1{\alpha^2}-\dfrac2{\alpha^3}\approx-1.430$. Theorem 5.5 predicts exactly the behaviour in the table; $g_2$ gains about $\log_{10}(1/0.19)\approx0.72$ digits per step, $g_3$ about $0.67$.
Lesson The same equation can produce convergent and divergent iterations. The test is $|g'(\alpha)|\lt1$, and the smaller $|g'(\alpha)|$, the faster. Newton's method (next subsection) is the rearrangement that makes $g'(\alpha)=0$. Try all four in Interactive 1.
Interactive 1 — Cobweb Diagrams: Why $|g'(\alpha)|$ Decides Everything

The iteration $x_{n+1}=g(x_n)$ is drawn as a cobweb: go up (or down) to the graph of $g$, then across to the diagonal $y=x$, which turns the output $g(x_n)$ into the next input. Near the fixed point the picture is a staircase if $0\lt g'(\alpha)\lt1$, an inward spiral if $-1\lt g'(\alpha)\lt0$, and it runs away if $|g'(\alpha)|\gt1$. Watch the ratio $e_n/e_{n-1}$ settle at $g'(\alpha)$. Drag the slider to change $x_0$.

—
step n—
x_n—
|x_n − α|—
e_n / e_(n−1)—
g′(α)—

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.

📘 Definition 5.5 — Newton–Raphson method; multiplicity of a root

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.

📐 Theorem 5.6 — Local quadratic convergence of Newton's method

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.

📐 Theorem 5.7 — Monotone convergence of Newton's method

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$.

📐 Theorem 5.8 — Newton's method at a multiple root; the modified method

Let $f(x)=(x-\alpha)^m h(x)$ with $m\ge2$, $h\in C^1$ near $\alpha$ and $h(\alpha)\ne0$.

  1. 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$.
  2. 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$).
  3. 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}$.

✏️ Example 3 — Square roots by Newton's method (Heron's rule)
Let $a\gt0$. (a) Show that Newton's method for $f(x)=x^2-a$ is $x_{n+1}=\tfrac12\left(x_n+\dfrac{a}{x_n}\right)$. (b) Prove that it converges to $\sqrt a$ for every $x_0\gt0$, monotonically from $n=1$ on, and find $\lim e_{n+1}/e_n^{\,2}$. (c) Compute $\sqrt2$ from $x_0=1$.
(a) $x_{n+1}=x_n-\dfrac{x_n^2-a}{2x_n}=\dfrac{x_n^2+a}{2x_n}$ $=\tfrac12\left(x_n+\dfrac a{x_n}\right)$: the average of $x_n$ and $a/x_n$, one of which is below $\sqrt a$ and one above.
(b) Error identity $$x_{n+1}-\sqrt a=\frac{x_n^2-2\sqrt a\,x_n+a}{2x_n}=\frac{(x_n-\sqrt a)^2}{2x_n}.$$ If $x_0\gt0$, all $x_n\gt0$ and the identity shows $x_n\ge\sqrt a$ for every $n\ge1$. Then $x_{n+1}-x_n=\dfrac{a-x_n^2}{2x_n}\le0$, so $(x_n)_{n\ge1}$ is non-increasing and bounded below by $\sqrt a$; its limit $L\gt0$ satisfies $L=\tfrac12(L+a/L)$, i.e. $L=\sqrt a$.
Constant $e_{n+1}/e_n^{\,2}=1/(2x_n)\to1/(2\sqrt a)$, in agreement with $f''(\alpha)/(2f'(\alpha))=2/(4\sqrt a)$.
(c) From $x_0=1$: $x_1=1.5$, $x_2=\tfrac{17}{12}=1.416\,666\ldots$, $x_3=\tfrac{577}{408}=1.414\,215\,686\ldots$, $x_4=1.414\,213\,562\,374\,69\ldots$ The errors are $8.6\times10^{-2}$, $2.5\times10^{-3}$, $2.1\times10^{-6}$, $1.6\times10^{-12}$: the number of correct digits roughly doubles at each step, and $e_{n+1}\approx e_n^2/(2\sqrt2)$.
✏️ Example 4 — A double root: Newton versus modified Newton
Let $f(x)=x^3-3x+2$. Factor $f$, then apply Newton's method and the modified Newton method with $m=2$ from $x_0=2$, and compare the convergence to the root $\alpha=1$.
Factor $f(1)=0$ and $f'(x)=3x^2-3$ gives $f'(1)=0$, $f''(1)=6\ne0$: $\alpha=1$ is a double root, and $f(x)=(x-1)^2(x+2)$. Here $h(x)=x+2$, $h(1)=3$.
Newton $x_{n+1}$ $=x_n-\dfrac{(x_n-1)^2(x_n+2)}{3(x_n-1)(x_n+1)}$ $=x_n-\dfrac{(x_n-1)(x_n+2)}{3(x_n+1)}$. From $x_0=2$: $x_1=1.5556$, $x_2=1.2979$, $x_3=1.1554$, $x_4=1.0796$, $x_5=1.0403$, $x_6=1.0203$. The ratios $e_{n+1}/e_n$ are $0.556,\ 0.536,\ 0.522,\ 0.512,\ 0.506,\ 0.504$ — tending to $1-\tfrac12=\tfrac12$ (Theorem 5.8): linear convergence, one binary digit per step, no better than bisection.
Modified $x_{n+1}=x_n-\dfrac{2(x_n-1)(x_n+2)}{3(x_n+1)}$: $x_1=1.1111$, $x_2=1.001\,949$, $x_3=1.000\,000\,633$, $x_4=1+6.7\times10^{-14}$. Errors $0.111\to1.9\times10^{-3}\to6.3\times10^{-7}$ $\to6.7\times10^{-14}$: quadratic again.
Check By the proof of Theorem 5.8, $e_{n+1}/e_n^{\,2}\to h'(1)/(2h(1))=\tfrac16$; indeed $\dfrac{6.3\times10^{-7}}{(1.95\times10^{-3})^2}\approx0.166$.
✏️ Example 5 — Prove or disprove
(a) If $g:\mathbb{R}\to\mathbb{R}$ is differentiable with $|g'(x)|\lt1$ for every $x$, then $g$ has a fixed point. (b) If $g:\mathbb{R}\to\mathbb{R}$ is differentiable with $|g'(x)|\le L\lt1$ for every $x$, then $x_{n+1}=g(x_n)$ converges for every $x_0$. (c) If $f'\gt0$ and $f''\gt0$ on $\mathbb{R}$ and $f$ has a root, Newton's method converges to it from every $x_0$. (d) If $f'\gt0$ on $\mathbb{R}$ and $f$ has a root, Newton's method converges to it from every $x_0$.
(a) False $g(x)=\sqrt{1+x^2}$ has $|g'(x)|=\dfrac{|x|}{\sqrt{1+x^2}}\lt1$ for all $x$, but $g(x)\gt|x|\ge x$, so $g(x)\ne x$ everywhere. The iterates from $x_0=0$ increase to $\infty$ with steps $x_{n+1}-x_n\to0$. A pointwise bound $|g'|\lt1$ is not a uniform bound $|g'|\le L\lt1$.
(b) True Now $|g(x)-g(y)|\le L|x-y|$ for all $x,y$. Then $|x_{n+1}-x_n|\le L^n|x_1-x_0|$, so for $m\gt n$, $|x_m-x_n|\le\dfrac{L^n}{1-L}|x_1-x_0|$: the sequence is Cauchy and converges to some $\alpha$, and $\alpha=g(\alpha)$ by continuity. (This is the Banach fixed-point theorem on the complete space $\mathbb{R}$.)
(c) True Let $\alpha$ be the root (unique, since $f$ is increasing). The tangent at any $x_0$ lies below the convex graph, so $f(x_1)\ge0$, i.e. $x_1\ge\alpha$ (whatever the side of $x_0$). From $x_1$ on, the proof of Theorem 5.7 (which used only $f'\gt0$, $f''\ge0$ on $[\alpha,x_1]$) shows that $x_n$ decreases to $\alpha$.
(d) False $f(x)=\arctan x$ has $f'\gt0$ and the root $0$, and $x_{n+1}=x_n-(1+x_n^2)\arctan x_n$. If $|x_0|\gt x^*\approx1.3917$, where $x^*$ solves $2x=(1+x^2)\arctan x$, then $|x_1|\gt|x_0|$ with the opposite sign, and the iterates oscillate with $|x_n|\to\infty$. (For $|x_0|=x^*$ exactly they cycle $x^*,-x^*,x^*,\dots$.) Convexity, not just monotonicity, is what saves (c).
Interactive 2 — Five Root-Finders, Step by Step, with the Measured Order

Choose an equation and a method and press Next (or Play). The left panel shows the construction — the bracket of bisection or regula falsi, the secant line, the tangent of Newton. The right panel plots the number of correct digits $-\log_{10}|e_n|$ against $n$: a straight line means linear convergence, an upward-bending curve means order $p\gt1$. The readout $p_n=\log\frac{|e_n|}{|e_{n-1}|}\big/\log\frac{|e_{n-1}|}{|e_{n-2}|}$ estimates the order from three consecutive errors: watch it approach $1$, $1.618$ or $2$.

step n—
x_n—
|e_n|—
estimated order p_n—
f-evaluations—

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.

📘 Definition 5.6 — Secant method; efficiency index

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.

📐 Theorem 5.9 — Order of the secant method

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$. ∎

✏️ Example 6 — Secant method versus regula falsi for $\cos x=x$
Apply regula falsi on $[0,1]$ and the secant method with $x_0=0$, $x_1=1$ to $f(x)=\cos x-x$. Compare the errors with the root $\alpha=0.739\,085\,133\ldots$ and explain the difference using Theorems 5.3 and 5.9.
Data $f(0)=1\gt0$, $f(1)=\cos1-1\approx-0.4597\lt0$; $f'(x)=-\sin x-1\lt0$ and $f''(x)=-\cos x\lt0$ on $[0,1]$.
stepregula falsi $c_n$error
10.685073357$-5.4\times10^{-2}$
20.736298998$-2.8\times10^{-3}$
30.738945356$-1.4\times10^{-4}$
40.739078131$-7.0\times10^{-6}$
50.739084782$-3.5\times10^{-7}$
stepsecant $x_{n+1}$error
10.685073357$-5.4\times10^{-2}$
20.736298998$-2.8\times10^{-3}$
30.739119362$+3.4\times10^{-5}$
40.739085112$-2.1\times10^{-8}$
50.739085133215$-1.6\times10^{-13}$
Same start The first two steps coincide: both methods use the chord through $(0,f(0))$, $(1,f(1))$, and then the chord through $(c_1,f(c_1))$, $(1,f(1))$ — for regula falsi because $f(c_1)\gt0$ replaces the left end, for the secant method because those are the latest two points.
Regula falsi $f(1)f''(1)\gt0$, so by Theorem 5.3 the endpoint $\beta=1$ never moves, the $c_n$ increase to $\alpha$, and the ratio of errors tends to $C=1-\dfrac{f'(\alpha)(1-\alpha)}{f(1)}$ $=1-\dfrac{(-1.6736)(0.2609)}{-0.4597}\approx0.050$ — the table shows ratios $0.052,\ 0.050,\ 0.050$. Linear, though with a small constant.
Secant From step 3 on the secant method uses the two latest points ($c_2$ and $c_1$), which need not bracket the root (the error changes sign), and the digits grow by a factor of about $1.6$ per step: $1.3,\ 2.6,\ 4.5,\ 7.7,\ 12.8$ correct digits.

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.

📘 Definition 5.7 — Newton's method for a system

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).

📐 Theorem 5.10 — Local quadratic convergence for systems
If $F$ is $C^2$ near a zero $\mathbf{x}^*$ and $J(\mathbf{x}^*)$ is nonsingular, then for $\mathbf{x}^{(0)}$ close enough to $\mathbf{x}^*$ Newton's method converges and $\|\mathbf{x}^{(n+1)}-\mathbf{x}^*\|\le M\,\|\mathbf{x}^{(n)}-\mathbf{x}^*\|^2$ for some constant $M$.

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. ∎

✏️ Example 7 — Newton's method for $x^2+y^2=4$, $xy=1$
Find the exact solution of $x^2+y^2=4$, $xy=1$ in the first quadrant with $x\gt y$, perform one Newton step from $(x_0,y_0)=(2,\tfrac12)$ by hand, and describe the following steps.
Exact $(x+y)^2=4+2=6$ and $(x-y)^2=4-2=2$, so $x=\tfrac{\sqrt6+\sqrt2}{2}=1.931\,851\,65\ldots$, $y=\tfrac{\sqrt6-\sqrt2}{2}=0.517\,638\,09\ldots$
Linearise $F=(x^2+y^2-4,\ xy-1)$, $J=\begin{pmatrix}2x&2y\\ y&x\end{pmatrix}$. At $(2,\tfrac12)$: $F=(\tfrac14,0)$ and $J=\begin{pmatrix}4&1\\ \tfrac12&2\end{pmatrix}$.
Solve $4\delta_1+\delta_2=-\tfrac14$, $\ \tfrac12\delta_1+2\delta_2=0$. The second equation gives $\delta_2=-\delta_1/4$, and then $\tfrac{15}{4}\delta_1=-\tfrac14$: $\delta_1=-\tfrac1{15}$, $\delta_2=\tfrac1{60}$. So $(x_1,y_1)=\left(\tfrac{29}{15},\tfrac{31}{60}\right)$ $=(1.933\,33$, $0.516\,67)$.
Next steps The maximum error of the components is $1.5\times10^{-3}$ after one step, then $1.1\times10^{-6}$, $8.0\times10^{-13}$, $4.5\times10^{-25}$: each error is roughly the square of the previous one, as Theorem 5.10 predicts ($J$ is nonsingular at the root since $\det J=2(x^2-y^2)=2\sqrt{12}\ne0$).
🧭 Problem-solving strategy — choosing and stopping a root-finder
  1. 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).
  2. 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.
  3. 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.
  4. 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$.
  5. 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$.
  6. 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).
⚠️ Counterexamples and pitfalls
  1. $|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.
  2. 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.
  3. 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.
  4. 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.
  5. 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$.
  6. 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$.
  7. 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.
  8. 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.
  9. 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$.
  10. 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.
  11. $|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$.
  12. 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

I
Bracketing methods.
  • 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 $f(x)=e^x-3x$: $f(0)=1\gt0$, $f(1)=e-3\lt0$, and $f'(x)=e^x-3\lt0$ on $[0,1]$ (as $e\lt3$), so there is exactly one root there. $c_1=0.5$: $f=0.149\gt0$, keep $[0.5,1]$. $c_2=0.75$: $f=-0.133$, keep $[0.5,0.75]$. $c_3=0.625$: $f=-0.0068$, keep $[0.5,0.625]$. $c_4=0.5625$: $f=0.068$, keep $[0.5625,0.625]$. The root is $\alpha=0.619\,06\ldots$ (and $|c_4-\alpha|=0.057\le2^{-4}$).
2 Need $2^{-n}\le10^{-8}$, i.e. $n\ge8\log_210=26.58$: $n=27$.
3 $f'(x)=5x^4+1\gt0$, so at most one real root; $f(0)=-1$, $f(1)=1$. $c_1=\dfrac{0\cdot1-1\cdot(-1)}{1-(-1)}=\tfrac12$ with $f(\tfrac12)=-0.46875$, so the new interval is $[\tfrac12,1]$; $c_2=\dfrac{0.5\cdot1+0.46875}{1.46875}$ $=\tfrac{31}{47}=0.6596$, $f(c_2)=-0.216$. The root is $0.754\,88$. Since $f''(x)=20x^3\gt0$ on $(0,1]$ and $f(1)f''(1)\gt0$, the end $1$ stays fixed (Theorem 5.3): every chord meets the axis to the left of the root.
4 $f(0)=(-0.1)(-0.4)(-0.8)$ $=-0.032$, $f(1)=0.9\cdot0.6\cdot0.2=0.108$. $c_1=0.5$: $f(0.5)=0.4\cdot0.1\cdot(-0.3)$ $=-0.012\lt0$, so the interval becomes $[0.5,1]$, which contains only the root $0.8$; bisection converges to $0.8$. Which root is found is decided by the signs at the midpoints, not by proximity to the start.
5 $f''=2\gt0$ and $f(2)=2\gt0$, so $\beta=2$ is fixed (Theorem 5.3) and $c_{n}=\dfrac{c_{n-1}\cdot2-2(c_{n-1}^2-2)}{2-(c_{n-1}^2-2)}$ $=\dfrac{2c_{n-1}+2}{c_{n-1}+2}$. From $c_0=1$: $c_1=\tfrac43$, $c_2=\tfrac75$, $c_3=\tfrac{24}{17}$. The ratio tends to $C=1-\dfrac{f'(\sqrt2)(2-\sqrt2)}{f(2)}$ $=1-\sqrt2(2-\sqrt2)=3-2\sqrt2$ $\approx0.1716$ (observed: $0.1757,\ 0.1723,\ 0.1717$).
6 $x_2=2-2\cdot\dfrac{1}{2-(-1)}=\tfrac43$; $x_3=\tfrac75$ (the same as regula falsi so far); $x_4$ $=\tfrac75-\dfrac{(49/25-2)(7/5-4/3)}{49/25-16/9}$ $=\tfrac{58}{41}=1.414\,63$. The error $4.2\times10^{-4}$ is already six times smaller than that of $c_3=\tfrac{24}{17}$ ($2.4\times10^{-3}$), because the secant method discards the stale end point $2$.
7 $(x-1)^2\ge0$ never changes sign, so no starting bracket exists. $(x-1)^3$ changes sign at $1$, so bisection works as usual. Newton: $x_{n+1}=x_n-\tfrac13(x_n-1)$, so $e_{n+1}=\tfrac23e_n$ exactly — linear with ratio $1-\tfrac13$ (Theorem 5.8 with $m=3$), slower than bisection's bound ratio $\tfrac12$.
8 Take $f(x)=\dfrac1{x-1}$ for $x\ne1$ and $f(1)=1$; this $f$ has no root at all. Then $f(0)=-1\lt0\lt\tfrac12=f(3)$; $c_1=1.5$ ($f\gt0$), $c_2=0.75$ ($f\lt0$), and the brackets shrink to $1$, where $f(1)=1\ne0$. Continuity fails at $1$, so the intermediate value theorem (and the last step of the proof of Theorem 5.2) is unavailable.
II
Fixed-point iteration.
  • 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 $g$ is decreasing, so $g([0.4,0.7])=[e^{-0.7},e^{-0.4}]$ $=[0.4966,0.6703]\subseteq[0.4,0.7]$, and $|g'(x)|=e^{-x}\le L=e^{-0.4}=0.6703$. With $|x_1-x_0|=0.6065-0.5=0.1065$, the a priori bound $\dfrac{L^n}{1-L}(0.1065)\le10^{-6}$ needs $n\ge31.7$, i.e. $n=32$. In fact $20$ iterations suffice: the true rate is $|g'(\alpha)|=e^{-\alpha}=\alpha=0.5671$ (the root satisfies $e^{-\alpha}=\alpha$), smaller than the worst case $L$. The convergence oscillates since $g'\lt0$.
2 $g_1'(x)=(2x+3)^{-1/2}$: $g_1'(3)=\tfrac13$, so convergence to $3$ (monotone); $-1$ is not a fixed point of $g_1$ at all, because $\sqrt{2x+3}\ge0$ (taking the square root kept only the positive root). $g_2'(x)=-3/(x-2)^2$: $g_2'(3)=-3$ (repels), $g_2'(-1)=-\tfrac13$ (attracts, oscillating): convergence to $-1$. $g_3'(x)=x$: $g_3'(3)=3$ (repels) and $g_3'(-1)=-1$, where Theorem 5.5 is inconclusive; in fact $e_{n+2}=e_n-\tfrac12e_n^3+O(e_n^4)$, so the iterates do creep towards $-1$, but sublinearly — from $x_0=-0.9$ they are still $0.03$ away after $2000$ steps.
3 $x=2.5x(1-x)$ gives $x=0$ or $x=0.6$. $g'(x)=2.5(1-2x)$: $g'(0)=2.5$ (repelling) and $g'(0.6)=-0.5$ (attracting, oscillating). From $0.1$: $0.225$, $0.4359$, $0.6147$, $0.5921$, $0.6038$, $0.5981$, $0.6010$, $0.5995,\dots$ — the population settles at $0.6$, alternately above and below, the deviation halving each step.
4 With $y=ax_n$: $1-y(3-3y+y^2)$ $=1-3y+3y^2-y^3=(1-y)^3$. Then $e_{n+1}=x_{n+1}-\tfrac1a$ $=-\tfrac1a(1-ax_{n+1})=-\tfrac1a(-ae_n)^3$ $=a^2e_n^{\,3}$: order $3$, constant $a^2$. Since $1-ax_n=(1-ax_0)^{3^n}$, it converges iff $|1-ax_0|\lt1$, i.e. $0\lt x_0\lt2/a$ (no division is ever performed).
5 $x_1=\cos x_0\in[-1,1]$ and $x_2=\cos x_1\in[\cos1,1]=[0.5403,1]$. On $I=[\cos1,1]$, $g=\cos$ is decreasing with $g(I)=[\cos1,\cos(\cos1)]$ $=[0.5403,0.8576]\subseteq I$, and $|g'|=\sin x\le\sin1=0.8415\lt1$. Theorem 5.4 applies from $x_2$. Rate $|g'(\alpha)|=\sin\alpha=0.6736$ ($\alpha=0.739\,085$), oscillating.
6 $g(x)=x+\lambda(x^2-2)$, $g'(\sqrt2)=1+2\sqrt2\lambda=0\iff\lambda$ $=-\dfrac1{2\sqrt2}\approx-0.3536$. Then $g''=2\lambda\ne0$, so the order is exactly $2$ with $e_{n+1}/e_n^{\,2}\to g''(\sqrt2)/2=\lambda=-\dfrac1{2\sqrt2}$. Newton's method uses the variable $\lambda_n=-1/f'(x_n)=-1/(2x_n)$, which tends to this optimal constant; here the optimal $\lambda$ needs $\sqrt2$ itself, which is why Newton's adaptive choice is the practical one.
7 $g$ is continuous (even $1$-Lipschitz), so Theorem 5.4(1) gives a fixed point. Two fixed points $\alpha\ne\beta$ would give $|\alpha-\beta|=|g(\alpha)-g(\beta)|\lt|\alpha-\beta|$. For $g(x)=x-\tfrac12x^2$: $g'(x)=1-x\in[0,1]$, $g([0,1])=[0,\tfrac12]$, and $|g(x)-g(y)|=|1-\xi|\,|x-y|$ $\lt|x-y|$ for $x\ne y$ (as $\xi\gt0$); but $\sup|g'|=1$, so no $L\lt1$ works near $0$. Its fixed point $0$ is reached only sublinearly ($e_{n+1}/e_n=1-\tfrac12x_n\to1$).
8 If $0\lt x_n\le0.5$ then $0\lt x_{n+1}=x_n(1-x_n^2)\lt x_n$, so $x_n\downarrow L$ with $L=L-L^3$, i.e. $L=0$. Next $\dfrac1{x_{n+1}^2}$ $=\dfrac1{x_n^2(1-x_n^2)^2}$ $=\dfrac1{x_n^2}\big(1+2x_n^2+O(x_n^4)\big)$, so the difference tends to $2$, and by Cesàro averaging $1/x_n^2\sim2n$. Indeed $x_{100}=0.0689$ against $1/\sqrt{200}=0.0707$. Since $x_{n+1}/x_n$ tends to $1$, the convergence is sublinear: no order $p\ge1$ in the sense of Definition 5.1.
III
Newton's method.
  • 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 $f'(x)=3x^2-2$. $x_1=2-\tfrac{-1}{10}=2.1$; $x_2=2.1-\tfrac{0.061}{11.23}=\tfrac{11761}{5615}=2.094\,568$; $x_3=2.094\,551\,481\,7$. The root is $2.094\,551\,481\,5\ldots$; errors $5.4\times10^{-3}$, $1.7\times10^{-5}$, $1.6\times10^{-10}$.
2 $f(x)=x^k-a$: $x-\dfrac{x^k-a}{kx^{k-1}}=\dfrac{(k-1)x^k+a}{kx^{k-1}}$, which is the stated formula. For $k=3$, $a=10$: $x_1=\tfrac13(4+\tfrac{10}4)=\tfrac{13}6=2.1667$, $x_2=\tfrac13\big(\tfrac{13}3+\tfrac{360}{169}\big)=\tfrac{3277}{1521}$ $=2.154\,504$; $\sqrt[3]{10}=2.154\,435$ (error $6.9\times10^{-5}$).
3 $f'=-1/x^2$, so $x-\dfrac{1/x-a}{-1/x^2}=x+x-ax^2$ $=x(2-ax)$. Then $1-ax_{n+1}=1-2ax_n+a^2x_n^2$ $=(1-ax_n)^2$, so $1-ax_n=(1-ax_0)^{2^n}$: convergence iff $|1-ax_0|\lt1$, i.e. $0\lt x_0\lt2/a$, quadratically. For $a=7$, $x_0=0.1$: $1-7x_n=0.3$, $0.09$, $0.0081$, $6.6\times10^{-5}$, i.e. $x_1=0.13$, $x_2=0.1417$, $x_3=0.142\,847\,77$, $x_4=0.142\,857\,142\,2$. (Early computers divided this way.)
4 $f'(x)=(1-x)e^{-x}$, $f/f'=x/(1-x)$, so $x_{n+1}=x-\dfrac{x}{1-x}=\dfrac{x^2}{x-1}$. From $x_0=2$: $4,\ \tfrac{16}3,\ 6.564,\ 7.744,\dots$; since $x_{n+1}-x_n=\dfrac{x_n}{x_n-1}\gt1$, $x_n\to\infty$ while $f(x_n)\to0$ — a "false convergence" that a residual test $|f(x_n)|\lt\eta$ would accept. From $x_0=0.5$: $-0.5,\ -0.1667,\ -0.0238,\dots\to0$ (quadratically; the true root). The dividing line is the critical point $x=1$, where $f'=0$.
5 $f'(x)=\tfrac13x^{-2/3}$, so $f/f'=3x$ and $x_{n+1}=x_n-3x_n=-2x_n$: $|x_n|=2^n|x_0|\to\infty$. Theorem 5.6 needs $f\in C^2$ near the root with $f'(\alpha)\ne0$; here $f'$ is not even defined at $0$ (it is infinite).
6 $f(0)=f'(0)=f''(0)=0$ and $f'''(0)=\cos0=1$: multiplicity $3$, $f(x)=x^3h(x)$ with $h(x)=\tfrac16-\tfrac{x^2}{120}+\cdots$. Newton: linear with ratio $\tfrac23$ — from $1$: $0.6551,\ 0.4336,\ 0.2881,\ 0.1918$ (ratios $0.655,\ 0.662,\ 0.665,\ 0.666$). Modified $x-3f/f'$: $-0.0346,\ 1.4\times10^{-6},\ -8.7\times10^{-20}$. By the proof of Theorem 5.8, $e_{n+1}=\rho_3(x_n)e_n$ with $\rho_3(x)$ proportional to $x\,h'(x)$; here $h$ is even, $h'(x)=O(x)$, so $\rho_3(x)=O(x^2)$ and the convergence is cubic ($e_{n+1}\approx-\tfrac1{30}e_n^3$).
7 Taylor about $x_n$ to third order: $0=f(x_n)-f'(x_n)e_n$ $+\tfrac12f''(x_n)e_n^2$ $-\tfrac16f'''(\xi_n)e_n^3$. Hence $e_{n+1}=e_n-\dfrac{f(x_n)}{f'(x_n)}$ $=\dfrac{\tfrac12f''(x_n)e_n^2-\tfrac16f'''(\xi_n)e_n^3}{f'(x_n)}$. Since $f''(\alpha)=0$, $f''(x_n)=f'''(\eta_n)e_n$, so $\dfrac{e_{n+1}}{e_n^{\,3}}=\dfrac{\tfrac12f'''(\eta_n)-\tfrac16f'''(\xi_n)}{f'(x_n)}$ $\to\dfrac{f'''(\alpha)}{3f'(\alpha)}$. For $\sin x$ at $\pi$: $f''(\pi)=-\sin\pi=0$, $f'(\pi)=-1$, $f'''(\pi)=-\cos\pi=1$, constant $-\tfrac13$. Directly: $x_{n+1}=x_n-\tan x_n$, so $e_{n+1}=e_n-\tan e_n=-\tfrac13e_n^3+O(e_n^5)$.
8 $F=(x^2-y-1,\ x+y^2-3)$, $J=\begin{pmatrix}2x&-1\\1&2y\end{pmatrix}$. At $(1,1)$: $F=(-1,-1)$, and $2\delta_1-\delta_2=1$, $\delta_1+2\delta_2=1$ give $\delta=(\tfrac35,\tfrac15)$: $(x_1,y_1)=(1.6,\ 1.2)$. At $(1.6,1.2)$: $F=(0.36,\ 0.04)$, $J=\begin{pmatrix}3.2&-1\\1&2.4\end{pmatrix}$, $\det J=8.68$; $\delta=-J^{-1}F=(-0.104\,15,\ 0.026\,73)$, so $(x_2,y_2)=(1.495\,85,\ 1.226\,73)$. The solution is $(1.492\,573,\ 1.227\,773)$.
IV
Order of convergence, variants and applications.
  • 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.
1 Try $|e_{n+1}|\approx A|e_n|^p$, so $|e_{n-1}|$ $\approx(|e_n|/A)^{1/p}$. Substituting, $A|e_n|^p\approx|C|\,|e_n|^2A^{-1/p}|e_n|^{1/p}$, and matching powers gives $p=2+\tfrac1p$, i.e. $p^2-2p-1=0$, $p=1+\sqrt2\approx2.414$. (Rigorously: $y_n=-\log|e_n|$ obeys $y_{n+1}=2y_n+y_{n-1}+O(1)$, whose dominant root is $1+\sqrt2$.)
2 (a) $e_{n+1}=e_n^2$: order $2$, $C=1$. (b) $e_{n+1}/e_n=\tfrac12$: linear, $C=\tfrac12$. (c) $e_{n+1}/e_n=\tfrac1{n+1}\to0$ (superlinear), but for $p\gt1$, $e_{n+1}/e_n^p=(n!)^{p-1}/(n+1)\to\infty$: superlinear with no order. (d) $e_{n+1}/e_n=\tfrac n{n+1}\to1$: sublinear.
3 $f'=2x$, $f''=2$: $x-\dfrac{4x(x^2-a)}{8x^2-2(x^2-a)}$ $=x-\dfrac{2x(x^2-a)}{3x^2+a}$ $=\dfrac{x(x^2+3a)}{3x^2+a}$. With $x=\sqrt a+e$ one finds $x_{n+1}-\sqrt a=\dfrac{e^3}{4a+6\sqrt a\,e+3e^2}$, so $e_{n+1}/e_n^3\to\tfrac1{4a}$: cubic. For $a=2$, $x_0=1$: $x_1=\tfrac75$, $x_2=\tfrac{1393}{985}=1.414\,213\,198$ (error $3.6\times10^{-7}$; check $3.6\times10^{-7}/(1.42\times10^{-2})^3\approx0.127$ $\approx\tfrac18$).
4 $x_1=1.5-\dfrac{0.0625}{(1.75^2-2)-0.25}$ $=1.5-\tfrac{0.0625}{0.8125}=\tfrac{37}{26}$ $=1.423\,077$, $x_2=1.414\,318\,6$, $x_3=1.414\,213\,577$. Errors $8.9\times10^{-3}$, $1.05\times10^{-4}$, $1.5\times10^{-8}$: each about $1.35\,e_n^2$ — quadratic (the denominator is a divided-difference approximation $f'(x_n)\approx\frac{f(x_n+f(x_n))-f(x_n)}{f(x_n)}$ with step $f(x_n)\to0$). Two evaluations per step: efficiency $\sqrt2$, the same as Newton's.
5 $g(E)=M+e\sin E$ has $|g'(E)|=e|\cos E|\le e\lt1$ on all of $\mathbb{R}$, a uniform contraction, so it converges from every $E_0$ (Example 5(b)). For $M=1$, $e=0.5$ the root is $E=1.498\,701\,1$. Fixed point from $E_0=1$: $1.4207,\ 1.4944,\ 1.4985$ (errors $7.8\times10^{-2}$, $4.3\times10^{-3}$, $1.6\times10^{-4}$, rate $e\cos E\approx0.036$). Newton $E-\dfrac{E-e\sin E-M}{1-e\cos E}$: $1.576\,47,\ 1.500\,208,\ 1.498\,701\,7$ (errors $7.8\times10^{-2}$, $1.5\times10^{-3}$, $5.9\times10^{-7}$).
6 $F(i)$ $=500000\,i-16500\big(1-(1+i)^{-36}\big)$, $F'(i)$ $=500000-16500\cdot36(1+i)^{-37}$. From $i_0=0.01$: $i_1=0.009\,637\,30$, $i_2=0.009\,625\,379$, $i_3=0.009\,625\,366$. So the rate is $0.9625\%$ per month: $11.55\%$ nominal per year, $(1+i)^{12}-1=12.18\%$ effective. Clearing the denominator introduced the spurious root $i=0$ ($F(0)=0$), and Newton started near $0$ may converge to it.
7 $f/f'=x/m$, so $x_{n+1}=x_n-x_n/m=(1-\tfrac1m)x_n$ exactly. For $x^m(1+x)$: $h(x)=1+x$, and by the proof of Theorem 5.8 $x_{n+1}/x_n=\rho_1(x_n)$ $=1-\dfrac{1+x_n}{m(1+x_n)+x_n}$ $\to1-\tfrac1m$, but is not equal to it.
8 $\dfrac{N(z)-1}{N(z)+1}=\dfrac{z^2-2z+1}{z^2+2z+1}=w^2$. So $w_n=w_0^{2^n}$. $\operatorname{Re}z_0\gt0\iff|z_0-1|$ $\lt|z_0+1|\iff|w_0|\lt1$, giving $w_n\to0$, i.e. $z_n\to1$; $\operatorname{Re}z_0\lt0\iff|w_0|\gt1$, $w_n\to\infty$, $z_n\to-1$. On the imaginary axis $|w_0|=1$ and $w_n$ runs around the unit circle under angle doubling — never settling (and $z_n$ stays on the imaginary axis, unless it hits $0$, where $N$ is undefined).
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

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$.

Idea $|c_n-\alpha|\le(b-a)/2^n=2^{-n}$ (Theorem 5.2).
Compute $2^{-n}\lt5\times10^{-4}\iff2^n\gt2000$; $2^{10}=1024$, $2^{11}=2048$. (D) confuses $2^n$ with $n$.
Answer (B) $11$.

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$.

Fixed points $5x=x^2+6\iff x\in\{2,3\}$; $g'(x)=\tfrac{2x}5$: $g'(3)=\tfrac65\gt1$ (repelling), $g'(2)=\tfrac45$ (attracting, monotone).
Start For $2\lt x\lt3$: $g(x)-x=\tfrac{(x-2)(x-3)}5\lt0$ and $g(x)\gt g(2)=2$, so the iterates decrease and stay above $2$: $2.882,\ 2.861,\dots\to2$, with ratio $\to g'(2)=0.8$ (Theorem 5.5). (D) happens for $x_0\gt3$.
Answer (B).

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$.

Idea $2$ is a root of multiplicity $m=3$ ($h(x)=x+1$, $h(2)=3\ne0$); Theorem 5.8: ratio $1-\tfrac1m$.
Answer (C) $\tfrac23$. ((A) would be the simple-root answer; the modified method $x-3f/f'$ restores it.)

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.

(A) True $g$ is a contraction of $\mathbb{R}$ with $L=\tfrac12$ (mean value theorem); Example 5(b) gives existence, and two fixed points would satisfy $|\alpha-\beta|\le\tfrac12|\alpha-\beta|$.
(B) True $|x_n-\alpha|\le2^{-n}|x_0-\alpha|\to0$.
(C) False The correct a priori bound is $\dfrac{L^n}{1-L}|x_1-x_0|=2^{1-n}|x_1-x_0|$. For $g(x)=x/2$, $x_0=1$: $|x_n-0|=2^{-n}$ but $2^{-n}|x_1-x_0|=2^{-n-1}$.
(D) False $g(x)=x/2$: $e_{n+1}=\tfrac12e_n$, linear.
Answer (A) and (B).

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$.

Map $N(x)=x-\dfrac{x^3-5x}{3x^2-5}=\dfrac{2x^3}{3x^2-5}$.
(A) True $N(1)=\tfrac{2}{-2}=-1$ and $N(-1)=1$: a $2$-cycle.
(B) True $f(2)f''(2)=(-2)(12)\lt0$, so the first step overshoots: $x_1=\tfrac{16}7=2.2857\gt\sqrt5$. On $[2,2.3]$ we have $f(2)=-2\lt0\lt f(2.3)=0.667$, $f'=3x^2-5\gt0$ and $f''=6x\gt0$, and $f(x_1)f''(x_1)\gt0$; Theorem 5.7 applied from $x_1$ gives monotone convergence ($2.2376,\ 2.236\,070,\ \dots\to2.236\,068$).
(C) True For $|x|\lt1$: $5-3x^2\gt2$, so $|N(x)|\lt|x|^3$ $\le|x|$; the iterates stay in $(-1,1)$ and $|x_n|\le|x_0|^{3^n}$ $\to0$. Near $0$, $N(x)=-\tfrac25x^3+O(x^5)$; this is the cubic case $f''(0)=0$ of Exercise III.7, with constant $f'''(0)/(3f'(0))=6/(-15)$.
(D) False $x_0=1.2$: $x_1=\dfrac{3.456}{-0.68}=-5.08$, after which the iterates converge to $-\sqrt5$ ($-3.62,\ -2.77,\ -2.36,\ \dots$).
Answer (A), (B) and (C).

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.

(A) True Theorem 5.9.
(B) True Theorem 5.3: $f(b)f''(b)\gt0$, and every chord meets the axis left of $\alpha$.
(C) False Example 1: $|c_4-\alpha|=0.0122$, $|c_5-\alpha|=0.0190$.
(D) True $1.618^{1/1}\gt2^{1/2}=1.414$.
Answer (A), (B) and (D).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. 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.
  2. 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.
  3. 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–Teaching NexusResearch-tutored · optional, about 60 minutes

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.

  1. 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.
  2. 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$.
  3. 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?).
  4. 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.

Instructor note: with tolerance $10^{-12}$ the maximum counts are approximately — fixed point: $12,\ 38,\ 238,\ 2381,\ 22781$ for $e=0.1,0.5,0.9,0.99,0.999$ (growing like $1/(1-e)$, as the contraction constant $e$ predicts); Newton from $E_0=M$: $4,\ 5,\ 8,\ 55$, and for $e=0.999$ some small $M$ do not converge within $200$ steps; Newton from $E_0=\pi$: at most $9$–$10$ for every $e$ in the list. Why the $\pi$ starter is safe: on $[0,\pi]$, $f'(E)=1-e\cos E\gt0$ and $f''(E)=e\sin E\ge0$, and $f(\pi)=\pi-M\ge0$; the proof of Theorem 5.7 uses only $f'\gt0$ and $f''\ge0$ between the current iterate and the root, so Newton from $E_0=\pi$ decreases monotonically to the root for every $M\in(0,\pi]$ and $0\le e\lt1$. The start $E_0=M$ lies on the wrong side ($f(M)=-e\sin M\le0$), and when $e\approx1$ and $M$ is small the tangent there is nearly flat ($f'(M)=1-e\cos M\approx0$), so the first step overshoots far beyond the root.

🧪 Self-check quiz

0/5 correct

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