iterative methods (CG, GMRES) do: solve Ax=b without explicitly inverting A

Iterative methods solve Ax=b without explicitly inverting A

Iterative methods generate a sequence of improving approximate solutions for problems like Ax=b, relying on previous approximations to derive the next one. These methods are used when direct methods, such as Gaussian elimination, are not feasible or practical. They are particularly useful for large or sparse systems where direct methods would be computationally expensive.

Example

Consider solving Ax=b using the Conjugate Gradient (CG) method. Starting with an initial guess x0, the CG method iteratively refines this guess by minimizing the residual r_i = b - Ax_i along conjugate directions until the solution converges to a satisfactory level of accuracy.

Remember this

Understanding iterative methods is crucial for efficiently solving large-scale linear systems that are impractical to handle with direct methods, especially when dealing with sparse matrices.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

second-order methods (Newton's) converge faster but are expensive: O(n³) per step

Second-order methods converge faster due to quadratic convergence but are expensive due to O(n³) per iteration

Finite element method

Runge-Kutta method improves Euler by providing higher-order accuracy with k₁,k₂,k₃,k₄

natural gradient descent does: preconditions with inverse Fisher matrix

Ever wondered how to climb a steep mountain without measuring every step?

Euler method

Euler method approximates ODE solution with y_{n+1} = y_n + h·f(y_n)

Master theorem (analysis of algorithms)

Master theorem solves T(n) = aT(n/b) + f(n) recurrences

Eigenvalues and eigenvectors

Eigenvectors are unchanged in direction by a linear transformation

Swipe through 100 ML concepts daily

Open Pocket Polymath