Chapter 02

Medium

Root-Finding Algorithms

00 · Symbol Glossary

$x^{*}$x star — a root

A number satisfying $f(x^{*})=0$ . The algorithms of this chapter build a sequence meant to converge to some $x^{*}$ . A root is simple when $f$ is differentiable there and $f'(x^{*})\neq 0$ .

$[a_n,b_n]$Bracket — an interval known to contain a root

A closed interval on which a continuous $f$ changes sign, so the intermediate-value theorem supplies at least one root inside. Bisection replaces the bracket by one of its halves and never lets the sign change escape.

$x=g(x)$Fixed-point form of an equation

A rewriting of $f(x)=0$ as "the number equals its own image under $g$ ." The associated iteration is the map $x_{n+1}=g(x_n)$ . Different rewritings of the same equation are different maps.

$L$L — a Lipschitz constant

A number such that $|g(x)-g(y)|\le L|x-y|$ for all $x,y$ in the interval under study. When $L<1$ , $g$ is a contraction: it pulls points closer together by at least the factor $L$ .

$x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$Newton update

The next guess is the place where the tangent line to $y=f(x)$ at $x_n$ crosses the horizontal axis. Calculus 05 drew that tangent. This chapter studies the speed of the resulting sequence, and the ways the step can fail.

$p,\ C$Order of convergence and its asymptotic constant

The error $e_n=x_n-x^{*}$ has order $p\ge 1$ with asymptotic constant $C$ when $|e_{n+1}|/|e_n|^{p}\to C$ with $0<C<\infty$ . Order $1$ is linear convergence and then requires $C<1$ . Order $2$ is quadratic convergence.

$|f(x_n)|$Residual — the function value at the current guess

How far $f(x_n)$ still sits from $0$ . A small residual is one of three stopping tests in this chapter. It measures the equation, which is a different number from the distance $|x_n-x^{*}|$ .

$m$m — multiplicity of a root

The positive integer such that $f(x)=(x-x^{*})^{m}h(x)$ with $h$ continuous and $h(x^{*})\neq 0$ . Simple roots have $m=1$ . For $m\ge 2$ the Newton map converges more slowly, at linear rate $(m-1)/m$ for a pure power.

01 · Solving a Continuous Equation

The problem of this chapter is: given a continuous real function $f$ , find a number $x^{*}$ with

f(x^{*})=0

Polynomials of degree four or less have radical formulas, and a few transcendental equations can be rearranged by hand. Most equations that arise from a derivative set to zero, from a balance of two smooth quantities, or from matching a model to a number, do not. The useful substitute for a closed form is a sequence $x_0,x_1,x_2,\ldots$ together with a theorem that says what the sequence converges to, how fast, and from which starting values.

Every method below is an iterative map. A rule $T$ produces the next object from the previous one: a new number $x_{n+1}=T(x_n)$ , or a new bracket from an old bracket. The mathematical questions are always the same. Does the sequence stay defined? Does it converge? Is the limit a root? How small is $|x_n-x^{*}|$ after $n$ steps, and which hypotheses does that bound use?

Existence is settled before any map is chosen. The intermediate-value theorem says that if $f$ is continuous on a closed bounded interval $[a,b]$ and $f(a)$ and $f(b)$ have opposite signs, then at least one root lies in $(a,b)$ . That sign condition is written $f(a)f(b)<0$ . Continuity is part of the hypothesis. On $[-1,1]$ , the jump that equals $-1$ for $x<0$ and $1$ for $x\ge 0$ changes sign and never hits $0$ .

Definition — Simple Root

Suppose $f$ is differentiable at $x^{*}$ . The root $x^{*}$ is simple when $f(x^{*})=0$ and $f'(x^{*})\neq 0$ . It has multiplicity $m\ge 2$ when $f$ can be factored as $f(x)=(x-x^{*})^{m}h(x)$ with $h$ continuous at $x^{*}$ and $h(x^{*})\neq 0$ . A simple root crosses or touches the axis with nonzero slope. A multiple root has a horizontal tangent.

Plain language: a simple root is a meeting with the axis that still has a tilt. Just to one side the graph is positive and just to the other it is negative, because the slope at the meeting is not zero. A multiple root is a flatter meeting: the graph touches the axis with a horizontal tangent, and the sign need not change at all.

02 · Bisection and a Guaranteed Bracket

Bisection turns the intermediate-value theorem into a sequence of brackets whose lengths form a geometric sequence.

Definition — Bisection

Let $f$ be continuous on $[a,b]$ with $f(a)f(b)<0$ . Set $a_0=a$ and $b_0=b$ . Given a bracket $[a_n,b_n]$ on which $f$ changes sign, let $c_n=(a_n+b_n)/2$ be its midpoint.

If $f(c_n)=0$ , then $c_n$ is a root and the construction stops.
If $f(a_n)f(c_n)<0$ , the next bracket is $[a_n,c_n]$ .
Otherwise $f(c_n)f(b_n)<0$ , and the next bracket is $[c_n,b_n]$ .

Plain language: start with an interval whose ends give opposite signs, so a root is trapped inside. Cut the interval in half, keep the half whose ends still give opposite signs, and throw the other half away. The trapped root stays inside, and the interval that holds it is half as long.

Compare: halving a bracket

Bisection is repeatedly halving a bracket that still holds the root. The midpoint is a sign test, not the answer. Whichever half still changes sign becomes the next bracket, and the root cannot slip out of it.

Proof — The brackets shrink to a root

The endpoints stay ordered, $a_n\le b_n$ , and the length is exactly

b_n-a_n=\frac{b-a}{2^{n}}

Each step replaces one endpoint by the midpoint, so $(a_n)$ is increasing and bounded above, and $(b_n)$ is decreasing and bounded below. A monotone bounded sequence of real numbers converges. The two limits agree, because the gap between $a_n$ and $b_n$ tends to $0$ . Call the common limit $L$ . Then $L$ lies in every bracket.

