8
$\begingroup$

I appologize in advance if this question is silly. I need to compute the root of

\begin{equation} u -f(u) =0 \end{equation}

Where $u$ is a real vector and $f(u)$ is a real-vector valued function. I started with Newton's method (which worked), but then realized a much simpler method would be an iterative solution

\begin{equation} u_{i+1} = f(u_{i}) \end{equation}

This is much quicker and apparently as accurate/stable as Newton's method.

Now the questions:

  • Is this the correct approach or should I use a different method?
  • Is there anything that can be said about it's convergence rate, stability, acc, etc?
  • Is it globally convergent?

Thank you all in advance for the attention.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ This is known as fixed point iteration. I am not well-versed on the subject but at the very least it should give you some new words to throw at google. If I remember correctly, fixed points appear for a wide variety of function with a wide variety of starting points. $\endgroup$ – Godric Seer Aug 17 '12 at 0:38
  • 1
    $\begingroup$ What's your $f(u)$? Newton's method is often faster than fixed point iteration. $\endgroup$ – Bill Barth Aug 17 '12 at 2:44
  • 4
    $\begingroup$ Your observed convergence depends heavily on the functional form of $f(\cdot)$. Furthermore, if $f(u) = u - (\nabla g)^{-1} g(u)$, then the iteration $u_{i+1} = f(u_i)$ is Newton iteration on $g(u) = 0$. $\endgroup$ – Jed Brown Aug 17 '12 at 3:06
7
$\begingroup$

If $q:=|f'(x^*)|<1$, where $x^*$ is the solution, the fixed point iteration you talk about is locally linearly convergent with convergence rate $q$. Thus if $q$ is small or zero, the method is competitive with Newton's method.

Far away from the solution, convergence is difficult to predict in the absence of global information (such as a Lipschitz constant $<1$, which produces a contraction).

Improve this answer
$\endgroup$
5
$\begingroup$

The Feigenbaum fractal is a good example of how strange fixpoint iteration can be:

http://en.wikipedia.org/wiki/Feigenbaum_fractal

http://en.wikipedia.org/wiki/File:Logistic_Bifurcation_map_High_Resolution.png

The second link plots the behavior of fixpoint iteration applied to the logistic map as one of the parameters varies. For certain values it converges, though only linearly. For other values it converges to a cycle of varying length. For yet another class of values, it behaves completely chaotically.

In other words, the behavior of fixpoint iteration depends entirely on the function in question. Even functions that look similar may exhibit radially different behavior.

Note: As Jed points out, Newton iteration can be equally weird.

Improve this answer
$\endgroup$
1
  • $\begingroup$ To be fair, many popular fractals are the Julia sets of Newton iteration on a simple equation. $\endgroup$ – Jed Brown Aug 17 '12 at 3:03
4
$\begingroup$

The Banach fixed-point theorem describes the standard situation when a fixed-point iteration is globally convergent. Especially the uniqueness part of the theorem indicates that you can only expect local convergence if the solution is not unique.

Most situations of local convergence can be explained by this theorem, at least in theory. This is even true for the convergence occurring in some of the fractals mentioned above. It's just that the theorem has to be applied to $f^n=f\circ \ldots\circ f$ instead of $f$ at some basins of attraction.

Improve this answer
$\endgroup$
2
$\begingroup$

You may consider useful this reference: A Homotopy for Solving Large, Sparse and Structured Fixed Point Problems. R. Saigal. Mathematics of Operations Research, Vol. 8, No. 4 (Nov., 1983), pp. 557-578.

Improve this answer
$\endgroup$
1
$\begingroup$

This method is correct and it is called "Successive Substitution". Please, look at page 189 of this reference for details.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.