Are there any other methods to apply to solving simultaneous equations?

Question

We are asked to solve for $x$ and $y$ in the following pair of simultaneous equations:

$$\begin{align}3x+2y&=36 \tag1\\ 5x+4y&=64\tag2\end{align}$$

I can multiply $(1)$ by $2$, yielding $6x + 4y = 72$, and subtracting $(2)$ from this new equation eliminates $4y$ to solve strictly for $x$; i.e. $6x - 5x = 72 - 64 \Rightarrow x = 8$. Substituting $x=8$ into $(2)$ reveals that $y=6$.

I could also subtract $(1)$ from $(2)$ and divide by $2$, yielding $x+y=14$. Let $$\begin{align}3x+3y - y &= 36 \tag{1a}\\ 5x + 5y - y &= 64\tag{1b}\end{align}$$ then expand brackets, and it follows that $42 - y = 36$ and $70 - y = 64$, thus revealing $y=6$ and so $x = 14 - 6 = 8$.

I can even use matrices!

$(1)$ and $(2)$ could be written in matrix form:

$$\begin{align}\begin{bmatrix} 3 &2 \\ 5 &4\end{bmatrix}\begin{bmatrix} x \\ y\end{bmatrix}&=\begin{bmatrix}36 \\ 64\end{bmatrix}\tag3 \\ \begin{bmatrix} x \\ y\end{bmatrix} &= {\begin{bmatrix} 3 &2 \\ 5 &4\end{bmatrix}}^{-1}\begin{bmatrix}36 \\ 64\end{bmatrix} \\ &= \frac{1}{2}\begin{bmatrix}4 &-2 \\ -5 &3\end{bmatrix}\begin{bmatrix}36 \\ 64\end{bmatrix} \\ &=\frac12\begin{bmatrix} 16 \\ 12\end{bmatrix} \\ &= \begin{bmatrix} 8 \\ 6\end{bmatrix} \\ \\ \therefore x&=8 \\ \therefore y&= 6\end{align}$$

---

Question

Are there any other methods to solve for both $x$ and $y$?

Answer 1

Is this method allowed ?

$$\left[\begin{array}{rr|rr} 3 & 2 & 36 \\ 5 & 4 & 64 \end{array}\right] \sim \left[\begin{array}{rr|rr} 1 & \frac{2}{3} & 12 \\ 5 & 4 & 64 \end{array}\right] \sim \left[\begin{array}{rr|rr} 1 & \frac{2}{3} & 12 \\ 0 & \frac{2}{3} & 4 \end{array}\right] \sim \left[\begin{array}{rr|rr} 1 & 0 & 8 \\ 0 & \frac{2}{3} & 4 \end{array}\right] \sim \left[\begin{array}{rr|rr} 1 & 0 & 8 \\ 0 & 1 & 6 \end{array}\right] $$

which yields $x=8$ and $y=6$

---

The first step is $R_1 \to R_1 \times \frac{1}{3}$

The second step is $R_2 \to R_2 - 5R_1$

The third step is $R_1 \to R_1 -R_2$

The fourth step is $R_2 \to R_2\times \frac{3}{2}$

Here $R_i$ denotes the $i$ -th row.

Answer 2

Fixed Point Iteration

This is not efficient but it's another valid way to solve the system. Treat the system as a matrix equation and rearrange to get $\begin{bmatrix} x\\ y\end{bmatrix}$ on the left hand side.

Define $f\begin{bmatrix} x\\ y\end{bmatrix}=\begin{bmatrix} (36-2y)/3 \\ (64-5x)/4\end{bmatrix}$

Start with an intial guess of $\begin{bmatrix} x\\ y\end{bmatrix}=\begin{bmatrix} 0\\ 0\end{bmatrix}$

The result is $f\begin{bmatrix} 0\\ 0\end{bmatrix}=\begin{bmatrix} 12\\ 16\end{bmatrix}$

Now plug that back into f

The result is $f\begin{bmatrix} 12\\ 6\end{bmatrix}=\begin{bmatrix} 4/3\\ 1\end{bmatrix}$

Keep plugging the result back in. After 100 iterations you have:

$\begin{bmatrix} 7.9991\\ 5.9993\end{bmatrix}$

