Roots of Equations - Theory & Concepts

Roots of Equations

Finding the roots of equations is a common problem in engineering. A root of an equation is the value of

x

that makes

f(x) = 0

Stopping Criteria

Iterative root-finding methods require a formal stopping criterion to determine when the estimated root is accurate enough. The most common criterion checks if the approximate relative error

\varepsilon_a

falls below a prespecified tolerance

\varepsilon_s

\varepsilon_a = \left| \frac{x_r^{\text{new}} - x_r^{\text{old}}}{x_r^{\text{new}}} \right| \times 100\% < \varepsilon_s

Another common approach is checking if the function value

|f(x_r)|

is sufficiently close to zero, often termed the residual.

Graphical Methods

A simple method for obtaining an estimate of the root of the equation

f(x) = 0

is to plot the function and observe where it crosses the x-axis. While graphical methods lack precision, they provide excellent visual intuition and can establish initial guesses for numerical methods.

Bracketing Methods (Bisection, False Position)

Bracketing methods require two initial guesses for the root that bracket, or are on either side of, the true root. Since a root is a point where the function crosses the x-axis, the function values at the two guesses must have opposite signs.

Bisection Method

A variation of the incremental search method in which the interval is always divided in half. If a function changes sign over an interval

[x_l, x_u]

, the function value at the midpoint is evaluated to establish a new, smaller bracketing interval.

x_r = \frac{x_l + x_u}{2}

Error Bound: The maximum possible error

E

after

n

iterations decreases strictly deterministically. The required number of iterations

n

to reach a specific tolerance

E_d

given an initial interval of length

\Delta x = x_u - x_l

can be computed explicitly:

E_n = \frac{\Delta x}{2^{n}} \implies n = \frac{\log(\Delta x) - \log(E_d)}{\log(2)}

Bisection Method Visualization

Finding the root of $f(x) = x^3 - 4x - 9$ using the bisection method.

Iteration Step: 0

Step 0 (Initial)Step 10

Iteration 0 Details

Lower Bound (x_l)

2.0000

f(x_l) = -9.0000

Upper Bound (x_u)

3.0000

f(x_u) = 6.0000

Midpoint Estimate (x_r)

2.500000

f(x_r) = -3.375000

Decision

f(x_l) \cdot f(x_r) = 30.3750

Product is positive. Root is in upper half. New x_l = x_r.

False Position Method (Regula Falsi)

An alternative bracketing technique that uses a linear interpolation to find the root. It connects the function values at the bounds with a straight line, and the intersection of this line with the x-axis provides an improved estimate.

x_r = x_u - \frac{f(x_u)(x_l - x_u)}{f(x_l) - f(x_u)}

Open Methods

Open methods require only a single starting value or two starting values that do not necessarily bracket the root. They sometimes diverge, but when they do converge, they typically do so much faster than bracketing methods.

Fixed-Point Iteration

Also known as successive substitution or one-point iteration. The original equation

f(x) = 0

is rearranged into the form

x = g(x)

. The iteration formula is:

x_{i+1} = g(x_i)

Convergence Criterion: The method will converge to the root if the magnitude of the derivative of

g(x)

evaluated at the root is less than

1

, i.e.,

|g'(x)| < 1

. If

|g'(x)| > 1

, the method diverges. The method converges linearly.

Newton-Raphson Method

Perhaps the most widely used of all root-locating formulas. If the initial guess at the root is

x_i

, a tangent can be extended from the point

[x_i, f(x_i)]

. The point where this tangent crosses the x-axis represents an improved estimate of the root.

x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}

Geometric Interpretation: The method works by linearly approximating the nonlinear function

f(x)

using its tangent line at the current guess

x_i

. The x-intercept of this tangent line becomes the next guess

x_{i+1}

. This process geometrically slides down the slope of the curve directly toward the x-axis.

Newton-Raphson Method Visualization

Finding the root of $f(x) = x^2 - 4$ using the Newton-Raphson method with initial guess $x_0 = 4$ .

Iteration Step: 0

Step 0 (Initial)Step 5

Iteration 0 Calculations

Current Guess (x_i)

4.0000

f(x_i) = 12.0000

Derivative (Slope)

8.0000

f'(x_i) = 8.0000

Formula

x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}

x_{i+1} = 4.0000 - \frac{12.0000}{8.0000}

Next Estimate (x_i+1)

2.500000

Caution

The Newton-Raphson method requires the evaluation of the derivative

f'(x)

. If the derivative is zero or very small at the guess, the method may diverge or fail entirely (division by zero).

Pitfalls of the Newton-Raphson Method

While highly efficient (quadratic convergence), Newton-Raphson is notorious for diverging under specific geometric conditions:

Inflection Points: If a guess is near an inflection point ( $f''(x) = 0$ ), the tangent line may intersect the x-axis far from the actual root, causing wild oscillations or divergence.
Local Minima/Maxima: If the tangent is evaluated near a local extremum, the near-zero slope will project the next guess extremely far away from the root.
Oscillations: The method can become trapped in a non-converging periodic loop (e.g., bouncing continuously between $x_1$ and $x_2$ ).

Secant Method

A variation of the Newton-Raphson method that approximates the derivative using a finite divided difference instead of evaluating it analytically.

x_{i+1} = x_i - \frac{f(x_i)(x_{i-1} - x_i)}{f(x_{i-1}) - f(x_i)}

Secant Method Visualization

Finding the root of $f(x) = e^{-x} - x$ using the Secant method with initial guesses $x_{-1} = 0$ and $x_0 = 1$ .

