Learned something fun today ... a method for solving a system of linear equations called “Gaussian elimination”. Something I'm working on now requires solving thousands of these things, and I certainly didn't want to do it by hand. The manual method that I knew of didn't lend itself to being implemented in software, but the Gaussian elimination does so admirably. I actually implemented it on a spreadsheet, and it worked beautifully.
It's rare that I implement something in software without understanding how it works – but this will likely be one of them. I've studied this article until my brains hurt, and I still have absolutely zero idea how it works. It might as well be black magic so far as I'm concerned :)
You are clearly a much better programmer than I, but I have used Gaussian elimination sporadically in my career starting back in college. Your musings got me to thinking about how I would explain Gaussian elimination, which got me to wondering how well I actually understand it. Let me take a whack at it ...
ReplyDeleteAfter discussing this with my calculus tutor wife, I think the key to this is a couple of basic principles of algebra. First, you can multiply both sides of an equation by the same constant and create another valid, true equation. Second, you can add equal quantities to both sides of an equation and get a valid equation.
Since an equation, by definition, has equal quantities on both sides of the equals sign, you can add one equation to another equation (left hand side to left hand side, right hand side to right hand side) and get a new valid equation. By itself, that isn't very useful or interesting, but if you multiply the first equation by a carefully chosen constant, something neat happens: you can make one (or more) of the coefficients of the resulting equation to be zero. If you keep doing this carefully, you can create an equation of the form:
CnXn = some constant.
You can repeat this process for all of the n variables to completely solve the system of equations. This process depends on having the same number of equations as variables.
Gaussian elimination is an efficient, numerically stable way to implement this process. We store the coefficients of the system of equations in a square matrix, one row per equation, which is augmented with a column holding the right hand side constants.
Multiplying an equation by a constant is as simple as multiplying each value in a row by the constant. Adding one equation to another is just adding one row to another. Rinse, repeat as necessary.
There are some things that can be done to improve the numerical stability by reducing the effects of finite precision round-off errors, but that is a detail left to the student. :)
Thank you, Richard! While reading your explanation, I had the proverbial light bulb moment. What was hanging me up was not remembering that the matrix just represents the coefficients of the equations I started with. Using algebra to manipulate the equations is something I'm quite used to - in fact, when calculating this stuff by hand, that's what I did (though mostly using substitution instead of the Gaussian elimination techniques). I've done very little work with matrices, so they are an unfamiliar (and therefore confusing) element for me. But if I just think about the matrix as a set of linear equations (really just a notation difference), I'm solidly back into familiar territory. So the Gaussian elimination isn't some form of dark magic, but just an algorithmic approach to solving a set of linear equations. Got it! Hooray!
ReplyDeleteI'm much more comfortable implementing something I actually understand :)
The floating point round-off issues I understand well, thankfully. Mainly that means avoiding dividing by little numbers, which I think mainly means swapping the order of the equations...
Yep, good Gaussian elimination routines do something called partial pivoting, which mainly means use the largest coefficient to eliminate the others.You can swap rows and even columns (if you keep track) to get the large coefficient into the right place. You can use Gaussian elimination for more than just solving the system of equations. You can also get matrix determinants and inverses, as well as some other linear algebra stuff that I've been trying to forget for thirty years.
ReplyDeleteMy wife and I had fun wordsmithing last night. We were both in the same linear algebra class those many years ago and it was interesting for us to dredge all this back up. She's the teacher of the two of us and she had strong opinions on phrases describing algebra operations that work and don't work with students. That's a different topic, though.