Chapter 13

Alternative System Solvers

We have encountered Gauss elimination methods for solving linear systems. These work well for moderately sized systems (up to a few thousand equations), in particular if they do not pose numerical problems. Ill-conditioned problems are more efficiently attacked using the Householder method below. Huge linear systems (up to a million equations) are more successfully solved with iterative methods. Often times, these linear systems are defined by a sparse matrix, one that has many zero entries, as is illustrated in Figure 13.1. All these alternative methods are the topics of this chapter.

13.1 The Householder Method

Let’s revisit the problem of solving the linear system Au = b, where A is an n× n matrix. We may think of A as n column vectors, each with n elements,

$\left[a_1...a_n\right]u=b.$

In Section 12.2 we examined the classical method of Gauss elimination, or the process of applying shears Gi to the vectors a1 ...an and b in order to convert A to upper triangular form, or

$G_{n-1}...G_{1}Au=G_{n-1}...G_{1}b,$

and then we were able to solve for u with back substitution. Each Gi is a shear matrix, constructed to transform the ith column vector Gi-1 ...G1ai to a vector with zeroes below the diagonal element, ai,i.

As it turns out, Gauss elimination is not the most robust method for solving a linear system. A more numerically stable method may be found by replacing shears with reflections. This is the Householder method.

The Householder method applied to a linear system takes the same form as Gauss elimination. A series of reflections Hi is constructed and applied to the system,

$H_{n-1}...H_{1}Au=H_{n-1}...H_{1}b,$

where each Hi transforms the column vector Hi−1 ... H1ai to a vector with zeroes below the diagonal element. Let’s examine how we construct a Householder transformation Hi.

A simple 2 × 2 matrix

$\left[\begin{array}{rr}\hfill 1& \hfill -2\\ \hfill 1& \hfill 0\end{array}\right]$

will help to illustrate the construction of a Householder transformation. The column vectors of this matrix are illustrated in Sketch 13.1. The first transformation, H1A, reflects a1 onto the e1 axis to the vector ${a^{\prime }}_1=||a_1||e_1$, or

$\begin{array}{rr}\hfill \left[\begin{array}{r}\hfill 1\\ \hfill 1\end{array}\right]\to & \hfill \left[\begin{array}{r}\hfill \sqrt{2}\\ \hfill 0\end{array}\right].\end{array}$

We will reflect about the line L1 illustrated in Sketch 13.1, so we must construct a normal n1 to this line:

$n_1=\frac{a_1-||a_1||e_1}{||a_1-||a_1||e_1||},$

which is simply the normalized difference between the original vector and the target vector (after the reflection). The implicit equation of the line L1 is

$n_1^{\text{T}}x=0,$

and $n_1^{\text{T}}{a}_1$ is the distance of the point (o + a1) to L1. Therefore, the reflection constitutes moving twice the distance to the line in the direction of the normal, so

${\overline{a}}_1=a_1-\left[2n_1^{\text{T}}{a}_1\right]n_1.$

(Notice that $2n_1^{\text{T}}{a}_1$ is a scalar.) To write this reflection in matrix form, we rearrange the terms,

$\begin{array}{cc}{a^{\prime }}_1=& a_1-2n_1\left[n_1^{\text{T}}{a}_1\right]\\ =& \left(I-2n_1{n}_1^{\text{T}}\right)a_1\end{array}$

Notice that $2n_1{n}_1^{\text{T}}$ is a dyadic matrix, as introduced in Section 11.5. We now have the matrix H1 defining one Householder transformation:

$H_1=I-2n_1{n}_1^{\text{T}}.$

This is precisely the reflection we constructed in (11.13)!

Example 13.1

The Householder matrix H1 for our 2 × 2 example is formed with

$n_1=\left[\begin{array}{c}-0.382\\ 0.923\end{array}\right],$

then

$\begin{array}{ccc}{H}_1=& I-2\left[\begin{array}{cc}0.146& -0.353\\ -0.353& 0.853\end{array}\right]=& \left[\begin{array}{cc}0.707& 0.707\\ 0.707& -0.707\end{array}\right].\end{array}$

The transformed matrix is formed from the column vectors

$\begin{array}{ccc}{H}_1{a}_1=\left[\begin{array}{c}\sqrt{2}\\ 0\end{array}\right]& \text{and}& H_1{a}_2=\left[\begin{array}{c}-\sqrt{2}\\ -\sqrt{2}\end{array}\right].\end{array}$

The 2 × 2 example serves only to illustrate the underlying geometry of a reflection matrix. The construction of a general Householder transformation Hi is a little more complicated. Suppose now that we have the following matrix

$\begin{array}{cc}A=& \left[\begin{array}{cccc}{a}_{1,1}& a_{1,2}& a_{1,3}& a_{1,4}\\ 0& a_{2,2}& a_{2,3}& a_{2,4}\\ 0& 0& a_{3,3}& a_{3,4}\\ 0& 0& a_{4,3}& a_{4,4}\end{array}\right].\end{array}$

We need to construct H3 to zero the element a4,3 while preserving A’s upper triangular nature. In other words, we want to preserve the elimination done by previous transformations, H1 and H2. To achieve this, construct

$\begin{array}{cc}{\overline{a}}_3=& \left[\begin{array}{c}0\\ 0\\ a_{3,3}\\ a_{4,3}\end{array}\right],\end{array}$

and then construct H3 so that

