Numerical Methods

Iteration Formula

Geometrically: draw the tangent line to f at the current approximation x_n, then take the x-intercept of that tangent line as the next approximation.

Lagrange Interpolation

Writes the interpolating polynomial as a sum of Lagrange basis polynomials L_i(x):

L_i(x) equals 1 at x_i and 0 at every other node. Easy to write but expensive to update when new data points are added.

Newton's Divided Differences

Builds the polynomial incrementally using divided difference coefficients. Define:

Adding a new point only requires computing one new diagonal of the divided difference table — preferred for incremental computation.

Cubic Splines

On each subinterval [x_i, x_(i+1)] a cubic spline S(x) uses a separate cubic polynomial S_i(x). The conditions enforced at interior knots are:

Splines avoid Runge's phenomenon — the wild oscillations seen in high-degree polynomial interpolation at equally spaced points.

Trapezoidal Rule

Simpson's 1/3 Rule

Requires n to be even. Uses parabolas over pairs of subintervals.

Gaussian Quadrature

Chooses both nodes and weights to maximize accuracy. An n-point Gauss-Legendre rule is exact for polynomials up to degree 2n - 1, compared to n for Newton-Cotes.

For integrals on [a, b], transform via x = ((b-a)t + (b+a)) / 2 and multiply by (b-a)/2.

Euler's Method

The simplest one-step method. Uses the slope at the current point to step forward.

Euler's method is rarely used in practice due to its low accuracy, but it is the conceptual foundation for understanding all higher-order methods.

Runge-Kutta 4th Order (RK4)

Computes four slope estimates and takes a weighted average for the step.

Halving h reduces global error by a factor of 16. RK4 is the standard method for non-stiff ODEs and is the first solver to try for any new problem.

Root-Finding Methods

Numerical Integration Methods

Example 1 — Bisection: Find root of f(x) = x^3 - x - 2 on [1, 2]

Example 2 — Newton-Raphson: Solve f(x) = x^2 - 2 = 0 starting at x_0 = 1

Example 3 — Simpson's 1/3 Rule: Approximate integral of e^x from 0 to 1 with n = 4

Example 4 — RK4: Solve y' = y, y(0) = 1 on [0, 0.5] with h = 0.5

Example 5 — Lagrange Interpolation: Find P(x) through (0,1), (1,3), (3,2)

What is the bisection method and when should you use it?

The bisection method finds a root of f(x) = 0 by repeatedly halving an interval [a, b] where f(a) and f(b) have opposite signs (guaranteed by the Intermediate Value Theorem). At each step you evaluate the midpoint c = (a + b)/2. If f(c) = 0 you found the root; otherwise replace a or b with c depending on which subinterval contains the sign change. It is guaranteed to converge but only linearly — the error halves each iteration. Use it when you need reliability over speed, or as a fallback when other methods fail.

What is the convergence order of Newton-Raphson and why does it matter?

Newton-Raphson converges quadratically near a simple root, meaning the number of correct decimal digits roughly doubles each iteration. The iteration formula is x_{n+1} = x_n - f(x_n)/f'(x_n). Quadratic convergence is extremely fast in practice — starting with 2 correct digits, one step gives ~4, then ~8, then ~16. However, Newton-Raphson requires f'(x) to be computable, requires a good initial guess near the root, can diverge for poorly chosen starting points, and degrades to linear convergence at repeated roots.

What is the difference between Lagrange interpolation and Newton's divided differences?

Both methods produce the same unique polynomial of degree at most n passing through n+1 data points. Lagrange interpolation writes the polynomial as a sum of basis polynomials L_i(x), each equal to 1 at x_i and 0 at all other nodes. It is easy to write but expensive to update — adding a new data point requires recomputing all basis polynomials. Newton's divided differences builds the polynomial incrementally using a triangular table of divided differences. Adding a new point only requires one new column of the table. For computational work Newton's form is preferred; Lagrange form is better for theoretical analysis.

How accurate is Simpson's 1/3 rule compared to the Trapezoidal rule?

Simpson's 1/3 rule is much more accurate. The Trapezoidal rule approximates the integrand by straight-line segments (degree-1 polynomials), giving a global error proportional to h^2 where h is the step size. Simpson's 1/3 rule fits parabolas through pairs of subintervals (degree-2 polynomials) and achieves error proportional to h^4. Halving the step size reduces Trapezoidal error by a factor of 4 but reduces Simpson's error by a factor of 16. Simpson's rule is also exact for any polynomial up to degree 3 due to a fortuitous cancellation.

What is Runge-Kutta 4th order (RK4) and why is it the standard ODE solver?

RK4 is a single-step method for solving y' = f(t, y) that computes four slope estimates per step: k1 at the start, k2 and k3 at the midpoint (using k1 and k2 respectively), and k4 at the end. The step is y_{n+1} = y_n + (h/6)(k1 + 2k2 + 2k3 + k4). RK4 has local truncation error proportional to h^5 and global error proportional to h^4, meaning halving h reduces error by a factor of 16. It requires no special starting procedure (unlike multi-step methods), handles most smooth problems well, and is simple to implement — making it the default choice in science and engineering.

What is the difference between truncation error and round-off error?

Truncation error arises from approximating an infinite mathematical process with a finite one — for example, truncating an infinite Taylor series after a few terms, or replacing a derivative with a finite difference. It decreases as the step size h decreases. Round-off error arises from the finite precision of floating-point arithmetic — every real number is stored with only ~15-16 significant digits in double precision. Round-off error increases as h decreases because subtracting nearly equal numbers amplifies relative error. The optimal step size balances these two competing effects.

What is the condition number and why does it matter for numerical computations?

The condition number of a problem measures how sensitive the output is to small changes in the input. For a matrix A, the condition number kappa(A) = ||A|| * ||A^{-1}||. A large condition number (ill-conditioned) means small perturbations in data or round-off errors can cause large errors in the solution. For example, solving Ax = b with cond(A) = 10^6 means you can lose up to 6 decimal digits of accuracy compared to a well-conditioned system. Condition number is a property of the problem, not the algorithm — an ill-conditioned problem is inherently hard to solve accurately regardless of the method used.

What is fixed-point iteration and when does it converge?

Fixed-point iteration solves f(x) = 0 by rewriting it as x = g(x) and iterating x_{n+1} = g(x_n). A fixed point is a value p where g(p) = p. The iteration converges to a fixed point p if |g'(p)| < 1 near p — the smaller |g'(p)|, the faster the convergence. If |g'(p)| > 1 the iteration diverges. If |g'(p)| = 0 convergence is superlinear. The choice of how to rearrange f(x) = 0 into x = g(x) is crucial — different rearrangements of the same equation can converge or diverge depending on the value of g' at the fixed point.

How do cubic splines differ from polynomial interpolation for large data sets?

High-degree polynomial interpolation through many points suffers from Runge's phenomenon — wild oscillations between data points, especially near the endpoints. Cubic splines avoid this by fitting a separate cubic polynomial on each subinterval between data points, then enforcing that the function, first derivative, and second derivative all match at each interior data point (knot). This produces a smooth curve that passes exactly through all data points without oscillation. Natural splines additionally set the second derivative to zero at the endpoints. Splines are the standard method in CAD, computer graphics, and data smoothing.