Noesis
Level 2 — RecallNumerical Methods

Numerical Methods

40 marksprintable — key stays hidden on paper

Level: 2 (Recall — definitions, standard problems, short derivations) Time: 30 minutes Total Marks: 40

Answer all questions. Show working. Use ...... for mathematics.

Q1. (4 marks) Define truncation error and round-off error, giving one clear example of each in numerical computation.

Q2. (4 marks) (a) State what machine epsilon εmach\varepsilon_{mach} represents in practice. (2) (b) For IEEE 754 double precision with a 52-bit mantissa, compute εmach=2−52\varepsilon_{mach} = 2^{-52} to 3 significant figures. (2)

Q3. (5 marks) The bisection method is applied to f(x)=x2−2f(x) = x^2 - 2 on [1,2][1, 2]. (a) Verify a root is bracketed. (1) (b) Perform two iterations, stating the interval after each. (3) (c) State the bracket width after two iterations. (1)

Q4. (5 marks) Derive the Newton–Raphson iteration formula from a first-order Taylor expansion of f(x)f(x) about xnx_n. State the update formula and name the order of convergence.

Q5. (5 marks) Perform one iteration of Newton–Raphson to approximate 5\sqrt{5} using f(x)=x2−5f(x) = x^2 - 5 with initial guess x0=2x_0 = 2. Give x1x_1 as an exact fraction and as a decimal to 4 d.p.

Q6. (5 marks) Using Lagrange interpolation, find the polynomial through the points (0,1)(0,1), (1,3)(1,3), (2,7)(2,7). Simplify to standard form ax2+bx+cax^2+bx+c.

Q7. (4 marks) Approximate ∫01ex dx\displaystyle\int_0^1 e^{x}\,dx using the trapezoidal rule with a single interval (n=1n=1). Give the numerical value to 4 d.p. and state the exact value for comparison.

Q8. (4 marks) Use the central difference formula to approximate f′(1)f'(1) for f(x)=x3f(x)=x^3 with step h=0.1h=0.1. Compare with the exact value.

Q9. (4 marks) Explain the term catastrophic cancellation. Compute 9001−9000\sqrt{9001}-\sqrt{9000} directly (4 sig figs each root) and by a rearranged, stable formula; comment on the difference.

Answer keyMark scheme & solutions

Q1. (4 marks)

  • Truncation error (1): error from approximating an infinite/exact process by a finite one (e.g. truncating a Taylor series or using finite hh in a difference formula). Example (1): approximating f′(x)≈f(x+h)−f(x)hf'(x)\approx\frac{f(x+h)-f(x)}{h} drops O(h)O(h) terms.
  • Round-off error (1): error from representing real numbers with finite precision on a computer. Example (1): 0.10.1 has no exact binary representation in IEEE 754.

Q2. (4 marks) (a) εmach\varepsilon_{mach} is the gap between 11 and the next representable floating-point number; equivalently the smallest ε\varepsilon with 1+ε≠11+\varepsilon\neq 1 in machine arithmetic. It bounds relative round-off. (2) (b) 2−52=2.2204×10−16≈2.22×10−162^{-52} = 2.2204\times10^{-16} \approx 2.22\times10^{-16}. (2)

Q3. (5 marks) (a) f(1)=−1<0f(1)=-1<0, f(2)=2>0f(2)=2>0, opposite signs ⇒ root in [1,2][1,2]. (1) (b) Iter 1: m=1.5m=1.5, f(1.5)=0.25>0f(1.5)=0.25>0 ⇒ root in [1,1.5][1,1.5]. (1.5) Iter 2: m=1.25m=1.25, f(1.25)=−0.4375<0f(1.25)=-0.4375<0 ⇒ root in [1.25,1.5][1.25,1.5]. (1.5) (c) Width =1.5−1.25=0.25=(2−1)/22=1.5-1.25=0.25 = (2-1)/2^2. (1)

Q4. (5 marks) Taylor: f(x)≈f(xn)+f′(xn)(x−xn)f(x)\approx f(x_n)+f'(x_n)(x-x_n). (2) Set f(x)=0f(x)=0 ⇒ x−xn=−f(xn)f′(xn)x - x_n = -\dfrac{f(x_n)}{f'(x_n)}. (1) xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} (1) Convergence is quadratic (order 2) near a simple root. (1)

