The Lumenary · Advanced undergraduate

Numerical analysis

Name: ______________________

Date: ______________________

You will learn to

Define condition numbers and prove the perturbation bound for linear systems; distinguish forward error, backward error and backward stability
Solve linear systems by LU factorisation with partial pivoting, explain why pivoting is needed and why one should not form $A^{-1}$
Solve least-squares problems by QR factorisation, explain why the normal equations square the condition number, and describe the QR algorithm for eigenvalues
Prove that Euler's method converges with order 1, state and test the order of Runge–Kutta methods, and analyse absolute stability, stiffness and A-stability

1.
What is the condition number $\kappa_\infty(A) = \|A\|_\infty\|A^{-1}\|_\infty$ of $A = \begin{pmatrix} 4 & 0 \\ 0 & 0.004 \end{pmatrix}$ ?
2.
A solver returns $\hat x$ for $Ax = b$ , and you find that $\hat x$ is the exact solution of $(A + \delta A)\hat x = b$ with $\|\delta A\| / \|A\| \approx 10^{-16}$ . What can you conclude?
- A.The backward error is tiny; the forward error may still be as large as about $\kappa(A) \cdot 10^{-16}$ .
- B. $\hat x$ is accurate to about 16 digits.
- C.The solver is unstable.
- D.Nothing at all about the error in $\hat x$ .
3.
You solve $Ax = b$ in IEEE double precision ( $u \approx 10^{-16}$ ) with a backward-stable method, and $\kappa(A) \approx 10^{10}$ . Roughly how many correct significant decimal digits can you expect in the solution?
4.
Which of these invertible matrices has no factorisation $A = LU$ (with $L$ unit lower triangular and $U$ upper triangular) unless rows are swapped?
- A. $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$
- B. $\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$
- C. $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$
- D. $\begin{pmatrix} 3 & 5 \\ 0 & 7 \end{pmatrix}$
5.
Why should you solve $Ax = b$ by LU with partial pivoting rather than by computing $A^{-1}$ and multiplying? Choose all correct reasons.
- A.Forming $A^{-1}$ costs about $2n^3$ flops, three times the $\frac23 n^3$ of LU.
- B.For a sparse matrix, $A^{-1}$ is usually dense, while LU factors can often be kept sparse.
- C.The residual $\|b - A\hat x\|$ of $\mathrm{fl}(A^{-1})b$ can be about $\kappa(A)$ times larger: it is not backward stable.
- D. $A^{-1}$ cannot be computed in floating point.
- E.Computing $A^{-1}$ increases the condition number of the problem.
6.
Which Lean conclusion correctly expresses Theorem 1, $\frac{\|\delta x\|}{\|x\|} \le \kappa(A)\frac{\|\delta b\|}{\|b\|}$ , without dividing by norms that might be zero?
- A.‖δx‖ * ‖b‖ ≤ condNum A * ‖δb‖ * ‖x‖
- B.‖δx‖ * ‖x‖ ≤ condNum A * ‖δb‖ * ‖b‖
- C.condNum A * ‖δb‖ * ‖x‖ ≤ ‖δx‖ * ‖b‖
- D.‖δx‖ ≤ condNum A * ‖δb‖
7.
Explicit Euler is applied to $y' = -200y$ on $[0, 1]$ with $N$ equal steps ( $h = 1/N$ ). What is the smallest $N$ for which the numerical solution decays, i.e. $|1 + h\lambda| < 1$ ?
8.
Write rk4(f, y0, t_end, n) that applies $n$ steps of the classical fourth-order Runge–Kutta method to $y' = f(t, y)$ , $y(0) = y_0$ , with step $h = t_{\text{end}}/n$ , and returns the approximation to $y(t_{\text{end}})$ .
Computational — Practice
9.
Let $A \in \R^{m \times n}$ ( $m > n$ ) have full column rank and 2-norm condition number $\kappa_2(A) = 10^8$ . Which statements are true? Choose all that apply.
- A. $\kappa_2(A^TA) = 10^{16}$ , so the normal equations may lose all accuracy in double precision.
- B.Householder QR followed by $Rx = Q^Tb$ is backward stable for the least-squares problem.
- C.The least-squares solution is unique.
- D.The minimal residual $\|Ax - b\|_2$ is $0$ .
- E.The normal equations are both cheaper and more accurate than QR.
10.
Which of these methods are A-stable, i.e. $|R(z)| \le 1$ for every complex $z$ with $\operatorname{Re} z \le 0$ ? Choose all that apply.
- A.Backward Euler, $R(z) = \frac{1}{1 - z}$
- B.The trapezoidal rule, $R(z) = \frac{1 + z/2}{1 - z/2}$
- C.Explicit Euler, $R(z) = 1 + z$
- D.Classical RK4

