From the free course CS323: Numerical Analysis and Computing on Lykke

Midterm 2: Review and Assessment

Key concepts: Root-Finding Methods (Newton's, Secant, Bisection) · Convergence Analysis · Polynomial Interpolation (Lagrange, Vandermonde, Newton) · Interpolation Error Analysis · Piecewise vs. Global Interpolation

This module provides a comprehensive review for the second midterm, focusing on root-finding and polynomial interpolation. It includes a practice exam and solutions that test the theoretical understanding and practical application of methods like Newton's, Secant, and various interpolation techniques (Lagrange, Vandermonde, piecewise). Key concepts like convergence rates and error analysis are heavily featured.

Midterm 2: Review and Assessment

This module provides a comprehensive technical review for the second midterm, focusing on the core numerical methods of root-finding and polynomial interpolation. The exam will probe not only your ability to execute these algorithms but also your deeper understanding of their underlying mathematical principles, convergence properties, and the trade-offs that guide their application in real-world scenarios. Mastering these topics requires moving beyond rote memorization to a fluent understanding of why each method behaves as it does.

This guide is structured to mirror the conceptual flow of the course, from finding solutions to single nonlinear equations to approximating complex functions with simpler ones. We will dissect each major algorithm, analyze its performance characteristics, and work through practical examples to solidify your knowledge.

Root-Finding Methods: Seeking f(x) = 0

At its core, root-finding is the process of finding a value x (a root or zero) for which a given function f(x) evaluates to zero. This seemingly simple problem is fundamental across computational science and engineering, appearing in optimization problems (where we find the root of the derivative), equilibrium calculations, and solving systems of nonlinear equations. The midterm will focus on three canonical iterative methods.

The Bisection Method: The Reliable Bracket

  • What it is: The Bisection Method is a bracketing method that iteratively narrows down an interval [a, b] that is known to contain a root. Its operation is guaranteed by the Intermediate Value Theorem, which states that if a continuous function f(x) has values of opposite sign at the endpoints of an interval (i.e., f(a) * f(b) < 0), then it must have at least one root within that interval.

  • Why it matters: Its primary virtue is its unconditional convergence. As long as the initial bracket is valid, the Bisection Method is guaranteed to find a root. This makes it an incredibly robust and reliable algorithm, often used as a fallback or to generate a safe starting point for faster, but less reliable, methods.

  • How it works:

    1. Start with an interval [a, b] such that f(a) and f(b) have opposite signs.
    2. Calculate the midpoint c = (a + b) / 2.
    3. Evaluate f(c).
    4. If f(c) is sufficiently close to zero, c is the approximate root.
    5. Otherwise, update the bracket:
      • If f(a) * f(c) < 0, the root is in [a, c]. Set b = c.
      • If f(b) * f(c) < 0, the root is in [c, b]. Set a = c.
    6. Repeat from step 2 until the interval |b - a| is smaller than a specified tolerance.
  • Convergence Analysis: The Bisection Method exhibits linear convergence. At each step, the size of the interval containing the root is halved. If e_n is the error at iteration n (represented by the interval width), then e_{n+1} = 0.5 * e_n. This is a constant factor reduction, which defines linear convergence. While reliable, this is considered slow compared to other methods.

Key Insight: The number of iterations n required to achieve a tolerance ε from an initial interval [a_0, b_0] can be calculated directly: n ≥ log₂((b_0 - a_0) / ε) This predictability is a unique and powerful feature of the Bisection Method.

  • Common Pitfalls:
    • Finding a valid initial bracket: For some functions, it can be difficult to find an initial [a, b] where f(a) and f(b) have opposite signs.
    • Multiple roots: If multiple roots exist in the initial bracket, Bisection will find one of them, but it's not predictable which one.
    • Performance: Its slow, linear convergence makes it impractical for problems requiring high precision quickly.

Newton's Method: The Tangent Line Approximation

  • What it is: Newton's Method (or Newton-Raphson) is an open method that uses tangent lines to iteratively find better approximations to a root. Starting with an initial guess x_0, it approximates the function f(x) with its tangent line at x_0 and finds where this line intersects the x-axis. This intersection point becomes the next guess, x_1.

The iteration formula is derived from the first-order Taylor expansion of f(x) around x_n: f(x) ≈ f(x_n) + f'(x_n)(x - x_n) Setting f(x) = 0 to find the root and solving for x (which becomes x_{n+1}) gives the celebrated formula: x_{n+1} = x_n - f(x_n) / f'(x_n)

  • Why it matters: Speed. When Newton's Method converges, it typically does so extremely fast. This rapid convergence makes it the method of choice for a vast number of applications where efficiency is paramount.

  • How it works:

    1. Start with an initial guess x_0 that is "reasonably close" to the root.
    2. Calculate the next approximation using the formula x_{n+1} = x_n - f(x_n) / f'(x_n).
    3. Repeat step 2 until the change |x_{n+1} - x_n| or the residual |f(x_{n+1})| is below a tolerance.

Concrete Example: Find the root of f(x) = x² - 2 (i.e., find √2) starting with x_0 = 1. * f'(x) = 2x * Iteration 1: x_1 = 1 - (1² - 2) / (2 * 1) = 1 - (-1) / 2 = 1.5 * Iteration 2: x_2 = 1.5 - (1.5² - 2) / (2 * 1.5) = 1.5 - (0.25) / 3 ≈ 1.41667 * Iteration 3: x_3 = 1.41667 - (1.41667² - 2) / (2 * 1.41667) ≈ 1.4142157 The true value of √2 is 1.41421356.... Notice how the number of correct digits roughly doubles with each iteration.

  • Convergence Analysis: Newton's Method has quadratic convergence under ideal conditions (the root is simple, f'(r) ≠ 0, and the initial guess is sufficiently close). This means the error e_{n+1} is proportional to the square of the previous error: e_{n+1} ≈ C * e_n². This is the source of its incredible speed.
