Gaussian elimination
When you solve systems of linear equations, you probably use Gaussian elimination, even if you don't call it that. You may learn Gaussian elimination before you see it formalized in terms of matrices.
So if you've had a course in linear algebra, and you sign up for a course in numerical linear algebra, it's natural to expect that Gaussian elimination would be one of the first things you talk about. That was my experience, and it was painful. I had this odd mixture of feeling like I already knew what the professor was talking about, while at the same time feeling lost.
Trefethen and Bau do not start their numerical linear algebra textbook with Gaussian elimination, and they explain why in the preface:
We have departed from the customary practice by not starting with Gaussian elimination. That algorithm is atypical of numerical linear algebra, exceptionally difficult to analyze, yet at the same time tediously familiar to every student in a course like this. Instead, we begin with the QR factorization, which is more important, less complicated, and fresher idea to most students.
It's reassuring to hear experts in numerical linear algebra admit that Gaussian elimination is exceptionally difficult to analyze." The algorithm is not exceptionally difficult to perform; children learn to manually execute the algorithm. But it is surprisingly difficult, and tedious, to analyze.
Numerical analysts like Trefethen and Bau have much more sophisticated questions in mind than how you would naively carry out the algorithm by hand. Numerical analysts are concerned, for example, with stability.
If your coefficients are known exactly and you carry out your arithmetic exactly, then you get an exact result. But can a small change to your inputs, say due to measurement uncertainty, or the inevitable loss of precision from floating point arithmetic, make a large change in your results? Absolutely, unless you use pivoting. But with pivoting, Gaussian elimination is stable [1].
After taking an introductory linear algebra course, you know how to solve any linear system of equations in principle. But when you actually want to compute the solution accurately, efficiently, at scale, in a real computer, with real data, things can get much more interesting. Many people have devoted their careers to doing in practice what high school students know how to do in principle.
Related posts- Low-rank matrix peturbations
- It all boils down to linear algebra
- Vector spaces over finite fields
- Gershgorin disks
[1] There are matrices for which Gaussian elimination is unstable, but they are rare. It's been shown that they are rare in the sense of having low probability, but more importantly they never arise naturally in applied problems.
The post Gaussian elimination first appeared on John D. Cook.