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
