Deep Dive into the Algorithm
In the previous post (Part 1), we introduced the basic concept and Excel VBA code for the Gauss Elimination Method. In this post, we will look under the hood at the mathematical derivation that makes this algorithm work.
Understanding these steps is critical for engineers who want to write their own solvers or understand why simulation software sometimes fails (e.g., division by zero errors).
Phase 1: Forward Elimination
Why do we call it "Elimination"? Because our goal is to systematically remove variables from equations until we are left with a solvable state.
Let's consider the general form of a system of linear equations:
Step 1: Normalization
The algorithm starts by normalizing the first equation. We divide the entire Equation (1) by the coefficient of x1 (which is a11). This prepares it for the elimination step.
Step 2: Elimination
Next, we multiply this normalized equation by the leading coefficient of the second equation (a21). This makes the x1 terms in both equations identical.
By subtracting Equation (2) from this new equation, the x1 term vanishes. We are left with a modified equation:
Mathematically, we simplify the notation using primes (') to indicate modified coefficients. This gives us the standard eliminated form:
Step 3: The Upper Triangular Matrix
We repeat this procedure for all remaining rows (n rows). For the next round, we move to the second column, using a'22 as the pivot to eliminate terms below it. Eventually, we achieve an Upper Triangular System:
At the final stage (n-1 rounds of elimination), the system looks like this. Note that the last equation now has only one variable (xn), which is easily solvable.
Phase 2: Backward Substitution
Now we simply climb back up the ladder. First, we compute the value of the last variable xn:
Once xn is known, we plug it into the previous equation to find xn-1. The general formula for finding any variable xi is:
Computational Complexity
For engineers dealing with massive matrices (like in 3D FEA meshes), speed matters. The computational cost of Gauss Elimination is approximately O(n3).
- For a small 3x3 matrix, this is negligible.
- For a 10,000 x 10,000 matrix (common in thermal analysis), the calculation becomes heavy, which is why optimized variations like LU Decomposition are often used in commercial software.
What if the Pivot is Zero?
A major limitation of the basic algorithm shown above is the "Division by Zero" error. If a11 or any pivot element is zero, the code will crash.
To solve this, we must use a technique called Partial Pivoting. We will cover this critical improvement in the next post.
Next Part
Continue to Part 3 where we discuss limitations and improvements:
Solving System of Equations using Gauss Elimination Method (Part 3)
Comments