Numerical linear algebra

Remarks

An algorithm is backward stable when its computed answer is the exact answer for slightly perturbed data. For a linear system this means $(A + \delta A)\hat x = b$ with $\norm{\delta A}$ of the order of the unit roundoff times $\norm{A}$. For a backward stable method, the relative error of $\hat x$ is roughly bounded by the condition number of $A$ times the unit roundoff. Example: Householder QR decomposition solves least squares problems in a backward stable way with about $2mn^2 - \tfrac{2}{3}n^3$ operations for an $m \times n$ matrix. Non-example: computing the exact determinant of an integer matrix with rational arithmetic is a task of computer algebra. It is not numerical linear algebra, because it does not work in finite precision and has no rounding error to analyse. Direct methods, such as LU decomposition, finish in a fixed number of steps; iterative methods, such as power iteration, improve an approximation step by step.