Deturck, Wilf - Lecture Notes on Numerical Analysis (523142), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

. , n, and it is kept at thebottomof the matrix. More precisely, the elements of {τj } are the first n entries of the newlast row of the matrix, where the row contains n + p entries altogether, the last p of whichare not used (refer to (3.3.1) to see the complete partitioning of the matrix C).Now suppose we have arrived at the end of the back solution, and the answers to theoriginal question are before us, except that they are scrambled. Here’s an example of thekind of situation that might result:1 0 0a0 1 0d0 0 1g.. ...

. ··· ···3 5 21b ce f h k ... .. . . 4 ∗(3.6.1)The matrix above represents schematically the reduced row echelon form in a problemwhere there are five unknowns (n = 5), the pseudorank r = 3, just one right-hand sidevector is given (p = 1), and the permuations that were carried out on the columns arerecorded in the array τ : [3, 5, 2, 1, 4] shown in the last row of the matrix as it would bestorded in a computation.The question now is, how do we express the general solution of the given set of equations?To find the answer, let’s go back to the set of equations that (3.6.1) stands for.

The first ofthese isx3 = c − ax1 − bx4(3.6.2)106Numerical linear algebrabecause the numbering of the unknowns is as shown in the τ array. The next two equationsarex5 = f − dx1 − ex4(3.6.3)x2 = k − gx1 − hx4 .If we add the two trivial equations x1 = x1 and x4 = x4 , then we get the whole solutionvector which, after re-ordering the equations, can be written asx1x2x3x4x5=0kc0f + (−x1 ) ∗ −1ga0d + (−x4 ) ∗ 0hb−1e.(3.6.4)Now we are looking at a display of the output as we would like our subroutine to giveit. The three vectors on the right side of (3.6.4) are, respectively, a particular solution ofthe given system of equations, and the two vectors of a basis for the kernel of the coefficientmatrix.The question can now be rephrased: exactly what operations must be done to the matrixshown in (3.6.1) that represents the situation at the end of the back solution, in order toobtain the three vectors in (3.6.4)?The first things to do are, as we have previously noted, to append the negative of a 2 × 2identity matrix to the bottom of the fourth and fifth columns of (3.6.1), and to lengthenthe last column on the right by appending two more zeros.

That brings us to the matrix1000 01 00 1ab cde fgh k−1 0 00 −1 0[3 5 2 14] ∗.(3.6.5)The first two of the three long columns above will be the basis for the kernel, and the lastcolumn above will be the particular solution, but only after we do the right rearrangement.Now here is the punch line: the right rearrangement to do is to permute the rows ofthose three long columns as described by the permuation τ .That means that the first row becomes the third, the second row becomes the fifth, thethird row becomes the second, the fourth row is the new first, and the old fifth row is thenew fourth.

The reader is invited to carry out on the rows the interchanges just described,and to compare the result with what we want, namely with (3.6.4). It will be seen that wehave gotten the desired result.The point that is just a little surprising is that to undo the column interchanges thatare recorded by τ , we do row interchanges.

Just roughly, the reason for this is that webegin by wanting to solve Ax = b, and instead we end up solving (AE)y = b, where E is3.6 To unscramble the eggs107a matrix obtained from the identity by elementary column operations. Evidently, x = Ey,which means that we must perform row operations on y to recover the answers in the rightorder.Now we can leave the example above, and state the rule in general. We are given psystems of m simultaneous equations each, all having a commom m × n coefficient matrixA, in n unknowns. At the end of the back solution we will have before us a matrix of theform I(r, r)B(r, n − r) P (r, p) (3.6.6)where I(r, r) is the r×r identity matrix, r is the pseudorank of A, and B and P are matricesof the sizes shown.We adjoin under B the negative of the (n − r) × (n − r) identity matrix, and under Pwe adjoin an (n − r) × p block of zeros.

