Previous Lecture

lect03

Next Lecture

lect03, Mon 01/14

Solving Ax=b by LU factorization

• Lecture Files

Reading assignment

Wednesday’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).

Outline of today’s lecture

More interesting kinds of matrices:

• triangular matrices
• unit triangular matrices

Solving Ax = b:

• Residual b - Ax, residual norm
• Solving triangular systems
• Gaussian elimination and LU factorization
• Partial pivoting
• Lecture codes:
  • LUfactor()
  • Lsolve()
  • Usolve()
• numpy/scipy routines:
  • npla.matrix_rank()
  • npla.norm()
  • npla.cond()
  • npla.solve()
  • linalg.lu()