Applied and computational mathematics

Approximate solutions of equations

Numerical methods like bisection and Newton's method that find roots a computer can compute step by step.

IntuitionIntuition: zooming in near a root

Suppose you are hunting for a root $r$ of an equation $f(x)=0$ , but there is no algebraic formula that produces $r$ exactly. A numerical method builds a sequence of guesses $x_0, x_1, x_2,\dots$ that gets closer and closer to $r$ at every step, much like repeatedly zooming a graph of $f$ toward the point where it crosses the horizontal axis lets you read off more and more correct decimal digits. The three methods below differ only in how cleverly they turn the current guess $x_n$ into the next, better guess $x_{n+1}$ .

Drag the secant line's step size

h

toward zero and watch it settle onto the tangent line at

x_0

with slope

f'(x_0)

: this is exactly the tangent line that Newton's method follows downhill to its next guess

x_1 = x_0 - \dfrac{f(x_0)}{f'(x_0)}

, instead of the cruder secant slope

\dfrac{f(x_0+h)-f(x_0)}{h}

UndergraduateDefinition: three root-finding methods

Definition: Bisection method

If a continuous function $f$ satisfies $f(a)f(b)<0$ on an interval $[a,b]$ , the Intermediate Value Theorem guarantees a root inside. Bisection halves this interval at every step: compute the midpoint $c=\dfrac{a+b}{2}$ , evaluate $f(c)$ , then keep whichever half still has a sign change and repeat.

|x_n - r| \le \dfrac{b-a}{2^{n+1}}

Here $|x_n - r| \le \dfrac{b-a}{2^{n+1}}$ bounds how far the $n$ -th midpoint $x_n$ can be from the true root $r$ : since the interval width $L=b-a$ halves at every single step, the worst-case error is cut in half too, so after only $n=4$ steps the uncertainty shrinks to $L/32$ . This guaranteed, predictable shrink rate is the whole appeal of bisection — it never fails to converge, though it is slow.

Definition: Newton's method

Newton's method replaces the curve near $x_n$ by its tangent line $y=f(x_n)+f'(x_n)(x-x_n)$ and takes the next guess $x_{n+1}$ to be where that tangent line crosses zero, giving the iteration $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$ . It needs the derivative $f'$ at every step but converges far faster than bisection when it works.

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

A third viewpoint unifies both: rewrite the equation as a fixed-point problem $x=g(x)$ for some function $g$ , so that a root of $f$ becomes a fixed point of $g$ , and iterate $x_{n+1} = g(x_n)$ starting from any $x_0$ . Both bisection and Newton's method are special cases of this idea with different choices of $g$ .

Comparing the three root-finding methods
Method	Iteration	Order of convergence	Requirement
Bisection	$c=\dfrac{a+b}{2}$	Linear ( $1$ )	$f$ continuous, $f(a)f(b)<0$
Newton	$x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$	Quadratic ( $2$ )	$f$ twice differentiable, $f'(r) \ne 0$ , $x_0$ close to $r$
Fixed-point iteration	$x_{n+1} = g(x_n)$	Linear ( $1$ ), generically	$\|g'(x)\| \le L < 1$ near $r$

UndergraduateKey theorems

Theorem: Bisection convergence and error bound

Let $f$ be continuous on $[a,b]$ with $f(a)f(b)<0$ . Then the bisection method produces midpoints $x_n=\dfrac{a_n+b_n}{2}$ with $x_n \to r$ for some root $r$ in $[a,b]$ , and the error after $n$ steps satisfies $|x_n - r| \le \dfrac{b-a}{2^{n+1}}$ .

Why is it true?

Every step traps the root inside a shrinking box, and a box that shrinks to a point with a root always inside it must shrink onto the root itself.

Proof

Step 1 (the invariant). Set $a_0=a$ , $b_0=b$ . At step $n$ , we maintain the invariant that $f(a_n)f(b_n)<0$ , i.e. the root is trapped somewhere in $[a_n,b_n]$ . This holds initially by hypothesis. Given $[a_n,b_n]$ , compute the midpoint $x_n=\dfrac{a_n+b_n}{2}$ and evaluate $f(x_n)$ : if it has the opposite sign to $f(a_n)$ set $a_{n+1}=a_n,\ b_{n+1}=x_n$ , otherwise set $a_{n+1}=x_n,\ b_{n+1}=b_n$ (if $f(x_n)=0$ exactly, $x_n$ is the root and the process stops). Either way $f(a_{n+1})f(b_{n+1})<0$ again, so the invariant is preserved by induction.

Step 2 (shrinking width). By construction each new interval is exactly half the previous one, so $b_n-a_n = \dfrac{b-a}{2^n}$ for every $n \ge 0$ . Since the root $r$ lies in $[a_n,b_n]$ at every step (by Step 1), and the midpoint $x_n$ also lies in $[a_n,b_n]$ , both are within the same interval of width $\dfrac{b-a}{2^n}$ of each other, so $|x_n - r| \le \dfrac{b-a}{2^n}$ already holds; a slightly sharper count (measuring from the midpoint to either endpoint) gives the stated bound $|x_n - r| \le \dfrac{b-a}{2^{n+1}}$ .

Step 3 (convergence). Since $\dfrac{b-a}{2^{n+1}} \to 0$ as $n\to\infty$ , the squeeze from Step 2 forces $x_n \to r$ . No continuity of $f$ beyond the initial sign condition is even needed for this part — only for guaranteeing a root existed inside $[a,b]$ to begin with, which is the Intermediate Value Theorem applied at step 0.

Theorem: Quadratic convergence of Newton's method

Suppose $f$ is twice continuously differentiable near a root $r$ with $f'(r) \ne 0$ . Then there is a neighborhood of $r$ such that, if the Newton iteration starts inside it, the iterates converge to $r$ and satisfy $|x_{n+1}-r| \le C\,|x_n-r|^2$ for a constant $C=\dfrac{\max|f''|}{2\min|f'|}$ (the maximum and minimum taken over that neighborhood).

