Training Numerical Methods Root-Finding Methods
1 / 5

Root-Finding Methods

25 min Numerical Methods

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.

$c_1 = 1.5$, $f(1.5) = 1.375 > 0$ → $[1,1.5]$.

$c_2 = 1.25$, $f(1.25) = -0.047 < 0$ → $[1.25,1.5]$.

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

$f'(x) = 2x$. $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/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

Interpolation