Finding a Limit by Iterating a Function
Date: 04/21/2004 at 21:49:25 From: Matan Subject: Determine the limit of f^n(x) for x > 0 Given: f(x) = 2x/(x + 1) 2 3 2 n n-1 Define f (x) = f(f(x)), f (x) = f(f (x)),...,f (x) = f(f (x)) n Determine the limit as n approaches infinity of f (x) for x > 0. I thought I should plug in the given f(x) into the first couple to see if I noticed a pattern, and then use my limit taking knowledge to take the limit. Things got very confusing at that point!
Date: 04/22/2004 at 09:28:41 From: Doctor Vogler Subject: Re: Determine the limit of f^n(x) for x > 0 Hi Matan, That's a very good question. What you are doing is called "iterating" the function f(x). In general, this is not a simple or easy thing to do, and it is where fractals (the Mandelbrot and Julia sets) come from. However, a rational function of degree 1 (which is what you have) is the only kind of rational function for which we can give an *explicit* formula for f^n(x). The trick lies in looking for the fixed points. Basically, we figure that if f^n(x) is going to approach a limit, and that limit is y, then we would expect f of something really close to y to be even closer to y, right? So we should also expect f(y) = y. So let's solve that equation: 2y/(y+1) = y 2y = y^2 + y 0 = y^2 - y 0 = y(y - 1) which has two solutions, namely 0 and 1. (You don't always get integers, but I expect someone chose this problem for you so that you would get integers.) Now the secret is to move these points to 0 and infinity. So we use a transformation: h(x) = x/(x - 1) which takes 0 to 0 and 1 to infinity. This is what I mean by that: We define a completely new function by g(x) = h(f(h^-1(x))) and it so happens (in this case) that h-inverse (h^-1) equals h (this doesn't always happen either). So then f(h(x)) = f(x/(x - 1)) = 2[x/(x - 1)]/([x/(x - 1)] + 1) = 2x/(x + x - 1) = 2x/(2x - 1) and g(x) = h(f(h(x))) = h(2x/(2x - 1)) = [2x/(2x - 1)]/([2x/(2x - 1)] - 1) = 2x/(2x - (2x - 1)) = 2x You see, we will always get a function in a very simple form when we transform the fixed points to 0 and infinity. Now we know what g^n(x) is, right? g^n(x) = (2^n)x Well, notice that g(x) = h(f(h^-1(x))) also implies that g^n(x) = h(f^n(h^-1(x))). Do you see why? (Induction will prove this.) It also means that h^-1(g^n(h(x))) = f^n(x), so that f^n(x) = h^-1(2^n * h(x)) = h^-1(2^n * x/(x - 1)) = [2^n * x/(x - 1)]/([2^n * x/(x - 1)] - 1) = (2^n * x)/(2^n * x - (x - 1)) = (2^n * x)/((2^n - 1)*x + 1) and now you have an explicit formula for f^n(x), which you might have discovered by experimenting, although this technique that I described will work for any rational function of degree 1, and which you could easily prove by induction (if we had come up with this formula by some less mathematical means), and whose limit you can now easily take, especially if you write it as f^n(x) = 1/[1 - 2^(-n)*(x - 1)/x]. Of course, we already figured out right from the beginning that the limit had to be either 0 or 1. In fact, if you take the limit as n goes to negative infinity (which is called backwards iterating), then you will get 0. If you have other questions or need more help, please write back, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.