The Lumenary · Early undergraduate

Numerical methods

Name: ______________________

Date: ______________________

You will learn to

Explain binary floating-point representation, machine epsilon and the unit roundoff, and prove that subtracting nearly equal numbers amplifies relative error (catastrophic cancellation)
Implement bisection and Newton's method, prove that bisection always converges for a continuous function with a sign change and that Newton's method converges quadratically near a simple root, and give examples where Newton fails
Define the order of convergence of an iterative method and estimate it from computed errors
Derive the error of polynomial interpolation and of difference quotients, and balance truncation error against rounding error
Implement the composite trapezoidal and Simpson rules and prove their error bounds $O(h^2)$ and $O(h^4)$ for smooth integrands

1.
Bisection is started on $[1, 2]$ to find $\sqrt 2$ as a root of $x^2 - 2$ . After $n$ halvings we report the midpoint of the current interval. What is the smallest $n$ for which Theorem 3 guarantees an error of at most $10^{-6}$ ?
2.
Newton's method for $x^2 - 2$ is $x_{n+1} = \frac12\left(x_n + \frac{2}{x_n}\right)$ . Starting from $x_0 = 1$ , compute exactly $x_1 = \frac32$ , $x_2 = \frac{17}{12}$ and $x_3 = \frac{p}{q}$ in lowest terms. Enter the numerator $p$ .
3.
For large $x$ (say $x = 10^{12}$ ), which formula computes $\sqrt{x + 1} - \sqrt{x}$ most accurately in floating point?
- A. $\dfrac{1}{\sqrt{x + 1} + \sqrt{x}}$
- B. $\sqrt{x + 1} - \sqrt{x}$ , as written
- C. $\sqrt{(x + 1) - x}$
- D. $\sqrt{x}\,\big(\sqrt{1 + 1/x} - 1\big)$
4.
Newton's method for $f(x) = \sqrt[3]{x}$ (the real cube root) gives $x_{n+1} = -2x_n$ and diverges from every $x_0 \ne 0$ , although $f(0) = 0$ . Which hypothesis of Theorem 4 fails?
- A. $f$ is not differentiable at the root $0$ (its derivative blows up there), so it is not $C^2$ near the root.
- B.The root is not simple: $f'(0) = 0$ .
- C.The starting point is too far from the root.
- D. $f$ is not continuous at $0$ .
5.
Apply Simpson's rule with $n = 2$ strips ( $h = 2$ ) to $\int_0^4 x^3\,dx$ . What value does it give?
6.
Which statements are true? (Choose all that apply.)
- A.The trapezoidal rule integrates every polynomial of degree $\le 1$ exactly.
- B.Simpson's rule integrates $x^4$ exactly.
- C.For a smooth integrand, halving $h$ divides the trapezoidal error by about $4$ .
- D.Simpson's rule has error $O(h^4)$ for $\int_0^1 \sqrt x\,dx$ .
- E.Simpson's rule with step $h/2$ equals $\frac{4T_{h/2} - T_h}{3}$ .
7.
In binary64 arithmetic, approximately which step $h$ minimises the total error of the forward difference $\frac{f(x + h) - f(x)}{h}$ for a typical smooth function with $f$ , $f''$ of moderate size?
- A. $h \approx 10^{-8}$
- B. $h \approx 10^{-16}$ , the unit roundoff
- C.As small as possible: the error tends to $0$ as $h \to 0$ .
- D. $h \approx 10^{-2}$
8.
With IsBinary64 x meaning " $x$ is a positive binary64 number", which Lean statement says that $2^{-52}$ is the gap between $1$ and the next larger binary64 number?
- A.IsBinary64 (1 + 2 ^ (-52 : ℤ)) ∧ ∀ x, IsBinary64 x → ¬ (1 < x ∧ x < 1 + 2 ^ (-52 : ℤ))
- B.∀ x, IsBinary64 x → 1 + 2 ^ (-52 : ℤ) ≤ x
- C.∃ x, IsBinary64 x ∧ 1 < x ∧ x < 1 + 2 ^ (-52 : ℤ)
- D.∀ x, ¬ (1 < x ∧ x < 1 + 2 ^ (-52 : ℤ))
9.
Write newton(f, df, x0, tol=1e-12, max_iter=50) that runs Newton's method and returns (x, n): the first iterate with abs(f(x)) <= tol and the number of steps taken. If a derivative is exactly 0, or max_iter steps pass without success, return (None, n).
Computational — Practice

