Skip to main content

Subsection 1.1.1 Why norms?

The following exercises expose some of the issues that we encounter when computing.

We start by computing \(b = U x \text{,}\) where \(U \) is upper triangular.

Homework 1.1.1.1.

Compute

\begin{equation*} \left(\begin{array}{rrr} 1 \amp -2 \amp 1 \\ 0 \amp -1 \amp -1 \\ \phantom{-}0 \amp \phantom{-}0 \amp \phantom{-}2 \end{array}\right) \left( \begin{array}{r} -1 \\ 2 \\ 1 \end{array} \right) = \end{equation*}
Solution
\begin{equation*} \left(\begin{array}{rrr} 1 \amp -2 \amp 1 \\ 0 \amp -1 \amp -1 \\ \phantom{-}0 \amp \phantom{-}0 \amp \phantom{-}2 \end{array}\right) \left( \begin{array}{r} -1 \\ 2 \\ 1 \end{array} \right) = \left(\begin{array}{r} -4\\ -3\\ 2 \end{array}\right) \end{equation*}

Next, let's examine the slightly more difficult problem of finding a vector \(x \) that satisfies \(U x = b \text{.}\)

Homework 1.1.1.2.

Solve

\begin{equation*} \left(\begin{array}{rrr} 1 \amp -2 \amp 1 \\ 0 \amp -1 \amp -1 \\ \phantom{-}0 \amp \phantom{-}0 \amp \phantom{-}2 \end{array}\right) \left( \begin{array}{c} \chi_0 \\ \chi_1 \\ \chi_2 \end{array} \right) = \left(\begin{array}{r} -4\\ -3\\ 2 \end{array}\right) \end{equation*}
Solution

We can recognize the relation between this problem and Homework 1.1.1.1 and hence deduce the answer without computation:

\begin{equation*} \left( \begin{array}{c} \chi_0 \\ \chi_1 \\ \chi_2 \end{array} \right) = \left( \begin{array}{r} -1 \\ 2 \\ 1 \end{array} \right) \end{equation*}

The point of these two homework exercises is that if one creates a (nonsingular) \(n \times n \) matrix \(U\) and vector \(x \) of size \(n \text{,}\) then computing \(b = U x \) followed by solving \(U \widehat x = b\) should leave us with a vector \(\widehat x \) such that \(x = \widehat x \text{.}\)

Remark 1.1.1.1.

We don't "teach" Matlab in this course. Instead, we think that Matlab is intuitive enough that we can figure out what the various commands mean. We can always investigate them by typing 

help <command>

in the command window. For example, for this unit you may want to execute 

help format
help rng
help rand
help triu
help *
help \
help diag
help abs
help min
help max

If you want to learn more about Matlab, you may want to take some of the tutorials offered by Mathworks at

https://www.mathworks.com/support/learn-with-matlab-tutorials.html.

Let us see if Matlab can compute the solution of a triangular matrix correctly.

Homework 1.1.1.3.

In Matlab's command window, create a random upper triangular matrix \(U \text{:}\)

format long
		
rng( 0 );      
n = 3          
U = triu( rand( n,n ) )
x = rand( n,1 )

Report results in long format. Seed the random number generator so that we all create the same random matrix \(U \) and vector \(x \text{.}\)

b = U * x;

Compute right-hand side \(b \) from known solution \(x \text{.}\)

xhat = U \ b;

Solve \(U \widehat x = b \text{.}\)

xhat - x

Report the difference between \(\widehat x \) and \(x \text{.}\)

What do we notice?

Next, check how close \(U \widehat x \) is to \(b = U x \text{:}\)

b - U * xhat

This is known as the residual.

What do we notice?

Solution

A script with the described commands can be found in

Some things we observe:

  • \(\widehat x - x \) does not equal zero. This is due to the fact that the computer stores floating point numbers and computes with floating point arithmetic, and as a result roundoff error happens.

  • The difference is small (notice the 1.0e-15* before the vector, which shows that each entry in \(\widehat x - x \) is around \(10^{-15} \text{.}\)

  • The residual \(b - U \widehat x \) is small.

  • Repeating this with a much larger \(n \) make things cumbersome since very long vectors are then printed.

To be able to compare more easily, we will compute the Euclidean length of \(\widehat x - x \) instead using the Matlab command norm( xhat - x ). By adding a semicolon at the end of Matlab commands, we suppress output.

Homework 1.1.1.4.

Execute

format long
		
rng( 0 );      
n = 100;          
U = triu( rand( n,n ) );
x = rand( n,1 );

Report results in long format.

Seed the random number generator so that we all create the same random matrix \(U \) and vector \(x \text{.}\)

b = U * x;

Compute right-hand side \(b \) from known solution \(x \text{.}\)

xhat = U \ b;

Solve \(U \widehat x = b \)

norm( xhat - x )

Report the Euclidean length of the difference between \(\widehat x \) and \(x \text{.}\)

What do we notice?

Next, check how close \(U \widehat x \) is to \(b = U x \text{,}\) again using the Euclidean length:

norm( b - U * xhat  )

What do we notice?

Solution

A script with the described commands can be found in Assignments/Week01/matlab/Test_Upper_triangular_solve_100.m

Some things we observe:

  • \(norm( \widehat x - x ) \text{,}\) the Euclidean length of \(\widehat x - x \text{,}\) is huge. Matlab computed the wrong answer!

  • However, the computed \(\widehat x \) solves a problem that corresponds to a slightly different right-hand side. Thus, \(\widehat x \) appears to be the solution to an only slightly changed problem.

The next exercise helps us gain insight into what is going on.

Homework 1.1.1.5.
Continuing with the U, x, b, and xhat from Homework 1.1.1.4, consider

  • When is an upper triangular matrix singular?

  • How large is the smallest element on the diagonal of the U from Homework 1.1.1.4? (min( abs( diag( U ) ) ) returns it!)

  • If \(U \) were singular, how many solutions to \(U \widehat x = b \) would there be? How can we characterize them?

  • What is the relationship between \(\widehat x - x \) and \(U \text{?}\)

What have we learned?
Solution

  • When is an upper triangular matrix singular?

    Answer:

    If and only if there is a zero on its diagonal.

  • How large is the smallest element on the diagonal of the U from Homework 1.1.1.4? (min( abs( diag( U ) ) ) returns it!)

    Answer:

    It is small in magnitude. This is not surprising, since it is a random number and hence as the matrix size increases, the chance of placing a small entry (in magnitude) on the diagonal increases.

  • If \(U \) were singular, how many solutions to \(U \widehat x = b \) would there be? How can we characterize them?

    Answer:

    The might be no answer or there might be an infinite number. Any vector in the null space can be added to a specific solution to create another solution.

    In the setting of this problem, we generated a right-hand side from a known solution. Hence, there would be an infinite number of solutions (unless roundoff error in computing the right-hand side created a problem for which there is no solution).

  • What is the relationship between \(\widehat x - x \) and \(U \text{?}\)

    Answer:

    It maps almost to the zero vector. In other words, it is close to a vector in the null space of the matrix \(U \) that has its smallest entry (in magnitude) on the diagonal changed to a zero.

What have we learned?

The :"wrong" answer that Matlab computed was due to the fact that matrix \(U \) was almost singular.

To mathematically qualify and quantify all this, we need to be able to talk about "small" and "large" vectors, and "small" and "large" matrices. For that, we need to generalize the notion of length. By the end of this week, this will give us some of the tools to more fully understand what we have observed.

login