Numerical Linear Algebra with Applications

Chapter 11

Gaussian Elimination and the LU Decomposition

Abstract

The chapter continues the development of Gaussian elimination started in Chapter 2. First, it intuitively explains the LU decomposition (factorization) without pivoting, introduces elementary row matrices, and uses them to prove why the LU decomposition (A = LU) works. The chapter gives an algorithm for Gaussian elimination without partial pivoting and computes its flop count. Gaussian elimination as introduced in Chapter 2 and continued here is unstable. The chapter introduces the idea of partial pivoting with a classic example where partial pivoting is necessary to obtain a correct result. After explaining the details of partial pivoting, the result PA = LU is proved using ...