Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Iterative Solvers: Theory and Comparison

Description

This lecture explores the concept of solving linear systems iteratively, where a subroutine is repeatedly run to converge to a more accurate solution. The instructor discusses theoretical and practical criteria for comparing different solvers, emphasizing worst-case assumptions and measures of convergence. Various solvers such as Richardson iteration, Chebyshev, and CG are compared based on iteration count, convergence guarantees, and bit complexity. The lecture delves into the importance of adaptivity and cost in the Preconditioned Conjugate Gradient method, highlighting the nested nonlinear hierarchy of problems and the Stieltjes problem of moments. Additionally, the lecture touches on the interplay of infinite and finite dimensions, spectral information, and the impact of rounding errors in iterative solvers.

Official source

Related concepts (23)

Iterative method

In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones. A specific implementation with termination criteria for a given iterative method like gradient descent, hill climbing, Newton's method, or quasi-Newton methods like BFGS, is an algorithm of the iterative method.

Conjugate gradient method

In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems.

Preconditioner

In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducing a condition number of the problem. The preconditioned problem is then usually solved by an iterative method. In linear algebra and numerical analysis, a preconditioner of a matrix is a matrix such that has a smaller condition number than .

Fixed-point iteration

In numerical analysis, fixed-point iteration is a method of computing fixed points of a function. More specifically, given a function defined on the real numbers with real values and given a point in the domain of , the fixed-point iteration is which gives rise to the sequence of iterated function applications which is hoped to converge to a point . If is continuous, then one can prove that the obtained is a fixed point of , i.e., More generally, the function can be defined on any metric space with values in that same space.

Jacobi method

In numerical linear algebra, the Jacobi method (a.k.a. the Jacobi iteration method) is an iterative algorithm for determining the solutions of a strictly diagonally dominant system of linear equations. Each diagonal element is solved for, and an approximate value is plugged in. The process is then iterated until it converges. This algorithm is a stripped-down version of the Jacobi transformation method of matrix diagonalization. The method is named after Carl Gustav Jacob Jacobi.

Related lectures (43)

Linear Systems: Convergence and Methods

Explores linear systems, convergence, and solving methods with a focus on CPU time and memory requirements.

Vectorization in Python: Efficient Computation with Numpy

Covers vectorization in Python using Numpy for efficient scientific computing, emphasizing the benefits of avoiding for loops and demonstrating practical applications.

Regression & Systemed Lineaires

Covers the principles of regression and linear systems, focusing on iterative methods.

Preconditioned Richardson Method

Covers the Preconditioned Richardson Method for solving linear systems and the impact of preconditioning on convergence.

Construction of an Iterative Method