[ Pobierz całość w formacie PDF ]

will be a natural extension of the familiar process of Gaussian elimination. Let s begin with
a little example, say of the following set of two equations in three unknowns:
x + y + z =2
(3.2.1)
x - y - z =5.
If we subtract the second equation from the first, then the two equations can be written
x + y + z = 2
(3.2.2)
2y + 2z = -3.
We divide the second equation by 2, and then subtract it from the first, getting
7
x =
2
(3.2.3)
y + z = -3.
2
The value of z can now be chosen arbitrarily, and then x and y will be determined. To
make this more explicit, we can rewrite the solution in the form
îø ùø îø ùø îø ùø
7
x 0
2
ïø úø ïø úø ïø úø
y =
ðø ûø ðø -3 + z -1 . (3.2.4)
ûø ðø ûø
2
z 0 1
3.2 Linear systems 87
In (3.2.4) we see clearly that the general solution is the sum of a particular solution
(7/2, -3/2, 0), plus any multiple of the basis vector (0, -1, 1) for the kernel of the coef-
ficient matrix of (3.2.1).
The calculation can be compactified by writing the numbers in a matrix and omitting
the names of the unknowns. A vertical line in the matrix will separate the left sides and
the right sides of the equations. Thus, the original system (3.2.1) is
1 1 1 2
. (3.2.5)
1 -1 -1 5
- - -
Now we do (-’! 2) := (-’! 1) - (-’! 2) and we have
row row row
1 1 1 2
. (3.2.6)
0 2 2 -3
- - - - -
Next (-’! 2) := (-’! 2)/2, and then (-’! 1) := (-’! 1) - (-’! 2) bring us to the final form
row row row row row
7
1 0 0
2
(3.2.7)
0 1 1 -3
2
which is the matrix equivalent of (3.2.3).
Now we will step up to a slightly larger example, to see some of the situations that
can arise. We won t actually write the numerical values of the coefficients, but we ll use
asterisks instead. So consider the three equations in five unknowns shown below.
îø ùø
" " " " " "
ïø úø
" " " " " " . (3.2.8)
ðø ûø
" " " " " "
The first step is to create a 1 in the extreme upper left corner, by dividing the first row
through by the [1,1] element. We will assume for the moment that the various numbers
that we want to divide by are not zero. Later on we will take extensive measures to assure
this.
After we divide the first row by the [1,1] element, we use the 1 in the upper left-hand
corner to zero out the entries below it in column 1. That is, we let t = a21 and then do
-’! -’! -’!
- - -
row(2) := row(2) - t " row(1). (3.2.9)
Then let t = a31 and do
-’! -’! -’!
- - -
row(3) := row(3) - t " row(1). (3.2.10)
The result is that we nowhave the matrix
îø ùø
1 " " " " "
ïø úø
0 " " " " " . (3.2.11)
ðø ûø
0 " " " " "
88 Numerical linear algebra
We pause for a moment to consider what we ve done, in terms of the original set of
simultaneous equations. First, to divide a row of the matrix by a number corresponds
to dividing an equation through by the same number. Evidently this does not change
the solutions of the system of equations. Next, to add a constant multiple of one row to
another in the matrix corresponds to adding a multiple of one equation to another, and this
also doesn t affect the solutions. Finally, in terms of the linear mapping that the matrix
represents, what we are doing is changing the sets of basis vectors, keeping the mapping
fixed, in such a way that the matrix that represents the mapping becomes a bit more
acceptable to our taste.
Now in (3.2.11) we divide through the second row by a22 (again blissfully assuming that
a22 is not zero) to create a 1 in the [2,2] position. Then we use that 1 to create zeroes (just
one zero in this case) below it in the second column by letting t = a32 and doing
-’! -’! -’!
- - -
row(3) := row(3) - t " row(2). (3.2.12)
Finally, we divide the third row by the [3,3] element to obtain
îø ùø
1 " " " " "
ïø úø
0 1 " " " " . (3.2.13)
ðø ûø
0 0 1 " " "
This is the end of the so-called forward solution, the first phase of the process of obtaining
the general solution.
Again, let s think about the system of equations that is represented here. What is
special about them is that the first unknown does not appear in the second equation, and
neither the first nor the second unknown appears in the third equation.
To finish the solution of such a system of equations we would use the third equation to
express x3 in terms of x4 and x5, then the second equation would give us x2 in terms of x4
and x5, and finally the first equation would yield x1, also expressed in terms of x4 and x5.
Hence, we would say that x4 and x5 are free, and that the others are determined by them.
More precisely, we should say that the kernel of A has a two-dimensional basis.
Let s see how all of this will look if we were to operate directly on the matrix (3.2.13).
The second phase of the solution, that we are now beginning, is called the backwards sub-
stitution, because we start with the last equation and work backwards.
First we use the 1 in the [3,3] position to create zeros in the third column above that 1.
To do this we let t = a23 and then we do
-’! -’! -’!
- - -
row(2) := row(2) - t " row(3). (3.2.14)
Then we let t = a13 and set
-’! -’! -’!
- - -
row 1 := row(1) - t " row(3) (3.2.15)
resulting in
îø ùø
1 " 0 " " "
ïø úø
0 1 1 " " " . (3.2.16)
ðø ûø
0 0 1 " " "
3.2 Linear systems 89
Observe that nowx3 does not appear in the equations before it. Next we use the 1 in
the [2,2] position to create a zero in column 2 above that 1 by letting t = a12 and
-’! -’! -’!
- - -
row(1) := row(1) - t " row(2). (3.2.17)
Of course, none of our previously constructed zeros gets wrecked by this process, and we
have arrived at the reduced echelon form of the original system of equations
îø ùø
1 0 0 " " "
ïø úø
0 1 0 " " " . (3.2.18)
ðø ûø
0 0 1 " " "
We need to be more careful about the next step, so it s time to use numbers instead of
asterisks. For instance, suppose that we have now arrived at
îø ùø
1 0 0 a14 a15 a16
ïø
0 1 0 a24 a25 a26 úø . (3.2.19)
ðø ûø
0 0 1 a34 a35 a36
Each of the unknowns is expressible in terms of x4 and x5:
x1 = a16 - a14x4 - a15x5
x2 = a26 - a24x4 - a25x5 [ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • moje-waterloo.xlx.pl

    •