Linear Equations

Given the two simultaneous, linear equations

you have learned that you could eliminate, for example, the variable x by multiplying the first equation by d, the second equation by a, and subtracting the second equation from the first, in order to find

This step led to the introduction of the short hand notation, called determinants:

.and Cramer's Rule: The solution of a set of simultaneous linear equations

is given by

where D is the determinant and D_i is the same determinant with the i-th column replaced by the vector b.

Note that the first subscript refers to the rows, the second to the columns of the determinant.

We have used here new notation and terminology. They were created to deal with problems of physics and applied mathematics rather than as mathematical theories. One step was the introduction of matrices

and row and column vectors

which let one write such systems in the simple algebraic form

with the solution

There still remains the problem of finding the inverse A^-1 of a matrix A.

In this way there arises the need to multiply matrices

We see that the orders of two matrices in a product have to be such that the number of columns of the first factor equals that of the number of rows of the second factor. A square matrix has as many rows as columns. If this is not so, these products exhibit a new and special feature of matrix calculus, non-associativity of products, i.e., AB ¹ BA.

EXAMPLE

Let

then

If we multiply a matrix by a scalar (not a vector or matrix), each element is multiplied by it:

The product of a row vector X and a column vector Y, called a scalar or inner product, is a scalar, i.e., a number:

The product of a column vector X by a row vector Y is an n*n matrix, often called an outer product:

SPECIAL MATRICES

1. Unit matrix:

2. Unit column and row vectors:

3. Lower and upper triangular matrices:

4. Tri-diagonal matrices:

5. Transposed matrices:

GAUSS ELIMINATION

This method is a generalization of what was seen above when dealing with two simultaneous equations. It relies on the result that addition to any column or row of a determinant of any other row or column, multiplied by a scalar, does not change the value of the determinant.

This rule is often used when evaluating determinants. In that way, a determinant is reduced to triangular form, so that its value is the product of the diagonal terms. In Gauss elimination, for the sake of simplicity, the matrix is augmented by the column vector on the right hand side, forming what appears to be an n*(n+1) matrix, followed by the algorithm:

Divide the first row by the first term and then subtract that row, after multiplication by the first term of the remaining rows from those rows, respectively; thus, the original system is reduced to one with a first column unit vector.
Then repeat the same steps for the second column, using the second row, etc., until the columns form an upper triagonal matrix with 1 along the diagonal.
Now use back substitution to find the variables from the triangular system.

COMPUTATION SCHEME

In this scheme, the column with the sums provides a welcome check for manual calculations, since its entry should equal the sum of the individual terms in that row.

There may arise problems such as that a diagonal element in the scheme vanishes and division becomes impossible. One must then interchange rows, i.e., apply partial pivoting. If one also wants to interchange columns, one speaks of total pivoting. The former is widely practiced, in order to avoid loss of accuracy. The aim is to have always a large element in the diagonal position.

If a system of linear equations is subject to loss of accuracy, it is said to be ill-conditioned.

EXAMPLE

Consider the system of 3 equations:

and set up the scheme:

Hence, by back-substitution:

x₃= 3.0
x₂ = -7.7 + 1.9*3 = 2.0
x₃ = 3.75 + 0.5*2 - 0.25*3 = 4.0

and the determinant has the value:

1.8*(-2.5)*4 = -18.

This work shows that one can evaluate the solutions for different right hand sides b. This can be done at the same time by adding two columns for each right hand side, namely the actual b column and the corresponding sum column.

What does one do when there appears a 0 or a very small term on the diagonal? One interchanges rows:

EXAMPLE

Consider the system

Note here that a₁₁ is very small compared to the other a_ij. If one uses Gauss, one obtains the non-normalized, augmented matrix

with the solution

If one interchanges Rows 1 and 2:

and repeats the calculations, one finds

with the solution:

One could try to solve the original system using more digits, but it will not be much better. The point is that without pivoting, accuracy is lost!

Ill-conditioning may be very disturbing without any other way out but using more decimals:

EXAMPLE

Consider the system:

Pivoting and Gauss elimination yield

Note the large number of decimals. We just retained always three numbers! The solution is:

Of course, you have been warned, because the value of the determinant is

If you repeat the calculation with six digits, you will find the solution:

There is no other cure! Now let us experiment. If we change the coefficient a₁₁ to 3.00, the exact solution is

This is a very big change for a small perturbation, the symptom of ill-conditioning!

These phenomena are displayed by the simple system:

with the solution

If you change the system slightly to:

the solution becomes:

Another change to:

yields the solution:

ILL-CONDITIONING CRITERION

The condition number of a coefficient matrix is defined as the product of two matrix norms:

Unfortunately, if one wants to use norms, one must also find A^-1, the inverse of A. If the absolute value of this number is very large, there is trouble. As a rule, its value will be about 1.

MATRIX INVERSION

In order to find the inverse of a matrix, Gauss Elimination can be employed by introducing as two right hand column vectors the columns of the unit matrix:

and obtaining the inverse matrix

Check this result:

It is not perfect, but good enough for our purpose. What about norms? They allow to talk about matrices as if they were simple numbers. There are different ways of doing this:

DEFINITIONS OF NORMS

A norm of a matrix satisfies the conditions:

It is known that these conditions are satisfied by the modulus or the length of a vector, also called its Euclidean norm:

However, one could also use instead of the sum the absolute values of its components x_i or even only their maximum value.

The norm of a matrix is defined in a corresponding manner in two steps. One first forms the sums of its columns or rows and then selects their maximum:

Reconsider the last example and apply this approach to find its condition number. We had

whence

This explains the difficulties encountered in solving the equations.

Exercises

Solve by Gauss elimination at least one of the following systems of equations to 4 decimals:

Find the inverse of the matrix and the condition number. Do you consider the solution to be reliable?

L-U Decomposition

Another convenient method of solving systems of equations is by decomposition of the matrix into a product of upper and lower triangular matrices and solving the system by combined forward and backwards substitutions. In L-U Decomposition of a 3x3 matrix, one has the product of two triangular matrices, each of which has six elements. However, the original matrix has only 9 elements. Hence onee can set the diagonal elements of one of the triangular matrices equal to 1, for example, the diagonal elements of the upper matrix:

You see now that there are 9 equations expressing the a_ij in terms of the l_ij and u_ij. A special feature of this system is that one can find the solution explicitly and that, once an a_ij has been used, it can be overwritten. For this purpose, we need only follow the proper sequence:

We can now rewrite our original system:

and set

Hence one has for the y_i the system:

which can be solved by forward substitution. Once the y_i have been found, the x_i are determined by backward substitution from the system defining the y_i.

EXAMPLE

Consider

We find

whence the system for the auxiliary variables y_i is

with the solutions

and the x_i are the solutions of the system:

i.e.,

last next