Level 4 — ApplicationNumerical Methods

Numerical Methods

⏱ 60 minutes60 marksprintable — key stays hidden on paper

Level: 4 (Application — novel problems, no hints) Time limit: 60 minutes Total marks: 60

Answer all questions. Calculators permitted. Show all working; unsupported answers earn no method marks.

Question 1 — Catastrophic cancellation & conditioning (12 marks)

Consider computing $f(x) = \dfrac{1 - \cos x}{x^2}$ for small $x$ , whose exact limit as $x \to 0$ is $\tfrac12$ .

(a) Working in a hypothetical decimal machine that carries only 6 significant digits, evaluate $f(x)$ directly at $x = 10^{-3}$ using $\cos(10^{-3}) \approx 0.999999$ (rounded to 6 sig. figs). Report the computed value and the relative error against $0.5$ . (4)

(b) Explain precisely which subtraction causes catastrophic cancellation and estimate how many significant digits are lost. (3)

(c) Derive an algebraically equivalent formula for $f(x)$ using a half-angle identity that avoids the cancellation, and re-evaluate at $x=10^{-3}$ using $\sin(5\times10^{-4}) \approx 0.000500000$ to 6 sig. figs. (3)

(d) The relative condition number of a function is $\kappa_f(x) = \left|\dfrac{x f'(x)}{f(x)}\right|$ . Compute $\kappa_f$ at $x \to 0$ (use the limit) and state whether the problem itself is well-conditioned there, distinguishing this from the algorithm's instability. (2)

Question 2 — Root finding, mixed methods (14 marks)

Let $g(x) = x^3 - 2x - 5$ (a classical test equation), which has a single real root near $x=2$ .

(a) Perform 2 iterations of the secant method starting from $x_0 = 2$ , $x_1 = 3$ . Report $x_2$ and $x_3$ to 5 decimal places. (5)

(b) Perform 1 iteration of Newton–Raphson from $x_0 = 2$ . Compare the resulting estimate's accuracy with your $x_2$ from part (a). (3)

(c) Bisection is applied on $[2,3]$ . Determine the minimum number of iterations required to guarantee the root is located to within an absolute error of $10^{-6}$ . (3)

(d) State the theoretical order of convergence of the secant method and of Newton's method, and explain in one or two sentences why the secant method can still be preferred in practice. (3)

Question 3 — Interpolation & numerical integration (14 marks)

The function values below are sampled from an unknown smooth $f$ :

$x$	0	1	2	3
$f(x)$	1	2	5	10

(a) Construct the Newton divided-difference interpolating polynomial through all four points and simplify it to standard form. (5)

(b) Use the composite Simpson's 1/3 rule with all four intervals-worth of data appropriately (i.e. use nodes $0,1,2$ for Simpson and handle the remaining subinterval) to estimate $\int_0^3 f(x)\,dx$ . Clearly state how you treat the interval $[2,3]$ and justify. (5)

(c) Given that a bound $|f^{(4)}(\xi)| \le M$ holds on $[0,2]$ , write the error term for the composite Simpson's 1/3 rule over $[0,2]$ with $h=1$ , and evaluate it for the polynomial you found in (a) (state the value of $f^{(4)}$ ). (4)

Question 4 — Linear systems & iterative convergence (10 marks)

Consider the system

\begin{aligned} 4x_1 - x_2 + x_3 &= 7,\\ 2x_1 + 5x_2 + x_3 &= -3,\\ x_1 + x_2 + 4x_3 &= 4. \end{aligned}

(a) Show the coefficient matrix is strictly diagonally dominant, and hence state what this guarantees about the Jacobi and Gauss–Seidel iterations. (3)

(b) Perform 1 iteration of Gauss–Seidel starting from $x^{(0)} = (0,0,0)^T$ . Report $x^{(1)}$ . (5)

Question 5 — ODE integration (10 marks)

Consider the IVP $y' = y - t^2 + 1$ , $\ y(0) = 0.5$ , on $[0, 0.4]$ with step $h = 0.2$ .

(a) Take one step of Heun's method (modified Euler) to estimate $y(0.2)$ . Show the predictor and corrector explicitly. (5)

(b) Take one step of the classical RK4 method to estimate $y(0.2)$ (compute $k_1,k_2,k_3,k_4$ ). (5)

Answer keyMark scheme & solutions

Question 1 (12)

(a) With $\cos(10^{-3})=0.999999$ (6 sig figs): $1-\cos x = 1 - 0.999999 = 0.000001 = 1.00000\times10^{-6}$ . $x^2 = (10^{-3})^2 = 1.00000\times10^{-6}$ . $f = \dfrac{1.0\times10^{-6}}{1.0\times10^{-6}} = 1.00000$ . Relative error $= \dfrac{|1.0 - 0.5|}{0.5} = 1.0$ (100%). (1 mark subtraction, 1 mark $x^2$ , 1 mark quotient, 1 mark rel. error.)

(b) The subtraction $1 - \cos x$ is the culprit: for small $x$ , $\cos x \approx 1 - x^2/2 = 1 - 5\times10^{-7}$ , which is closer to 1 than 6 digits can resolve. Rounding $\cos x$ to $0.999999$ retains only ~1 significant digit of the true difference $\approx 5\times10^{-7}$ ; the leading matching digits cancel. About 5–6 significant digits are lost (the true difference has magnitude $10^{-7}$ but is represented as $10^{-6}$ ). (2 marks identify subtraction & why, 1 mark digit-loss estimate.)

(c) Half-angle: $1-\cos x = 2\sin^2(x/2)$ , so $f(x)=\frac{2\sin^2(x/2)}{x^2}=\frac12\left(\frac{\sin(x/2)}{x/2}\right)^2.$ At $x=10^{-3}$ , $x/2 = 5\times10^{-4}$ , $\sin(x/2)=0.000500000$ : $\dfrac{\sin(x/2)}{x/2} = \dfrac{0.000500000}{0.000500000} = 1.00000$ , so $f = \tfrac12(1)^2 = 0.500000$ . No cancellation because $\sin(x/2)$ is computed directly (no near-equal subtraction). (2 marks derivation, 1 mark value.)

(d) $f(x)=\tfrac12$ (limit), and $f'(x)\to 0$ as $x\to0$ (even function, smooth min). Hence $\kappa_f = \left|\dfrac{xf'(x)}{f(x)}\right| \to \dfrac{0}{1/2}=0$ . The problem is well-conditioned near $0$ (tiny perturbations in $x$ barely change $f$ ). The 100% error in (a) is purely algorithmic instability (catastrophic cancellation in the chosen formula), not inherent to the problem. (1 mark $\kappa\to0$ , 1 mark distinction.)

