Solving Linear Systems of Equations

Solving Linear Systems of Equations Through Gauss-Jordan Elimination

Many algorithms exist for solving systems of equations, and one popular method is Gauss-Jordan Elimination. The basic idea of that algorithm is that each equation is added to a multiple of another equation, so for example, given these equations:

R₁: x + y = 30
R₂: 2x - y = 15
You would add -2R₁ to R₁, which would become:
-3y = -45, so y = 15

This algorithm is very fast in solving systems, because they require a linear amount of time: every 2 x 2 system of equations has three steps: take out the first term of the second equation like that, and take out the second term of the first equation, and then divide by the x or y terms to get the answer. Because solving linear systems of equations are so ubiquitous in schools, I decided to write a program to solve 2 x 2 systems of equations.

It was similar to the algorithm explained above, but I implemented it using a two-dimensional array. Two by two systems of equations are very simple because you only have to account for two variables. This is what I did:

Here, I wrote a function to multiple a list by a scalar and another to add two lists,  to do the aforementioned task to eliminate a variable. 

def multList(scalar, array):
    return list(map(lambda x: x * scalar, array))
def addLists(array1,array2):
    return [array1[i] + array2[i] for i in range(len(array1))]

In order to take out a specific spot, I wrote a function to take out a specific variable, so taking out the Nth position, will take out the Nth position of the second equation.

def toPos(arrays,pos):#takeout position
    arrays[1] = addLists(multList(-arrays[1][pos]/arrays[0][pos], arrays[0]), arrays[1])
    return arrays

After that, you get a result like:

[3, 0, 12], [0, -5, 15], and now all you have to do is divide by 3 or -5, respectively. That becomes:

arrays = [multList(1/i[1-n], i) for n, i in enumerate(arrays)]
arrays = [[round(j, 5) for j in i] for i in arrays]

I round it to take out any floating point precision error. So, it takes out the first position, switches the order of the lists, and takes out the second position. 

A 3 by 3 system of equations is pretty similar, and I do three steps, I take out the first term, I solve the last two equations, and I back substitute the answer into the first equation. I did it like this:

def toPos(rows): #sort and eliminate
        rows[1:] = [addparts(i, multList(-i[0]/rows[0][0], rows[0])) for i in rows[1:]]
        return rows

After, I solve the last two rows, and I back substitute: implemented like this:

def backSubstitute(self):
        rows[0] = addparts(addparts(rows[0], multList(-rows[0][1], rows[2])), multList(-rows[0][2], rows[1]))
        rows[0] = multList(1/rows[0][0], rows[0])
        return rows

Overall, it's very fast, as the amount of steps it takes to do the operation is always constant. Also, it only works when there's only one solution for the system: I didn't bother making it account for a line being a solution. 

Here's the code: Systemsolver

-David Witten