A lineal equation systems is formed by n equations with n variables, where all the terms in the equations have the form constant*variable. For example, this is a system with 4 equations and 4 variables.
2x + 3y + 4z + 3w - 17 = 0 x + y + z + 2w - 4 = 0 -2x + 4y - z + 4w + 1 = 0 x + 3y + 5z + 7w - 15 = 0To solve the system means to find a value for all the variables such as all the equations are satisfied.
One method to solve these systems is to mix pairs of equations in order to get a diagonalizated system. A diagonalizated system is a system where all the terms are zero, but terms in the main diagonal and in the last column. After the diagonalization process of the previos example, we could get a system like this:
-2.701x + 0 + 0 + 0 + 2.701 = 0 0 + -3.019y + 0 + 0 + 6.039 = 0 0 + 0 + 3.666z + 0 - 11.000 = 0 0 + 0 + 0 - 4.666w - 4.666 = 0With this transformed system is very easy to calculate the variable values: for each variable, divide the value in the last column between the variable coeficient, and change the sign.
x = 1 y = 2 z = 3 w = -1
The steps to program this exercise are:
2 | 3 | 4 | 3 | -17 |
1 | 1 | 1 | 2 | -4 |
-2 | 4 | -1 | 4 | 1 |
1 | 3 | 5 | 7 | -15 |
FOR (d=0 ; d<N ; d++) // get 0 in all positions but (d-th,d-th). FOR (row=0 ; row<N ; row++) // transforms row: "row-th", column: "d-th". IF (row != d) // but skip row d-th. (d-th,d-th) is a non-zero position. IF (array[row][d] != 0) { // skip (row,d) if already zero. // sum rows d-th and row-th. k = array[d][d]/array[row][d]; // multiply factor to get 0 at (row,d) FOR (col=0 ; col<=N ; col++) array[row][col] = k*array[row][col] - array[d][col]; }The values in the array are now:
-2.701 | 0 | 0 | 0 | 2.701 |
0 | -3.019 | 0 | 0 | 6.039 |
0 | 0 | 3.666 | 0 | -11.000 |
0 | 0 | 0 | -4.666 | -4.666 |