Numerical Linear Algebra

Cholesky Factorization

QR Factorization

LU Factorization

$A = R^T R$

$ A $ symmetric positive definite

$ R $ upper triangular

$ A = LU $

$ A = QR $

$ A\in\mathbb{R}^{m\times n}, m\geq n $

$ Q $ orthogonal

$ R $ upper trapezoidal

$ A\in\mathbb{R}^{n\times n} $

$ L $ unit lower triangular

$ U $ upper triangular

Numerical stability

$ \sum_{k=1}^i r_{ki}^2 = a_{ii} \Rightarrow r_{ki}^2 \leq a_{ii} $

excellent numerical stability

runs to completion if $ \kappa_2(A) d_n u < 1$

Householder

Givens

Gaussian elimination

Pivoting

$ a_{ij}^{(k+1)} = a_{ij}^{(k)} - \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}} a_{kj}^{(k)} $

ensure $ a_{kk}^{(k)} $ isn't too small

Partial pivoting

Complete pivoting

Rook pivoting

Wilkinson

$ \frac{\lVert \Delta A \rVert_\infty}{\lVert A \rVert_\infty} \leq p(n) \rho_n u $

$ PA = LU $