Answer key — Numerical methods

1.
We need $(2 - 1)/2^{n+1} \le 10^{-6}$ , i.e. $2^{n+1} \ge 10^6$ . Since $2^{19} = 524\,288 < 10^6 \le 1\,048\,576 = 2^{20}$ , we need $n + 1 \ge 20$ , so $n = 19$ . That is about $3.3$ steps per decimal digit, the price of bisection's reliability.
2.
$x_3 = \frac12\left(\frac{17}{12} + \frac{24}{17}\right) = \frac12 \cdot \frac{289 + 288}{204} = \frac{577}{408}$ . Its error is about $2.1 \times 10^{-6}$ , compared with $2.5 \times 10^{-3}$ for $x_2$ : roughly squared, as Heron's error identity $x' - \sqrt2 = (x - \sqrt2)^2/(2x)$ predicts.
3.
$\sqrt{x + 1} - \sqrt x = \frac{(x + 1) - x}{\sqrt{x + 1} + \sqrt x} = \frac{1}{\sqrt{x + 1} + \sqrt x}$ . The right-hand side involves only additions, a square root and a division, each with relative error at most $u$ , so it is accurate to almost full precision. The original form subtracts two numbers that agree to about $12$ digits, losing them by Theorem 2.
4.
Theorem 4 assumes that $f$ is $C^2$ on an interval around the root with $f'(r) \ne 0$ . The cube root is not differentiable at $0$ ( $f'(x) = \frac13 x^{-2/3}$ is unbounded), so the theorem does not apply — and indeed $x - f(x)/f'(x) = x - 3x = -2x$ , so the iterates double in size and alternate in sign.
5.
$S_h = \frac{2}{3}(0 + 4 \cdot 8 + 64) = \frac23 \cdot 96 = 64$ , which is exactly $\int_0^4 x^3\,dx = \frac{4^4}{4} = 64$ . Simpson's rule is exact for cubics because $f^{(4)} = 0$ (Theorem 7; the Lean theorem simpson_exact_cubic).
6.
True: (a), (c), (e). (b) is false because Simpson's rule has degree of exactness $3$ ; (d) is false because the error bound needs a bounded fourth derivative, which $\sqrt x$ lacks at $0$ — the third experiment measures a rate of $h^{1.5}$ .
7.
With $E(h) = \frac{h}{2}M_2 + \frac{2\epsilon}{h}$ , $E'(h) = 0$ gives $h^* = 2\sqrt{\epsilon/M_2} \approx 10^{-8}$ for $\epsilon \approx 10^{-16}$ and $M_2 \approx 1$ , with error about $2\sqrt{\epsilon M_2} \approx 10^{-8}$ . The experiment on $\sin$ at $1$ shows exactly this V shape.
8.
Option (a) states both parts: $1 + 2^{-52}$ is representable, and no representable number lies strictly between $1$ and $1 + 2^{-52}$ . These are the Lean theorems one_add_eps_is_binary64 and machine_epsilon. Option (d) forgets the hypothesis IsBinary64 x and becomes false — a typical way a formal statement exposes a hidden assumption.

def newton(f, df, x0, tol=1e-12, max_iter=50):
    x = x0
    for n in range(max_iter):
        if abs(f(x)) <= tol:
            return x, n
        d = df(x)
        if d == 0:
            return None, n
        x = x - f(x) / d
    if abs(f(x)) <= tol:
        return x, max_iter
    return None, max_iter

The safeguards matter: a zero derivative would divide by zero, and the cycle for $x^3 - 2x + 2$ from $0$ would loop forever. Quadratic convergence (Theorem 4) explains why only a handful of steps are needed for $\sqrt 2$ ; the tests are finite checks, not a proof.