c2-1 (779459)

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

Текст из файла

36Chapter 2.Solution of Linear Algebraic EquationsColeman, T.F., and Van Loan, C. 1988, Handbook for Matrix Computations (Philadelphia: S.I.A.M.).Forsythe, G.E., and Moler, C.B. 1967, Computer Solution of Linear Algebraic Systems (Englewood Cliffs, NJ: Prentice-Hall).Wilkinson, J.H., and Reinsch, C. 1971, Linear Algebra, vol. II of Handbook for Automatic Computation (New York: Springer-Verlag).Johnson, L.W., and Riess, R.D. 1982, Numerical Analysis, 2nd ed. (Reading, MA: AddisonWesley), Chapter 2.Ralston, A., and Rabinowitz, P. 1978, A First Course in Numerical Analysis, 2nd ed.

(New York:McGraw-Hill), Chapter 9.2.1 Gauss-Jordan EliminationFor inverting a matrix, Gauss-Jordan elimination is about as efficient as anyother method. For solving sets of linear equations, Gauss-Jordan eliminationproduces both the solution of the equations for one or more right-hand side vectorsb, and also the matrix inverse A−1 . However, its principal weaknesses are (i) thatit requires all the right-hand sides to be stored and manipulated at the same time,and (ii) that when the inverse matrix is not desired, Gauss-Jordan is three timesslower than the best alternative technique for solving a single linear set (§2.3).

Themethod’s principal strength is that it is as stable as any other direct method, perhapseven a bit more stable when full pivoting is used (see below).If you come along later with an additional right-hand side vector, you canmultiply it by the inverse matrix, of course. This does give an answer, but one that isquite susceptible to roundoff error, not nearly as good as if the new vector had beenincluded with the set of right-hand side vectors in the first instance.For these reasons, Gauss-Jordan elimination should usually not be your methodof first choice, either for solving linear equations or for matrix inversion.

Thedecomposition methods in §2.3 are better. Why do we give you Gauss-Jordan at all?Because it is straightforward, understandable, solid as a rock, and an exceptionallygood “psychological” backup for those times that something is going wrong and youthink it might be your linear-equation solver.Some people believe that the backup is more than psychological, that GaussJordan elimination is an “independent” numerical method. This turns out to bemostly myth. Except for the relatively minor differences in pivoting, describedbelow, the actual sequence of operations performed in Gauss-Jordan elimination isvery closely related to that performed by the routines in the next two sections.For clarity, and to avoid writing endless ellipses (· · ·) we will write out equationsonly for the case of four equations and four unknowns, and with three different righthand side vectors that are known in advance.

You can write bigger matrices andextend the equations to the case of N × N matrices, with M sets of right-handside vectors, in completely analogous fashion. The routine implemented belowis, of course, general.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).Westlake, J.R. 1968, A Handbook of Numerical Matrix Inversion and Solution of Linear Equations(New York: Wiley).372.1 Gauss-Jordan EliminationElimination on Column-Augmented MatricesConsider the linear matrix equation  a12a22a32a42a13a23a33a43=a14x11x12x13y11a24   x21   x22   x23   y21·ttta34x31x32x33y31a44x41x42x43y41b11b12b131 b21  t  b22  t  b23  t  00b31b32b330b41b42b4301000010y12y22y32y42y13y23y33y43y14y24 y34y4400 01(2.1.1)Here the raised dot (·) signifies matrix multiplication, while the operator t justsignifies column augmentation, that is, removing the abutting parentheses andmaking a wider matrix out of the operands of the t operator.It should not take you long to write out equation (2.1.1) and to see that it simplystates that xij is the ith component (i = 1, 2, 3, 4) of the vector solution of the jthright-hand side (j = 1, 2, 3), the one whose coefficients are bij , i = 1, 2, 3, 4; andthat the matrix of unknown coefficients yij is the inverse matrix of aij .