Q5. (5 marks) f(x)=x2−5f(x)=x^2-5, f′(x)=2xf'(x)=2x. (1) x1=2−22−52⋅2=2−−14=2+14x_1 = 2 - \dfrac{2^2-5}{2\cdot2} = 2-\dfrac{-1}{4} = 2+\dfrac14. (2) x1=94=2.2500x_1=\dfrac{9}{4}=2.2500. (2) (True 5≈2.2361\sqrt5\approx2.2361.)

Q6. (5 marks) Basis: L0=(x−1)(x−2)(0−1)(0−2)=(x−1)(x−2)2L_0=\frac{(x-1)(x-2)}{(0-1)(0-2)}=\frac{(x-1)(x-2)}{2}, L1=(x)(x−2)(1)(−1)=−x(x−2)L_1=\frac{(x)(x-2)}{(1)(-1)}=-x(x-2), L2=x(x−1)(2)(1)=x(x−1)2L_2=\frac{x(x-1)}{(2)(1)}=\frac{x(x-1)}{2}. (2) P(x)=1⋅L0+3⋅L1+7⋅L2P(x)=1\cdot L_0+3\cdot L_1+7\cdot L_2. (1) =(x−1)(x−2)2−3x(x−2)+7x(x−1)2=\frac{(x-1)(x-2)}{2}-3x(x-2)+\frac{7x(x-1)}{2}. Expand: 12(x2−3x+2)−3x2+6x+72(x2−x)\frac12(x^2-3x+2) -3x^2+6x + \frac72(x^2-x) =(0.5−3+3.5)x2+(−1.5+6−3.5)x+1=x2+x+1=(0.5-3+3.5)x^2 + (-1.5+6-3.5)x + 1 = x^2+x+1. (2)

Q7. (4 marks) Trapezoidal, n=1n=1: ∫01exdx≈12(e0+e1)=12(1+2.71828)=1.8591\int_0^1 e^x dx \approx \frac{1}{2}(e^0+e^1)=\frac{1}{2}(1+2.71828)=1.8591. (3) Exact =e−1=1.7183=e-1=1.7183. (1) (Overestimate since exe^x convex.)

Q8. (4 marks) Central diff: f′(1)≈f(1.1)−f(0.9)2(0.1)=1.331−0.7290.2=0.6020.2=3.01f'(1)\approx\dfrac{f(1.1)-f(0.9)}{2(0.1)}=\dfrac{1.331-0.729}{0.2}=\dfrac{0.602}{0.2}=3.01. (3) Exact f′(1)=3⋅12=3f'(1)=3\cdot1^2=3; error 0.01=O(h2)0.01=O(h^2). (1)

Q9. (4 marks) Catastrophic cancellation (2): loss of significant digits when subtracting two nearly equal numbers, amplifying relative round-off. Direct: 9001≈94.87\sqrt{9001}\approx94.87, 9000≈94.87\sqrt{9000}\approx94.87 ⇒ difference ≈0.00\approx0.00 (digits lost). (1) Stable: 9001−9000=19001+9000≈1189.74=0.005270\sqrt{9001}-\sqrt{9000}=\dfrac{1}{\sqrt{9001}+\sqrt{9000}}\approx\dfrac{1}{189.74}=0.005270. Retains precision. (1)

[
  {"claim":"Newton iteration for sqrt5 from x0=2 gives 9/4",
   "code":"x0=Rational(2); x1=x0-(x0**2-5)/(2*x0); result=(x1==Rational(9,4))"},
  {"claim":"Lagrange interpolant through (0,1),(1,3),(2,7) is x**2+x+1",
   "code":"x=symbols('x'); P=1*(x-1)*(x-2)/2 -3*x*(x-2) +7*x*(x-1)/2; result=(expand(P)==x**2+x+1)"},
  {"claim":"Trapezoid n=1 for exp on [0,1] equals (1+e)/2",
   "code":"val=Rational(1,2)*(exp(0)+exp(1)); result=(simplify(val-(1+E)/2)==0)"},
  {"claim":"Central difference of x**3 at 1 with h=0.1 equals 3.01",
   "code":"f=lambda t:t**3; d=(f(Rational(11,10))-f(Rational(9,10)))/(2*Rational(1,10)); result=(nsimplify(d)==Rational(301,100))"}
]