Appendix B — Exam solutions

In this appendix you find example solutions to the exam-style questions.

B.1 Numbers

(a) Machine Precision

Machine precision is the gap between the number 1 and the next larger floating point number. With 4 bits for the mantissa, the smallest number greater than \(1\) that can be represented is \(1.0001_2\). So machine precision is \(\epsilon = 0.0001_2=1/16\). The machine precision is the upper bound for the relative rounding error.

(b) Conversion of 13.5

Sign: Positive (\(+13.5\)), so \(s=0\).
Convert \(13.5\) to binary:
- \(13_{10} = 1101_2\).
- \(0.5_{10} = 0.1_2\).
- Result: \(1101.1_2\).
Normalize: \(1.1011 \times 2^3\).
Exponent (\(E=3\)):
- Stored exponent \(e = E + 3 = 3 + 3 = 6\).
- \(6_{10} = 110_2\).
Mantissa (\(m\)): Drop the leading 1 \(\rightarrow\) 1011.
Final Bit Pattern: 0 110 1011.

(c) Addition: 13.5 + 0.25

Convert second number (0.25):
- \(0.25 = 1/4 = 1.0 \times 2^{-2}\).
Align Exponents:
- \(x_1 = 1.1011 \times 2^3\)
- \(x_2 = 1.0000 \times 2^{-2}\)
- Shift \(x_2\) to match exponent \(3\): Shift right by \(3 - (-2) = 5\) positions.
- \(x_2 \rightarrow 0.00001 \times 2^3\).

Add Significands:

  1.1011      (13.5)
+ 0.00001     (0.25 aligned)
-----------
  1.10111

Rounding:
- The result \(1.10111_2\) has 5 fractional bits, but we can only store 4.
- It lies exactly halfway between \(1.1011\) (\(13.5\)) and \(1.1100\) (\(14.0\)).
- Tie-breaking rule: “Ties to Even”.
- The Least Significant Bit (4th bit) is 1 (odd). To make it even, we round up (add 1 to the LSB).
- \(1.1011 + 0.0001 = 1.1100\).
Final Result:
- Significand: \(1.1100\)
- Value: \(1.1100_2 \times 2^3 = 1110.0_2 = \mathbf{14.0}\).
Error:
- Exact sum: \(13.75\).
- Stored sum: \(14.0\).
- Absolute Error: \(|13.75 - 14.0| = \mathbf{0.25}\).

(d) Loss of Significance

Error Type: Catastrophic Cancellation (or Loss of Significant Digits).
Explanation: When \(x\) is very large (\(10^8\)), \(x^2 + 1 \approx x^2\), so \(\sqrt{x^2+1} \approx x\). Subtracting two extremely close numbers causes the cancellation of the leading digits, leaving only the random “noise” from the least significant bits.
Improved (Stable) Formula: Multiply by the conjugate: \[f(x) = \frac{(\sqrt{x^2+1} - x)(\sqrt{x^2+1} + x)}{\sqrt{x^2+1} + x} = \frac{1}{\sqrt{x^2+1} + x}.\]

B.2 Functions

(a) Missing \(x^2\) term

The coefficient for the \(x^2\) term in the Taylor Series expansion around \(x_0 = 0\) is given by \(\frac{f''(0)}{2!}\). For \(f(x) = \sin(x)\), the second derivative is \(f''(x) = -\sin(x)\). Evaluating this at \(x=0\) yields \(f''(0) = -\sin(0) = 0\). Hence, the coefficient is 0. Alternatively, one could note that \(\sin(x)\) is an odd function, so its Taylor series only contains odd powers of \(x\).

(b) Python Code

import math

def sin_taylor(x, n):
    """
    Calculate the Taylor expansion for f(x) = sin(x) centred at x_0 = 0 up to order n.
    """
    term = x / 1
    result = term
    for i in range(3, n + 1, 2):
        term = -term * x**2 / (i * (i-1))
        result += term
    return result

(Other valid implementations, such as computing terms from scratch using math.factorial or checking if i % 2 != 0 within a regular loop, are also acceptable).

(c) Truncation Error

i) If we truncate the series after the \(x^3\) term, the next term in the mathematical Taylor series is the \(x^5\) term (since the \(x^4\) term is 0). Therefore, the truncation error is \(\mathcal{O}(x^5)\).
ii) Evaluating the function at \(x = 0.05\) instead of \(x = 0.1\) reduces \(x\) by a factor of \(1/2\). Because the error scales as \(\mathcal{O}(x^5)\), the truncation error is expected to decrease by a factor of \((1/2)^5 = \mathbf{1/32}\).

B.3 Roots 1

(a) Conditions for Bisection Method Convergence

The function \(f\) must be continuous on the closed interval \([a, b]\).
The function values at the endpoints must have opposite signs, i.e., \(f(a) \cdot f(b) < 0\).

(b) Number of Iterations

The error after \(n\) iterations is bounded by \(\frac{|b-a|}{2^n} = \frac{1}{2^n}\).
We need \(\frac{1}{2^n} \le 2^{-20}\). Therefore, \(n = 20\) iterations are required.

(c) Three Iterations of Bisection Method

