2.2 Gaussian Elimination and Pivoting In this section we develop a scheme for solving a general system AX=B N equations and N unknowns. The goal is to construct an equivalent upper-triangular system UX=Y that can be solved by the method of Section 2.3 Two linear systems of dimension N x N are said to be equivalent provided that their solution sets are the same. Theorems from linear algebra show that when certain transformations are applied to a given system the solution sets do not chan
2.2 Gaussian Elimination and Pivoting In this section we develop a scheme for solving a general system AX = B of N equations and N unknowns. The goal is to construct an equivalent upper-triangular system UX = Y that can be solved by the method of Section 2.3. Two linear systems of dimension N × N are said to be equivalent provided that their solution sets are the same. Theorems from linear algebra show that when certain transformations are applied to a given system the solution sets do not change. 7
Theorem 2.7.(Elementary Transformations). The following operations applied to a linear system yield an equivalent system Interchange: The order of two equations can be changed (212) g Multiplying an equation by a nonzero constant Replacement: An equation can be replaced by the sum of itself and a nonzero multiple of any other equation (214) It is common to use(2. 14) by replacing an equation with the difference of that tion and Itiple of another equation. There concepts are illustrated in the next example Example 2.15. Find the parabola y= A+ Br Ca that passes through the three points(1,1),(2,-1),and(3,1) For each point we obtain an equation relating the value of to the value of y. The resu llt is the linear system A+B+C=1 A+2B+4c A+3B+9C=1 The variable A is eliminated from the second and third equations by subtractin the first equation from them. This is an application of replacement transformation 3) and the resulting equivalent linear system is A+B+C=1 B+3C=2 2B+8C=0 The variable B is eliminated from the third equation in(5)by subtracting from it two times the second equation. We arrive at the equivalent upper-triangular system A+b+C=1 B+3C=2 The back-substitution algorithm is now used to find the coefficients C=4/2=1,B 2-3(2) (-8)-2=7 +2x2 2.3 Triangular factorization In Section 3. 3 we saw how easy it is to solve an upper-triangular system. Now we introduce the concept of factorization of given matrix A into the product of a lower- triangular matrix L that has 1s along the main diagonal and an upper-triangular ma- trix U with nonzero diagonal elements. For ease of notation we illustrate the concepts
Theorem 2.7. (Elementary Transformations). The following operations applied to a linear system yield an equivalent system: Interchange: The order of two equations can be changed. (2.12) Scaling: Multiplying an equation by a nonzero constant. (2.13) Replacement: An equation can be replaced by the sum of itself and a nonzero multiple of any other equation. (2.14) It is common to use (2.14) by replacing an equation with the difference of that equation and a multiple of another equation. There concepts are illustrated in the next example. Example 2.15. Find the parabola y = A + Bx + Cx2 that passes through the three points (1, 1),(2, −1), and (3, 1). For each point we obtain an equation relating the value of x to the value of y. The result is the linear system A + B + C = 1 at (1, 1) A + 2B + 4C = −1 at (2, −1) A + 3B + 9C = 1 at (3, 1). (2.15) The variable A is eliminated from the second and third equations by subtracting the first equation from them. This is an application of replacement transformation (3), and the resulting equivalent linear system is A + B + C = 1 B + 3C = 2 2B + 8C = 0. The variable B is eliminated from the third equation in (5) by subtracting from it two times the second equation. We arrive at the equivalent upper-triangular system: A + B + C = 1 B + 3C = 2 2C = 4. The back-substitution algorithm is now used to find the coefficients C = 4/2 = 1, B = −2 − 3(2) = −8, and A = 1 − (−8) − 2 = 7, and equation of the parabola is y = 7 − 8x + 2x 2 . 2.3 Triangular Factorization In Section 3.3 we saw how easy it is to solve an upper-triangular system. Now we introduce the concept of factorization of given matrix A into the product of a lowertriangular matrix L that has 1’s along the main diagonal and an upper-triangular matrix U with nonzero diagonal elements. For ease of notation we illustrate the concepts 8