10.1 The Gaussian Elimination Algorithm

---

 

	Java Number Cruncher: The Java Programmer's Guide to Numerical Computing By Ronald  Mak
	Table of Contents
	Chapter  10.   Solving Systems of Linear Equations

---

10.1 The Gaussian Elimination Algorithm

Let's start with the following example of a system of four linear equations in four unknowns x ₁ , x ₂ , x ₃ , and x ₄ :

The correct solution is x ₁ = 1, x ₂ = -2, x ₃ = 3, and x ₄ = -1.

The first set of operations is called forward elimination. The goal is to systematically remove one unknown at a time from the system. To keep things simpler, we'll do all the arithmetic with three significant digits.

• Eliminate x ₁ from the second, third, and fourth equations . Designate the first equation as the pivot equation and its leading coefficient, 3, the pivot element. To eliminate x ₁ from the second equation, multiply the pivot equation by the multiplier (the ratio of the coefficients of x ₁ ) and subtract the result from the second equation. To eliminate x ₁ from the third equation, multiply the pivot equation by the multiplier and subtract the result from the third equation. To eliminate x ₁ from the fourth equation, multiply the pivot equation by the multiplier and subtract the result from the fourth equation. After these operations, the system becomes

  

  
  

  Note that the pivot element was the common divisor for each pivot equation multiplier, and that the pivot equation (after the multiplication) is subtracted from each of the equations below it.

• Eliminate x ₂ from the third and fourth equations . Now the second equation is the pivot equation, and -3.67 is the pivot element. To eliminate x ₂ from the third equation, multiply the pivot equation by the multiplier and subtract the result from the third equation. To eliminate x ₂ from the fourth equation, multiply the pivot equation by the multiplier and subtract the result from the fourth equation. After these operations, the system becomes

  

  
  

• Eliminate x ₃ from the fourth equation . The third equation is the pivot equation, and 4.25 becomes the pivot element. Multiply the pivot equation by the multiplier and subtract the result from the fourth equation. After this operation, the system becomes

  

  
  

  The system is now in upper triangular form.

Once the system is in upper triangular form, it is easy to solve for each unknown, starting with x ₄ at the bottom equation, and moving up one equation at a time for each of the other unknowns. This process is called back substitution:

We see that there are some roundoff errors.

This algorithm, forward elimination followed by back substitution, is known as Gaussian elimination.

---

Top