Solving Equations

1.1 The Bisection Method

1) Root

Root: A number $r$ satisfying

$$f(r)=0.$$

Finding a root of $f$ is equivalent to solving the equation $f(x)=0$.

2) Bracketing a Root

Bracketing: Finding an interval $[a,b]$ whose endpoint function values have opposite signs.

$$f(a)f(b)<0.$$

If $f$ is continuous on $[a,b]$, the Intermediate Value Theorem guarantees that at least one root lies in $(a,b)$.

3) Bisection Method

Bisection Method: A bracketing method that repeatedly halves an interval containing a root.

At each step, calculate the midpoint

$$c=\frac{a+b}{2}.$$

Then select the half interval in which the function changes sign:

$$f(a)f(c)<0 \quad\Longrightarrow\quad b=c,$$

or

$$f(c)f(b)<0 \quad\Longrightarrow\quad a=c.$$

The new interval continues to contain at least one root.

4) Bisection Error

After $n$ bisection steps, the interval length is

$$\frac{b-a}{2^n}.$$

Using the midpoint $x_c$ as the approximate root gives

$$|x_c-r| < \frac{b-a}{2^{n+1}}.$$

The Bisection Method therefore has a guaranteed error bound.

5) Required Number of Steps

To guarantee

$$|x_c-r|<\mathrm{TOL},$$

the required number of steps satisfies

$$\frac{b-a}{2^{n+1}} < \mathrm{TOL}.$$

Thus,

$$n > \log_2\left( \frac{b-a}{2\,\mathrm{TOL}} \right).$$

6) Correct Decimal Places

Correct to $p$ Decimal Places: An approximation whose absolute error satisfies

$$|x_c-r| < \frac{1}{2}\times10^{-p}.$$

7) Properties of the Bisection Method

• Requires a continuous function.
• Requires an initial sign-changing interval.
• Does not require derivatives.
• Guarantees convergence to a root within the bracket.
• Reduces the error by approximately one-half per step.
• Converges reliably but relatively slowly.

1.2 Fixed-Point Iteration

1) Fixed Point

Fixed Point: A number $r$ satisfying

$$g(r)=r.$$

An equation $f(x)=0$ can often be rewritten in the fixed-point form

$$x=g(x).$$

Different rearrangements of the same equation may have different convergence behavior.

2) Fixed-Point Iteration

Fixed-Point Iteration: An iterative method defined by

$$x_{i+1}=g(x_i), \qquad i=0,1,2,\ldots$$

starting from an initial guess $x_0$.

If the sequence converges to $r$ and $g$ is continuous, then

$$r=g(r),$$

so $r$ is a fixed point.

3) Iteration Error

The error at step $i$ is

$$e_i=|x_i-r|.$$

By the Mean Value Theorem,

$$x_{i+1}-r = g(x_i)-g(r) = g'(c_i)(x_i-r)$$

for some $c_i$ between $x_i$ and $r$.

Therefore,

$$e_{i+1} = |g'(c_i)|e_i.$$

Near the fixed point,

$$e_{i+1} \approx |g'(r)|e_i.$$

4) Fixed-Point Convergence Test

If

$$g(r)=r$$

and

$$|g'(r)|<1,$$

then Fixed-Point Iteration is locally convergent to $r$.

The approximate convergence rate is

$$S=|g'(r)|.$$

If

$$|g'(r)|>1,$$

nearby iterates generally move away from the fixed point.

5) Linear Convergence

Linear Convergence: An iterative method converges linearly with rate $S$ if

$$\lim_{i\to\infty} \frac{e_{i+1}}{e_i} = S, \qquad 0<S<1.$$

For sufficiently large $i$,

$$e_{i+1}\approx Se_i.$$

A smaller value of $S$ means faster linear convergence.

6) Locally Convergent Method

Local Convergence: A method is locally convergent to $r$ if it converges to $r$ whenever the initial guess is sufficiently close to $r$.

Local convergence does not guarantee convergence from every initial guess.

7) Cobweb Diagram

Cobweb Diagram: A graphical representation of Fixed-Point Iteration using the curves

$$y=g(x) \qquad\text{and}\qquad y=x.$$

The intersections of the two curves are fixed points.

A fixed point is locally attracting when

$$|g'(r)|<1$$

and locally repelling when

$$|g'(r)|>1.$$

8) Stopping Criteria

Because the exact root is usually unknown, practical stopping criteria include

$$|x_{i+1}-x_i|<\mathrm{TOL},$$ $$\frac{|x_{i+1}-x_i|}{\max(1,|x_{i+1}|)} < \mathrm{TOL},$$

or

$$|f(x_i)|<\mathrm{TOL}.$$

A maximum iteration count should also be used to prevent infinite iteration.

1.3 Limits of Accuracy

1) Forward Error

Forward Error: The distance between an approximate root $x_a$ and the exact root $r$.

$$E_{\mathrm{forward}} = |x_a-r|.$$

Forward error directly measures the accuracy of the computed solution.

2) Backward Error

Backward Error: The amount by which the equation fails to be satisfied at the approximate root.

For $f(x)=0$,

