Solution of Nonlinear Equations
Finding roots of a nonlinear equation f(x) = 0 is one of the most common problems in numerical computing. This chapter surveys the standard methods, their convergence behaviour, and practical implementation guidelines.
Graphical and Analytical Approaches
For simple equations, plotting f(x) locates roots approximately. Analytical methods (factoring, quadratic formula, trigonometric identities) solve special cases exactly. Most equations, however, require iterative numerical techniques.
Bisection Method
The bisection method assumes f is continuous and changes sign between a and b, guaranteeing a root by the Intermediate Value Theorem. It repeatedly halves the interval, keeping the half where the sign change persists. Bisection is guaranteed to converge and the error is halved each iteration—linear convergence—but it is slow. It serves as a reliable fallback and a good warm-up for faster methods.
Regula Falsi (False Position)
The method of false position improves on bisection by using a linear interpolation between (a, f(a)) and (b, f(b)) instead of simply halving. It also brackets the root but often converges faster than bisection. One endpoint may stagnate on one side for concave functions, leading to modifications such as the Illinois variant.
Fixed-Point Iteration
Rewriting f(x) = 0 as x = g(x) leads to the iteration xn+1 = g(xn). If |g'(x)| < 1 near the root, the iteration converges; otherwise it diverges. Fixed-point iteration has linear convergence but is conceptually simple and forms the basis of the more powerful Newton method.
Newton–Raphson Method
The Newton–Raphson method uses the recurrence xn+1 = xn − f(xn)/f'(xn). Near a simple root with nonzero derivative, it has quadratic convergence: the number of correct digits roughly doubles per step. Drawbacks include: it requires f'(x) (or a numerical approximation), it can diverge if f'(x) is small or the starting guess is poor, and multiple roots reduce the convergence rate.
Secant Method
The secant method replaces the derivative in Newton's method by the finite difference (f(xn) − f(xn−1))/(xn − xn−1). It does not require derivatives and achieves super-linear convergence (order ≈ 1.618, the golden ratio). It requires two starting points but avoids the cost of derivative evaluations.
Convergence Criteria
Iteration stops when |xn+1 − xn| is less than a tolerance, when |f(xn)| is below a tolerance, or when a maximum iteration count is reached. A robust implementation combines all three checks.
Multiple Roots and Systems
If f has a root of multiplicity m, Newton's convergence degrades from quadratic to linear. Modified Newton xn+1 = xn − m f(xn)/f'(xn) restores quadratic convergence when m is known. Systems of nonlinear equations are solved by the multi-dimensional Newton method using the Jacobian matrix.
Practical Guidelines
Robust software combines bracketing (bisection) with rapid local methods (Newton or secant): Brent's method is a popular hybrid. Good initial guesses, proper scaling, and careful handling of special cases are essential to reliable root finding.
Summary
Root-finding methods range from slow-but-reliable bisection to fast-but-delicate Newton iterations. Understanding the convergence properties and failure modes of each is essential for solving real-world nonlinear equations.