Deturck, Wilf - Lecture Notes on Numerical Analysis (523142), страница 20
Текст из файла (страница 20)
Next, to add a constant multiple of one row toanother in the matrix corresponds to adding a multiple of one equation to another, and thisalso doesn’t affect the solutions. Finally, in terms of the linear mapping that the matrixrepresents, what we are doing is changing the sets of basis vectors, keeping the mappingfixed, in such a way that the matrix that represents the mapping becomes a bit moreacceptable to our taste.Now in (3.2.11) we divide through the second row by a22 (again blissfully assuming thata22 is not zero) to create a 1 in the [2,2] position. Then we use that 1 to create zeroes (justone zero in this case) below it in the second column by letting t = a32 and doing−−→−→ − t ∗ −−→row(3):= −row(3)row(2).(3.2.12)Finally, we divide the third row by the [3,3] element to obtain1 ∗ ∗ ∗ ∗ ∗ 0 1 ∗ ∗ ∗ ∗ .0 0 1 ∗ ∗ ∗(3.2.13)This is the end of the so-called forward solution, the first phase of the process of obtainingthe general solution.Again, let’s think about the system of equations that is represented here.
What isspecial about them is that the first unknown does not appear in the second equation, andneither 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 toexpress x3 in terms of x4 and x5 , then the second equation would give us x2 in terms of x4and 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 substitution, 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−−→−−→ − t ∗ −−→row(2):= row(2)row(3).(3.2.14)−−→ 1 := −−→−→rowrow(1)−t∗−row(3)(3.2.15)Then we let t = a13 and setresulting in1 ∗ 0 ∗ ∗ ∗ 0 1 1 ∗ ∗ ∗ .0 0 1 ∗ ∗ ∗(3.2.16)3.2 Linear systems89Observe that now x3 does not appear in the equations before it.
Next we use the 1 inthe [2,2] position to create a zero in column 2 above that 1 by letting t = a12 and−−→−→ − t ∗ −−→row(1):= −row(1)row(2).(3.2.17)Of course, none of our previously constructed zeros gets wrecked by this process, and wehave arrived at the reduced echelon form of the original system of equations1 0 0 ∗ ∗ ∗ 0 1 0 ∗ ∗ ∗ .0 0 1 ∗ ∗ ∗(3.2.18)We need to be more careful about the next step, so it’s time to use numbers instead ofasterisks. For instance, suppose that we have now arrived at1 0 0 a14 a15 a16 0 1 0 a24 a25 a26 .0 0 1 a34 a35 a36(3.2.19)Each of the unknowns is expressible in terms of x4 and x5 :x1x2x3x4x5= a16 − a14 x4 − a15 x5= a26 − a24 x4 − a25 x5= a36 − a34 x4 − a35 x5=x4=x5 .(3.2.20)This means that we have found the general solution of the given system by finding aparticular solution and a pair of basis vectors for the kernel of A.
They are, respectively,the vector and the two columns of the matrix shown below:a16a26a3600,a14a24a34−10a15a25a350−1.(3.2.21)As this shows, we find a particular solution by filling in extra zeros in the last columnuntil its length matches the number (five in this case) of unknowns. We find a basis matrix(i.e., a matrix whose columns are a basis for the kernel of A) by extending the fourth andfifth columns of the reduced row echelon form of A with −I, where I is the identity matrixwhose size is equal to the nullity of the system, in this case 2.It’s time to deal with the case where one of the ∗’s that we divide by is actually a zero.In fact we will have to discuss rather carefully what we mean by zero. In numerical work oncomputers, in the presence of rounding errors, it is unreasonable to expect a 0 to be exactlyzero.
Instead we will set a certain threshold level, and numbers that are smaller than thatwill be declared to be zero. The hard part will be the determination of the right threshold,90Numerical linear algebrabut let’s postpone that question for a while, and make the convention that in this and thefollowing sections, when we speak of matrix entries being zero, we will mean that their sizeis below our current tolerance level.With that understanding, suppose we are carrying out the row reduction of a certainsystem, and we’ve arrived at a stage like this:1000...∗100...∗∗0∗...∗∗∗∗...············...∗∗∗∗...∗∗∗∗....(3.2.22)Normally, the next step would be to divide by a33 , but it is zero. This means that x3happens not to appear in the third equation.
However, x3 might appear in some laterequation.If so, we can renumber the equations so that later equation becomes the third equation,and continue the process. In the matrix, this means that we would exchange two rows, soas to bring a nonzero entry into the [3,3] position, and continue.It is possible, though, that x3 does not appear in any later equation. Then all entriesai3 = 0 for i ≥ 3.
Then we could ask for some other unknown xj for j > 3 that does appearin some equation later than the third. In the matrix, this amounts to searching throughthe whole rectangle that lies “southeast” of the [3,3] position, extending over to, but notbeyond, the vertical line, to find a nonzero entry, if there is one.If aij is such a nonzero entry, then we want next to bring aij into the pivot position [3,3].We can do this in two steps.
First we exchange rows 3 and i (interchange two equations).Second, exchange columns 3 and j (interchange the numbers of the unknowns, so that x3becomes x0j and xj becomes x03 ). We must remember somehow that we renumbered theunknowns, so we’ll be able to recognize the answers when we see them. The calculation cannow proceed from the rejuvenated pivot element in the [3,3] position.Else, it may happen that the rectanglethis:1 ∗ ∗ 0 1 ∗ 0 0 0 0 0 0 0 0 0.. ..
... . .southeast of [3,3] consists entirely of zeros, like∗∗000...∗∗000...···············...∗∗∗∗∗....(3.2.23)What then? We’re finished with the forward solution. The equations from the third onwardshave only zeros on their left-hand sides. If any solutions at all exist, then those equationshad better have only zeros on their right-hand sides also. The last three ∗’s in the lastcolumn (and all the entries below them) must all be zeros, or the calculation halts with theannouncement that the input system was inconsistent (i.e, has no solutions).
If the systemis consistent, then of course we ignore the final rows of zeros, and we do the backwardssolution just as in the preceding case.3.2 Linear systems91It follows that in all cases, whether there are more equations than unknowns, fewer, orthe same number, the backwards solution always begins with a matrix that has a diagonalof 1’s stretching from top to bottom (the bottom may have moved up, though!), with onlyzero entries below the 1’s on the diagonal.Speaking in theoretical, rather than practical terms for a moment, the number of nonzerorows in the coefficient matrix at the end of the forward solution phase is the rank of thematrix. Speaking practically again, this number simply represents a number of rows beyondwhich we cannot do any more reductions because the matrix entries are all indistinguishablefrom zero. Perhaps a good name for it is pseudorank.
The pseudorank should be thoughtof then, not as some interesting property of the matrix that we have just computed, but asthe number of rows we were able to reduce before roundoff errors became overwhelming.Exercises 3.2In problems 1–5, solve each system of equations by transforming the coefficient matrixto reduced echelon form. To “solve” a system means either to show that no solution existsor to find all possible solutions. In the latter case, exhibit a particular solution and a basisfor the kernel of the coefficient matrix.1.2x3x7x8x−+−+yyyy+ z = 6+ 2z = 3+ 4z = 15+ 5z = 12(3.2.24)2.x + y + z + q = 0x − y − z − q = 0(3.2.25)x + y + z =33x − y − 2z = −15x + y=7(3.2.26)3x + u + v + w + t = 1x − u + 2v + w − 3t = 2(3.2.27)3.4.5.x2xx3x+ 3y − z =4− y + 2z =6+ y + z =6− y − z = −2(3.2.28)6. Construct a set of four equations in four unknowns, of rank two.7.
Construct a set of four equations in three unknowns, with a unique solution.8. Construct a system of homogeneous equations that has a three-dimensional vectorspace of solutions.92Numerical linear algebra9. Under precisely what conditions is the set of all solutions of the system Ax = b avector space?10. Given a set of m vectors in n space, describe an algorithm that will extract a maximalsubset of linearly independent vectors.11.
Given a set of m vectors, and one more vector w, describe an algorithm that willdecide whether or not w is in the vector subspace spanned by the given set.3.3Building blocks for the linear equation solverLet’s now try to amplify some of the points raised by the informal discussion of the procedurefor solving linear equations, with a view towards the development of a formal algorithm.First, let’s deal with the fact that a diagonal element might be zero (in the fuzzy sensedefined in the previous section) at the time when we want to divide by it.Consider the moment when we are carrying out the forward solution, we have made i− 11’s down the diagonal, all the entries below the 1’s are zeros, and next we want to put a 1into the [i, i] position and use that 1 as a pivot to reduce the entries below it to zeros.Previously we had said that this could be done by dividing through the ith row by the[i, i] element, unless that element is zero, in which case we carry out a search for somenonzero element in the rectangle that lies southeast of [i, i] in the matrix.
After carefulanalysis, it turns out that an even more conservative approach is better: the best procedureconsists in searching through the entire southeast rectangle, whether or not the [i, i] elementis zero, to find the largest matrix element in absolute value.If this complete search is done every time, whether or not the [i, i] element is zero, thenit develops that the sizes of the matrix elements do not grow very much as the algorithmunfolds, and the growth of the numerical errors is also kept to a minimum.If that largest element found in the rectangle is, say, auv , then we bring auv into the pivotposition [i, i] by interchanging rows u and i (renumbering the equations) and interchangingcolumns v and i (renumbering the unknowns). Then we proceed as before.It may seem wasteful to make a policy of carrying out a complete search of the rectanglewhenever we are ready to find the next pivot element, and especially even if a nonzeroelement already occupies the pivot position anyway, without a search, but it turns out thatthe extra labor is well rewarded with optimum numerical accuracy and stability.If we are solving m equations in n unknowns, then we need to carry along an extraarray of length n.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
