Simultaneous Linear Equations

Several methods for solving systems of simultaneous linear equations. All the examples shown are for 3 variables, but can easily be expanded 2 $n$ variables.

Cramer's Rule

For a system of 3 equations:

Calculate the determinant $Δ$ of the matrix of coefficients
Calculate determinants $Δ_{1}, Δ_{2}, ..., Δ_{n}$ by replacing 1 column of the matrix with the solutions
Use determinants to calculate unknowns

$a_{1} x + b_{1} y + c_{1} z = d_{1} a_{2} x + b_{2} y + c_{2} z = d_{2} a_{3} x + b_{3} y + c_{3} z = d_{3}$

$a_{1} a_{2} a_{3} b_{1} b_{2} b_{3} c_{1} c_{2} c_{3} \cdot x y z = d_{1} d_{2} d_{3}$

$Δ = a_{1} a_{2} a_{3} b_{1} b_{2} b_{3} c_{1} c_{2} c_{3} Δ_{1} = d_{1} d_{2} d_{3} b_{1} b_{2} b_{3} c_{1} c_{2} c_{3}$

$Δ_{2} = a_{1} a_{2} a_{3} d_{1} d_{2} d_{3} c_{1} c_{2} c_{3} Δ_{3} = a_{1} a_{2} a_{3} b_{1} b_{2} b_{3} d_{1} d_{2} d_{3}$

$x = \frac{Δ _{1}}{Δ} y = \frac{Δ _{2}}{Δ} z = \frac{Δ _{3}}{Δ}$

Matrix Inversion

For a system of equations in matrix form $M x = a$ The solutions $x$ is given by

$x = M^{- 1} a$

The system has no solutions if $det M = 0$

Gaussian Elimination

Eliminating variables from equations one at a time to give a solution. Generally speaking, for a system of 3 equations

$a_{1} x + b_{1} y + c_{1} z = d_{1} (1) a_{2} x + b_{2} y + c_{2} z = d_{2} (2) a_{3} x + b_{3} y + c_{3} z = d_{3} (3)$

First, eliminate x from $(2)$ and $(3)$ $a_{1} (2) - a_{2} (1) = (2) (n e w)$ $a_{1} (3) - a_{3} (1) = (3) (n e w)$

This gives

$a_{1} x + b_{1} y + c_{1} z = d_{1} (1) b_{2} y + c_{2} z = d_{2} (2) b_{3} y + c_{3} z = d_{3} (3)$

Then, eliminate y from $(3)$ $b_{2} (3) - b_{3} (2) = (3) (n e w)$

Giving

$a_{1} x + b_{1} y + c_{1} z = d_{1} (1) b_{2} y + c_{2} z = d_{2} (2) c_{3} z = \tilde{d_{3}} (3)$

This gives a solution for $z$ , which can then be back-substituted to find the solutions for $x$ and $y$ .

$z = \frac{d _{3}}{c _{3}}$ $y = \frac{d _{2}}{b _{2}} - \frac{c _{2}}{b _{2}} z$ $x = \frac{d _{1}}{a _{1}} - \frac{b _{1}}{a _{1}} y - f r a c c_{1} a_{1} z$

The advantages of this method are:

No need for matrices (yay)
Works for homogenous and inhomogeneous systems
The matrix need not be square
Works for any size of system if a solution exists

Sometimes, the solution can end up being in a parametric form, for example:

$4 x + y + z = 9 x + y + z = 6 x + 2 y + 2 z = 11 (1) (2) (3)$

$4 x + y + z = 9 3 y + 3 z = 15 7 y + 7 z = 35 (1) 4 (2) - 1 (1) 4 (3) - 1 (1)$

$4 x + y + z = 9 3 y + 3 z = 15 0 z = 0 (1) 4 (2) - 1 (1) 3 (3) - 7 (2)$

This doesn't make sense, as the final equation is satisfied for any value of $z$ . Substituting a parameter $λ$ for $z$ gives:

$z = λ y = 5 - λ x = 1$

Iterative methods involve starting with a guess, then making closer and closer approximations to the solution. If iterations tend towards a limit, then the system converges and the limit will be a solution. If the system diverges, there is no solution for this iteration. For the gauss-seidel scheme:

$a_{1} x + b_{1} y + c_{1} z = d_{1} (1) a_{2} x + b_{2} y + c_{2} z = d_{2} (2) a_{3} x + b_{3} y + c_{3} z = d_{3} (3)$

Rearrange to get iterative formulae:

$x^{r + 1} = (d_{1} - b_{1} y^{r} - c_{1} z^{r}) / a_{1} (1) y^{r + 1} = (d_{2} - a_{2} x^{r + 1} - c_{2} z^{r}) / b_{2} (2) z^{r + 1} = (d_{3} - a_{3} x^{r + 1} - b_{3} y^{r + 1}) / c_{3} (3)$

Using these formulae, make a guess at a starting value and then continue to iterate. For example:

$4 x + 1 y + 1 z = 9 (1) 1 x + 5 y + 1 z = 14 (2) 1 x + 1 y + 3 z = 12 (3)$

Rearranging:

$x^{r + 1} = (9 - y^{r} - z^{r}) /4 (1) y^{r + 1} = (14 - x^{r + 1} - z^{r}) /5 (2) z^{r + 1} = (12 - x^{r + 1} - y^{r + 1}) /3 (3)$

The solutions are $x = 1$ , $y = 2$ , $z = 3$ , as can be seen from the table below containing the iterations:

r	x	y	z
0	0	0	0
1	2.25	2.35	2.467
2	1.046	2.098	2.952
3	0.988	2.012	3.000
4	0.997	2.001	3.001

Note that this will only work if the system is diagonally dominant. For a system to be diagonally dominant, the divisor of the iterative equation must be greater than the sum of the other coefficients.

$4 x + 1 y + 1 z = 9 1 x + 5 y + 1 z = 14 1 x + 1 y + 3 z = 12$

Systems can be rearranged to have this property:

$2 x + 7 y + 1 z = 5 - 1 x + 3 y + 3 z = 2 - 6 x + 2 y + 2 z = - 3$

Rearranges to:

$- 6 x + 2 y + 1 z = - 3 2 x + 7 y + 1 z = 5 - 1 x + 3 y + 8 z = 2$

Computer Systems Engineering Notes

Simultaneous Linear Equations

Cramer's Rule

Matrix Inversion

Gaussian Elimination

Gauss-Seidel Iteration