Iterative methods#
Guass Elimination / LU decomposition are direct solvers in that they solve systems in a fixed number of operations. If we could calculate in infinite precision these answers would be exact. Direct solvers generally scale ~\(O(n^3)\) and are therefore impractical for large systems.
We will now talk about iterative / indirect methods which start with an initial guess and iterate (hopefully) towards a solution. Each iteration is typically faster and more memory efficient than direct solvers, but convergence is only guaranteed under certain limited circumstances. Even then, the rate of convergence can still make these techniques impractical.
Iterative techniques have some useful properties:
They are self-correcting in that roundoff (or arithmatic) errors are corrected through further cycles.
They are more conducive to sparse matrix storage.
Only the solution vector \(x\) is altered during these computations. Neither the matrix (nor anything we will do to it) is not altered during any of these steps!
In fact, there are a class of solvers called matrix free solvers that avoid the explicit writing of \(A\) entirely… This is useful if the matrix product \(Ax\) can be calculated in a more effective manner such that we don’t bother writing out and storing A$!
Each iteration will (hopefully) improve the answer asymptotically, so we estimate the error and say when it is stopped getting better. As discussed with error analysis, this involves defining tolerances for computation.
Iterative approach#
Consider: What does it mean for a vector \(x\) to satisfy \(Ax=b\)?
-> All the elements in \(x\) must be consistent.
What if one element was not consistent?
-> We could solve for it based on the others!
Big picture algorithm#
Start with a guess
For each iterative step, identify a single element in \(x\), make it consistent with all the others.
Check how well the guess solves the linear system
Repeat (possibly updating a parameter first)
Quantifying convergence#
The system has converged when \(Ax=b\). Define the residual vector, \(R = Ax-b\) such that when \(R\rightarrow 0\) (the system is converged).
Let’s use the norm (some measure of magnitude) of \(R\) and say the system has converged when \(||R|| \lt tolerance\).
Should we use absolute tolerance or relative?
What other tolerance could we imagine using? (Hint: We are actually interested \(x\)…)