# Talk:Fixed-point iteration

WikiProject Mathematics (Rated Start-class, Low-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 Start Class
 Low Importance
Field:  Analysis

The Numerical analysis article gives one example of fixed point iteration: ${\displaystyle x_{k+1}=(x_{k}^{2}-2)^{2}+x_{k}}$. This article can accommodate several examples and can illustrate them with graphics (maybe animations too?).

The example in the NA article can be complemented here by comparing it with the the superficially similar iteration: ${\displaystyle x_{k+1}=(x_{k}^{2}-2)+x_{k}}$.

The Fixed point (mathematics) article has a nice graphic of an iteration of sin(x) that --uhvpirate 04:55, 12 April 2007 (UTC)could be used to show that FPI can be used on many types of functions.

Examples of "what can go wrong" would also be nice.

Of course, examples are only part of the article.

--Jtir 14:13, 8 October 2006 (UTC)

I redirected this for now. Feel free to undo that if more example are added. Oleg Alexandrov (talk) 01:31, 9 October 2006 (UTC)

## "fixed point iteration" is a technique in theoretical computer science

(copied from User talk:Oleg Alexandrov) --Jtir 06:17, 9 October 2006 (UTC)
Actually "fixed point iteration" is a technique in theoretical computer science: definition by recursion is regarded as solution of a fixed point problem g = F(g) and iterates of F converge to the fixed point. This technique has various flavors: an order theoretic one and a metric space one. --CSTAR 06:06, 9 October 2006 (UTC)

## How are the iteration and the function related?

The third example has me wondering about the relation between the iteration and the function — why this function and not some other? Put another way, if someone gives you an iteration, can you say what function corresponds(?) to it?

"... - this function is not continuous at x=0, and in fact has no fixed points."
I'm not sure what the dash in the third example means. Can it be replaced with the word "because"? --Jtir 18:05, 10 October 2006 (UTC)

The function f and the iteration rule ${\displaystyle x_{n}\rightarrow x_{n+1}}$ are related by ${\displaystyle x_{n+1}=f(x_{n})}$. The point of the third example is to show that the condition that f is continuous is a necessary condition; if f is not continuous then the iterations of f can converge to a value that is not a fixed point of f. Gandalf61 14:39, 11 October 2006 (UTC)

## an example comparing FPI and Newton's method?

I tried computing the example xn+1 = sin xn on a handheld calculator. I was down to about 0.2 when I got tired of pressing the sin button. The Further properties section could give an example comparing the number of iterations needed to reach some value using FPI with the number needed using Newton's method. --Jtir 18:25, 10 October 2006 (UTC)

The Newton iteration is a fixed point iteration. Loisel 22:37, 10 October 2006 (UTC)

I took that distinction from the article, which reads:
• "Fixed point iteration is not always the best method of computing fixed points. For example, Newton's method ..."
--Jtir 22:47, 10 October 2006 (UTC)

Well obviously the article is missing a point. Loisel 00:24, 11 October 2006 (UTC)

You are right. Newton's iteration is a fixed point iteration. I fixed that in the article. Oleg Alexandrov (talk) 03:27, 11 October 2006 (UTC)
Sorry, I think I overwrote your text when I got an edit conflict. I had written up a bunch of stuff which seemed to moot your changes. Loisel 04:27, 11 October 2006 (UTC)

## example of the Babylonian method

Thanks for adding the Babylonian method to the examples. I noticed that it is the only example that does not give the iteration. --Jtir 17:03, 12 October 2006 (UTC)

## complex fixed points?

not sure if this is the right place to ask this but here goes anyway: obviously functions that don't cross f(x)=x shouldn't have fixed points, like ln(x). But you can use fixed point iteration on ln(x) to obtain an attractive complex fixed point. Does anyone have any information on complex fixed points?--uhvpirate 04:55, 12 April 2007 (UTC)

## Toilet flushing

I had some diarrhea today and when i flushed i wondered: Can the question of whether the water spirals clockwise or counter-clockwise finally be answered by using a fixed-point problem? —Preceding unsigned comment added by 130.85.237.88 (talk) 11:55, 14 November 2007 (UTC)

## Methodological Error

I have updated the "Fixed Point Iteration" page with "Methodological Error" section. I have added some points which would help to know if the iteration would converge or diverge.When we calculate the exact root of a given function we could plug in the root value into g'(r). After plugging in the value we run a check if the calculated value '<1 ' or '>1'. If |g'(r)| < 1 then the scheme converges else it is diverging. If there is divergence then the iteration should be terminated. Pooja929 21:09, 07 October 2010

I have removed the new section because it was mostly cut-and-pasted from the source; it was not consistent with the notation or flow of the rest of the article; and it was also unenecylopedic in tone - Wikipedia strongly discourages use of the second person ("we", "us") in articles, see WP:TONE. Also, I think there is a logical error in that section - the method it proposes for determining the convergence of an iterative process depends on knowing a root of the iterated function, which can in turn only be found if the iterative process converges. So there is some circular reasoning here.Gandalf61 (talk) 08:02, 8 October 2010 (UTC)

## Sample Code

A simple Matlab code has been added to the page. PoojaP 10:02 A.M, 07 November 2010

## When will the fixed-point iteration converge?

This article gives some examples about the fixed-point iteration converges and diverges respectively. But it does not state specifically about when the iteration would converge (thus it is the one we should use) and when the iteration diverges (so it won't give us the fixed-point). Of course there are a lot of fixed-point theorems that we can use to tell if it exists, but for the fixed-point iteration, since the function has to be continuous (mentioned in example 4), I think we can add the section about how to tell the iteration converges into this article. I noticed in the Properties section there is a theorem that we can use: If a function ${\displaystyle f}$ defined on the real line with real values is Lipschitz continuous with Lipschitz constant ${\displaystyle L<1}$, then this function has precisely one fixed point, and the fixed-point iteration converges towards that fixed point for any initial guess ${\displaystyle x_{0}}$.

I suggest to add this paragraph:

Not all iterations can arrive at a convergent fixed-point. Therefore, when constructing a fixed-point iteration, it is very important to make sure it converges. There are several fixed-point theorems to guarantee the existence of the fixed point, but since the iteration function is continuous, we can usually use the following theorem to test if an iteration converges or not: If a function ${\displaystyle f}$ defined on the real line with real values is Lipschitz continuous with Lipschitz constant ${\displaystyle L<1}$, then this function has precisely one fixed point, and the fixed-point iteration converges towards that fixed point for any initial guess ${\displaystyle x_{0}}$. One can generalize this to any metric space.

Proof of this theorem:

Since ${\displaystyle f}$ is Lipschitz continuous with Lipschitz constant ${\displaystyle L<1}$, then for the sequence ${\displaystyle \{x_{n},n=0,1,2...\}}$, we have:

${\displaystyle |x_{2}-x_{1}|=|f(x_{1})-f(x_{0})|\leq L|x_{1}-x_{0}|}$,

${\displaystyle |x_{3}-x_{2}|=|f(x_{2})-f(x_{1})|\leq L|x_{2}-x_{1}|}$,

${\displaystyle \cdots }$,

and

${\displaystyle |x_{n}-x_{n-1}|=|f(x_{n-1})-f(x_{n-2})|\leq L|x_{n-1}-x_{n-2}|}$.

Combining the above inequalities yields:

${\displaystyle |x_{n}-x_{n-1}|\leq L^{n-1}|x_{1}-x_{0}|}$.

Since ${\displaystyle L<1}$, ${\displaystyle L^{n-1}\rightarrow 0}$ as ${\displaystyle n\rightarrow \infty }$.

Therefore, we can show ${\displaystyle \{x_{n}\}}$ is a Cauchy sequence and it converges to a point ${\displaystyle x^{*}}$. This ${\displaystyle x^{*}}$ is apparently the fixed point for ${\displaystyle x^{*}=f(x^{*})}$. XueGong (talk) 01:26, 17 September 2012 (UTC)