Vector and Matrix Norms

To talk about the size of an error in a vector answer, we need the size of a vector. The length from the dot product, $\sqrt{\mathbf{x}\cdot\mathbf{x}}$, is one choice; numerical work also uses two others that are cheaper and often easier to bound.

For $\mathbf{x} = (x_1, \ldots, x_n)$: $$\lVert\mathbf{x}\rVert_1 = \sum|x_i|,\quad \lVert\mathbf{x}\rVert_2 = \sqrt{\sum x_i^{2}},\quad \lVert\mathbf{x}\rVert_\infty = \max|x_i|.$$ Each is a norm: positive for $\mathbf{x} \ne \mathbf{0}$, scaled by $|c|$ when $\mathbf{x}$ is multiplied by $c$, and obeying the triangle inequality $\lVert\mathbf{x} + \mathbf{y}\rVert \le \lVert\mathbf{x}\rVert + \lVert\mathbf{y}\rVert$.

A matrix norm measures how much $A$ can stretch a vector: $$\lVert A\rVert = \max_{\mathbf{x} \ne \mathbf{0}}\frac{\lVert A\mathbf{x}\rVert}{\lVert\mathbf{x}\rVert}.$$ So $\lVert A\mathbf{x}\rVert \le \lVert A\rVert\lVert\mathbf{x}\rVert$ always.

Why keep three norms? In $n$ dimensions they never differ by more than a fixed factor: for example $\lVert\mathbf{x}\rVert_\infty \le \lVert\mathbf{x}\rVert_2 \le \sqrt{n}\,\lVert\mathbf{x}\rVert_\infty$. So "the error goes to zero" means the same thing in all of them, and we pick whichever is easiest to compute or to bound. The $\infty$-norm answers "how wrong is the worst entry?", which is often what we want to know. Errors in a vector answer are then measured as $\frac{\lVert\tilde{\mathbf{x}} - \mathbf{x}\rVert}{\lVert\mathbf{x}\rVert}$, just like relative error for numbers.