Nash - Compact Numerical Methods for Computers (523163), страница 9
Текст из файла (страница 9)
By requiring A+ to satisfyAA + A = A(2.40)(AA+)T = AA+(2.41)andthis can indeed be made to happen. The proposed solution (2.36) is therefore aleast-squares solution under the conditions (2.40) and (2.41) on A+. In order that(2.36) gives the minimum-length least-squares solution, it is necessary that xT x beminimal also. But from equation (2.36) we findx T x = b T (A+ ) T A+ b + g T (1 – A+A) T ( 1 – A+A)g + 2g T(1 – A+ A) TA+ b (2.42)which can be seen to have a minimum atg =0if(1 – A + A) T(2.43)26Compact numerical methods for computersis the annihilator of A+ b, thus ensuring that the two contributions (that is, from band g) to x T x are orthogonal. This requirement imposes on A + the furtherconditionsA+ AA + = A+(2.44)(A+ A)T = A+ A.(2.45)The four conditions (2.40), (2.41), (2.44) and (2.45) were proposed by Penrose(1955).
The conditions are not, however, the route by which A + is computed.Here attention has been focused on one generalised inverse, called the MoorePenrose inverse. It is possible to relax some of the four conditions and arrive atother types of generalised inverse.
However, these will require other conditions tobe applied if they are to be specified uniquely. For instance, it is possible toconsider any matrix which satisfies (2.40) and (2.41) as a generalised inverse of Asince it provides, via (2.33), a least-squares solution to equation (2.14). However,in the rank-deficient case, (2.36) allows arbitrary components from the null spaceof A to be added to this least-squares solution, so that the two-condition generalised inverse is specified incompletely.Over the years a number of methods have been suggested to calculate ‘generalisedinverses’.
Having encountered some examples of dubious design, coding or applications of such methods, I strongly recommend testing computed generalised inversematrices to ascertain the extent to which conditions (2.40), (2.41), (2.44) and (2.45)are satisfied (Nash and Wang 1986).2.5. DECOMPOSITIONS OF A MATRIXIn order to carry out computations with matrices, it is common to decomposethem in some way to simplify and speed up the calculations.
For a real m by nmatrix A, the QR decomposition is particularly useful. This equates the matrix Awith the product of an orthogonal matrix Q and a right- or upper-triangularmatrix R, that isA = QR(2.46)where Q is m by m andQT Q = QQT = 1 m(2.47)and R is m by n with all elementsRij = 0for i > j.(2.48)The QR decomposition leads to the singular-value decomposition of the matrix Aif the matrix R is identified with the product of a diagonal matrix S and an orthogonal matrix VT, that isR = SVT(2.49)where the m by n matrix S is such thatj(2.50)V T V = VVT = 1 n .(2.5 1)Sij = 0for iand V, n by n, is such thatFormal problems in linear algebra27Note that the zeros below the diagonal in both R and S imply that, apart fromorthogonality conditions imposed by (2.47), the elements of columns (n + 1),(n + 2), .
. . , m of Q are arbitrary. In fact, they are not needed in most calculations, so will be dropped, leaving the m by n matrix U, whereUT U = 1n .(2.52)TNote that it is no longer possible to make any statement regarding UU . Omittingrows (n + 1) to m of both R and S allows the decompositions to be written asA = UR = USVT(2.53)where A is m by n, U is m by n and U T U = 1n, R is n by n and upper-triangular, Sis n by n and diagonal, and V is n by n and orthogonal. In the singular-valuedecomposition the diagonal elements of S are chosen to be non-negative.Both the QR and singular-value decompositions can also be applied to squarematrices.
In addition, an n by n matrix A can be decomposed into a product ofa lower- and an upper-triangular matrix, thusA = LR.(2.54)In the literature this is also known as the LU decomposition from the use of ‘U’ for‘upper triangular’. Here another mnemonic, ‘U’ for ‘unitary’ has been employed.If the matrix A is symmetric and positive definite, the decompositionA = LLT(2.55)is possible and is referred to as the Choleski decomposition.A scaled form of this decomposition with unit diagonal elements for L can be writtenA = LDL Twhere D is a diagonal matrix.To underline the importance of decompositions, it can be shown by directsubstitution that ifA = USVT(2.53)then the matrix(2.56)A+ = VS+ U Twherefor Sii 0S = 1/S ii(2.57)0for Sii = 0{satisfies the four conditions (2.40), (2.41), (2.44) and (2.45), that isAA + A = USVT VS+ UT USVT= USS+ SVT= USVT = A(2.58)(2.59)28Compact numerical methods for computersA+ AA+ = VS+ UT USVT VS+ UT= VS+ SS+ UT = VS+ U T = A+(2.60)andT T(A+ A)T = (VS + UT USVT)T = ( VS+ SV )= VS + SVT = A+ A.Several of the above relationships depend on the diagonal nature of S and Son the fact that diagonal matrices commute under multiplication.(2.61)+and2.6.
THE MATRIX EIGENVALUE PROBLEMAn eigenvalue e and eigenvector x of an n by n matrix A, real or complex, arerespectively a scalar and vector which together satisfy the equationAx = ex.(2.62)There will be up to n eigensolutions (e, x) for any matrix (Wilkinson 1965) andfinding them for various types of matrices has given rise to a rich literature. Inmany cases, solutions to the generalised eigenproblemAx = eBx(2.63)are wanted, where B is another n by n matrix. For matrices which are of a sizethat the computer can accommodate, it is usual to transform (2.63) into type(2.62) if this is possible.
For large matrices, an attempt is usually made to solve(2.63) itself for one or more eigensolutions. In all the cases where the author hasencountered equation (2.63) with large matrices, A and B have fortunately beensymmetric, which provides several convenient simplifications, both theoretical andcomputational.Example 2.5. Illustration of the matrix eigenvalue problemIn quantum mechanics, the use of the variation method to determine approximateenergy states of physical systems gives rise to matrix eigenvalue problems if thetrial functions used are linear combinations of some basis functions (see, forinstance, Pauling and Wilson 1935, p 180ff).If the trial function is F, and the energy of the physical system in question isdescribed by the Hamiltonian operator H, then the variation principle seeksstationary values of the energy functional(F, HF)C = (E, F)(2.64)subject to the normalisation condition(F, F) = 1(2.65)where the symbol ( , ) represents an inner product between the elementsseparated by the comma within the parentheses.
This is usually an integral over allFormal problems in linear algebra29the dimensions of the system. If a linear combination of some functions fi,j = 1, 2, . . . ) n, is used for F, that is(2.66)then the variation method gives rise to the eigenvalue problemAx = eBx(2.63)Aij = (fj, Hfi)(2.67)Bij = (fi, fj)(2.68)withandIt is obvious that if B is a unit matrix, that is, if1for i = j(fi, fi) = δ ij = 0for i j{(2.69)a problem of type (2.56) arises. A specific example of such a problem is equation(11.1).PreviousChapter 3THE SINGULAR-VALUE DECOMPOSITION ANDITS USE TO SOLVE LEAST-SQUARES PROBLEMS3.1.
INTRODUCTIONThis chapter presents an algorithm for accomplishing the powerful and versatilesingular-value decomposition. This allows the solution of a number of problems tobe realised in a way which permits instabilities to be identified at the same time.This is a general strategy I like to incorporate into my programs as much aspossible since I find succinct diagnostic information invaluable when users raisequestions about computed answers-users do not in general raise too many idlequestions! They may, however, expect the computer and my programs to producereliable results from very suspect data, and the information these programsgenerate together with a solution can often give an idea of how trustworthy arethe results.
This is why the singular values are useful. In particular, the appearance of singular values differing greatly in magnitude implies that our data arenearly collinear. Collinearity introduces numerical problems simply because smallchanges in the data give large changes in the results. For example, consider thefollowing two-dimensional vectors:A = (1, 0)TB = (1, 0·1)TC = (0·95, 0·1)T.Vector C is very close to vector B, and both form an angle of approximately 6°with vector A. However, while the angle between the vector sums (A + B) and(A + C) is only about 0.07°, the angle between (B – A) and (C – A) is greaterthan 26°.
On the other hand, the set of vectorsA = (1, 0)TD = (0, 1)TE = (0, 0·95)Tgives angles between (A + D) and (A + E) and between (D – A) and (E – A) ofapproximately 1·5°. In summary, the sum of collinear vectors is well determined,the difference is not. Both the sum and difference of vectors which are notcollinear are well determined.30HomeNextSingular-value decomposition, and use in least-squares problems313.2. A SINGULAR-VALUE DECOMPOSITION ALGORITHMIt may seem odd that the first algorithm to be described in this work is designed tocompute the singular-value decomposition (svd) of a matrix. Such computations aretopics well to the back of most books on numerical linear algebra.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