$\begin{array}{cc}{H}_3{\overline{a}}_3=\gamma e_3=& \left[\begin{array}{c}0\\ 0\\ \gamma \\ 0\end{array}\right]\end{array},$

where $\text{γ}=\pm ||{\overline{a}}_3||$. The matrix H3 has been designed so that H3a3 will modify only elements a3,3 and a4,3 and the length of a3 will be preserved.

That is the idea, so let’s develop it for n × n matrices. Suppose we have

$\begin{array}{cc}{\overline{a}}_i=& \left[\begin{array}{c}0\\ ⋮\\ 0\\ a_{i,i}\\ ⋮\\ a_{n,i}\end{array}\right].\end{array}$

We want to construct the Householder matrix Hi for the following transformation

$\begin{array}{cc}{H}_i{\overline{a}}_i=\gamma e_i=& \left[\begin{array}{c}0\\ ⋮\\ \gamma \\ ⋮\\ 0\end{array}\right],\end{array}$

where $\gamma \text{=}\pm ||{\overline{a}}_i||$. Just as we developed for the 2 × 2 example,

$\begin{array}{cc}{H}_i=I-2n_i{n}_i^{\text{T}},& \left(13.1\right)\end{array}$

but we make a slight modification of the normal,

$\begin{array}{cc}{n}_i=& \frac{{\overline{a}}_i-\text{γ}{e}_i}{||\cdot ||},\end{array}$

If ${\overline{a}}_i$ is nearly parallel to ei then numerical problems can creep into our construction due to loss of significant digits in subtraction of nearly equal numbers. Therefore, it is better to reflect onto the direction of the ei-axis that represents the largest reflection.

Let $N_i=n_i{n}_i^{\text{T}}$ and note that it is symmetric and idempotent. Properties of Hi include being:

• symmetric: $H_i=H_i^{\text{T}}$, since Ni is symmetric;
• involutary: HiHi = I and thus Hi = Hi−1,
• unitary (orthogonal): $H_i^{\text{T}}{H}_i=I$, and thus Hiv has the same length as v.

Implementation of Householder transformations doesn’t involve explicit construction and multiplication by the Householder matrix in (13.1). A numerically and computationally more efficient algorithm is easy to achieve since we know quite a bit about how each Hi acts on the column vectors. So the following describes some of the variables in the algorithm that aid optimization.

Some optimization of the algorithm can be done by rewriting n; let