import math

def newtons_method(f, df, x0, tol=1e-9, max_iter=100):
    """
    Finds a root of a function using Newton's method.

    Args:
        f (callable): The function for which to find a root, f(x).
        df (callable): The derivative of the function, f'(x).
        x0 (float): Initial guess for the root.
        tol (float): The convergence tolerance.
        max_iter (int): The maximum number of iterations.

    Returns:
        float: The approximate root, or None if the method fails to converge.
    """
    x = x0
    for i in range(max_iter):
        fx = f(x)
        if abs(fx) < tol:
            print(f"Converged after {i} iterations.")
            return x
        
        dfx = df(x)
        if dfx == 0:
            print("Error: Derivative is zero. Newton's method fails.")
            return None
            
        x_new = x - fx / dfx
        
        if abs(x_new - x) < tol:
            print(f"Converged after {i+1} iterations.")
            return x_new
            
        x = x_new
        
    print("Warning: Maximum iterations reached. Did not converge.")
    return None

# Example usage: find the root of cos(x) - x^3
f = lambda x: math.cos(x) - x**3
df = lambda x: -math.sin(x) - 3*x**2
root = newtons_method(f, df, x0=0.5)
if root is not None:
    print(f"The root is approximately: {root:.8f}")
    print(f"f(root) = {f(root):.2e}")
# Derivation of Quadratic Convergence for Newton's Method

Let r be the true root, so f(r) = 0. Let e_n = x_n - r be the error at iteration n.
We use a Taylor expansion of f(r) around x_n:
  f(r) = f(x_n) + f'(x_n)(r - x_n) + (f''(ξ_n)/2)(r - x_n)²
  0    = f(x_n) - f'(x_n)e_n + (f''(ξ_n)/2)e_n²

Divide by f'(x_n) (assuming f'(x_n) ≠ 0):
  0 = f(x_n)/f'(x_n) - e_n + (f''(ξ_n)/(2f'(x_n)))e_n²

Rearrange to isolate the term f(x_n)/f'(x_n):
  f(x_n)/f'(x_n) = e_n - (f''(ξ_n)/(2f'(x_n)))e_n²

