Roots of Equations - Theory & Concepts

Roots of Equations

Learning Objectives

Understand the definition and engineering significance of finding roots of equations.
Apply bracketing methods like the Bisection and False Position methods.
Implement open methods including Fixed-Point Iteration, Newton-Raphson, and the Secant method.
Determine convergence rates and understand stopping criteria for iterative methods.
Use hybrid techniques like Brent's method.
Solve systems of nonlinear equations and find roots of polynomials.

Root of an Equation

The value of $x$ that makes the function equal to zero, i.e., $f(x) = 0$ .

Finding the roots of equations is a common problem in engineering.

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

Stopping Criterion for Iterative Methods

Computes the approximate relative error and compares it to a prespecified tolerance to decide when to stop iterating.

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

Variables

Symbol	Description	Unit
$\varepsilon_a$	Approximate relative error	%
$x_r^{\text{new}}$	Current estimated root	-
$x_r^{\text{old}}$	Previous estimated root	-
$\varepsilon_s$	Prespecified error tolerance	%

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.

Error Bound: The maximum possible error $E$ after $n$ iterations decreases strictly deterministically.

Bisection Root Estimate

Calculates the new root estimate as the midpoint of the current interval.

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

Variables

Symbol	Description	Unit
$x_r$	Estimated root at the midpoint	-
$x_l$	Lower bound of the interval	-
$x_u$	Upper bound of the interval	-

Bisection Method Iteration Count

Calculates the required number of iterations to reach a specific error tolerance given an initial interval.

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

Variables

Symbol	Description	Unit
$E_n$	Maximum possible error after n iterations	-
$\Delta x$	Initial interval length ( $x_u - x_l$ )	-
$n$	Number of iterations	-
$E_d$	Desired error tolerance	-

Interactive Simulation

Use the simulation below to explore how the Bisection method halves the interval iteratively to find the root.

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.

False Position Formula

Computes the next root estimate using linear interpolation between the bounds.

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

Variables

Symbol	Description	Unit
$x_r$	Improved estimate of the root	-
$x_l$	Lower bound	-
$x_u$	Upper bound	-
$f(x_l)$	Function value at the lower bound	-
$f(x_u)$	Function value at the upper bound	-

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

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.

Fixed-Point Iteration Formula

Iterative formula for fixed-point iteration.

x_{i+1} = g(x_i)

Variables

Symbol	Description	Unit
$x_{i+1}$	Next estimate of the root	-
$x_i$	Current estimate of the root	-
$g(x)$	Rearranged function $x = g(x)$	-

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.

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 Formula

Calculates the next root estimate using the tangent of the function.

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

Variables

Symbol	Description	Unit
$x_{i+1}$	Next estimate of the root	-
$x_i$	Current estimate of the root	-
$f(x_i)$	Function value at the current estimate	-
$f'(x_i)$	Derivative of the function at the current estimate	-

Interactive Simulation

Observe how the Newton-Raphson method slides down the tangent line to find the root in the simulation below.

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

Relative Error:Initial estimate

Zero or Small Derivative Risk

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.

Secant Method Formula

Computes the next estimate using a secant line between two recent guesses.

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

Variables

Symbol	Description	Unit
$x_{i+1}$	Next estimate of the root	-
$x_i$	Current estimate of the root	-
$x_{i-1}$	Previous estimate of the root	-
$f(x_i)$	Function value at current estimate	-
$f(x_{i-1})$	Function value at previous estimate	-

Interactive Simulation

Explore how the Secant method converges without needing analytical derivatives in the simulation below.

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

Multiple Root

A root that corresponds to a point where a function is tangent to the x-axis, meaning both the function and its derivative evaluate to zero ( $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.

Modified Newton-Raphson Formula

Restores quadratic convergence when dealing with multiple roots.

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

Variables

Symbol	Description	Unit
$x_{i+1}$	Next estimate of the root	-
$x_i$	Current estimate of the root	-
$f(x_i)$	Function value	-
$f'(x_i)$	First derivative	-
$f''(x_i)$	Second derivative	-

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.

Newton-Raphson for 2-Variable Systems

Updates the x-coordinate guess for a system of two nonlinear equations using the Jacobian.

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}}

Variables

Symbol	Description	Unit
$x_{i+1}$	Next estimate for x	-
$x_i$	Current estimate for x	-
$f_1, f_2$	Nonlinear equations in the system	-
$\frac{\partial f_j}{\partial k}$	Partial derivative of function $j$ with respect to variable $k$	-

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

Polynomial Deflation

The process of reducing the degree of a polynomial by factoring out a known root $r$ as $(x - r)$ to find subsequent roots.

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

Polynomial Deflation

Reduces the degree of a polynomial after finding a root $r$ .

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

Variables

Symbol	Description	Unit
$P_n(x)$	Original polynomial of degree $n$	-
$r$	A known root	-
$Q_{n-1}(x)$	Deflated polynomial of degree $n-1$	-

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.

Previous TopicIntroduction and Error Analysis - Examples & Applications

Next TopicRoots of Equations - Examples & Applications

Prev Next