Skip to Content
PrepPath logoPrepPath

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 y=f(x)y = f(x) at an intermediate point xx lying inside the domain bounded by a discrete set of known observational points [x0,xn][x_0, x_n].
  • Extrapolation is the process of estimating functional values at an argument xx lying outside the interval [x0,xn][x_0, x_n] (x<x0x < x_0 or x>xnx > x_n). Extrapolation carries greater uncertainty because the function's trend may change outside the observed region.

2. Condition for Observation Sequence

Given x0<x1<x2<⋯<xnx_0 < x_1 < x_2 < \dots < x_n:

  • Interpolation Condition: x0≤x≤xnx_0 \le x \le x_n
  • Extrapolation Condition: x<x0x < x_0 or x>xnx > x_n

3. Forward Difference Operator Δ\Delta

Let y0,y1,y2,…,yny_0, y_1, y_2, \dots, y_n be functional values at equispaced nodes xi=x0+ihx_i = x_0 + i h with step size hh.

  • First Forward Differences: Δyi=yi+1−yifor i=0,1,…,n−1\Delta y_i = y_{i+1} - y_i \quad \text{for } i = 0, 1, \dots, n-1
  • Second Forward Differences: Δ2yi=Δ(Δyi)=Δyi+1−Δyi\Delta^2 y_i = \Delta(\Delta y_i) = \Delta y_{i+1} - \Delta y_i
  • General kk-th Forward Difference: Δkyi=Δk−1yi+1−Δk−1yi=∑j=0k(−1)k−j(kj)yi+j\Delta^k y_i = \Delta^{k-1} y_{i+1} - \Delta^{k-1} y_i = \sum_{j=0}^k (-1)^{k-j} \binom{k}{j} y_{i+j}

Solution 1.2: Difference Operator Identities and Difference Tables

1. Algebraic Proof: Δ2y2=y4−2y3+y2\Delta^2 y_2 = y_4 - 2y_3 + y_2

Starting from the definition of the difference operator: Δ2y2=Δ(Δy2)\Delta^2 y_2 = \Delta(\Delta y_2)

Substitute the first forward difference Δy2=y3−y2\Delta y_2 = y_3 - y_2: Δ2y2=Δ(y3−y2)=Δy3−Δy2\Delta^2 y_2 = \Delta(y_3 - y_2) = \Delta y_3 - \Delta y_2

Expand both first forward differences: Δy3=y4−y3\Delta y_3 = y_4 - y_3 Δy2=y3−y2\Delta y_2 = y_3 - y_2

Subtracting the two: Δ2y2=(y4−y3)−(y3−y2)=y4−y3−y3+y2=y4−2y3+y2■\Delta^2 y_2 = (y_4 - y_3) - (y_3 - y_2) = y_4 - y_3 - y_3 + y_2 = y_4 - 2y_3 + y_2 \quad \blacksquare

Similarly, for the third forward difference: Δ3y3=y6−3y5+3y4−y3\Delta^3 y_3 = y_6 - 3y_5 + 3y_4 - y_3

2. Symbolic Forward Difference Table

xxyyΔy\Delta yΔ2y\Delta^2 yΔ3y\Delta^3 yΔ4y\Delta^4 yΔ5y\Delta^5 y
x0x_0y0y_0Δy0\Delta y_0Δ2y0\Delta^2 y_0Δ3y0\Delta^3 y_0Δ4y0\Delta^4 y_0Δ5y0\Delta^5 y_0
x1x_1y1y_1Δy1\Delta y_1Δ2y1\Delta^2 y_1Δ3y1\Delta^3 y_1Δ4y1\Delta^4 y_1
x2x_2y2y_2Δy2\Delta y_2Δ2y2\Delta^2 y_2Δ3y2\Delta^3 y_2
x3x_3y3y_3Δy3\Delta y_3Δ2y3\Delta^2 y_3
x4x_4y4y_4Δy4\Delta y_4
x5x_5y5y_5

3. Numerical Forward Difference Table

Given:

  • x∈{20,23,26,29}x \in \{20, 23, 26, 29\}, step size h=3h = 3
  • y∈{0.3420,0.3907,0.4384,0.4848}y \in \{0.3420, 0.3907, 0.4384, 0.4848\}

Compute column differences:

  • Δy0=0.3907−0.3420=0.0487\Delta y_0 = 0.3907 - 0.3420 = 0.0487
  • Δy1=0.4384−0.3907=0.0477\Delta y_1 = 0.4384 - 0.3907 = 0.0477
  • Δy2=0.4848−0.4384=0.0464\Delta y_2 = 0.4848 - 0.4384 = 0.0464
  • Δ2y0=0.0477−0.0487=−0.0010\Delta^2 y_0 = 0.0477 - 0.0487 = -0.0010
  • Δ2y1=0.0464−0.0477=−0.0013\Delta^2 y_1 = 0.0464 - 0.0477 = -0.0013
  • Δ3y0=−0.0013−(−0.0010)=−0.0003\Delta^3 y_0 = -0.0013 - (-0.0010) = -0.0003
xxyyΔy\Delta yΔ2y\Delta^2 yΔ3y\Delta^3 y
20200.34200.34200.04870.0487−0.0010-0.0010−0.0003-0.0003
23230.39070.39070.04770.0477−0.0013-0.0013
26260.43840.43840.04640.0464
29290.48480.4848

Solution 1.3: Newton's Forward Interpolation Numerical Evaluation

1. Formula Definition

Pn(x)=y0+u Δy0+u(u−1)2! Δ2y0+u(u−1)(u−2)3! Δ3y0+⋯+u(u−1)⋯(u−n+1)n! Δny0P_n(x) = y_0 + u\,\Delta y_0 + \frac{u(u-1)}{2!}\,\Delta^2 y_0 + \frac{u(u-1)(u-2)}{3!}\,\Delta^3 y_0 + \cdots + \frac{u(u-1)\cdots(u-n+1)}{n!}\,\Delta^n y_0 where u=x−x0hu = \frac{x - x_0}{h} is the normalized coordinate parameter.

2. Numerical Calculation of y(21)y(21)

  • Query point: x=21x = 21
  • Base node: x0=20x_0 = 20 (near the beginning of the table)
  • Step size: h=23−20=3h = 23 - 20 = 3
  • Normalized coordinate: u=21−203=13≈0.3333u = \frac{21 - 20}{3} = \frac{1}{3} \approx 0.3333

From the difference table in Solution 1.2:

  • y0=0.3420y_0 = 0.3420
  • Δy0=0.0487\Delta y_0 = 0.0487
  • Δ2y0=−0.0010\Delta^2 y_0 = -0.0010
  • Δ3y0=−0.0003\Delta^3 y_0 = -0.0003

Substitute values into the formula: y(21)=y0+u Δy0+u(u−1)2 Δ2y0+u(u−1)(u−2)6 Δ3y0y(21) = y_0 + u\,\Delta y_0 + \frac{u(u-1)}{2}\,\Delta^2 y_0 + \frac{u(u-1)(u-2)}{6}\,\Delta^3 y_0

Evaluate each term:

  1. Term 0: y0=0.3420y_0 = 0.3420
  2. Term 1: u Δy0=0.3333×0.0487≈0.016217u\,\Delta y_0 = 0.3333 \times 0.0487 \approx 0.016217
  3. Term 2: 0.3333(0.3333−1)2(−0.0010)=0.3333(−0.6667)2(−0.0010)≈+0.000111\frac{0.3333(0.3333 - 1)}{2}(-0.0010) = \frac{0.3333(-0.6667)}{2}(-0.0010) \approx +0.000111
  4. Term 3: 0.3333(0.3333−1)(0.3333−2)6(−0.0003)=0.3333(−0.6667)(−1.6667)6(−0.0003)≈−0.000019\frac{0.3333(0.3333 - 1)(0.3333 - 2)}{6}(-0.0003) = \frac{0.3333(-0.6667)(-1.6667)}{6}(-0.0003) \approx -0.000019

Summing all terms: y(21)=0.3420+0.016217+0.000111−0.000019=0.358309≈0.3583y(21) = 0.3420 + 0.016217 + 0.000111 - 0.000019 = 0.358309 \approx 0.3583

Why Forward Formula: The target argument x=21x = 21 lies close to the initial node x0=20x_0 = 20. 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: (0,1),(1,3),(2,7),(3,13)(0, 1), (1, 3), (2, 7), (3, 13)

1. Difference Table

xxyyΔy\Delta yΔ2y\Delta^2 yΔ3y\Delta^3 y
0011222200
11334422
227766
331313

2. Parameters

  • x0=0,h=1x_0 = 0, h = 1
  • u=x−01=xu = \frac{x - 0}{1} = x
  • y0=1,Δy0=2,Δ2y0=2,Δ3y0=0y_0 = 1, \Delta y_0 = 2, \Delta^2 y_0 = 2, \Delta^3 y_0 = 0

