Root-Finding

The Central Idea

A root, or zero, of a function \(f\) is a value \(r\) satisfying

Root-finding asks us to approximate \(r\) numerically when an exact formula is unavailable, inconvenient, or unstable.

Equations Become Root Problems

Any equation

can be rewritten as

Define

Then solving the original equation is equivalent to finding roots of \(f\).

Example: Converting an Equation

Solve

Rewrite as

Define

Numerical root-finding can now be applied directly to \(f\).

Why Numerical Root-Finding Is Needed

Exact algebraic solutions are not always practical.

Examples include:

• transcendental equations;
• high-degree polynomial equations;
• equations arising from simulation or measurement;
• implicit models;
• equations whose exact solutions exist but are cumbersome to use.

Two Broad Families of Methods

Root-finding methods can be organized into two broad families.

1. Bracketing methods: maintain an interval known to contain a root.
2. Open methods: generate approximations without always preserving a bracket.

Bracketing methods emphasize robustness. Open methods often emphasize speed.

Bracketing a Root

Suppose \(f\) is continuous on \([a,b]\) and

Then \(f(a)\) and \(f(b)\) have opposite signs.

By the Intermediate Value Theorem, there is at least one root in

Why a Sign Change Matters

If a continuous function changes sign between two points, its graph must cross the horizontal axis somewhere between them.

For example, if

and

continuity guarantees at least one root in \((1,2)\).

A Sign Change Does Not Guarantee a Unique Root

The Intermediate Value Theorem guarantees at least one root, not exactly one.

A function may cross the axis several times inside the interval.

Additional information, such as monotonicity, may be needed to establish uniqueness.

A Root May Exist Without a Sign Change

Consider

The root \(x=0\) has even multiplicity.

The function touches the axis but does not change sign.

Therefore, sign-change bracketing is powerful but does not detect every possible root.

The Bisection Method

Bisection begins with a continuous function and a bracket

satisfying

Compute the midpoint

Then retain the half-interval that still contains a sign change.

Bisection Step by Step

1. Start with \(a\) and \(b\) such that \(f(a)f(b)<0\).
2. Compute \(m=(a+b)/2\).
3. Evaluate \(f(m)\).
4. If \(f(m)=0\), stop.
5. If \(f(a)f(m)<0\), replace \(b\) by \(m\).
6. Otherwise, replace \(a\) by \(m\).
7. Repeat.

Example: Bisection Setup

Find a root of

Since

and

there is a root in

First Bisection Step

The midpoint is

Evaluate:

Since

and

the root lies in

Second Bisection Step

The new midpoint is

Then

The root therefore lies in

Bisection Error Bound

Each bisection step cuts the interval length in half.

If the initial interval length is

then after \(n\) bisections the interval length is

If the midpoint is used as the approximation, the root error is bounded by half that width:

How Many Bisection Steps Are Needed?

Suppose we require

It is sufficient to choose \(n\) so that

Solving for \(n\) gives a predictable computational budget.

Strengths of Bisection

• simple to understand and implement;
• guaranteed to converge under the bracketing assumptions;
• maintains a certified root interval;
• has a clear error bound;
• requires only function evaluations.

Limitations of Bisection

• convergence is relatively slow;
• a sign-changing bracket is required;
• even-multiplicity roots may not be detected by sign change;
• the method does not use derivative information.

Linear Convergence

Bisection reduces the interval error by a factor of approximately

each step.

This is an example of linear convergence.

Linear convergence is reliable but generally slower than quadratic convergence.

Fixed-Point Iteration

Instead of solving

we may rewrite the equation as

A root becomes a fixed point of \(g\).

Starting from \(x_0\), define

What Is a Fixed Point?

A value \(r\) is a fixed point of \(g\) if

If the iteration converges,

then under appropriate continuity assumptions,

Not Every Rearrangement Converges

An equation can often be rewritten as \(x=g(x)\) in many different ways.

These rearrangements are algebraically equivalent but can have very different numerical behavior.

Some fixed-point iterations converge rapidly, some slowly, and some diverge.

Local Fixed-Point Convergence

Suppose \(r\) is a fixed point:

If

then nearby errors tend to contract:

This supports local convergence.

When Fixed-Point Iteration Can Diverge

If

then nearby perturbations are locally amplified.

The iteration may move away from the fixed point rather than toward it.

Example: Fixed-Point Form

Consider

Define

Then

Starting from a suitable \(x_0\), this iteration converges to the familiar fixed point near \(0.739\).

