60 Chapter 2.Solution of Linear Algebraic Equations or as a tableau, U 。f4 83 granted for 198891992 11800 (2.6.4) from NUMERICAL RECIPESI Since V is square,it is also row-orthonormal,V.VT =1. The SVD decomposition can also be carried out when M<N.In this case (Nort server 9 the singular values wj for j=M+1,...,N are all zero,and the corresponding columns of U are also zero.Equation (2.6.2)then holds only for k,n <M. America The decomposition (2.6.1)can always be done,no matter how singular the matrix is,and it is"almost"unique.That is to say,it is unique up to (i)making the same permutation of the columns of U,elements of W,and columns of V(or Programs rows of V),or (ii)forming linear combinations of any columns of U and V whose corresponding elements of W happen to be exactly equal.An important consequence of the permutation freedom is that for the case M<N,a numerical algorithm for the decomposition need not return zero wi's for j=M+1,...,N;the N-M 6 zero singular values can be scattered among all positionsj=1,2,...,N. At the end of this section,we give a routine,svdcmp,that performs SVD on an arbitrary matrix A,replacing it by U(they are the same shape)and giving back W and V separately.The routine svdcmp is based on a routine by Forsythe et al.[1],which is in turn based on the original routine of Golub and Reinsch,found,in various forms,in [2-4]and elsewhere.These references include extensive discussion of the algorithm used.As much as we dislike the use of black-box routines,we are Fuurggoglrion going to ask you to accept this one,since it would take us too far afield to cover Numerical Recipes 10621 43108. its necessary background material here.Suffice it to say that the algorithm is very stable,and that it is very unusual for it ever to misbehave.Most of the concepts that (outside enter the algorithm(Householder reduction to bidiagonal form,diagonalization by North Software. QR procedure with shifts)will be discussed further in Chapter 11. Ifyou are as suspicious of black boxes as we are,you will want to verify yourself that svdcmp does what we say it does.That is very easy to do:Generate an arbitrary matrix A,call the routine,and then verify by matrix multiplication that (2.6.1)and (2.6.4)are satisfied.Since these two equations are the only defining requirements for SVD,this procedure is(for the chosen A)a complete end-to-end check. Now let us find out what SVD is good for.60 Chapter 2. Solution of Linear Algebraic Equations Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). or as a tableau,   UT   ·   U   =   VT   ·   V   =   1   (2.6.4) Since V is square, it is also row-orthonormal, V · VT = 1. The SVD decomposition can also be carried out when M<N. In this case the singular values wj for j = M + 1,...,N are all zero, and the corresponding columns of U are also zero. Equation (2.6.2) then holds only for k, n ≤ M. The decomposition (2.6.1) can always be done, no matter how singular the matrix is, and it is “almost” unique. That is to say, it is unique up to (i) making the same permutation of the columns of U, elements of W, and columns of V (or rows of VT ), or (ii) forming linear combinations of any columns of U and V whose corresponding elements of W happen to be exactly equal. An important consequence of the permutation freedom is that for the case M<N, a numerical algorithm for the decomposition need not return zero wj ’s for j = M + 1,...,N; the N − M zero singular values can be scattered among all positions j = 1, 2,...,N. At the end of this section, we give a routine, svdcmp, that performs SVD on an arbitrary matrix A, replacing it by U (they are the same shape) and giving back W and V separately. The routine svdcmp is based on a routine by Forsythe et al. [1], which is in turn based on the original routine of Golub and Reinsch, found, in various forms, in [2-4] and elsewhere. These references include extensive discussion of the algorithm used. As much as we dislike the use of black-box routines, we are going to ask you to accept this one, since it would take us too far afield to cover its necessary background material here. Suffice it to say that the algorithm is very stable, and that it is very unusual for it ever to misbehave. Most of the concepts that enter the algorithm (Householder reduction to bidiagonal form, diagonalization by QR procedure with shifts) will be discussed further in Chapter 11. If you are as suspicious of black boxes as we are, you will want to verify yourself that svdcmp does what we say it does. That is very easy to do: Generate an arbitrary matrix A, call the routine, and then verify by matrix multiplication that (2.6.1) and (2.6.4) are satisfied. Since these two equations are the only defining requirements for SVD, this procedure is (for the chosen A) a complete end-to-end check. Now let us find out what SVD is good for