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 x1,x2,,xn:

{a12x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2an1x1+an2x2++annxn=bn

In the matrix form, we have

Ax=b

with

Ax=(a11a12a1na21a22a2nan1an2ann)(x1x2xn)=(b1b2bn)=b

Example of resolution

Consider the following system:

{x1+2x2+2x3=2L1x1+3x22x3=1L23x1+5x2+8x3=8L3

with

A=(122132358),x=(x1x2x3),b=(218)
  • First step of the Gaussian elimination: we eliminate x1 in the lines L2 and L3:
{x1+2x2+2x3=2L1x24x3=3L2L2L1x2+2x3=2L3L33L1
  • Second step of the Gaussian elimination: we eliminate x2 in the line L3:
{x1+2x2+2x3=2L1x24x3=3L22x3=1L3L3+L2
  • By backward elimination we solve the linear system, we get the solution x:
x=(311/2)

Gaussian Elimination algorithm: forward elimination and triangular form

k=1,,n1{aij(k+1)=aij(k)i=1,,kj=1,,naij(k+1)=0i=k+1,,nj=1,,kaij(k+1)=aij(k)aik(k)akj(k)akk(k)i=k+1,,nj=k+1,,nbi(k+1)=bi(k)i=1,,kbi(k+1)=bi(k)aik(k)bk(k)akk(k)i=k+1,,n

Let U the triangular upper matrix, we have

U=(uij)1i,jn=(aij(n))1i,jn

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):

{xn=ynunn=ynann(n);xi=1uii(yij=i+1nuijxj)=1aii(n)(yij=i+1naij(n)xj)i=n1,n2,,1.