Newton's Method

Newton's method uses the tangent line to approximate the root of

Starting from \(x_n\), linearize:

Set the tangent-line approximation equal to zero and solve for \(x\).

Deriving Newton's Formula

From

solve for \(x_{n+1}\):

Therefore,

Geometric Interpretation of Newton's Method

At \(x_n\), draw the tangent line to the graph of \(y=f(x)\).

The next approximation \(x_{n+1}\) is where that tangent line intersects the \(x\)-axis.

Each step replaces the nonlinear function locally with a linear model.

Example: Newton's Method for \(\sqrt{2}\)

Solve

Here,

and

Newton's formula becomes

Simplifying the Newton Iteration

The iteration can be rewritten as

Thus,

This is also known as the Babylonian or Heron iteration for square roots.

Newton Iteration from \(x_0=1.5\)

Start with

Then

The next iteration gives approximately

The root is approached rapidly.

Quadratic Convergence

Near a simple root and under appropriate smoothness assumptions, Newton's method often satisfies

This is quadratic convergence.

Once sufficiently close to the root, the number of correct digits can roughly double from one iteration to the next.

Simple Roots

A root \(r\) is simple when

and

Newton's strongest local convergence behavior is associated with simple roots.

Multiple Roots

If

and

the root may have multiplicity greater than one.

Ordinary Newton iteration can then converge more slowly than in the simple-root case.

Modified Newton Method for Known Multiplicity

If a root has known multiplicity \(m\), a modified iteration is

Under suitable assumptions, this can restore faster local convergence.

Newton's Method Can Fail

Newton's method is powerful but not automatically reliable from every starting point.

Failure modes include:

• \(f'(x_n)=0\);
• a derivative that is extremely small;
• iterations leaving the useful domain;
• cycling between points;
• convergence to an unintended root;
• divergence from a poor starting value.

Small Derivatives Are Dangerous

Newton's correction is

If \(f'(x_n)\) is very small, the correction can become extremely large.

This can launch the next iterate far away from the desired root.

Starting Values Matter

Newton's method is generally a local method.

Fast convergence is most reliable when the starting value is already within a suitable neighborhood of the desired root.

Bracketing or graphical inspection can help produce a better initial estimate.

The Secant Method

Newton's method requires \(f'(x)\).

The secant method avoids explicit derivatives by approximating the derivative with a difference quotient:

Secant Formula

Substitute the difference quotient into Newton's formula:

The method requires two starting values rather than one.

Geometric Interpretation of the Secant Method

Instead of using the tangent line at one point, the secant method uses the line through

and

The next iterate is where that secant line crosses the \(x\)-axis.

Secant Convergence

Under suitable conditions, the secant method converges faster than linearly but slower than quadratically.

Its convergence order is approximately

This number is the golden ratio.

Strengths of the Secant Method

• does not require analytic derivatives;
• often converges faster than bisection;
• uses only function evaluations;
• is easy to adapt to many nonlinear equations.

Limitations of the Secant Method

• convergence is not guaranteed from arbitrary starting points;
• the denominator can become very small;
• the method may leave a desired interval;
• it does not preserve a root bracket automatically.

False Position

The false-position, or regula falsi, method combines a sign-changing bracket with a secant-line estimate.

It computes the secant intercept but retains the subinterval that preserves the sign change.

This gives some of the speed intuition of secant methods while maintaining a bracket.

Hybrid Methods

Practical root-finding software often combines multiple methods.

A hybrid strategy may:

• begin with a reliable bracket;
• attempt a faster Newton or secant step;
• accept the fast step when it remains safe;
• fall back to bisection when necessary.

Hybrid methods balance robustness and speed.

Residual as a Stopping Measure

For an approximation \(x_n\), the residual is

A natural stopping condition is

But conditioning determines whether a small residual implies a small root error.

Step Size as a Stopping Measure

Another common criterion is

A small step suggests the iterates have stabilized.

However, a small step alone does not prove the correct root has been reached.

Relative Step Criterion

When the scale of the root varies, use a relative criterion such as

This avoids demanding the same absolute accuracy at every magnitude.

Bracket Width as a Stopping Measure

Bracketing methods provide a direct interval-based criterion:

If the root remains inside the bracket, the interval width provides a certified uncertainty measure.

Maximum Iteration Safeguard

Every iterative method should have a maximum iteration limit.

This prevents an algorithm from running indefinitely when:

• convergence fails;
• the tolerance is unrealistic;
• the method cycles;
• rounding prevents further improvement.

Use More Than One Stopping Test

Reliable root-finding often combines:

• residual size;
• step size;
• bracket width;
• maximum iteration count;
• domain and finite-value checks.

No single test answers every reliability question.

Forward Error and Root-Finding

If \(r\) is the exact root and \(x_n\) is an approximation, the forward error is

The difficulty is that \(r\) is usually unknown.

Root-finding methods therefore rely on computable estimates and bounds.

Residual-to-Error Estimate

Near a simple root \(r\),

Therefore,

If the derivative near the root is small, a small residual may correspond to a larger root error.

Root Conditioning

For a simple root, sensitivity is strongly connected to

If

is small, the root location can be sensitive to perturbations in the function.

Multiple Roots Are More Sensitive

At a multiple root,

The graph is flatter at the axis, and small function perturbations can move the apparent root significantly.

This is one reason repeated roots are numerically more delicate.

Convergence Rate

Suppose

A method has convergence order \(p\) when, approximately,

for some constant \(C\) and sufficiently large \(n\).

Common Convergence Orders

• bisection: linear;
• many fixed-point iterations: linear;
• secant method: approximately order \(1.618\);
• Newton's method near a simple root: quadratic.

Faster asymptotic order does not automatically mean a method is best in every practical situation.

Cost per Iteration Matters

Newton's method may use fewer iterations but require both

and

The secant method avoids derivative evaluation but uses two recent points.

Bisection requires only one new function evaluation per step after initialization.

Convergence Speed Is Not the Only Goal

A numerical method should be judged by:

• robustness;
• cost per iteration;
• convergence rate;
• availability of derivatives;
• quality of initial guesses;
• conditioning of the root;
• required error guarantees.

Graphical Preprocessing

Before iterating, it can be valuable to inspect the graph or sample the function.

This can help identify:

• possible root intervals;
• multiple roots;
• singularities;
• flat regions;
• poor starting values.

Tabulation as a Bracketing Strategy

Evaluate

on a coarse grid.

Whenever consecutive values have opposite signs,

a continuous function has at least one root in that subinterval.

Root-Finding with Discontinuities

A sign change alone is not enough if continuity fails.

For example,

changes sign across \(x=0\), but it has no root there.

Continuity must be checked before using a sign-change theorem.

Domain Restrictions Matter

Root iterations can leave the domain of the function.

Examples include:

• square roots of negative numbers in real arithmetic;
• logarithms of nonpositive values;
• division by zero;
• model parameters leaving physically meaningful ranges.

A practical solver should guard against invalid iterates.

Detecting Stagnation

Floating-point rounding can eventually produce

even when the mathematical method could continue in exact arithmetic.

This is numerical stagnation.

Further iterations then provide no improvement.

Detecting Divergence

Indicators of divergence include:

• rapidly growing \(|x_n|\);
• rapidly growing residuals;
• oscillation without contraction;
• repeated invalid values;
• failure to improve after many steps.

A Reliable Bisection Workflow

1. Verify continuity on the interval.
2. Confirm \(f(a)f(b)<0\).
3. Compute the midpoint.
4. Evaluate the midpoint sign.
5. Retain the sign-changing half.
6. Track the bracket width.
7. Stop when the error target is met.

A Reliable Newton Workflow

1. Define \(f(x)\) and \(f'(x)\).
2. Choose a reasonable starting value.
3. Evaluate \(f(x_n)\) and \(f'(x_n)\).
4. Reject or safeguard steps with very small derivatives.
5. Compute the Newton correction.
6. Check the new iterate for domain validity.
7. Monitor residual and step size.
8. Stop when tolerances are satisfied or a safeguard triggers.

A Reliable Secant Workflow

1. Choose two starting values.
2. Evaluate the function at both points.
3. Form the secant slope.
4. Check that the slope denominator is not too small.
5. Compute the new intercept.
6. Shift the two-point history forward.
7. Monitor residual and step size.
8. Stop according to the required tolerance and safeguards.

Common Error: Using Bisection Without Continuity

Opposite signs at two endpoints do not guarantee a root if the function is discontinuous between them.

Always verify the continuity assumption before invoking the Intermediate Value Theorem.

Common Error: Assuming a Sign Change Means One Root

A sign change guarantees at least one root, not uniqueness.

Multiple crossings may occur inside the bracket.

Common Error: Assuming No Sign Change Means No Root

Even-multiplicity roots can touch the axis without changing sign.

Root searches should therefore use more than sign-change detection when repeated roots are possible.

Common Error: Using Newton's Method Blindly

Newton's method is not guaranteed to converge from every initial value.

Inspect derivatives, domain restrictions, and the local graph before trusting a long iteration.

Common Error: Dividing by a Tiny Derivative

If

is very small, the Newton step may become enormous.

A robust implementation should detect and handle this situation.

Common Error: Stopping Only Because Two Iterates Match

A small step can result from stagnation or a poorly conditioned update.

Check the residual as well as the change in the iterate.

Common Error: Using Only the Residual

A small residual is not sufficient when the root is ill-conditioned.

A flat function near the root can make \(f(x_n)\) small while \(x_n\) remains noticeably displaced from the exact root.

Common Error: Ignoring Multiple Roots

Newton's method can lose quadratic convergence at repeated roots.

If multiplicity is known or suspected, adjust expectations and consider a modified method.

Common Error: Chasing More Digits Than the Data Support

A highly accurate numerical root of an uncertain model is not necessarily a highly accurate estimate of the real-world quantity.

Root-finding error should be interpreted alongside measurement, modeling, and conditioning error.

Example: Bisection Error Budget

Suppose a root is bracketed in

The initial interval length is \(1\).

After \(10\) bisections, the midpoint error is bounded by

Therefore,

Example: Newton Step

Let

Then

Starting from \(x_0=2\),

and

Therefore,

Example: Secant Step

Suppose

and

The secant estimate is

Thus,

Practice 1: Identify a Bracket

For

show that \([1,2]\) brackets a root.

Practice 2: First Bisection Step

Using

on \([1,2]\), compute the first midpoint and identify the new bracket.

Practice 3: Bisection Error Bound

An initial interval has length \(4\).

What is the midpoint error bound after \(8\) bisections?

Practice 4: Newton Formula

Derive the Newton iteration for

Practice 5: One Newton Step

Using

and

compute \(x_1\).

Practice 6: Fixed-Point Convergence Test

Suppose \(r\) is a fixed point of \(g\) and

What does this suggest about local convergence?

Practice 7: Secant Formula Concept

What derivative approximation does the secant method use in place of \(f'(x_n)\)?

Practice 8: Residual

For

compute the residual at

Practice 9: Method Selection

Which method is the most natural choice when:

1. a guaranteed sign-changing bracket is available and robustness is the priority;
2. a good starting point and derivative are available and rapid local convergence is desired?

Practice 10: Explain the Risk

Why can Newton's method behave poorly when \(f'(x_n)\) is close to zero?

Practice Answers

Practice 1

Evaluate the endpoints:

and

Since

the interval

brackets at least one root.

Practice 2

The midpoint is

Then

Since \(f(1.5)<0\) and \(f(2)>0\), the new bracket is

Practice 3

The midpoint error bound is

or approximately

Practice 4

Since

and

Newton's method gives

Practice 5

Practice 6

Since

nearby perturbations contract locally. This suggests local convergence to the fixed point from sufficiently close starting values.

Practice 7

The secant method uses

Practice 8

Practice 9

1. Bisection is the natural robust choice.
2. Newton's method is the natural fast local choice.

Practice 10

Newton's correction contains division by \(f'(x_n)\). If that derivative is close to zero, the correction can become extremely large, sending the next iterate far from the desired root or outside the valid domain.

What to Remember

Root-finding solves

by constructing successive approximations to a zero of \(f\).

• bisection uses a sign-changing bracket and provides guaranteed interval reduction;
• fixed-point iteration rewrites the problem as \(x=g(x)\);
• local fixed-point convergence is supported when \(|g'(r)|<1\);
• Newton's method uses tangent-line linearization;
• Newton's method is often quadratically convergent near a simple root;
• the secant method approximates derivatives with recent function values;
• multiple roots and small derivatives can reduce reliability;
• residual, step size, bracket width, and iteration limits should be used together;
• conditioning determines how residual error relates to root error;
• hybrid methods combine bracketing reliability with faster open steps.

The most important practical principle is to match the method to the structure of the problem rather than treating one root-finding algorithm as universally superior.

Where We Go Next

Root-finding addresses one-dimensional nonlinear equations. Many scientific and engineering computations require the solution of much larger systems involving vectors and matrices.

The next lesson, Numerical Linear Algebra, develops the computational treatment of linear systems, matrix factorizations, pivoting, conditioning, iterative methods, and the numerical issues that arise when matrix problems are solved in finite precision.