Now, look at the error in the next step, e_{n+1}:
  e_{n+1} = x_{n+1} - r
          = (x_n - f(x_n)/f'(x_n)) - r
          = (x_n - r) - f(x_n)/f'(x_n)
          = e_n - f(x_n)/f'(x_n)

Substitute the expression for f(x_n)/f'(x_n) from above:
  e_{n+1} = e_n - [e_n - (f''(ξ_n)/(2f'(x_n)))e_n²]
  e_{n+1} = (f''(ξ_n)/(2f'(x_n)))e_n²

As x_n approaches r, ξ_n also approaches r. So for large n:
  e_{n+1} ≈ [f''(r)/(2f'(r))] * e_n²

This shows that e_{n+1} is proportional to e_n², which is the definition of quadratic convergence.
The constant C is f''(r) / (2f'(r)).
  • Common Pitfalls:
    • Divergence: If the initial guess x_0 is not in the "basin of attraction" for the root, the iterations can diverge to infinity.
    • Zero Derivative: If f'(x_n) is zero or very close to it, the next step will be huge or cause a division-by-zero error. This happens at local extrema.
    • Oscillation: The method can get stuck in a cycle between two or more points without converging.
    • Requirement of f'(x): The analytical derivative must be known and easy to compute, which is not always the case.

The Secant Method: The Finite-Difference Newton

  • What it is: The Secant Method is a clever modification of Newton's Method that avoids the need for an explicit derivative. It approximates the derivative f'(x_n) using a finite difference based on the two most recent iterates, x_n and x_{n-1}.

The derivative approximation is: f'(x_n) ≈ (f(x_n) - f(x_{n-1})) / (x_n - x_{n-1}) Substituting this into Newton's formula gives the Secant iteration: x_{n+1} = x_n - f(x_n) * (x_n - x_{n-1}) / (f(x_n) - f(x_{n-1}))

  • Why it matters: It provides a practical alternative when the derivative is unavailable or computationally expensive. It almost achieves the speed of Newton's method without its main implementation burden.

  • How it works:

    1. Start with two initial guesses, x_0 and x_1.
    2. Calculate the next approximation x_{n+1} using the iteration formula.
    3. Repeat, always using the two most recent points, until convergence is achieved.
  • Convergence Analysis: The Secant Method has superlinear convergence. Its rate is approximately φ = (1 + √5) / 2 ≈ 1.618 (the golden ratio). This means e_{n+1} ≈ C * e_n^1.618. This is faster than linear but slower than quadratic. In practice, since it only requires one function evaluation per step (compared to two for Newton: f and f'), it can sometimes be faster in terms of wall-clock time.

  • Common Pitfalls:

    • Requires two initial points.
    • It inherits many of the same potential divergence issues as Newton's method, as it is essentially a close approximation.
    • If f(x_n) becomes very close to f(x_{n-1}), the denominator can become small, leading to numerical instability (a form of subtractive cancellation).

Method Comparison

Feature Bisection Method Newton's Method Secant Method
Convergence Rate Linear (p=1) Quadratic (p=2) Superlinear (p≈1.618)
Reliability Guaranteed if bracket is valid Can diverge Can diverge
Requirements [a, b] with f(a)f(b)<0 f(x), f'(x), and a good x₀ f(x) and two initial points x₀, x₁
Cost per Iteration 1 f evaluation 1 f eval, 1 f' eval 1 f evaluation
Key Advantage Robustness & Predictability Speed No derivative needed
Key Disadvantage Slow Needs derivative, can fail Needs two points, can fail

Polynomial Interpolation: Connecting the Dots

Polynomial Interpolation is the task of finding a polynomial that passes exactly through a given set of data points. Given n+1 points (x_0, y_0), (x_1, y_1), ..., (x_n, y_n) with distinct x_i, we seek a unique polynomial P_n(x) of degree at most n such that P_n(x_i) = y_i for all i. The choice of basis for representing this polynomial leads to different algorithms with distinct computational trade-offs.

The Vandermonde Approach (Monomial Basis)

  • What it is: This is the most direct approach. We assume the polynomial is in the standard monomial basis: P_n(x) = c_0 + c_1x + c_2x² + ... + c_nx^n. Plugging in each data point (x_i, y_i) creates a system of n+1 linear equations for the n+1 unknown coefficients c_j.

This system can be written in matrix form as Vc = y: [ 1 x₀ x₀² ... x₀ⁿ ] [ c₀ ] [ y₀ ] [ 1 x₁ x₁² ... x₁ⁿ ] [ c₁ ] = [ y₁ ] [ ... ... ... ... ... ] [ .. ] [ .. ] [ 1 xₙ xₙ² ... xₙⁿ ] [ cₙ ] [ yₙ ] The matrix V is the famous Vandermonde matrix.

  • Why it matters: It's a conceptually straightforward way to prove that a unique interpolating polynomial exists (since the Vandermonde matrix is invertible for distinct x_i). However, it is rarely used in practice due to its severe numerical limitations.

  • Pitfalls: The Vandermonde matrix is notoriously ill-conditioned, especially for high degrees and/or clustered points. This means that small errors in the input y_i can lead to huge errors in the computed coefficients c_j. Solving the system Vc=y is also computationally expensive, requiring O(n³) operations.

import numpy as np

# Data points to interpolate
x_vals = np.array([0, 1, 3, 4])
y_vals = np.array([2, 1, 5, 3])

# Build the Vandermonde matrix
V = np.vander(x_vals, increasing=True)
print("Vandermonde Matrix V:\n", V)

# Solve the linear system Vc = y for the coefficients c
try:
    coeffs = np.linalg.solve(V, y_vals)
    print("\nCoefficients (c0, c1, c2, c3):", coeffs)

    # Create a polynomial function from the coefficients
    p = np.poly1d(np.flip(coeffs)) # np.poly1d expects coeffs in decreasing power order
    print("\nInterpolating Polynomial P(x):\n", p)

except np.linalg.LinAlgError:
    print("\nCould not solve the system. The Vandermonde matrix may be singular or ill-conditioned.")

# A real-world library call for interpolation often uses a more stable basis internally.
# For example, using SciPy's BarycentricInterpolator which is related to Lagrange.
from scipy.interpolate import BarycentricInterpolator

poly_bary = BarycentricInterpolator(x_vals, y_vals)
print(f"\nValue at x=2 (using a stable library method): {poly_bary(2.0)}")

The Lagrange Basis

  • What it is: The Lagrange approach constructs the polynomial differently. Instead of solving for coefficients, it builds the final polynomial as a weighted sum of special Lagrange basis polynomials, L_j(x).

The interpolating polynomial is P_n(x) = Σ_{j=0}^{n} y_j * L_j(x), where each L_j(x) is a polynomial of degree n with the property that L_j(x_i) = 1 if i=j and 0 if i≠j. L_j(x) = Π_{i=0, i≠j}^{n} (x - x_i) / (x_j - x_i)

  • Why it matters: It provides an elegant, explicit formula for the interpolating polynomial without needing to solve a linear system. The "coefficients" are simply the y_i values themselves.

  • Pitfalls:

    • Evaluation is expensive: Evaluating P_n(x) at a new point takes O(n²) operations.
    • Not adaptive: If a new data point (x_{n+1}, y_{n+1}) is added, all the basis polynomials L_j(x) must be recomputed from scratch. This makes it inflexible.

The Newton Basis

  • What it is: The Newton form represents the polynomial in a basis that is built up incrementally. This is arguably the most practical and computationally sound approach. P_n(x) = c_0 + c_1(x-x_0) + c_2(x-x_0)(x-x_1) + ... + c_n(x-x_0)...(x-x_{n-1})

  • Why it matters: It strikes an excellent balance between computational efficiency and flexibility.

    • Efficient Coefficient Calculation: The coefficients c_j (called divided differences) can be computed in O(n²) time using a dynamic programming approach.
    • Efficient Evaluation: The nested structure of the Newton form can be evaluated in O(n) time using Horner's method.
    • Adaptive: Adding a new data point only requires computing one new row in the divided differences table; all previous coefficients remain unchanged.
  • How it works: The coefficients c_j are the diagonal entries of a divided differences table.

    • c_0 = f[x_0] = y_0
    • c_1 = f[x_0, x_1] = (y_1 - y_0) / (x_1 - x_0)
    • c_2 = f[x_0, x_1, x_2] = (f[x_1, x_2] - f[x_0, x_1]) / (x_2 - x_0)
    • ...and so on.
function build_divided_diff_table(x_points, y_points):
    n = length(x_points)
    // Initialize a 2D array (table) of size n x n
    table = new array[n][n]

    // The first column is just the y-values
    for i from 0 to n-1:
        table[i][0] = y_points[i]

    // Fill the rest of the table
    for j from 1 to n-1: // Column index
        for i from j to n-1: // Row index
            numerator = table[i][j-1] - table[i-1][j-1]
            denominator = x_points[i] - x_points[i-j]
            table[i][j] = numerator / denominator
            
    // The coefficients are the top diagonal: table[0][0], table[1][1], ...
    coefficients = []
    for i from 0 to n-1:
        coefficients.append(table[i][i])
        
    return coefficients

Basis Comparison

Feature Monomial (Vandermonde) Lagrange Newton
Coefficient Cost O(n³) (solve system) O(1) (they are the yᵢ) O(n²) (build table)
Evaluation Cost O(n) (Horner's method) O(n²) O(n) (nested form)
Adding a New Point O(n³) (re-solve) O(n²) (re-build all Lⱼ) O(n) (add one row to table)
Numerical Stability Very Poor (ill-conditioned) Moderate Good
Primary Use Case Theoretical proofs Mathematical elegance Practical implementation

Error Analysis and Advanced Topics

A common exam theme is understanding when and why interpolation fails. Simply increasing the degree of the polynomial is not a panacea for achieving better accuracy.

The Interpolation Error Formula

If f(x) is a sufficiently smooth function and P_n(x) is the polynomial that interpolates f at n+1 distinct points x_0, ..., x_n, then for any x in the interval containing the nodes, the error E(x) = f(x) - P_n(x) is given by: E(x) = (f^(n+1)(ξ) / (n+1)!) * Π_{i=0}^{n} (x - x_i) for some ξ in the interval.

This formula is crucial. It tells us that the error depends on two things:

  1. The function itself: via the (n+1)-th derivative. If the function is "wiggly" (has large derivatives), the error will be large.
  2. The choice of interpolation points: via the nodal polynomial ω(x) = Π(x - x_i). The error is zero at the nodes and largest between them.

Runge's Phenomenon: The Peril of High-Degree Interpolation

  • What it is: Runge's Phenomenon is the classic example of the failure of high-degree global interpolation. When interpolating the function f(x) = 1 / (1 + 25x²) on the interval [-1, 1] with a high-degree polynomial using equally spaced nodes, the polynomial exhibits wild oscillations near the endpoints, causing the error to grow, not shrink, as more points are added.

  • Why it happens: For the Runge function, the high-order derivatives f^(n+1)(x) grow very rapidly, especially near the endpoints. At the same time, for equally spaced points, the nodal polynomial ω(x) is largest near the endpoints. The product of these two large terms in the error formula leads to catastrophic error.

# Using gnuplot to visualize Runge's Phenomenon

# Set up the plot environment
gnuplot -persist <<-EOF
    set title "Runge's Phenomenon: Interpolating f(x) = 1/(1+25x^2)"
    set xlabel "x"
    set ylabel "y"
    set grid
    set key top center
    set samples 500
    set xrange [-1:1]
    set yrange [-1:2]

    # Define the Runge function
    f(x) = 1.0 / (1.0 + 25.0 * x**2)

    # Plot the original function and data points for N=11
    # Gnuplot can't do polynomial interpolation directly, so we generate data points
    # that would be used by an external script. This script visualizes the concept.
    plot f(x) with lines lw 2 title "Original f(x)", \
         '<(for i in {-5..5}; do x=$(echo "$i/5.0" | bc -l); y=$(echo "1/(1+25*$x*$x)" | bc -l); echo "$x $y"; done)' \
         with points pt 7 ps 1.5 title "11 Equally Spaced Nodes"
EOF

# In a real analysis, one would pipe these points to a Python script
# to compute the 10th-degree interpolant and plot it back.
# The command demonstrates how to generate the nodes for visualization.
# The resulting plot would show a polynomial that matches the points but
# wildly oscillates between them, especially near x=-1 and x=1.

Piecewise vs. Global Interpolation

  • The Solution: To avoid Runge's phenomenon and the instability of high-degree polynomials, the universal modern approach is piecewise interpolation. Instead of using one polynomial of degree n for n+1 points, we break the domain into subintervals and use a separate low-degree polynomial (e.g., linear, cubic) on each piece.

  • Piecewise Linear Interpolation: Simply connect adjacent data points with straight lines. This is simple and robust but not smooth (the derivative is discontinuous at the nodes).

  • Splines: Splines are more sophisticated piecewise polynomials (most commonly, cubic splines) that are constrained to have continuous derivatives at the nodes. This results in a curve that is both accurate locally and smooth globally. They are the foundation of modern computer graphics, CAD software, and data visualization.

Feature Global Polynomial Interpolation Piecewise Interpolation (e.g., Splines)
Polynomial Degree High (n) Low (e.g., 1 or 3)
Smoothness Infinitely differentiable Controllable (e.g., C² for cubic splines)
Runge's Phenomenon Highly susceptible Immune
Local Control No (changing one point affects the entire curve) Yes (changing one point only affects nearby segments)
Computational Cost High (O(n³) or O(n²)) Low (often linear in n)
Typical Use Function approximation over small, well-behaved domains Standard for data fitting, graphics, engineering
Midterm 2: Review and Assessment - CS323: Numerical Analysis and Computing - diagram 1
Midterm 2: Review and Assessment - CS323: Numerical Analysis and Computing - diagram 1

Source Materials

Study CS323: Numerical Analysis and Computing on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of CS323: Numerical Analysis and Computing · Browse more course pages

Midterm 2: Review and Assessment — CS323: Numerical Analysis and Computing | Lykke