In otherwords, the matrix solution of[A] · [x1 t x2 t x3 t Y] = [b1 t b2 t b3 t 1](2.1.2)where A and Y are square matrices, the bi ’s and xi ’s are column vectors, and 1 isthe identity matrix, simultaneously solves the linear setsA · x1 = b 1A · x2 = b2A · x3 = b3(2.1.3)andA·Y = 1(2.1.4)Now it is also elementary to verify the following facts about (2.1.1):• Interchanging any two rows of A and the corresponding rows of the b’sand of 1, does not change (or scramble in any way) the solution x’s andY. Rather, it just corresponds to writing the same set of linear equationsin a different order.• Likewise, the solution set is unchanged and in no way scrambled if wereplace any row in A by a linear combination of itself and any other row,as long as we do the same linear combination of the rows of the b’s and 1(which then is no longer the identity matrix, of course).• Interchanging any two columns of A gives the same solution set onlyif we simultaneously interchange corresponding rows of the x’s and ofY.

In other words, this interchange scrambles the order of the rows inthe solution. If we do this, we will need to unscramble the solution byrestoring the rows to their original order.Gauss-Jordan elimination uses one or more of the above operations to reducethe matrix A to the identity matrix. When this is accomplished, the right-hand sidebecomes the solution set, as one sees instantly from (2.1.2).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).a11 a21a31a4138Chapter 2.Solution of Linear Algebraic EquationsPivotingSample 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 “Gauss-Jordan elimination with no pivoting,” only the second operation inthe above list is used. The first row is divided by the element a11 (this being atrivial linear combination of the first row with any other row — zero coefficient forthe other row). Then the right amount of the first row is subtracted from each otherrow to make all the remaining ai1 ’s zero. The first column of A now agrees withthe identity matrix. We move to the second column and divide the second row bya22 , then subtract the right amount of the second row from rows 1, 3, and 4, so as tomake their entries in the second column zero.

The second column is now reducedto the identity form. And so on for the third and fourth columns. As we do theseoperations to A, we of course also do the corresponding operations to the b’s and to1 (which by now no longer resembles the identity matrix in any way!).Obviously we will run into trouble if we ever encounter a zero element on the(then current) diagonal when we are going to divide by the diagonal element.

(Theelement that we divide by, incidentally, is called the pivot element or pivot.) Not soobvious, but true, is the fact that Gauss-Jordan elimination with no pivoting (no use ofthe first or third procedures in the above list) is numerically unstable in the presenceof any roundoff error, even when a zero pivot is not encountered. You must never doGauss-Jordan elimination (or Gaussian elimination, see below) without pivoting!So what is this magic pivoting? Nothing more than interchanging rows (partialpivoting) or rows and columns (full pivoting), so as to put a particularly desirableelement in the diagonal position from which the pivot is about to be selected.

Sincewe don’t want to mess up the part of the identity matrix that we have already built up,we can choose among elements that are both (i) on rows below (or on) the one thatis about to be normalized, and also (ii) on columns to the right (or on) the columnwe are about to eliminate. Partial pivoting is easier than full pivoting, because wedon’t have to keep track of the permutation of the solution vector.

Partial pivotingmakes available as pivots only the elements already in the correct column. It turnsout that partial pivoting is “almost” as good as full pivoting, in a sense that can bemade mathematically precise, but which need not concern us here (for discussionand references, see [1]). To show you both variants, we do full pivoting in the routinein this section, partial pivoting in §2.3.We have to state how to recognize a particularly desirable pivot when we seeone. The answer to this is not completely known theoretically.

It is known, boththeoretically and in practice, that simply picking the largest (in magnitude) availableelement as the pivot is a very good choice. A curiosity of this procedure, however, isthat the choice of pivot will depend on the original scaling of the equations. If we takethe third linear equation in our original set and multiply it by a factor of a million, itis almost guaranteed that it will contribute the first pivot; yet the underlying solutionof the equations is not changed by this multiplication! One therefore sometimes seesroutines which choose as pivot that element which would have been largest if theoriginal equations had all been scaled to have their largest coefficient normalized tounity. This is called implicit pivoting.

There is some extra bookkeeping to keep trackof the scale factors by which the rows would have been multiplied. (The routines in§2.3 include implicit pivoting, but the routine in this section does not.)Finally, let us consider the storage requirements of the method. With a littlereflection you will see that at every stage of the algorithm, either an element of A is2.1 Gauss-Jordan Elimination39Here is the routine for Gauss-Jordan elimination with full pivoting:#include <math.h>#include "nrutil.h"#define SWAP(a,b) {temp=(a);(a)=(b);(b)=temp;}void gaussj(float **a, int n, float **b, int m)Linear equation solution by Gauss-Jordan elimination, equation (2.1.1) above.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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