Introduction
Theory
HOWTO
Error Analysis
Examples
Questions
Applications in Engineering
Matlab
Maple

# Introduction

To calculate the relative error of a solution **x** to a
system of linear equations **Mx** = **b**,
we must determine a way of measuring the relative error of a
matrix and a vector. To do this, we need an equivalent version
of the absolute value of a real number. In this topic, we look
at various definitions of norms of vectors and extensions of these
definitions to matrices.

# Background

Useful background for this topic includes:

# References

# Theory

# The 2-Norm

Because the Euclidean norm takes the square root (1/2) of the sum of the squares (2),
it is also known as 2-norm. In this class, we will always refer to the Euclidean
norm by this name. It is also written as ||⋅||_{2}.

# Norms of Matrices

Given a linear circuit, we may define a system of linear equations
**Gv = i** where **G** is a matrix of conductances, **v** is an
unknown vector of voltages, and **i** is a vector of currents.

Given a vector of currents, we may determine the size of the
error by taking the 2-norm of the error vector, which
you have seen in your course on linear algebra.
You have probably also seen these three properties of
a norm ||⋅||_{2}, as well:

- ||
**x**||_{2} ≥ 0 and ||**x**||_{2} = 0 if and only if **x** = **0**.
- ||
*a* **x**||_{2} = |*a*| ||**x**||_{2} for any scalar *a*.
- ||
**x** + **y**||_{2} ≤ ||**x**||_{2} + ||**y**||_{2}

However, as we are dealing with matrices, one further condition
we would like to satisfy is that the norm of the identity matrix is 1, that is,
|||**Id**|||_{2} = 1.

Thus, our next goal is to try to define a technique of defining
the error in the matrix **G**. For this, we need a norm on matrices.
We will denote a matrix norm by three bars and therefore, to summarize
our usage:

- |
*a*| - Absolute value of a scalar
*a*.
- ||
**v**||_{2} - Norm of a vector
**v**.
- |||
**M**|||_{2} - Norm of a matrix
**M**.

The first *norm* which comes to mind is probably to take the square
root of the sum of the squares of all of the entries of the matrix.
Unfortunately, this fails our second *desirable* property of a norm,
namely, for an *n* × *n* identity matrix **Id**, it is quite
easy to determine that |||**Id**||| is the square root of *n*.

# A Better Definition

Given a matrix **M**, let us define the norm of the matrix to be the
maximum amount which it stretches any vector. For example, the vector
(1, 0)^{T} which has norm 1, when multiplied by the matrix **M**

has norm 5, while (0, 1)^{T} multiplied by this matrix has norm 4. In fact,
you can show that there exists a unit vector **v** such that
||**Mv**||_{2} ≈ 6.092681.

It can be shown that this definition of a matrix norm satisfies all of the four
conditions which we have placed on a norm. We could define the matrix norm as

Unfortunately, this is difficult to calculate, however, it can be shown
that this is equivalent to:

The 2-norm of a matrix **M** is the square root of the maximum eigenvalue
of **MM**^{T}. In Matlab:

>> sqrt( max( eig( M*M' ) ) )

We could solve for this using the technique given previously to find the maximum
eigenvalue, however, we should note the following:

- Calculating
**MM**^{T} is an O(*n*^{3}) operation.
- Calculating
**Mv** is an O(*n*^{2}) operation.

Therefore, if we calculate **M**(**M**^{T}**v**) instead of calculating
(**MM**^{T})**v**, we have an O(*n*^{2}) operation instead of
an O(*n*^{3}) operation.

# Other Vector Norms

There are two other definitions of norms on vectors:

- ||
**v**||_{1}: the sum of the absolute values of the entries of **v**
- ||
**v**||_{∞}: the maximum of the absolute values of the entries of **v**

It can be shown that these have similar properties of the 2-norm, that is, if a sequence
converges in the 2-norm, then it converges in the 1-norm and the ∞-norm, and vice versa.

These are also easier to calculate than the 2-norm: no squaring, no square root.

# The 1- and ∞-Matrix Norms

It can be shown that the 1-norm of a matrix **M**, if we use the same definition from above,
may be given by: the maximum column sum of the absolute values of the entries of the matrix, or
using Matlab:

>> max( sum( abs( M ) ) )

It can be shown that the ∞-norm of a matrix **M**, if we use the same definition from above,
may be given by: the maximum row sum of the absolute values of the entries of the matrix, or
using Matlab:

>> max( sum( abs( M' ) ) )

# The Use of the Norm

The most powerful tool which the above matrix norm gives us is the property:

where * may be any one of 1, 2, or ∞.

# HOWTO

# The 2 Norm

As you saw in linear algebra, the 2 norm (or Euclidean norm) of
a vector is the square root of the sum of the squares of the entries
of the vector:

or in Matlab:

norm( v, 2 )
sqrt( sum( v.^2 ) )

The 2 norm |||**M**|||_{2} of a matrix **M** is the square root of the maximum
eigenvalue of **MM**^{T}. We could find this maximum
eigenvalue using the technique described in the previous topic,
and in Matlab, we could calculate:

norm( M, 2 )
sqrt( max( eig( M*M' ) ) ) % all the eigenvalues of M*M' are positive and real if M is real

# The 1 Norm

The 1 norm of a vector is defined as the sum of the absolute values of
the entries of **v**:

or in Matlab:

>> norm( v, 1 );
>> sum( abs( v ) );

The corresponding 1 norm |||**M**|||_{1} of a matrix **M** is defined as the maximum
absolute column sum. In Matlab, this is given by:

>> norm( M, 1 )
>> max( sum( abs( M ) ) )

# The ∞ Norm

The ∞ norm of a vector is defined as the maximum absolute entry of
**v**:

or in Matlab:

>> norm( v, Inf )
>> max( abs( v ) )

The corresponding ∞ norm |||**M**|||_{∞} of a matrix **M** is defined as the maximum
absolute row sum. In Matlab, this is given by:

>> norm( M, Inf )
>> max( sum( abs( M' ) ) )

# The Condition Number of a Matrix

The condition number of a matrix **M** is defined as cond(**M**) = |||**M**||| |||**M**^{-1}|||.
For each of the three norms, 1, 2, and ∞ there is a corresponding
condition number for the matrix.

# Error Analysis

Given a system of linear equations **Mx** = **b**, we
never have the actual values of the matrix **M** and we can
never store them exactly, even if we could. Therefore,
there must always be a relative error for our matrix **M**,
and if we define Δ**M** to be this error,
the ratio |||Δ**M**|||/|||**M**|||
is a measurement of the *relative error* the matrix **M**.

Thus, we may state the relative error of our solution **x** is
proportional to the relative error of **M** according to the following
formula:

This statement holds true regardless of the norm used (1, 2, or ∞), so long
as the same norm is used in all cases, including the calculation of the condition
number. Usually using the 1 norm is sufficient.

# Examples

# Example 1

What are the 1 and ∞ norms of the matrix

?
The three absolute column sums are 10, 12, and 10, and thus the
1 norm is |||**M**|||_{1} = 12.

The three absolute row sums are 6, 13, and 13, and
thus the ∞ norm is |||**M**|||_{∞} = 13.

# Example 2

What is the largest 1 or ∞ norm of the **L** matrix found
during the process of the PLU decomposition of an *n* ×
*n* matrix?

As all the entries of **L** are less than or equal to
1, it follows that the maximum 1 and ∞ norms are *n* while
the minimum 1 and ∞ norms are 1.

# Example 3

Using the 1-norm, what is the maximum error in solving for **x** of the system **Mx** = **b**
where **M** is the same matrix as in Question 1,
|||Δ**M**|||_{1} = 0.003 and **b** = (2, -1, 1)^{T}.

Using Matlab, we can solve **Mx** = **b** to get
that **x** = (1,1,1)^{T}. Also, we find that the condition number of the matrix **M** is 22.5,
and therefore, we get that ||Δ**x**||_{1} = 22.5⋅0.003⋅3/12 = 0.016875.

# Questions

# Question 1

What are the 1, 2, and ∞ norms of the vector **v** = (1, -2, 3, 4, -5)^{T}?

Answer: use Matlab

# Question 2

What are the 1 and ∞ norms of the matrix

Answer: use Matlab

# Question 3

Use Matlab to calculate the condition number of the matrix `[1 2 3; 4 5 6; 7 8 10]`
for 1, 2, and ∞ using two techniques each: one using `cond` and the other
using the formulae we have seen. The inverse of a matrix may be found by entering `M^-1`.

# Applications to Engineering

To be filled in later.

# Matlab

The `norm` and `cond` functions find
the norm and condition number of a matrix:

>> M = rand( 5, 5 ); % create a random matrix
>> norm( M, 1 )
>> cond( M, 1 )
>> norm( M, 2 )
>> cond( M, 2 )
>> norm( M, Inf )
>> cond( M, Inf )

For very large matrices, this can be very expensive,
so Matlab provides two estimators of these numbers,
`normest` and `condest`:

>> normest( M, 1 )
>> condest( M, 1 )
>> normest( M, 2 )
>> condest( M, 2 )
>> normest( M, Inf )
>> condest( M, Inf )

# Maple

The norm and condition number of a matrix may be found using the `Norm` and
`ConditionNumber` functions:

M := <<-6, 12, 2.4, 0>|<-1, 2, 10.4, 1>|<3.25, 1, -1.8, 14.8>|<10.25, 0, 2, 1.2>>;
LinearAlgebra[Norm]( M, 1 );
LinearAlgebra[ConditionNumber]( M, 1 );
LinearAlgebra[Norm]( M, 2 );
LinearAlgebra[ConditionNumber]( M, 2 );
LinearAlgebra[Norm]( M, infinity );
LinearAlgebra[ConditionNumber]( M, infinity );

For more help on either of these routines or on the LinearAlgebra
package, enter:

?LinearAlgebra
?LinearAlgebra,Norm
?LinearAlgebra,ConditionNumber