Here is a graph of the progression of the iteration:

Answer 3

How about using Cramer's Rule? Define $\Delta_x=\left[\begin{matrix}36 & 2 \\ 64 & 4\end{matrix}\right]$, $\Delta_y=\left[\begin{matrix}3 & 36\\ 5 & 64\end{matrix}\right]$ and $\Delta_0=\left[\begin{matrix}3 & 2\\ 5 &4\end{matrix}\right]$.

Now computation is trivial as you have: $x=\dfrac{\det\Delta_x}{\det\Delta_0}$ and $y=\dfrac{\det\Delta_y}{\det\Delta_0}$.

Answer 4

By false position:

Assume $x=10,y=3$, which fulfills the first equation, and let $x=10+x',y=3+y'$. Now, after simplification

$$3x'+2y'=0,\\5x'+4y'=2.$$

We easily eliminate $y'$ (using $4y'=-6x'$) and get

$$-x'=2.$$

Though this method is not essentially different from, say elimination, it can be useful for by-hand computation as it yields smaller terms.

Answer 5

Construct the Groebner basis of your system, with the variables ordered $x$, $y$: $$ \mathrm{GB}(\{3x+2y-36, 5x+4y-64\}) = \{y-6, x-8\} $$ and read out the solution. (If we reverse the variable order, we get the same basis, but in reversed order.) Under the hood, this is performing Gaussian elimination for this problem. However, Groebner bases are not restricted to linear systems, so can be used to construct solution sets for systems of polynomials in several variables.

---

Perform lattice reduction on the lattice generated by $(3,2,-36)$ and $(5,4,-64)$. A sequence of reductions (similar to the Euclidean algorithm for GCDs): \begin{align*} (5,4,-64) - (3,2,-36) &= (2,2,-28) \\ (3,2,-36) - (2,2,-28) &= (1,0,-8) \tag{1} \\ (2,2,-28) - 2(1,0,-8) &= (0,2,-12) \tag{2} \\ \end{align*} From (1), we have $x=8$. From (2), $2y = 12$, so $y = 6$. (Generally, there can be quite a bit more "creativity" required to get the needed zeroes in the lattice vector components. One implementation of the LLL algorithm, terminates with the shorter vectors $\{(-1,2,4), (-2,2,4)\}$, but we would continue to manipulate these to get the desired zeroes.)

Answer 6

Another method to solve simultaneous equations in two dimensions, is by plotting graphs of the equations on a cartesian plane, and finding the point of intersection.

Answer 7

Any method you can come up with will in the end amount to Cramer's rule, which gives explicit formulas for the solution. Except special cases, the solution of a system is unique, so that you will always be computing the ratio of those determinants.

Anyway, it turns out that by organizing the computation in certain ways, you can reduce the number of arithmetic operations to be performed. For $2\times2$ systems, the different variants make little difference in this respect. Things become more interesting for $n\times n$ systems.

Direct application of Cramer is by far the worse, as it takes a number of operations proportional to $(n+1)!$, which is huge. Even for $3\times3$ systems, it should be avoided. The best method to date is Gaussian elimination (you eliminate one unknown at a time by forming linear combinations of the equations and turn the system to a triangular form). The total workload is proportional to $n^3$ operations.

---

The steps of standard Gaussian elimination:

$$\begin{cases}ax+by=c,\\dx+ey=f.\end{cases}$$

Subtract the first times $\dfrac da$ from the second,

$$\begin{cases}ax+by=c,\\0x+\left(e-b\dfrac da\right)y=f-c\dfrac da.\end{cases}$$

Solve for $y$,

$$\begin{cases}ax+by=c,\\y=\dfrac{f-c\dfrac da}{e-b\dfrac da}.\end{cases}$$

Solve for $x$,

$$\begin{cases}x=\dfrac{c-b\dfrac{f-c\dfrac da}{e-b\dfrac da}}a,\\y=\dfrac{f-c\dfrac da}{e-b\dfrac da}.\end{cases}$$

So written, the formulas are a little scary, but when you use intermediate variables, the complexity vanishes:

