# 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:

# 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:

1. ||x||2 ≥ 0 and ||x||2 = 0 if and only if x = 0.
2. ||a x||2 = |a| ||x||2 for any scalar a.
3. ||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 MMT. 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 MMT is an O(n3) operation.
• Calculating Mv is an O(n2) operation.

Therefore, if we calculate M(MTv) instead of calculating (MMT)v, we have an O(n2) operation instead of an O(n3) 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 ∞.

# 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 MMT. 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.

# 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.

# Question 1

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

# Question 2

What are the 1 and ∞ norms of the matrix

# 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