Question 2 (14)

(a) Secant: $x_{n+1} = x_n - g(x_n)\dfrac{x_n-x_{n-1}}{g(x_n)-g(x_{n-1})}$ . $g(2) = 8-4-5 = -1$ ; $g(3)=27-6-5=16$ . $x_2 = 3 - 16\cdot\dfrac{3-2}{16-(-1)} = 3 - \dfrac{16}{17} = 2.05882\,(35294)$ . $g(x_2)$ : $x_2=2.0588235$ , $x_2^3=8.72670$ , $g(x_2)=8.72670-4.11765-5=-0.39094$ . $x_3 = x_2 - g(x_2)\dfrac{x_2-x_1}{g(x_2)-g(x_1)}$ $= 2.05882 - (-0.39094)\dfrac{2.05882-3}{-0.39094-16}$ $= 2.05882 - (-0.39094)\cdot\dfrac{-0.94118}{-16.39094}$ $= 2.05882 + (-0.39094)(-0.05742)\cdot(-1)$ ... compute carefully: $\dfrac{-0.94118}{-16.39094}=0.057421$ ; $(-0.39094)(0.057421)=-0.022449$ ; $x_3 = 2.05882 - (-0.022449) = 2.08127$ . $x_2 \approx 2.05882$ , $x_3 \approx 2.08127$ . (2 marks $x_2$ , 3 marks $x_3$ .)

(b) Newton: $g'(x)=3x^2-2$ , $g'(2)=10$ , $g(2)=-1$ . $x_1 = 2 - (-1)/10 = 2.1$ . True root $\approx 2.09455$ . Newton's error $\approx 0.0055$ ; secant $x_2=2.05882$ has error $\approx 0.036$ . Newton's single step is more accurate than one secant step (it uses exact derivative). (2 marks value+compare, 1 mark reasoning.)

(c) Bisection error after $n$ steps $\le \dfrac{b-a}{2^n}=\dfrac{1}{2^n}$ . Require $\dfrac{1}{2^n}\le10^{-6}$ , i.e. $2^n\ge10^6$ . $2^{19}=524288<10^6$ , $2^{20}=1048576\ge10^6$ . So $n=20$ iterations. (1 formula, 1 inequality, 1 answer.)

(d) Secant order $\approx \dfrac{1+\sqrt5}{2}\approx1.618$ (superlinear); Newton order $=2$ (quadratic). Secant is often preferred because it needs no derivative evaluation — each step costs one function evaluation vs Newton's two (f and f'), giving comparable or better efficiency per work unit when derivatives are expensive/unavailable. (1 each order, 1 practical reason.)

Question 3 (14)

(a) Divided differences: $f[0]=1,\ f[1]=2,\ f[2]=5,\ f[3]=10$ . First: $f[0,1]=1,\ f[1,2]=3,\ f[2,3]=5$ . Second: $f[0,1,2]=\dfrac{3-1}{2}=1,\ f[1,2,3]=\dfrac{5-3}{2}=1$ . Third: $f[0,1,2,3]=\dfrac{1-1}{3}=0$ . Polynomial: $P(x)=1 + 1\cdot x + 1\cdot x(x-1) + 0 = 1 + x + x^2 - x = 1 + x^2.$ $P(x)=x^2+1$ . (Check: $0\to1,1\to2,2\to5,3\to10$ . ✓) (3 marks DD table, 2 marks simplification.)