3. Analytic Polynomial Derivation

f(x)=y0+u Δy0+u(u−1)2! Δ2y0f(x) = y_0 + u\,\Delta y_0 + \frac{u(u-1)}{2!}\,\Delta^2 y_0 f(x)=1+x(2)+x(x−1)2(2)f(x) = 1 + x(2) + \frac{x(x-1)}{2}(2) f(x)=1+2x+(x2−x)=x2+x+1f(x) = 1 + 2x + (x^2 - x) = x^2 + x + 1

Verification:

  • f(0)=1f(0) = 1
  • f(1)=1+1+1=3f(1) = 1 + 1 + 1 = 3
  • f(2)=4+2+1=7f(2) = 4 + 2 + 1 = 7
  • f(3)=9+3+1=13f(3) = 9 + 3 + 1 = 13 (Matches perfectly)

Solution 1.5: Higher-Order Polynomial Reconstruction & Point Estimation

Data: (1,1),(2,8),(3,27),(4,64),(5,125),(6,216),(7,343),(8,512)(1, 1), (2, 8), (3, 27), (4, 64), (5, 125), (6, 216), (7, 343), (8, 512)

1. Difference Table

xxyyΔy\Delta yΔ2y\Delta^2 yΔ3y\Delta^3 yΔ4y\Delta^4 y
11117712126600
2288191918186600
3327273737242466
44646461613030
551251259191
66216216

2. Degree Analysis

The third forward difference Δ3y=6\Delta^3 y = 6 is constant across all entries, and all fourth differences Δ4y\Delta^4 y are zero. By the Fundamental Theorem of Finite Differences, the underlying function is an exact cubic polynomial (degree n=3n = 3).

3. Closed-Form Polynomial f(x)f(x)

Base node x0=1,h=1  ⟹  u=x−1x_0 = 1, h = 1 \implies u = x - 1. f(x)=y0+u Δy0+u(u−1)2! Δ2y0+u(u−1)(u−2)3! Δ3y0f(x) = y_0 + u\,\Delta y_0 + \frac{u(u-1)}{2!}\,\Delta^2 y_0 + \frac{u(u-1)(u-2)}{3!}\,\Delta^3 y_0 f(x)=1+(x−1)(7)+(x−1)(x−2)2(12)+(x−1)(x−2)(x−3)6(6)f(x) = 1 + (x-1)(7) + \frac{(x-1)(x-2)}{2}(12) + \frac{(x-1)(x-2)(x-3)}{6}(6) f(x)=1+7x−7+6(x2−3x+2)+(x3−6x2+11x−6)f(x) = 1 + 7x - 7 + 6(x^2 - 3x + 2) + (x^3 - 6x^2 + 11x - 6) f(x)=1+7x−7+6x2−18x+12+x3−6x2+11x−6=x3f(x) = 1 + 7x - 7 + 6x^2 - 18x + 12 + x^3 - 6x^2 + 11x - 6 = x^3

4. Estimation at (10,s)(10, s)

s=f(10)=103=1000s = f(10) = 10^3 = 1000


Solution 1.6: Village Census Population Estimation

Data:

  • x∈{1941,1951,1961,1971,1981,1991}x \in \{1941, 1951, 1961, 1971, 1981, 1991\}, h=10h = 10
  • y∈{2500,2800,3200,3700,4350,5225}y \in \{2500, 2800, 3200, 3700, 4350, 5225\}

1. Difference Table

Year (xx)Pop (yy)Δy\Delta yΔ2y\Delta^2 yΔ3y\Delta^3 yΔ4y\Delta^4 yΔ5y\Delta^5 y
1941194125002500300300100100005050−25-25
195119512800280040040010010050502525
19611961320032005005001501507575
1971197137003700650650225225
1981198143504350875875
1991199152255225

2. Parameter uu for x=1945x = 1945

x0=1941,h=10  ⟹  u=1945−194110=0.4x_0 = 1941, \quad h = 10 \implies u = \frac{1945 - 1941}{10} = 0.4

3. Interpolation Calculation

y(1945)=y0+u Δy0+u(u−1)2 Δ2y0+u(u−1)(u−2)6 Δ3y0+u(u−1)(u−2)(u−3)24 Δ4y0+u(u−1)(u−2)(u−3)(u−4)120 Δ5y0y(1945) = y_0 + u\,\Delta y_0 + \frac{u(u-1)}{2}\,\Delta^2 y_0 + \frac{u(u-1)(u-2)}{6}\,\Delta^3 y_0 + \frac{u(u-1)(u-2)(u-3)}{24}\,\Delta^4 y_0 + \frac{u(u-1)(u-2)(u-3)(u-4)}{120}\,\Delta^5 y_0

Substitute the numerical values:

  • y0=2500y_0 = 2500
  • u Δy0=0.4×300=120u\,\Delta y_0 = 0.4 \times 300 = 120
  • 0.4(−0.6)2(100)=−12\frac{0.4(-0.6)}{2}(100) = -12
  • 0.4(−0.6)(−1.6)6(0)=0\frac{0.4(-0.6)(-1.6)}{6}(0) = 0
  • 0.4(−0.6)(−1.6)(−2.6)24(50)=−0.998424×50=−2.08\frac{0.4(-0.6)(-1.6)(-2.6)}{24}(50) = \frac{-0.9984}{24} \times 50 = -2.08
  • 0.4(−0.6)(−1.6)(−2.6)(−3.6)120(−25)=3.59424120(−25)=−0.7488\frac{0.4(-0.6)(-1.6)(-2.6)(-3.6)}{120}(-25) = \frac{3.59424}{120}(-25) = -0.7488

y(1945)=2500+120−12+0−2.08−0.7488=2605.1712≈2605 peopley(1945) = 2500 + 120 - 12 + 0 - 2.08 - 0.7488 = 2605.1712 \approx 2605 \text{ people}


Solution 1.7: Trigonometric Table Interpolation

1. Difference Table

xxsin⁡(x)\sin(x)Δy\Delta yΔ2y\Delta^2 yΔ3y\Delta^3 yΔ4y\Delta^4 yΔ5y\Delta^5 y
15∘15^\circ0.25881900.25881900.08320110.0832011−0.0026029-0.0026029−0.0006136-0.00061360.00002480.00002480.00000410.0000041
20∘20^\circ0.34202010.34202010.08059820.0805982−0.0032165-0.0032165−0.0005888-0.00058880.00002890.0000289
25∘25^\circ0.42261830.42261830.07738170.0773817−0.0038053-0.0038053−0.0005599-0.0005599
30∘30^\circ0.50000000.50000000.07357640.0735764−0.0043652-0.0043652
35∘35^\circ0.57357640.57357640.06921120.0692112
40∘40^\circ0.64278760.6427876

2. Evaluation of sin⁡(18∘)\sin(18^\circ)

  • x0=15∘,h=5∘,x=18∘  ⟹  u=18−155=0.6x_0 = 15^\circ, h = 5^\circ, x = 18^\circ \implies u = \frac{18 - 15}{5} = 0.6
  • y(18)=0.2588190+0.6(0.0832011)+0.6(−0.4)2(−0.0026029)+0.6(−0.4)(−1.4)6(−0.0006136)+0.6(−0.4)(−1.4)(−2.4)24(0.0000248)y(18) = 0.2588190 + 0.6(0.0832011) + \frac{0.6(-0.4)}{2}(-0.0026029) + \frac{0.6(-0.4)(-1.4)}{6}(-0.0006136) + \frac{0.6(-0.4)(-1.4)(-2.4)}{24}(0.0000248)
  • y(18)=0.2588190+0.04992066+0.00031235−0.00003436−0.00000083≈0.3090168y(18) = 0.2588190 + 0.04992066 + 0.00031235 - 0.00003436 - 0.00000083 \approx 0.3090168

True analytical value: sin⁡(18∘)=5−14≈0.30901699\sin(18^\circ) = \frac{\sqrt{5} - 1}{4} \approx 0.30901699. Accuracy is within 10−710^{-7}.

% 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
end

2. Newton's Backward Difference Interpolation

Solution 2.1: Backward Difference Operator and Table Construction

1. Definition and Operator Relationship

The backward difference operator ∇\nabla acts on a sequence of functional ordinates as: ∇yk=yk−yk−1\nabla y_k = y_k - y_{k-1}

Relationship to forward difference: Δyk−1=yk−yk−1=∇yk  ⟹  ∇=1−E−1\Delta y_{k-1} = y_k - y_{k-1} = \nabla y_k \implies \nabla = 1 - E^{-1}

2. Higher-Order Differences

