Difficulty: Intermediate | Prerequisites: Calculus I and II (derivatives, integration), First-Order ODEs
Numerical methods provide approximate solutions when exact analytical answers are impractical or impossible. This half of MAT 2388 covers root-finding algorithms, polynomial interpolation, numerical integration, and ODE approximation. The emphasis is procedural: you need to set up the table, run the iterations, and compute the error.
Numerical methods give you approximate answers when analytical solutions are too difficult or do not exist. Root-finding methods (fixed point, Newton's, secant) locate where a function crosses zero. Interpolation methods (Lagrange, Newton's divided differences, Gregory-Newton) build a polynomial that passes through known data points. Numerical integration (midpoint, trapezoidal, Simpson's) estimates definite integrals. Euler's method approximates the solution to a differential equation by stepping forward in small increments.
Error (ε)
The difference between the approximate value and the actual value: ε = approx – actual. Relative error is ε divided by the actual value. In simple terms, it measures how far off your approximation is.
Stopping criteria
The threshold |x_{n+1} – x_n| < SC that tells you when to stop iterating. Once consecutive iterations are close enough, further refinement is not worth the effort.
Order of convergence
How quickly a method approaches the true answer. Higher order means fewer iterations for the same accuracy.
Interpolation
Building a polynomial that passes exactly through a given set of data points. Used to estimate function values between known points.
Numerical integration (quadrature)
Approximating the value of a definite integral using sums of function values, rather than finding an antiderivative.
Step size (h)
The spacing between consecutive x-values in a numerical method. Smaller h generally means better accuracy but more computation.
Used to find a root of f(x) = 0 within a known interval.
Write the equation, interval [a,b], and starting point x₀.
Verify a root exists: f(a) and f(b) should have opposite signs.
Rearrange f(x) = 0 into x = g(x) (isolate one x). Derive g(x) and confirm |g'(x)| < 1 on the interval. This guarantees convergence.
Iterate: x_{n+1} = g(x_n). Build a table until the stopping criteria is met.
Uses the tangent line at x_n to approximate the next root estimate.
Formula: x_{n+1} = x_n – f(x_n) / f'(x_n)
Choose an initial estimate x₀, compute x₁, and continue until |x_{n+1} – x_n| < SC.
Converges quadratically (fast) when it works, but can fail if f'(x_n) is near zero or x₀ is poorly chosen.
Modified Newton's Method: x_{n+1} = x_n – 2 f(x_n) / f'(x_n). Used when the root has multiplicity greater than 1 (the function touches but does not cross zero).
Same idea as Newton's but uses a secant line instead of a tangent, so no derivative is needed.
Formula: x_{n+1} = x_n – [(x_n – x_{n−1}) / (f(x_n) – f(x_{n−1}))] · f(x_n)
Requires two starting points x₀ and x₁.
Slower convergence than Newton's, but useful when the derivative is expensive or difficult to compute.
Given n+1 data points, build a polynomial of degree n that passes through all of them.
For each point k, compute the basis polynomial L_k:
L_k = product of (x – x_j) / (x_k – x_j) for all j ≠ k.
The interpolating polynomial is P_n = f(x₀)L₀ + f(x₁)L₁ + ... + f(x_n)L_n.
An alternative construction that is easier to extend when new points are added.
State all data points.
Compute first divided differences: f[x_n, x_{n+1}] = (y_{n+1} – y_n) / (x_{n+1} – x_n).
Compute higher divided differences recursively: f[x₀, x₁, x₂] = (f[x₁,x₂] – f[x₀,x₁]) / (x₂ – x₀).
Assemble: P = y₀ + (x–x₀)f[x₀,x₁] + (x–x₀)(x–x₁)f[x₀,x₁,x₂] + ...
Specialised versions for equally spaced data.
Build a difference table: Δf_n = f_{n+1} – f_n, Δ²f_n = Δf_{n+1} – Δf_n, and so on.
Let r = (x – x₀) / Δx.
Forward formula starts from the first data point.
Backward formula: P_n(r) = f₀ + Σ [r(r+1)...(r+k−1) / k!] Δ^k f_k, useful for extrapolating near the end of the data set.
Approximate the integral using rectangles evaluated at the midpoint of each subinterval.
Error bound: |ε_m| ≤ h² f''(b) · (b–a) / 24 < desired error.
Isolate h, compute n, then evaluate: h[f(x₁) + f(x₂) + ... + f(x_n)].
Approximate using trapezoids.
Error bound: |ε_m| ≤ h² f''(b) · (b–a) / 12 < desired error.
Isolate h, n = (b–a)/h (or equivalently 2/h depending on formulation).
Formula: (h/2) [f(x₁) + 2f(x₂) + 2f(x₃) + ... + 2f(x_{n−1}) + f(x_n)].
The first and last evaluations have coefficient 1; all interior points have coefficient 2.
Higher accuracy using parabolic segments.
Error bound: |ε_s| ≤ h⁴ f^(IV)(b) · (b–a) / 180 < desired error.
Isolate h, compute n (must be even).
Formula: (h/3) [f(x₁) + 4f(x₂) + 2f(x₃) + 4f(x₄) + ... + f(x_n)].
Coefficients alternate 4, 2, 4, 2, ... between the endpoints.
The simplest numerical method for approximating the solution to an ODE of the form y' = f(x,y), y(x₀) = y₀, over an interval x₀ < x < x_n with step size h.
Compute n_max = (x_n – x₀) / h.
Build a table with columns: n, x_n = x₀ + hn, y_{n+1} = y_n + h · f(x_n, y_n).
Optionally solve the ODE analytically to get the exact solution y(x_n) and compute the absolute error at each step.
Euler's method is first-order: the error per step is proportional to h², and the global error over the interval is proportional to h. Halving h roughly halves the global error but doubles the number of steps.
The method is straightforward to execute in an exam setting. The main challenge is careful arithmetic across many rows of the table.
\text{Newton's method: } x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\text{Secant method: } x_{n+1} = x_n - \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})} \cdot f(x_n)\text{Trapezoidal rule: } \int_a^b f(x)\,dx \approx \frac{h}{2}[f(x_0) + 2f(x_1) + \cdots + 2f(x_{n-1}) + f(x_n)]\text{Simpson's rule: } \int_a^b f(x)\,dx \approx \frac{h}{3}[f(x_0) + 4f(x_1) + 2f(x_2) + 4f(x_3) + \cdots + f(x_n)]\text{Euler's method: } y_{n+1} = y_n + h\,f(x_n, y_n)Root finding is how engineers locate operating points in circuits, determine break-even in financial models, and find equilibria in chemical systems.
Interpolation is used whenever you have measured data at discrete points and need to estimate values in between, for instance estimating temperature between weather-station readings.
Numerical integration powers everything from computing areas under experimental curves to calculating probabilities from statistical distributions when no closed-form antiderivative exists.
Euler's method (and its more accurate cousins like Runge-Kutta) is how simulations step forward in time: weather models, population dynamics, and orbital mechanics all rely on stepping methods.
Students often forget to check |g'(x)| < 1 before starting fixed point iteration. Without this check, the method may diverge and waste all your time.
In Newton's method, students sometimes use the wrong sign in the formula. It is x_n minus f/f', not plus.
With Simpson's rule, n must be even. Students who compute an odd n and proceed anyway will get a wrong answer.
In Euler's method, students sometimes compute f(x_{n+1}, y_{n+1}) instead of f(x_n, y_n). Euler's method evaluates the slope at the current point, not the next one.
⚠️ Euler's method table construction is a near-certain exam question. The arithmetic is simple but tedious; practice until you can do it quickly and without sign errors.
⚠️ Newton's method and the secant method are commonly tested side by side. Know the formulas and when each is preferred.
⚠️ Simpson's rule error bounds appear regularly. You must be able to determine h and n from a given error tolerance.
⚠️ Lagrange interpolation or Newton's divided differences often appear as a "build the polynomial" question. The construction is mechanical but demands care with the fractions.
Fill in the blank: Newton's method formula is x_{n+1} = x_n – ___. (f(x_n)/f'(x_n))
True or false: fixed point iteration always converges. (False, convergence requires |g'(x)| < 1 on the interval.)
Fill in the blank: Simpson's rule requires n to be ___. (even)
True or false: Euler's method has second-order global accuracy. (False, it is first-order.)
Fill in the blank: the secant method does not require computing a ___. (derivative)
Q: Use Newton's method with x₀ = 1 to find one iteration for f(x) = x² – 3.
A: f(1) = 1 – 3 = –2, f'(x) = 2x so f'(1) = 2. x₁ = 1 – (–2)/2 = 1 + 1 = 2.
Q: Given three points (0,1), (1,3), (2,7), write the Lagrange interpolating polynomial.
A: L₀ = (x–1)(x–2)/((0–1)(0–2)) = (x–1)(x–2)/2. L₁ = (x)(x–2)/((1)(1–2)) = –x(x–2). L₂ = x(x–1)/((2)(1)) = x(x–1)/2. P = 1·L₀ + 3·L₁ + 7·L₂.
Q: Apply Euler's method with h = 0.1 for y' = x + y, y(0) = 1. Find y₁.
A: y₁ = y₀ + h · f(x₀, y₀) = 1 + 0.1 · (0 + 1) = 1.1.
Q: Which numerical integration rule has an error bound involving h⁴ and the fourth derivative?
A: Simpson's rule.
Numerical methods approximate the solutions you learn to find analytically in the ODE portions of the course (Docs 1–3). When an equation cannot be solved in closed form, Euler's method or its higher-order relatives (Runge-Kutta, which goes beyond MAT 2388) are the standard fallback. Interpolation connects to curve fitting in statistics and data science. Numerical integration is used throughout physics and engineering wherever a closed-form antiderivative does not exist.
Related Terms / Search Tags
numerical methods, root finding, fixed point iteration, Newton's method, modified Newton's, secant method, Lagrange interpolation, Newton's divided difference, Gregory-Newton, forward difference, backward difference, midpoint rule, trapezoidal rule, Simpson's rule, error bound, step size, Euler's method, numerical integration, quadrature, convergence, stopping criteria, MAT 2388