NLA MT25, Linear systems
Flashcards
What are the pros and cons of solving (consistent) linear systems with QR factorisation compared to LU factorisation?
- Pros: QR is unconditionally backward stable. LU + partial pivoting is also backward stable in practice, but only up to the growth factor $\rho _ n = \|U\|/\|A\|$, which can in principle be exponentially large for pathological matrices.
- Cons: QR is around twice as slow as LU ($4n^3/3$ vs $2n^3/3$ flops to leading order).
@State a fact about the backwards stability of a certain class of linear systems.
Triangular linear systems can be solved in a backward stable manner, i.e. if $R$ is an upper or lower triangular linear system $Rx = b$, then the computed solution satisfies
\[(R + \Delta R) \hat x = b, \quad \vert \vert \Delta R \vert \vert = O(\epsilon \vert \vert R \vert \vert )\]for some $\Delta R$, $\hat x$.
Stability analysis
How are linear systems solved in a backward stable manner? You may appeal to a useful result.
Two parts. The triangular solves $Ly = b$, $Ux = y$ are unconditionally backward stable (∆triangular-systems-backward-stable). The catch is the LU factorisation: the computed $\hat L \hat U$ reproduces $A$ only to within $\|L\| \, \|U\|$, so the whole solve is backward stable only when $\|L\| \, \|U\| = O(\|A\|)$ (∆lu-backward-stable-solve-condition). Partial pivoting makes that growth-factor condition hold in practice, though not in the worst case. For an unconditional guarantee, use QR instead.
Bite-sized
Linear-system setup: given square $A \in \mathbb R^{n \times n}$ and $b$, find $x$ such that $A x = b$. The default solver is LU with partial pivoting for general $A$, and Cholesky for $A \succ 0$.
For a backward-stable linear-system solve with $\ \vert \Delta A\ \vert \le \epsilon \ \vert A\ \vert $, the relative error of the computed solution is bounded by $\ \vert \hat x - x\ \vert / \ \vert x\ \vert \le $ $\epsilon \kappa _ 2(A) + O(\epsilon^2)$. The condition number is the amplification factor: when $\epsilon \kappa _ 2(A) > 1$ the solution may be useless, but the algorithm is not at fault — the problem is ill-conditioned.
When should you prefer the SVD over LU/QR to solve $Ax = b$?
Almost never for the standard problem — SVD is roughly $10\times$ slower than QR and $\approx 20\times$ slower than LU. The SVD pays off when $A$ is (nearly) rank-deficient: it gives the minimum-norm least-squares solution via the pseudoinverse, while LU and QR fail outright on singular systems. The SVD also pays off when you need spectral information about $A$ alongside the solution.
Flop counts to leading order for solving $A x = b$ with square $A \in \mathbb R^{n \times n}$: LU costs $\tfrac{2}{3} n^3$, QR costs $\tfrac{4}{3} n^3$, SVD-based costs around $\tfrac{20}{3} n^3$. (Plus $O(n^2)$ for the back-substitution after factorisation.)