Previous Lecture

lect04

Next Lecture

lect04, Thu 01/16

LU factorization: error, residual, complexity, partial pivoting

• Lecture Files

Reading assignment

Next Tuesday’s lecture topics are not in the NCM book. Instead, please read two sections of the Templates book: one on the Jacobi method and one on the conjugate gradient method (CG).

If you’re interested in learning more about how CG works, there’s a great paper called An introduction to the conjugate gradient method without the agonizing pain by Jonathan Shewchuk at Berkeley. Reading it is optional for CS 111, but fun if you like the math.

References for today’s lecture

NCM Sections 2.1 through 2.6 (linear equations and Gaussian elimination), Sections 2.8 (error and residual).

Outline

• This week’s big idea: Matrix Factorizations

• More on solving Ax = b by Gaussian elimination:
  • Residual b - Ax, residual norm
  • Details of lower triangular solve
  • Complexity analysis of LU factorization and triangular solve
  • LU factorization with partial pivoting
  • Permutation vectors and permutation matrices
• Interesting matrices:
  • Permutation matrices
• numpy/scipy routines:
  • npla.norm()
  • npla.solve()
  • spla.lu()
• Lecture codes:
  • LUfactor()
  • Lsolve()
  • Usolve()
  • LUsolve()