Gaussian elimination
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$:
- Second step of the Gaussian elimination: we eliminate $x_2$ in the line $L_3$:
- By backward elimination we solve the linear system, we get the solution $x$:
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.\]If you found this post or this website helpful and would like to support our work, please consider making a donation. Thank you!
Help Us