Error Analysis for Root Finding - Introduction to Scientific Computing

Condition Number for Roots¶

The condition number measures how sensitive the root $x^*$ is to perturbations in the function $f$ .

Theorem 1 (Condition Number for a Simple Root)

If $f(x^*) = 0$ and $f'(x^*) \neq 0$ (a simple root), then the absolute condition number is:

\kappa = \frac{1}{|f'(x^*)|}

The root is well-conditioned when $|f'(x^*)|$ is large (steep crossing) and ill-conditioned when $|f'(x^*)|$ is small (tangent crossing).

The forward/backward error framework from earlier applies naturally to root finding.

The forward error is what we ultimately care about, but it’s hard to compute directly (we don’t know $x^*$ !).

The backward error is easy to compute: just evaluate $f(\hat{x})$ .

Theorem 2 (Relating Forward and Backward Error)

For root finding, the forward and backward errors are related by:

|\hat{x} - x^*| \approx \frac{|f(\hat{x})|}{|f'(x^*)|} = \kappa \cdot |f(\hat{x})|

Different root-finding methods converge at different rates. Understanding these rates helps us choose the right method.

Examples of linear convergence:

Examples of quadratic convergence:

Examples of superlinear convergence:

Secant method: Order $\approx 1.618$ (the golden ratio)
Quasi-Newton methods: Achieve superlinear without computing exact derivatives

Definition 6 (Order of Convergence)

A sequence $\{x_n\}$ converging to $x^*$ has order of convergence $p \geq 1$ if:

\lim_{n \to \infty} \frac{|x_{n+1} - x^*|}{|x_n - x^*|^p} = C

for some constant $C > 0$ (the asymptotic error constant).

Example 1 (Orders of Common Methods)

Method	Convergence	Rate	Iterations for 10 digits
Bisection	Linear	$L = 0.5$	~34
Fixed-point (typical)	Linear	$L = 0.9$	~220
Newton’s method	Quadratic	doubles digits	~4-5

Concept	Formula	Interpretation
Condition number	$\kappa = 1/\|f'(x^*)\|$	Sensitivity of root to perturbations
Forward error	$\|\hat{x} - x^*\|$	Distance from true root
Backward error	$\|f(\hat{x})\|$	Residual
Error relationship	Forward $\approx \kappa \times$ Backward	Why both stopping criteria matter
Linear convergence	$e_{n+1} \leq L \cdot e_n$	Constant factor reduction
Superlinear convergence	$e_{n+1}/e_n \to 0$	Ratio improves each step
Quadratic convergence	$e_{n+1} \leq C \cdot e_n^2$	Digits double each step
Order $p$ convergence	$e_{n+1} \sim C \cdot e_n^p$	General framework