1
$\begingroup$

I don't quite get why things are rearranged the way they are when trying to get an equation to be used in fixed point iteration. For example,

$x^3+2x+5=0$

could be rearranged to give

$\:x=-\frac{5}{x^2+2}\:or\:x=-\sqrt[3]{2x+5}$

But apparently not

$x=-\frac{x^3+5}{2}$.

Why so?

$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

The problem is that you generally want the fixed point iteration mapping to be contractive, at least in a neighborhood of the fixed point. Otherwise you start with a small error and end up with a larger error.

The situation is easier to see in a case where the exact solution of the equation is easily constructed. Look at something like $x^2-x-12=0$, and you're trying to find the root $x=4$. If you use $x=x^2-12$, the problem is that although indeed $4=4^2-12$ (i.e. the desired solution is a fixed point of the mapping), if you have an $x$ close to $4$ instead, $x^2-12$ is generally further away from $4$ than $x$ was. For example $3.9^2-12=3.21$.

The standard way to check this is to compute the absolute value of the derivative of the fixed point function at the fixed point, which in this example is $8$. If it is larger than $1$, then the mapping is not contractive near the fixed point, so the iteration (usually) does not converge.

$\endgroup$
2
  • $\begingroup$ So does this mean that I can just move the $x$ term to one side, isolate $x$ and use that as a function as long as the derivative of the function at the fixed point is $-1<x<1$? Because in textbooks they seem to never just get the $x$ term on its own immediately, they usually just factorise $x$ out then rearrange or take a cube root. $\endgroup$
    – Chx
    Commented Aug 6, 2018 at 0:50
  • 1
    $\begingroup$ @CheksNweze Yes, that's right. There is nothing mathematically incorrect about isolating $x$ from the linear term rather than, say, the leading order term of a polynomial equation. It just often leads to non-contractive mappings in practice. $\endgroup$
    – Ian
    Commented Aug 6, 2018 at 0:59
1
$\begingroup$

The key idea is to rewrite $f(x)=0$ in the form $x=\phi(x)$ such that $\vert \phi'(x)\vert <1$ for some $x$ in the vicinity of the root.

enter image description here

The picture above depicts the iteration process $x_{n+1}=\phi(x_n)$ for $n=0,1,2,...$ which guarantees the convergence as $\vert \phi'(x)\vert <1$ as the movement along the cobweb cycle indeed takes you towards the point of intersection of the curves.

You can easily see by drawing the graph that the iteration may diverge (this time the cobweb cycle will take you away from the point of intersection of the curves) rather if we relax the condition $\vert \phi'(x)\vert <1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .