Solve the following system using straightforward Gaussian el

Solve the following system using straightforward Gaussian elimination with forward elimination and back substitution. Carry four significant digits.

Solution

Stage 1

The goal of stage 1 is to eliminate x1 from all but the first equation.
The first step, called the exchange step, exchanges equations so that among the coefficients

multiplying x1 in all of the equations, the coefficient in the first equation has largest magnitude. If there is more than one such coefficient with largest magnitude, choose the first. If this coefficient with largest magnitude is nonzero, then it is underlined and called the pivot for stage 1, otherwise stage 1 has no pivot and we terminate. In Example A, the pivot is already in the first equation so no exchange is necessary. In Example B, the pivot occurs in the third equation so equations 1 and 3 are exchanged.

The second step, called the elimination step, eliminates variable x1 from all but the first equa- tion. For Example A, this involves subtracting m2,1 = 2/4, times equation 1 from equation 2, and subtracting m3,1 = 1/4 times equation 1 from equation 3. For Example B, this involves subtracting m2,1 = 1/2 times equation 1 from equation 2. Each of the numbers mi,1 is a multiplier; the first subscript on mi,1 tells you from which equation the multiple of the first equation is subtracted. The multiplier mi,1 is computed as the coefficient of x1 in equation i divided by the coefficient of x1 in equation 1 (that is, the pivot).

The third step, the removal step, removes the first equation and makes it the 1st equation of the final upper triangular linear system.

Stage 2

Stage 2 continues with the smaller linear system produced at the end of stage 1. Note that this smaller linear system involves one fewer unknown (the elimination step in the first stage eliminated variable x1) and one fewer equation (the removal step in the first stage removed the first equation) than does the original linear system. The goal of stage 2 is to eliminate the variable x2 from all but the first equation of this smaller linear system.

As stated before, each stage uses the same 3 steps. For stage 2, the exchange step exchanges equations so that among the coefficients multiplying x2 in all of the remaining equations, the co- efficient in the first equation has largest magnitude. If this coefficient with largest magnitude is nonzero, then it is called the pivot for stage 2, otherwise stage 2 has no pivot and we terminate. The elimination step eliminates the variable x2 from all but the first equation. For each of Example A and B, we compute a single multiplier m3,2 which is the coefficient of x2 in equation 2 divided by the coefficient of x2 in equation 1 (that is, the pivot). (Note that the numbering of the multiplier m3,2 corresponds to the equation and variable numbering in the original linear system.) Then we subtract m3,2 times the first equation off the second equation to eliminate x2 from the second equation. The removal step then removes the first equation and uses it to form the 2nd equation of the final upper triangular linear system.

Stage 3

Stage 3 continues with the smaller linear system produced by the last step of stage 2. Its goal is to eliminate the variable x3 from all but the first equation. However, in this, the last stage of GE, the linear system consists of just one equation in one unknown, so the exchange and elimination steps do not change anything. The only useful work performed by this stage consists of (1) identifying

Stage 1 Start
4x1 + 6x2 + (10)x3 = 0 2x1+ 2x2+ 2x3=6 1x1 +(1)x2 + 4x3 =4

Stage 1 Eliminate
4x1 + 6x2 +(10)x3 =0

Stage 1 Exchange
4 x1 + 6x2 + (10)x3 =0 2x1+ 2x2+ 2x3 =6 1x1 + (1)x2 + 4x3 =4

Stage 1 Removal

0x1 + (1)x2 + 7x3 =6 0x1 + (2.5)x2 + 6.5x3 = 4

(1)x2 + 7x3 = 6 (2.5)x2 + 6.5x3 = 4

Stage 2 Start (1)x2 + 7x3 = 6 (2.5)x2 + 6.5x3 = 4

Stage 2 Eliminate (2.5)x2 + 6.5x3 = 4 0x2 + 4.4x3 = 4.4

Stage 3 Start 4.4 x3 = 4.4

Stage 2 Exchange (2.5)x2 + 6.5x3 = 4 (1)x2 + 7x3 = 6

Stage 2 Removal 4.4x3 = 4.4

Upper Triangular Linear System 4x1 + 6x2 +(10)x3 = 0 0x1 + (2.5)x2 + 6.5x3 = 4 0x1 + 0x2 + 4.4x3 =4.4

Figure 3.7: Gaussian elimination, example A.

the pivot, if one exists (if it does not we terminate), and (2) removing this equation and making it the last equation of the final upper triangular linear system.

Solving the Upper Triangular Linear System

GE is now finished. When the entries on the diagonal of the final upper triangular linear system are nonzero, as in Figs. 3.7 and 3.8, the linear system is nonsingular and its solution may be determined by backward substitution. (Recommendation: If you’re determining the solution by hand, then check by substituting that your computed solution satisfies all the equations of the original linear system.)

The diagonal entries of the upper triangular linear system produced by GE play an important role. Specifically, the kth diagonal entry, i.e., the coefficient of xk in the kth equation, is the pivot for the kth stage of GE. So, the upper triangular linear system produced by GE is nonsingular if and only if each stage of GE has a pivot.

To summarize:

GE can always be used to transform a linear system of order n into an upper triangular linear system with the same solution set.

The kth stage of GE starts with a linear system that involves nk+1 equations in the nk+1 unknowns xk,xk+1,··· ,xn. The kth stage of GE ends with a linear system that involves nk equations in the n k unknowns xk+1, xk+2, · · · , xn, having removed its first equation and added it to the final upper triangular linear system.

If GE finds a non–zero pivot in every stage, then the final upper triangular linear system is nonsingular. The solution of the original linear system can be determined by applying backward substitution to this upper triangular linear system.

Stage 1 Start
0x1 +3x2 +4x3 =7 1x1 +1x2 +2x3 =4

(2)x1 +1x2 +3x3 =2

Stage 1 Eliminate (2)x1 + 1x2 + 3x3 =2 0x1 + 1.5x2 + 3.5x3 = 5 0x1+ 3x2+ 4x3=7

Stage 2 Start 1.5x2 + 3.5x3 = 5 3x2+ 4x3=7

Stage 2 Eliminate 3x2+ 4x3= 7 0x2 + 1.5x3 = 1.5

Stage 3 Start 1.5 x3 = 1.5

(2)x1 +1x2 +3x3 =2 1x1 +1x2 +2x3 =4 0x1 +3x2 +4x3 =7

Stage 1 Removal 1.5x2 + 3.5x3 = 5

3x2+ 4x3=7

Stage 2 Exchange 3x2+ 4x3=7 1.5x2 + 3.5x3 = 5

Stage 2 Removal 1.5x3 = 1.5

Upper Triangular Linear System (2)x1+1x2+ 3x3= 2 0x1+3x2+ 4x3= 7 0x1 + 0x2 + 1.5x3 =1.5

Figure 3.8: Gaussian elimination, example B.

• If GE fails to find a pivot at some stage, then the linear system is singular and the original linear system either has no solution or an infinite number of solutions.

We emphasize that if GE does not find a pivot during some stage, then we can conclude immediately that the original linear system is singular. Consequently, as in our algorithm, many GE codes simply terminate elimination and return a message that indicates the original linear system is singular.