While the construction has not already stopped on an exact root, $f(a_n)f(b_n)<0$ . Continuity sends $f(a_n)$ and $f(b_n)$ both to $f(L)$ , so the products tend to $f(L)^{2}$ . The limit of negative numbers is at most $0$ , and a square that is at most $0$ is $0$ . Hence $f(L)=0$ .

Plain language: the two endpoints march toward each other, the gap between them is cut in half at every step, and they meet at one number. The signs stayed opposite the whole way, so that meeting point has to be a root.

The nested brackets pick out one root of $f$ on the original interval. If $f$ has several roots in $[a,b]$ , the signs at the midpoints decide which one remains. The midpoint $c_n$ and the root $L$ are both inside $[a_n,b_n]$ , so

|c_n-L|\le \frac{b_n-a_n}{2}=\frac{b-a}{2^{n+1}}

This is an upper bound that holds at every step, with no extra hypothesis on $f'$ . To force the bound under a prescribed tolerance $\varepsilon>0$ , choose $n$ so that $(b-a)/2^{n+1}<\varepsilon$ , that is

n>\log_2\!\left(\frac{b-a}{\varepsilon}\right)-1

That integer is known before the first midpoint is computed. The hypotheses are the continuity of $f$ and one sign change, both checkable at the start.

Definition — Linear Convergence of a Bound

A positive sequence $(E_n)$ converges linearly with rate $r\in(0,1)$ when $E_{n+1}=r\,E_n$ for every $n$ , or more generally when $E_{n+1}/E_n\to r$ . The bisection bound $E_n=(b-a)/2^{n+1}$ has rate $1/2$ : each step buys exactly one factor of two, which is about $0.30$ extra decimal digits.

Plain language: a bound converges linearly when each new allowance is a fixed fraction of the previous one. For bisection that fraction is one half. The guarantee gets steadily tighter — about three tenths of a new decimal digit each step — and the count of steps is known before any midpoint is computed.

Section 04 measures the error $e_n=x_n-x^{*}$ itself. For bisection that ratio need not tend to $1/2$ : the root can sit anywhere inside the current bracket, so a midpoint can land almost on it and the next midpoint can miss by nearly the whole half-length. The quantity that is guaranteed to halve is the bound.

Example — Three bisection steps for $x^2-2$ on $[1,2]$

Here $f(x)=x^2-2$ , $f(1)=-1$ , and $f(2)=2$ . The length starts at $1$ .

c_0=\frac32,\ f\!\left(\frac32\right)=\frac14>0,\quad c_1=\frac54,\ f\!\left(\frac54\right)=-\frac{7}{16}<0,\quad c_2=\frac{11}{8},\ f\!\left(\frac{11}{8}\right)=-\frac{7}{64}<0

The signs send the bracket through $[1,\ 3/2]$ , then $[5/4,\ 3/2]$ , and then $[11/8,\ 3/2]$ , of length $1/8$ . The bound of this section gives $|c_2-\sqrt{2}|\le 1/8$ . The actual gap is about $0.039$ , which sits inside the bound, as a bound requires. The same formula $|c_n-\sqrt{2}|\le 2^{-(n+1)}$ drops below $10^{-3}$ at $n=9$ : the bound is then $1/1024$ , and $1/512$ is still too large.

❌ Starting bisection on an interval that does not change sign

Take $f(x)=x^2$ on $[-1,1]$ . A root sits at $0$ , and $f(-1)f(1)=1>0$ . Every midpoint test is looking for a sign change that the bracket does not contain in its endpoint values. The procedure as stated never begins.

Why it breaks: the intermediate-value theorem was used in the form "opposite signs, hence a root." The converse is false. A continuous function can touch zero and stay non-negative, and a bracket can hide two roots, or a double root, behind endpoints of equal sign. Squaring a simple factor produces exactly this touch.

Consequence: bisection is a method for a bracket you already hold, not a search of the whole line. Producing the first sign change is a separate step. If $f$ does not change sign on any interval you are willing to try, this chapter's guarantee is silent, and a multiple root is a typical reason.

03 · Fixed-Point Iteration and Contractions

Suppose a root of $f$ is rewritten as a number that $g$ leaves fixed.

Definition — Fixed Point and the Iteration

A fixed point of $g$ is a number $x^{*}$ with $x^{*}=g(x^{*})$ . Fixed-point iteration from a start $x_0$ is the sequence

x_{n+1}=g(x_n)

If the sequence converges to $L$ and $g$ is continuous at $L$ , then $L=g(L)$ . Continuity lets the limit pass inside $g$ : the limit of $g(x_n)$ is $g(L)$ , and it is also the limit of $x_{n+1}$ , which is $L$ .

Plain language: a fixed point is a number that $g$ leaves where it is. Iteration feeds each output straight back in as the next input. If the numbers settle and $g$ does not jump at the settling point, that point is a fixed point: the output of the limit and the limit of the outputs are the same number.

A fixed point is where the graph of $g$ crosses the diagonal $y=x$ . Convergence belongs to the chosen $g$ . One equation has many rewritings.

Example — Three maps for one quadratic

The positive root of $x^2-x-1=0$ is $\varphi=(1+\sqrt{5})/2\approx 1.618$ , and $\varphi$ satisfies $\varphi^2=\varphi+1$ . Three continuous rearrangements are

g_1(x)=1+\frac{1}{x},\qquad g_3(x)=\sqrt{x+1},\qquad g_2(x)=x^2-1

each defined near $\varphi$ , with the square root the non-negative one. Differentiating and using $\varphi^2=\varphi+1$ gives

