Numerical Linear Algebra

Cholesky Factorization

QR Factorization

LU Factorization

A=RTR

\( 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 \)