Chapter 2.Solution of Linear Algebraic Equations http://www.nr.com or call 2.0 Introduction 1-800-872 Cambridge NUMERICAL RECIPES IN A set of linear algebraic equations looks like this: to make University a11c1+a12x2+a13c3+··+a1NEN=b1 one paper Press a21E1+a22T2+a23r3+···+a2NEN=b2 9 a31T1+a32x2+a33T3+·+a3NEN=b3 (2.0.1) strictly Programs C:THE ART OF SCIENTIFIC aM1I1 aM2T2 aM33+..+aMNIN bM 6 yright(C) Here the N unknowns zj,j=1,2,...,N are related by M equations.The COMPUTING coefficients aij with i =1,2,...,M and j=1,2,...,N are known numbers,as are the right-hand side quantities bi.i=1.2.....M 188-1992 v@cambr urther Nonsingular versus Singular Sets of Equations Numerical Recipes 58/06211401099 If N =M then there are as many equations as unknowns,and there is a good chance of solving for a unique solution set of is.Analytically,there can fail to be a unique solution if one or more of the M equations is a linear combination of (outside the others,a condition called row degeneracy,or if all equations contain certain North Software. variables only in exactly the same linear combination,called column degeneracy. (For square matrices,a row degeneracy implies a column degeneracy,and vice versa.)A set of equations that is degenerate is called singular.We will consider America) visit website singular matrices in some detail in 82.6. machine Numerically,at least two additional things can go wrong: While not exact linear combinations of each other,some of the equations may be so close to linearly dependent that roundoff errors in the machine render them linearly dependent at some stage in the solution process.In this case your numerical procedure will fail,and it can tell you that it has failed. 32Permission 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). Chapter 2. Solution of Linear Algebraic Equations 2.0 Introduction A set of linear algebraic equations looks like this: a11x1 + a12x2 + a13x3 + ··· + a1N xN = b1 a21x1 + a22x2 + a23x3 + ··· + a2N xN = b2 a31x1 + a32x2 + a33x3 + ··· + a3N xN = b3 ··· ··· aM1x1 + aM2x2 + aM3x3 + ··· + aMN xN = bM (2.0.1) Here the N unknowns xj , j = 1, 2,...,N are related by M equations. The coefficients aij with i = 1, 2,...,M and j = 1, 2,...,N are known numbers, as are the right-hand side quantities bi, i = 1, 2,...,M. Nonsingular versus Singular Sets of Equations If N = M then there are as many equations as unknowns, and there is a good chance of solving for a unique solution set of xj ’s. Analytically, there can fail to be a unique solution if one or more of the M equations is a linear combination of the others, a condition called row degeneracy, or if all equations contain certain variables only in exactly the same linear combination, called column degeneracy. (For square matrices, a row degeneracy implies a column degeneracy, and vice versa.) A set of equations that is degenerate is called singular. We will consider singular matrices in some detail in §2.6. Numerically, at least two additional things can go wrong: • While not exact linear combinations of each other, some of the equations may be so close to linearly dependent that roundoff errors in the machine render them linearly dependent at some stage in the solution process. In this case your numerical procedure will fail, and it can tell you that it has failed. 32