Miqdad Abdurrahman
How To Programmatically Solve Linear Equation using Gaussian Elimination
Gaussian Elimination also known as row reduction process that uses these operations:
Swapping two rows,
Multiplying a row by a nonzero scalar,
Adding a multiple of one row to another.
Using these operations, the goal is to transformed the matrix into echelon form.
Echelon form is more less an upper triangular matrix which has zeros below the main diagonal (from top left to botton right) and it is also unique. Here is an example.
[21−1−3−12−212][8−113]⟶[21−10121200−1][811]\begin{bmatrix}
2 & 1 & -1\\
-3 & -1 & 2\\
-2 & 1 & 2\\
\end{bmatrix}
\begin{bmatrix}
8\\
-11\\
3\\
\end{bmatrix}
\longrightarrow
\begin{bmatrix}
2 & 1 & -1\\
0 & \frac{1}{2} & \frac{1}{2}\\
0 & 0 & -1\\
\end{bmatrix}
\begin{bmatrix}
8\\
1\\
1\\
\end{bmatrix}2−3−21−11−1228−113⟶2001210−121−1811
How to get the echelon form programatically?
Remember we can do operation mentioned above, from that we can make a generic like:
Li=Li−ϕLi+1L_i = L_i - \phi L_{i+1}Li=Li−ϕLi+1
where LLL is the row and iii is the row index and ϕ\phiϕ is a scaling factor obtained from
ϕ=e(j,i)e(i,i)\phi = \frac{e_{(j,i)}}{e_{(i,i)}} ϕ=e(i,i)e(j,i)
where jjj is the column index.
Step 1:
for example reducing the L2L_2L2 from the matrix above
the ϕ\phiϕ will be the element at 0,0 and 1,0:
ϕ=e0,0e1,0=−31\phi = \frac{e_{0,0}}{e_{1,0}} = \frac{-3}{1}ϕ=e1,0e0,0=1−3
then do operation
L2=L2−−31L1L_2 = L_2 - \frac{-3}{1} L_1L2=L2−1−3L1
so the L2L_2L2 becomes
[21−101212−212][813]\begin{bmatrix}
2 & 1 & -1\\
0 & \frac{1}{2} & \frac{1}{2}\\
-2 & 1 & 2\\
\end{bmatrix}
\begin{bmatrix}
8\\
1\\
3\\
\end{bmatrix}20−21211−1212813
After that do same operation for the L3L_3L3,
calculate the ϕ\phiϕ
ϕ=e0,0e2,0=2−2\phi = \frac{e_{0,0}}{e_{2,0}} = \frac{2}{-2}ϕ=e2,0e0,0=−22
then L3L_3L3 becomes,
[21−101212021][815]\begin{bmatrix}
2 & 1 & -1\\
0 & \frac{1}{2} & \frac{1}{2}\\
0 & 2 & 1\\
\end{bmatrix}
\begin{bmatrix}
8\\
1\\
5\\
\end{bmatrix}2001212−1211815
Why not do L3=L3+L1L_3=L_3+L_1L3=L3+L1 directly?
It's because we need to do the same operation for all rows, otherwise it will be hard to code
Step 2
Now, it's done for the second column, move to the third columns.
This time what is the ϕ\phiϕ will be ?
ϕ=e1,1e2,1=212\phi = \frac{e_{1,1}}{e_{2,1}} = \frac{2}{\frac{1}{2}}ϕ=e2,1e1,1=212
Do we need to operate the first row?
NO, because we only need to make zeros below the main diagonal.
now the L3L_3L3 will be
[21−10121200−1][811]\begin{bmatrix}
2 & 1 & -1\\
0 & \frac{1}{2} & \frac{1}{2}\\
0 & 0 & -1\\
\end{bmatrix}
\begin{bmatrix}
8\\
1\\
1\\
\end{bmatrix}2001210−121−1811
Is it finished?
Yes, because it's all zeros below the main diagonal
Step 3
Now, we can get the value of Z and from that we do back substitution for Y and X
Tue Sep 24 2024