Exercises - Introduction to Scientific Computing

Practice implementing and analyzing direct methods for linear systems.

\begin{pmatrix} 3 & 1 & 2 \\ 0 & 2 & 4 \\ 0 & 0 & 5 \end{pmatrix}

\begin{pmatrix} 2 & 0 & 0 \\ 1 & 3 & 0 \\ 4 & 2 & 1 \end{pmatrix}

Solve the following system using Gaussian elimination (show all steps):

\begin{aligned} x_1 + 2x_2 + 3x_3 &= 6 \\ 2x_1 + 3x_2 + x_3 &= 6 \\ 3x_1 + x_2 + 2x_3 &= 6 \end{aligned}

(a) Find the LU decomposition of:
$\mathcal{A} = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix}$
(4)
(b) Use your decomposition to solve $\mathcal{A}\mathbf{x} = (4, 10, 24)^T$ .
(c) Solve $\mathcal{A}\mathbf{x} = (3, 7, 17)^T$ (same LU, different RHS).

(a) Verify that back substitution requires exactly $n^2$ flops.
(b) Verify that Gaussian elimination requires $\frac{2}{3}n^3 + \mathcal{O}(n^2)$ flops.
(c) For $n = 1000$ , how many times faster is solving with a precomputed LU versus fresh Gaussian elimination?

Consider: $$

\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}

(a) Why does Gaussian elimination without pivoting fail?
(b) Apply Gaussian elimination with partial pivoting.
(c) Write out the $\mathcal{P}\mathcal{A} = \mathcal{L}\mathcal{U}$ decomposition.

Implement the following in Python:

Test on random $100 \times 100$ matrices and compare with scipy.linalg.lu.

(a) Create a $10 \times 10$ matrix where pivoting makes a significant difference. Solve the system with and without pivoting and compare errors.
(b) Investigate the Hilbert matrix: compare the computed solution to the exact solution for increasing matrix sizes.

Self-Assessment Questions¶

Test your understanding with these conceptual questions:

Complexity: How many flops does Gaussian elimination require for an $n \times n$ matrix?
LU Advantage: If you need to solve $\mathcal{A}\mathbf{x} = \mathbf{b}$ for 100 different $\mathbf{b}$ vectors, is it better to use Gaussian elimination 100 times or compute LU once?
Pivoting: Why does dividing by small numbers cause problems in floating point arithmetic?
Back Substitution: Why is back substitution $\mathcal{O}(n^2)$ rather than $\mathcal{O}(n^3)$ ?