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 xx that makes the function equal to zero, i.e., f(x)=0f(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 εa\varepsilon_a falls below a prespecified tolerance εs\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.

εa=∣xrnew−xroldxrnew∣×100%<εs\varepsilon_a = \left| \frac{x_r^{\text{new}} - x_r^{\text{old}}}{x_r^{\text{new}}} \right| \times 100\% < \varepsilon_s

Variables

SymbolDescriptionUnit
εa\varepsilon_aApproximate relative error%
xrnewx_r^{\text{new}}Current estimated root
xroldx_r^{\text{old}}Previous estimated root
εs\varepsilon_sPrespecified error tolerance%

Another common approach is checking if the function value ∣f(xr)∣|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)=0f(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 [xl,xu][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 EE after nn iterations decreases strictly deterministically.

Bisection Root Estimate

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

xr=xl+xu2x_r = \frac{x_l + x_u}{2}

Variables

SymbolDescriptionUnit
xrx_rEstimated root at the midpoint
xlx_lLower bound of the interval
xux_uUpper bound of the interval

Bisection Method Iteration Count

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

En=Δx2n  ⟹  n=log⁡(Δx)−log⁡(Ed)log⁡(2)E_n = \frac{\Delta x}{2^{n}} \implies n = \frac{\log(\Delta x) - \log(E_d)}{\log(2)}

Variables

SymbolDescriptionUnit
EnE_nMaximum possible error after n iterations
Δx\Delta xInitial interval length (xu−xlx_u - x_l)
nnNumber of iterations
EdE_dDesired error tolerance

Interactive Simulation

Choose a starting interval and inspect how bisection halves a valid bracket. Try endpoints with the same sign to see why the method requires a sign change.

Bisection Method Visualization

Concept and model scope

Track how a sign-changing interval shrinks around a root.

Study f(x)=x3−4x−9f(x)=x^3-4x-9. The run stops when the absolute residual is at most 10⁻⁸, when bisection bounds the root to that tolerance, or when the method reaches its iteration or domain limit.

Controls

2.00

Starting x coordinate for the first endpoint or estimate.

3.00

Starting x coordinate for the second endpoint or estimate.

0

Select a computed step. The graph and numerical readout describe the same iteration.

f(x)=x3−4x−9f(x)=x^3-4x-9

Function and current root-finding stepf(x)01.653.35x
Current estimate
2.50000000
Step 0
Absolute residual
3.375e+0
Change from prior step
First step
Bracket error bound
5.000e-1

Converged within the bracket error bound. Final estimate 2.70652796.

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.

xr=xu−f(xu)(xl−xu)f(xl)−f(xu)x_r = x_u - \frac{f(x_u)(x_l - x_u)}{f(x_l) - f(x_u)}

Variables

SymbolDescriptionUnit
xrx_rImproved estimate of the root
xlx_lLower bound
xux_uUpper bound
f(xl)f(x_l)Function value at the lower bound
f(xu)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)=0f(x) = 0 is rearranged into the form x=g(x)x = g(x).

Convergence Criterion: The method will converge to the root if the magnitude of the derivative of g(x)g(x) evaluated at the root is less than 11, i.e., ∣g′(x)∣<1|g'(x)| < 1. If ∣g′(x)∣>1|g'(x)| > 1, the method diverges. The method converges linearly.

Fixed-Point Iteration Formula

Iterative formula for fixed-point iteration.

xi+1=g(xi)x_{i+1} = g(x_i)

Variables

SymbolDescriptionUnit
xi+1x_{i+1}Next estimate of the root
xix_iCurrent estimate of the root
g(x)g(x)Rearranged function x=g(x)x = g(x)

Newton-Raphson Method

Perhaps the most widely used of all root-locating formulas. If the initial guess at the root is xix_i, a tangent can be extended from the point [xi,f(xi)][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)f(x) using its tangent line at the current guess xix_i. The x-intercept of this tangent line becomes the next guess xi+1x_{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.

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

Variables

SymbolDescriptionUnit
xi+1x_{i+1}Next estimate of the root
xix_iCurrent estimate of the root
f(xi)f(x_i)Function value at the current estimate
f′(xi)f'(x_i)Derivative of the function at the current estimate

Interactive Simulation

Choose a starting estimate and follow the Newton–Raphson tangent intersections. Try a zero derivative to see when the method stops.

Newton-Raphson Method Visualization

Concept and model scope

Track how the local tangent proposes a new estimate and see what happens when the derivative vanishes.

Study f(x)=x2−4f(x)=x^2-4. The run stops when the absolute residual is at most 10⁻⁸, when bisection bounds the root to that tolerance, or when the method reaches its iteration or domain limit.

Controls

4.00

Starting x coordinate for the first endpoint or estimate.

0

Select a computed step. The graph and numerical readout describe the same iteration.

f(x)=x2−4f(x)=x^2-4

Function and current root-finding stepf(x)02.154.35x
Current estimate
4.00000000
Step 0
Absolute residual
1.200e+1
Change from prior step
First step
Next estimate
2.50000000

Converged within the residual tolerance. Final estimate 2.00000000.

Zero or Small Derivative Risk

The Newton-Raphson method requires the evaluation of the derivative f′(x)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)=0f''(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 x1x_1 and x2x_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.

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

Variables

SymbolDescriptionUnit
xi+1x_{i+1}Next estimate of the root
xix_iCurrent estimate of the root
xi−1x_{i-1}Previous estimate of the root
f(xi)f(x_i)Function value at current estimate
f(xi−1)f(x_{i-1})Function value at previous estimate

Interactive Simulation

Choose two starting estimates and follow the secant intersections. Compare distinct and coincident starting estimates.

Secant Method Visualization

Concept and model scope

Compare successive secant intercepts as the method searches for a root without derivatives.

Study f(x)=e−x−xf(x)=e^{-x}-x. The run stops when the absolute residual is at most 10⁻⁸, when bisection bounds the root to that tolerance, or when the method reaches its iteration or domain limit.

Controls

0.00

Starting x coordinate for the first endpoint or estimate.

1.00

Starting x coordinate for the second endpoint or estimate.

0

Select a computed step. The graph and numerical readout describe the same iteration.

f(x)=e−x−xf(x)=e^{-x}-x

Function and current root-finding stepf(x)0-0.351.35x
Current estimate
1.00000000
Step 0
Absolute residual
6.321e-1
Change from prior step
First step
Next estimate
0.61269984

Converged within the residual tolerance. Final estimate 0.56714329.

Convergence Rates

The speed at which a root-finding method approaches the true root is measured by its rate of convergence. If eie_i is the error at iteration ii, the relationship ei+1≈Ceipe_{i+1} \approx C e_i^p defines the convergence rate pp.

Common Convergence Orders

  • Linear (p=1p=1): The error is reduced by a constant factor each step (e.g., Bisection method, Fixed-Point Iteration).
  • Superlinear (1<p<21 < p < 2): Faster than linear but slower than quadratic (e.g., Secant method, p≈1.618p \approx 1.618).
  • Quadratic (p=2p=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).

Root-Finding Strategy and Convergence Checks

Choose a root-solving path from the available bracket and derivative, then verify convergence or route failure to a safeguarded alternative.

Check exact endpoints first. A sign change brackets a root only when f is continuous on the interval. With a valid bracket, use Brent's method: prefer inverse quadratic interpolation when three distinct points are available, otherwise try a secant step; reject any candidate outside the bracket or failing Brent's progress safeguards and use the bracket midpoint. Preserve the sign bracket and continue until both task-appropriate residual and bracket-width tolerances pass or the iteration limit is reached. Without a bracket, use Newton-Raphson only with a usable derivative and credible starting estimate; otherwise use Secant with two distinct estimates. Continue the open method only while steps remain finite and progressing, and require both task-appropriate residual and root-change tolerances. If an open method stalls, becomes non-finite, or reaches its limit, search a bounded interval for a sign-changing bracket and use Brent when one is found; otherwise revise the estimates or formulation. A small residual alone may not imply a small root error for a flat or ill-conditioned root, so report the final residual and an error indicator.

Root-Finding Strategy and Convergence ChecksChoose a root-solving path from the available bracket and derivative, then verify convergence or route failure to a safeguarded alternative.. Check exact endpoints first. A sign change brackets a root only when f is continuous on the interval. With a valid bracket, use Brent's method: prefer inverse quadratic interpolation when three distinct points are available, otherwise try a secant step; reject any candidate outside the bracket or failing Brent's progress safeguards and use the bracket midpoint. Preserve the sign bracket and continue until both task-appropriate residual and bracket-width tolerances pass or the iteration limit is reached. Without a bracket, use Newton-Raphson only with a usable derivative and credible starting estimate; otherwise use Secant with two distinct estimates. Continue the open method only while steps remain finite and progressing, and require both task-appropriate residual and root-change tolerances. If an open method stalls, becomes non-finite, or reaches its limit, search a bounded interval for a sign-changing bracket and use Brent when one is found; otherwise revise the estimates or formulation. A small residual alone may not imply a small root error for a flat or ill-conditioned root, so report the final residual and an error indicator.. Start → Define f(x) = 0, tolerances, and estimates; Define f(x) = 0, tolerances, and estimates → Is a tested endpoint an exact root?; Is a tested endpoint an exact root? — Yes → Report endpoint root and residual; Is a tested endpoint an exact root? — No → Bracket: Brent; otherwise Newton or Secant with Brent fallback; Report endpoint root and residual → Endpoint root found; Bracket: Brent; otherwise Newton or Secant with Brent fallback → Did method-specific residual and error tests pass?; Did method-specific residual and error tests pass? — Yes → Report root, residual, and error indicator; Did method-specific residual and error tests pass? — No → Revise estimates or formulation; report unresolved root; Report root, residual, and error indicator → Converged; Revise estimates or formulation; report unresolved root → Unresolved

Start → Define f(x) = 0, tolerances, and estimates; Define f(x) = 0, tolerances, and estimates → Is a tested endpoint an exact root?; Is a tested endpoint an exact root? — Yes → Report endpoint root and residual; Is a tested endpoint an exact root? — No → Bracket: Brent; otherwise Newton or Secant with Brent fallback; Report endpoint root and residual → Endpoint root found; Bracket: Brent; otherwise Newton or Secant with Brent fallback → Did method-specific residual and error tests pass?; Did method-specific residual and error tests pass? — Yes → Report root, residual, and error indicator; Did method-specific residual and error tests pass? — No → Revise estimates or formulation; report unresolved root; Report root, residual, and error indicator → Converged; Revise estimates or formulation; report unresolved root → Unresolved

  • Start: terminator
  • Define f(x) = 0, tolerances, and estimates: process
  • Is a tested endpoint an exact root?: decision
  • Report endpoint root and residual: process
  • Endpoint root found: terminator
  • Bracket: Brent; otherwise Newton or Secant with Brent fallback: subprocess
  • Did method-specific residual and error tests pass?: decision
  • Report root, residual, and error indicator: process
  • Converged: terminator
  • Revise estimates or formulation; report unresolved root: process
  • Unresolved: terminator

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)=0f(x)=0 and f′(x)=0f'(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.

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

Variables

SymbolDescriptionUnit
xi+1x_{i+1}Next estimate of the root
xix_iCurrent estimate of the root
f(xi)f(x_i)Function value
f′(xi)f'(x_i)First derivative
f′′(xi)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, f1(x,y)=0f_1(x, y) = 0 and f2(x,y)=0f_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.

xi+1=xi−f1∂f2∂y−f2∂f1∂y∂f1∂x∂f2∂y−∂f1∂y∂f2∂xx_{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

SymbolDescriptionUnit
xi+1x_{i+1}Next estimate for x
xix_iCurrent estimate for x
f1,f2f_1, f_2Nonlinear equations in the system
∂fj∂k\frac{\partial f_j}{\partial k}Partial derivative of function jj with respect to variable kk

Roots of Polynomials

Polynomials of the form f(x)=a0+a1x+a2x2+⋯+anxnf(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 rr as (x−r)(x - r) to find subsequent roots.

Once a root rr of an nn-th degree polynomial Pn(x)P_n(x) is found, the polynomial can be reduced to a lower-degree polynomial Qn−1(x)Q_{n-1}(x) by factoring out (x−r)(x - r).

Polynomial Deflation

Reduces the degree of a polynomial after finding a root rr.

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

Variables

SymbolDescriptionUnit
Pn(x)P_n(x)Original polynomial of degree nn
rrA known root
Qn−1(x)Q_{n-1}(x)Deflated polynomial of degree n−1n-1

Subsequent roots are then found using Qn−1(x)Q_{n-1}(x). However, deflation is highly sensitive to round-off errors. If the root rr 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 Pn(x)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(xr)∣|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.