Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Linear Systems > Gaussian elimination

Gaussian elimination

All the versions of this article: [English] [français]

Gaussian elimination is an algorithm in linear algebra for determining the solutions of a system of linear equations. First we do a forward elimination: Gaussian elimination reduces a given system to either triangular. Next, we do a backward elimination to solve the linear system

Problem

We want to solve the following linear system of n equations with n unknowns x_1,x_2,\ldots,x_n:


\left \{
\begin{array}{c}
a_{12}x_1+a_{12}x_2+\ldots+a_{1n}x_n=b_1\\
a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n=b_2\\
\vdots\\
a_{n1}x_1+a_{n2}x_2+\ldots+a_{nn}x_n=b_n
\end{array}\right.


In the matrix form, we have

Ax=b


with

Ax=
[ \left(
  \begin{array}{c c  c c }
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nn}
  \end{array} \right)
]
[ \left(
  \begin{array}{c }
x_1 \\
x_2 \\
\vdots \\
x_n
  \end{array} \right)
]=
[ \left(
  \begin{array}{c }
b_1 \\
b_2 \\
\vdots \\
b_n
  \end{array} \right)
]=b

Example of resolution

Consider the following system:


\left \{
\begin{array}{cccccccl}
x_1&+&2x_2&+&2x_3&=&2&L_1\\
x_1&+&3x_2&-&2x_3&=&-1&L_2\\
3x_1&+&5x_2&+&8x_3&=&8&L_3
\end{array}\right.


with


A=[ \left(
  \begin{array}{ccc}
1 & 2  & 2 \\
1 & 3  & -2\\
3 & 5  & 8
  \end{array} \right)
]
,
x=[ \left(
  \begin{array}{c}
x_1\\
x_2\\
x_3
  \end{array} \right)
],b=[ \left(
  \begin{array}{c}
2\\
-1\\
8
  \end{array} \right)
]

- First step of the Gaussian elimination: we eliminate x_1 in the lines L_2 and L_3:


\left \{
\begin{array}{cccccccl}
x_1&+&2x_2&+&2x_3&=&2&L_1\\
&&x_2&-&4x_3&=&-3&L_2\leftarrow L_2-L_1\\
&&-x_2&+&2x_3&=&2&L_3\leftarrow L_3-3L_1
\end{array}\right.

- Second step of the Gaussian elimination: we eliminate x_2
in the line L_3:


\left \{
\begin{array}{cccccccl}
x_1&+&2x_2&+&2x_3&=&2&L_1\\
&&x_2&-&4x_3&=&-3&L_2\\
&&&-&2x_3&=&-1&L_3\leftarrow L_3+L_2
\end{array}\right.


- By backward elimination we solve the linear system, we get the solution x:

x=[ \left(
  \begin{array}{c}
3\\
-1\\
1/2
  \end{array} \right)
]

Gaussian Elimination algorithm: forward elimination and triangular form

k=1,\ldots,n-1\left\{
\begin{array}{l|ll}
a_{ij}^{(k+1)}=a_{ij}^{(k)}&i=1,\ldots,k    & j=1,\ldots,n   \\
a_{ij}^{(k+1)}=0 &i=k+1,\ldots,n    & j=1,\ldots,k   \\
a_{ij}^{(k+1)}=a_{ij}^{(k)}-\displaystyle\frac{a_{ik}^{(k)}a_{kj}^{(k)}}{a_{kk}^{(k)}} & i=k+1,\ldots,n   &j=k+1,\ldots,n\\
b_i^{(k+1)}=b_i^{(k)}&i=1,\ldots,k    &   \\
b_i^{(k+1)}=b_i^{(k)}-\displaystyle\frac{a_{ik}^{(k)}b_{k}^{(k)}}{a_{kk}^{(k)}}&i=k+1,\ldots,n    &
\end{array}\right.


Let U the triangular upper matrix, we have

U=(u_{ij})_{1\leq i,j\leq n}=(a^{(n)}_{ij})_{1\leq i,j\leq n}

Gaussian Elimination algorithm: backward elimination

Now the matrix A is in triangular form U, we can solve:

Ux=b^{(n)}


with b^{(n)} the second member after the same operations than U.

We use a backward elimination for solving Ux = b^{(n)}:


\left\{\begin{array}{ll}
x_n =  \displaystyle\frac{y_n}{u_{nn}}= \displaystyle\frac{y_n}{a^{(n)}_{nn}};& \\
x_i = \displaystyle\frac{1}{u_{ii}}(y_i-\sum_{j=i+1}^{n}u_{ij}x_j)=
\displaystyle\frac{1}{a^{(n)}_{ii}}(y_i-\sum_{j=i+1}^{n}a^{(n)}_{ij}x_j)
 &\forall i=n-1,n-2,\ldots,1.
\end{array}\right.

Any message or comments?

comments powered by Disqus