Root Finding of Non-Linear Equations

Many non-linear equations involving high powers, series, polynomials, or rational functions cannot be solved analytically. Instead, we apply iterative algorithms to find their roots numerically, where a root $x^*$ satisfies $f(x^*) = 0$ . This chapter covers the five most important root-finding algorithms: from the simple but robust bisection method, through fixed-point iteration and its convergence theory, to the fast Newton-Raphson method and two of its practical variants.

Learning Objectives

By the end of this chapter you should be able to:

State the sign-change condition for the bisection method and apply it to locate a root within a given interval.
Derive the minimum number of bisection iterations required to achieve a prescribed error tolerance.
Convert $f(x) = 0$ into a fixed-point form $g(x) = x$ in multiple ways.
Apply the contraction mapping theorem to determine whether a given $g(x)$ converges, and to which root.
Classify convergence as super-linear ( $\lambda = 0$ ) or linear ( $0 < \lambda < 1$ ) using the derivative $g'(x^*)$ .
Derive Newton’s method geometrically and prove that it achieves super-linear convergence.
Identify situations where Newton’s method fails due to a zero derivative.
Apply Aitken acceleration to speed up a slowly converging fixed-point sequence.
Derive the secant method as an approximation of Newton’s method and apply it when the derivative is unavailable.

Chapter Sections

#	Section	Key Concepts
1	Bisection Method	Sign-change condition, minimum iterations proof, worked example
2	Fixed Point Iteration	Converting $f(x)=0$ to $g(x)=x$ , iteration formula, convergence examples
3	Contraction Mapping Theory	$\lambda = \\|g'(x^*)\\|$ , order of convergence, comprehensive example
4	Newton’s Method	Tangent line derivation, super-linear convergence proof, drawbacks
5	Aitken Acceleration	Acceleration formula, speeding up fixed-point sequences
6	Secant Method	Finite difference derivative approximation, two-point startup