Next, we forget the identity matrix on the left,and we consider the entire remaining n × (n − r + p) matrix as a whole, call it T , say. Nowwe exchange the rows of T according to the permuation array τ . Preciesly, row 1 of T willbe row τ1 of the new T , row 2 will be row τ2 , . . . . Conceptually, we should regard theold T and the new T as occupying different areas of storage, so that the new T is just arearrangement of the rows of the old.Now the first n − r columns of the new T are a basis for the kernel of A, and should beoutput as such, and the jth one of the last p columns of the new T is a particular solutionof the jth one of the input systems of equations, and should be output as such.Although conceptually we should think of the old T and the new T as occupying distinctarrays in memory, in fact it is perfectly possible to carry out the whole row interchangeprocedure described above in just one array, the one that holds T , without ever “steppingon our own toes,” so let’s consider that problem.Suppose a linear array a = [a1 , .

. . , an ] is given, along with a permutation array τ =[τ1 , . . . , τn ]. We want to rearrange the entries of the array a according to the permuation τwithout using any additional array storage. Thus the present array a1 will end up as theoutput aτ1 , the initial a2 will end up as aτ2 , etc.To do this with no extra array storage, let’s first pick up the element a1 and move it toaτ1 , being careful to store the original aτ1 in a temporary location t so it won’t be destroyed.Next we move the contents of t to its destination, and so forth. After a certain number ofsteps (maybe only 1), we will be back to a1 .Her’s an example to help clarify the situation. Suppose the arrays a and τ at input timewere:a = [5, 7, 13, 9, 2, 8](3.6.7)τ = [3, 4, 5, 2, 1, 6].So we move the 5 in position a1 to position a3 (after putting the 13 into a safe place), andthen the 13 goes to position a5 (after putting the 2 into a safe place) and the 2 is movedinto position a1 , and we’re back where we started.

The a array now has becomea = [2, 7, 5, 9, 13, 8].(3.6.8)108Numerical linear algebraThe job, however, is not finished. Somehow we have to recognize that the elements a2 ,a4 and a6 haven’t yet been moved, while the others have been moved to their destinations.For this purpose we will flag the array positions. A convenient place to hang a flag is inthe sign position of an entry of the array τ , since we’re sure that the entries of τ are allsupposed to be positive. Therefore, initially we’ll change the signs of all of the entries of τto make them negative. Then as elements are moved around in the a array we will reversethe sign of the corresponding entry of the τ array. In that way we can always begin thenext block of entries of a to move by searching τ for a negative entry.

When none exist, thejob is finished.Here’s a complete algorithm, in Maple:shuffle:=proc(a,tau,n) local i,j,t,q,u,v;#permutes the entries of a according to the permutation tau## flag entries of tau with negative signsfor i from 1 to n do tau[i]:=-tau[i] od;for i from 1 to n do# has entry i been moved?if tau[i]<0 then# move the block of entries beginning at a[i]t:=i; q:=-tau[i]; tau[i]:=q;u:=a[i]; v:=u;while q<>t dov:=a[q]; a[q]:=u; tau[q]:=-tau[q];u:=v; q:=tau[q]; od;a[t]:=v;fi;od;return(1);end;The reader should carefullythe sample arrays shown above.program, the entries C[r + 1, i],n whose entries are going to beC in rows 1, .

. . , n.3.7trace through the complete operation of this algorithm onIn order to apply the method to the linear equation solvingi = 1. . . . , n are interpreted as τi , and the array a of lengthmoved is one of the columns r + 1, . . . , n + p of the matrixEigenvalues and eigenvectors of matricesOur next topic in numerical linear algebra concerns the computation of the eigenvalues andeigenvectors of matrices. Until further notice, all matrices will be square. If A is n × n, byan eigenvector of A we mean a vector x 6= 0 such thatAx = λx(3.7.1)3.7 Eigenvalues and eigenvectors of matrices109where the scalar λ is called an eigenvalue of A.

We say that the eigenvector x corresponds to,or belongs to, the eigenvalue λ. We will see that in fact the eigenvalues of A are propertiesof the linear mapping that A represents, rather than of the matrix A, so we can exploitchanges of basis in the computation of eigenvalues.For an example, consider the 2 × 2 matrix"A=3 −1−13#.(3.7.2)If we write out the vector equation (3.7.1) for this matrix, it becomes the two scalar equations3x1 − x2 = λx1(3.7.3)−x1 + 3x2 = λx2 .These are two homogeneous equations in two unknowns, and therefore they have no solutionother than the zero vector unless the determinant 3−λ−1−1 3 − λ(3.7.4)is equal to zero.

Характеристики

Список файлов книги