Naive Gaussian Elimination PDF

1 NAÏVE GAUSSSIAN ELIMINATION How is a set of equations solved numerically? One of the most popular techniques for solving simultaneous linear equations is the Gaussian elimination method. The approach is designed to solve a general set of n equations and n unknowns a11x1 + a12...

1 NAÏVE GAUSSSIAN ELIMINATION How is a set of equations solved numerically? One of the most popular techniques for solving simultaneous linear equations is the Gaussian elimination method. The approach is designed to solve a general set of n equations and n unknowns a11x1 + a12 x2 + a13 x3 +... + a1n xn = b1 a21x1 + a22 x2 + a23 x3 +... + a2 n xn = b2...... an1 x1 + an 2 x2 + an3 x3 +... + ann xn = bn Gaussian elimination consists of two steps 1. Forward Elimination of Unknowns: In this step, the unknown is eliminated in each equation starting with the first equation. This way, the equations are reduced to one equation and one unknown in each equation. 2. Back Substitution: In this step, starting from the last equation, each of the unknowns is found. Forward Elimination of Unknowns: In the first step of forward elimination, the first unknown, x1 is eliminated from all rows below the first row. The first equation is selected as the pivot equation to eliminate x1. So, to eliminate x1 in the second equation, one divides the first equation by a11 (hence called the pivot element) and then multiplies it by a21. This is the same as multiplying the first equation by a21 / a11 to give a a a a 21 x1 + 21 a12 x2 +... + 21 a1n xn = 21 b1 a11 a11 a11 Now, this equation can be subtracted from the second equation to give  a   a  a  a 22 − 21 a12  x 2 +... +  a 2 n − 21 a1n  x n = b2 − 21 b1  a11   a11  a11 or  x2 +... + a2 n xn = b2 a22 where a21  = a22 − a22 a12 a11  a21 a2 n = a2 n − a1n a11 This procedure of eliminating x1 , is now repeated for the third equation to the n th equation to reduce the set of equations as a11 x1 + a12 x2 + a13 x3 +... + a1n xn = b1  x2 + a23 a22  x3 +... + a2 n xn = b2  x2 + a33 a32  x3 +... + a3 n xn = b3......... an 2 x2 + an 3 x3 +... + ann  xn = bn ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 1 2 NAÏVE GAUSSSIAN ELIMINATION This is the end of the first step of forward elimination. Now for the second step of forward elimination, we start with the second equation as the pivot equation and a22  as the pivot element. So, to eliminate x2 in the third equation, one divides the second equation by a22 . This is the same  (the pivot element) and then multiply it by a32 as multiplying the second equation by a32  / a22  and subtracting it from the third equation. This makes the coefficient of x2 zero in the third equation. The same procedure is now repeated for the fourth equation till the n th equation to give a11 x1 + a12 x2 + a13 x3 +... + a1n xn = b1  x2 + a23 a22  x3 +... + a2 n xn = b2  x3 +... + a3n xn = b3 a33...... an3 x3 +... + ann  xn = bn The next steps of forward elimination are conducted by using the third equation as a pivot equation and so on. That is, there will be a total of n − 1 steps of forward elimination. At the end of n − 1 steps of forward elimination, we get a set of equations that look like a11 x1 + a12 x2 + a13 x3 +... + a1n x n = b1  x2 + a23 a22  x3 +... + a2 n xn = b2  x3 +... + a3n xn = b3 a33...... (n −1) ann xn = bn(n −1) Back Substitution: Now the equations are solved starting from the last equation as it has only one unknown. b ( n −1) x n = n( n −1) a nn Then the second last equation, that is the (n − 1) th equation, has two unknowns: x n and xn−1 , but x n is already known. This reduces the (n − 1) th equation also to one unknown. Back substitution hence can be represented for all equations by the formula: bi(i −1) −  aij(i −1) x j n j =i +1 xi = for i = n − 1, n − 2,,1 aii(i −1) and bn( n −1) xn = ( n −1) a nn Example 1 The upward velocity of a rocket is given at three different times in Table 1. Table 1 Velocity vs. time data. Time, t (s) Velocity, v (m/s) ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 2 3 NAÏVE GAUSSSIAN ELIMINATION 5 106.8 8 177.2 12 279.2 The velocity data is approximated by a polynomial as v(t ) = a1t 2 + a2t + a3 , 5  t  12 The coefficients a1, a2 , and a3 for the above expression are given by  25 5 1  a1  106.8   64 8 1 a  = 177.2     2   144 12 1  a3  279.2 Find the values of a1, a2 , and a3 using the Naïve Gauss elimination method. Find the velocity at t = 6, 7.5, 9, 11 seconds. Solution Forward Elimination of Unknowns Since there are three equations, there will be two steps of forward elimination of unknowns. First step Divide Row 1 by 25 and then multiply it by 64, that is, multiply Row 1 by 64/25 = 2.56. (25 5 1 106.8) 2.56 gives Row 1 as 64 12.8 2.56 273.408 Subtract the result from Row 2 64 8 1 177.2 − 64 12.8 2.56 273.408 0 − 4.8 − 1.56 − 96.208 to get the resulting equations as  25 5 1   a1   106.8   0 − 4.8 − 1.56 a  = − 96.208    2   144 12 1   a3   279.2  Divide Row 1 by 25 and then multiply it by 144, that is, multiply Row 1 by 144/25 = 5.76. (25 5 1 106.8) 5.76 gives Row 1 as 144 28.8 5.76 615.168 Subtract the result from Row 3 144 12 1 279.2 − 144 28.8 5.76 615.168  0 − 16.8 − 4.76 − 335.968 to get the resulting equations as ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 3 4 NAÏVE GAUSSSIAN ELIMINATION 25 5 1   a1   106.8   0 − 4.8 − 1.56  a  =  − 96.208     2    0 − 16.8 − 4.76  a3  − 335.968 Second step We now divide Row 2 by –4.8 and then multiply by –16.8, that is, multiply Row 2 by − 16.8/ − 4.8 = 3.5. (0 − 4.8 −1.56 − 96.208) 3.5 gives Row 2 as 0 − 16.8 − 5.46 − 336.728 Subtract the result from Row 3 0 − 16.8 − 4.76 − 335.968  − 0 − 16.8 − 5.46 − 336.728  0 0 0.7 0.76 to get the resulting equations as 25 5 1   a1   106.8   0 − 4.8 − 1.56 a  = − 96.208    2    0 0 0.7   a3   0.76  Back substitution From the third equation 0.7a3 = 0.76 0.76 a3 = 0.7 = 1.08571 Substituting the value of a3 in the second equation, − 4.8a 2 − 1.56a3 = −96.208 − 96.208 + 1.56 a3 a2 = − 4.8 − 96.208 + 1.56  1.08571 = − 4.8 = 19.6905 Substituting the value of a2 and a3 in the first equation, 25a1 + 5a 2 + a3 = 106.8 106.8 − 5a 2 − a3 a1 = 25 106.8 − 5  19.6905 − 1.08571 = 25 = 0.290472 Hence the solution vector is  a1  0.290472  a  =  19.6905   2    a3   1.08571  The polynomial that passes through the three data points is then v(t ) = a1t 2 + a2 t + a3 = 0.290472 t 2 + 19.6905t + 1.08571, 5  t  12 ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 4 5 NAÏVE GAUSSSIAN ELIMINATION Since we want to find the velocity at t = 6, 7.5, 9 and 11 seconds, we could simply substitute each value of t in v(t ) = 0.290472 t 2 + 19.6905t + 1.08571 and find the corresponding velocity. For example, at t = 6 v(6) = 0.290472 (6) + 19.6905 (6) + 1.08571 2 = 129.686 m/s However, we could also find all the needed values of velocity at t = 6, 7.5, 9, 11 seconds using matrix multiplication. t 2    v(t ) = 0.290472 19.6905 1.08571  t  1   So, if we want to find v(6), v(7.5), v(9), v(11), it is given by 6 2 7.5 2 9 2 112  v(6) v(7.5) v(9) v(11) = 0.290472 19.6905 1.08571  6 7.5 9 11   1 1 1 1   36 56.25 81 121 = 0.290472 19.6905 1.08571  6 7.5 9 11   1 1 1 1  = 129.686 165.104 201.828 252.828 v(6) = 129.686 m/s v(7.5) = 165.104 m/s v(9) = 201.828 m/s v(11) = 252.828 m/s Example 2 Use Naïve Gauss elimination to solve 20 x1 + 15 x2 + 10 x3 = 45 − 3x1 − 2.249 x2 + 7 x3 = 1.751 5 x1 + x2 + 3x3 = 9 Use six significant digits with chopping in your calculations. Solution Working in the matrix form  20 15 10  x1   45  − 3 − 2.249 7   x  = 1.751    2    5 1 3   x3   9  Forward Elimination of Unknowns First step Divide Row 1 by 20 and then multiply it by –3, that is, multiply Row 1 by − 3 / 20 = −0.15. (20 15 10 45) −0.15 gives Row 1 as − 3 − 2.25 −1.5 − 6.75 Subtract the result from Row 2 ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 5 6 NAÏVE GAUSSSIAN ELIMINATION − 3 − 2.249 7 1.751 − − 3 − 2.25 − 1.5 − 6.75 0 0.001 8.5 8.501 to get the resulting equations as 20 15 10   x1   45   0 0.001 8.5  x  = 8.501    2    5 1 3   x3   9  Divide Row 1 by 20 and then multiply it by 5, that is, multiply Row 1 by 5 / 20 = 0.25 (20 15 10 45) 0.25 gives Row 1 as 5 3.75 2.5 11.25 Subtract the result from Row 3 5 1 3 9 − 5 3.75 2.5 11.25 0 − 2.75 0.5 − 2.25 to get the resulting equations as 20 15 10   x1   45   0 0.001 8.5  x  =  8.501     2    0 − 2.75 0.5  x3  − 2.25 Second step Now for the second step of forward elimination, we will use Row 2 as the pivot equation and eliminate Row 3: Column 2. Divide Row 2 by 0.001 and then multiply it by –2.75, that is, multiply Row 2 by − 2.75 / 0.001 = −2750. (0 0.001 8.5 8.501) −2750 gives Row 2 as 0 − 2.75 − 23375 − 23377.75 Rewriting within 6 significant digits with chopping 0 − 2.75 − 23375 − 23377.7 Subtract the result from Row 3 0 − 2.75 0.5 − 2.25 − 0 − 2.75 − 23375  − 23377.7 0 0 23375.5 23375.45 Rewriting within 6 significant digits with chopping 0 0 23375.5 − 23375.4 to get the resulting equations as 20 15 10   x1   45   0 0.001 8.5   x 2  =  8.501    0 0 23375.5  x3  23375.4 This is the end of the forward elimination steps. Back substitution We can now solve the above equations by back substitution. From the third equation, 23375.5 x3 = 23375.4 23375.4 x3 = 23375.5 = 0.999995 Substituting the value of x3 in the second equation 0.001x2 + 8.5 x3 = 8.501 ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 6 7 NAÏVE GAUSSSIAN ELIMINATION 8.501 − 8.5 x3 x2 = 0.001 8.501 − 8.5  0.999995 = 0.001 8.501 − 8.49995 = 0.001 0.00105 = 0.001 = 1.05 Substituting the value of x3 and x 2 in the first equation, 20 x1 + 15 x2 + 10 x3 = 45 45 − 15 x 2 − 10 x3 x1 = 20 45 − 15  1.05 − 10  0.999995 = 20 45 − 15.75 − 9.99995 = 20 29.25 − 9.99995 = 20 19.2500 = 20 = 0.9625 Hence the solution is  x1  [ X ] =  x2   x3   0.9625  =  1.05  0.999995  Compare this with the exact solution of  x1  X  =  x2   x3  1 = 1 1 Are there any pitfalls of the Naïve Gauss elimination method? Yes, there are two pitfalls of the Naïve Gauss elimination method.. Division by zero: It is possible for division by zero to occur during the beginning of the n −1 steps of forward elimination. For example: 5 x2 + 6 x3 = 11 ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 7 8 NAÏVE GAUSSSIAN ELIMINATION 4 x1 + 5 x2 + 7 x3 = 16 9 x1 + 2 x2 + 3x3 = 15 will result in division by zero in the first step of forward elimination as the coefficient of x1 in the first equation is zero as is evident when we write the equations in matrix form. 0 5 6  x1  11 4 5 7  x  = 16   2    9 2 3  x3  15 But what about the equations below: Is division by zero a problem? 5 x1 + 6 x2 + 7 x3 = 18 10 x1 + 12 x2 + 3x3 = 25 20 x1 + 17 x2 + 19 x3 = 56 Written in matrix form,  5 6 7   x1  18  10 12 3   x  = 25   2    20 17 19   x3  56  there is no issue of division by zero in the first step of forward elimination. The pivot element is the coefficient of x1 in the first equation, 5, and that is a non-zero number. However, at the end of the first step of forward elimination, we get the following equations in matrix form 5 6 7   x1   18  0 0 − 11  x  =  − 11   2    0 − 7 − 9   x3  − 16 Now at the beginning of the 2nd step of forward elimination, the coefficient of x2 in Equation 2 would be used as the pivot element. That element is zero and hence would create the division by zero problem. So, it is important to consider that the possibility of division by zero can occur at the beginning of any step of forward elimination. Round-off error: The Naïve Gauss elimination method is prone to round-off errors. This is true when there are large numbers of equations as errors propagate. Also, if there is subtraction of numbers from each other, it may create large errors. See the example below. Example 3 Remember Example 2 where we used Naïve Gauss elimination to solve 20 x1 + 15 x2 + 10 x3 = 45 − 3x1 − 2.249 x2 + 7 x3 = 1.751 5 x1 + x 2 + 3x3 = 9 using six significant digits with chopping in your calculations? Repeat the problem, but now use five significant digits with chopping in your calculations. Solution Writing in the matrix form ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 8 9 NAÏVE GAUSSSIAN ELIMINATION  20 15 10  x1   45  − 3 − 2.249 7   x  = 1.751    2    5 1 3   x3   9  Forward Elimination of Unknowns First step Divide Row 1 by 20 and then multiply it by –3, that is, multiply Row 1 by − 3 / 20 = −0.15. (20 15 10 45) −0.15 gives Row 1 as − 3 − 2.25 −1.5 − 6.75 Subtract the result from Row 2 − 3 − 2.249 7 1.751 − − 3 − 2.25 − 1.5 − 6.75 0 0.001 8.5 8.501 to get the resulting equations as 20 15 10   x1   45   0 0.001 8.5  x  = 8.501    2    5 1 3   x3   9  Divide Row 1 by 20 and then multiply it by 5, that is, multiply Row 1 by 5 / 20 = 0.25. (20 15 10 45) 0.25 gives Row 1 as 5 3.75 2.5 11.25 Subtract the result from Row 3 5 1 3 9 − 5 3.75 2.5 11.25 0 − 2.75 0.5 − 2.25 to get the resulting equations as 20 15 10   x1   45   0 0.001 8.5  x  =  8.501     2    0 − 2.75 0.5  x3  − 2.25 Second step Now for the second step of forward elimination, we will use Row 2 as the pivot equation and eliminate Row 3: Column 2. Divide Row 2 by 0.001 and then multiply it by –2.75, that is, multiply Row 2 by − 2.75 / 0.001 = −2750. (0 0.001 8.5 8.501) −2750 gives Row 2 as 0 − 2.75 − 23375  − 23377.75 Rewriting within 5 significant digits with chopping 0 − 2.75 − 23375 − 23377  ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 9 10 NAÏVE GAUSSSIAN ELIMINATION Subtract the result from Row 3 0 − 2.75 0.5 − 2.25 − 0 − 2.75 − 23375  − 23377  0 0 23375 23374 Rewriting within 6 significant digits with chopping 0 0 23375 − 23374  to get the resulting equations as 20 15 10   x1   45   0 0.001 8.5  x  =  8.501     2    0 0 23375   x3  23374  This is the end of the forward elimination steps. Back substitution We can now solve the above equations by back substitution. From the third equation, 23375 x3 = 23374 23374 x3 = 23375 = 0.99995 Substituting the value of x3 in the second equation 0.001x2 + 8.5 x3 = 8.501 8.501 − 8.5 x3 x2 = 0.001 8.501 − 8.5  0.99995 = 0.001 8.501 − 8.499575 = 0.001 8.501 − 8.4995 = 0.001 0.0015 = 0.001 = 1.5 Substituting the value of x3 and x 2 in the first equation, 20 x1 + 15 x2 + 10 x3 = 45 45 − 15 x 2 − 10 x3 x1 = 20 45 − 15 1.5 − 10  0.99995 = 20 45 − 22.5 − 9.9995 = 20 22.5 − 9.9995 = 20 12.5005 = 20 12.500 = 20 = 0.625 Hence the solution is ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 10 11 NAÏVE GAUSSSIAN ELIMINATION  x1  X  =  x2   x3   0.625  =  1.5  0.99995  Compare this with the exact solution of  x1  1 X  =  x2  = 1  x3  1 What are some techniques for improving the Naïve Gauss elimination method? As seen in Example 3, round off errors were large when five significant digits were used as opposed to six significant digits. One method of decreasing the round-off error would be to use more significant digits, that is, use double or quad precision for representing the numbers. However, this would not avoid possible division by zero errors in the Naïve Gauss elimination method. To avoid division by zero as well as reduce (not eliminate) round-off error, Gaussian elimination with partial pivoting is the method of choice. How does Gaussian elimination with partial pivoting differ from Naïve Gauss elimination? The two methods are the same, except in the beginning of each step of forward elimination, a row switching is done based on the following criterion. If there are n equations, then there are n − 1 forward elimination steps. At the beginning of the k th step of forward elimination, one finds the maximum of a kk , a k +1,k , …………, a nk Then if the maximum of these values is a pk in the p th row, k  p  n , then switch rows p and k. The other steps of forward elimination are the same as the Naïve Gauss elimination method. The back substitution steps stay the same as the Naïve Gauss elimination method. Example 4 In the previous two examples, we used Naïve Gauss elimination to solve 20 x1 + 15 x2 + 10 x3 = 45 − 3x1 − 2.249 x2 + 7 x3 = 1.751 5 x1 + x 2 + 3x3 = 9 using five and six significant digits with chopping in the calculations. Using five significant digits with chopping, the solution found was  x1  X  =  x2   x3   0.625  =  1.5  0.99995  This is different from the exact solution of ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 11 12 NAÏVE GAUSSSIAN ELIMINATION  x1  X  =  x2   x3  1 = 1 1 Find the solution using Gaussian elimination with partial pivoting using five significant digits with chopping in your calculations. Solution  20 15 10  x1   45  − 3 − 2.249 7   x  = 1.751    2    5 1 3   x3   9  Forward Elimination of Unknowns Now for the first step of forward elimination, the absolute value of the first column elements below Row 1 is 20 , − 3 , 5 Or 20, 3, 5 So, the largest absolute value is in the Row 1. So as per Gaussian elimination with partial pivoting, the switch is between Row 1 and Row 1 to give  20 15 10  x1   45  − 3 − 2.249 7   x  = 1.751    2    5 1 3   x3   9  Divide Row 1 by 20 and then multiply it by –3, that is, multiply Row 1 by − 3 / 20 = −0.15. (20 15 10 45) −0.15 gives Row 1 as − 3 − 2.25 −1.5 − 6.75 Subtract the result from Row 2 − 3 − 2.249 7 1.751 − − 3 − 2.25 − 1.5 − 6.75 0 0.001 8.5 8.501 to get the resulting equations as 20 15 10   x1   45   0 0.001 8.5  x  = 8.501    2    5 1 3   x3   9  Divide Row 1 by 20 and then multiply it by 5, that is, multiply Row 1 by 5 / 20 = 0.25. ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 12 13 NAÏVE GAUSSSIAN ELIMINATION (20 15 10 45) 0.25 gives Row 1 as 5 3.75 2.5 11.25 Subtract the result from Row 3 51 3 9 − 53.75 2.5 11.25 0 − 2.75 0.5 − 2.25 to get the resulting equations as 20 15 10   x1   45   0 0.001 8.5  x   8.501     2 =    0 − 2.75 0.5  x3  − 2.25 This is the end of the first step of forward elimination. Now for the second step of forward elimination, the absolute value of the second column elements below Row 1 is 0.001 , − 2.75 or 0.001, 2.75 So the largest absolute value is in Row 3. So Row 2 is switched with Row 3 to give 20 15 10   x1   45   0 − 2.75 0.5  x  = − 2.25    2    0 0.001 8.5  x3   8.501  Divide Row 2 by –2.75 and then multiply it by 0.001, that is, multiply Row 2 by 0.001 / − 2.75 = −0.00036363. (0 − 2.75 0.5 − 2.25) −0.00036363 gives Row 2 as 0 0.00099998 − 0.00018182  0.00081816  Subtract the result from Row 3 0 0.001 8.5 8.501 − 0 0.00099998 − 0.00018182  0.00081816  0 0 8.50018182 8.50018184 Rewriting within 5 significant digits with chopping 0 0 8.5001 8.5001 to get the resulting equations as 20 15 10   x1   45   0 − 2.75 0.5   x  =  − 2.25    2    0 0 8.5001  x3  8.5001 ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 13 14 NAÏVE GAUSSSIAN ELIMINATION Back substitution 8.5001 x3 = 8.5001 8.5001 x3 = 8.5001 =1 Substituting the value of x3 in Row 2 − 2.75 x2 + 0.5 x3 = −2.25 − 2.25 − 0.5 x 2 x2 = − 2.75 − 2.25 − 0.5 1 = − 2.75 − 2.25 − 0.5 = − 2.75 − 2.75 = − 2.75 =1 Substituting the value of x3 and x 2 in Row 1 20 x1 + 15 x2 + 10 x3 = 45 45 − 15 x 2 − 10 x3 x1 = 20 45 − 15  1 − 10  1 = 20 45 − 15 − 10 = 20 30 − 10 = 20 20 = 20 =1 So the solution is  x1  X  =  x2   x3  1 = 1  1 This, in fact, is the exact solution. By coincidence only, in this case, the round-off error is fully removed. Can we use Naïve Gauss elimination methods to find the determinant of a square matrix? One of the more efficient ways to find the determinant of a square matrix is by taking advantage of the following two theorems on a determinant of matrices coupled with Naïve Gauss elimination. ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 14 15 NAÏVE GAUSSSIAN ELIMINATION Theorem 1: Let [ A] be a n  n matrix. Then, if [B ] is a n  n matrix that results from adding or subtracting a multiple of one row to another row, then det( A) = det( B) (The same is true for column operations also). Theorem 2: Let [ A] be a n  n matrix that is upper triangular, lower triangular or diagonal, then det( A) = a11  a 22 ...  aii ...  a nn n =  aii i =1 This implies that if we apply the forward elimination steps of the Naïve Gauss elimination method, the determinant of the matrix stays the same according to Theorem 1. Then since at the end of the forward elimination steps, the resulting matrix is upper triangular, the determinant will be given by Theorem 2. Example 5 Find the determinant of  25 5 1 [A] =  64 8 1 144 12 1 Solution Remember in Example 1, we conducted the steps of forward elimination of unknowns using the Naïve Gauss elimination method on [ A] to give 25 5 1   B =  0 − 4.8 − 1.56  0 0 0.7  According to Theorem 2 det( A) = det( B) = 25  ( −4.8)  0.7 = −84.00 What if I cannot find the determinant of the matrix using the Naïve Gauss elimination method, for example, if I get division by zero problems during the Naïve Gauss elimination method? Well, you can apply Gaussian elimination with partial pivoting. However, the determinant of the resulting upper triangular matrix may differ by a sign. The following theorem applies in addition to the previous two to find the determinant of a square matrix. Theorem 3: Let [ A] be a n  n matrix. Then, if [B ] is a matrix that results from switching one row with another row, then det( B) = − det( A). ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 15 16 NAÏVE GAUSSSIAN ELIMINATION Example 6 Find the determinant of  10 − 7 0  [A] = − 3 2.099 6  5 − 1 5 Solution The end of the forward elimination steps of Gaussian elimination with partial pivoting, we would obtain 10 − 7 0   [B] =  0 2.5 5   0 0 6.002  det(B) = 10  2.5  6.002 = 150.05 Since rows were switched once during the forward elimination steps of Gaussian elimination with partial pivoting, det( A) = − det(B) = −150.05 Example 7 Prove 1 det( A) = ( ) det A−1 Solution [ A][ A]−1 = [ I ] det (A A ) = det (I ) −1 det ( A) det(A ) = 1 −1 det ( A) = 1 det (A−1 ) If [ A] is a n  n matrix and det( A)  0 , what other statements are equivalent to it? 1. [ A] is invertible. 2. [ A] −1 exists. 3. [ A][ X ] = [C ] has a unique solution.  4. [ A][ X ] = solution is [ X ] =. [ A][ A]−1 = [ I ] = [ A]−1 [ A]. ME613: Numerical Methods in Engineering | Prepared by : ENGR. AQUIM P. BORDOMEO 16