Đang chuẩn bị liên kết để tải về tài liệu:
Solution of Linear Algebraic Equations part 12

We will make use of QR decomposition, and its updating, in §9.7. CITED REFERENCES AND FURTHER READING: Wilkinson, J.H., and Reinsch, C. 1971, Linear Algebra, vol. II of Handbook for Automatic Computation (New York: Springer-Verlag), Chapter I/8. [1] Golub, G.H., and Van Loan, C.F. 1989, Matrix Computations, 2nd ed. (Baltimore: Johns Hopkins University Press), §§5.2, 5.3, 12.6. [2] | 102 Chapter 2. Solution of Linear Algebraic Equations We will make use of QR decomposition and its updating in 9.7. CITED REFERENCES AND FURTHER READING Wilkinson J.H. and Reinsch C. 1971 Linear Algebra vol. II of Handbook for Automatic Computation New York Springer-Verlag Chapter I 8. 1 Golub G.H. and Van Loan C.F. 1989 Matrix Computations 2nd ed. Baltimore Johns Hopkins University Press 5.2 5.3 12.6. 2 2.11Is Matrix Inversion anN3 Process We close this chapter with a little entertainment a bit of algorithmic prestidigitation which probes more deeply into the subject of matrix inversion. We start with a seemingly simple question How many individual multiplications does it take to perform the matrix multiplication of two 2 x 2 matrices 11 21 2.11.1 Eight right Here they are written explicitly cii 11 x bn ai2 x 21 C12 11 x bi2 12 x b22 C21 21 x bii 22 x b21 C22 21 x bi2 22 x b22 2.11.2 Do you think that one can write formulas for the c s that involve only seven multiplications Try it yourself before reading on. Such a set of formulas was infact discovered by Strassen 1 . The formulas are Qi 11 22 x bii b22 Q2 21 22 x bii Q3 11 x bi2 b22 Q4 22 x bii 21 2.11.3 Q5 11 12 x b22 Q6 11 21 x b11 b12 Q7 12 22 x b21 b22 Sample page from NUMERICAL RECIPES IN C THE ART OF SCIENTIFIC COMPUTING ISBN 0-521-43108-5 2.111s Matrix Inversion an N3 Process in terms of which cii Qi Q4 Q5 Q7 C21 Q2 Q4 C12 Q3 Q5 103 2.11.4 C22 Q1 Q3 Q2 Q6 What s the use of this There is one fewer multiplication than in equation 2.11.2 but many more additions and subtractions. It is not clear that anything has been gained. But notice that in 2.11.3 the as and Vs are never commuted. Therefore 2.11.3 and 2.11.4 are valid when the a s and Vs are themselves matrices. The problem of multiplying two very large matrices of order N 2m for some integer m can now be broken down recursively by partitioning the matrices into quarters sixteenths etc. And note the key point The savings is not just a factor 7 8 it is .