$\begin{array}{ccc}{v}_i={\overline{a}}_i-\text{γ}{e}_i,& \text{where}\text{γ}\text{=}\{\begin{array}{c}-\text{sign}{a}_{i,i}||{\overline{a}}_i||\\ -||{\overline{a}}_i||\end{array}& \begin{array}{c}\text{if}{\text{a}}_{i,i}\ne 0\\ \text{otherwise}.\end{array}\end{array}$

Then we have that

$2n{n}^{\text{T}}=\frac{v{v}^{\text{T}}}{\frac{1}{2}{v}^{\text{T}}v}=\frac{v{v}^{\text{T}}}{\alpha }$

thus

$\alpha ={\text{γ}}^2-a_{i,i}\gamma .$

When Hi is applied to column vector c,

$H_{i}c=\left(I-\frac{v{v}^{\text{T}}}{\alpha }\right)c=c-sv.$

In the Householder algorithm that follows, as we work on the jth column vector, we call

$\begin{array}{cc}{\widehat{a}}_k=& \left[\begin{array}{c}{a}_{j,k}\\ ⋮\\ a_{n,k}\end{array}\right]\end{array}$

to indicate that only elements j, ..., n of the kth column vector ak (with k ≥ j) are involved in a calculation. Thus application of Hj results in changes in the sub-block of A with aj,j at the upper-left corner. Hence, the vector aj and Hjaj coincide in the first j − 1 components.

For a more detailed discussion, see [2] or [11].

Example 13.2

Let’s apply the Householder algorithm to the linear system

$\begin{array}{ccc}\left[\begin{array}{rrr}\hfill 1& \hfill 1& \hfill 0\\ \hfill 1& \hfill -1& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1\end{array}\right]& u=& \left[\begin{array}{r}\hfill -1\\ \hfill 0\\ \hfill 1\end{array}\right]\end{array}.$

For j = 1 in the algorithm, we calculate the following values: $\text{γ}=-\sqrt{2}$, $\alpha =2+\sqrt{2}$, and then we temporarily set

${\widehat{a}}_1=\left[\begin{array}{c}1+\sqrt{2}\\ 1\\ 0\end{array}\right].$

For k = 2, $s=\sqrt{2}/\left(2+\sqrt{2}\right)$. This results in

${\widehat{a}}_2=\left[\begin{array}{c}0\\ -\sqrt{2}\\ 0\end{array}\right].$

For k = 3, s = 0 and ${\widehat{a}}_3$ remains unchanged. For k = 4, $s=-\sqrt{2}/2$ and then the right-hand side vector becomes

$\begin{array}{cc}{\widehat{a}}_4=& \left[\begin{array}{c}\sqrt{2/2}\\ \sqrt{2/2}\\ 0\end{array}\right].\end{array}$

Now we set ${\widehat{a}}_1$, and the reflection H1 results in the linear system

$\begin{array}{ccc}\left[\begin{array}{ccc}-\sqrt{2}& 0& 0\\ 0& -\sqrt{2}& 0\\ 0& 0& 1\end{array}\right]& u=& \left[\begin{array}{c}\sqrt{2/2}\\ \sqrt{2/2}\\ 1\end{array}\right].\end{array}$

Although not explicitly computed,

$\begin{array}{cc}{n}_1=& \frac{\left[\begin{array}{c}1+\sqrt{2}\\ 1\\ 0\end{array}\right]}{||\cdot ||}\end{array}$

and the Householder matrix

$\begin{array}{cc}{H}_1=& \left[\begin{array}{ccc}-\sqrt{2/2}& -\sqrt{2/2}& 0\\ -\sqrt{2/2}& \sqrt{2/2}& 0\\ 0& 0& 1\end{array}\right].\end{array}$

Notice that a3 was not affected because it is in the plane about which we were reflecting, and this is a result of the involutary property of the Householder matrix. The length of each column vector was not changed as a result of the orthogonal property. Since the matrix is upper triangular, we may now use back substitution to find the solution vector

$u=\left[\begin{array}{c}-1/2\\ -1/2\\ 1\end{array}\right].$

The Householder algorithm is the method of choice if one is dealing with ill-conditioned systems. An example: for some data sets, the least squares solution to an overdetermined linear system can produce unreliable results because of the nature of ATA. In Section 13.4, we will examine this point in more detail. The Householder algorithm above is easy to use for such overdetermined problems: The input matrix A is of dimension n × m where n ≥ m. The following example illustrates that the Householder method will result in the least squares solution to an overdetermined system.

Example 13.3

Let’s revisit the least squares line-fitting problem from Example 12.13. See that example for a problem description, and see Figure 12.4 for an illustration. The overdetermined linear system for this problem is

$\begin{array}{ccc}\left[\begin{array}{cc}0& 1\\ 10& 1\\ 20& 1\\ 30& 1\\ 40& 1\\ 50& 1\\ 60& 1\end{array}\right]& \left[\begin{array}{c}a\\ b\end{array}\right]=& \left[\begin{array}{c}30\\ 25\\ 40\\ 40\\ 30\\ 5\\ 25\end{array}\right].\end{array}$

After the first Householder reflection (j = 1), the linear system becomes

$\begin{array}{ccc}\left[\begin{array}{cc}-95.39& -2.20\\ 0& 0.66\\ 0& 0.33\\ 0& -0.0068\\ 0& -0.34\\ 0& -0.68\\ 0& -1.01\end{array}\right]& \left[\begin{array}{c}a\\ b\end{array}\right]=& \left[\begin{array}{c}-54.51\\ 16.14\\ 22.28\\ 13.45\\ -5.44\\ -39.29\\ -28.15\end{array}\right].\end{array}$

For the second Householder reflection (j = 2), the linear system becomes

$\begin{array}{ccc}\left[\begin{array}{cc}-95.39& -2.20\\ 0& -1.47\\ 0& 0\\ 0& 0\\ 0& 0\\ 0& 0\\ 0& 0\end{array}\right]& \left[\begin{array}{c}a\\ b\end{array}\right]& \left[\begin{array}{c}-54.51\\ -51.10\\ 11.91\\ 13.64\\ 5.36\\ -17.91\\ 3.81\end{array}\right].\end{array}$

We can now solve the system with back substitution, starting with the first nonzero row, and the solution is

$\begin{array}{ccc}\left[\begin{array}{c}a\\ b\end{array}\right]& =& \left[\begin{array}{c}-0.23\\ 34.82\end{array}\right].\end{array}$

Excluding numerical round-off, this is the same solution found using the normal equations in Example 12.13.

13.2 Vector Norms

Finding the magnitude or length of a 3D vector is fundamental to many geometric operations. It is also fundamental for n-dimensional vectors, even though such vectors might no longer have geometric meaning. For example, in Section 13.6, we examine iterative methods for solving linear systems, and vector length is key for monitoring improvements in the solution.

The magnitude or length of an n–dimensional vector v is typically measured by

$\begin{array}{cc}{||v||}_2=\sqrt{v_1^2+...+v_n^2}.& \left(13.2\right)\end{array}$

The (nonnegative) scalar ||v||2 is also referred to as the Euclidean norm because in ℝ3 it is Euclidean length. Since this is the “usual” way to measure length, the subscript 2 often is omitted.

More generally, (13.2) is a vector norm. Other vector norms are conceivable, for instance the 1-norm

$\begin{array}{cc}{||v||}_1=\left|v_1\right|+\left|v_2\right|+...+\left|v_n\right|& \left(13.3\right)\end{array}$

or the ∞-norm

$\begin{array}{cc}{||v||}_{\infty }=\underset{i}{\max }\left|v_i\right|& \left(13.4\right)\end{array}$

We can gain an understanding of these norms by studying the familiar case n = 2. Recall that a unit vector is one whose norm equals one. For the 2-norm ||v||2, all unit vectors form a circle of radius one. With a bit of thinking, we can see that for the 1-norm all unit vectors form a diamond, while in the ∞-norm, all unit vectors form a square of edge length two. This geometric interpretation is shown in Figure 13.2.

All three of these norms may be viewed as members of a whole family of norms, referred to as p-norms. The p-norm of v is given by

${||v||}_p={\left(v_1^p+v_2^p+...+v_n^p\right)}^{1/p}.$

It is easy to see that the 1- and 2-norm fit this mold. That p → ∞ gives the ∞-norm requires a little more thought; give it a try!

Example 13.4

Let

$v=\left[\begin{array}{c}1\\ 0\\ -2\end{array}\right].$

Then

$\begin{array}{ccc}{||v||}_1=3& {||v||}_2=\sqrt{5}\approx 2.24,& {||v||}_{\infty }=2.\end{array}$

This example and Figure 13.2 demonstrate that

$\begin{array}{cc}{||v||}_1\ge {||v||}_2\ge {||v||}_{\infty };& \left(13.5\right)\end{array}$

this is also true in n dimensions.

All vector norms share some basic properties:

$\begin{array}{cc}||v||\ge 0,& \left(13.6\right)\end{array}$

$\begin{array}{cc}||v||=0\text{if}\text{and}\text{only}\text{if}v=0\text{,}& \left(13.7\right)\end{array}$

$\begin{array}{cc}||cv||=\left|c\right|||v|\text{for}c\in ℝ,& \left(13.8\right)\end{array}$

$\begin{array}{cc}||v+w||\le ||v||+||w||.& \left(13.9\right)\end{array}$

The last of these is the familiar triangle inequality.

By this time, we have developed a familiarity with the 2-norm, and these properties are easily verified. Recall the steps for the triangle inequality were demonstrated in (2.24).

Let’s show that the vector norm properties hold for the ∞-norm. Examining (13.4), for each v in ℝn, by definition, maxi|vi| ≥ 0. If maxi |vi| = 0 then vi = 0 for each i = 1,..., n and v = 0. Conversely, if v = 0 then maxi|vi| = 0. Thus we have established that the first two properties hold. The third property is easily shown by the properties of the absolute value function:

${||cv||}_{\infty }=\underset{i}{\max }\left|c{v}_i\right|=\left|c\right|\underset{i}{\max }\left|v_i\right|=\left|c\right|{||v||}_{\infty }$

For the triangle inequality:

$\begin{array}{ll}{||v+w||}_{\infty }& =\underset{i}{\max }\left|v_i+w_i\right|\\ & \le \underset{i}{\max }\left\{\left|v_i\right|+\left|w_i\right|\right\}\\ & \le \underset{i}{\max }\left|v_i\right|+\underset{i}{\max }\left|w_i\right|\\ & ={||v||}_{\infty }+{||w||}_{\infty }.\end{array}$

From a 2D geometric perspective, consider the 1-norm: starting at the origin, move v1 units along the e1-axis and then move v2 units along the e2-axis. The sum of these travels determines v’s length. This is analogous to driving in a city with rectilinear streets, and thus this norm is also called the Manhattan or taxicab norm.

The ∞-norm is also called the max-norm. Our standard measure of length, the 2-norm, can take more computing power than we might be willing to spend on a proximity problem, where we want to determine whether two points are closer than a given tolerance. Problems of this sort are often repeated many times and against many points. Instead, the max norm might be more suitable from a computing point of view and sufficient given the relationship in (13.5). This method of using an inexpensive measure to exclude many possibilities is called trivial reject in some disciplines such as computer graphics.

13.3 Matrix Norms

A vector norm measures the magnitude of a vector; does it also make sense to talk about the magnitude of a matrix?

Instead of exploring the general case right away, we will first give some 2D insight. Let A be a 2 × 2 matrix. It maps the unit circle to an ellipse—the action ellipse. In Figure 13.3 we see points on the unit circle at the end of unit vectors vi and their images Avi forming this action ellipse. We can learn more about this ellipse by looking at ATA. It is symmetric and positive definite, and thus has real and positive eigenvalues, which are λ′1, and λ′2, in decreasing value. We then define

$\begin{array}{cc}{\sigma }_i=\sqrt{{{\lambda }^{\prime }}_i},& \left(13.10\right)\end{array}$

to be the singular values of A. (In Chapter 16, we will explore singular values in more detail.)

The singular value σ1 is the length of the action ellipse’s semi-major axis and σ2 is the length of the action ellipse’s semi-minor axis. If A is a symmetric positive definite matrix, then its singular values are equal to its eigenvalues.

How much does A distort the unit circle? This is measured by its 2-norm, ||A||2. If we find the largest ||Avi||2, then we have an indication of how much A distorts. Assuming that we have k unit vectors vi we can compute

$\begin{array}{cc}{||A||}_2\approx \underset{i}{\max }{||A{v}_i||}_2.& \left(13.11\right)\end{array}$

As we increase k, (13.11) gives a better and better approximation to ||A||2. We then have

$\begin{array}{cc}{||A||}_2=\underset{{||v||}_2=1}{\max }{||Av||}_2.& \left(13.12\right)\end{array}$

It should be clear by now that this development is not restricted to 2 × 2 matrices, but holds for n × n ones as well. From now on, we will discuss this general case, where the matrix 2-norm is more complicated to compute than its companion vector norm. It is given by

${||A||}_2={\sigma }_1,$

where σ1 is A’s largest singular value.

Recall that the inverse matrix A−1 “undoes” the action of A. Let the singular values of A−1 be called ${\widehat{\sigma }}_i$, then

${\widehat{\sigma }}_1=\frac{1}{{\sigma }_n},...,{\widehat{\sigma }}_n=\frac{1}{{\sigma }_1}$

and

${||A^{-1}||}_2=\frac{1}{{\sigma }_n}.$

Singular values are frequently used in the numerical analysis of matrix operations. If you do not have access to software for singular values, then (13.11) will give a decent approximation. Singular values are typically computed using a method called singular value decomposition, or SVD, and they are the focus of Chapter 16.

Analogous to vector norms, there are other matrix norms. We give two important examples:

$\begin{array}{ll}{||A||}_1:& \text{maximum}\text{absolute}\text{column}\text{sum},\\ {||A||}_{\infty }:& \text{maximum}\text{absolute}\text{row}\text{sum}\text{.}\end{array}$

Because the notation for matrix and vector norms is identical, it is important to note what is enclosed in the norm symbols—a vector or a matrix.

Another norm that is sometimes used is the Frobenius norm, which is given by

$\begin{array}{cc}{||A||}_F=\sqrt{{\sigma }_1^2+...+{\sigma }_n^2},& \left(13.13\right)\end{array}$

where the σi are A’s singular values.

The following is not too obvious. The Euclidean norm: add up the squares of all matrix elements, and take the square root,

$\begin{array}{cc}{||A||}_F=\sqrt{a_{1,1}^2+a_{1,2}^2+...a_{n,n}^2}& \left(13.14\right)\end{array}$

is identical to the Frobenius norm.

A matrix A maps all unit vectors to an ellipsoid whose semi-axis lengths are given by σ1,...,σn. Then the Frobenius norm gives the total distortion caused by A.

Example 13.5

Let’s examine matrix norms for

$A=\left[\begin{array}{ccc}1& 2& 3\\ 3& 4& 5\\ 5& 6& -7\end{array}\right].$

Its singular values are given by 10.5, 7.97, 0.334 resulting in

$\begin{array}{cc}\hfill {||A||}_2& =\max \left\{10.5,7.97,0.334\right\}=10.5\hfill \\ \hfill {||A||}_1& =\max \left\{9,12,15\right\}=15\hfill \\ \hfill {||A||}_{\infty }& =\max \left\{6,12,15\right\}=18\hfill \\ \hfill {||A||}_F& =\sqrt{1^2+3^2+...{\left(-7\right)}^2}=\sqrt{{10.5}^2+{7.97}^2+0.334}=13.2\hfill \end{array}$

From the examples above, we see that matrix norms are real-valued functions of the linear space defined over all n × n matrices.1 Matrix norms satisfy conditions very similar to the vector norm conditions (13.6), (13.7), (13.8) and (13.9):

$\begin{array}{cc}||A||>0\text{for}A\ne Z,& \left(13.15\right)\end{array}$

$\begin{array}{cc}||A||=0\text{for}A=Z& \left(13.16\right)\end{array}$

$\begin{array}{rr}\hfill ||cA||=\left|c\right|||A|c\in ℝ,& \hfill \left(13.17\right)\end{array}$

$\begin{array}{cc}||A+B||\le ||A||+||B||,& \left(13.18\right)\end{array}$

$\begin{array}{cc}||AB||\le ||A||||B||,& \left(13.19\right)\end{array}$

Z being the zero matrix.

How to choose a matrix norm? Computational expense and properties of the norm are the deciders. For example, the Frobenius and 2-norms are invariant with respect to orthogonal transformations. Many numerical methods texts provide a wealth of information on matrix norms and their relationships.

13.4 The Condition Number

We would like to know how sensitive the solution to Au = b is to changes in A and b. For this problem, the matrix 2-norm helps us define the condition of the map.

In most of our figures describing linear maps, we have mapped a circle, formed by many unit vectors Vi, to an ellipse, formed by vectors Avi. This ellipse is evidently closely related to the geometry of the map, and indeed its semi-major and semi-minor axis lengths correspond to A’s singular values. For n = 2, the eigenvalues of ATA are λ′1 and λ′2, in decreasing value. The singular values of A are defined in (13.10). If σ1 is very large and σ2 is very small, then the ellipse will be very elongated, as illustrated by the example in Figure 13.4. The ratio

$k\left(A\right)={||A||}_2{||A^{-1}||}_2={\sigma }_1/{\sigma }_2$

is called the condition number of A. In Figure 13.4, we picked the (symmetric, positive definite) matrix

$A=\left[\begin{array}{cc}1.5& 0\\ 0& 0.05\end{array}\right],$

which has condition number K(A) = 1.5/0.05 = 30.

Since ATA is symmetric and positive definite, κ(A) ≥ 1. If a matrix has a condition number close to one, it is called well-conditioned. If the condition number is 1 (such as for the identity matrix), then no distortion happens. The larger the κ(A), the more A distorts, and if κ(A) is “large,” the matrix is called ill-conditioned.

Example 13.6

Let

$A=\left[\begin{array}{cc}\cos \alpha & -\sin \alpha \\ \sin \alpha & \cos \alpha \end{array}\right],$

meaning that A is an α degree rotation. Clearly, ATA = I, where I is the identity matrix. Thus, σ1 = σ2 = 1. Hence the condition number of a rotation matrix is 1. Since a rotation does not distort, this is quite intuitive.

Example 13.7

Now let

$A=\left[\begin{array}{cc}100& 0\\ 0& 0.01\end{array}\right],$

a matrix that scales by 100 in the e1-direction and by 0.01 in the e2- direction. This matrix is severely distorting! We quickly find σ1 = 100 and σ2 = 0.01 and thus the condition number is 100/0.01 = 10,000. The fact that A distorts is clearly reflected in the magnitude of its condition number.

Back to the initial problem: solving Au = b. We will always have round-off error to deal with, but we want to avoid creating a poorly designed linear system, which would mean a matrix A with a “large” condition number. The definition of large is subjective and problem- specific. A guideline: κ(A) ≈ 10k can result in a loss of k digits of accuracy. If the condition number of a matrix is large, then irrespective of round-off, the solution cannot be depended upon. Practically speaking, a large condition number means that the solution to the linear system is numerically very sensitive to small changes in A or b. Alternatively, we can say that we can confidently calculate the inverse of a well-conditioned matrix.

The condition number is a better measure of singularity than the determinant because it is a scale and size n invariant measure. If s is a scalar, then κ(SA) = κ(A).

Example 13.8

Let n = 100. Form the identity matrix I and J = 0.1I.

$\begin{array}{cccc}\det I=1,& k\left(I\right)=1,& \det J={10}^{-100,}& k\left(J\right)=1.\end{array}$

The determinant of J is small, indicating that there is a problem with this matrix. However, in solving a linear system with such a coefficient matrix, the scale of J poses no problem.

In Section 12.7, we examined overdetermined linear systems Au = b in m equations and n unknowns, where m > n. (Thus A is an m × n matrix.) Our approach to this problem depended on the approximation method of least squares, and we solved the system AT Au = ATb. The condition number for this new matrix, κ(ATA) = κ(A)2, so if A has a high condition number to start with, this process will create an ill-posed problem. In this situation, a method such as the Householder method (see Section 13.1), is preferred. We will revisit this topic in more detail in Section 16.6.

An advanced linear algebra or numerical analysis text will provide an in-depth study of the condition number and error analysis.

13.5 Vector Sequences

You are familiar with sequences of real numbers such as

$1,\frac{1}{2},\frac{1}{4},\frac{1}{8},...$

or

$1,2,4,8,...$

The first of these has the limit 0, whereas the second one does not have a limit. One way of saying a sequence of real numbers ai has a limit a is that beyond some index i, all ai differ from the limit a by an arbitrarily small amount ε.

Vector sequences in ℝn,

$v^{\left(0\right)},v^{\left(1\right)},v^{\left(2\right)},...,$

are not all that different. A vector sequence has a limit if each component has a limit.

Example 13.9

Let a vector sequence be given by

$v^{\left(i\right)}=\left[\begin{array}{c}1/i\\ {1/i}^2\\ 1/i^3\end{array}\right].$

This sequence has the limit

$v=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right].$

