Training Numerical Methods Root-Finding Methods
1 / 5

Root-Finding Methods

25 min Numerical Methods
Root-finding algorithms locate values of x where f(x) = 0—a problem that arises everywhere from engineering design to financial modeling. The bisection method is the simplest: given an interval [a, b] where f changes sign, it repeatedly halves the interval, guaranteeing convergence at a predictable rate of one binary digit per step. Newton's method uses the tangent line x_{n+1} = x_n − f(x_n)/f′(x_n) and converges quadratically when started near a root, but it can fail if the derivative is zero or the initial guess is poor. The secant method approximates Newton's method without requiring an explicit derivative, using the slope between the two most recent points. Choosing among these methods involves balancing reliability (bisection), speed (Newton), and ease of implementation (secant).

Root-Finding Methods

The Problem

Find $x$ such that $f(x) = 0$. When no algebraic solution exists, iterative numerical methods converge to the root.

Bisection Method

Given $f(a)f(b) < 0$, repeatedly halve the interval $[a,b]$ by testing the midpoint $c = (a+b)/2$.

  • If $f(a)f(c) < 0$: root in $[a,c]$
  • Else: root in $[c,b]$

Error after $n$ steps: $\leq \frac{b-a}{2^n}$.

Newton's Method

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

Converges quadratically near simple roots if $f'(x_n) \neq 0$.

Secant Method

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

Like Newton's but uses a finite-difference approximation to $f'$.

Example 1

Use bisection on $f(x) = x^3 - 2$ in $[1,2]$. Find the first three midpoints.

  1. $c_1 = 1.5$, $f(1.5) = 1.375 > 0$ → $[1,1.5]$.
  2. $c_2 = 1.25$, $f(1.25) = -0.047 < 0$ → $[1.25,1.5]$.
  3. $c_3 = 1.375$, $f(1.375) = 0.599 > 0$ → $[1.25,1.375]$.
Example 2

One iteration of Newton's method for $f(x) = x^2 - 3$ starting at $x_0 = 2$.

  1. $f'(x) = 2x$.
  2. $x_1 = 2 - (4-3)/4 = 2 - 0.25 = 1.75$.
Example 3

How many bisection steps guarantee error $< 0.01$ on $[0,1]$?

  1. $1/2^n < 0.01 \Rightarrow 2^n > 100 \Rightarrow n \geq 7$.

Practice Problems

1. Verify $f(x)=x^3-x-1$ has a root in $[1,2]$.
2. Bisection: first midpoint of $[1,2]$ for Problem 1.
3. Newton's: one step for $f(x)=x^2-5$, $x_0=2$.
4. When does Newton's method fail?
5. Bisection: how many steps for error $<0.001$ on $[0,2]$?
6. Newton's: $f(x) = e^x - 3$, $x_0 = 1$. Find $x_1$.
7. What is the order of convergence of bisection?
8. Secant: $x_0=1, x_1=2, f(x)=x^2-3$. Find $x_2$.
9. Does bisection always converge?
10. Newton's: $f(x) = \cos x - x$, $x_0 = 0.5$. Find $x_1$.
11. Compare convergence rates: bisection vs. Newton.
12. Why is a good initial guess important for Newton's method?
Show Answer Key

1. $f(1)=-1<0$, $f(2)=5>0$; sign change ✓

2. $c = 1.5$; $f(1.5)=0.875>0$ → root in $[1,1.5]$

3. $x_1 = 2-(4-5)/4 = 2+0.25 = 2.25$

4. When $f'(x_n)=0$ (horizontal tangent) or bad initial guess

5. $2/2^n<0.001$; $2^n>2000$; $n \geq 11$

6. $x_1 = 1-(e-3)/e \approx 1-(-0.282)/2.718 \approx 1.104$

7. Linear — $O(1/2^n)$

8. $f(1)=-2$, $f(2)=1$. $x_2 = 2-1\cdot(2-1)/(1-(-2)) = 2-1/3 \approx 1.667$

9. Yes, as long as initial bracket satisfies $f(a)f(b)<0$ and $f$ is continuous

10. $f(0.5)=0.378-0.5=-0.122$; $f'(0.5)=-\sin(0.5)-1=-1.479$. $x_1 = 0.5-(-0.122)/(-1.479) \approx 0.418$... actually $x_1 \approx 0.7553$

11. Bisection: linear; Newton: quadratic (much faster near root)

12. Poor guess can lead to divergence or cycling

✂ Bisection Method Demo
Root estimate
Actual √K
Error
Interval width
Interpolation