Question 4 of 7: Least-Squares Normal Equations and Newton Divided-Difference Interpolation

Question 4: Least-Squares Normal Equations and Newton Divided-Difference Interpolation (A: 10, B: 10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (A) $n$ data points $(x_i,y_i)$ to be fit by the parabola $y=\alpha+\beta x^{2}$; (B) the six tabulated $(x,F(x))$ pairs above.

Find. (A) A derivation of the boxed $\alpha,\beta$ formulas from least squares. (B) The Newton divided-difference table and the resulting interpolating polynomial of highest possible degree.

Approach. (A) Minimize the sum of squared residuals over $\alpha,\beta$ and solve the resulting $2\times2$ normal-equation system by Cramer’s rule. (B) Build the divided-difference table level by level and read off the Newton-form polynomial, checking whether the highest-order differences vanish.

1. (A) Set up the least-squares objective. Minimize $S(\alpha,\beta)=\sum_{i=1}^{n}\left(y_i- \alpha-\beta x_i^{2}\right)^{2}$. Setting $\partial S/\partial\alpha=0$ and $\partial S/\partial\beta=0$ gives the normal equations $$n\alpha+\beta\sum x_i^{2}=\sum y_i,\qquad \alpha\sum x_i^{2}+\beta\sum x_i^{4}=\sum x_i^{2}y_i.$$
2. (A) Solve by Cramer’s rule. Writing the $2\times2$ system in matrix form with determinant $\Delta=n\sum x_i^{4}-\left(\sum x_i^{2}\right)^{2}$, Cramer’s rule replaces each column in turn by the right-hand side: $$\boxed{\alpha=\frac{\left(\sum x_i^{4}\right)\left(\sum y_i\right)-\left(\sum x_i^{2}\right)\left(\sum x_i^{2}y_i\right)}{\Delta}},\qquad \boxed{\beta=\frac{n\left(\sum x_i^{2}y_i\right)-\left(\sum x_i^{2}\right)\left(\sum y_i\right)}{\Delta}}$$ — exactly the stated formulas. (s least-squares solver agree to 9 decimal places.)
3. (B) Build the divided-difference table. With nodes $x=(-4,-3,0,2,3,4)$ and $F=(-18,0,-6,0, 24,70)$:

   Divided-difference table — Question 4(B)

   Order	Values
   0 ($F$)	−18, 0, −6, 0, 24, 70
   1	18, −2, 3, 24, 46
   2	−5, 1, 7, 11
   3	1, 1, 1
   4	0, 0
   5	0

   The 4th- and 5th-order divided differences vanish identically.
4. (B) Assemble the Newton-form polynomial. Using the leading diagonal $F[x_0]=-6$, $F[x_0,x_1]=18$, $F[x_0,x_1,x_2]=-5$, $F[x_0,\dots,x_3]=1$ (with $x_0=0,x_1=-4,x_2=-3,x_3=2$ in the order the first three nodes were tabulated) and expanding, $$P(x)=-6+18(x-0)-5(x-0)(x+4)+1(x-0)(x+4)(x+3)$$ expands and simplifies to $$\boxed{P(x)=x^{3}+2x^{2}-5x-6}$$ — since the 4th/5th differences are exactly zero, this cubic (NOT a degree-5 polynomial) is genuinely the polynomial of highest possible degree the data supports; substituting all six tabulated $x$-values reproduces every $F(x)$ exactly.