From the free course CS323: Numerical Analysis and Computing on Lykke

Iterative Methods and Least Squares

Key concepts: Jacobi Method · Gauss-Seidel Method · Diagonal Dominance · Least Squares (Normal Equations)

Solving large-scale systems and overdetermined problems where an exact solution may not exist.

Iterative Methods and Least Squares

Overview

For extremely large or sparse matrices, direct methods become computationally expensive. Iterative methods refine an initial guess until convergence. Additionally, we address "overdetermined" systems where we seek the best possible fit.

Key Concepts

  • Jacobi vs. Gauss-Seidel: Jacobi updates all components simultaneously, while Gauss-Seidel uses the most recently updated values within the same iteration.
  • Convergence: Iterative methods are guaranteed to converge if the matrix $A$ is strictly diagonally dominant.
  • Least Squares: Used when $Ax = b$ has no solution. We solve the Normal Equations ($A^T Ax = A^T b$) to minimize the squared residual $||Ax - b||_2^2$.

Practical Application

Homework #3 explores least squares polynomial fitting and the sensitivity of normal equations to perturbations.

Source Materials

Study CS323: Numerical Analysis and Computing on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of CS323: Numerical Analysis and Computing · Browse more course pages

Iterative Methods and Least Squares — CS323: Numerical Analysis and Computing | Lykke