Section 3.6.1 Elimination Methods for Linear Equations

Solve:

4 x₁ + 2 x₂ = 1

x₁ - 4 x₂ = 5

Eliminate x₁ from both equations by making the coefficients of x₁in each the same and subtracting:
- divide first equation by 4
  x₁ + 0.5 x₂ = 0.25
- subtract
  (1-1) x₁ + (-4 - 0.5) x₂ = (5-0.25)
- leaving a single equation in x₂ -4.5 x₂ = 4.75
- Hence x₂
  x₂ = -1.055556
Now substitute x₂ back into the first equation as reduced in the first step of 1. above, i.e.:

x₁ + 0.5 (-1.055556) = 0.25
This is in a convenient form for obtaining x₁:

x₁ = 0.25 + 0.5 (1.055556) = 0.77778

In symbols:

$\begin{eqnarray*}a_{1,1} x_1 + a_{1,2} x_2 & = & b_1 \\ a_{2,1} x_1 + a_{2,2} x_2 & = & b_2 \\ \end{eqnarray*}$

Eliminate x₁

by dividing first equation by a_1,1 and and keep this modified equation for future use:
x₁ + a_1,2 / a_1,1 x₂ = b₁ / a_1,1
multiply by a_2,1, giving both equations same x₁ coefficient:
$\begin{eqnarray*}a_{2,1} x_1 + a_{2,1} a_{1,2} / a_{1,1} x_2 & = & a_{2,1} b_1 / a_{1,1} \\ a_{2,1} x_1 + a_{2,2} & = & b_2 \\ \end{eqnarray*}$
Subtract giving single equation:

( a_2,2 - a_2,1 a_1,2 / a_1,1 ) x₂ = b₂ - a_2,1 b₁ / a_1,1

Hence x₂:

$\begin{displaymath}x_2 = \frac{b_2 - a_{2,1} b_1 / a_{1,1}} { a_{2,2} - a_{2,1} a_{1,2} / a_{1,1} } \end{displaymath}$

Back substitute in `saved' equation to get x₁.
The equation, now rearranged for x₁ is:

x₁ = b₁ / a_1,1 - (a_1,2 / a_1,1) x₂

Substituting:

$\begin{displaymath}x_1 = b_1 / a_{1,1} - a_{1,2} / a_{1,1} \frac{b_2 - a_{2,1} b_1 / a_{1,1}} { a_{2,2} - a_{2,1} a_{1,2} / a_{1,1} } \end{displaymath}$

Set of n equations

$\begin{eqnarray*}a_{1,1} x_1 + a_{1,2} x_2 + % a_{2,1} x_1 + a_{2,2} x_2 + % \vdots \ \ \ \ & = & \vdots \\ a_{n,1} x_1 + a_{n,2} x_2 + % \end{eqnarray*}$

$\begin{displaymath}\left[ \begin{array}{c c c c} a_{1,1} & a_{1,2} & & a_{1,n} \... ...egin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array}\right] \end{displaymath}$

(1)

This may be written in matrix-vector form:

$\begin{displaymath}{\bf A x = b} \end{displaymath}$

     !Start the elimination loop.....  
       do i=1,n-1  
     !... go down the matrix by rows i...  
     !.. reducing all the other rows k.. 
       do k=i+1,n 
       pivot=(a(k,i)/a(i,i))  
     !This is the number to multiply each  
     !row of equn i by before subtracting it..  
     !.. along each row k ..  
       do j=1,n
       a(k,j)=a(k,j)-pivot*a(i,j)  
       end do  
     ! .. and also the constant.  
       b(k)=b(k)-pivot*b(i)  
     !  
       end do  
     !.. go on to next row with current elimination 
     !end do  
     !.. and then eliminate next equation  
     !  
     !.. and finally solve the one remaining  
     !equation for x(n) 
       x(n)=b(n)/a(n,n) 
     !--- Elimination Complete --------- 
     !Back substitute for other x() ...
       do l=n-1,1,-1 
       x(l)=b(l) 
       do j=l+1,n  
       x(l)=x(l)-a(l,j)*x(j) end do  
       x(l)=x(l)/a(l,l)  
       end do  
     !----- Finished ------------

Using the Library Solver

       program lintest  
       implicit none 
     !test linear solver  
       integer :: n,i,j,ifg  
       integer, parameter :: max=50  
       real :: a(max,max),x(max),c(max) 
       print *, 'Solver for small sets of linear equations...'
       print *, 'Enter number of equations, less than ',max  
       read *, n  
       print *, 'Now enter coefficients ...'  
       print *, 'i.e. ',n+1, ' numbers per row...'  
       do i=1,n  
       print *, 'Elements for row ', i, ':'  
       read *, (a(i,j), j=1,n), c(i) 
       end do  
       ....... 
       print *, 'Matrix and constants are:'  
       do i=1,n  
     !check print  
       write(6,'(7f10.4)') (a(i,j),j=1,n), c(i)  
       end do 
       call solve_linear (a,max,x,n,c,ifg) 
       write(6,*) 'flag =',ifg  
       write(6,*) 'solution..'  
       write(6,*) (x(i),i=1,n) 
       end program

Next - Section 3.6.2: Example Questions
Return to Section 3 Index