$$E_{\mathrm{backward}} = |f(x_a)|.$$

A small backward error means that $x_a$ is an exact root of a nearby problem.

A small backward error does not always imply a small forward error.

3) Simple Root

Simple Root: A root $r$ satisfying

$$f(r)=0 \qquad\text{and}\qquad f'(r)\neq0.$$

A simple root has multiplicity one.

4) Multiple Root

Root of Multiplicity $m$: A root $r$ satisfying

$$f(r) = f'(r) = \cdots = f^{(m-1)}(r) = 0$$

and

$$f^{(m)}(r)\neq0.$$

A root is called a multiple root when

$$m>1.$$

Equivalently, a function with a root of multiplicity $m$ can be written locally as

$$f(x)=(x-r)^m h(x), \qquad h(r)\neq0.$$

Functions are relatively flat near multiple roots, so a very small backward error may correspond to a much larger forward error.

5) Sensitivity

Sensitivity: The degree to which small changes in the input problem cause changes in the solution.

A problem is sensitive if small perturbations in the equation produce large changes in its roots.

6) Perturbed Root Problem

Suppose $r$ is a root of

$$f(x)=0$$

and $r+\Delta r$ is a root of the perturbed equation

$$f(x)+\epsilon g(x)=0.$$

For a simple root and sufficiently small $\epsilon$,

$$\Delta r \approx -\epsilon \frac{g(r)}{f'(r)}.$$

This is the sensitivity formula for roots.

A small value of $|f'(r)|$ can cause a large change in the root.

7) Relative Error Magnification

Error Magnification Factor: The ratio of relative forward error to relative backward error.

$$\text{Error Magnification Factor} = \frac{\text{relative forward error}} {\text{relative backward error}}.$$

For the perturbation $\epsilon g(x)$,

$$\text{Error Magnification Factor} = \frac{|g(r)|}{|r f'(r)|}.$$

A large error magnification factor indicates a sensitive problem.

8) Condition Number

Condition Number: A measure of the maximum error magnification inherent in a mathematical problem.

• A problem with a condition number near $1$ is well-conditioned.
• A problem with a large condition number is ill-conditioned.

Conditioning is a property of the problem, not the algorithm.

9) Stability

Numerical Stability: A property of an algorithm that produces a solution with small backward error.

Stability describes error introduced or amplified by the algorithm.

Conditioning and stability are different:

• Conditioning concerns sensitivity of the problem.
• Stability concerns behavior of the algorithm.

A stable algorithm applied to a well-conditioned problem generally produces a small forward error.

1.4 Newton’s Method

1) Tangent-Line Approximation

Near the current approximation $x_i$, the function can be approximated by its tangent line:

$$f(x) \approx f(x_i)+f'(x_i)(x-x_i).$$

Setting this approximation equal to zero gives the next root estimate.

2) Newton’s Method

Newton’s Method: An iterative root-finding method defined by

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

Newton’s Method requires:

• An initial guess $x_0$.
• Evaluation of $f(x)$.
• Evaluation of $f'(x)$.
• A nonzero derivative at each iterate.

3) Newton Iteration Function

Newton’s Method can be viewed as Fixed-Point Iteration with

$$g(x) = x-\frac{f(x)}{f'(x)}.$$

At a simple root $r$,

$$g'(r)=0,$$

which explains its fast local convergence.

4) Quadratic Convergence

Quadratic Convergence: An iterative method converges quadratically if

$$\lim_{i\to\infty} \frac{e_{i+1}}{e_i^2} = M$$

for some constant $M>0$.

Near a simple root,

$$e_{i+1} \approx M e_i^2.$$

Quadratic convergence approximately doubles the number of correct digits at each step.

5) Newton Convergence Theorem

If $f$ is twice continuously differentiable near $r$ and

$$f(r)=0, \qquad f'(r)\neq0,$$

then Newton’s Method is locally quadratically convergent to $r$.

The asymptotic error satisfies

$$e_{i+1} \approx \left| \frac{f''(r)}{2f'(r)} \right| e_i^2.$$

6) Newton’s Method at Multiple Roots

For a root of multiplicity $m>1$, ordinary Newton’s Method converges only linearly.

The asymptotic error relation is

$$e_{i+1} \approx \frac{m-1}{m}e_i.$$

Thus, multiple roots remove the usual quadratic convergence.

7) Modified Newton’s Method

If the root multiplicity $m$ is known, use

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

Modified Newton’s Method: A version of Newton’s Method that restores quadratic convergence at a root of known multiplicity.

8) Failure of Newton’s Method

Newton’s Method can fail when:

• $f'(x_i)=0$.
• The initial guess is too far from a root.
• Iterates diverge.
• Iterates enter a cycle.
• An iterate leaves the domain of the function.
• The function or derivative is evaluated inaccurately.
• The root is multiple and the method converges too slowly.

Newton’s Method is fast near a suitable root but does not guarantee global convergence.

1.5 Root-Finding without Derivatives

1) Secant Approximation

The derivative at $x_i$ can be approximated using two consecutive iterates:

