5.2 The LU decomposition

In the previous chapter, I promised that you’d never have to solve a linear equation by hand. As it turns out, this task is perfectly suitable for computers. In this chapter, we will dive deep into the art of solving linear equations, developing the tools from scratch.

We start by describing the process of Gaussian elimination in terms of matrices. Why would we even do that? Because matrix multiplication can be performed extremely fast in modern computers. Expressing any algorithm in terms of matrices is a sure way to accelerate.

At the start, our linear equation Ax = b is given by the coefficient matrix

and at the end of the elimination process, A is transformed into the form

A⁽ⁿ⁻¹⁾ is upper diagonal; that is, all elements below its diagonal are 0.

Gaussian elimination performs this task one step at a time, focusing on consecutive columns. After the first elimination step, this is turned into the equation (5.1.1), described by the coefficient...