Chapter Introduction and Learning Objectives

Learning Objectives

By the end of this chapter, you should be able to:

1. 1Recognize a root-finding problem and distinguish it from a symbolic equation-solving problem.
2. 2Explain the role of the Intermediate Value Theorem in bracketing methods.
3. 3Apply the bisection method, compute error bounds, and determine the number of steps needed for a given tolerance.
4. 4Apply fixed-point iteration, recognize convergence conditions, and identify diverging cases.
5. 5Apply Newton's method, interpret it geometrically, and identify cases where it fails.
6. 6Apply the secant method and explain how it approximates Newton's method without requiring derivatives.
7. 7Apply appropriate stopping criteria to terminate root-finding iterations.
8. 8Compare root-finding methods by reliability, speed, and required information.
9. 9Identify common mistakes in numerical root-finding and interpret reliability warnings.

Sections at a Glance

• 3.1 What a Root-Finding Problem Is Equations without closed-form solutions; reformulating as \(f(x)=0\); the Abel–Ruffini theorem; why iteration replaces formula
• 3.2 Roots, Zeros, and Solutions Terminology; multiplicity; simple versus repeated roots; sign-change detection
• 3.3 Graphical Root Estimates Sketching to locate roots; the Intermediate Value Theorem; limitations of graphical methods
• 3.4 Bracketing Methods The bracket condition; establishing an initial interval; reliability of bracketing; IVT as the guarantee
• 3.5 Bisection Method Halving the interval; algorithm; worked example with table; linear convergence
• 3.6 Error Bounds for Bisection Guaranteed error bound \((b-a)/2^n\); predetermining step count; linear convergence explained
• 3.7 Fixed-Point Iteration Reformulating \(f(x)=0\) as \(g(x)=x\); convergence condition \(|g'|<1\); worked example; divergence example
• 3.8 Newton's Method Tangent-line derivation; Newton–Raphson formula; algorithm; worked example; quadratic convergence
• 3.9 Tangent Line Interpretation of Newton's Method Geometric meaning; why it converges quadratically; failure modes: flat derivative, bad start, repeated roots
• 3.10 Secant Method Finite-difference approximation to derivative; two starting values; algorithm; worked example; superlinear convergence
• 3.11 Stopping Criteria Absolute change; relative change; function value; interval width; combining criteria; maximum iteration limit
• 3.12 Comparing Root-Finding Methods Summary table; hybrid strategy; choosing a method in practice
• 3.13 Common Root-Finding Mistakes Seven common errors; misconceptions about convergence, stopping, and starting conditions
• 3.14 Preparing for Interpolation and Approximation Bridge to Part II; how root-finding ideas recur in later chapters

Vocabulary Before You Begin

What a Root-Finding Problem Is

Roots, Zeros, and Solutions

Graphical Root Estimates

Bracketing Methods

Bisection Method

Purpose:  Find a root of f on [a, b] within tolerance tol
Inputs:   Continuous function f
          Bracket [a, b] with f(a)*f(b) < 0
          Tolerance tol
          Maximum iterations N

Steps:
  1. Verify f(a) * f(b) < 0. If not, stop: bracket condition fails.
  2. For n = 1, 2, ..., N:
       a. Compute midpoint:  p = (a + b) / 2
       b. Compute f(p).
       c. If |b - a| / 2 < tol, or f(p) = 0:
            accept p as the root. Stop.
       d. If f(a) * f(p) < 0:  set b = p   (root in left half)
          Else:                  set a = p   (root in right half)
  3. If max iterations reached: report p with a warning.

Stopping criterion:  |b - a| / 2 < tol  or  f(p) = 0
Output:   Approximation p of the root
Notes:    Guaranteed to converge if f continuous and bracket valid.
          Convergence is linear: each step halves the interval.

Error Bounds for Bisection

Fixed-Point Iteration

Purpose:  Find fixed point of g(x) = x (i.e., root of f(x) = 0 rewritten as g(x) = x)
Inputs:   Function g, initial guess p_0, tolerance tol, max iterations N

Steps:
  1. For n = 0, 1, 2, ..., N-1:
       a. Compute p_{n+1} = g(p_n).
       b. If |p_{n+1} - p_n| < tol:  accept p_{n+1}. Stop.
  2. If max iterations reached: report best approximation with warning.

Stopping criterion:  |p_{n+1} - p_n| < tol
Output:   Approximation of fixed point p
Notes:    Converges when |g'(x)| < 1 near the fixed point.
          May diverge or converge to wrong value if |g'(x)| >= 1.
          The choice of g dramatically affects convergence.

Newton's Method

Purpose:  Find a root of f(x) = 0
Inputs:   Differentiable function f, derivative f'
          Initial guess p_0, tolerance tol, max iterations N

Steps:
  1. For n = 0, 1, 2, ..., N-1:
       a. Compute f(p_n) and f'(p_n).
       b. If f'(p_n) = 0: STOP. Derivative is zero; cannot proceed.
       c. Compute p_{n+1} = p_n - f(p_n) / f'(p_n).
       d. If |p_{n+1} - p_n| < tol or |f(p_{n+1})| < tol: accept p_{n+1}. Stop.
  2. If max iterations reached: report best approximation with warning.

Stopping criterion:  |p_{n+1} - p_n| < tol  or  |f(p_{n+1})| < tol
Output:   Approximation of root r
Notes:    Quadratic convergence near simple roots.
          Requires f'(p_n) ≠ 0.
          Starting point must be sufficiently close to root.
          Slow or fails at repeated roots. May cycle or diverge for bad starts.

Tangent Line Interpretation of Newton's Method

Secant Method

Purpose:  Find a root of f(x) = 0 without requiring f'
Inputs:   Function f, two initial guesses p_0 and p_1
          Tolerance tol, max iterations N

Steps:
  1. For n = 1, 2, ..., N:
       a. Compute q_0 = f(p_{n-1}),  q_1 = f(p_n).
       b. If q_1 - q_0 = 0: STOP. Division by zero; method cannot proceed.
       c. Compute p_{n+1} = p_n - q_1 * (p_n - p_{n-1}) / (q_1 - q_0).
       d. If |p_{n+1} - p_n| < tol: accept p_{n+1}. Stop.
  2. If max iterations reached: report best approximation with warning.

Stopping criterion:  |p_{n+1} - p_n| < tol
Output:   Approximation of root r
Notes:    No derivative required; approximates Newton's method.
          Superlinear convergence (order ≈ 1.618, the golden ratio).
          Requires two starting values.
          Does not maintain a bracket; convergence not guaranteed.

Stopping Criteria

Comparing Root-Finding Methods

Common Root-Finding Mistakes

Preparing for Interpolation and Approximation

Chapter Summary

• Section 3.1 Root-finding solves \(f(x)=0\) when algebraic formulas are unavailable. The Abel–Ruffini theorem guarantees no general formula exists for degree-5 polynomials; transcendental equations offer no symbolic solution at all. Numerical methods create converging sequences of approximations.
• Sections 3.2–3.4 Roots have multiplicity; simple roots behave better numerically. Graphical analysis locates roots approximately. The Intermediate Value Theorem guarantees a root in \([a,b]\) when \(f(a)\cdot f(b)<0\) and \(f\) is continuous — the bracket condition.
• Section 3.5–3.6 Bisection halves the bracket at each step: \(p_{n+1}=(a+b)/2\). Error bound: \(|p_n-r|\leq (b-a)/2^n\). Number of steps for tolerance \(\varepsilon\): \(n>\log_2((b-a)/\varepsilon)\). Convergence is guaranteed (linear) whenever the bracket is valid.
• Section 3.7 Fixed-point iteration rewrites \(f(x)=0\) as \(g(x)=x\) and iterates \(p_{n+1}=g(p_n)\). Converges when \(|g'(x)|<1\) near the fixed point (Contraction Mapping Theorem). The choice of \(g\) determines whether the iteration converges or diverges.
• Sections 3.8–3.9 Newton's method uses the tangent line at \(p_n\): \(p_{n+1}=p_n-f(p_n)/f'(p_n)\). Converges quadratically near simple roots — digits roughly double per step. Requires \(f'\), a good starting point, and \(f'(p_n)\neq 0\). Fails at repeated roots and with poor starts.
• Section 3.10 The secant method approximates \(f'\) using two previous function values: \(p_{n+1}=p_n - f(p_n)(p_n-p_{n-1})/(f(p_n)-f(p_{n-1}))\). Requires no derivative formula. Converges at superlinear order ≈1.618. Needs two starting values; does not maintain a bracket.
• Section 3.11–3.12 Stopping criteria include absolute change, relative change, function value, and interval width. Combining two criteria is safest. Bisection is most reliable; Newton is fastest; the secant method balances speed and derivative cost. Hybrid strategies combine bisection's safety with Newton's speed.

Key Terms Review

1. What condition must be satisfied before bisection can begin? What theorem guarantees a root under this condition?
2. Explain in your own words why bisection always converges but Newton's method may not.
3. What does \(|g'(x)|<1\) mean geometrically, and why does it ensure convergence of fixed-point iteration?
4. The Newton formula involves \(f'(p_n)\) in the denominator. What goes wrong when \(f'(p_n)=0\)?
5. Describe the tangent-line interpretation of Newton's method. Why does the tangent crossing approximate the root better when the starting point is close to the root?
6. How does the secant method approximate the derivative? What is the geometric interpretation?
7. A student applies Newton's method and obtains \(p_5=1.99999\) with \(f(p_5)=10^{-6}\). The student declares success. What else should be checked?
8. Why is it recommended to combine bisection and Newton's method in practice?
9. What does quadratic convergence mean? Give a numerical illustration comparing it to linear convergence.
10. A root has multiplicity 2. What happens to Newton's method convergence at such a root?

Bisection

1. Apply the bisection method to \(f(x)=\cos x - x\) on \([0,1]\) for four steps. Compute the error bound after each step.
2. For \(f(x)=e^x-2\) on \([0,1]\), determine how many bisection steps are required to guarantee error below \(10^{-5}\).
3. Apply bisection to \(f(x)=x^4-3\) on \([1,2]\) for five steps. Record each midpoint and error bound.

Fixed-Point Iteration

4. Verify that \(g(x)=\cos x\) has a fixed point near \(x=0.739\). Apply fixed-point iteration from \(p_0=0.7\) for five steps. Compute \(g'(0.739)\) and verify the convergence condition.
5. For \(f(x)=x^2-3\), write two different fixed-point reformulations. Compute \(g'(x)\) for each near \(x=\sqrt{3}\approx 1.732\) and determine which will converge.
6. Apply fixed-point iteration to \(f(x)=x^3-x-1\) using \(g(x)=(x+1)^{1/3}\) from \(p_0=1.3\) for five steps.

Newton's Method

7. Apply Newton's method to \(f(x)=x^3-x-1\) with \(p_0=1.5\), tolerance \(10^{-6}\). Record all iterates.
8. Apply Newton's method to \(f(x)=\sin x - x/2\) with \(p_0=2\) for four steps.
9. Apply Newton's method to \(f(x)=x^2-2\) starting from \(p_0=1\). Recognize this as the classical algorithm for computing \(\sqrt{2}\).

Secant Method

10. Apply the secant method to \(f(x)=x^3-x-1\) with \(p_0=1.0\), \(p_1=1.5\), tolerance \(10^{-4}\). Record all iterates.
11. Apply the secant method to \(f(x)=e^x-3x\) with \(p_0=0\), \(p_1=1\) for four steps. Compare convergence with bisection on the same function.

1. Write the bisection algorithm in pseudocode from first principles. Identify each step's purpose in plain language.
2. Write the Newton iteration explicitly for \(f(x)=x^5-x-1\). Compute \(f'(x)\) and write the full iteration formula.
3. Explain why the secant method requires two starting values while Newton's method requires only one.
4. Design a stopping criterion that combines absolute change and function value. Explain the rationale for combining both and give an example where each alone would be misleading.

1. A root-finding algorithm produces iterates: \(1.5,\ 1.8,\ 2.0,\ 2.09,\ 2.094,\ 2.0946\). Without knowing the method, estimate the order of convergence from the error reductions.
2. An engineer computes \(f(p_{10})=10^{-8}\) and concludes the root is accurate to eight decimal places. Is this conclusion valid? What additional information is needed?
3. Two methods are applied to find a root. Method A takes 50 steps but always converges. Method B takes 5 steps but fails 10% of the time. Discuss when each is preferable and what a hybrid strategy might look like.
4. A function satisfies \(f(1.99)=-0.001\) and \(f(2.01)=0.001\). Discuss whether a root must exist between them and estimate its location. What assumption is required?

1. Projectile range. A projectile is launched at angle \(\theta\) with initial speed \(v_0=50\) m/s. The range is \(R(\theta)=(v_0^2/g)\sin 2\theta\). Find the angle \(\theta\) that achieves \(R=220\) m, given \(g=9.8\) m/s². Reformulate as \(f(\theta)=0\) and solve using Newton's method.
2. Equilibrium. The equation \(e^{-x}=x\) arises in certain equilibrium problems. Show that it has a root in \((0,1)\) and find it using bisection to four decimal places.
3. Supply and demand. A supply-demand model gives \(S(p)=p^2+2p\) and \(D(p)=50-3p\). Equilibrium satisfies \(S(p)=D(p)\). Reformulate as a root problem and solve using Newton's method.
4. Classic example. The function \(f(x)=x-\cos x\) has exactly one root. Find it using both bisection and Newton's method and compare the number of steps required for tolerance \(10^{-6}\).
5. Finance. Interest rate \(r\) satisfying a present-value equation obeys \(1000(1+r)^{10}-2000=0\). Solve for \(r\) using Newton's method and interpret the result as an annual return rate.

1. For bisection applied to \(f(x)=x^3-2x-5\) on \([2,3]\), compute the guaranteed error bound after 5, 10, and 20 steps. How many steps are needed to guarantee accuracy of \(10^{-8}\)?
2. The fixed-point iteration \(g(x)=(x+3)/4\) is applied near \(x=1\). Compute \(g'(1)\) and estimate the ratio of successive errors. How many steps to reach tolerance \(10^{-6}\) from \(p_0=1.5\)?
3. Newton's method is applied to \(f(x)=x^2-a\) to compute \(\sqrt{a}\). Derive the Newton formula explicitly and demonstrate quadratic convergence for \(a=2\), \(p_0=1\) by computing three iterates and the error at each step.
4. Explain why Newton's method converges only linearly at a double root \(f(x)=(x-r)^2\). Compute the derivative ratio that determines the linear convergence constant.
5. Compare the number of function evaluations required by bisection and Newton's method to achieve error below \(10^{-8}\), starting from an interval of length 1 for bisection or a starting point within distance \(0.5\) of the root for Newton.

1. Newton fractals. Newton's method can be applied in the complex plane to find complex roots of polynomials. Describe what a Newton fractal is and why it arises near the boundaries between basins of attraction. (Conceptual description; no computation required.)
2. Modified Newton's method. For a root of multiplicity \(m\), the modified iteration is \(p_{n+1}=p_n - m\cdot f(p_n)/f'(p_n)\). Verify that this restores quadratic convergence for \(f(x)=(x-1)^2\) with \(m=2\).
3. Brent's method. Brent's method combines bisection, secant, and inverse quadratic interpolation. Research its basic idea and describe how it avoids the failure modes of each individual method while maintaining bisection's reliability.
4. Divergence analysis. Apply Newton's method to \(f(x)=x^3-2x+2\) starting from \(p_0=0\). What happens? Explain the behavior by examining the graph of \(f\) near \(p_0=0\).