Now take the sequence

$v^{\left(i\right)}=\left[\begin{array}{c}i\\ 1/i^2\\ 1/i^3\end{array}\right].$

It does not have a limit: even though the last two components each have a limit, the first component diverges.

We say that a vector sequence converges to v with respect to a norm if for any tolerance ε > 0, there exists an integer m such that

$\begin{array}{rrrr}\hfill ||v^{\left(i\right)}-v||<\epsilon & \hfill \text{for}\text{all}& \hfill i>m.& \hfill \left(13.20\right)\end{array}$

In other words, from some index i on, the distance of any v(i) from v is smaller than an arbitrarily small amount ε. See Figure 13.5 for an example. If the sequence converges with respect to one norm, it will converge with respect to all norms. Our focus will be on the (usual) Euclidean or 2-norm, and the subscript will be omitted.

Vector sequences are key to iterative methods, such as the two methods for solving Au = b in Section 13.6 and the power method for finding the dominant eigenvalue in Section 15.2. In practical applications, the limit vector v is not known. For some special problems, we can say whether a limit exists; however, we will not know it a priori. So we will modify our theoretical convergence measure (13.20) to examine the distance between iterations. This can take on different forms depending on the problem at hand. In general, it will lead to testing the condition

$||v^{\left(i\right)}-v^{\left(i+1\right)}||<\epsilon ,$

