I'm in AS level and we've done numerical methods: iteration( i didn't know it was called fixed point).I understand how it sometimes converges or diverges by looking at it done practically on a graph and can solve the questions I am given.I'm trying to understood why this method actually works and why it fails, and also why my chosen starting value is limited to certain ranges.
The principle of fixed point iteration is that we convert the problem of finding root for $f(x)=0$ to an iterative method by manipulating the equation so that we can rewrite it as $x=g(x)$. Then we use the iterative procedure $x_{i+1} =g(x_i)$.My first question is why is the condition for convergence of the fixed‐point iteration that the derivative of g is smaller than 1 in absolute magnitude
You should know from your AS Mathematics course that $g'(x)\approx \frac{g(x+h)-g(x)}{h}$ when $h$ is small. The university mathematicians will want to talk about limits and differentiability tests, but for your purpose this is enough for now. This can be rearranged to give $g(x+h)\approx g(x)+hg'(x)$ (still provided $h$ is small).
The iteration method you describe takes a function in the form $f(x)=0$ and rearranges into the form $g(x)=x$. There is at least one value of $x$ that will be the root to your equation. Let's call this value $a$. $a$ has the important property that $g(a)=a$.
You start with an initial guess $x_0$ and find $x_1=g(x_0)$ in the hope that $x_1$ is closer to $a$ than $x_0$ was. You then repeat the process.
Let's consider the point where you have an estimate $x_n$. It isn't the exact value you are hoping to get, so there is some small "error" in your estimate. We don't know $a$ but if we did, we could work out the error by finding the difference between our estimate and the true value.
$\epsilon_n=x_n-a$
or $x_n=a+\epsilon_n$
When we put $x_n$ into the function we are working out $x_{n+1}=g(x_n)$
So $a+\epsilon_{n+1}=g(a+\epsilon_n)$
We can now use the result from earlier to say that
$a+\epsilon_{n+1}\approx g(a)+\epsilon_ng'(a)$
and we can use the fact that $g(a)=a$ to give:
$a+\epsilon_{n+1}\approx a+\epsilon_ng'(a)$
$\Rightarrow \epsilon_{n+1}\approx \epsilon_ng'(a)$
What this says is that the new error will be the old error multiplied by the value of $g'(a)$ and as long as $|g'(a)|<1$, then the new error will be smaller in magnitude than the old error. That means that the errors keep decreasing - or the estimate converges towards the actual value.
Of course, if $|g'(a)|>1$ then the errors are increasing... bad news!
This approach also explains why you need to start fairly close to the true value. If you don't, the approximation we are depending on will not hold.