Answers
Step-by-step solutions and MATLAB implementations for Numerical Analysis.
1. Newton's Forward Difference Interpolation
Solution 1.1: Concept of Interpolation and Extrapolation
1. Definitions
- Interpolation is the mathematical technique of estimating unknown values of a function at an intermediate point lying inside the domain bounded by a discrete set of known observational points .
- Extrapolation is the process of estimating functional values at an argument lying outside the interval ( or ). Extrapolation carries greater uncertainty because the function's trend may change outside the observed region.
2. Condition for Observation Sequence
Given :
- Interpolation Condition:
- Extrapolation Condition: or
3. Forward Difference Operator
Let be functional values at equispaced nodes with step size .
- First Forward Differences:
- Second Forward Differences:
- General -th Forward Difference:
Solution 1.2: Difference Operator Identities and Difference Tables
1. Algebraic Proof:
Starting from the definition of the difference operator:
Substitute the first forward difference :
Expand both first forward differences:
Subtracting the two:
Similarly, for the third forward difference:
2. Symbolic Forward Difference Table
3. Numerical Forward Difference Table
Given:
- , step size
Compute column differences:
Solution 1.3: Newton's Forward Interpolation Numerical Evaluation
1. Formula Definition
where is the normalized coordinate parameter.
2. Numerical Calculation of
- Query point:
- Base node: (near the beginning of the table)
- Step size:
- Normalized coordinate:
From the difference table in Solution 1.2:
Substitute values into the formula:
Evaluate each term:
- Term 0:
- Term 1:
- Term 2:
- Term 3:
Summing all terms:
Why Forward Formula: The target argument lies close to the initial node . In forward interpolation, differences propagate from the top of the table, maximizing numerical stability and retaining significant digits.
Solution 1.4: Polynomial Reconstruction via Forward Differences
Points:
1. Difference Table
2. Parameters
3. Analytic Polynomial Derivation
Verification:
- (Matches perfectly)
Solution 1.5: Higher-Order Polynomial Reconstruction & Point Estimation
Data:
1. Difference Table
2. Degree Analysis
The third forward difference is constant across all entries, and all fourth differences are zero. By the Fundamental Theorem of Finite Differences, the underlying function is an exact cubic polynomial (degree ).
3. Closed-Form Polynomial
Base node .
4. Estimation at
Solution 1.6: Village Census Population Estimation
Data:
- ,
1. Difference Table
| Year () | Pop () | |||||
|---|---|---|---|---|---|---|
2. Parameter for
3. Interpolation Calculation
Substitute the numerical values:
Solution 1.7: Trigonometric Table Interpolation
1. Difference Table
2. Evaluation of
True analytical value: . Accuracy is within .
% MATLAB script: Newton's Forward Difference Interpolation
function y_interp = newton_forward(x_nodes, y_nodes, x_eval)
n = length(x_nodes);
diff_table = zeros(n, n);
diff_table(:, 1) = y_nodes(:);
for j = 2:n
for i = 1:(n - j + 1)
diff_table(i, j) = diff_table(i+1, j-1) - diff_table(i, j-1);
end
end
h = x_nodes(2) - x_nodes(1);
u = (x_eval - x_nodes(1)) / h;
y_interp = diff_table(1, 1);
u_term = 1;
fact = 1;
for k = 1:(n-1)
u_term = u_term * (u - k + 1);
fact = fact * k;
y_interp = y_interp + (u_term / fact) * diff_table(1, k+1);
end
end2. Newton's Backward Difference Interpolation
Solution 2.1: Backward Difference Operator and Table Construction
1. Definition and Operator Relationship
The backward difference operator acts on a sequence of functional ordinates as:
Relationship to forward difference:
2. Higher-Order Differences
3. Symbolic Backward Difference Table
Solution 2.2: Newton's Backward Interpolation Formula
where:
When to use: When the point of interest is situated in the lower half or near the terminal boundary of the tabular data ().
Solution 2.3: Numerical Evaluation using Backward Differences
Measurements:
- , step size
1. Complete Backward Difference Table
2. Terminal Differences and Normalized Parameter
- Terminal point:
- Target:
- Bottom row difference coefficients:
3. Step-by-Step Numerical Computation of
Evaluate term-by-term:
- Term 3 is because
Summing all components:
Lecture Slide Arithmetic Note
In the course lecture slides, the intermediate addition was recorded as , but due to a typo/subtraction oversight, the printed final answer was given as . The true algebraic sum is , which minus the remaining terms yields (or ). Both answers are provided for examination reference.
Solution 2.4: Advantages, Disadvantages & Computer Science Applications
1. Trade-Offs
- Advantages:
- Simple, structured, and computationally inexpensive for equidistant tables.
- Highly accurate for data points located near the end of a series.
- Incrementally extendable when new chronological data arrives without recomputing previous difference columns.
- Disadvantages:
- Strictly limited to uniform grid spacings ().
- Truncation and round-off error accumulate when higher-order differences oscillate.
2. Computer Science Applications
- Digital Image Processing: In image scaling and super-resolution, pixel intensities at sub-pixel coordinates are interpolated from neighboring discrete grid pixels using 2D separable interpolation formulas.
- Game Physics & Graphics (
lerp): The linear interpolation function: is the degree-1 instance of Newton's forward/backward difference formula (). It enables smooth camera panning, character skeletal animation, and frame-rate independent physics trajectory integration.
% MATLAB script: Newton's Backward Difference Interpolation
function y_interp = newton_backward(x_nodes, y_nodes, x_eval)
n = length(x_nodes);
diff_table = zeros(n, n);
diff_table(:, 1) = y_nodes(:);
for j = 2:n
for i = j:n
diff_table(i, j) = diff_table(i, j-1) - diff_table(i-1, j-1);
end
end
h = x_nodes(2) - x_nodes(1);
p = (x_eval - x_nodes(end)) / h;
y_interp = diff_table(n, 1);
p_term = 1;
fact = 1;
for k = 1:(n-1)
p_term = p_term * (p + k - 1);
fact = fact * k;
y_interp = y_interp + (p_term / fact) * diff_table(n, k+1);
end
end3. Lagrange Interpolation for Unequal Intervals
Solution 3.1: Derivation of the Lagrange Interpolation Formula
1. Limitation of Newton Difference Formulas
Newton's forward and backward formulas require strict uniform spacing . In experimental datasets, missing samples, non-uniform sensor rates, or arbitrary sampling require methods supporting arbitrary unequal intervals.
2. Formal Derivation
Given points with distinct abscissae: Let the interpolating polynomial of degree be: P_n(x) = A_0(x - x_1)(x - x_2)\cdots(x - x_n) + A_1(x - x_0)(x - x_2)\cdots(x - x_n) + \cdots + A_n(x - x_0)(x - x_1)\cdots(x - x_{n-1}) \tag{1}
To determine the constant , evaluate (1) at :
Similarly, evaluating at eliminates all terms except the -th:
Substituting back into (1) yields the Lagrange Interpolation Formula:
3. Kronecker Delta Property
The cardinal Lagrange polynomials satisfy:
Solution 3.2: Lagrange Evaluation with Unequally Spaced Nodes
Dataset:
- (Intervals: — non-uniform)
1. Evaluation at
Compute each cardinal basis function :
-
for :
-
for :
-
for :
-
for :
-
for :
Summing the exact contributions:
Course Slide Arithmetic Note
In the course lecture notes, the author made handwritten arithmetic slips in the denominators (e.g., miscomputing as instead of , yielding , , , , ), which led to the printed value of . Both the exact mathematical value () and the slide artifact value () are recorded here for complete transparency.
2. Exact Analytic Evaluation at
The underlying generator polynomial for the data points is:
Evaluating via Lagrange interpolation at (as originally posed on Slide 8):
Summing all contributions:
% MATLAB script: Lagrange Interpolation
function y_eval = lagrange_interp(x_nodes, y_nodes, x_val)
n = length(x_nodes);
y_eval = 0;
for i = 1:n
L_i = 1;
for j = 1:n
if j ~= i
L_i = L_i * (x_val - x_nodes(j)) / (x_nodes(i) - x_nodes(j));
end
end
y_eval = y_eval + y_nodes(i) * L_i;
end
end4. Central Difference Interpolation Methods
Solution 4.1: Gauss's Forward Central Difference Formula
1. Derivation via Operator Identities
Let the origin be , step size , and normalized parameter . The shift operator gives:
To centralize around , relate higher-order forward differences to negative indices using :
Grouping terms with common central difference coefficients yields Gauss's Forward Formula:
2. Numerical Problem:
Data:
- , step
Choose central origin :
Central Difference Table:
| () | () | () | () | ||
| () | () | ||||
Selected coefficients:
Compute terms for :
Summing all terms:
Solution 4.2: Gauss's Backward Central Difference Formula
1. Formula
2. Population in
Data:
- ,
- (thousands)
Choose :
Difference Table:
| Year | Pop | |||||
|---|---|---|---|---|---|---|
| () | () | () | () | () | () | |
Selected terms:
Evaluation:
Solution 4.3: Stirling's Central Difference Formula
1. Derivation
Stirling's formula is formed by taking the arithmetic mean of Gauss's forward formula and Gauss's backward formula:
2. Evaluation of
Data: .
Difference Table:
- :
- : ()
- : ()
- : ()
Substitute into Stirling's formula:
Solution 4.4: Bessel's Central Difference Formula
1. Formula
Bessel's formula is symmetric about , making it ideal for the range .
2. Temperature
Data: , , .
- Choose .
Differences:
- :
- :
- :
Computation:
5. Numerical Quadrature: Trapezoidal & Simpson's Rules
Solution 5.1: Composite Trapezoidal Rule
1. Formula & Step Size
Dividing into equal subintervals with and :
2. Evaluation of with
Grid coordinates and ordinates:
Sum of intermediate terms :
Substitute into formula:
Slide Typo Note
In the course slide (PDF 5, Slide 5), the intermediate sum was handwritten
with a minor typo as 6.1871, but the final computation correctly evaluated
.
Analytical exact value: Absolute Error: .
Solution 5.2: Simpson's 1/3 Rule
1. Formula & Interval Constraint
Constraint: must be an even number () because each parabola is fitted across a pair of adjacent intervals ().
2. Evaluation of with
Grid ordinates:
Grouping terms:
- Endpoints:
- Odd indices ():
- Even indices ():
Substitute into formula:
Solution 5.3: Simpson's 3/8 Rule
1. Formula & Constraint
Constraint: must be a multiple of 3 () because cubic polynomials are fitted over sets of three subintervals.
2. Numerical Computation for
Using the identical coordinates and values from Solution 5.2:
- Endpoints:
- Multipliers of 3: Indices :
- Multipliers of 2: Index :
Substitute into Simpson's 3/8 formula:
Comparison: Simpson's 1/3 () and Simpson's 3/8 () agree to three decimal places. Simpson's 3/8 exhibits slightly higher accuracy per panel due to cubic polynomial fitting.
Solution 5.4: Comparison of Newton-Cotes Quadrature Methods
| Method | Polynomial Degree () | Subinterval Constraint | Local Error | Global Error | Degree of Exactness |
|---|---|---|---|---|---|
| Trapezoidal Rule | (Linear) | (any positive integer) | |||
| Simpson's 1/3 Rule | (Quadratic) | must be even () | |||
| Simpson's 3/8 Rule | (Cubic) | must be a multiple of 3 () |
% MATLAB script: Numerical Integration Suite
function [trap, simp13, simp38] = numerical_integration(f, a, b, n)
h = (b - a) / n;
x = linspace(a, b, n + 1);
y = f(x);
% Trapezoidal Rule
trap = (h / 2) * (y(1) + 2 * sum(y(2:end-1)) + y(end));
% Simpson's 1/3 Rule (requires even n)
if mod(n, 2) == 0
simp13 = (h / 3) * (y(1) + y(end) + 4 * sum(y(2:2:end-1)) + 2 * sum(y(3:2:end-2)));
else
simp13 = NaN;
end
% Simpson's 3/8 Rule (requires n multiple of 3)
if mod(n, 3) == 0
idx_2 = 4:3:n;
idx_3 = setdiff(2:n, idx_2);
simp38 = (3 * h / 8) * (y(1) + y(end) + 3 * sum(y(idx_3)) + 2 * sum(y(idx_2)));
else
simp38 = NaN;
end
end6. Systems of Linear Equations: Iterative Methods
Solution 6.1: Strictly Diagonally Dominant Systems
1. Definition
A matrix is strictly diagonally dominant (SDD) if in every row, the absolute value of the diagonal entry strictly exceeds the sum of the absolute values of all off-diagonal entries:
2. Convergence Guarantee
By the Levy-Desplanques theorem and spectral radius properties (), strict diagonal dominance guarantees that the iteration matrices and have spectral radii strictly bounded inside the unit disk (). Thus, iterations are guaranteed to converge unconditionally for any initial guess .
3. Rearrangement of Given System
Initial system:
Examine coefficients:
- In Eq 2: (Boundary / dominant for ).
- In Eq 3: (Strictly dominant for ).
- In Eq 1: (Strictly dominant for ).
Rearranged diagonally dominant system:
Solution 6.2: Gauss-Jacobi Method Iterative Solution
1. Iterative Formulas
Isolating each diagonal variable:
2. Step-by-Step Iterations from
-
Iteration :
-
Iteration :
-
Iteration :
3. Summary Table (Iter 0 to 10)
(Exact analytical limit: )
Solution 6.3: Gauss-Seidel Method Iterative Solution
1. In-Place Iterative Update Formulas
In Gauss-Seidel, as soon as a new coordinate value is calculated, it is immediately substituted into subsequent formulas within the same iteration:
2. Step-by-Step Iterations from
-
Iteration :
-
Iteration :
3. Complete Gauss-Seidel Iteration Table
At iteration , the solution converges rapidly toward the exact system root .
% MATLAB script: Gauss-Jacobi and Gauss-Seidel Solvers
function [x_jacobi, x_seidel] = linear_iterative_solvers(A, b, max_iter, tol)
n = length(b);
% Gauss-Jacobi
x_j = zeros(n, 1);
for k = 1:max_iter
x_new = zeros(n, 1);
for i = 1:n
sigma = A(i, :) * x_j - A(i, i) * x_j(i);
x_new(i) = (b(i) - sigma) / A(i, i);
end
if norm(x_new - x_j, inf) < tol
break;
end
x_j = x_new;
end
x_jacobi = x_j;
% Gauss-Seidel
x_s = zeros(n, 1);
for k = 1:max_iter
x_old = x_s;
for i = 1:n
sigma1 = A(i, 1:i-1) * x_s(1:i-1);
sigma2 = A(i, i+1:n) * x_old(i+1:n);
x_s(i) = (b(i) - sigma1 - sigma2) / A(i, i);
end
if norm(x_s - x_old, inf) < tol
break;
end
end
x_seidel = x_s;
endSolution 6.4: Comparison: Gauss-Jacobi vs. Gauss-Seidel
- Convergence Speed: Gauss-Seidel incorporates updated state vectors immediately, generally converging approximately twice as fast as Gauss-Jacobi ().
- Memory Footprint:
- Gauss-Jacobi requires two separate vectors in memory ( and ) because updates cannot overwrite values needed by other equations.
- Gauss-Seidel operates in-place with a single memory vector, halving the state storage requirement.
- Parallel Architecture Suitability:
- Gauss-Jacobi is highly parallelizable across GPUs and multi-threaded clusters since every coordinate update is completely independent of other updates at step .
- Gauss-Seidel possesses inherently sequential data dependencies ( depends on , on ), requiring specialized graph coloring or wavefront algorithms for parallelization.