which measures the change from one iteration to the next. In the case of an iterative solution to a linear system, u(i), we will test for the condition that ||Au(i) − b|| < ε, which indicates that this iteration has provided an acceptable solution.

13.6 Iterative System Solvers: Gauss-Jacobi and Gauss-Seidel

In applications such as finite element methods (FEM) in the context of the solution of fluid flow problems, scientists are faced with linear systems with many thousands of equations. Gauss elimination would work, but would be far too slow. Typically, huge linear systems have one advantage: the coefficient matrix is sparse meaning it has only very few (such as ten) nonzero entries per row. Thus, a 100,000 × 100,000 system would only have 1,000,000 nonzero entries, compared to 10,000,000,000 matrix elements! In these cases, one does not store the whole matrix, but only its nonzero entries, together with their i,j location. An example of a sparse matrix is shown in Figure 13.1. The solution to such systems is typically obtained by iterative methods, which we will discuss next.

Example 13.10

Let a system2 be given by

$\begin{array}{cc}\left[\begin{array}{ccc}4& 1& 0\\ 2& 5& 1\\ -1& 2& 4\end{array}\right] \left[\begin{array}{c}{u}_1\\ u_2\\ u_3\end{array}\right]=& \left[\begin{array}{c}1\\ 0\\ 3\end{array}\right].\end{array}$

