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