# Gaussian elimination

(Difference between revisions)
 Revision as of 07:55, 27 September 2005 (view source)Zxaar (Talk | contribs)← Older edit Latest revision as of 15:08, 22 August 2007 (view source)Chiel (Talk | contribs) (→Algorithm) (20 intermediate revisions not shown) Line 1: Line 1: - == Gauss Elimination == + == Description == - We consider the system of linear equations '''$Ax = b$''' or
+ We consider the system of linear equations '''$A\phi = b$''' or
:$:[itex] \left[ \left[ Line 12: Line 12: \left[ \left[ \begin{matrix} \begin{matrix} - {x_1 } \\ + {\phi_1 } \\ - {x_2 } \\ + {\phi_2 } \\ . \\ . \\ - {x_n } \\ + {\phi_n } \\ \end{matrix} \end{matrix} \right] \right] Line 52: Line 52: \left[ \left[ \begin{matrix} \begin{matrix} - {x_1 } \\ + {\phi_1 } \\ - {x_2 } \\ + {\phi_2 } \\ . \\ . \\ - {x_n } \\ + {\phi_n } \\ \end{matrix} \end{matrix} \right] \right]$
[/itex]
- After performing elementary raw operations the '''augmented matrix''' is put into the upper triangular form:
+ After performing elementary row operations the '''augmented matrix''' is put into the upper triangular form:
:$:[itex] Line 74: Line 74: \begin{matrix} \begin{matrix} {b_1^' } \\ {b_1^' } \\ - {b_1^' } \\ + {b_2^' } \\ . \\ . \\ - {b_1^' } \\ + {b_n^' } \\ \end{matrix} \end{matrix} Line 84: Line 84:$
[/itex]
- By using the formula:
+ The solution to the original system is found via '''back substitution'''.  The solution to the last equation is + :$:[itex] - x_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' x_j } } \right) + \phi_n = b_n^'/a_{nn}'. -$
+ [/itex] - Solve the equation of the kth row for xk, then substitute back into the equation of the (k-1)st row to obtain a solution for  (k-1)st raw, and so on till k = 1. + + This result may now be substituted into the second to last equation, allowing us to solve for $\phi_{n-1}$.  Repetition of this substitution process will give us the complete solution vector.  The back substitution process may be expressed as + + :$+ \phi_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' \phi_j } } \right), +$ + + where $i=n,n-1,\ldots,1$. + + == Algorithm == + Forward elimination phase + :    for k:= 1 step until n-1 do
+ ::    for i:=k+1 step until n do
+ :::    $m = {{a_{ik} } \over {a_{kk} }} + ::: for j:= 1 step until n do + :::: [itex] a_{ij}=a_{ij}-ma_{kj} + ::: end loop (j) + ::: [itex]b_i=b_i-mb_k + :: end loop (i) + : end loop (k) + Back substitution phase + : for k:= n stepdown until 1 do + :: for i:= 1 step until k-1 do + ::: [itex]b_i=b_i-a_{ik}/a_{kk}b_{k}$
+ ::    end loop (i)
+ ::    \phi_{k}=b_{k}/a_{kk}
+ :      end loop (k) + + == Important Considerations == + Gaussian elimination is best used for relatively small, relatively full systems of equations.  If properly used, it should outperform most iterative methods for these systems.  As the system to be solved becomes larger, the overhead associated with the more complicated iterative methods becomes less of an issue, and the iterative methods should outperform Gaussian Elimination.  For sparse systems, the use of Gaussian elimination is complicated by the possible introduction of more nonzero entries (fill-in).  In any case, it is important to keep in mind that the basic algorithm is vulnerable to accuracy issues, including (but not limited to) the distinct possibility of division by zero at various places in the solution process.  In practice, it is best to employ safeguards against such problems (e.g. pivoting). + + ==External link== + *[http://en.wikipedia.org/wiki/Gaussian_elimination Wikipedia's article ''Gaussian elimination'']

## Description

We consider the system of linear equations $A\phi = b$ or

$\left[ \begin{matrix} {a_{11} } & {a_{12} } & {...} & {a_{1n} } \\ {a_{21} } & {a_{22} } & . & {a_{21} } \\ . & . & . & . \\ {a_{n1} } & {a_{n1} } & . & {a_{nn} } \\ \end{matrix} \right] \left[ \begin{matrix} {\phi_1 } \\ {\phi_2 } \\ . \\ {\phi_n } \\ \end{matrix} \right] = \left[ \begin{matrix} {b_1 } \\ {b_2 } \\ . \\ {b_n } \\ \end{matrix} \right]$

To perform Gaussian elimination starting with the above given system of equations we compose the augmented matrix equation in the form:

$\left[ \begin{matrix} {a_{11} } & {a_{12} } & {...} & {a_{1n} } \\ {a_{21} } & {a_{22} } & . & {a_{21} } \\ . & . & . & . \\ {a_{n1} } & {a_{n1} } & . & {a_{nn} } \\ \end{matrix} \left| \begin{matrix} {b_1 } \\ {b_2 } \\ . \\ {b_n } \\ \end{matrix} \right. \right] \left[ \begin{matrix} {\phi_1 } \\ {\phi_2 } \\ . \\ {\phi_n } \\ \end{matrix} \right]$

After performing elementary row operations the augmented matrix is put into the upper triangular form:

$\left[ \begin{matrix} {a_{11}^' } & {a_{12}^' } & {...} & {a_{1n}^' } \\ 0 & {a_{22}^' } & . & {a_{2n}^' } \\ . & . & . & . \\ 0 & 0 & . & {a_{nn}^' } \\ \end{matrix} \left| \begin{matrix} {b_1^' } \\ {b_2^' } \\ . \\ {b_n^' } \\ \end{matrix} \right. \right]$

The solution to the original system is found via back substitution. The solution to the last equation is

$\phi_n = b_n^'/a_{nn}'.$

This result may now be substituted into the second to last equation, allowing us to solve for $\phi_{n-1}$. Repetition of this substitution process will give us the complete solution vector. The back substitution process may be expressed as

$\phi_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' \phi_j } } \right),$

where $i=n,n-1,\ldots,1$.

## Algorithm

Forward elimination phase

for k:= 1 step until n-1 do
for i:=k+1 step until n do
$m = {{a_{ik} } \over {a_{kk} }}$
for j:= 1 step until n do
$a_{ij}=a_{ij}-ma_{kj}$
end loop (j)
$b_i=b_i-mb_k$
end loop (i)
end loop (k)

Back substitution phase

for k:= n stepdown until 1 do
for i:= 1 step until k-1 do
$b_i=b_i-a_{ik}/a_{kk}b_{k}$
end loop (i)
$\phi_{k}=b_{k}/a_{kk}$
end loop (k)

## Important Considerations

Gaussian elimination is best used for relatively small, relatively full systems of equations. If properly used, it should outperform most iterative methods for these systems. As the system to be solved becomes larger, the overhead associated with the more complicated iterative methods becomes less of an issue, and the iterative methods should outperform Gaussian Elimination. For sparse systems, the use of Gaussian elimination is complicated by the possible introduction of more nonzero entries (fill-in). In any case, it is important to keep in mind that the basic algorithm is vulnerable to accuracy issues, including (but not limited to) the distinct possibility of division by zero at various places in the solution process. In practice, it is best to employ safeguards against such problems (e.g. pivoting).
The text passage describes the Gaussian elimination method for solving systems of linear equations. It provides a detailed explanation of the process, including the forward elimination and back substitution phases, and mentions important considerations for its use.
no_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Gaussian elimination

(Difference between revisions)
 Revision as of 07:55, 27 September 2005 (view source)Zxaar (Talk | contribs)← Older edit Latest revision as of 15:08, 22 August 2007 (view source)Chiel (Talk | contribs) (→Algorithm) (20 intermediate revisions not shown) Line 1: Line 1: - == Gauss Elimination == + == Description == - We consider the system of linear equations '''$Ax = b$''' or
+ We consider the system of linear equations '''$A\phi = b$''' or
:$:[itex] \left[ \left[ Line 12: Line 12: \left[ \left[ \begin{matrix} \begin{matrix} - {x_1 } \\ + {\phi_1 } \\ - {x_2 } \\ + {\phi_2 } \\ . \\ . \\ - {x_n } \\ + {\phi_n } \\ \end{matrix} \end{matrix} \right] \right] Line 52: Line 52: \left[ \left[ \begin{matrix} \begin{matrix} - {x_1 } \\ + {\phi_1 } \\ - {x_2 } \\ + {\phi_2 } \\ . \\ . \\ - {x_n } \\ + {\phi_n } \\ \end{matrix} \end{matrix} \right] \right]$
[/itex]
- After performing elementary raw operations the '''augmented matrix''' is put into the upper triangular form:
+ After performing elementary row operations the '''augmented matrix''' is put into the upper triangular form:
:$:[itex] Line 74: Line 74: \begin{matrix} \begin{matrix} {b_1^' } \\ {b_1^' } \\ - {b_1^' } \\ + {b_2^' } \\ . \\ . \\ - {b_1^' } \\ + {b_n^' } \\ \end{matrix} \end{matrix} Line 84: Line 84:$
[/itex]
- By using the formula:
+ The solution to the original system is found via '''back substitution'''.  The solution to the last equation is + :$:[itex] - x_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' x_j } } \right) + \phi_n = b_n^'/a_{nn}'. -$
+ [/itex] - Solve the equation of the kth row for xk, then substitute back into the equation of the (k-1)st row to obtain a solution for  (k-1)st raw, and so on till k = 1. + + This result may now be substituted into the second to last equation, allowing us to solve for $\phi_{n-1}$.  Repetition of this substitution process will give us the complete solution vector.  The back substitution process may be expressed as + + :$+ \phi_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' \phi_j } } \right), +$ + + where $i=n,n-1,\ldots,1$. + + == Algorithm == + Forward elimination phase + :    for k:= 1 step until n-1 do
+ ::    for i:=k+1 step until n do
+ :::    $m = {{a_{ik} } \over {a_{kk} }} + ::: for j:= 1 step until n do + :::: [itex] a_{ij}=a_{ij}-ma_{kj} + ::: end loop (j) + ::: [itex]b_i=b_i-mb_k + :: end loop (i) + : end loop (k) + Back substitution phase + : for k:= n stepdown until 1 do + :: for i:= 1 step until k-1 do + ::: [itex]b_i=b_i-a_{ik}/a_{kk}b_{k}$
+ ::    end loop (i)
+ ::    \phi_{k}=b_{k}/a_{kk}
+ :      end loop (k) + + == Important Considerations == + Gaussian elimination is best used for relatively small, relatively full systems of equations.  If properly used, it should outperform most iterative methods for these systems.  As the system to be solved becomes larger, the overhead associated with the more complicated iterative methods becomes less of an issue, and the iterative methods should outperform Gaussian Elimination.  For sparse systems, the use of Gaussian elimination is complicated by the possible introduction of more nonzero entries (fill-in).  In any case, it is important to keep in mind that the basic algorithm is vulnerable to accuracy issues, including (but not limited to) the distinct possibility of division by zero at various places in the solution process.  In practice, it is best to employ safeguards against such problems (e.g. pivoting). + + ==External link== + *[http://en.wikipedia.org/wiki/Gaussian_elimination Wikipedia's article ''Gaussian elimination'']

## Description

We consider the system of linear equations $A\phi = b$ or

$\left[ \begin{matrix} {a_{11} } & {a_{12} } & {...} & {a_{1n} } \\ {a_{21} } & {a_{22} } & . & {a_{21} } \\ . & . & . & . \\ {a_{n1} } & {a_{n1} } & . & {a_{nn} } \\ \end{matrix} \right] \left[ \begin{matrix} {\phi_1 } \\ {\phi_2 } \\ . \\ {\phi_n } \\ \end{matrix} \right] = \left[ \begin{matrix} {b_1 } \\ {b_2 } \\ . \\ {b_n } \\ \end{matrix} \right]$

To perform Gaussian elimination starting with the above given system of equations we compose the augmented matrix equation in the form:

$\left[ \begin{matrix} {a_{11} } & {a_{12} } & {...} & {a_{1n} } \\ {a_{21} } & {a_{22} } & . & {a_{21} } \\ . & . & . & . \\ {a_{n1} } & {a_{n1} } & . & {a_{nn} } \\ \end{matrix} \left| \begin{matrix} {b_1 } \\ {b_2 } \\ . \\ {b_n } \\ \end{matrix} \right. \right] \left[ \begin{matrix} {\phi_1 } \\ {\phi_2 } \\ . \\ {\phi_n } \\ \end{matrix} \right]$

After performing elementary row operations the augmented matrix is put into the upper triangular form:

$\left[ \begin{matrix} {a_{11}^' } & {a_{12}^' } & {...} & {a_{1n}^' } \\ 0 & {a_{22}^' } & . & {a_{2n}^' } \\ . & . & . & . \\ 0 & 0 & . & {a_{nn}^' } \\ \end{matrix} \left| \begin{matrix} {b_1^' } \\ {b_2^' } \\ . \\ {b_n^' } \\ \end{matrix} \right. \right]$

The solution to the original system is found via back substitution. The solution to the last equation is

$\phi_n = b_n^'/a_{nn}'.$

This result may now be substituted into the second to last equation, allowing us to solve for $\phi_{n-1}$. Repetition of this substitution process will give us the complete solution vector. The back substitution process may be expressed as

$\phi_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' \phi_j } } \right),$

where $i=n,n-1,\ldots,1$.

## Algorithm

Forward elimination phase

for k:= 1 step until n-1 do
for i:=k+1 step until n do
$m = {{a_{ik} } \over {a_{kk} }}$
for j:= 1 step until n do
$a_{ij}=a_{ij}-ma_{kj}$
end loop (j)
$b_i=b_i-mb_k$
end loop (i)
end loop (k)

Back substitution phase

for k:= n stepdown until 1 do
for i:= 1 step until k-1 do
$b_i=b_i-a_{ik}/a_{kk}b_{k}$
end loop (i)
$\phi_{k}=b_{k}/a_{kk}$
end loop (k)

## Important Considerations

Gaussian elimination is best used for relatively small, relatively full systems of equations. If properly used, it should outperform most iterative methods for these systems. As the system to be solved becomes larger, the overhead associated with the more complicated iterative methods becomes less of an issue, and the iterative methods should outperform Gaussian Elimination. For sparse systems, the use of Gaussian elimination is complicated by the possible introduction of more nonzero entries (fill-in). In any case, it is important to keep in mind that the basic algorithm is vulnerable to accuracy issues, including (but not limited to) the distinct possibility of division by zero at various places in the solution process. In practice, it is best to employ safeguards against such problems (e.g. pivoting).
user
The text passage describes the Gaussian elimination method for solving systems of linear equations. It provides a detailed explanation of the process, including the forward elimination and back substitution phases, and mentions important considerations for its use.

TYPE: NO_QUESTION