|g_1'(\varphi)|=\frac{3-\sqrt{5}}{2}\approx 0.382,\qquad |g_3'(\varphi)|=\frac{\sqrt{5}-1}{4}\approx 0.309,\qquad |g_2'(\varphi)|=1+\sqrt{5}\approx 3.236

The first two derivatives are strictly smaller than $1$ in absolute value. The third is strictly larger than $1$ . Starting at $1.6$ , the map $g_1$ produces $1.625$ , then $1.61538$ , then $1.61905$ , walking toward $\varphi$ . The map $g_2$ produces $1.56$ , $1.434$ , $1.055$ , $0.113$ , $-0.987$ , and then values alternating near $0$ and $-1$ . Both maps were built from the same equation. Only the first stays with the root.

Definition — Lipschitz Condition and Contraction

A function $g$ on an interval $I$ satisfies a Lipschitz condition with constant $L$ when

|g(x)-g(y)|\le L\,|x-y|\qquad\text{for all }x,y\in I

If $L<1$ , then $g$ is a contraction on $I$ . If $g$ is differentiable on $I$ and $|g'(x)|\le L$ for every $x\in I$ , the mean-value theorem supplies the Lipschitz condition: $g(x)-g(y)=g'(\xi)(x-y)$ for some $\xi$ between $x$ and $y$ , so the absolute value is at most $L|x-y|$ .

Plain language: a Lipschitz condition caps how far apart the outputs of $g$ can be. They stretch by at most a fixed factor $L$ times the gap between the inputs. When $L<1$ , $g$ is a contraction: every pair of points on the interval is pulled strictly closer, and the same factor works everywhere on that interval.

Compare: a map that pulls points closer

A contraction is a map that always pulls points closer. The distance between $g(x)$ and $g(y)$ is at most $L$ times the distance between $x$ and $y$ , with $L<1$ . Continuity only keeps nearby points nearby. A contraction shortens every gap by one uniform factor.

Proof — Banach Fixed-Point Theorem on a Closed Interval

Let $g$ send a closed bounded interval $[a,b]$ into itself, and let $g$ be a contraction on $[a,b]$ with constant $L<1$ .

The image condition keeps every iterate inside $[a,b]$ : if $x_0\in[a,b]$ , then $x_1=g(x_0)\in[a,b]$ , and so on. The contraction turns one step into the next,

|x_{k+1}-x_k|=|g(x_k)-g(x_{k-1})|\le L\,|x_k-x_{k-1}|\le L^{k}|x_1-x_0|

For $m>n$ , the telescope from $x_n$ to $x_m$ is a piece of a geometric series:

|x_m-x_n|\le \big(L^{n}+L^{n+1}+\cdots+L^{m-1}\big)\,|x_1-x_0|\le \frac{L^{n}}{1-L}\,|x_1-x_0|

The right-hand side tends to $0$ as $n\to\infty$ , uniformly in $m$ . A sequence of real numbers whose gaps from index $n$ onward are dominated by a convergent geometric series converges to some limit $x^{*}$ . The limit lies in $[a,b]$ because the interval is closed. Lipschitz continuity gives $|g(x_n)-g(x^{*})|\le L|x_n-x^{*}|\to 0$ , so $g(x_n)\to g(x^{*})$ . The left side is $x_{n+1}$ , whose limit is $x^{*}$ . Therefore $x^{*}=g(x^{*})$ . If $y=g(y)$ as well, then $|x^{*}-y|=|g(x^{*})-g(y)|\le L|x^{*}-y|$ , so $(1-L)|x^{*}-y|\le 0$ and $y=x^{*}$ .

The same geometric estimate yields the rate. By induction $|x_n-x^{*}|\le L^{n}|x_0-x^{*}|$ , and the latest step controls the unknown gap:

|x^{*}-x_{n+1}|\le \frac{L}{1-L}\,|x_{n+1}-x_n|

Plain language: if a contraction sends a closed interval into itself, repeated application is squeezed toward a single point inside that interval, and that point is the only number the map leaves fixed. The latest step already reports the remaining gap: it is at most $L/(1-L)$ times the size of that step.

For $g_1(x)=1+1/x$ on $I=[3/2,\ 2]$ both hypotheses hold. The map is decreasing from $g_1(3/2)=5/3$ to $g_1(2)=3/2$ , so the image $[3/2,\ 5/3]$ sits inside $I$ , and $|g_1'(x)|=1/x^2\le 4/9$ on $I$ . The theorem supplies a unique fixed point in $I$ , namely $\varphi$ , and a geometric rate $(4/9)^n$ .

Local attraction from the derivative at the fixed point

Suppose $g'$ is continuous, $g(x^{*})=x^{*}$ , and $|g'(x^{*})|<1$ . Choose $L$ with $|g'(x^{*})|<L<1$ . Continuity of $g'$ gives a small closed interval $I$ about $x^{*}$ on which $|g'|\le L$ . On that interval $|g(x)-x^{*}|=|g(x)-g(x^{*})|\le L|x-x^{*}|$ , so $g$ sends $I$ into itself. The Banach theorem on $I$ says that every start in $I$ converges to $x^{*}$ . If instead $|g'(x^{*})|>1$ , no such $L<1$ exists on any neighborhood, and starts other than $x^{*}$ itself are pushed away at the first step: the mean-value theorem gives $|x_1-x^{*}|\approx |g'(x^{*})|\,|x_0-x^{*}|>|x_0-x^{*}|$ . The borderline $|g'(x^{*})|=1$ is not covered by either conclusion.

❌ Cycling where the derivative at the fixed point has absolute value one

The map $g(x)=2/x$ has fixed point $\sqrt{2}$ , because $x=2/x$ is $x^2=2$ for $x>0$ . From the start $x_0=1$ the iteration is $2,\ 1,\ 2,\ 1,\ \ldots$ and never approaches $\sqrt{2}$ .

