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

Question 4: Least-Squares Parabola Normal Equations & Newton Divided-Difference Interpolation (A: 10 marks; 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 model $y=\alpha+\beta x^2$. (B) The six points $(x,F(x))$ tabulated above.

Find. (A) A derivation of the stated $\alpha,\beta$ formulas from the least-squares principle. (B) The Newton divided-difference interpolating polynomial of highest possible degree through the six points.

Approach. (A) Minimize the sum of squared residuals by calculus (two normal equations), then solve the resulting $2\times2$ linear system by elimination. (B) Build the full divided-difference table; the highest-order entry reveals whether the "true" degree is lower than the point count would suggest.

1. (A) Set up the least-squares objective. Minimize $S(\alpha,\beta)=\sum_{i=1}^n\big(y_i-\alpha-\beta x_i^2\big)^2$ over $\alpha,\beta$. Setting the partial derivatives to zero, $$\dfrac{\partial S}{\partial\alpha}=-2\sum_i\big(y_i-\alpha-\beta x_i^2\big)=0,\qquad \dfrac{\partial S}{\partial\beta}=-2\sum_i x_i^2\big(y_i-\alpha-\beta x_i^2\big)=0$$ gives the two normal equations $$n\alpha+\beta\sum x_i^2=\sum y_i\qquad\text{(I)}\qquad\qquad \alpha\sum x_i^2+\beta\sum x_i^4=\sum x_i^2y_i\qquad\text{(II)}$$
2. Solve the $2\times2$ linear system. Writing $S_1=\sum x_i^2$, $S_2=\sum x_i^4$, $S_3=\sum y_i$, $S_4=\sum x_i^2y_i$, equations (I)–(II) are $n\alpha+S_1\beta=S_3$ and $S_1\alpha+S_2\beta=S_4$. By Cramer's rule with determinant $D=nS_2-S_1^2$, $$\alpha=\dfrac{S_2S_3-S_1S_4}{D},\qquad\beta=\dfrac{nS_4-S_1S_3}{D}$$
3. Box the result. Substituting the sum notation back in reproduces exactly the stated formulas: $$\boxed{\alpha=\dfrac{\big(\sum x_i^4\big)\big(\sum y_i\big)-\big(\sum x_i^2\big)\big(\sum x_i^2y_i\big)}{n\big(\sum x_i^4\big)-\big(\sum x_i^2\big)^2},\qquad \beta=\dfrac{n\big(\sum x_i^2y_i\big)-\big(\sum x_i^2\big)\big(\sum y_i\big)}{n\big(\sum x_i^4\big)-\big(\sum x_i^2\big)^2}}$$ as required. (The determinant $D=nS_2-S_1^2$ is positive whenever the $x_i^2$ are not all equal, by the Cauchy–Schwarz inequality, so the minimizer is unique.)
4. (B) Build the divided-difference table. With nodes $x_0,\dots,x_5=-4,-3,-2,-1,1,4$ and $F(x_0),\dots,F(x_5)=216,0,-56,-36,16,-56$, each column is $f[x_i,\dots,x_{i+k}]=\dfrac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}$:

   Newton divided-difference table

   $x_i$	$f[x_i]$	1st	2nd	3rd	4th	5th
   $-4$	$216$	$-216$	$80$	$-14$	$1$	$0$
   $-3$	$0$	$-56$	$38$	$-9$	$1$
   $-2$	$-56$	$20$	$2$	$-2$
   $-1$	$-36$	$26$	$-10$
   $1$	$16$	$-24$
   $4$	$-56$

5. Read off the true degree. The top-diagonal coefficients feeding the Newton form are $f[x_0]=216,\ f[x_0,x_1]=-216,\ f[x_0,x_1,x_2]=80,\ f[x_0,\dots,x_3]=-14,\ f[x_0,\dots,x_4]=1,\ f[x_0,\dots,x_5]=\boxed{0}$. The vanishing 5th divided difference means the 6th data point adds no new polynomial information beyond degree 4 — the "polynomial of highest possible degree" through these six points is only degree 4, not degree 5.
6. Assemble and expand the Newton form. $$P(x)=216-216(x+4)+80(x+4)(x+3)-14(x+4)(x+3)(x+2)+1\cdot(x+4)(x+3)(x+2)(x+1)$$ Expanding (the $f[x_0,\dots,x_5](x+4)(x+3)(x+2)(x+1)(x-1)$ term drops out since its coefficient is $0$): $$\boxed{P(x)=x^4-4x^3-11x^2+30x}$$ Spot-check: $P(-4)=256+256-176-120=216$ ✓, $P(1)=1-4-11+30=16$ ✓, $P(4)=256-256-176+120=-56$ ✓ — matches the table at every node.