∇2yn=∇(∇yn)=∇yn−∇yn−1=yn−2yn−1+yn−2\nabla^2 y_n = \nabla(\nabla y_n) = \nabla y_n - \nabla y_{n-1} = y_n - 2y_{n-1} + y_{n-2} ∇kyn=∑j=0k(−1)j(kj)yn−j\nabla^k y_n = \sum_{j=0}^k (-1)^j \binom{k}{j} y_{n-j}

3. Symbolic Backward Difference Table

xxyy∇y\nabla y∇2y\nabla^2 y∇3y\nabla^3 y∇4y\nabla^4 y
x0x_0y0y_0
x1x_1y1y_1∇y1\nabla y_1
x2x_2y2y_2∇y2\nabla y_2∇2y2\nabla^2 y_2
x3x_3y3y_3∇y3\nabla y_3∇2y3\nabla^2 y_3∇3y3\nabla^3 y_3
x4x_4y4y_4∇y4\nabla y_4∇2y4\nabla^2 y_4∇3y4\nabla^3 y_4∇4y4\nabla^4 y_4

Solution 2.2: Newton's Backward Interpolation Formula

Pn(x)=yn+p ∇yn+p(p+1)2! ∇2yn+p(p+1)(p+2)3! ∇3yn+⋯+p(p+1)⋯(p+n−1)n! ∇nynP_n(x) = y_n + p\,\nabla y_n + \frac{p(p+1)}{2!}\,\nabla^2 y_n + \frac{p(p+1)(p+2)}{3!}\,\nabla^3 y_n + \cdots + \frac{p(p+1)\cdots(p+n-1)}{n!}\,\nabla^n y_n where: p=x−xnhp = \frac{x - x_n}{h}

When to use: When the point of interest xx is situated in the lower half or near the terminal boundary of the tabular data (x≈xnx \approx x_n).


Solution 2.3: Numerical Evaluation using Backward Differences

Measurements:

  • x∈{20,25,30,35,40,45}x \in \{20, 25, 30, 35, 40, 45\}, step size h=5h = 5
  • y∈{354,332,291,260,231,204}y \in \{354, 332, 291, 260, 231, 204\}

1. Complete Backward Difference Table

xxyy∇y\nabla y∇2y\nabla^2 y∇3y\nabla^3 y∇4y\nabla^4 y∇5y\nabla^5 y
2020354354
2525332332−22-22
3030291291−41-41−19-19
3535260260−31-3110102929
4040231231−29-2922−8-8−37-37
4545204204−27-272200884545

2. Terminal Differences and Normalized Parameter

  • Terminal point: xn=45,yn=204,h=5x_n = 45, y_n = 204, h = 5
  • Target: x=42x = 42
  • p=42−455=−35=−0.6p = \frac{42 - 45}{5} = \frac{-3}{5} = -0.6
  • Bottom row difference coefficients:
    • yn=204y_n = 204
    • ∇yn=−27\nabla y_n = -27
    • ∇2yn=2\nabla^2 y_n = 2
    • ∇3yn=0\nabla^3 y_n = 0
    • ∇4yn=8\nabla^4 y_n = 8
    • ∇5yn=45\nabla^5 y_n = 45

3. Step-by-Step Numerical Computation of f(42)f(42)

f(42)=204+(−0.6)(−27)+(−0.6)(−0.6+1)2(2)+(−0.6)(−0.6+1)(−0.6+2)6(0)+(−0.6)(0.4)(1.4)(2.4)24(8)+(−0.6)(0.4)(1.4)(2.4)(3.4)120(45)f(42) = 204 + (-0.6)(-27) + \frac{(-0.6)(-0.6 + 1)}{2}(2) + \frac{(-0.6)(-0.6+1)(-0.6+2)}{6}(0) + \frac{(-0.6)(0.4)(1.4)(2.4)}{24}(8) + \frac{(-0.6)(0.4)(1.4)(2.4)(3.4)}{120}(45)

Evaluate term-by-term:

  1. yn=204y_n = 204
  2. p ∇yn=(−0.6)(−27)=+16.2p\,\nabla y_n = (-0.6)(-27) = +16.2
  3. (−0.6)(0.4)2(2)=−0.24\frac{(-0.6)(0.4)}{2}(2) = -0.24
  4. Term 3 is 00 because ∇3yn=0\nabla^3 y_n = 0
  5. −0.806424(8)=−0.2688≈−0.26\frac{-0.8064}{24}(8) = -0.2688 \approx -0.26
  6. −2.74176120(45)=−1.02816≈−1.02\frac{-2.74176}{120}(45) = -1.02816 \approx -1.02

Summing all components: f(42)=204+16.2−0.24+0−0.2688−1.02816=218.66304≈218.66f(42) = 204 + 16.2 - 0.24 + 0 - 0.2688 - 1.02816 = 218.66304 \approx 218.66

Lecture Slide Arithmetic Note

In the course lecture slides, the intermediate addition was recorded as 204+16.2−0.24−0.26−1.02204 + 16.2 - 0.24 - 0.26 - 1.02, but due to a typo/subtraction oversight, the printed final answer was given as 216.68216.68. The true algebraic sum is 204+16.2=220.2204 + 16.2 = 220.2, which minus the remaining terms yields 218.66218.66 (or 218.68218.68). 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 (h=constanth = \text{constant}).
    • 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 (x,y)(x, y) are interpolated from neighboring discrete grid pixels using 2D separable interpolation formulas.
  • Game Physics & Graphics (lerp): The linear interpolation function: lerp(a,b,t)=a+t(b−a)\text{lerp}(a, b, t) = a + t(b - a) is the degree-1 instance of Newton's forward/backward difference formula (h=1,u=th=1, u=t). 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
end

3. 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 xi+1−xi=h=constantx_{i+1} - x_i = h = \text{constant}. In experimental datasets, missing samples, non-uniform sensor rates, or arbitrary sampling require methods supporting arbitrary unequal intervals.

2. Formal Derivation

Given (n+1)(n+1) points (x0,y0),(x1,y1),…,(xn,yn)(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n) with distinct abscissae: Let the interpolating polynomial of degree nn 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 A0A_0, evaluate (1) at x=x0x = x_0: Pn(x0)=y0=A0(x0−x1)(x0−x2)⋯(x0−xn)+0+⋯+0P_n(x_0) = y_0 = A_0(x_0 - x_1)(x_0 - x_2)\cdots(x_0 - x_n) + 0 + \dots + 0   ⟹  A0=y0(x0−x1)(x0−x2)⋯(x0−xn)\implies A_0 = \frac{y_0}{(x_0 - x_1)(x_0 - x_2)\cdots(x_0 - x_n)}

Similarly, evaluating at x=xkx = x_k eliminates all terms except the kk-th: yk=Ak∏j≠k(xk−xj)  ⟹  Ak=yk∏j≠k(xk−xj)y_k = A_k \prod_{j \ne k} (x_k - x_j) \implies A_k = \frac{y_k}{\prod_{j \ne k} (x_k - x_j)}

Substituting AkA_k back into (1) yields the Lagrange Interpolation Formula: Pn(x)=∑i=0nyiLi(x),where Li(x)=∏j=0,j≠inx−xjxi−xjP_n(x) = \sum_{i=0}^n y_i L_i(x), \quad \text{where } L_i(x) = \prod_{j=0, j \ne i}^n \frac{x - x_j}{x_i - x_j}

3. Kronecker Delta Property

