Norm

The vector p-norms are intuitive

$$ |\textbf{x}|_p=\left(\sum_{i=1}^n|x_i|^p\right)^{1/p}.$$

In general \(|\textbf{x}|_1\ge|\textbf{x}|_2\ge|\textbf{x}|_\infty\). In words, the vector 1-norm is the absolute sum of the vector, vector p-norm is the absolute sum of the vector\(~^p\), from which we can deduce that the vector \(\infty\)-norm is the component with maximum absolute value. Matrix norms are less intuitive, as they are the induced norms of the vector p-norms
$$ |A|_p = \max_{x\neq0}\frac{|Ax|_p}{|x|_p}.$$

For this class, it is sufficient to remember that:

1. matrix 1-norm is the maximum absolute column sum
2. matrix \(\infty\)-norm is the maximum absolute row sum
3. matrix 2-norm is the largest singular value

The first two are easy to remember by considering an \(n\times 1\) matrix, as it must have the same norm as the corresponding vector.

Condition Number

Given a function \(f\) of a variable (or many variables) \(x\), the condition number

$$ cond=\lim\limits_{x’\rightarrow x}\frac{|(f(x’)-f(x))/f(x)|}{|(x’-x)/x|}$$

In words, it is the magnitude of the ratio of the maximum forward error to the maximum backward error. Physically, the condition number measures the sensitivity of the output to a small change in the input. The Wikipedia page for it is quite nice. All we need to realize here are:

1. Large condition number (>>1) implies the output is sensitive to changes in input, thus the problem is ill-conditioned.
2. Small condition number (~1) means the error in the output is similar in size to the error in the input.
3. Errors in the solution due to large condition number have nothing to do with the stability of the algorithm in use, truncation error or rounding error.

In practical situations, we just want to know how to compute the condition number in specific cases, so here it is:

1. In algebraic problems where \(f\) maps a real number \(x\) to another real number \(f(x)\)
   $$ cond=\frac{df(x)/f(x)}{dx/x}=\frac{x}{f(x)}f'(x).$$
   For example:
   $$cond(a+x)=\frac{x}{a+x}\cdot 1=\frac{x}{a+x},$$
   $$cond(ax)=\frac{x}{ax}\cdot a=1,$$
   Therefore addition is potentially ill-conditioned, whereas multiplication is never so.
2. In linear system problems where \(f=A\) is a matrix that maps a vector \(x=\textbf{x}\) to another vector \(A\textbf{x}\), the condition number
   $$ cond=|A||A|^{-1},$$
   depends on the choice of norm for the matrix.