92
5. Solution of Linear Equation Systems
5.2 Direct Methods
The matrix A is assumed t o be very sparse. In fact, the most complicated
matrix we shall encounter is a banded matrix of block type; this greatly
simplifies the task of solution but we shall briefly review methods for general
matrices as methods for sparse matrices are closely related to them. For the
description of methods designed to deal with full matrices, use of full-matrix
notation (as opposed to the diagonal notation introduced earlier) is more
sensible and will be adopted.
5.2.1 Gauss Elimination
The basic method for solving linear systems of algebraic equations is Gauss
elimination. Its basis is the systematic reduction of large systems of equations
to smaller ones. In this procedure, the elements of the matrix are modified
but, as the dependent variable names do not change, it is convenient to
describe the method in terms of the matrix alone:
All A12 A13 . . . Aln
A21 A22 A23 . . . A2n
. . . . .
An1 An2 An3 . . . Ann
The heart of the algorithm is the technique for eliminating Azl i.e., replacing
it with a zero. This is accomplished by multiplying the first equation (first
row of the matrix) by A21/A11 and subtracting it from the second row or
equation; in the process, all of the elements in the second row of the matrix
are modified as is the second element of the forcing vector on the right hand
side of the equation. The other elements of the first column of the matrix,
A31,
. . , Anl are treated similarly; for example, to eliminate Ail, the
first row of the matrix is multiplied by Ail/AI1 and subtracted from the ith
row. By systematically proceeding down the first column of the matrix, all of
the elements below All are eliminated. When this process is complete, none
of the equations 2 , 3 , . . . , n contain the variable $1; they are a set of n - 1
equations for the variables 42, $3, . . . ,$,. The same procedure is then applied
to this smaller set of equations - all of the elements below Az2 in the second
column are eliminated.
This procedure is carried out for columns 1,2,3, . . . , n - 1. After this process is complete, the original matrix has been replaced by an upper triangular
one:
5. Solution of Linear Equation Systems
5.2 Direct Methods
The matrix A is assumed t o be very sparse. In fact, the most complicated
matrix we shall encounter is a banded matrix of block type; this greatly
simplifies the task of solution but we shall briefly review methods for general
matrices as methods for sparse matrices are closely related to them. For the
description of methods designed to deal with full matrices, use of full-matrix
notation (as opposed to the diagonal notation introduced earlier) is more
sensible and will be adopted.
5.2.1 Gauss Elimination
The basic method for solving linear systems of algebraic equations is Gauss
elimination. Its basis is the systematic reduction of large systems of equations
to smaller ones. In this procedure, the elements of the matrix are modified
but, as the dependent variable names do not change, it is convenient to
describe the method in terms of the matrix alone:
All A12 A13 . . . Aln
A21 A22 A23 . . . A2n
. . . . .
An1 An2 An3 . . . Ann
The heart of the algorithm is the technique for eliminating Azl i.e., replacing
it with a zero. This is accomplished by multiplying the first equation (first
row of the matrix) by A21/A11 and subtracting it from the second row or
equation; in the process, all of the elements in the second row of the matrix
are modified as is the second element of the forcing vector on the right hand
side of the equation. The other elements of the first column of the matrix,
A31,
. . , Anl are treated similarly; for example, to eliminate Ail, the
first row of the matrix is multiplied by Ail/AI1 and subtracted from the ith
row. By systematically proceeding down the first column of the matrix, all of
the elements below All are eliminated. When this process is complete, none
of the equations 2 , 3 , . . . , n contain the variable $1; they are a set of n - 1
equations for the variables 42, $3, . . . ,$,. The same procedure is then applied
to this smaller set of equations - all of the elements below Az2 in the second
column are eliminated.
This procedure is carried out for columns 1,2,3, . . . , n - 1. After this process is complete, the original matrix has been replaced by an upper triangular
one: