Solving Systems of Linear Equations.

Unknown | 05:36 | 0 comments


The Problem :

You may have solved linear equation early in the school. Problems involving solving sets of linear equation are very important in the field of Engineering and Mathematics. 
Let us consider that we have a system of linear equations 
                 a11x1 + a12x2 + a13x3 = c1 
                 a21x1 + a22x2 + a23x3 = c2 
                 a31x1 + a32x2 + a33x3 = c3 
We can solve it by reducing technique: 
            Step 1: 
            x1 + a12/a11x2 + a13/a11x3 = c1/a11 
            a21x1 + a22x2 + a23x3 = c2 
            a31x1 + a32x2 + a33x3 = c3
            Step 2:
            x1 + a12/a11x2 + a13/a11x3 = c1/a11
                    (-a21* a12/a11)a22x2 +  (-a21* a13/a11)a23x3 =  (-a21* c1/a11)c2
                    (-a31* a12/a11)a22x2 +  (-a31* a13/a11)a23x3 =  (-a31* c1/a11)c2
Now do as step 1 for second row and so on.
This can be made more effective using matrix method. The set of equation for `n' unknowns can be written as
                 a11x1 + a12x2 + a13x3 + ... + a1nxn = c1
                 a21x1 + a22x2 + a23x3 + ... +  a2nxn = c2
                 a31x1 + a32x2 + a33x3 + ... +  a3nx = c3
                         ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...
                 am1x1 + am2x2 + am3x3 + ... +  amnx = cn
In matrix form
Equations in matrix form: [A] * {X} = {C}
Compactly        [A] * {X} = {C}
From this we can solve values of X's. The matrix [AC] is called an augmented (see example below) matrix. If after elimination process the rank of matrix [A] and rank of matrix [AC] not equals, the system is called inconsistent and it does not have a solution. If the matrix is consistent and number of unknowns is greater then rank of matrix then the matrix system has arbitarily many solutions containing (NumberOfUnknowns-rank) arbitary constants. Rank of a matrix is defined as the number of non zero rows of a matrix system. Otherwise if the rank and number of unknows equals then the system has been solved.
For example let a system of equations be
                  9x1 + 4x2 + x3 = -17
                  x1 - 2x2 - 6x3 = 14
                  x1 + 6x2  = 4
This sets of equation can be written as
9    4      1   -17
1  -2   -6      14
1    6      0        4
So the steps involving the solution is
Step : 1
              1             -2             -6             14
              1              6              0              4
              9              4              1            -17
Step : 2
              1             -2             -6             14
              0              8              6            -10
              0             22             55           -143
Step : 3
              1             -2             -6             14
              0              1              3/4             -5/4
              0              0             77/2           -231/2
Step : 4
              1             -2             -6             14
              0              1              3/4             -5/4
              0              0              1             -3
Step : 5
              1             -2              0             -4
              0              1              0              1
              0              0              1             -3
Step : 6
              1              0              0             -2
              0              1              0              1
              0              0              1             -3
x1 = -2
x2 = 1
x3 = -3
Again consider this system
        2x1 + 2x2 + 2x3 = 2
        4x1 + 4x2 + 4x3 = 4
        16x1 + 16x2 + 16x3 = 16
Steps are:
Step : 1
              2              2              2              2
              4              4              4              4
             16             16             16             16
Step : 2
              1              1              1              1
              0              0              0              0
              0              0              0              0
This system has number of unknowns 3 and rank is 1. So this system has arbitarily many solutions containing (3-1) = 2 arbitary constants.
Another system
x + y = 10
x + y = 20
x + y = 50
Steps are:
Step : 1
              1              1             10
              1              1             20
              2              2             50
Step : 2
              1              1             10
              0              0             10
              0              0             30
Step : 3
              1              1             10
              0              0             10
              0              0             30
Step : 4
              1              1             10
              0              0             10
              0              0              1
Step : 5
              1              1              0
              0              0              0
              0              0              1
Step : 6
              1              1              0
              0              0              0
              0              0              1
As rank of [A] (in this case: rank(A) = 1) is not equal to the rank of augmented matrix [AC] (in this case: rank(AC) = 2) , the system has no solution.
However though there are other methods to compute this solution for the matrix system, the main problem occurs are
        1. Round off errors or computational error due to the use of floating point number
        2. Error due to wrong order of the given equation.
To prevent round off error due to floating point number an approach can be used, similar to the process of doing fractional number. So we may use 1/3 as a expression of two integer, the numerator and the denominator, instead of .333333 (with loss of precision). Thus we can prevent this kind of error.
Consider this set of equations
                  5x3 = 10
                  3x2 - 3x3 = 3
                  2x1 - x2 + 2x3 = 7
This set of equations can be written as
0     0     5    10
0     3   -3     3
2   -1     2     7
Now how will you evaluate this matrix without ordering?

The Input

The first line of input is the number of the problem. The next line contains two integers - NumberOfUnknowns and NumberOfEquations (none of these is less then or equal to 0 and greater then 50). The next lines contains the matrix for the system of linear equations. There are number of rows equal to the NumberOfEquations and number of column equal to the NumberOfUnknowns+1. The numbers may be fractional, that is there may be numbers like 1/3 or 6/8. An problem number zero indicates the end of input.

The Output : 

First print (without the quotation mark)
"Solution for Matrix System # N"
Here `N' is the problem number as taken from input. Then on the next line, for each system of equations output the solution (if exists) expressed in the fractional form in each line. You may assume each of the numerator and denominator part will not exceed the limit of data type long long (64 bit). If there are many solutions as described above print (without the quotation mark)
"Infinitely many solutions containing n arbitrary constants."
(here `n' is the number as described above) , and if there is no solutions print (without the quotation mark)
"No Solution."
.Print a blank line between two systems of linear equations.

Sample Input : 

1
3 3
9  4  1 -17
1 -2 -6 14
1  6  0  4

2
3 3
2 2 2 2
4 4 4 4
16/1 16/1 16/1 16/1

3
2 3
1 1 10
1 1 20
2 2 50

4
1 1
3 10

0

Sample Output : 

Solution for Matrix System # 1

x[1] = -2
x[2] = 1
x[3] = -3

Solution for Matrix System # 2
Infinitely many solutions containing 2 arbitrary constants.

Solution for Matrix System # 3
No Solution.

Solution for Matrix System # 4

x[1] = 10/3

Category: , ,

About GalleryBloggerTemplates.com:
GalleryBloggerTemplates.com is Free Blogger Templates Gallery. We provide Blogger templates for free. You can find about tutorials, blogger hacks, SEO optimization, tips and tricks here!

0 comments