MATH347

MATH347 L15: Matrix factorizations

New concepts:
- Gaussian elimination as $𝑳 𝑼$
- Gram-Schmidt as $𝑸 𝑹$
- Solving linear systems

Solving

𝑨 𝒙 = 𝒃

by Gaussian elimination

Recall from Lesson 9

Gaussian elimination produces a sequence matrices similar to $𝑨 \in ℝ^{m \times m}$
$𝑨 = 𝑨^{(0)} \sim 𝑨^{(1)} \sim \dots \sim 𝑨^{(k)} \sim \dots \sim 𝑨^{(m - 1)}$
Step $k$ produces zeros underneath diagonal position $(k, k)$
Step $k$ can be represented as multiplication by matrix
$𝑨^{(k)} = 𝑳_{_{k}} 𝑨^{(k - 1)}, 𝑳_{k} = (\begin{array}{ccccc} 1 & \dots & 0 & \dots & 1 \\ 0 & ⋱ & 0 & \dots & 0 \\ 0 & \dots & 1 & \dots & 0 \\ 0 & \dots & - l_{k + 1, k} & \dots & 0 \\ ⋮ & \dots & ⋮ & ⋱ & ⋮ \\ 0 & \dots & - l_{m, k} & \dots & 1 \end{array}), l_{j, k} = \frac{a_{j, k}^{(k - 1)}_{}}{a_{k, k}^{(k - 1)}}, 𝑨^{(k)} = [a_{i, j}^{(k)}]$
All $m - 1$ steps produce an upper triangular matrix
$𝑳_{m - 1} \dots 𝑳_{2} 𝑳_{1} 𝑨 = 𝑼 \Rightarrow 𝑨 = 𝑳_{1}^{- 1} 𝑳_{2}^{- 1} \dots 𝑳_{m - 1}^{- 1} 𝑼 = 𝑳 𝑼$
With permutations $𝑷 𝑨 =^{} 𝑳 𝑼$ (Matlab [L,U,P]=lu(A), A=P'*L*U)

Matrix formulation of Gaussian elimination

With known $L U$ -factorization: $𝑨 𝒙 = 𝒃 \Rightarrow (𝑳 𝑼) 𝒙 = 𝑷 𝒃 \Rightarrow 𝑳 (𝑼 𝒙) = 𝑷 𝒃$
To solve $𝑨 𝒙 = 𝒃$ :
1. Carry out $L U$ -factorization: $𝑷^{T} 𝑳 𝑼 = 𝑨$
2. Solve $𝑳 𝒚 = 𝒄 = 𝑷 𝒃$ by forward substitution to find $𝒚$
3. Solve $𝑼 𝒙 = 𝒚$ by backward substitution
FLOP = floating point operation = one multiplication and one addition
Operation counts: how many FLOPS in each step?
1. Each $𝑳_{k} 𝑨^{(k - 1)}$ costs ${(m - k)}^{2}$ FLOPS. Overall
  ${(m - 1)}^{2} + {(m - 2)}^{2} + \dots + 1^{2} = \frac{m (m - 1) (2 m - 1)}{6} \approx \frac{m^{3}}{3}$
2. Forward substitution step $k$ costs $k$ flops
  $1 + 2 + \dots + m = \frac{m (m + 1)}{2} \approx \frac{m^{2}}{2}$
3. Backward substitution cost is identical $m (m + 1) / 2 \approx m^{2} / 2$ /

Gram-Schmidt as

𝑸 𝑹

Recall from Lesson 13

Orthonormalization of columns of $𝑨$ is also a factorization
$𝑨 = [\begin{array}{llll} 𝒂_{1} & 𝒂_{2} & \dots & 𝒂_{n} \end{array}] = [\begin{array}{llll} 𝒒_{1} & 𝒒_{2} & \dots & 𝒒_{n} \end{array}] [\begin{array}{llll} r_{11} & r_{12} & \dots & r_{1 n} \\ 0 & r_{22} & \dots & r_{2 n} \\ ⋮ & ⋱ \\ 0 & 0 & \dots & r_{n n} \end{array}] = 𝑸 𝑹$ $\begin{array}{l} 𝒂_{1} = r_{11} 𝒒_{1} \\ 𝒂_{2} = r_{12} 𝒒_{1} + r_{2 2} 𝒒_{2} \\ 𝒂_{3} = r_{13} 𝒒_{1} + r_{23} 𝒒_{2} + r_{3 3} 𝒒_{3} \\ ⋮ \\ 𝒂_{n} = r_{1 n} 𝒒_{1} + r_{2 n} 𝒒_{2} + r_{3 n} 𝒒_{3} + \dots + r_{n n} 𝒒_{n} \end{array} \begin{array}{l} 𝒒_{1} = 𝒂_{1} / r_{11} \\ 𝒒_{2} = (𝒂_{2} - r_{12} 𝒒_{1}) / r_{2 2} \\ 𝒒_{3} = (𝒂_{3} - r_{13} 𝒒_{1} - r_{23} 𝒒_{2}) / r_{3 3} \\ ⋮ \end{array}$
Operation count:
- $r_{j k} = 𝒒_{j}^{T} 𝒂_{k}$ costs $m$ FLOPS
- There are $1 + 2 + \dots + n$ components in $𝑹$ , Overall cost $n (n + 1) m / 2$
With permutations $𝑨 𝑷 = 𝑸 𝑹$ (Matlab [Q,R,P]=qr(A) )

Solving linear

𝑨 𝒙 = 𝒃

,

𝑨 \in ℝ^{m \times m}

systems by

Q R

With known $Q R$ -factorization: $𝑨 𝒙 = 𝒃 \Rightarrow (𝑸 𝑹 𝑷^{T}) 𝒙 = 𝒃 \Rightarrow 𝑹 𝒚 = 𝑸^{T} 𝒃$
To solve $𝑨 𝒙 = 𝒃$ :
1. Carry out $Q R$ -factorization: $𝑸 𝑹 𝑷^{T} = 𝑨$
2. Compute $𝒄 = 𝑸^{T} 𝒃$
3. Solve $𝑹 𝒚 = 𝒄$ by backward substitution
4. Find $𝒙 = 𝑷^{T} 𝒚$
Operation counts: how many FLOPS in each step?
1. $Q R$ -factorization $m^{2} (m + 1) / 2 \approx m^{3} / 2$
2. Compute $𝒄$ , $m^{2}$
3. Backward substitution $m (m + 1) / 2 \approx m^{2} / 2$