Understanding iterative methods for solving $Ax=b$ and why they are iterative

Question

Firstly let me preface by saying I wasn't sure if this is the correct site to ask the question.

I am currently trying to gain a better understanding of where iterative methods to solve systems such as $Ax=b$ come from and I am missing what I think is quite a fundamental understanding.

The question is fairly simple. Often we want to solve the aforementioned system but it isn't practical for reasons of stability etc to compute an inverse of $A$ and directly solve $x=A^{-1}b$. So instead we aim to solve it using an iterative method by splitting $A$ into parts.

For example if we perform the following splitting of $A$, $A=S-T$, we could write

$$ Ax = b\\ Sx_{n+1}=Tx_n+b. $$

What I want to know is why does this now become an iterative system, other than the fact I have written it as such. For me personally I would not come up with the step to split $A$ into $S$ and $T$ and then re-write iteratively. I might split it and end up with a line such as

$$Sx=Tx+b$$

but I wouldn't make the jump myself to make it $iterative$. I know how to apply the methods and I get that by doing so we slowly improve our guess for $x$ each time until we converge to a solution. But why? I am just making it iterative because I have been taught that's what to do. I hope I managed to express what I don't get clearly but if I haven't please let me know.

Answer 1

Suppose we start with the root finding problem of $$H(x)=0,$$ if someone has come across the notion of fixed point theorem, it would be natural to ask the question of whether we can write something in the form of $$x=G(x).$$ of which considering iterations

$$x_{n+1}=G(x_n)$$ would converge.

Other question of interest include rate of convergence and where should we start the iteration.

This thinking has invented famous method such as Newton's method, steepest descent method, and Picard's method. Its impact is beyond solving linear system.

Answer 2

The general idea is that one chooses the decomposition in such a way that $Sx=b$ is easy to solve (and $S$ easy to construct from $A$). Common examples are that $S$ is the diagonal or lower triangular part of $A$ for diagonally dominant matrices or a sparse $LU$ approximation of a sparse $A$ as in the incomplete LU decomposition method.

Then insert the solution of $Sx_1=b$ into the original equation to get $Ax_1=b+r_1$ with some error or residual vector $r_1$. One would expect that $\|r_1\|<\|b\|$. Now the problem is reduced to solving $Ad_1=-r_1$, as then $x=x_1+d_1$ is the exact solution. However, the same arguments against a direct solution as in the original problem apply, so use an approximate solution $Sd_1=-r_1$ to get the better approximation $x_2=x_1+d_1$. Then iterate until the residual is sufficiently small.