Difference between revisions of "Gaussian elimination"

From Citizendium
Jump to: navigation, search
(Matrix Format)
(a matrix does not equal a vector; fix some spelling mistakes)
 
Line 1: Line 1:
 
{{subpages}}
 
{{subpages}}
'''Gaussian elimination''', sometimes called simpy '''elimination''', is a method in [[mathematics]] that is used to solve a system of linear equations.  Such sets of equations occur throughout mathematics, physics, and even in the optimization of business practices, such as scheduling of bus routes, airlines, trains, and optimization of profits as a function of supplies and sales.  The method can be accomplished using written equations, but is more often simplified using matrix forms of the  equations.
+
'''Gaussian elimination''', sometimes called simply '''elimination''', is a method in [[mathematics]] that is used to solve a system of linear equations.  Such sets of equations occur throughout mathematics, physics, and even in the optimization of business practices, such as scheduling of bus routes, airlines, trains, and optimization of profits as a function of supplies and sales.  The method can be accomplished using written equations, but is more often simplified using matrix forms of the  equations.
  
Three basic manuevers are allowed in the Gaussian elimination method:
+
Three basic maneuvers are allowed in the Gaussian elimination method:
  
 
# Interchanging any two equations
 
# Interchanging any two equations
Line 15: Line 15:
 
*(Eq. 3) <math>2X - 2Y + 1Z = -6</math>
 
*(Eq. 3) <math>2X - 2Y + 1Z = -6</math>
  
Typically, the equation with the simplest form of X is placed on the top of the equation list.  Subsequently, variable X is removed from the second or third equation by the addition or substract of the first equation, or a multiple thereof. Subtracting 3 times equation 1 from equation 2 eliminates X from equation 2, as shown below.
+
Typically, the equation with the simplest form of X is placed on the top of the equation list.  Subsequently, variable X is removed from the second or third equation by the addition or subtract of the first equation, or a multiple thereof. Subtracting 3 times equation 1 from equation 2 eliminates X from equation 2, as shown below.
  
 
*(Eq. 1) <math>1X + 1Y + 2Z = 0</math>
 
*(Eq. 1) <math>1X + 1Y + 2Z = 0</math>
Line 39: Line 39:
 
*(Eq. 3) <math>0X + 0Y + 1Z = -2</math>
 
*(Eq. 3) <math>0X + 0Y + 1Z = -2</math>
  
The last step of elimination entails removing the variable Z from equation 2.  Note that Z was removed from equation 1 previously at the time that Y was removed.  By adding twice equation 3 to equation 2, and subsequently multiplying equation 2 by -1, one obtains the final solution.
+
The last step of elimination entails removing the variable Z from equation 2.  Note that Z was removed from equation 1 previously at the time that Y was removed.  By adding twice equation 3 to equation 2, and subsequently multiplying equation 2 by −1, one obtains the final solution.
  
 
*(Eq. 1) <math>1X + 0Y + 0Z = 1</math>
 
*(Eq. 1) <math>1X + 0Y + 0Z = 1</math>
Line 45: Line 45:
 
*(Eq. 3) <math>0X + 0Y + 1Z = -2</math>
 
*(Eq. 3) <math>0X + 0Y + 1Z = -2</math>
  
Thus, the ordered triplet (1, 3, -2) is the simultaneous solution to this set of equations.
+
Thus, the ordered triplet (1, 3, −2) is the simultaneous solution to this set of equations.
  
 
*(Eq. 1) <math>X = 1</math>
 
*(Eq. 1) <math>X = 1</math>
Line 51: Line 51:
 
*(Eq. 3) <math>Z = -2</math>
 
*(Eq. 3) <math>Z = -2</math>
  
