c2-11 (779469)
Текст из файла
102Chapter 2.Solution of Linear Algebraic EquationsWe will make use of QR decomposition, and its updating, in §9.7.CITED REFERENCES AND FURTHER READING:Golub, G.H., and Van Loan, C.F. 1989, Matrix Computations, 2nd ed. (Baltimore: Johns HopkinsUniversity Press), §§5.2, 5.3, 12.6. [2]2.11 Is Matrix Inversion an N 3 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 startwith a seemingly simple question:How many individual multiplications does it take to perform the matrixmultiplication of two 2 × 2 matrices,a11a21a12a22 b11·b21b12b22=c11c21c12c22(2.11.1)Eight, right? Here they are written explicitly:c11 = a11 × b11 + a12 × b21c12 = a11 × b12 + a12 × b22c21 = a21 × b11 + a22 × b21(2.11.2)c22 = a21 × b12 + a22 × b22Do you think that one can write formulas for the c’s that involve only sevenmultiplications? (Try it yourself, before reading on.)Such a set of formulas was, in fact, discovered by Strassen [1]. The formulas are:Q1 ≡ (a11 + a22 ) × (b11 + b22 )Q2 ≡ (a21 + a22 ) × b11Q3 ≡ a11 × (b12 − b22 )Q4 ≡ a22 × (−b11 + b21 )Q5 ≡ (a11 + a12 ) × b22Q6 ≡ (−a11 + a21 ) × (b11 + b12 )Q7 ≡ (a12 − a22 ) × (b21 + b22 )(2.11.3)Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Wilkinson, J.H., and Reinsch, C. 1971, Linear Algebra, vol.
II of Handbook for Automatic Computation (New York: Springer-Verlag), Chapter I/8. [1]2.11 Is Matrix Inversion an N 3 Process?103in terms of whichc11 = Q1 + Q4 − Q5 + Q7c21 = Q2 + Q4c12 = Q3 + Q5(2.11.4)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 anythinghas been gained. But notice that in (2.11.3) the a’s and b’s are never commuted.Therefore (2.11.3) and (2.11.4) are valid when the a’s and b’s are themselvesmatrices.
The problem of multiplying two very large matrices (of order N = 2m forsome integer m) can now be broken down recursively by partitioning the matricesinto quarters, sixteenths, etc. And note the key point: The savings is not just a factor“7/8”; it is that factor at each hierarchical level of the recursion. In total it reducesthe process of matrix multiplication to order N log2 7 instead of N 3 .What about all the extra additions in (2.11.3)–(2.11.4)? Don’t they outweighthe advantage of the fewer multiplications? For large N , it turns out that there aresix times as many additions as multiplications implied by (2.11.3)–(2.11.4).
But,if N is very large, this constant factor is no match for the change in the exponentfrom N 3 to N log2 7 .With this “fast” matrix multiplication, Strassen also obtained a surprising resultfor matrix inversion [1]. Suppose that the matricesa11 a12c11 c12and(2.11.5)a21 a22c21 c22are inverses of each other. Then the c’s can be obtained from the a’s by the followingoperations (compare equations 2.7.22 and 2.7.25):R1 = Inverse(a11 )R2 = a21 × R1R3 = R1 × a12R4 = a21 × R3R5 = R4 − a22R6 = Inverse(R5 )c12 = R3 × R6c21 = R6 × R2R7 = R3 × c21c11 = R1 − R7c22 = −R6(2.11.6)Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).c22 = Q1 + Q3 − Q2 + Q6104Chapter 2.Solution of Linear Algebraic EquationsCITED REFERENCES AND FURTHER READING:Strassen, V. 1969, Numerische Mathematik, vol. 13, pp. 354–356. [1]Kronsjö, L. 1987, Algorithms: Their Complexity and Efficiency, 2nd ed. (New York: Wiley).Winograd, S. 1971, Linear Algebra and Its Applications, vol. 4, pp. 381–388.Pan, V. Ya. 1980, SIAM Journal on Computing, vol. 9, pp. 321–342.Pan, V. 1984, How to Multiply Matrices Faster, Lecture Notes in Computer Science, vol.
179(New York: Springer-Verlag)Pan, V. 1984, SIAM Review, vol. 26, pp. 393–415. [More recent results that show that anexponent of 2.496 can be achieved — theoretically!]Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).In (2.11.6) the “inverse” operator occurs just twice. It is to be interpreted as thereciprocal if the a’s and c’s are scalars, but as matrix inversion if the a’s and c’s arethemselves submatrices. Imagine doing the inversion of a very large matrix, of orderN = 2m , recursively by partitions in half. At each step, halving the order doublesthe number of inverse operations. But this means that there are only N divisions inall! So divisions don’t dominate in the recursive use of (2.11.6). Equation (2.11.6)is dominated, in fact, by its 6 multiplications. Since these can be done by an N log2 7algorithm, so can the matrix inversion!This is fun, but let’s look at practicalities: If you estimate how large N has to bebefore the difference between exponent 3 and exponent log2 7 = 2.807 is substantialenough to outweigh the bookkeeping overhead, arising from the complicated natureof the recursive Strassen algorithm, you will find that LU decomposition is in noimmediate danger of becoming obsolete.If, on the other hand, you like this kind of fun, then try these: (1) Can youmultiply the complex numbers (a+ib) and (c+id) in only three real multiplications?[Answer: see §5.4.] (2) Can you evaluate a general fourth-degree polynomial inx for many different values of x with only three multiplications per evaluation?[Answer: see §5.3.].
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
