Difference between revisions of "Gaussian Elimination"
(great addition by Jacob; this improves intro) |
|||
| Line 1: | Line 1: | ||
| − | '''Gaussian Elimination''' is a simple method for solving a system of simultaneous linear equations by expressing them in [[matrix]] form and then subtracting rows from each other sequentially in order to create all zeros below the diagonal, thereby facilitating identification of solutions or range of solutions. | + | '''Gaussian Elimination''' is a simple method for solving a system of simultaneous linear equations by expressing them in [[matrix]] form and then subtracting rows from each other sequentially in order to create all ones on the main diagonal and all zeros below the diagonal, thereby facilitating identification of solutions or range of solutions. |
==Example== | ==Example== | ||
| Line 34: | Line 34: | ||
as expected. | as expected. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Sources == | == Sources == | ||
Revision as of 04:57, February 8, 2010
Gaussian Elimination is a simple method for solving a system of simultaneous linear equations by expressing them in matrix form and then subtracting rows from each other sequentially in order to create all ones on the main diagonal and all zeros below the diagonal, thereby facilitating identification of solutions or range of solutions.
Example
Here, we work a simple example. Consider the two equations:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3x-2y=7 \ }
.
We represent this collection of equations in matrix form as:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{pmatrix}3 & -2 & 7\\1 & 1/2 & -2\end{pmatrix}} .
Now, the technique of Gaussian elimination allows us to add and subtract rows from each other, as well as multiples of rows. The idea is to achieve 1s in the main diagonal, and 0s elsewhere. This will become clear as we work the example.
Since the row is a multiple of the second row ( ), we can add this row to the first row:
As you can see, we have already begun altering the matrix so that there will be 0s off of the main diagonal. In our next step, we will divide the top row by 7 and multiply the bottom row by 2 to put 1s in the main diagonal:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{pmatrix}7 & 0 & -1\\1 & 1/2 & -2\end{pmatrix} \to \begin{pmatrix}1 & 0 & -1/7\\2 & 1 & -4\end{pmatrix}}
Finally, we subtract twice the top row from the bottom to put a zero off the main diagonal in the bottom:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{pmatrix}1 & 0 & -1/7\\2 & 1 & -4\end{pmatrix} \to \begin{pmatrix}1 & 0 & -1/7\\0 & 1 & -4+2/7\end{pmatrix}=\begin{pmatrix}1 & 0 & -1/7\\0 & 1 & -26/7\end{pmatrix}}
This should yield a solution to the original equation: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=-1/7, y=-26/7 \ } . To check, we insert these values into the original equations:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3\frac{-1}{7} - 2\frac{-26}{7} = \frac{-3+52}{7} = \frac{49}{7} = 7}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{-1}{7} + \frac{1}{2}{-26}{7} = \frac{-1-13}{7} = \frac{-14}{7} = -2}
as expected.