An iterative method starts from a guess for the solution and then refines it until it is the solution. Let’s take

$\begin{array}{ccc}{u}^{\left(1\right)}=& \left[\begin{array}{c}{u}_1^{\left(1\right)}\\ u_2^{\left(1\right)}\\ u_3^{\left(1\right)}\end{array}\right]& =\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]\end{array}$

for our first guess, and note that it clearly is not the solution to our system: Au(1) ≠ b.

A better guess ought to be obtained by using the current guess and solving the first equation for a new $u_1^{\left(2\right)}$, the second for a new $u_2^{\left(2\right)}$, and so on. This gives us

$\begin{array}{r}4u_1^{\left(2\right)}+1=1,\\ 2+5u_2^{\left(2\right)}+1=0,\\ -1+2+4u_3^{\left(2\right)}=3,\end{array}$

and thus

$\begin{array}{c}{u}^{\left(2\right)}=\left[\begin{array}{c}0\\ -0.6\\ 0.5\end{array}\right].\end{array}$

The next iteration becomes

$\begin{array}{r}4u_1^{\left(3\right)}-0.6=1,\\ 5u_2^{\left(3\right)}+0.5=0,\\ -1.2+4u_3^{\left(3\right)}=3,\end{array}$

and thus

$\begin{array}{c}{u}^{\left(3\right)}=\left[\begin{array}{r}\hfill 0.4\\ \hfill -0.1\\ \hfill 1.05\end{array}\right].\end{array}$