$$d'=\frac da,e'=e-bd',f'=f-cd'\to y=\frac{f'}{e'}, x=\frac{c-by}a.$$

Anyway, for a $2\times2$ system, this is worse than Cramer !

$$\begin{cases}x=\dfrac{ce-bf}{\Delta},\\y=\dfrac{af-cd}{\Delta}\end{cases}$$ where $\Delta=ae-bd$.

---

For large systems, say $100\times100$ and up, very different methods are used. They work by computing approximate solutions and improving them iteratively until the inaccuracy becomes acceptable. Quite often such systems are sparse (many coefficients are zero), and this is exploited to reduce the number of operations. (The direct methods are inappropriate as they will break the sparseness property.)

Answer 8

$$\begin{align}3x+2y&=36 \tag1\\ 5x+4y&=64\tag2\end{align}$$

From $(1)$, $x=\frac{36-2y}{3}$, substitute in $(2)$ and you'll get $5(\frac{36-2y}{3})+4y=64 \implies y=6$ and then you can get that $x=24/3=8$

Another Method From $(1)$, $x=\frac{36-2y}{3}$

From $(2)$, $x=\frac{64-4y}{5}$

But $x=x \implies \frac{36-2y}{3}=\frac{64-4y}{5}$ do cross multiplication and you'll get $5(36-2y)=3(64-4y) \implies y=6$ and substitute to get $x=8$

Answer 9

Other answers have given standard, elementary methods of solving simultaneous equations. Here are a few other ones that can be more long-winded and excessive, but work nonetheless.

---

Method $1$: (multiplicity of $y$)

Let $y=kx$ for some $k\in\Bbb R$. Then $$3x+2y=36\implies x(2k+3)=36\implies x=\frac{36}{2k+3}\\5x+4y=64\implies x(4k+5)=64\implies x=\frac{64}{4k+5}$$ so $$36(4k+5)=64(2k+3)\implies (144-128)k=(192-180)\implies k=\frac34.$$ Now $$x=\frac{64}{4k+5}=\frac{64}{4\cdot\frac34+5}=8\implies y=kx=\frac34\cdot8=6.\quad\square$$

---

Method $2$: (use this if you really like quadratic equations :P)

How about we try squaring the equations? We get $$3x+2y=36\implies 9x^2+12xy+4y^2=1296\\5x+4y=64\implies 25x^2+40xy+16y^2=4096$$ Multiplying the first equation by $10$ and the second by $3$ yields $$90x^2+120xy+40y^2=12960\\75x^2+120xy+48y^2=12288$$ and subtracting gives us $$15x^2-8y^2=672$$ which is a hyperbola. Notice that subtracting the two linear equations gives you $2x+2y=28\implies y=14-x$ so you have the nice quadratic $$15x^2-8(14-x)^2=672.$$ Enjoy!

Answer 10

It is clear that:

• $x=10$, $y=3$ is an integer solution of $(1)$.
• $x=12$, $y=1$ is an integer solution of $(2)$.

Then, from the theory of Linear Diophantine equations:

• Any integer solution of $(1)$ has the form $x_1=10+2t$, $y_1=3-3t$ with $t$ integer.
• Any integer solution of $(2)$ has the form $x_2=12+4t$, $y_2=1-5t$ with $t$ integer.

Then, the system has an integer solution $(x_0,y_0)$ if and only if there exists an integer $t$ such that

$$10+2t=x_0=12+4t\qquad\text{and}\qquad 3-3t=y_0=1-5t.$$

Solving for $t$ we see that there exists an integer $t$ satisfying both equations, which is $t=-1$. Thus the system has the integer solution $$x_0=12+4(-1)=8,\; y_0=1-5(-1)=6.$$

Note that we can pick any pair of integer solutions to start with. And the method will give the solution provided that the solution is integer, which is often not the case.

Answer 11

As another iterative method I suggest the Jacobi Method. A sufficient criterion for its convergence is that the matrix must be diagonally dominant. Which this one in our system is not:

$\begin{bmatrix} 3 &2 \\ 5 &4\end{bmatrix}\begin{bmatrix} x \\ y\end{bmatrix}=\begin{bmatrix}36 \\ 64\end{bmatrix}$

We can however fix this by replacing e.g. $y' := \frac{1}{1.3} y$. Then the system is

$\underbrace{\begin{bmatrix} 3 & 2.6 \\ 5 & 5.2\end{bmatrix}}_{=:A}\begin{bmatrix} x \\ y'\end{bmatrix}=\begin{bmatrix}36 \\ 64\end{bmatrix}$

and $A$ is diagonally dominant. Then we can decompose $A = L + D + U$ into $L,U,D$ where $L,U$ are the strict upper and lower triangular parts and $D$ is the diagonal of $A$ and the iteration

$$\vec x_{i+1} = - D^{-1}((L+R)\vec x_i + b)$$

will converge to the solution $(x,y')$. Note that $D^{-1}$ is particularly easy to compute as you just have to invert the entries. So in theis case the iteration is

$$\vec x_{i+1} = -\begin{bmatrix} 1/3 & 0 \\ 0 & 1/5.2 \end{bmatrix}\left(\begin{bmatrix} 0 & 2.6 \\ 5 & 0 \end{bmatrix} \vec x_i + b\right)$$

So you can actually view this as a fixed point iteration of the function $f(\vec x) = -D^{-1}((L+R)\vec x + b)$ which is guaranteed to be a contraction in the case of diagonal dominance of $A$. It is actually quite slow and doesn't any practical application for directly solving systems of linear equations but it (or variations of it) is quite often used as a preconditioner.

Answer 12

Consider the three vectors $\textbf{A}=(3,2)$, $\textbf{B}=(5,4)$ and $\textbf{X}=(x,y)$. Your system could be written as $$\textbf{A}\cdot\textbf{X}=a\\\textbf{B}\cdot\textbf{X}=b$$ where $a=36$, $b=64$ and $\textbf{A}_{\perp}=(-2,3)$ is orthogonal to $\textbf{A}$. The first equation gives us $\textbf{X}=\dfrac{a\textbf{A}}{\textbf{A}^2}+\lambda\textbf{A}_{\perp}$. Now to find $\lambda$ we use the second equation, we get $\lambda=\dfrac{b}{\textbf{A}_{\perp}\cdot\textbf{B}}-\dfrac{a\textbf{A}\cdot\textbf{B}}{\textbf{A}^2\times\textbf{A}_{\perp}\cdot\textbf{B}}$. Et voilà : $$\textbf{X}=\dfrac{a\textbf{A}}{\textbf{A}^2}+\dfrac{\textbf{A}_{\perp}}{\textbf{A}_{\perp}\cdot\textbf{B}}\left(b-\dfrac{a\textbf{A}\cdot\textbf{B}}{\textbf{A}^2}\right)$$

Answer 13

$$3x+2y=36\tag1$$ $$5x+4y=64\rightarrow \rightarrow \rightarrow \rightarrow 3x+2y+3x+2y-x=64$$ $$36+36-x=64$$ $$x=8$$

Answer 14

If you prefer using parametric form or your equations are already in parametric form, this is how you can proceed:

We know that $(0,18)$ is a solution to $3x+2y=36$ and $(0,16)$ is a solution to $5x + 4y = 64$. Therefore the equations in parametric form become:

$${ \begin{pmatrix} 0 \\ 18 \\ \end{pmatrix} } + t_1 { \begin{pmatrix} 2 \\ -3 \\ \end{pmatrix} } \tag{3}$$ $$\pmatrix { \begin{matrix} 0 \\ 16 \\ \end{matrix} } + t_2 { \begin{pmatrix} 4 \\ -5 \\ \end{pmatrix} } \tag{4} $$

Equate the $x$ and $y$ coordinates:

$$0+2t_1 = 0+4t_2 \Rightarrow t_1 = 2t_2 \tag{5}$$ $$18-3t_1 = 16-5t_2 \Rightarrow 18-6t_2 = 16-5t_2 \text{ (using (5) }) \Rightarrow2 = t_2 \tag{6}$$ and now substitute back into $(4)$:

$$\pmatrix { \begin{matrix} 0 \\ 16 \\ \end{matrix} } + 2 { \begin{pmatrix} 4 \\ -5 \\ \end{pmatrix} } =\pmatrix { \begin{matrix} 8 \\ 6 \\ \end{matrix} } $$

i.e $x=8, y=6$.