Finite Differences & Interpolation
The Building Blocks of Numerical Analysis
\(\Delta f(x) = f(x+h) – f(x)\)
\(\nabla f(x) = f(x) – f(x-h)\)
\(E f(x) = f(x+h)\)
\(E^{-1} f(x) = f(x-h)\)
\(\delta f(x) = f(x+\frac{h}{2}) – f(x-\frac{h}{2})\)
\(\mu f(x) = \frac{1}{2}[f(x+\frac{h}{2}) + f(x-\frac{h}{2})]\)
Key Relationships (Memorize!)
\(E = 1 + \Delta\)
\(\nabla = 1 – E^{-1}\)
\(\delta = E^{1/2} – E^{-1/2}\)
Calculus Conversion:
\(E = e^{hD}\) (Taylor Series)
\(D = \frac{1}{h} \ln(1 + \Delta)\)
For a polynomial of degree \(n\):
- The \(n\)-th difference (\(\Delta^n\)) is a non-zero constant.
- The \((n+1)\)-th difference is zero.
Estimating values inside the data range.
Given \(n+1\) points, there is a unique polynomial of degree \(\le n\).
Methods Comparison
| Method | Pros & Cons |
|---|---|
| Lagrange |
✓ Symmetric (Order doesn’t matter) ✗ Hard to update (New point = Restart) |
| Newton’s Divided Difference |
✓ Easy to update (Add one term) Form: \(b_0 + b_1(x-x_0) + \dots\) |
Where to Interpolate? (Equal Spacing)
Use Newton’s Forward
Use Stirling’s / Bessel’s (Central)
Use Newton’s Backward
Numerical Integration
Area Under the Curve Approximations
The Concept
- Approximation: Connects points with a Straight Line (Trapezoids).
- Polynomial: Linear (Degree 1) \( y=mx+c \).
- Accuracy: Global Error \( O(h^2) \). Exact for Linear functions.
Composite Formula
Coefficient Pattern
Ends get weight 1, Intermediates get weight 2.
The Concept
- Approximation: Connects 3 points with a Parabola.
- Polynomial: Fits Degree 2, but exact for Degree 3 (Cubic)!
Formula
Coefficient Pattern
Alternates 4, 2, 4, 2…
The Concept
- Approximation: Connects 4 points with a Cubic Curve.
- Polynomial: Degree 3 (Cubic).
Formula
Coefficient Pattern
Pattern: 1, 3, 3, 2…
Exam Critical Details
Error Analysis & Strategy Cheat Sheet
Memorize this table. Exams often ask for the Order of Error or Degree of Exactness.
| Method | Polynomial Fit | Global Error | Exact Up To |
|---|---|---|---|
| Euler’s Method | Degree 1 (Linear) | \( O(h) \) | Degree 1 |
| Trapezoidal | Degree 1 (Linear) | \( O(h^2) \) | Degree 1 |
| Simpson’s 1/3 | Degree 2 (Parabola) | \( O(h^4) \) | Degree 3 (Cubic)! |
| Simpson’s 3/8 | Degree 3 (Cubic) | \( O(h^4) \) | Degree 3 (Cubic) |
If you are given \(N\) points, you have \(n = N-1\) intervals.
Example Scenario
You are given 5 Data Points.
Check Validity:
- Can use Simpson’s 1/3?
Is 4 even? YES → Valid. - Can use Simpson’s 3/8?
Is 4 multiple of 3? NO → Invalid.
- 1 Interval: Must use Trapezoidal.
- 2 Intervals: Use Simpson’s 1/3.
- 3 Intervals: Use Simpson’s 3/8.
- 6 Intervals: Both work. Prefer Simpson’s 1/3.
(It has a slightly smaller error constant).
How much does the error drop if you halve the step size \(h\)?
Euler’s Method
Error Order \( O(h) \)
Error drops by 2x
(Linear Convergence)Simpson’s 1/3
Error Order \( O(h^4) \)
Error drops by 16x
(\( (1/2)^4 = 1/16 \))Euler’s Method
Numerical Solution of Ordinary Differential Equations
- Type: Explicit, Single-step method.
- Geometry: Approximates the curve using Tangent Lines.
Error Analysis
- Order: First-Order Method.
- Global Error: \(O(h)\).
(Halving the step size \(h\) cuts the error in half). - Local Error: \(O(h^2)\)
(The error introduced in a single step).
Concavity Rules
\((y” > 0)\)
Method Underestimates
\((y” < 0)\)
Method Overestimates
Step Size (\(h\)) Dilemma
- Too Large: Instability and large errors (overshooting the curve).
- Too Small: Accumulation of round-off errors and high computational cost (slow).
Error Analysis in Interpolation
Key Formulas
Error Term: The error \( \color{purple}{E(x)} \) is defined as: $$ \color{purple}{E(x)} = \frac{\color{blue}{\Pi(x)}}{\color{blue}{(n+1)!}} \cdot \color{red}{f^{(n+1)}(\xi)} $$ Where \( \color{blue}{\Pi(x) = (x-x_0)(x-x_1)…(x-x_n)} \).
Error Bound Formula: To find the maximum error: $$ |E(x)| \le \frac{1}{(n+1)!} \cdot \max |\color{blue}{\Pi(x)}| \cdot \max |\color{red}{f^{(n+1)}(x)}| $$
Step Size Formula (Linear Interpolation): For equal spacing \( h \): $$ |E(x)| \le \frac{\color{green}{h^2}}{8} \max |\color{red}{f”(x)}| $$
Methodology
- Step 1: Identify \( n = \text{number of points} – 1 \).
- Step 2: Formulate \( \color{blue}{\Pi(x)} \).
- Step 3 (Derivative): Calculate \( \color{red}{f^{(n+1)}(x)} \) and find its maximum on the interval.
- Step 4 (Polynomial): Find the maximum of \( |\color{blue}{\Pi(x)}| \) by setting derivative to zero or checking endpoints.
4 Key Interpolation Formulas
1. Newton’s General Divided Difference Formula
Used for unequal intervals.
$$ f(x) = f(x_0) + \color{blue}{(x-x_0)}\color{red}{f[x_0, x_1]} + \color{blue}{(x-x_0)(x-x_1)}\color{red}{f[x_0, x_1, x_2]} + \dots $$2. Lagrange’s Interpolation Formula
Used for unequal intervals; no difference table required.
$$ P_n(x) = \sum_{i=0}^{n} \color{blue}{L_i(x)} \cdot \color{red}{f(x_i)} $$Where the basis polynomial is:
$$ \color{blue}{L_i(x)} = \frac{(x-x_0)\dots(x-x_{i-1})(x-x_{i+1})\dots(x-x_n)}{(x_i-x_0)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)} $$3. Newton’s Forward Difference Formula
Used for equal intervals (near start). Let \( \color{green}{u = \frac{x – x_0}{h}} \).
$$ y(x) = y_0 + \color{green}{u} \color{red}{\Delta y_0} + \frac{\color{green}{u(u-1)}}{2!} \color{red}{\Delta^2 y_0} + \frac{\color{green}{u(u-1)(u-2)}}{3!} \color{red}{\Delta^3 y_0} + \dots $$4. Newton’s Backward Difference Formula
Used for equal intervals (near end). Let \( \color{green}{u = \frac{x – x_n}{h}} \).
$$ y(x) = y_n + \color{green}{u} \color{red}{\nabla y_n} + \frac{\color{green}{u(u+1)}}{2!} \color{red}{\nabla^2 y_n} + \frac{\color{green}{u(u+1)(u+2)}}{3!} \color{red}{\nabla^3 y_n} + \dots $$