Iteration 1:
- Interval: \([a, b] = [1, 2]\).
- Midpoint \(m_1 = 1.5\).
Iteration 2:
- From the graph, \(f(1.5)\) is slightly below the x-axis, so \(f(1.5) < 0\).
- Since \(f(1.5) < 0\) and \(f(2) > 0\), the root must lie in the new interval \([1.5, 2]\).
- Midpoint \(m_2 = \frac{1.5 + 2}{2} = 1.75\).
Iteration 3:
- From the graph, at \(x=1.75\), the function curve is clearly above the x-axis, so \(f(1.75) > 0\).
- Since \(f(1.5) < 0\) and \(f(1.75) > 0\), the narrower interval containing the root is \([1.5, 1.75]\).
- Midpoint \(m_3 = \frac{1.5 + 1.75}{2} = 1.625\).

(d) Fixed-Point Iteration

i) Convergence check:
- \(g(x) = (x+2)^{1/3}\)
- \(g'(x) = \frac{1}{3}(x+2)^{-2/3}\).
- For \(x \in [1, 2]\), the denominator is positive and increasing.
- The maximum of \(|g'(x)|\) on this interval occurs at \(x = 1\), where \(g'(1) = \frac{1}{3(3)^{2/3}}\).
- Since \(|g'(x)| < 1\) for all \(x \in [1, 2]\) and \(g(x) \in [1, 2]\) on this interval (as \(g(1) \approx 1.44\) and \(g(2) \approx 1.58\)), the Fixed-Point Theorem guarantees convergence for any \(x_0 \in [1, 2]\).

ii) Code:

def fixed_point_iteration():
    x = 1.0
    for i in range(10):
        x = (x + 2)**(1/3)
    return x

B.4 Roots 2

(a) Secant Method vs Newton’s Method

Explanation: The Secant method replaces the exact derivative \(f'(x_n)\) in Newton’s iteration formula with a finite difference approximation (the slope of the secant line) using the two previous iterates: \(f'(x_n) \approx \frac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}}\).
Advantage: It does not require an explicit formula for the derivative of the function, which is useful if the derivative is difficult or computationally expensive to evaluate.
Disadvantage: It has a lower order of convergence (superlinear, \(\alpha \approx 1.62\)) compared to Newton’s method (quadratic, \(\alpha = 2\)), so it may require more iterations to achieve the same accuracy. It also requires two initial guesses instead of one.

(b) Order of Convergence

Definition: A sequence \(\{x_n\}\) converging to \(p\) (with \(x_n \neq p\)) has an order of convergence \(\alpha \ge 1\) if there exists a constant \(\lambda > 0\) such that \(\lim_{n \to \infty} \frac{|x_{n+1}-p|}{|x_n - p|^\alpha} = \lambda\).
Orders of convergence:
- Bisection Method: 1 (Linear)
- Secant Method: \(\frac{1+\sqrt{5}}{2} \approx 1.618\) (Superlinear)
- Newton’s Method: 2 (Quadratic)

(c) Applying the Methods to \(f(x) = x^2 - 5\)

i) Newton’s method:
- \(f(x) = x^2 - 5 \implies f'(x) = 2x\).
- Formula: \(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\).
- \(x_0 = 2\).
- \(f(2) = 2^2 - 5 = -1\).
- \(f'(2) = 2(2) = 4\).
- \(x_1 = 2 - \frac{-1}{4} = 2.25\).
ii) Secant method:
- Formula: \(x_{n+1} = x_n - \frac{f(x_n)(x_n - x_{n-1})}{f(x_n) - f(x_{n-1})}\).
- \(x_0 = 3, f(x_0) = 3^2 - 5 = 4\).
- \(x_1 = 2, f(x_1) = 2^2 - 5 = -1\).
- \(x_2 = 2 - \frac{(-1)(2 - 3)}{(-1) - 4} = 2 - \frac{(-1)(-1)}{-5} = 2 - \frac{1}{-5} = 2.2\).

(d) Error Estimation

Given \(E_{n+1} \approx E_n^2\).
\(E_3 \approx E_2^2 = (10^{-3})^2 = 10^{-6}\).
\(E_4 \approx E_3^2 = (10^{-6})^2 = 10^{-12}\).
The expected error \(E_4\) is roughly \(10^{-12}\).

(e) Order of Convergence for Newton’s Method

Newton’s method is defined by \(x_{n+1} = g(x_n)\) where \(g(x) = x - \frac{f(x)}{f'(x)}\).
To find the order of convergence, we evaluate the derivatives of \(g(x)\) at the root \(p\).
First derivative: \(g'(x) = 1 - \frac{f'(x)f'(x) - f(x)f''(x)}{[f'(x)]^2} = \frac{[f'(x)]^2 - [f'(x)]^2 + f(x)f''(x)}{[f'(x)]^2} = \frac{f(x)f''(x)}{[f'(x)]^2}\).
Evaluate \(g'(x)\) at \(p\): since \(p\) is a root, \(f(p) = 0\). Since it is a simple root, \(f'(p) \neq 0\). Thus, \(g'(p) = \frac{f(p)f''(p)}{[f'(p)]^2} = \frac{0 \cdot f''(p)}{[f'(p)]^2} = 0\).
According to the theorem on the order of convergence for fixed-point iterations, if \(g(p) = p\) and \(g'(p) = 0\), but \(g''(p) \neq 0\) (which is generally true unless \(f''(p)=0\)), the sequence has an order of convergence of \(m=2\) (quadratic convergence).