Solve the following linear system starting from (x₁, x₂, x₃) = (0, 0, 0) using Gauss-Seidel iteration with stopping criterion εs = 1%:
10x₁ + 2x₂ − x₃ = 27
−3x₁ − 6x₂ + 2x₃ = −61.5
x₁ + x₂ + 5x₃ = −21.5
✅ Target for Validation: Exact solution: x₁ = 0.5 | x₂ = 8.0 | x₃ = −6.0. Your iterated values should converge to these within 1%.
📋 Step-by-Step Excel Guide — P1_GaussSeidel
- Enter the coefficient matrix (rows 2–4, columns B–E):
B2=10 C2=2 D2=-1 E2=27
B3=-3 C3=-6 D3=2 E3=-61.5
B4=1 C4=1 D4=5 E4=-21.5
Label column A: A2="Eq.1", A3="Eq.2", A4="Eq.3".
- Build the Diagonal Dominance table (rows 7–10):
Row 7 headers: A7="Equation" B7="|aii|" C7="Σ|aij|(off-diag)" D7="Dominant?" E7="Excel Check"
Row 8 (Eq.1 — diagonal is B2=10):
B8 =ABS(B2)
C8 =ABS(C2)+ABS(D2)
D8 =IF(B8>C8,"YES","NO")
E8 =B8>C8
Row 9 (Eq.2 — diagonal is C3=−6):
B9 =ABS(C3)
C9 =ABS(B3)+ABS(D3)
D9 =IF(B9>C9,"YES","NO")
E9 =B9>C9
Row 10 (Eq.3 — diagonal is D4=5):
B10 =ABS(D4)
C10 =ABS(B4)+ABS(C4)
D10 =IF(B10>C10,"YES","NO")
E10 =B10>C10
- Set up iteration table headers (row 13):
A13="Iter" B13="x₁" C13="x₂" D13="x₃"
E13="|εa| x₁ (%)" F13="|εa| x₂ (%)" G13="|εa| x₃ (%)" H13="Converged?"
- Enter iteration 0 (initial guess) in row 14:
A14=0 B14=0 C14=0 D14=0
E14="—" F14="—" G14="—" H14="—"
- Enter Gauss-Seidel formulas for iteration 1 in row 15:
A15 =A14+1
B15 =(E2-C2*C14-D2*D14)/B2
→ Explanation: x₁ = (27 − 2·x₂_old + x₃_old) / 10
C14 and D14 are previous-iteration x₂ and x₃.
C15 =(E3-B3*B15-D3*D14)/C3
→ Explanation: x₂ = (−61.5 − (−3)·x₁_new − 2·x₃_old) / (−6)
Uses UPDATED x₁ (B15) — this is the Gauss-Seidel rule.
D14 is the still-unchanged x₃ from the previous iteration.
D15 =(E4-B4*B15-C4*C15)/D4
→ Explanation: x₃ = (−21.5 − x₁_new − x₂_new) / 5
Uses UPDATED x₁ (B15) and UPDATED x₂ (C15).
E15 =IF(B15=0,100,ABS((B15-B14)/B15)*100)
F15 =IF(C15=0,100,ABS((C15-C14)/C15)*100)
G15 =IF(D15=0,100,ABS((D15-D14)/D15)*100)
→ On iteration 1, old values are 0; error = 100% by convention.
The IF guard prevents division by zero when xnew itself equals 0.
H15 =IF(AND(E15<1,F15<1,G15<1),"YES ✓","No")
- Copy row 15 downward: Select A15:H15 and drag down until column H shows "YES ✓". The formulas automatically use the current row's updated values (Gauss-Seidel behavior) because they reference the cells in the SAME row for x₁ and x₂.
- Highlight convergence: Apply a green fill to the first row where H = "YES ✓" (use conditional formatting or fill manually).
▶ Diagonal Dominance: For each equation, the absolute value of the diagonal coefficient must be strictly greater than the sum of absolute values of all OTHER coefficients in that row. If true for all rows, convergence is guaranteed.
▶ Gauss-Seidel update rule: When computing x₂ in row 15, use B15 (just computed), NOT B14 (previous). When computing x₃, use both B15 and C15. This is what makes it Gauss-Seidel instead of Jacobi.
▶ Stopping criterion: Stop iterating (stop copying rows down) when ALL three error columns are below 1% simultaneously.
▶ Division by zero on iteration 1: If xnew = 0 (unlikely here but possible in other problems), the error formula would divide by zero. The =IF(B15=0,100,...) guard handles this gracefully by reporting 100%.
Required Table Layout — Diagonal Dominance Verification
| Equation | |aii| | Σ|aij| (off-diagonal) | Dominant? | Excel Check (TRUE/FALSE) |
|---|
| Eq. 1: 10x₁ + 2x₂ − x₃ = 27 | | | | |
| Eq. 2: −3x₁ − 6x₂ + 2x₃ = −61.5 | | | | |
| Eq. 3: x₁ + x₂ + 5x₃ = −21.5 | | | | |
Required Table Layout — Gauss-Seidel Iteration (extend rows until convergence)
| Iter | x₁ | x₂ | x₃ | |εa| x₁ (%) | |εa| x₂ (%) | |εa| x₃ (%) | Converged? |
|---|
| 0 | 0 | 0 | 0 | — | — | — | — |
| 1 | | | | | | | |
| 2 | | | | | | | |
| ⋯ | ⋯ | ⋯ | ⋯ | ⋯ | ⋯ | ⋯ | ⋯ |
Using the same system and initial guess as Problem 1, apply the Jacobi iteration method with εs = 1%.
✅ Target for Validation: Same exact solution: x₁ = 0.5 | x₂ = 8.0 | x₃ = −6.0. Jacobi requires more iterations than Gauss-Seidel to converge.
📋 Step-by-Step Excel Guide — P2_Jacobi
- Re-enter (or copy) the coefficient matrix in rows 2–4, columns B–E exactly as in P1_GaussSeidel. This keeps all formulas self-contained in this sheet.
- Set up table headers in row 7:
A7="Iter"
B7="x₁ (prev)" C7="x₂ (prev)" D7="x₃ (prev)"
E7="x₁ (new)" F7="x₂ (new)" G7="x₃ (new)"
H7="Max |εa| (%)"
- Enter iteration 0 (initial guess) in row 8:
A8=0 B8=0 C8=0 D8=0
E8="—" F8="—" G8="—" H8="—"
- Enter Jacobi formulas for iteration 1 in row 9:
A9 =A8+1
B9 =B8
C9 =C8
D9 =D8
→ "prev" values for iteration 1 are simply copied from the initial row.
For iteration 2 onward, these will reference the "new" column of the row above.
E9 =(E2-C2*C9-D2*D9)/B2
→ x₁_new = (27 − 2·x₂_prev + x₃_prev) / 10
Uses C9 (x₂ prev) and D9 (x₃ prev) — NOT C8 or D8.
This is the KEY difference from Gauss-Seidel.
F9 =(E3-B3*B9-D3*D9)/C3
→ x₂_new = (−61.5 − (−3)·x₁_prev − 2·x₃_prev) / (−6)
Uses B9 (x₁ prev), D9 (x₃ prev) — uses OLD x₁, not the just-computed E9.
G9 =(E4-B4*B9-C4*C9)/D4
→ x₃_new = (−21.5 − x₁_prev − x₂_prev) / 5
Uses B9 (x₁ prev) and C9 (x₂ prev) — all from the previous iteration.
H9 =MAX(
IF(E9=0,100,ABS((E9-B9)/E9)*100),
IF(F9=0,100,ABS((F9-C9)/F9)*100),
IF(G9=0,100,ABS((G9-D9)/G9)*100)
)
- Enter row 10 (iteration 2) — this is the template for all remaining rows:
A10 =A9+1
B10 =E9 ← x₁ prev = x₁ new from previous iteration
C10 =F9 ← x₂ prev = x₂ new from previous iteration
D10 =G9 ← x₃ prev = x₃ new from previous iteration
E10 =(E2-C2*C10-D2*D10)/B2
F10 =(E3-B3*B10-D3*D10)/C3
G10 =(E4-B4*B10-C4*C10)/D4
H10 =MAX(
IF(E10=0,100,ABS((E10-B10)/E10)*100),
IF(F10=0,100,ABS((F10-C10)/F10)*100),
IF(G10=0,100,ABS((G10-D10)/G10)*100)
)
- Copy row 10 downward until column H shows a value below 1%. Because B10=E9 (etc.), the "prev" columns will automatically chain through each iteration.
- Add the Comparison Text Box: Insert → Text Box on the sheet. Type your answer explaining which method converged faster and why (see Hint below).
▶ Simultaneous update: In Jacobi, the new values for ALL variables are computed using ONLY the PREV columns of the CURRENT row (i.e., the same row's B, C, D). This is the fundamental difference from Gauss-Seidel, where x₁_new is immediately used when computing x₂_new.
▶ Why "prev" columns exist: In Gauss-Seidel you can overwrite x₁, x₂, x₃ in place because each updated value is immediately used. In Jacobi you CANNOT overwrite until all three are computed — you need to hold the old values until the end of the sweep. The "prev" columns preserve those old values.
▶ Convergence comparison (for your text box): Gauss-Seidel converges in fewer iterations because it uses each updated value immediately, propagating information faster within a single sweep. Both methods converge when the system is diagonally dominant, but Gauss-Seidel's spectral radius is typically smaller, meaning faster error reduction per iteration.
Required Table Layout — Jacobi Iteration (separate prev/new column groups)
| Iter | x₁ (prev) | x₂ (prev) | x₃ (prev) | x₁ (new) | x₂ (new) | x₃ (new) | Max |εa| (%) |
|---|
| 0 | 0 | 0 | 0 | — | — | — | — |
| 1 | 0 | 0 | 0 | | | | |
| 2 | (= x₁ new of iter 1) | (= x₂ new of iter 1) | (= x₃ new of iter 1) | | | | |
| ⋯ | ⋯ | ⋯ | ⋯ | ⋯ | ⋯ | ⋯ | ⋯ |
Determine the best-fit linear model ŷ = a₀ + a₁x using the method of least squares for the data set below:
(1, 0.5) (2, 2.5) (3, 2.0) (4, 4.0) (5, 3.5) (6, 6.0) (7, 5.5)
✅ Target for Validation: Equation: ŷ = 0.0714 + 0.8393x | R²: ≈ 0.8683. The sum of all residuals must equal 0.
📋 Step-by-Step Excel Guide — P3_LeastSquares
- Enter column headers in row 1:
A1="i" B1="x" C1="y" D1="x²" E1="xy" F1="ŷ = a₀+a₁x" G1="e = y−ŷ"
- Enter the data in rows 2–8 (columns A, B, C):
A2:A8 = 1, 2, 3, 4, 5, 6, 7 B2:B8 = 1, 2, 3, 4, 5, 6, 7 C2:C8 = 0.5, 2.5, 2.0, 4.0, 3.5, 6.0, 5.5
- Enter computed columns in row 2, then copy down to row 8:
D2 =B2^2 ← x² for each data point
E2 =B2*C2 ← xy for each data point
- Enter the Sigma (summary) row in row 9:
A9 ="Σ"
B9 =SUM(B2:B8) ← Σx
C9 =SUM(C2:C8) ← Σy
D9 =SUM(D2:D8) ← Σx²
E9 =SUM(E2:E8) ← Σxy
- Compute n and the statistics in column I (rows 2–10) — these cells feed the normal equations:
I2 ="n" J2 =COUNT(B2:B8) ← n = 7
I3 ="Σx" J3 =B9 ← reference the sum row
I4 ="Σy" J4 =C9
I5 ="Σx²" J5 =D9
I6 ="Σxy" J6 =E9
I7 ="x̄" J7 =J3/J2 ← mean of x
I8 ="ȳ" J8 =J4/J2 ← mean of y
I9 ="a₁" J9 =(J2*J6-J3*J4)/(J2*J5-J3^2) ← Normal equation for slope
I10 ="a₀" J10 =J8-J9*J7 ← Intercept = ȳ − a₁·x̄
- Enter ŷ and residual formulas in row 2, copy down to row 8:
F2 =$J$10+$J$9*B2
→ Uses absolute references ($J$10 = a₀, $J$9 = a₁) so they don't shift when copied down.
→ This is ŷ = a₀ + a₁·x for each row.
G2 =C2-F2
→ Residual e = actual y − predicted ŷ.
After copying to row 8, check that G9==SUM(G2:G8) equals (or is extremely close to) 0 — this confirms your regression is correct.
- Create the scatter chart:
- Select columns B and C (x and y data only, rows 1–8).
- Insert → Charts → Scatter (first option: Scatter with Only Markers).
- Right-click any data point on the chart → "Add Trendline" → select Linear.
- In the Format Trendline panel, check "Display Equation on chart" and "Display R-squared value on chart".
- Verify the chart equation matches your computed a₀ and a₁ values.
▶ Why absolute references for a₀ and a₁: When you copy the ŷ formula from F2 down to F8, the B2 part should change to B3, B4, … but $J$10 and $J$9 must always point to the same cells. Use F4 after clicking a cell reference to toggle absolute ($J$10) vs relative (J10).
▶ Normal equations — avoid hard-coding: J9 and J10 must reference J2–J6, not manually typed numbers. The grader will change the data to verify your formulas are dynamic.
▶ Residual sum check: The sum of all residuals Σe must equal 0 (or a near-zero floating-point value like 1E-15). If your sum is not near 0, your a₀ or a₁ formula is wrong.
Required Summary Statistics Table
| i | x | y | x² | xy | ŷ = a₀ + a₁x | e = y − ŷ |
|---|
| 1 | 1 | 0.5 | | | | |
| 2 | 2 | 2.5 | | | | |
| 3 | 3 | 2.0 | | | | |
| 4 | 4 | 4.0 | | | | |
| 5 | 5 | 3.5 | | | | |
| 6 | 6 | 6.0 | | | | |
| 7 | 7 | 5.5 | | | | |
| Σ | Σx | Σy | Σx² | Σxy | — | Σe = 0 ✓ |
In a separate section on the same sheet, show: n, x̄, ȳ, a₁, a₀ (computed via normal equations with cell references).
Using the data below, construct a Newton's Divided Difference interpolating polynomial and estimate f(2.5):
(1, 0.5) (2, 2.5) (3, 2.0) (4, 4.0) (5, 3.5)
■ Scoring Breakdown
- Divided Difference Tableau (8 pts): Build the complete tableau. Each divided difference is defined as:
f[xᵢ, xᵢ₊₁] = ( f[xᵢ₊₁] − f[xᵢ] ) / ( xᵢ₊₁ − xᵢ )
f[xᵢ, …, xᵢ₊ₖ] = ( f[xᵢ₊₁,…,xᵢ₊ₖ] − f[xᵢ,…,xᵢ₊ₖ₋₁] ) / ( xᵢ₊ₖ − xᵢ )
- Polynomial Write-out (4 pts): State the interpolating polynomial explicitly in a text box on the sheet:
P(x) = f[x₀] + f[x₀,x₁](x−x₀) + f[x₀,x₁,x₂](x−x₀)(x−x₁) + f[x₀,x₁,x₂,x₃](x−x₀)(x−x₁)(x−x₂) + f[x₀,…,x₄](x−x₀)(x−x₁)(x−x₂)(x−x₃)
- Interpolated Value f(2.5) (3 pts): Evaluate P(2.5) in a formula cell referencing your tableau coefficients — do not type the numbers manually.
✅ Target for Validation: f(2.5) = 2.015625 (exact: 129/64).
📋 Step-by-Step Excel Guide — P4_Newton
- Enter headers and data in columns A and B (rows 1–6):
A1="xᵢ" B1="f[xᵢ]" C1="1st Div.Diff." D1="2nd Div.Diff." E1="3rd Div.Diff." F1="4th Div.Diff."
Enter x values A2:A6 = 1, 2, 3, 4, 5 and f(x) values B2:B6 = 0.5, 2.5, 2.0, 4.0, 3.5
- 1st Divided Differences in column C — enter in C2:C5 (C6 is blank):
C2 =(B3-B2)/(A3-A2) ← f[x₁,x₂] = (f(2)−f(1))/(2−1) = 2.0
C3 =(B4-B3)/(A4-A3) ← f[x₂,x₃] = (f(3)−f(2))/(3−2) = −0.5
C4 =(B5-B4)/(A5-A4) ← f[x₃,x₄] = (f(4)−f(3))/(4−3) = 2.0
C5 =(B6-B5)/(A6-A5) ← f[x₄,x₅] = (f(5)−f(4))/(5−4) = −0.5
C6 = (leave blank or type "—")
- 2nd Divided Differences in column D — enter in D2:D4 (D5 and D6 blank):
D2 =(C3-C2)/(A4-A2) ← f[x₁,x₂,x₃] = (C3−C2)/(x₃−x₁) = −1.25
D3 =(C4-C3)/(A5-A3) ← f[x₂,x₃,x₄] = 1.25
D4 =(C5-C4)/(A6-A4) ← f[x₃,x₄,x₅] = −1.25
Note: each 2nd diff spans 3 x-values. The denominator is x[row+2] − x[row].
- 3rd Divided Differences in column E — enter in E2:E3 only:
E2 =(D3-D2)/(A5-A2) ← f[x₁,x₂,x₃,x₄] = (D3−D2)/(x₄−x₁) ≈ 0.8333
E3 =(D4-D3)/(A6-A3) ← f[x₂,x₃,x₄,x₅] = −0.8333
- 4th Divided Difference in column F — enter only in F2:
F2 =(E3-E2)/(A6-A2) ← f[x₁,…,x₅] = (E3−E2)/(x₅−x₁) ≈ −0.4167
- Enter the x value to evaluate and compute P(x):
H1 ="x to evaluate"
I1 =2.5 ← type the value here; the formula below will reference it
H2 ="P(x) ="
I2 =B2
+C2*(I1-A2)
+D2*(I1-A2)*(I1-A3)
+E2*(I1-A2)*(I1-A3)*(I1-A4)
+F2*(I1-A2)*(I1-A3)*(I1-A4)*(I1-A5)
→ Each term adds the next Newton coefficient multiplied by the
growing product of (x − xᵢ) terms.
→ B2 = f[x₀] = 0.5
→ C2 = f[x₀,x₁] = first divided difference (top of column C)
→ D2 = f[x₀,x₁,x₂] = second divided difference (top of column D)
→ E2 = f[x₀,x₁,x₂,x₃] = third divided difference (top of column E)
→ F2 = f[x₀,x₁,x₂,x₃,x₄] = fourth divided difference (top of column F)
Type the entire formula as one expression on a single line in Excel — shown on multiple lines above for readability only.
- Add a text box (Insert → Text Box) writing out the polynomial explicitly:
P(x) = 0.5 + 2.0(x−1) + (−1.25)(x−1)(x−2) + (0.8333)(x−1)(x−2)(x−3) + (−0.4167)(x−1)(x−2)(x−3)(x−4)
▶ Staircase structure: Column C has 4 values, D has 3, E has 2, F has 1. Each column has one fewer entry than the one before it. Lower cells in each column must be left blank or marked "—".
▶ Denominator rule: For a divided difference involving k+1 points starting at row i, the denominator is always A[i+k] − A[i] (the LAST x minus the FIRST x in that difference's span).
▶ Coefficients = top row of each column: The Newton polynomial coefficients are B2, C2, D2, E2, F2 — always the top (first) entry of each column. This is why the formula in I2 references the "2" row throughout.
▶ Single formula cell for P(x): Reference I1 (the x value) in your polynomial formula — do not hard-code 2.5. Changing I1 to any other x should instantly recalculate P(x).
Required Divided Difference Tableau (— = intentionally blank)
| xᵢ | f[xᵢ] | 1st Div. Diff. | 2nd Div. Diff. | 3rd Div. Diff. | 4th Div. Diff. |
|---|
| 1 | 0.5 | | | | |
| 2 | 2.5 | | | | — |
| 3 | 2.0 | | | — | — |
| 4 | 4.0 | | — | — | — |
| 5 | 3.5 | — | — | — | — |
| P(2.5) = | |
Using the same data set as Problem 4, estimate f(2.5) via Lagrange interpolation and compare your result with Problem 4.
✅ Target for Validation: P(2.5) = 2.015625. This must match Problem 4 exactly. If it does not, one of the Lk formulas has an error.
📋 Step-by-Step Excel Guide — P5_Lagrange
- Enter headers and data in rows 1–6:
A1="k" B1="xₖ" C1="f(xₖ)" D1="Lₖ(x)" E1="f(xₖ)·Lₖ(x)"
A2:A6 = 0, 1, 2, 3, 4 B2:B6 = 1, 2, 3, 4, 5 C2:C6 = 0.5, 2.5, 2.0, 4.0, 3.5
- Enter the evaluation point in a named cell:
G1 = "x =" H1 = 2.5 ← put 2.5 here. All Lk formulas reference $H$1 so you can change the evaluation point in one place.
- Enter Lₖ formulas in column D (one per row). Each Lk is a product of (x−xⱼ) terms in the numerator and (xₖ−xⱼ) terms in the denominator, excluding j = k:
D2 (L₀ — excludes k=0, so product over j=1,2,3,4):
= ($H$1-$B$3)*($H$1-$B$4)*($H$1-$B$5)*($H$1-$B$6)
/ (($B$2-$B$3)*($B$2-$B$4)*($B$2-$B$5)*($B$2-$B$6))
D3 (L₁ — excludes k=1, so product over j=0,2,3,4):
= ($H$1-$B$2)*($H$1-$B$4)*($H$1-$B$5)*($H$1-$B$6)
/ (($B$3-$B$2)*($B$3-$B$4)*($B$3-$B$5)*($B$3-$B$6))
D4 (L₂ — excludes k=2, so product over j=0,1,3,4):
= ($H$1-$B$2)*($H$1-$B$3)*($H$1-$B$5)*($H$1-$B$6)
/ (($B$4-$B$2)*($B$4-$B$3)*($B$4-$B$5)*($B$4-$B$6))
D5 (L₃ — excludes k=3, so product over j=0,1,2,4):
= ($H$1-$B$2)*($H$1-$B$3)*($H$1-$B$4)*($H$1-$B$6)
/ (($B$5-$B$2)*($B$5-$B$3)*($B$5-$B$4)*($B$5-$B$6))
D6 (L₄ — excludes k=4, so product over j=0,1,2,3):
= ($H$1-$B$2)*($H$1-$B$3)*($H$1-$B$4)*($H$1-$B$5)
/ (($B$6-$B$2)*($B$6-$B$3)*($B$6-$B$4)*($B$6-$B$5))
Pattern rule: In the numerator, the factors are ($H$1 − $B$[all rows EXCEPT current row]). In the denominator, the factors are ($B$[current row] − $B$[all rows EXCEPT current row]).
- Verify the basis polynomials sum to 1: Enter in G3: =SUM(D2:D6). The result must equal exactly 1.0. If not, check your Lk formulas.
- Enter the f(xₖ)·Lₖ column in E2:E6:
E2 =C2*D2 ← f(x₀)·L₀(2.5)
E3 =C3*D3 ...copy down to E6
- Compute P(2.5) in the final row (row 7):
A7 ="P(2.5)"
E7 =SUM(E2:E6) ← This is your interpolated value
- Add the Comparison Text Box: Insert → Text Box. State that the Lagrange result matches Newton's result and explain uniqueness of the interpolating polynomial.
▶ One basis polynomial per data point: For n = 5 data points, you compute 5 basis polynomials, L₀ through L₄. Each one is a rational product with 4 factors in both numerator and denominator.
▶ Which j to exclude: For Lk, you exclude xₖ itself from both the numerator and denominator products. Numerator factors: (x − xⱼ) for all j ≠ k. Denominator factors: (xₖ − xⱼ) for all j ≠ k. For example, D3 (L₁, where k=1, xₖ=B3) excludes B3 from both products and uses B2, B4, B5, B6.
▶ Verify with SUM(D2:D6) = 1: A key property of Lagrange basis polynomials is that they sum to 1 for any x. If your sum is not exactly 1, one of the Lk formulas is wrong.
▶ Comparison note content: Both methods must agree because there is exactly one polynomial of degree ≤ n that passes through n+1 given data points. Newton's and Lagrange's forms are two different algebraic representations of the same unique polynomial.
Required Table Layout — Lagrange Interpolation at x = 2.5
| k | xₖ | f(xₖ) | Lk(2.5) | f(xₖ) · Lk(2.5) |
|---|
| 0 | 1 | 0.5 | | |
| 1 | 2 | 2.5 | | |
| 2 | 3 | 2.0 | | |
| 3 | 4 | 4.0 | | |
| 4 | 5 | 3.5 | | |
| Verification: Σ Lₖ = 1.0 ✓ |
|
P(2.5) = |