$$f'(x_i) \approx \frac{f(x_i)-f(x_{i-1})} {x_i-x_{i-1}}.$$

This replaces the tangent line in Newton’s Method with a secant line.

2) Secant Method

Secant Method: A derivative-free iterative method defined by

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

The Secant Method requires two initial guesses, $x_0$ and $x_1$.

Unlike the Bisection Method, the initial guesses do not have to bracket a root.

3) Superlinear Convergence

Superlinear Convergence: Convergence faster than linear but slower than quadratic.

For a simple root, the Secant Method has convergence order

$$\alpha = \frac{1+\sqrt{5}}{2} \approx 1.618.$$

Thus,

$$e_{i+1} \approx C e_i^\alpha.$$

The Secant Method usually converges more slowly than Newton’s Method but does not require derivative evaluations.

4) Method of False Position

Method of False Position: A bracketing method that replaces the midpoint of the Bisection Method with the root of a secant line.

Given

$$f(a)f(b)<0,$$

the next approximation is

$$c = \frac{b f(a)-a f(b)} {f(a)-f(b)}.$$

The new interval is chosen so that its endpoint values continue to have opposite signs.

False Position preserves the root bracket but may converge very slowly if one endpoint remains fixed.

5) Muller’s Method

Muller’s Method: A derivative-free method that fits a quadratic polynomial

$$y=p(x)$$

through three previous points and uses a root of the quadratic as the next approximation.

Muller’s Method can locate both real and complex roots.

6) Inverse Quadratic Interpolation

Inverse Quadratic Interpolation: A method that fits an inverse quadratic polynomial

$$x=p(y)$$

through three function values and evaluates it at $y=0$.

Given the points

$$(a,A),\qquad(b,B),\qquad(c,C),$$

where

$$A=f(a),\qquad B=f(b),\qquad C=f(c),$$

the interpolating polynomial is

$$P(y) = a\frac{(y-B)(y-C)}{(A-B)(A-C)} + b\frac{(y-A)(y-C)}{(B-A)(B-C)} + c\frac{(y-A)(y-B)}{(C-A)(C-B)}.$$

The next approximation is

$$x_{\mathrm{new}}=P(0).$$

Inverse Quadratic Interpolation generally converges faster than the Secant Method.

7) Hybrid Method

Hybrid Method: A root-finding method that combines a reliable bracketing method with faster open methods.

A hybrid method attempts fast steps when they appear safe and falls back to a guaranteed bracketing step when necessary.

8) Brent’s Method

Brent’s Method: A hybrid root-finding method combining:

• Bisection
• Secant Method
• Inverse Quadratic Interpolation

Brent’s Method maintains an interval satisfying

$$f(a)f(b)<0.$$

It attempts Inverse Quadratic Interpolation or a secant step when the result is sufficiently reliable.

Otherwise, it uses a bisection step.

Brent’s Method provides:

• Guaranteed convergence for a continuous function with a valid bracket.
• Faster practical convergence than pure bisection.
• No requirement for derivative evaluations.

It is commonly used as a general-purpose one-dimensional root solver.

Comparison of Root-Finding Methods

Method	Initial Requirement	Derivative	Convergence	Guaranteed
Bisection	Sign-changing interval	No	Linear	Yes
Fixed-Point Iteration	One initial guess	Depends on $g$	Usually linear	No
Newton’s Method	One initial guess	Yes	Quadratic at simple roots	No
Secant Method	Two initial guesses	No	Superlinear	No
False Position	Sign-changing interval	No	Usually linear	Yes
Brent’s Method	Sign-changing interval	No	Superlinear in practice	Yes

Essential Concepts

1. Root: A value $r$ satisfying $f(r)=0$.
2. Bracket: An interval whose endpoint function values have opposite signs.
3. Bisection Method: Repeatedly halves a bracket containing a root.
4. Bisection Error Bound: After $n$ steps, the midpoint error is less than $(b-a)/2^{n+1}$.
5. Fixed Point: A value $r$ satisfying $g(r)=r$.
6. Fixed-Point Iteration: Generates approximations using $x_{i+1}=g(x_i)$.
7. Local Convergence Test: Fixed-Point Iteration converges locally when $|g'(r)|<1$.
8. Linear Convergence: The error decreases by an approximately constant factor.
9. Forward Error: The distance between the approximate and exact solutions.
10. Backward Error: The residual $|f(x_a)|$ of an approximate root.
11. Root Multiplicity: The number of times a root occurs as a factor.
12. Conditioning: Sensitivity inherent in the mathematical problem.
13. Stability: Control of errors by the numerical algorithm.
14. Newton’s Method: Uses tangent lines and converges quadratically near a simple root.
15. Modified Newton’s Method: Restores quadratic convergence at a root of known multiplicity.
16. Secant Method: Approximates Newton’s Method without evaluating derivatives.
17. Superlinear Convergence: Faster than linear but slower than quadratic convergence.
18. False Position: Combines a secant approximation with root bracketing.
19. Inverse Quadratic Interpolation: Uses a quadratic model of the inverse function.
20. Brent’s Method: Combines bisection, secant, and inverse quadratic interpolation.