The cardinal Lagrange polynomials satisfy: Li(xj)=δij={1if i=j0if i≠jL_i(x_j) = \delta_{ij} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{if } i \ne j \end{cases}


Solution 3.2: Lagrange Evaluation with Unequally Spaced Nodes

Dataset:

  • x=[5,7,11,13,17]x = [5, 7, 11, 13, 17] (Intervals: 2,4,2,42, 4, 2, 4 — non-uniform)
  • y=[150,392,1452,2366,5202]y = [150, 392, 1452, 2366, 5202]

1. Evaluation at x=10x = 10

Compute each cardinal basis function Li(10)=∏j≠i10−xjxi−xjL_i(10) = \prod_{j \ne i} \frac{10 - x_j}{x_i - x_j}:

  • L0(10)L_0(10) for x0=5x_0 = 5: L0(10)=(10−7)(10−11)(10−13)(10−17)(5−7)(5−11)(5−13)(5−17)=(3)(−1)(−3)(−7)(−2)(−6)(−8)(−12)=−631152=−0.0546875L_0(10) = \frac{(10 - 7)(10 - 11)(10 - 13)(10 - 17)}{(5 - 7)(5 - 11)(5 - 13)(5 - 17)} = \frac{(3)(-1)(-3)(-7)}{(-2)(-6)(-8)(-12)} = \frac{-63}{1152} = -0.0546875 y0L0(10)=150×(−0.0546875)=−8.203125y_0 L_0(10) = 150 \times (-0.0546875) = -8.203125

  • L1(10)L_1(10) for x1=7x_1 = 7: L1(10)=(10−5)(10−11)(10−13)(10−17)(7−5)(7−11)(7−13)(7−17)=(5)(−1)(−3)(−7)(2)(−4)(−6)(−10)=−105−480=+0.21875L_1(10) = \frac{(10 - 5)(10 - 11)(10 - 13)(10 - 17)}{(7 - 5)(7 - 11)(7 - 13)(7 - 17)} = \frac{(5)(-1)(-3)(-7)}{(2)(-4)(-6)(-10)} = \frac{-105}{-480} = +0.21875 y1L1(10)=392×0.21875=+85.750000y_1 L_1(10) = 392 \times 0.21875 = +85.750000

  • L2(10)L_2(10) for x2=11x_2 = 11: L2(10)=(10−5)(10−7)(10−13)(10−17)(11−5)(11−7)(11−13)(11−17)=(5)(3)(−3)(−7)(6)(4)(−2)(−6)=315288=+1.09375L_2(10) = \frac{(10 - 5)(10 - 7)(10 - 13)(10 - 17)}{(11 - 5)(11 - 7)(11 - 13)(11 - 17)} = \frac{(5)(3)(-3)(-7)}{(6)(4)(-2)(-6)} = \frac{315}{288} = +1.09375 y2L2(10)=1452×1.09375=+1588.125000y_2 L_2(10) = 1452 \times 1.09375 = +1588.125000

  • L3(10)L_3(10) for x3=13x_3 = 13: L3(10)=(10−5)(10−7)(10−11)(10−17)(13−5)(13−7)(13−11)(13−17)=(5)(3)(−1)(−7)(8)(6)(2)(−4)=105−384=−0.2734375L_3(10) = \frac{(10 - 5)(10 - 7)(10 - 11)(10 - 17)}{(13 - 5)(13 - 7)(13 - 11)(13 - 17)} = \frac{(5)(3)(-1)(-7)}{(8)(6)(2)(-4)} = \frac{105}{-384} = -0.2734375 y3L3(10)=2366×(−0.2734375)=−646.953125y_3 L_3(10) = 2366 \times (-0.2734375) = -646.953125

  • L4(10)L_4(10) for x4=17x_4 = 17: L4(10)=(10−5)(10−7)(10−11)(10−13)(17−5)(17−7)(17−11)(17−13)=(5)(3)(−1)(−3)(12)(10)(6)(4)=452880=+0.015625L_4(10) = \frac{(10 - 5)(10 - 7)(10 - 11)(10 - 13)}{(17 - 5)(17 - 7)(17 - 11)(17 - 13)} = \frac{(5)(3)(-1)(-3)}{(12)(10)(6)(4)} = \frac{45}{2880} = +0.015625 y4L4(10)=5202×0.015625=+81.281250y_4 L_4(10) = 5202 \times 0.015625 = +81.281250

Summing the exact contributions: f(10)=−8.203125+85.75+1588.125−646.953125+81.28125=1100f(10) = -8.203125 + 85.75 + 1588.125 - 646.953125 + 81.28125 = 1100

Course Slide Arithmetic Note

In the course lecture notes, the author made handwritten arithmetic slips in the denominators (e.g., miscomputing (−2)(−6)(−8)(−12)(-2)(-6)(-8)(-12) as −32-32 instead of 11521152, yielding −98.4375-98.4375, −428.75-428.75, 1058.751058.75, −647.03125-647.03125, 81.2812581.28125), which led to the printed value of −34.1875-34.1875. Both the exact mathematical value (11001100) and the slide artifact value (−34.1875-34.1875) are recorded here for complete transparency.

2. Exact Analytic Evaluation at x=9x = 9

The underlying generator polynomial for the data points is: f(x)=x3+x2=x2(x+1)f(x) = x^3 + x^2 = x^2(x + 1)

Evaluating via Lagrange interpolation at x=9x = 9 (as originally posed on Slide 8):

  • L0(9)=(9−7)(9−11)(9−13)(9−17)(5−7)(5−11)(5−13)(5−17)=−1281152=−19  ⟹  y0L0(9)=150×(−19)=−16.6667L_0(9) = \frac{(9-7)(9-11)(9-13)(9-17)}{(5-7)(5-11)(5-13)(5-17)} = \frac{-128}{1152} = -\frac{1}{9} \implies y_0 L_0(9) = 150 \times \left(-\frac{1}{9}\right) = -16.6667
  • L1(9)=(9−5)(9−11)(9−13)(9−17)(7−5)(7−11)(7−13)(7−17)=−256−480=815  ⟹  y1L1(9)=392×815=+209.0667L_1(9) = \frac{(9-5)(9-11)(9-13)(9-17)}{(7-5)(7-11)(7-13)(7-17)} = \frac{-256}{-480} = \frac{8}{15} \implies y_1 L_1(9) = 392 \times \frac{8}{15} = +209.0667
  • L2(9)=(9−5)(9−7)(9−13)(9−17)(11−5)(11−7)(11−13)(11−17)=256288=89  ⟹  y2L2(9)=1452×89=+1290.6667L_2(9) = \frac{(9-5)(9-7)(9-13)(9-17)}{(11-5)(11-7)(11-13)(11-17)} = \frac{256}{288} = \frac{8}{9} \implies y_2 L_2(9) = 1452 \times \frac{8}{9} = +1290.6667
  • L3(9)=(9−5)(9−7)(9−11)(9−17)(13−5)(13−7)(13−11)(13−17)=128−384=−13  ⟹  y3L3(9)=2366×(−13)=−788.6667L_3(9) = \frac{(9-5)(9-7)(9-11)(9-17)}{(13-5)(13-7)(13-11)(13-17)} = \frac{128}{-384} = -\frac{1}{3} \implies y_3 L_3(9) = 2366 \times \left(-\frac{1}{3}\right) = -788.6667
  • L4(9)=(9−5)(9−7)(9−11)(9−13)(17−5)(17−7)(17−11)(17−13)=642880=145  ⟹  y4L4(9)=5202×145=+115.6000L_4(9) = \frac{(9-5)(9-7)(9-11)(9-13)}{(17-5)(17-7)(17-11)(17-13)} = \frac{64}{2880} = \frac{1}{45} \implies y_4 L_4(9) = 5202 \times \frac{1}{45} = +115.6000

Summing all contributions: f(9)=−16.6667+209.0667+1290.6667−788.6667+115.6000=810f(9) = -16.6667 + 209.0667 + 1290.6667 - 788.6667 + 115.6000 = 810 f(9)=93+92=729+81=810■f(9) = 9^3 + 9^2 = 729 + 81 = 810 \quad \blacksquare

% 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
end

4. Central Difference Interpolation Methods

Solution 4.1: Gauss's Forward Central Difference Formula

1. Derivation via Operator Identities

Let the origin be x0x_0, step size hh, and normalized parameter p=x−x0hp = \frac{x - x_0}{h}. The shift operator gives: yp=Epy0=(1+Δ)py0=[1+p Δ+p(p−1)2! Δ2+p(p−1)(p−2)3! Δ3+⋯ ]y0y_p = E^p y_0 = (1 + \Delta)^p y_0 = \left[ 1 + p\,\Delta + \frac{p(p-1)}{2!}\,\Delta^2 + \frac{p(p-1)(p-2)}{3!}\,\Delta^3 + \cdots \right] y_0

To centralize around y0y_0, relate higher-order forward differences to negative indices using Δky0=ΔkEy−1=Δk(1+Δ)y−1=Δky−1+Δk+1y−1\Delta^k y_0 = \Delta^k E y_{-1} = \Delta^k (1 + \Delta) y_{-1} = \Delta^k y_{-1} + \Delta^{k+1} y_{-1}:

  • Δ2y0=Δ2y−1+Δ3y−1\Delta^2 y_0 = \Delta^2 y_{-1} + \Delta^3 y_{-1}
  • Δ3y0=Δ3y−1+Δ4y−1\Delta^3 y_0 = \Delta^3 y_{-1} + \Delta^4 y_{-1}

Grouping terms with common central difference coefficients yields Gauss's Forward Formula: yp=y0+p Δy0+p(p−1)2! Δ2y−1+(p+1)p(p−1)3! Δ3y−1+(p+1)p(p−1)(p−2)4! Δ4y−2+⋯y_p = y_0 + p\,\Delta y_0 + \frac{p(p-1)}{2!}\,\Delta^2 y_{-1} + \frac{(p+1)p(p-1)}{3!}\,\Delta^3 y_{-1} + \frac{(p+1)p(p-1)(p-2)}{4!}\,\Delta^4 y_{-2} + \cdots

2. Numerical Problem: f(3.6)f(3.6)

Data:

  • x=[2.5,3.0,3.5,4.0,4.5]x = [2.5, 3.0, 3.5, 4.0, 4.5], step h=0.5h = 0.5
  • y=[24.145,22.043,20.225,18.644,17.644]y = [24.145, 22.043, 20.225, 18.644, 17.644]

Choose central origin x0=3.5x_0 = 3.5: p=3.6−3.50.5=0.10.5=0.2p = \frac{3.6 - 3.5}{0.5} = \frac{0.1}{0.5} = 0.2

Central Difference Table:

xxyyΔy\Delta yΔ2y\Delta^2 yΔ3y\Delta^3 yΔ4y\Delta^4 y
2.52.524.14524.145
3.03.022.04322.043−2.102-2.1020.2840.284
3.53.5 (x0x_0)20.22520.225 (y0y_0)−1.818-1.8180.2370.237 (Δ2y−1\Delta^2 y_{-1})−0.047-0.0470.3910.391 (Δ4y−2\Delta^4 y_{-2})
4.04.018.64418.644−1.581-1.581 (Δy0\Delta y_0)0.5810.5810.3440.344 (Δ3y−1\Delta^3 y_{-1})
4.54.517.64417.644−1.000-1.000

Selected coefficients:

  • y0=20.225y_0 = 20.225
  • Δy0=−1.581\Delta y_0 = -1.581
  • Δ2y−1=0.237\Delta^2 y_{-1} = 0.237
  • Δ3y−1=0.344\Delta^3 y_{-1} = 0.344
  • Δ4y−2=0.391\Delta^4 y_{-2} = 0.391

Compute terms for p=0.2p = 0.2:

  1. y0=20.225y_0 = 20.225
  2. p Δy0=0.2×(−1.581)=−0.3162p\,\Delta y_0 = 0.2 \times (-1.581) = -0.3162
  3. 0.2(0.2−1)2(0.237)=−0.162(0.237)=−0.01896\frac{0.2(0.2 - 1)}{2}(0.237) = \frac{-0.16}{2}(0.237) = -0.01896
  4. (1+0.2)(0.2)(0.2−1)6(0.344)=1.2×0.2×(−0.8)6(0.344)=−0.011008\frac{(1 + 0.2)(0.2)(0.2 - 1)}{6}(0.344) = \frac{1.2 \times 0.2 \times (-0.8)}{6}(0.344) = -0.011008
  5. (1.2)(0.2)(−0.8)(−1.8)24(0.391)=0.345624(0.391)=+0.0056304\frac{(1.2)(0.2)(-0.8)(-1.8)}{24}(0.391) = \frac{0.3456}{24}(0.391) = +0.0056304

Summing all terms: f(3.6)=20.225−0.3162−0.01896−0.011008+0.0056304=19.8844624f(3.6) = 20.225 - 0.3162 - 0.01896 - 0.011008 + 0.0056304 = 19.8844624


Solution 4.2: Gauss's Backward Central Difference Formula

1. Formula

yp=y0+p Δy−1+(p+1)p2! Δ2y−1+(p+1)p(p−1)3! Δ3y−2+(p+2)(p+1)p(p−1)4! Δ4y−2+⋯y_p = y_0 + p\,\Delta y_{-1} + \frac{(p+1)p}{2!}\,\Delta^2 y_{-1} + \frac{(p+1)p(p-1)}{3!}\,\Delta^3 y_{-2} + \frac{(p+2)(p+1)p(p-1)}{4!}\,\Delta^4 y_{-2} + \cdots

2. Population in 19361936

Data:

  • x=[1901,1911,1921,1931,1941,1951]x = [1901, 1911, 1921, 1931, 1941, 1951], h=10h = 10
  • y=[12,15,20,27,39,52]y = [12, 15, 20, 27, 39, 52] (thousands)

Choose x0=1931x_0 = 1931: p=1936−193110=0.5p = \frac{1936 - 1931}{10} = 0.5

Difference Table:

YearPopΔ\DeltaΔ2\Delta^2Δ3\Delta^3Δ4\Delta^4Δ5\Delta^5
190119011212
1911191115153322
192119212020552200−7-7−10-10
19311931 (x0x_0)2727 (y0y_0)77 (Δy−1\Delta y_{-1})55 (Δ2y−1\Delta^2 y_{-1})33 (Δ3y−2\Delta^3 y_{-2})−7-7 (Δ4y−2\Delta^4 y_{-2})
194119413939121211−4-4
1951195152521313

Selected terms:

  • y0=27y_0 = 27
  • Δy−1=7\Delta y_{-1} = 7
  • Δ2y−1=5\Delta^2 y_{-1} = 5
  • Δ3y−2=3\Delta^3 y_{-2} = 3
  • Δ4y−2=−7\Delta^4 y_{-2} = -7
  • Δ5y−3=−10\Delta^5 y_{-3} = -10

Evaluation: y(1936)=27+0.5(7)+(1.5)(0.5)2(5)+(1.5)(0.5)(−0.5)6(3)+(2.5)(1.5)(0.5)(−0.5)24(−7)+(2.5)(1.5)(0.5)(−0.5)(−1.5)120(−10)y(1936) = 27 + 0.5(7) + \frac{(1.5)(0.5)}{2}(5) + \frac{(1.5)(0.5)(-0.5)}{6}(3) + \frac{(2.5)(1.5)(0.5)(-0.5)}{24}(-7) + \frac{(2.5)(1.5)(0.5)(-0.5)(-1.5)}{120}(-10) y(1936)=27+3.5+1.875−0.1875+0.2734375−0.1171875=32.3437 thousand≈32,344 peopley(1936) = 27 + 3.5 + 1.875 - 0.1875 + 0.2734375 - 0.1171875 = 32.3437 \text{ thousand} \approx 32,344 \text{ people}


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: yp=y0+p[Δy0+Δy−12]+p22! Δ2y−1+p(p2−1)3![Δ3y−1+Δ3y−22]+p2(p2−1)4! Δ4y−2+⋯y_p = y_0 + p\left[\frac{\Delta y_0 + \Delta y_{-1}}{2}\right] + \frac{p^2}{2!}\,\Delta^2 y_{-1} + \frac{p(p^2 - 1)}{3!}\left[\frac{\Delta^3 y_{-1} + \Delta^3 y_{-2}}{2}\right] + \frac{p^2(p^2 - 1)}{4!}\,\Delta^4 y_{-2} + \cdots

2. Evaluation of f(35)f(35)

Data: f(20)=512,f(30)=439,f(40)=346,f(50)=243f(20) = 512, f(30) = 439, f(40) = 346, f(50) = 243.

  • x0=30,h=10,x=35  ⟹  p=35−3010=0.5x_0 = 30, h = 10, x = 35 \implies p = \frac{35 - 30}{10} = 0.5

Difference Table:

  • yy: 512,439,346,243512, 439, 346, 243
  • Δy\Delta y: −73,−93,−103-73, -93, -103 (Δy−1=−73,Δy0=−93\Delta y_{-1} = -73, \Delta y_0 = -93)
  • Δ2y\Delta^2 y: −20,−10-20, -10 (Δ2y−1=−20\Delta^2 y_{-1} = -20)
  • Δ3y\Delta^3 y: 1010 (Δ3y−1=10\Delta^3 y_{-1} = 10)

Substitute into Stirling's formula: y(35)=439+0.5[−73+(−93)2]+0.522(−20)+0.5(0.52−1)6(10)y(35) = 439 + 0.5\left[\frac{-73 + (-93)}{2}\right] + \frac{0.5^2}{2}(-20) + \frac{0.5(0.5^2 - 1)}{6}(10) y(35)=439+0.5(−83)+0.252(−20)+0.5(−0.75)6(10)y(35) = 439 + 0.5(-83) + \frac{0.25}{2}(-20) + \frac{0.5(-0.75)}{6}(10) y(35)=439−41.5−2.5−0.625=394.375≈395y(35) = 439 - 41.5 - 2.5 - 0.625 = 394.375 \approx 395


Solution 4.4: Bessel's Central Difference Formula

1. Formula

yp=[y0+y12]+(p−12)Δy0+p(p−1)2![Δ2y−1+Δ2y02]+(p−12)p(p−1)3!Δ3y−1+⋯y_p = \left[\frac{y_0 + y_1}{2}\right] + \left(p - \frac{1}{2}\right)\Delta y_0 + \frac{p(p-1)}{2!}\left[\frac{\Delta^2 y_{-1} + \Delta^2 y_0}{2}\right] + \frac{\left(p - \frac{1}{2}\right)p(p-1)}{3!}\Delta^3 y_{-1} + \cdots Bessel's formula is symmetric about x=x0+12hx = x_0 + \frac{1}{2}h, making it ideal for the range 0.25≤p≤0.750.25 \le p \le 0.75.

2. Temperature θ(4.3)\theta(4.3)

Data: t=[2,3,4,5,6]t = [2, 3, 4, 5, 6], θ=[61.87,54.08,47.03,40.65,34.88]\theta = [61.87, 54.08, 47.03, 40.65, 34.88], h=1h = 1.

  • Choose t0=4  ⟹  p=4.3−41=0.3t_0 = 4 \implies p = \frac{4.3 - 4}{1} = 0.3.

Differences:

  • Δy\Delta y: −7.79,−7.05,−6.38,−5.77  ⟹  Δy0=−6.38-7.79, -7.05, -6.38, -5.77 \implies \Delta y_0 = -6.38
  • Δ2y\Delta^2 y: 0.74,0.67,0.61  ⟹  Δ2y−1=0.67,Δ2y0=0.610.74, 0.67, 0.61 \implies \Delta^2 y_{-1} = 0.67, \Delta^2 y_0 = 0.61
  • Δ3y\Delta^3 y: −0.07,−0.06  ⟹  Δ3y−1=−0.06-0.07, -0.06 \implies \Delta^3 y_{-1} = -0.06

Computation: θ(4.3)=47.03+0.3(−6.38)+0.3(0.3−1)2[0.67+0.612]+(0.3−0.5)(0.3)(0.3−1)6(−0.06)\theta(4.3) = 47.03 + 0.3(-6.38) + \frac{0.3(0.3 - 1)}{2}\left[\frac{0.67 + 0.61}{2}\right] + \frac{(0.3 - 0.5)(0.3)(0.3 - 1)}{6}(-0.06) θ(4.3)=47.03−1.914+−0.212(0.64)+(−0.2)(0.3)(−0.7)6(−0.06)\theta(4.3) = 47.03 - 1.914 + \frac{-0.21}{2}(0.64) + \frac{(-0.2)(0.3)(-0.7)}{6}(-0.06) θ(4.3)=47.03−1.914−0.0672−0.00042=45.04838∘C≈45.05∘C\theta(4.3) = 47.03 - 1.914 - 0.0672 - 0.00042 = 45.04838^\circ\text{C} \approx 45.05^\circ\text{C}


5. Numerical Quadrature: Trapezoidal & Simpson's Rules

Solution 5.1: Composite Trapezoidal Rule

1. Formula & Step Size

Dividing [a,b][a, b] into nn equal subintervals with h=b−anh = \frac{b - a}{n} and xi=a+ihx_i = a + i h: ∫abf(x) dx≈Tn=h2[f(x0)+2∑i=1n−1f(xi)+f(xn)]\int_a^b f(x)\,dx \approx T_n = \frac{h}{2}\left[ f(x_0) + 2\sum_{i=1}^{n-1} f(x_i) + f(x_n) \right]

2. Evaluation of ∫121x dx\int_1^2 \frac{1}{x}\,dx with n=10n = 10

  • a=1,b=2,n=10  ⟹  h=2−110=0.1a = 1, b = 2, n = 10 \implies h = \frac{2 - 1}{10} = 0.1

Grid coordinates and ordinates:

iixix_if(xi)=1xif(x_i) = \frac{1}{x_i}
001.01.01.00001.0000
111.11.10.90910.9091
221.21.20.83330.8333
331.31.30.76920.7692
441.41.40.71430.7143
551.51.50.66670.6667
661.61.60.62500.6250
771.71.70.58820.5882
881.81.80.55560.5556
991.91.90.52630.5263
10102.02.00.50000.5000

Sum of intermediate terms ∑i=19f(xi)\sum_{i=1}^9 f(x_i): ∑i=19f(xi)=0.9091+0.8333+0.7692+0.7143+0.6667+0.6250+0.5882+0.5556+0.5263=6.1877\sum_{i=1}^9 f(x_i) = 0.9091 + 0.8333 + 0.7692 + 0.7143 + 0.6667 + 0.6250 + 0.5882 + 0.5556 + 0.5263 = 6.1877

Substitute into formula: T10=0.12[1.0000+2(6.1877)+0.5000]=0.05[1.5000+12.3754]=0.05×13.8754=0.69377T_{10} = \frac{0.1}{2}\left[ 1.0000 + 2(6.1877) + 0.5000 \right] = 0.05 \left[ 1.5000 + 12.3754 \right] = 0.05 \times 13.8754 = 0.69377

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 0.05×(1.5+2×6.1877)=0.693770.05 \times (1.5 + 2 \times 6.1877) = 0.69377.

Analytical exact value: ∫121x dx=ln⁡(2)≈0.693147\int_1^2 \frac{1}{x}\,dx = \ln(2) \approx 0.693147 Absolute Error: ∣0.69377−0.69315∣=0.00062|0.69377 - 0.69315| = 0.00062.


Solution 5.2: Simpson's 1/3 Rule

1. Formula & Interval Constraint

S1/3=h3[y0+yn+4∑i oddyi+2∑i evenyi]S_{1/3} = \frac{h}{3}\left[ y_0 + y_n + 4\sum_{i \text{ odd}} y_i + 2\sum_{i \text{ even}} y_i \right] Constraint: nn must be an even number (n=2mn = 2m) because each parabola is fitted across a pair of adjacent intervals ([x2k−2,x2k][x_{2k-2}, x_{2k}]).

2. Evaluation of ∫0121+x3 dx\int_0^1 \frac{2}{1 + x^3}\,dx with n=6n = 6

  • a=0,b=1,n=6  ⟹  h=1−06=16a = 0, b = 1, n = 6 \implies h = \frac{1 - 0}{6} = \frac{1}{6}

Grid ordinates:

  • y0=f(0)=21+0=2.0000y_0 = f(0) = \frac{2}{1 + 0} = 2.0000
  • y1=f(1/6)=21+(1/6)3=21+1/216=432217≈1.9908y_1 = f(1/6) = \frac{2}{1 + (1/6)^3} = \frac{2}{1 + 1/216} = \frac{432}{217} \approx 1.9908
  • y2=f(2/6)=21+(1/3)3=21+1/27=5428≈1.9286y_2 = f(2/6) = \frac{2}{1 + (1/3)^3} = \frac{2}{1 + 1/27} = \frac{54}{28} \approx 1.9286
  • y3=f(3/6)=21+(1/2)3=21+1/8=169≈1.7778y_3 = f(3/6) = \frac{2}{1 + (1/2)^3} = \frac{2}{1 + 1/8} = \frac{16}{9} \approx 1.7778
  • y4=f(4/6)=21+(2/3)3=21+8/27=5435≈1.5432y_4 = f(4/6) = \frac{2}{1 + (2/3)^3} = \frac{2}{1 + 8/27} = \frac{54}{35} \approx 1.5432
  • y5=f(5/6)=21+(5/6)3=21+125/216=432341≈1.2618y_5 = f(5/6) = \frac{2}{1 + (5/6)^3} = \frac{2}{1 + 125/216} = \frac{432}{341} \approx 1.2618
  • y6=f(1)=21+13=1.0000y_6 = f(1) = \frac{2}{1 + 1^3} = 1.0000

Grouping terms:

  • Endpoints: y0+y6=2.0000+1.0000=3.0000y_0 + y_6 = 2.0000 + 1.0000 = 3.0000
  • Odd indices (i∈{1,3,5}i \in \{1, 3, 5\}): 1.9908+1.7778+1.2618=5.0304  ⟹  4×5.0304=20.12161.9908 + 1.7778 + 1.2618 = 5.0304 \implies 4 \times 5.0304 = 20.1216
  • Even indices (i∈{2,4}i \in \{2, 4\}): 1.9286+1.5432=3.4718  ⟹  2×3.4718=6.94361.9286 + 1.5432 = 3.4718 \implies 2 \times 3.4718 = 6.9436

Substitute into formula: S1/3=1/63[3.0000+20.1216+6.9436]=118[30.0652]≈1.6703S_{1/3} = \frac{1/6}{3}\left[ 3.0000 + 20.1216 + 6.9436 \right] = \frac{1}{18} [30.0652] \approx 1.6703


Solution 5.3: Simpson's 3/8 Rule

1. Formula & Constraint

S3/8=3h8[y0+yn+3∑i≠3kyi+2∑i=3kyi]S_{3/8} = \frac{3h}{8}\left[ y_0 + y_n + 3\sum_{i \ne 3k} y_i + 2\sum_{i = 3k} y_i \right] Constraint: nn must be a multiple of 3 (n=3mn = 3m) because cubic polynomials are fitted over sets of three subintervals.

2. Numerical Computation for n=6n = 6

Using the identical coordinates and values from Solution 5.2:

  • Endpoints: y0+y6=2.0000+1.0000=3.0000y_0 + y_6 = 2.0000 + 1.0000 = 3.0000
  • Multipliers of 3: Indices i∈{1,2,4,5}i \in \{1, 2, 4, 5\}: y1+y2+y4+y5=1.9908+1.9286+1.5432+1.2618=6.7244y_1 + y_2 + y_4 + y_5 = 1.9908 + 1.9286 + 1.5432 + 1.2618 = 6.7244 3×6.7244=20.17323 \times 6.7244 = 20.1732
  • Multipliers of 2: Index i=3i = 3: 2×y3=2×1.7778=3.55562 \times y_3 = 2 \times 1.7778 = 3.5556

Substitute into Simpson's 3/8 formula: S3/8=3(1/6)8[3.0000+20.1732+3.5556]=116[26.7288]≈1.6706S_{3/8} = \frac{3(1/6)}{8}\left[ 3.0000 + 20.1732 + 3.5556 \right] = \frac{1}{16} [26.7288] \approx 1.6706

Comparison: Simpson's 1/3 (1.67031.6703) and Simpson's 3/8 (1.67061.6706) 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

MethodPolynomial Degree (mm)Subinterval ConstraintLocal ErrorGlobal ErrorDegree of Exactness
Trapezoidal Rule11 (Linear)n≥1n \ge 1 (any positive integer)−h312f′′(ξ)-\frac{h^3}{12} f''(\xi)O(h2)\mathcal{O}(h^2)11
Simpson's 1/3 Rule22 (Quadratic)nn must be even (2∣n2 \mid n)−h590f(4)(ξ)-\frac{h^5}{90} f^{(4)}(\xi)O(h4)\mathcal{O}(h^4)33
Simpson's 3/8 Rule33 (Cubic)nn must be a multiple of 3 (3∣n3 \mid n)−3h580f(4)(ξ)-\frac{3h^5}{80} f^{(4)}(\xi)O(h4)\mathcal{O}(h^4)33
% 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
end

6. Systems of Linear Equations: Iterative Methods

Solution 6.1: Strictly Diagonally Dominant Systems

1. Definition

A matrix A∈Rn×nA \in \mathbb{R}^{n \times n} 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: ∣aii∣>∑j=1,j≠in∣aij∣∀i=1,2,…,n|a_{ii}| > \sum_{j=1, j \ne i}^n |a_{ij}| \quad \forall i = 1, 2, \dots, n

2. Convergence Guarantee

By the Levy-Desplanques theorem and spectral radius properties (ρ(M)<1\rho(M) < 1), strict diagonal dominance guarantees that the iteration matrices TJ=D−1(L+U)T_J = D^{-1}(L + U) and TGS=(D−L)−1UT_{GS} = (D - L)^{-1}U have spectral radii strictly bounded inside the unit disk (ρ<1\rho < 1). Thus, iterations are guaranteed to converge unconditionally for any initial guess x(0)\mathbf{x}^{(0)}.

3. Rearrangement of Given System

Initial system:

  1. 25=−4x1−2x2+11x325 = -4x_1 - 2x_2 + 11x_3
  2. −11=7x1−3x2−4x3-11 = 7x_1 - 3x_2 - 4x_3
  3. 3=−3x1+6x2−2x33 = -3x_1 + 6x_2 - 2x_3

Examine coefficients:

  • In Eq 2: ∣7∣>∣−3∣+∣−4∣  ⟹  7>7|7| > |-3| + |-4| \implies 7 > 7 (Boundary / dominant for x1x_1).
  • In Eq 3: ∣6∣>∣−3∣+∣−2∣  ⟹  6>5|6| > |-3| + |-2| \implies 6 > 5 (Strictly dominant for x2x_2).
  • In Eq 1: ∣11∣>∣−4∣+∣−2∣  ⟹  11>6|11| > |-4| + |-2| \implies 11 > 6 (Strictly dominant for x3x_3).

Rearranged diagonally dominant system:

Eq 1:7x1−3x2−4x3=−11Eq 2:−3x1+6x2−2x3=3Eq 3:−4x1−2x2+11x3=25\begin{aligned} \text{Eq 1:} \quad 7x_1 - 3x_2 - 4x_3 &= -11 \\ \text{Eq 2:} \quad -3x_1 + 6x_2 - 2x_3 &= 3 \\ \text{Eq 3:} \quad -4x_1 - 2x_2 + 11x_3 &= 25 \end{aligned}

Solution 6.2: Gauss-Jacobi Method Iterative Solution

1. Iterative Formulas

Isolating each diagonal variable: x1(k+1)=−11+3x2(k)+4x3(k)7x_1^{(k+1)} = \frac{-11 + 3x_2^{(k)} + 4x_3^{(k)}}{7} x2(k+1)=3+3x1(k)+2x3(k)6x_2^{(k+1)} = \frac{3 + 3x_1^{(k)} + 2x_3^{(k)}}{6} x3(k+1)=25+4x1(k)+2x2(k)11x_3^{(k+1)} = \frac{25 + 4x_1^{(k)} + 2x_2^{(k)}}{11}

2. Step-by-Step Iterations from x(0)=[0,0,0]T\mathbf{x}^{(0)} = [0, 0, 0]^T

  • Iteration k=1k = 1: x1(1)=−11+0+07=−117≈−1.5714x_1^{(1)} = \frac{-11 + 0 + 0}{7} = -\frac{11}{7} \approx -1.5714 x2(1)=3+0+06=36=0.5000x_2^{(1)} = \frac{3 + 0 + 0}{6} = \frac{3}{6} = 0.5000 x3(1)=25+0+011=2511≈2.2727x_3^{(1)} = \frac{25 + 0 + 0}{11} = \frac{25}{11} \approx 2.2727

  • Iteration k=2k = 2: x1(2)=−11+3(0.5000)+4(2.2727)7=−11+1.5+9.09087=−0.40927≈−0.0585x_1^{(2)} = \frac{-11 + 3(0.5000) + 4(2.2727)}{7} = \frac{-11 + 1.5 + 9.0908}{7} = \frac{-0.4092}{7} \approx -0.0585 x2(2)=3+3(−1.5714)+2(2.2727)6=3−4.7142+4.54546=2.83126≈0.4719x_2^{(2)} = \frac{3 + 3(-1.5714) + 2(2.2727)}{6} = \frac{3 - 4.7142 + 4.5454}{6} = \frac{2.8312}{6} \approx 0.4719 x3(2)=25+4(−1.5714)+2(0.5000)11=25−6.2856+1.000011=19.714411≈1.7922x_3^{(2)} = \frac{25 + 4(-1.5714) + 2(0.5000)}{11} = \frac{25 - 6.2856 + 1.0000}{11} = \frac{19.7144}{11} \approx 1.7922

  • Iteration k=3k = 3: x1(3)=−11+3(0.4719)+4(1.7922)7=−11+1.4157+7.16887≈−0.3451x_1^{(3)} = \frac{-11 + 3(0.4719) + 4(1.7922)}{7} = \frac{-11 + 1.4157 + 7.1688}{7} \approx -0.3451 x2(3)=3+3(−0.0585)+2(1.7922)6=3−0.1755+3.58446≈1.0682x_2^{(3)} = \frac{3 + 3(-0.0585) + 2(1.7922)}{6} = \frac{3 - 0.1755 + 3.5844}{6} \approx 1.0682 x3(3)=25+4(−0.0585)+2(0.4719)11=25−0.2340+0.943811≈2.3373x_3^{(3)} = \frac{25 + 4(-0.0585) + 2(0.4719)}{11} = \frac{25 - 0.2340 + 0.9438}{11} \approx 2.3373

3. Summary Table (Iter 0 to 10)

kkx1(k)x_1^{(k)}x2(k)x_2^{(k)}x3(k)x_3^{(k)}
000.00000.00000.00000.00000.00000.0000
11−1.5714-1.57140.50000.50002.27272.2727
22−0.0585-0.05850.47190.47191.79221.7922
33−0.3451-0.34511.06821.06822.33732.3373
440.22200.22201.10661.10662.34152.3415
550.24080.24081.39151.39152.55472.5547
660.48480.48481.47201.47202.61332.6133
770.55270.55271.61351.61352.71672.7167
880.67250.67251.68191.68192.76712.7671
990.73060.73061.75861.75862.82312.8231
10100.79550.79551.80631.80632.85812.8581

(Exact analytical limit: x1=1.0000,x2=2.0000,x3=3.0000x_1 = 1.0000, x_2 = 2.0000, x_3 = 3.0000)


Solution 6.3: Gauss-Seidel Method Iterative Solution

1. In-Place Iterative Update Formulas

In Gauss-Seidel, as soon as a new coordinate value xi(k+1)x_i^{(k+1)} is calculated, it is immediately substituted into subsequent formulas within the same iteration: x1(k+1)=−11+3x2(k)+4x3(k)7x_1^{(k+1)} = \frac{-11 + 3x_2^{(k)} + 4x_3^{(k)}}{7} x2(k+1)=3+3x1(k+1)+2x3(k)6x_2^{(k+1)} = \frac{3 + 3x_1^{(k+1)} + 2x_3^{(k)}}{6} x3(k+1)=25+4x1(k+1)+2x2(k+1)11x_3^{(k+1)} = \frac{25 + 4x_1^{(k+1)} + 2x_2^{(k+1)}}{11}

2. Step-by-Step Iterations from x(0)=[0,0,0]T\mathbf{x}^{(0)} = [0, 0, 0]^T

  • Iteration k=1k = 1: x1(1)=−11+3(0)+4(0)7=−117≈−1.5714x_1^{(1)} = \frac{-11 + 3(0) + 4(0)}{7} = -\frac{11}{7} \approx -1.5714 x2(1)=3+3(−1.5714)+2(0)6=3−4.71426=−1.71426≈−0.2857x_2^{(1)} = \frac{3 + 3(-1.5714) + 2(0)}{6} = \frac{3 - 4.7142}{6} = \frac{-1.7142}{6} \approx -0.2857 x3(1)=25+4(−1.5714)+2(−0.2857)11=25−6.2856−0.571411=18.14311≈1.6494x_3^{(1)} = \frac{25 + 4(-1.5714) + 2(-0.2857)}{11} = \frac{25 - 6.2856 - 0.5714}{11} = \frac{18.143}{11} \approx 1.6494

  • Iteration k=2k = 2: x1(2)=−11+3(−0.2857)+4(1.6494)7=−11−0.8571+6.59767=−5.25957≈−0.7514x_1^{(2)} = \frac{-11 + 3(-0.2857) + 4(1.6494)}{7} = \frac{-11 - 0.8571 + 6.5976}{7} = \frac{-5.2595}{7} \approx -0.7514 x2(2)=3+3(−0.7514)+2(1.6494)6=3−2.2542+3.29886=4.04466≈0.6741x_2^{(2)} = \frac{3 + 3(-0.7514) + 2(1.6494)}{6} = \frac{3 - 2.2542 + 3.2988}{6} = \frac{4.0446}{6} \approx 0.6741 x3(2)=25+4(−0.7514)+2(0.6741)11=25−3.0056+1.348211=23.342611≈2.1221x_3^{(2)} = \frac{25 + 4(-0.7514) + 2(0.6741)}{11} = \frac{25 - 3.0056 + 1.3482}{11} = \frac{23.3426}{11} \approx 2.1221

3. Complete Gauss-Seidel Iteration Table

kkx1(k)x_1^{(k)}x2(k)x_2^{(k)}x3(k)x_3^{(k)}
11−1.5714-1.5714−0.2857-0.28571.64941.6494
22−0.7514-0.75140.67410.67412.12212.1221
33−0.0699-0.06991.17241.17242.46052.4605
440.33700.33701.48871.48872.66592.6659
550.59000.59001.68361.68362.79342.7934
660.74630.74631.80431.80432.87222.8722

At iteration k=6k=6, the solution converges rapidly toward the exact system root [1,2,3]T[1, 2, 3]^T.

% 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;
end

Solution 6.4: Comparison: Gauss-Jacobi vs. Gauss-Seidel

  1. Convergence Speed: Gauss-Seidel incorporates updated state vectors immediately, generally converging approximately twice as fast as Gauss-Jacobi (ρ(TGS)≈ρ(TJ)2\rho(T_{GS}) \approx \rho(T_J)^2).
  2. Memory Footprint:
    • Gauss-Jacobi requires two separate vectors in memory (x(k)\mathbf{x}^{(k)} and x(k+1)\mathbf{x}^{(k+1)}) because updates cannot overwrite values needed by other equations.
    • Gauss-Seidel operates in-place with a single memory vector, halving the state storage requirement.
  3. Parallel Architecture Suitability:
    • Gauss-Jacobi is highly parallelizable across GPUs and multi-threaded clusters since every coordinate update xi(k+1)x_i^{(k+1)} is completely independent of other updates at step k+1k+1.
    • Gauss-Seidel possesses inherently sequential data dependencies (x2x_2 depends on x1x_1, x3x_3 on x2x_2), requiring specialized graph coloring or wavefront algorithms for parallelization.

On this page

1. Newton's Forward Difference InterpolationSolution 1.1: Concept of Interpolation and Extrapolation1. Definitions2. Condition for Observation Sequence3. Forward Difference Operator Δ\DeltaSolution 1.2: Difference Operator Identities and Difference Tables1. Algebraic Proof: Δ2y2=y4−2y3+y2\Delta^2 y_2 = y_4 - 2y_3 + y_22. Symbolic Forward Difference Table3. Numerical Forward Difference TableSolution 1.3: Newton's Forward Interpolation Numerical Evaluation1. Formula Definition2. Numerical Calculation of y(21)y(21)Solution 1.4: Polynomial Reconstruction via Forward Differences1. Difference Table2. Parameters3. Analytic Polynomial DerivationSolution 1.5: Higher-Order Polynomial Reconstruction & Point Estimation1. Difference Table2. Degree Analysis3. Closed-Form Polynomial f(x)f(x)4. Estimation at (10,s)(10, s)Solution 1.6: Village Census Population Estimation1. Difference Table2. Parameter uu for x=1945x = 19453. Interpolation CalculationSolution 1.7: Trigonometric Table Interpolation1. Difference Table2. Evaluation of sin⁡(18∘)\sin(18^\circ)2. Newton's Backward Difference InterpolationSolution 2.1: Backward Difference Operator and Table Construction1. Definition and Operator Relationship2. Higher-Order Differences3. Symbolic Backward Difference TableSolution 2.2: Newton's Backward Interpolation FormulaSolution 2.3: Numerical Evaluation using Backward Differences1. Complete Backward Difference Table2. Terminal Differences and Normalized Parameter3. Step-by-Step Numerical Computation of f(42)f(42)Solution 2.4: Advantages, Disadvantages & Computer Science Applications1. Trade-Offs2. Computer Science Applications3. Lagrange Interpolation for Unequal IntervalsSolution 3.1: Derivation of the Lagrange Interpolation Formula1. Limitation of Newton Difference Formulas2. Formal Derivation3. Kronecker Delta PropertySolution 3.2: Lagrange Evaluation with Unequally Spaced Nodes1. Evaluation at x=10x = 102. Exact Analytic Evaluation at x=9x = 94. Central Difference Interpolation MethodsSolution 4.1: Gauss's Forward Central Difference Formula1. Derivation via Operator Identities2. Numerical Problem: f(3.6)f(3.6)Solution 4.2: Gauss's Backward Central Difference Formula1. Formula2. Population in 19361936Solution 4.3: Stirling's Central Difference Formula1. Derivation2. Evaluation of f(35)f(35)Solution 4.4: Bessel's Central Difference Formula1. Formula2. Temperature θ(4.3)\theta(4.3)5. Numerical Quadrature: Trapezoidal & Simpson's RulesSolution 5.1: Composite Trapezoidal Rule1. Formula & Step Size2. Evaluation of ∫121x dx\int_1^2 \frac{1}{x}\,dx with n=10n = 10Solution 5.2: Simpson's 1/3 Rule1. Formula & Interval Constraint2. Evaluation of ∫0121+x3 dx\int_0^1 \frac{2}{1 + x^3}\,dx with n=6n = 6Solution 5.3: Simpson's 3/8 Rule1. Formula & Constraint2. Numerical Computation for n=6n = 6Solution 5.4: Comparison of Newton-Cotes Quadrature Methods6. Systems of Linear Equations: Iterative MethodsSolution 6.1: Strictly Diagonally Dominant Systems1. Definition2. Convergence Guarantee3. Rearrangement of Given SystemSolution 6.2: Gauss-Jacobi Method Iterative Solution1. Iterative Formulas2. Step-by-Step Iterations from x(0)=[0,0,0]T\mathbf{x}^{(0)} = [0, 0, 0]^T3. Summary Table (Iter 0 to 10)Solution 6.3: Gauss-Seidel Method Iterative Solution1. In-Place Iterative Update Formulas2. Step-by-Step Iterations from x(0)=[0,0,0]T\mathbf{x}^{(0)} = [0, 0, 0]^T3. Complete Gauss-Seidel Iteration TableSolution 6.4: Comparison: Gauss-Jacobi vs. Gauss-Seidel