After a few more iterations, we will be close enough to the true solution

$\begin{array}{r}\hfill u=\left[\begin{array}{c}0.333\\ -0.333\\ 1.0\end{array}\right].\end{array}$

Try one more iteration for yourself.

This iterative method is known as Gauss-Jacobi iteration. Let us now formulate this process for the general case. We are given a linear system with n equations and n unknowns ui, written in matrix form as

$Au=b.$

Let us also assume that we have an initial guess u(1) for the solution vector u.

We now define two matrices D and R as follows: D is the diagonal matrix whose diagonal elements are those of A, and R is the matrix obtained from A by setting all its diagonal elements to zero. Clearly then

$A=D+R$

and our linear system becomes

$Du+Ru=b$

or

$u=D^{-1}\left[b-Ru\right].$

In the spirit of our previous development, we now write this as

$u^{\left(k+1\right)}=D^{-1}\left[b-R{u}^{\left(k\right)}\right],$

meaning that we attempt to compute a new estimate u(k+1) from an existing one u(k). Note that D must not contain zeroes on the diagonal; this can be achieved by row or column interchanges.

Example 13.11

With this new framework, let us reconsider our last example. We have

$\begin{array}{ccc}A=\left[\begin{array}{rrr}\hfill 4& \hfill 1& \hfill 0\\ \hfill 2& \hfill 5& \hfill 1\\ \hfill -1& \hfill 2& \hfill 4\end{array}\right],& R=\left[\begin{array}{rrr}\hfill 0& \hfill 1& \hfill 0\\ \hfill 2& \hfill 0& \hfill 1\\ \hfill -1& \hfill 2& \hfill 0\end{array}\right],& D^{-1}=\left[\begin{array}{ccc}0.25& 0& 0\\ 0& 0.2& 0\\ 0& 0& 0.25\end{array}\right].\end{array}$

Then

$\begin{array}{c}{u}^{\left(2\right)}=\left[\begin{array}{ccc}0.25& 0& 0\\ 0& 0.2& 0\\ 0& 0& 0.25\end{array}\right]\left(\left[\begin{array}{c}1\\ 0\\ 3\end{array}\right]-\left[\begin{array}{rrr}\hfill 0& \hfill 1& \hfill 0\\ \hfill 2& \hfill 0& \hfill 1\\ \hfill -1& \hfill 2& \hfill 0\end{array}\right] \left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]\right)=\left[\begin{array}{r}\hfill 0\\ \hfill -0.6\\ \hfill 0.5\end{array}\right]\end{array}$

Will the Gauss-Jacobi method succeed, i.e., will the sequence of vectors u(k) converge? The answer is: sometimes yes, and sometimes no. It will always succeed if A is diagonally dominant, which means that if, for every row, the absolute value of its diagonal element is larger than the sum of the absolute values of its remaining elements. In this case, it will succeed no matter what our initial guess u(1) was. Strictly diagonally dominant matrices are nonsingular. Many practical problems, for example, finite element ones, result in diagonally dominant systems.

In a practical setting, how do we determine if convergence is taking place? Ideally, we would like u(k) = u, the true solution, after a number of iterations. Equality will most likely not happen, but the length of the residual vector

$||A{u}^{\left(k\right)}-b||$

should become small (i.e., less than some preset tolerance). Thus, we check the length of the residual vector after each iteration, and stop once it is smaller than our tolerance.

A modification of the Gauss-Jacobi method is known as Gauss- Seidel iteration. When we compute u(k+1) in the Gauss-Jacobi method, we can observe the following: the second element, $u_2^{\left(k+1\right)}$, is computed using $u_1^{\left(k\right)}$, $u_3^{\left(k\right)}$, ... $u_n^{\left(k\right)}$. We had just computed $u_1^{\left(k+1\right)}$. It stands to reason that using it instead of $u_1^{\left(k\right)}$ would be advantageous. This idea gives rise to the Gauss-Seidel method: as soon as a new element $u_i^{\left(k+1\right)}$ is computed, the estimate vector u(k+1) is updated.

In summary, Gauss-Jacobi updates the new estimate vector once all of its elements are computed, Gauss-Seidel updates as soon as a new element is computed. Typically, Gauss-Seidel iteration converges faster than Gauss-Jacobi iteration.