Why is it true?

The tangent line is such a good approximation to a smooth curve that the error it makes is proportional to the square of the distance already traveled, so each correct digit roughly doubles the number of correct digits at the next step.

Proof

Step 1 (Taylor expand around the current guess). Since $f$ is twice differentiable, Taylor's theorem with the Lagrange remainder gives $f(r) = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2$ for some $\xi_n$ between $x_n$ and $r$ . This is exact, not an approximation, because the remainder term carries the full second-order error.

Step 2 (substitute the root condition). Since $f(r)=0$ , the left side vanishes, leaving $0 = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2$ . Dividing through by $f'(x_n)$ (nonzero near $r$ since $f'(r) \ne 0$ and $f'$ is continuous) isolates $r - x_n$ : $0 = \dfrac{f(x_n)}{f'(x_n)} + (r-x_n) + \dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2$ .

Step 3 (recognize the Newton step). Rearranging, $r - \left(x_n - \dfrac{f(x_n)}{f'(x_n)}\right) = -\dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2$ . The left-hand parenthesis is exactly the Newton update $x_{n+1}$ , so with $e_n = x_n - r$ this reads $r - x_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2$ , i.e. $e_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2$ .

Step 4 (bound the constant). Taking absolute values and bounding $|f''(\xi_n)|$ and $1/|f'(x_n)|$ by their extreme values $\max|f''|$ and $1/\min|f'|$ on the neighborhood gives $|x_{n+1}-r| \le C\,|x_n-r|^2$ with $C=\dfrac{\max|f''|}{2\min|f'|}$ . Once $C\,|x_0-r| < 1$ , this recursion forces $|x_n - r|$ to shrink to $0$ , proving convergence, and the squaring in $|x_{n+1}-r| \le C\,|x_n-r|^2$ is exactly the quadratic rate.

Theorem: Convergence of fixed-point iteration

Let $g:[a,b]\to[a,b]$ be continuously differentiable with $|g'(x)| \le L < 1$ for all $x\in[a,b]$ . Then $g$ has a unique fixed point $r$ in $[a,b]$ , and for every starting point $x_0 \in [a,b]$ the iteration $x_{n+1}=g(x_n)$ converges to $r$ with $|x_n - r| \le L^n |x_0 - r|$ .

Why is it true?

A slope smaller than one in absolute value means every application of g squeezes points closer together, so no matter where you start, repeated squeezing must collapse the whole interval onto a single point.

Proof

Step 1 (existence via the intermediate value theorem). Let $h(x)=g(x)-x$ . Since $g(a)\in[a,b]$ we have $g(a)\ge a$ so $h(a)\ge0$ , and similarly $g(b)\le b$ gives $h(b)\le0$ . Since $h$ is continuous, the Intermediate Value Theorem gives some $r$ with $h(r)=0$ , i.e. $g(r)=r$ : a fixed point exists.

Step 2 (uniqueness via the mean value theorem). Suppose $r_1,r_2\in[a,b]$ are both fixed points with $r_1\ne r_2$ . The Mean Value Theorem gives some $c$ between them with $g(r_1)-g(r_2) = g'(c)(r_1-r_2)$ ; since $g(r_1)=r_1$ and $g(r_2)=r_2$ , this reads $r_1-r_2 = g'(c)(r_1-r_2)$ , so $|r_1-r_2| = |g'(c)|\,|r_1-r_2| \le L\,|r_1-r_2|$ . Since $L<1$ and $|r_1-r_2|>0$ , this is a contradiction, so $r_1=r_2$ .

Step 3 (contraction at every step). For any $x_n\in[a,b]$ , apply the Mean Value Theorem to $g(x_n)-g(r)$ : there is some $c_n$ between $x_n$ and $r$ with $g(x_n)-g(r) = g'(c_n)(x_n-r)$ . Since $g(r)=r$ and $x_{n+1}=g(x_n)$ , the left side is $x_{n+1}-r$ , so $|x_{n+1}-r| = |g'(c_n)|\,|x_n-r| \le L\,|x_n-r|$ .

Step 4 (iterate the contraction). Applying Step 3 repeatedly from $n=0$ gives $|x_1-r|\le L|x_0-r|$ , then $|x_2-r|\le L|x_1-r|\le L^2|x_0-r|$ , and inductively $|x_n - r| \le L^n |x_0 - r|$ for every $n$ . Since $0\le L<1$ , the right side tends to $0$ as $n\to\infty$ , proving $x_n\to r$ .

UndergraduateReal-World Applications and Worked Examples

Root-finding is the hidden engine behind countless calculations that have no closed-form answer. Engineers use Newton's method to solve nonlinear systems in structural and circuit design; finance uses it to back out an unknown interest rate from a bond price or an implied volatility from an option price; computer graphics uses it to intersect rays with implicit surfaces; and every scientific calculator computes $\sqrt{2}$ or a cube root by running a few steps of Newton's method internally. Bisection, being foolproof, is the fallback used inside root-finding libraries whenever Newton's method risks diverging.

Example: Bisection for a cubic equation with no algebraic root formula

A mechanical system's equilibrium position satisfies $x^3-x-2=0$ . Using the interval $[1,2]$ (where $f(1)=-2<0$ and $f(2)=4>0$ ), perform two bisection steps and report the resulting midpoint $x_2$ .

Solution

Step 1: compute the first midpoint. $x_0 = \dfrac{1+2}{2} = 1.5$ , and $f(1.5) = 1.5^3 - 1.5 - 2 = -0.125 < 0$ , so the root lies in $[1.5, 2]$ since $f$ changes sign there ( $f(1.5)<0$ , $f(2)>0$ ).

Step 2: compute the second midpoint. $x_1 = \dfrac{1.5+2}{2} = 1.75$ , and $f(1.75) = 1.75^3 - 1.75 - 2 = 1.609375 > 0$ , so the root lies in $[1.5, 1.75]$ .

Step 3: compute $x_2$ . $x_2 = \dfrac{1.5+1.75}{2} = 1.625$ .

Step 4: interpret. After only two steps the search interval has shrunk from width $1$ to width $0.25$ , and $x_2=1.625$ is already within $0.125$ of the true root $r\approx1.5214$ , consistent with the error bound $|x_2-r|\le \dfrac{2-1}{2^{3}}=0.125$ from the bisection theorem.

Example: Newton's method computing a square root by hand

Before calculators, engineers computed square roots this way: to find $\sqrt{5}$ , apply Newton's method to $f(x)=x^2-5$ starting from $x_0=2$ , and compute $x_1$ and $x_2$ .

Solution

Step 1: set up the iteration. Here $f(x)=x^2-5$ and $f'(x)=2x$ , so the Newton update is $x_{n+1}=x_n-\dfrac{x_n^2-5}{2x_n}$ .

Step 2: compute $x_1$ . With $x_0=2$ : $x_1 = 2 - \dfrac{2^2-5}{2\cdot2} = 2 - \dfrac{-1}{4} = 2.25$ .

Step 3: compute $x_2$ . With $x_1=2.25$ : $x_2 = 2.25 - \dfrac{2.25^2-5}{2\cdot2.25} = 2.25 - \dfrac{0.0625}{4.5} \approx 2.236111$ .

Step 4: interpret. The true value is $\sqrt{5}\approx2.236068$ , so $x_2$ is already correct to four decimal places after just two steps — the number of correct digits roughly doubled from $x_1$ to $x_2$ , the signature of quadratic convergence proved above.

Starting bisection on $[a,b]=[0,1]$ and performing $n=5$ iterations, what is the guaranteed bound on $|x_5 - r|$ ?

Which formula correctly gives one step of Newton's method?

A bond trader uses Newton's method to solve a nonlinear pricing equation $P(y)=0$ for the yield $y$ , starting from a guess $y_0$ . Which situation is most likely to make the iteration fail to converge?

For the fixed-point iteration $x_{n+1} = g(x_n)$ on $[a,b]$ to be guaranteed to converge to a fixed point for any starting $x_0 \in [a,b]$ , which condition is required?