Answer key — Numerical analysis

1.
$\|A\|_\infty = 4$ and $A^{-1} = \mathrm{diag}(0.25, 250)$ , so $\|A^{-1}\|_\infty = 250$ and $\kappa_\infty(A) = 1000 = \max|d_i|/\min|d_i|$ . Note that rescaling the second equation by $1000$ would make $\kappa = 1$ : diagonal ill-conditioning can often be removed by scaling.
2.
The statement says the backward error is about $10^{-16}$ , so the algorithm behaved in a backward-stable way. By Theorem 2 the relative forward error is at most about $\kappa(A) \cdot 10^{-16}$ , which may be large if $A$ is ill conditioned.
3.
The relative error is about $\kappa(A)u \approx 10^{10} \cdot 10^{-16} = 10^{-6}$ : about $6$ correct significant digits. Rule of thumb: $\kappa \approx 10^k$ costs about $k$ of the $16$ digits.
4.
Only $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ fails: its first pivot is $0$ . With partial pivoting, $PA = \begin{pmatrix}1&1\\0&1\end{pmatrix}$ is already upper triangular. In floating point, a pivot that is merely tiny is just as dangerous, which is why partial pivoting chooses the largest available pivot.
5.
Cost (three times as many flops), sparsity (inverses fill in) and backward stability (the inverse-based solution can have a much larger residual) all favour LU. Inverses can be computed, and the problem's condition number does not depend on the method.
6.
Multiplying $\frac{\|\delta x\|}{\|x\|} \le \kappa\frac{\|\delta b\|}{\|b\|}$ by $\|x\|\|b\|$ gives ‖δx‖ * ‖b‖ ≤ condNum A * ‖δb‖ * ‖x‖, which is what relative_error_bound proves. Formal statements prefer this form because Lean's division by zero returns zero.
7.
We need $h \cdot 200 < 2$ , i.e. $h < 0.01$ , i.e. $N > 100$ : the smallest choice is $N = 101$ . The solution itself, $e^{-200t}$ , is negligible after $t = 0.05$ , yet stability still forces more than $100$ steps — that is stiffness. Backward Euler is stable for every $N$ .

def rk4(f, y0, t_end, n):
    h = t_end / n
    t, y = 0.0, y0
    for _ in range(n):
        k1 = f(t, y)
        k2 = f(t + h / 2, y + h * k1 / 2)
        k3 = f(t + h / 2, y + h * k2 / 2)
        k4 = f(t + h, y + h * k3)
        y = y + h * (k1 + 2 * k2 + 2 * k3 + k4) / 6
        t += h
    return y

The error ratio near $16 = 2^4$ when $h$ is halved is the signature of order $4$ . When $f$ depends only on $t$ , RK4 reduces to Simpson's rule, which is exact for cubics.

9.
True: $\kappa_2(A^TA) = \kappa_2(A)^2 = 10^{16}$ ; Householder QR is backward stable; the solution is unique under full rank. False: the minimal residual is generally non-zero, and the normal equations, though cheaper, are less accurate for ill-conditioned $A$ .
10.
Backward Euler and the trapezoidal rule are A-stable (Theorem 7a). Explicit Euler and RK4 are not, and no explicit Runge–Kutta method can be, because its stability function is a polynomial (Theorem 7b). Dahlquist's barrier adds that A-stable linear multistep methods have order at most $2$ .