13.7 Exercises

1. Use the Householder method to solve the following linear system

   $\begin{array}{cc}\left[\begin{array}{ccc}1& 1.1& 1.1\\ 1& 0.9& 0.9\\ 0& -0.1& 0.2\end{array}\right]& u=\left[\begin{array}{c}1\\ 1\\ 0.3\end{array}\right].\end{array}$

   Notice that the columns are almost linearly dependent.

2. Show that the Householder matrix is involuntary.

3. What is the Euclidean norm of

   $v=\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right].$

4. Examining the 1- and 2-norms defined in Section 13.2, how would you define a 3-norm?
5. Show that the ||v||1 satisfies the properties (13.6), (13.7), (13.8) and (13.9) of a vector norm.
6. Define a new vector norm to be max{2|v1|, |v2|, ..., |vn|}. Show that this is indeed a vector norm. For vectors in ℝ2, sketch the outline of all unit vectors with respect to this norm.

7. Let

   $A=\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 2\\ 0& 0& 1\end{array}\right].$

   What is A’s 2-norm?

8. Let four unit vectors be given by

   $\begin{array}{cccc}{v}_1=\left[\begin{array}{c}1\\ 0\end{array}\right],& v_2=\left[\begin{array}{c}0\\ 1\end{array}\right],& v_3=\left[\begin{array}{c}-1\\ 0\end{array}\right],& v_4\end{array}=\left[\begin{array}{c}0\\ -1\end{array}\right].$

   Using the matrix

   $A=\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right],$

   compute the four image vectors Avi. Use these to find an approximation to ∥A∥2.

9. Is the determinant of a matrix a norm?
10. Why is 1 the smallest possible condition number for a nonsingular matrix?

11. What is the condition number of the matrix

    $A=\left[\begin{array}{cc}0.7& 0.3\\ -1& 1\end{array}\right]$

    that generated Figure 7.11?

12. What can you say about the condition number of a rotation matrix?

13. What is the condition number of the matrix

    $\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right]?$

    What type of matrix is it, and is it invertible?

14. Is the condition number of a matrix a norm?

15. Define a vector sequence by

    $\begin{array}{cc}{u}^i=\left[\begin{array}{ccc}0& 0& 1/i\\ 0& 1& 0\\ -1/i& 0& 0\end{array}\right] \left[\begin{array}{c}1\\ 1\\ 1\end{array}\right];& i=1,2,....\end{array}$

    Does it have a limit? If so, what is it?

16. Let a vector sequence be given by

    $\begin{array}{ccc}{u}^{\left(1\right)}=\left[\begin{array}{r}\hfill 1\\ \hfill -1\end{array}\right]& \text{and}& u^{\left(i+1\right)}=\left[\begin{array}{cc}1/2& 1/4\\ 0& 3/4\end{array}\right]u^{\left(i\right)}.\end{array}$

    Will this sequence converge? If so, to what vector?

17. Let a linear system be given by

    $\begin{array}{ccc}A=\left[\begin{array}{rrr}\hfill 4& \hfill 0& \hfill -1\\ \hfill 2& \hfill 8& \hfill 2\\ \hfill 1& \hfill 0& \hfill 2\end{array}\right]& \text{and}& b=\left[\begin{array}{r}\hfill 2\\ \hfill -2\\ \hfill 0\end{array}\right]\end{array}.$

    Carry out three iterations of the Gauss-Jacobi iteration starting with an initial guess

    $u^{\left(1\right)}=\left[\begin{array}{r}\hfill 0\\ \hfill 0\\ \hfill 0\end{array}\right].$

18. Let a linear system be given by

    $\begin{array}{rrr}\hfill A=\left[\begin{array}{rrr}\hfill 4& \hfill 0& \hfill 1\\ \hfill 2& \hfill -8& \hfill 2\\ \hfill 1& \hfill 0& \hfill 2\end{array}\right]& \hfill \text{and}& \hfill b=\left[\begin{array}{r}\hfill 0\\ \hfill 2\\ \hfill 0\end{array}\right].\end{array}$

    Carry out three iterations of the Gauss-Jacobi iteration starting with an initial guess

    $u^{\left(1\right)}=\left[\begin{array}{r}\hfill 0\\ \hfill 0\\ \hfill 0\end{array}\right].$

19. Carry out three Gauss-Jacobi iterations for the linear system

    $\begin{array}{rrr}\hfill A=\left[\begin{array}{rrrr}\hfill 4& \hfill 1& \hfill 0& \hfill 1\\ \hfill 1& \hfill 4& \hfill 1& \hfill 0\\ \hfill 0& \hfill 1& \hfill 4& \hfill 1\\ \hfill 1& \hfill 0& \hfill 1& \hfill 4\end{array}\right]& \hfill \text{and}& \hfill b=\left[\begin{array}{r}\hfill 0\\ \hfill 1\\ \hfill 1\\ \hfill 0\end{array}\right],\end{array}$

    starting with the initial guess

    $u^{\left(1\right)}=\left[\begin{array}{r}\hfill 1\\ \hfill 1\\ \hfill 1\\ \hfill 1\end{array}\right].$

20. Carry out three iterations of Gauss-Seidel for Example 13.10. Which method, Gauss-Jacobi or Gauss-Seidel, is converging to the solution faster? Why?

1More on this type of linear space in Chapter 14.

2This example was taken from Johnson and Riess [11].