Why it breaks: $g'(x)=-2/x^2$ and $|g'(\sqrt{2})|=1$ , so the strict contraction test fails at the root itself. On the interval $[1,2]$ the map does send the interval to itself, but the best Lipschitz constant is $2$ , from $|g'(1)|=2$ . The Banach hypothesis $L<1$ is false, and the iteration has a second orbit, the two-cycle, that the fixed-point theorem says nothing to prevent.

Consequence: algebra can exhibit a fixed point while the iteration diverges, cycles, or converges to a different fixed point of the same $g$ . The derivative, or a Lipschitz constant on a stated interval, is the part of the work that decides which.

One more identity is worth having before Newton's method, because Newton is a fixed-point map with a special derivative. If $g'$ is continuous at a fixed point and the iteration converges to it, then

\frac{x_{n+1}-x^{*}}{x_n-x^{*}}=g'(\xi_n)\to g'(x^{*})

for some $\xi_n$ between $x_n$ and $x^{*}$ , by the mean-value theorem. Whenever $g'(x^{*})\neq 0$ , the errors form a linear sequence with rate $|g'(x^{*})|$ . Whenever $g'(x^{*})=0$ , that rate is $0$ : the error shrinks faster than every linear rate. Newton's method is built so that this second case happens at a simple root.

04 · Order of Convergence

Definition — Order and Asymptotic Constant

Let $e_n=x_n-x^{*}$ and suppose $e_n\neq 0$ for every $n$ , with $e_n\to 0$ . The convergence has order $p\ge 1$ and asymptotic constant $C$ when

\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_n|^{p}}=C\qquad\text{for some }C\text{ with }0<C<\infty

Order $1$ is linear convergence, and it describes a sequence that actually tends to zero only when $C<1$ . Order $2$ is quadratic convergence. The convergence is superlinear when $|e_{n+1}|/|e_n|\to 0$ , which holds for every order $p>1$ .

Plain language: the order is a report on how the error shrinks each step. Order $1$ multiplies the error by roughly the same factor $C$ every time, and the error actually tends to zero only when that factor is smaller than $1$ . Order $2$ squares the error, up to the constant $C$ , so once the miss is a small fraction the number of correct digits roughly doubles.

Compare: how the error shrinks

Order of convergence describes how the error shrinks each step. Linear convergence trims a fixed share of whatever error remains. Quadratic convergence replaces the error by something on the scale of its square: a miss of a thousandth can become a miss of about a millionth. The asymptotic constant $C$ is the multiplier in front of that shrinkage once the guesses are close.

Linear convergence multiplies the error by about the same factor $C$ each step, so the number of correct digits grows by a fixed amount. Quadratic convergence squares the error, up to $C$ , and once the error is below $1$ that roughly doubles the number of correct digits. The fixed-point identity of Section 03 is the order statement for a map with $g'(x^{*})\neq 0$ : the order is $1$ and $C=|g'(x^{*})|$ . If $g'(x^{*})=0$ and $g''$ is continuous, one more term of Taylor's theorem raises the order. Then $g(x)=g(x^{*})+g'(x^{*})(x-x^{*})+\frac12 g''(\xi)(x-x^{*})^2$ , so $e_{n+1}=\frac12 g''(\xi_n)\,e_n^2$ and

\frac{|e_{n+1}|}{|e_n|^{2}}\to \frac12\,|g''(x^{*})|

provided the limit on the right is positive. The order is then exactly $2$ . If that second derivative also vanishes, the order is higher still. Newton's method is the systematic way to choose a $g$ whose first derivative vanishes at the root.

05 · Newton's Method and Quadratic Convergence

Calculus 05 already drew the picture. The tangent line to $y=f(x)$ at a guess $x_n$ is $y=f(x_n)+f'(x_n)(x-x_n)$ . Setting $y=0$ and solving for $x$ produces the next guess, provided the tangent is not horizontal.

Definition — Newton's Method

For $f$ differentiable and $f'(x_n)\neq 0$ ,

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}

Equivalently, $x_{n+1}=g(x_n)$ with the Newton map $g(x)=x-f(x)/f'(x)$ , defined wherever $f'(x)\neq 0$ .

Plain language: at the current guess, draw the line that grazes the graph, and follow that line until it hits the horizontal axis. The hitting point is the next guess. In numbers, that is the current guess minus the height $f(x_n)$ divided by the slope $f'(x_n)$ .

Compare: follow the tangent to the axis

Newton's method follows the tangent until it hits the axis. For one step the curve is replaced by the straight line that matches its height and its slope at $x_n$ . Where that line meets $y=0$ is $x_{n+1}$ . A horizontal tangent never meets the axis, so the step has nowhere to land.

The derivative of this particular $g$ explains the speed. Where $f'$ is differentiable and nonzero,

g'(x)=\frac{f(x)\,f''(x)}{\big(f'(x)\big)^{2}}

At a simple root the factor $f(x^{*})$ is zero and the denominator is not, so $g'(x^{*})=0$ . Section 04 then predicts quadratic convergence as soon as $g''$ is continuous near $x^{*}$ , which for this $g$ follows from $f$ being three times continuously differentiable, or by the direct Taylor argument below, which needs only two continuous derivatives.

Proof — Quadratic Error for a Simple Root

Assume $f(x^{*})=0$ , $f'(x^{*})\neq 0$ , and $f''$ continuous on a neighborhood of $x^{*}$ . Taylor expansion with remainder, centered at a current guess $x_n$ near $x^{*}$ , gives a point $\xi_n$ between $x_n$ and $x^{*}$ such that

0=f(x^{*})=f(x_n)+f'(x_n)(x^{*}-x_n)+\frac12 f''(\xi_n)(x^{*}-x_n)^{2}