Iteration Step: 0

Step 0 (Initial)Step 4

Iteration 0 Calculations

Previous Guess (x_i-1)

0.00000

f(x_i-1) = 1.00000

Current Guess (x_i)

1.00000

f(x_i) = -0.63212

Formula

x_{i+1} = x_i - \frac{f(x_i)(x_{i-1} - x_i)}{f(x_{i-1}) - f(x_i)}

Next Estimate (x_i+1)

0.612700

Convergence Rates

The speed at which a root-finding method approaches the true root is measured by its rate of convergence. If

e_i

is the error at iteration

i

, the relationship

e_{i+1} \approx C e_i^p

defines the convergence rate

p

Common Convergence Orders

Linear ( $p=1$ ): The error is reduced by a constant factor each step (e.g., Bisection method, Fixed-Point Iteration).
Superlinear ( $1 < p < 2$ ): Faster than linear but slower than quadratic (e.g., Secant method, $p \approx 1.618$ ).
Quadratic ( $p=2$ ): The number of correct significant digits roughly doubles with each iteration (e.g., Newton-Raphson method).

Brent's Method

Brent's method is a popular, highly reliable hybrid root-finding algorithm that combines the robustness of bisection with the speed of open methods like the secant method and inverse quadratic interpolation.

How Brent's Method Works

It maintains a bracketing interval, guaranteeing convergence, while attempting to use faster open methods when possible:

Inverse Quadratic Interpolation: If the last three points are distinct, it fits a parabola to them and finds where it crosses the x-axis.
Secant Method: If only two points are distinct (or the interpolation step is unacceptable), it uses the secant method for a linear approximation.
Bisection Method: If the faster methods predict a step outside the current bracket or if convergence is too slow, it falls back to a safe bisection step, halving the interval.

This combination makes it the method of choice in many standard software libraries (like MATLAB's fzero or SciPy's brentq).

Multiple Roots and the Modified Newton-Raphson

A multiple root corresponds to a point where a function is tangent to the x-axis (e.g.,

f(x)=0

and

f'(x)=0

). Standard Newton-Raphson and secant methods converge slowly (linearly rather than quadratically) for multiple roots and may encounter division by zero.

Modified Newton-Raphson

To restore quadratic convergence for multiple roots, a modified formula is used:

x_{i+1} = x_i - \frac{f(x_i)f'(x_i)}{[f'(x_i)]^2 - f(x_i)f''(x_i)}

Systems of Nonlinear Equations

The Newton-Raphson method can be extended to systems of nonlinear equations. For a system with two variables,

f_1(x, y) = 0

and

f_2(x, y) = 0

, the Jacobian matrix (consisting of partial derivatives) is used to iteratively update the guesses.

x_{i+1} = x_i - \frac{f_1 \frac{\partial f_2}{\partial y} - f_2 \frac{\partial f_1}{\partial y}}{\frac{\partial f_1}{\partial x} \frac{\partial f_2}{\partial y} - \frac{\partial f_1}{\partial y} \frac{\partial f_2}{\partial x}}

Roots of Polynomials

Polynomials of the form

f(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n

often arise in engineering. Methods specifically designed for polynomials, such as Bairstow's method and Muller's method, can find both real and complex roots effectively.

Specialized Polynomial Methods

Muller's Method: Similar to the secant method, but it uses a parabola fitted to three points instead of a straight line through two points. This allows it to locate complex roots.
Bairstow's Method: An iterative approach based on dividing the polynomial by a quadratic factor to systematically extract real and complex roots.

Polynomial Deflation

Once a root

r

of an

n

-th degree polynomial

P_n(x)

is found, the polynomial can be reduced to a lower-degree polynomial

Q_{n-1}(x)

by factoring out

(x - r)

. This process is called deflation:

P_n(x) = (x - r)Q_{n-1}(x)

Subsequent roots are then found using

Q_{n-1}(x)

. However, deflation is highly sensitive to round-off errors. If the root

r

is inaccurate, the errors will propagate and severely distort the remaining roots. A common strategy to mitigate this is to polish the final roots using the original polynomial

P_n(x)

Key Takeaways

Bracketing methods (Bisection, False Position) always converge but can be slow.
The iterations required for the Bisection method to reach a desired error bound can be calculated exactly since the interval halves reliably each step.
Open methods (Fixed-Point, Newton-Raphson, Secant) are usually faster but may diverge if the initial guess is poor.
Stopping Criteria typically rely on checking the relative error against a tolerance or the residual $|f(x_r)|$ against zero.
Convergence rates range from Linear (Bisection) to Superlinear (Secant) and Quadratic (Newton-Raphson).
The Bisection method halves the interval, while False Position uses a straight-line approximation.
The Newton-Raphson method uses the tangent line, requiring the analytical derivative. It can fail due to inflection points, local minima, or zero derivatives. It can also be extended to systems of nonlinear equations using the Jacobian.
The Secant method approximates the derivative using two recent guesses.
Multiple roots cause standard open methods to converge linearly; the Modified Newton-Raphson restores quadratic convergence.
Polynomial Deflation isolates subsequent roots but is prone to propagating round-off errors, necessitating root polishing.
Muller's and Bairstow's methods are specialized techniques that can efficiently locate complex roots of polynomials.
Brent's Method is a hybrid approach that provides the reliability of bracketing methods with the speed of open interpolation techniques.

PreviousIntroduction and Error Analysis - Examples & Applications

NextRoots of Equations - Examples & Applications