Numerical linear algebra (source code)

= Numerical linear algebra
{wiki}

<Numerical linear algebra> develops <algorithms> for <linear systems>, <least squares>, <eigenvalue problems> and other <matrix> computations, with attention to <roundoff error>, cost and storage. A mathematically equivalent formula can behave very differently in <floating-point arithmetic>: solving through an <LU decomposition> avoids forming an explicit <matrix inverse>, while a <QR decomposition> gives an orthogonal route to <least squares>.

The central distinction is between accuracy of the computed answer and accuracy of the problem it solves. For $Ax=b$, an approximate <vector> $\widehat x$ has <linear-system residual> $r=b-A\widehat x$. A small <linear-system residual> need not imply a small <forward error> when the <condition number> is large. For the exact example
$$
A=\begin{pmatrix}1&0\\0&10^{-12}\end{pmatrix},\qquad b=\begin{pmatrix}1\\10^{-12}\end{pmatrix},
$$
the solution is $x=(1,1)^T$, whereas $\widehat x=(1,0)^T$ has <Euclidean norm> residual $10^{-12}$ but <Euclidean norm> error $1$. Here the <condition number> in the <spectral norm> is $10^{12}$. The lost component barely changes the equations because its coefficient is tiny.

<Direct linear solvers> such as <Gaussian elimination> factor a <matrix>; <iterative methods> such as <conjugate gradient> successively improve a <vector>. For a large <sparse matrix>, <fill-in> and <matrix preconditioning> can matter as much as arithmetic count. The task is to preserve the structure that makes a computation accurate and affordable.