== Matrix Format ==
+
== Matrix format ==
The repeated writing of the variables is time consuming and unneccessary, particularly when the number of equations and variables is greater than 3 or 4.  Thus, using a [[matrix]] representation is often used.  The example shown previously can be written succintly as
+
The repeated writing of the variables is time consuming and unnecessary, particularly when the number of equations and variables is greater than 3 or 4.  Thus, using a [[matrix]] representation is often used.  The example shown previously can be written succinctly as
  
 
:<math>\begin{pmatrix}
 
:<math>\begin{pmatrix}
Line 58: Line 58:
 
3 & 1 & 2  \\
 
3 & 1 & 2  \\
 
2 & -2 & 1
 
2 & -2 & 1
 +
\end{pmatrix} \begin{pmatrix}
 +
X \\
 +
Y  \\
 +
Z
 
\end{pmatrix} =  \begin{pmatrix}
 
\end{pmatrix} =  \begin{pmatrix}
 
0 \\
 
0 \\
Line 70: Line 74:
 
0 & 1 & 0  \\
 
0 & 1 & 0  \\
 
0 & 0 & 1
 
0 & 0 & 1
 +
\end{pmatrix} \begin{pmatrix}
 +
X \\
 +
Y  \\
 +
Z
 
\end{pmatrix} =  \begin{pmatrix}
 
\end{pmatrix} =  \begin{pmatrix}
 
1 \\
 
1 \\

Latest revision as of 10:42, 11 May 2009

This article is a stub and thus not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

Gaussian elimination, sometimes called simply elimination, is a method in mathematics that is used to solve a system of linear equations. Such sets of equations occur throughout mathematics, physics, and even in the optimization of business practices, such as scheduling of bus routes, airlines, trains, and optimization of profits as a function of supplies and sales. The method can be accomplished using written equations, but is more often simplified using matrix forms of the equations.

Three basic maneuvers are allowed in the Gaussian elimination method:

  1. Interchanging any two equations
  2. Multiplying both sides of any equation by a non-zero number
  3. Adding a multiple of one equation to another equation

Equation format

Consider the following system of linear equations that must all be satisfied simultaneously:

  • (Eq. 1)
  • (Eq. 2)
  • (Eq. 3)

Typically, the equation with the simplest form of X is placed on the top of the equation list. Subsequently, variable X is removed from the second or third equation by the addition or subtract of the first equation, or a multiple thereof. Subtracting 3 times equation 1 from equation 2 eliminates X from equation 2, as shown below.

  • (Eq. 1)
  • (Eq. 2)
  • (Eq. 3)

After removing X from the third equation in a similar fashion, that is subtracting 2 times Eq. 1 from Eq. 2, one obtains

  • (Eq. 1)
  • (Eq. 2)
  • (Eq. 3)

Once one variable has been removed from all but one equation, and second variable is removed from all but one equation. In this set of equations for example, the variable Y can be removed from equation Eq. 1 by addition of 1/2 Eq. 2 to it, and Y can be removed from Eq. 3 by subtracting twice Eq. 2 from it, resulting in

  • (Eq. 1)
  • (Eq. 2)
  • (Eq. 3)

Equations 2 & 3 can be simplified by division, yielding the following set of equations

  • (Eq. 1)
  • (Eq. 2)
  • (Eq. 3)

The last step of elimination entails removing the variable Z from equation 2. Note that Z was removed from equation 1 previously at the time that Y was removed. By adding twice equation 3 to equation 2, and subsequently multiplying equation 2 by −1, one obtains the final solution.

  • (Eq. 1)
  • (Eq. 2)
  • (Eq. 3)

Thus, the ordered triplet (1, 3, −2) is the simultaneous solution to this set of equations.

  • (Eq. 1)
  • (Eq. 2)
  • (Eq. 3)

Matrix format

The repeated writing of the variables is time consuming and unnecessary, particularly when the number of equations and variables is greater than 3 or 4. Thus, using a matrix representation is often used. The example shown previously can be written succinctly as

and the final solution, shown in echelon form, is

The steps used to solve the matrix representation are identical to those shown for the equation format shown above. Only the notation has changed.