For $x_n$ near $x^{*}$ , continuity of $f'$ and $f'(x^{*})\neq 0$ keep $f'(x_n)\neq 0$ . Dividing by $f'(x_n)$ and rearranging gives

e_{n+1}=\frac{f''(\xi_n)}{2\,f'(x_n)}\,e_n^{2}

On a small enough neighborhood one has $|f''|\le M$ and $|f'|\ge m>0$ , so $|e_{n+1}|\le K|e_n|^{2}$ with $K=M/(2m)$ . Choose the neighborhood also small enough that $K|e_n|\le 1/2$ throughout it, and start with $x_0$ inside it. Then $|e_{n+1}|\le \tfrac12 |e_n|$ , so the iterates stay inside the neighborhood and $e_n\to 0$ . Once the error tends to zero, $\xi_n\to x^{*}$ and $x_n\to x^{*}$ , and

\frac{|e_{n+1}|}{|e_n|^{2}}\to \left|\frac{f''(x^{*})}{2\,f'(x^{*})}\right|

whenever $f''(x^{*})\neq 0$ . That limit is the asymptotic constant. If $f''(x^{*})$ happens to vanish, the order is higher than $2$ and the same proof still gives convergence.

Plain language: near a simple root the tangent is a faithful stand-in for the graph, and the leftover miss is proportional to the square of the current miss. Each successful step therefore squares the error. The correct digits start to double once the guess is close enough to stay in that neighborhood.

Example — Square root of two, with an exact ratio

Let $f(x)=x^2-2$ , so $f'(x)=2x$ and $f''(x)=2$ . From $x_0=1$ ,

x_1=\frac32,\qquad x_2=\frac{17}{12},\qquad x_3=\frac{577}{408}

Because $f''$ is the constant $2$ , the error identity is exact: $e_{n+1}=e_n^{2}/(2x_n)$ . Thus $|e_1|/|e_0|^{2}=1/2$ and $|e_2|/|e_1|^{2}=1/3$ . With $\sqrt{2}\approx 1.414213562$ the absolute errors are about $4.14\times 10^{-1}$ , $8.58\times 10^{-2}$ , $2.45\times 10^{-3}$ , and $2.12\times 10^{-6}$ . The asymptotic constant $1/(2\sqrt{2})\approx 0.3536$ equals $|f''(\sqrt{2})/(2f'(\sqrt{2}))|$ , and the third ratio $6/17\approx 0.3529$ has already met it.

❌ A horizontal tangent at a non-root

The update divides by $f'(x_n)$ . Calculus 05 recorded $f(x)=x^3-3x$ at $x_0=1$ : there $f'(1)=0$ and $f(1)=-2\neq 0$ , so the Newton formula asks for a division by zero.

Why it breaks: the tangent line at $x_0$ is horizontal, and a horizontal line at height $-2$ does not meet the axis. There is no next real iterate. A horizontal tangent at the root itself is the multiple-root case of Section 08: the formula is undefined at $x^{*}$ , and where it is defined the order drops from $2$ to $1$ .

Consequence: before a Newton step is legal, $f'(x_n)$ has to be checked nonzero. A simple root guarantees that only in a neighborhood of $x^{*}$ , not at every guess on the line.

❌ A Newton orbit that cycles and never approaches a root

Let $f(x)=x^3-2x+2$ . Then $f'(x)=3x^2-2$ . Starting at $x_0=0$ ,

x_1=0-\frac{f(0)}{f'(0)}=0-\frac{2}{-2}=1,\qquad x_2=1-\frac{f(1)}{f'(1)}=1-\frac{1}{1}=0

The iteration alternates $0,1,0,1,\ldots$ forever. Neither value is a root: $f(0)=2$ and $f(1)=1$ .

Why it breaks: the quadratic-convergence theorem is a statement about starts inside some neighborhood of a simple root. It is silent about a start outside every such neighborhood. Here the Newton map sends $0$ to $1$ and $1$ to $0$ , a periodic orbit of period $2$ . Along that orbit $f'$ is $-2$ and $1$ , both nonzero, so every individual step is defined. Defined steps can still form a cycle.

Consequence: a derivative that never vanishes is not a convergence proof. Newton needs a start already close to a simple root, or some other structure that forces the iterates into that neighborhood. When that structure is absent, the sequence may cycle or march to infinity. Bisection, given a genuine bracket, cannot cycle. The price of its guarantee is the linear bound of Section 02.

06 · The Secant Method

Newton's step uses the slope of a tangent. Replacing that slope by the slope of the chord through the two latest guesses removes the need to differentiate $f$ .

Definition — Secant Method

From two starts $x_0$ and $x_1$ with $f(x_1)\neq f(x_0)$ ,

x_{n+1}=x_n-f(x_n)\,\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}

The fraction is the reciprocal of the difference quotient $(f(x_n)-f(x_{n-1}))/(x_n-x_{n-1})$ , which approximates $f'(x_n)$ . The formula is the Newton update with that approximation in place of $f'(x_n)$ .

Plain language: draw the straight line through the two latest guesses instead of the tangent, and take the place where that chord hits the axis. The slope of the chord stands in for $f'(x_n)$ , so the derivative is never required. If the two function values agree, the chord is horizontal and there is no next guess.

If $f(x_n)=f(x_{n-1})$ , the chord is horizontal and the next guess is undefined. Nothing in the formula forces $x_{n+1}$ to lie between $x_{n-1}$ and $x_n$ , so the method does not maintain a sign-change bracket.

The order is derived from a two-step error relation. Under the same smoothness used for Newton, a simple root, and starts close enough to it, the chord error satisfies

e_{n+1}\approx C\,e_n\,e_{n-1},\qquad C=\frac{f''(x^{*})}{2\,f'(x^{*})}

The constant is the Newton constant. The product of two successive errors, rather than the square of one, is the footprint of a chord: each new error is proportional to both previous errors. To read an order off this relation, look for $p$ and $K>0$ such that $|e_{n+1}|\sim K|e_n|^{p}$ . Then $|e_{n-1}|\sim (|e_n|/K)^{1/p}$ . Substitute into $|e_{n+1}|\approx |C|\,|e_n|\,|e_{n-1}|$ :

\frac{|e_{n+1}|}{|e_n|^{p}}\approx |C|\,K^{-1/p}\,|e_n|^{1+1/p-p}

The power of $|e_n|$ has to be zero, otherwise the ratio tends to $0$ or to $\infty$ and cannot tend to a positive finite limit. Hence $p=1+1/p$ , so $p^2-p-1=0$ and

p=\frac{1+\sqrt{5}}{2}\approx 1.618

Under the standard hypotheses — $f''$ continuous, $x^{*}$ a simple root, and both starts close enough that the denominators stay nonzero — the secant method therefore converges superlinearly, of order equal to the golden ratio, strictly between the linear bound of bisection and the quadratic rate of Newton.

Example — Two secant steps for $x^2-2$

Take $x_0=1$ , $x_1=2$ , $f(x)=x^2-2$ , so $f(x_0)=-1$ and $f(x_1)=2$ . The chord through those two guesses meets the axis at $4/3$ ; the next chord, through $2$ and $4/3$ , meets it at $7/5$ :

x_2=2-\frac23=\frac43,\qquad f\!\left(\frac43\right)=-\frac29,\qquad x_3=\frac43+\frac{1}{15}=\frac75

The errors against $\sqrt{2}$ are about $0.081$ at $x_2$ and about $0.014$ at $x_3$ . The drop is faster than halving and slower than the Newton drop from $3/2$ to $17/12$ in Section 05, which is the order $1.618$ sitting between $1$ and $2$ .

❌ Expecting a sign-change chord to move both ends of the bracket

Apply the bracket-preserving chord to $f(x)=x^2-2$ on $[1,2]$ . The first point is $4/3$ , where $f$ is negative, so the new bracket is $[4/3,\ 2]$ . The next point is $7/5$ , where $f$ is again negative, so the bracket is $[7/5,\ 2]$ . The right endpoint is still $2$ .

Why it breaks: $f(x)=x^2-2$ is strictly convex, so on an interval where it changes sign the chord lies above the graph. The chord's root therefore lies to the left of $\sqrt{2}$ , the new function value is negative, and the positive endpoint is never the one replaced. Every later bracket has the form $[a_n,\ 2]$ with $a_n$ increasing toward $\sqrt{2}$ and the right end frozen.

Consequence: keeping the bracket restores a guarantee of convergence and gives up the golden-ratio order. With one end frozen, the errors behave linearly. The secant method of the definition above does not freeze an endpoint, and it also does not promise to stay inside $[1,2]$ . A chord is not a bracket unless the update says so.

07 · When to Stop

Definition — Three Stopping Tests

For a tolerance $\varepsilon>0$ , and a current pair of iterates,

Residual test: $|f(x_n)|<\varepsilon$ .
Absolute step test: $|x_{n+1}-x_n|<\varepsilon$ .
Relative step test: $|x_{n+1}-x_n|\le \varepsilon\,|x_{n+1}|$ , used when $x_{n+1}$ is bounded away from zero.

Plain language: three different questions can stop the iteration. The residual asks whether the equation is already nearly true. The absolute step asks whether the latest move was tiny on its own. The relative step asks whether that move is tiny compared with the size of the guess. A yes to one of them is not, by itself, a certificate that the guess sits within $\varepsilon$ of the root.

The residual asks how nearly the equation holds. The step tests ask how much the map is still moving. For a contraction, the Banach bound of Section 03 converts a step into a root error: $|x^{*}-x_{n+1}|\le L|x_{n+1}-x_n|/(1-L)$ . A step smaller than $\varepsilon$ does not mean a root error smaller than $\varepsilon$ unless $L/(1-L)$ is taken into account. If $L=4/9$ , that factor is $4/5$ , and the step is already a faithful stand-in for the error. If $L=0.99$ , the factor is $99$ , and a tiny step can hide a large remaining gap.

The residual is converted by the mean-value theorem. If $f(x^{*})=0$ and $f'$ exists between $x_n$ and $x^{*}$ , then $f(x_n)=f'(\xi)(x_n-x^{*})$ for some $\xi$ , so

|x_n-x^{*}|=\frac{|f(x_n)|}{|f'(\xi)|}

A small residual certifies a small root error when $|f'|$ is bounded below by a comfortable positive number near the root. A flat graph, $|f'|$ tiny, turns a modest residual into a large uncertainty in $x$ . A steep graph does the reverse: the residual can still look large when $x_n$ is already close to $x^{*}$ .

Example — Residual and error on a flat graph and on a steep one

For $f(x)=x^3$ at $x=0.1$ , the residual is $|f(0.1)|=0.001$ and the root error is $0.1$ . The residual is one hundred times smaller than the error. For $f(x)=1000(x-1)$ at $x=1.001$ , the residual is $1$ and the root error is $0.001$ . The residual is one thousand times larger than the error. In the first case a residual tolerance of $10^{-3}$ accepts a guess that is still a tenth away from the root. In the second, a residual tolerance of $10^{-3}$ rejects a guess that is already accurate to a thousandth.

Chapter 01 measured rounding by machine epsilon: a computed value of $f(x_n)$ agrees with the mathematical value only up to a small multiple of that epsilon, the multiple depending on how $f$ is built from arithmetic operations. A residual test with $\varepsilon$ many times smaller than the rounding error in $f(x_n)$ is comparing the iteration with digits the evaluation does not contain. Likewise, once $|x_{n+1}-x_n|$ drops to a few units in the last place of $x_n$ , further steps are changes the number system cannot represent. The conditioning relation above says how that rounding enters the root. An error of size about machine epsilon in the value of $f$ is consistent with an error of size about machine epsilon divided by $|f'(x^{*})|$ in the root. A simple root with a very small derivative is an ill-conditioned root: the iteration can be exactly the Newton map and the computed $x_n$ can still be uncertain in digits that the stopping test appears to have settled.

Reading the residual and the step together uses both identities. A residual that shrinks while the step stays large fits a flat graph. A step that shrinks while the residual stays large fits a steep graph, or a stalled orbit such as the two-cycle of Section 05, where the step is eventually $1$ and the residual is $1$ or $2$ .

08 · Multiple Roots

Suppose $f(x)=(x-x^{*})^{m}h(x)$ with $m\ge 2$ , $h$ smooth, and $h(x^{*})\neq 0$ . Then $f(x^{*})=f'(x^{*})=0$ . The Newton update divides by a derivative that vanishes at the root, so the theorem of Section 05 does not apply. The iteration can still converge. The order drops.

For a pure power $f(x)=(x-x^{*})^{m}$ and $x_n\neq x^{*}$ ,

\frac{f(x_n)}{f'(x_n)}=\frac{x_n-x^{*}}{m}

so the Newton map simplifies to $g(x)=x-(x-x^{*})/m$ and $g'(x)=(m-1)/m$ . The error is exactly linear:

x_{n+1}-x^{*}=\frac{m-1}{m}\,(x_n-x^{*})

The rate $(m-1)/m$ lies in $(0,1)$ . A double root has rate $1/2$ , and a triple root has rate $2/3$ . The Newton derivative $g'(x^{*})$ equals that rate, so the convergence is linear.

Example — The double root of $(x-1)^2$

Let $f(x)=(x-1)^2$ . For $x_n\neq 1$ the update is $x_{n+1}=(x_n+1)/2$ , so $x_{n+1}-1=(x_n-1)/2$ . From $x_0=3$ the iterates are $2$ , $1.5$ , $1.25$ , $1.125$ , and the errors are $2$ , $1$ , $1/2$ , $1/4$ , $1/8$ . Each error is half the one before it, matching $(m-1)/m=1/2$ . At $x_2=1.5$ the residual is $f(1.5)=0.25$ , while the root error is $0.5$ . The residual is the square of the error, so it understates the distance to the root, in line with the flat-graph warning of Section 07.

If the multiplicity $m$ is known, the modified update $x_{n+1}=x_n-m\,f(x_n)/f'(x_n)$ multiplies the correction by $m$ . On a pure power that modified map hits $x^{*}$ in a single step. For a general factor $h(x^{*})$ the same multiple restores $g'(x^{*})=0$ and, with it, quadratic convergence. When $m$ is unknown, the quotient $u=f/f'$ has a simple root at $x^{*}$ for a pure power, since $u(x)=(x-x^{*})/m$ , and Newton's method applied to $u$ falls back under the theorem of Section 05. Either repair uses extra knowledge or an extra derivative. Neither is free, and both exist because the unmodified rate $(m-1)/m$ is the generic price of a horizontal tangent at the root.

09 · Exercises

EXERCISE 2.1

Keep the half on which the function values at the endpoints have opposite signs. The midpoint error after $n$ steps is at most $2^{-(n+1)}$ on a bracket of length $1$ . Compare $2^{-10}$ with $10^{-3}$ .

(a) $f(1)=-1$ and $f(2)=5$ . The midpoint $3/2$ has $f(3/2)=27/8-3/2-1=7/8>0$ , so the bracket becomes $[1,\ 3/2]$ . The midpoint $5/4$ has $f(5/4)=125/64-5/4-1=-19/64<0$ , so the bracket becomes $[5/4,\ 3/2]$ . The midpoint $11/8$ has $f(11/8)=1331/512-11/8-1=115/512>0$ , so the bracket becomes $[5/4,\ 11/8]=[1.25,\ 1.375]$ . (b) The third midpoint is $c_2=11/8$ , taken from a bracket of length $1/4$ , so $|c_2-x^{*}|\le (1/4)/2=1/8$ . (c) The midpoint bound is $2^{-(n+1)}$ . This drops below $10^{-3}$ when $n+1\ge 10$ , since $2^{-10}=1/1024<10^{-3}$ and $2^{-9}=1/512>10^{-3}$ . The smallest such $n$ is $9$ .

Let $f(x)=x^3-x-1$ . Then $f$ is continuous, $f(1)=-1$ , and $f(2)=5$ . (a) Carry out three bisection steps from $[1,2]$ , and record the bracket after each step. (b) Bound the distance from the third midpoint to a root. (c) Find the smallest index $n$ such that the bound on $|c_n-x^{*}|$ is below $10^{-3}$ , where $c_0$ is the first midpoint.

EXERCISE 2.2

On $[0,1]$ , cosine is decreasing and positive. A bound on $|\sin x|$ is a Lipschitz constant, by the mean-value theorem. The a posteriori factor is $L/(1-L)$ times the latest step, with $L=\sin 1$ .

(a) Cosine decreases on $[0,1]$ , from $\cos 0=1$ to $\cos 1$ . Since $0<\cos 1<1$ , the image is $[\cos 1,\ 1]\subseteq[0,1]$ . And $|g'(x)|=\sin x\le \sin 1<1$ on the interval, so $|g(x)-g(y)|\le (\sin 1)\,|x-y|$ . (b) The Banach theorem gives a unique fixed point in $[0,1]$ , and every start in the interval converges to it. (c) $x_1=\cos 0=1$ and $x_2=\cos 1$ . The step is $|1-\cos 1|$ . With $L/(1-L)=\sin 1/(1-\sin 1)$ , the bound is $|x^{*}-x_2|\le \dfrac{\sin 1}{1-\sin 1}\,\lvert 1-\cos 1\rvert$ .

Let $g(x)=\cos x$ on the interval $[0,1]$ , with $x$ in radians. (a) Show that $g$ maps the interval into itself and is a contraction with constant $L=\sin 1$ . (b) Conclude that the equation $x=\cos x$ has a unique solution in $[0,1]$ , and that iteration from any start in the interval converges to it. (c) From $x_0=0$ , compute $x_1$ and $x_2$ , and write the a posteriori bound on $|x_2-x^{*}|$ .

EXERCISE 2.3

The Newton correction for $x^2-2$ is $(x^2-2)/(2x)$ . Because $f''$ is constant, $e_{n+1}=e_n^2/(2x_n)$ . The asymptotic constant is $|f''(\sqrt{2})/(2f'(\sqrt{2}))|$ . The update at $0$ divides by $f'(0)$ .

(a) $x_1=1- (1-2)/2=3/2$ . Then $x_2=3/2-( (9/4)-2 )/3=3/2-(1/4)/3=3/2-1/12=17/12$ . Then $x_3=17/12 - ( (289/144)-2 ) / (17/6)=17/12-1/408=577/408$ . (b) Here $e_{n+1}=e_n^2/(2x_n)$ , so $|e_1|/|e_0|^2=1/2$ and $|e_2|/|e_1|^2=1/3$ . The limit constant is $2/(2\cdot 2\sqrt{2})=1/(2\sqrt{2})\approx 0.3536$ . The ratios $1/2$ and $1/3$ are the exact finite- $n$ values $1/(2|x_n|)$ , and they approach $1/(2\sqrt{2})$ as $x_n$ approaches $\sqrt{2}$ . (c) $f'(x)=2x$ , so $f'(0)=0$ . The Newton update divides by $f'(0)$ and is undefined. The tangent to $y=x^2-2$ at $x=0$ is the horizontal line $y=-2$ , which does not meet the axis.

Let $f(x)=x^2-2$ and $x_0=1$ . (a) Compute the first three Newton iterates as exact fractions. (b) Show that $|e_1|/|e_0|^2=1/2$ and $|e_2|/|e_1|^2=1/3$ , and compare these with $|f''(\sqrt{2})/(2f'(\sqrt{2}))|$ . (c) Explain why the iteration is undefined at the start $x_0=0$ .

EXERCISE 2.4

For $f(x)=(x-1)^2$ and $x\neq 1$ , the quotient $f(x)/f'(x)$ equals $(x-1)/2$ . The modified correction multiplies that quotient by $2$ . Compare $f(x_2)$ with $|x_2-1|$ directly from the halved errors.

(a) $f'(x)=2(x-1)$ , so for $x_n\neq 1$ one has $f(x_n)/f'(x_n)=(x_n-1)/2$ and $x_{n+1}=x_n-(x_n-1)/2=(x_n+1)/2$ . Hence $x_{n+1}-1=(x_n-1)/2$ . (b) The error is multiplied by $1/2$ at every step, so $|e_{n+1}|/|e_n|\to 1/2$ . The order is $1$ and the asymptotic constant is $1/2$ . (c) From $x_0=3$ the next two iterates are $x_1=2$ and $x_2=3/2$ . The true error is $|3/2-1|=1/2$ , while the residual is $f(3/2)=1/4$ . The residual is smaller than the root error. A residual test alone would describe this guess as twice as accurate as it is, which is the flat-graph gap of a multiple root: $f'(1)=0$ . (d) The modified update subtracts $2\cdot (x-1)/2=x-1$ , so it returns $x-(x-1)=1$ from every $x\neq 1$ .

Let $f(x)=(x-1)^2$ . (a) Show that Newton's method gives $x_{n+1}-1=(x_n-1)/2$ whenever $x_n\neq 1$ . (b) Deduce the order and the asymptotic constant. (c) Starting from $x_0=3$ , compute $|f(x_2)|$ and $|x_2-1|$ , and say what the comparison means for a residual test. (d) Show that the modified update $x-2f(x)/f'(x)$ reaches the root in one step.

10 · Chapter Summary

Object	What the theorem uses
Sign-change bracket	Continuous $f$ with $f(a)f(b)<0$ ; bisection keeps one root and halves the bound
Bisection bound	$\lvert c_n-x^{*}\rvert\le (b-a)/2^{n+1}$ , linear with rate $1/2$
Fixed-point map	$x_{n+1}=g(x_n)$ ; the limit is a fixed point when $g$ is continuous
Contraction	$g([a,b])\subseteq[a,b]$ and Lipschitz constant $L<1$ ; unique fixed point, geometric rate
Local test	$\lvert g'(x^{})\rvert<1$ attracts nearby starts; $\lvert g'(x^{})\rvert>1$ repels them
Order $p$	$\lvert e_{n+1}\rvert/\lvert e_n\rvert^p\to C\in(0,\infty)$ ; linear means $p=1$ and needs $C<1$
Newton	Tangent step; simple root and continuous $f''$ give quadratic convergence, constant $\lvert f''(x^{})/(2f'(x^{}))\rvert$
Secant	Chord through the last two guesses; order $(1+\sqrt{5})/2$ near a simple root
Stopping	Residual, absolute step, relative step; $\lvert e\rvert\approx \lvert f(x)\rvert/\lvert f'\rvert$ relates the first to the error
Rounding	A residual at the scale of the rounding noise in $f$ , or a step at the last place of $x$ , has left exact arithmetic
Multiple root	Newton on $(x-x^{*})^m$ is linear with rate $(m-1)/m$ ; the factor $m$ restores the quadratic case

Next: Chapter 03 — Polynomial Interpolation, which builds the polynomial that matches prescribed values at prescribed nodes, and the error formula that measures how far that polynomial sits from the function it is standing in for.