2.1 Systems of Linear equations.
Consider a system of m linear equations with n unknowns
|
(1) |
Here, aij and bj, (i = 1,2,...,m; j = 1,2,...,n) are known scalars and x1,...,xn are unknowns. Some of the scalars aij and bj may be zero, but we assume that among a11, a21,...,am1 at least one is not zero (otherwise, if all ai1 = 0, i = 1,2..., m, then x1 would not be present in any of the equations so the system has only (n-1) unknown x2,...,xn. Analogously, for every j = 2,3,...,n, at least one element among a1j, a2j,...,am,j must be different from zero.
A solution to (1) is a set of n scalars x1,...,xn such that when substituted into (1) all the equations are satisfied. In this chapter we will use the matrix theory to consider the questions of existence of solutions and how to find them. We associate with system (1) a matrix A of order m×n and two column vectors x, b given by
|
Then, as we can see easily, system (1) can be rewritten in the following matrix form:
|
(2) |
Alternatively, if we denote by ak the k-column of A then system (1)-(2) can be rewritten in the following form:
|
(3) |
It may happen the the system (1)-(2) has no solutions, has exactly one solution, or has more than one solution. For example, the system
|
(4) |
has no solutions. The system
|
(5) |
has precisely one solution (x = 1, y = 0), and the system
|
(6) |
has infinitely many solutions (take any number z and put x = -3/2z, y = 1+1/2z).
The representation of system (1) in the form (3) immediately implies the following fact: if (1) has a solution, then the (column) vector b is a linear combination of the (column) vectors ak, k = 1,...,n.
A linear system is called consistent if it has at least one solution. Thus, system (3) is not consistent and systems (4)-(5) are consistent.
System (1)-(2) is called homogeneous if b = 0, i.e. b1 = b2 = ... = bm = 0. If b ¹ 0, i.e. at least one of bi is different from 0, then (1)-(2) is called nonhomogeneous. Since a homogeneous system always has a solution x = 0, it is consistent (the zero solution is called a trivial solution of the homogeneous system).
2.2 Substitution method.
Consider system (1):
|
(7) |
There is a very narural and straighforward method of solving the system (1). Let us first consider some examples.
Example 1: Consider the system
|
From the first equation we obtain x = 1-y-z. Substituting this value of x into the second and third equations we obtain 2-2y-2z-y+z = 2-3y-z = -1, or y = 1-1/3z, and -1+y+z+2y-z = -1+3y = 0, or y = 1/3. Thus, we obtain the following system
|
Now, substituting y = 1/3 back into the second equation we obtain z = 2, and substituting y = 1/3, z = 2 into the first equation we obtain x = -4/3.
Example 2: Consider the system
|
and apply the same method as in Example 1. From the first equation we have x = 1-y. Substituting this value of x into the second equation we have 1-y+y = 2, or 1 = 2, which is absurd. Thus, the system does not have solution (is inconsistent).
The above examples are illustrations of the method of substitution which consists in the following:
1. Since not all ai1 are equall zero, we can always rearrange the equations so that to assume that a11 ¹ 0. Take the first equation a11x1+a12x2+...+a1nxn = b1, solve for x1 in terms of x2,...,xn (namely, x1 = -a11-1(b1-a12x2-...-a1nxn)), and substitude the value of x1 into all other equations in the system. This way we obtain the first derived system of m-1 equations with n-1 unknowns x2,...,xn.
2. We repeat step 1 for the first derived system, as a result we obtain the second derived system.
3. We keep continuing the process until either we obtain a system in the following form which can be solved easily by back substitutions:
|
(8) |
(or until we obtain an obvious inconsistency which means that the system does not have a solution).
2.3 Gaussian elimination. System (1) of linear equations is completely described by the matrix A and the column vector b. Therefore, it is convenient to introduce the notation
|
which will be called the augmented matrix associated with system (1). Any matrix is an augmented matrix of some system of linear equations.
For instance, the matrix
|
is the augmented matrix of the system
|
The Gausian elimination method is in fact a version of the substitution method in which only the numbers aij, bj are present. Therefore, it is effective for computer implementation. First we make the following simple observations. We call two systems of linear equations containing the same unknown equivalent if they have the same solutions. We obtain an equivalent system if we do one or more of the following operations:
(1) Interchange any two equations in a system;
(2) Multiply an equation in a system by a nonzero scalar;
(3) Add to one equation a scalar times another equation.
In terms of the augmented matrices representing systems of linear equations the operations 1-3 above correspond to the following operations which are called elementary row transformations of matrices.
(i) Interchange any two rows in a matrix;
(ii) Multiply any row by a nonzero scalar;
(iii) Add to any row of a matrix a scalar times another row of that same matrix.
The Gaussian elimination method consists in applying the elementary row transformations (i)-(iii) to the augmented matrix of a system of linear equations in order to get a matrix which has a special row-reduced form. The special row-reduced form is suggested by the substitution method described in the previous section, namely, a matrix is said to be in a row-reduced form if it has the following properties:
(a) The first nonzero element of any row is 1;
(b) Elements below the first nonzero elements of any row are zeros;
(c) All zero rows (i.e. rows consisting of only zeros) are below nonzero rows.
We remark that the property (a) above is just a normalized condition which can be achieved by applying the elementary row transform (i) - multiplying by a nonzero scalar. The property (b) is the most important - it means that every next equation in the corresponding system contains less unknown than the preceding equations. The zero rows correspond to trivial equations (of the form 0x1+0x2+...+0xn = 0) which are satisfied trivially. Such equations can be ignored in solving the systems and property (c) means that we put them at the bottom to ignore them.
Below are some examples of row-reduced matrices:
|
(9) |
|
(10) |
|
(11) |
Systems of equations corresponding to the row reduced matrices (9), (10), (11) have exactly one solution, infinitely many solution, and no solutions, respectively.
Below we give an example of using the Gaussian elimination.
Example: Solve the system
|
Solution: The augmented matrix of the system is:
|
The elementary row transformations yield:
|
|
|