How are norms different from absolute values?

Hopefully without getting too complicated, how is a norm different from an absolute value?

In context, I am trying to understand relative stability of an algorithim:

Using the inequality $\frac{|(x_0)- \tilde{f}(\epsilon, x_0)|}{|f(x_0)|} \leq \sigma_{rel} ||\epsilon|| + o(||\epsilon||)$

For which $\sigma_{rel}$ describes the relative stability.

And $||\epsilon||$ is the maximum rounding error of an elementary function: $||\epsilon|| = \mbox{max} |\epsilon_i|, i=1,...n$, $\epsilon = (\epsilon_1,...,\epsilon_n)$.

After reading some of the wikipedia article on norms, I could not take away much other than a norm is positive and a length. I am confused about the statement that it is a function...

Any help trying to understand this would be great, thanks!

The absolute value is a particular instance of a norm. Or perhaps, you can think of norms as functions $\mathbf{V}\to\mathbb{R}$ where $\mathbf{V}$ is a vector space over a field $\mathbf{F}$, and "absolute values" are "norms on the base field".

The absolute value is a function $|\>|\colon\mathbb{R}\to[0,\infty)$; given any real number $r$, you get a nonnegative real number that we write $|r|$, and which satisfies the following properties:

1. $|x|\geq 0$ for all $x\in\mathbb{R}$; $|x|=0$ if and only if $x=0$.
2. $|rx| = |r||x|$ for all $r,x$.
3. $|x+y| \leq |x|+|y|$.

It's a real valued function of real variable, because it takes a real number as an input, and gives a (nonnegative) real number as an output. It's just that instead of calling the function, say, $f$, and writing the output as $f(x)$, we call the function "$|\>|$" and write the output as $|x|$.

Similarly, we have the modulus function for complex numbers, $|\>|\colon\mathbb{C}\to[0,\infty)$, defined by $|z| = \sqrt{z\overline{z}}$, and which also satisfies the three conditions above.

If $\mathbf{V}$ is a vector space over $\mathbb{R}$, then a norm on $\mathbf{V}$ is a function $||\>||\colon \mathbf{V}\to[0,\infty)$ that generalizes the absolute value; it must satisfy:

• $||\mathbf{x}|| \geq 0$ for all $\mathbf{x}\in\mathbf{V}$; $||\mathbf{x}||=0$ if and only if $\mathbf{x}=\mathbf{0}$.
• $||r\mathbf{x}|| = |r|\,||\mathbf{x}||$ for all $r\in\mathbb{R}$, all $\mathbf{x}\in\mathbf{V}$.
• $||\mathbf{x}+\mathbf{y}|| \leq ||\mathbf{x}|| + ||\mathbf{y}||$ for all $\mathbf{x},\mathbf{y}\in\mathbf{V}$.

Again, this is a function: given any vector $\mathbf{x}$ in the domain, $||\mathbf{x}||$ is the output of the function (a nonnegative real number).

In particular, if you view $\mathbb{R}$ as a vector space over itself, then the absolute value gives a norm on $\mathbb{R}$.

For vector spaces over $\mathbb{C}$, you replace the absolute value of $r$ in the second property with the modulus of $r$.

The norm you describe in your post, $||\epsilon||=\max|\epsilon_i|$ is a particular norm that can be placed on $\mathbb{R}^n$; there are many norms that can be defined on $\mathbb{R}^n$.

The notion of norm on a vector space can be done with any field that is contained in $\mathbb{C}$, by restricting the modulus to that field.

Added. One can also extend the notion of norm by starting with any field $\mathbf{F}$, such as the rationals, simply asking for an "absolute value" function $|\>|\colon \mathbf{F}\to [0,\infty)$ that satisfies properties 1, 2, and 3 above. Then you extend the notion of norm for any vector space over that field. It is common to refer to such "absolute values" as "norms" so as not to confuse them with the usual absolute value. One classical example, mentioned by Asaf, are the $p$-adic norms on the rationals. First, fix a prime $p$; given an integer $p$, we define the $p$-order of $a$ to be the largest power of $p$ that divides $a$: that is, $\mathrm{ord}_p(a) = n$ if and only if $p^n$ divides $a$ and $p^{n+1}$ does not divide $a$. We formally set $\mathrm{ord}_p(0)=\infty$. We then extend this to the rationals: given a rational $\frac{a}{b}$, we let $\mathrm{o}_p(\frac{a}{b}) = \mathrm{ord}_p(a) - \mathrm{ord}_p(b)$. Finally, we define the $p$-adic norm on the rationals, $||\>||_p\colon\mathbb{Q}\to[0,\infty)$ by $||\frac{a}{b}||_p = p^{-o_p(a/b)}$. (You can use bases other than $p$; they amount to what are called "equivalent norms").

Here you really want to think of $||\>||_p$ as a kind of "non-standard absolute value" on the rationals; it leads to a lot of interesting mathematics, beginning with the $p$-adic numbers, if you use $||\>||_p$ to define "Cauchy-sequences" instead of $|\>|$ and do the same construction that leads to the reals in the latter case.