(b) Composite Simpson's 1/3 on $[0,2]$ (nodes $0,1,2$ , $h=1$ ): $\int_0^2 \approx \dfrac{h}{3}[f_0+4f_1+f_2] = \dfrac{1}{3}[1+4(2)+5]=\dfrac{14}{3}=4.6667.$ Simpson's 1/3 needs an even number of intervals; $[2,3]$ is a single leftover interval, so use the trapezoidal rule there: $\int_2^3 \approx \dfrac{1}{2}(5+10)=7.5.$ Total $\approx 4.6667 + 7.5 = 12.1667$ . (Exact for $P=x^2+1$ : $\int_0^3(x^2+1)dx = 9+3 = 12$ . Simpson is exact on $[0,2]$ giving $14/3$ ; trapezoid over-estimates the quadratic on $[2,3]$ .) (2 marks Simpson, 2 marks handling $[2,3]$ with justification, 1 mark total.)

(c) Composite Simpson error over $[a,b]=[0,2]$ : $E=-\dfrac{(b-a)h^4}{180}f^{(4)}(\xi)=-\dfrac{2\cdot1^4}{180}f^{(4)}(\xi)=-\dfrac{f^{(4)}(\xi)}{90}$ . For $P(x)=x^2+1$ , $f^{(4)}\equiv 0$ , so $E=0$ — Simpson's 1/3 is exact for polynomials up to degree 3, consistent with the exact match $14/3$ on $[0,2]$ . (2 marks error formula, 2 marks $f^{(4)}=0\Rightarrow E=0$ with explanation.)

Question 4 (10)

(a) Row 1: $|4|=4 > |-1|+|1|=2$ . Row 2: $|5|=5>|2|+|1|=3$ . Row 3: $|4|=4>|1|+|1|=2$ . Strictly diagonally dominant. This guarantees both Jacobi and Gauss–Seidel converge for any initial guess. (2 marks checks, 1 mark guarantee.)

(b) Gauss–Seidel (use updated values immediately), $x^{(0)}=(0,0,0)$ : $x_1 = \dfrac{7 + x_2 - x_3}{4} = \dfrac{7+0-0}{4}=1.75.$ $x_2 = \dfrac{-3 - 2x_1 - x_3}{5} = \dfrac{-3-2(1.75)-0}{5}=\dfrac{-6.5}{5}=-1.3.$ $x_3 = \dfrac{4 - x_1 - x_2}{4}=\dfrac{4-1.75-(-1.3)}{4}=\dfrac{3.55}{4}=0.8875.$ $x^{(1)}=(1.75,\ -1.3,\ 0.8875)^T$ . (2 marks $x_1$ , 1.5 each $x_2,x_3$ .)

(c) Gauss–Seidel uses the most recently updated components within the same sweep, so it incorporates new information immediately rather than waiting for the next iteration (as Jacobi does), giving a smaller spectral radius / faster convergence for diagonally dominant systems. (2 marks.)

Question 5 (10)

$f(t,y)=y-t^2+1$ , $y_0=0.5$ , $t_0=0$ , $h=0.2$ .

(a) Heun. Predictor (Euler): $f(0,0.5)=0.5-0+1=1.5$ ; $\tilde y = 0.5+0.2(1.5)=0.8$ . Corrector slope at $(0.2,0.8)$ : $f=0.8-0.04+1=1.76$ . $y_1 = 0.5 + \dfrac{0.2}{2}(1.5+1.76)=0.5+0.1(3.26)=0.5+0.326=0.826.$ $y(0.2)\approx 0.826$ . (2 predictor, 2 corrector slope, 1 update.)

(b) RK4. $k_1 = f(0,0.5)=1.5.$ $k_2 = f(0.1,\,0.5+0.1(1.5)) = f(0.1,0.65)=0.65-0.01+1=1.64.$ $k_3 = f(0.1,\,0.5+0.1(1.64))=f(0.1,0.664)=0.664-0.01+1=1.654.$ $k_4 = f(0.2,\,0.5+0.2(1.654))=f(0.2,0.8308)=0.8308-0.04+1=1.7908.$ $y_1 = 0.5 + \dfrac{0.2}{6}(k_1+2k_2+2k_3+k_4)$ $= 0.5 + \dfrac{0.2}{6}(1.5 + 3.28 + 3.308 + 1.7908)$ $= 0.5 + 0.0333333(9.8788) = 0.5 + 0.329293 = 0.829293.$ $y(0.2)\approx 0.82929$ . (Exact solution $y=(t+1)^2-0.5e^t$ gives $y(0.2)=0.829299$ .) *(1 each $k_1..k_4$ , 1