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
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
We can recognize the relation between this problem and Homework 1.1.1.1 and hence deduce the answer without computation:
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/learnwithmatlabtutorials.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 righthand 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?
A script with the described commands can be found in Assignments/Week01/matlab/Test_Upper_triangular_solve_3.m.
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.0e15* 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 righthand 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?
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 righthand 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, considerWhen 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{?}\)

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:
An infinite number. Any vector in the null space can be added to a specific solution to create another 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.
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.