Re: Convergence of an iterative sequence

Ooops, I forgot to mention that -1<f'(x)<0. In that case your
counterexamples do not apply. Is there a "standard" way to prove the
convergence of these kind of recursions?

I tried the following: defining

z(k) = (x_2k,x_{2k-1}),

the recursion can be written in vector form

z(k) = g(z(k-1))

for some g. I can prove that the eigenvalues of the Jacobian dz(k)/
dz(k-1) have module less than unity. Is this a proof of convergence
near the fixed point? How to prove convergence from any starting
point?

Thx,

Jesús Cid


On 1 abr, 00:50, Robert Israel <isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
"jcidsue...@xxxxxxxxx" <jcidsue...@xxxxxxxxx> writes:
Consider the recursive relation,

x_k =3D f(x_{k-1}) + f(x_{k-2})

where f is non-negative, strictly decreasing and concave (f''>0) with

You mean convex.

f(0)=3D1 and f(inf)=3D0.

Also, x_0=3D0

I would need to know if this always converges to the fixed point
x=3D2f(x), and why. How to solve this kind of problems? Any help would
be appreciated.

Thanks in advance,

Jes=FAs Cid.

No, it doesn't always.

Let p be the fixed point, and write y_k = x_k - p. Let f'(p) = -m.
Linearizing, for x_{k-1} and x_{k-2} near p we have

y_k ~= -m y_{k-1} - m y_{k-2}

If m > 1, the polynomial z^2 + m z + m has roots with absolute value > 1,
which implies the fixed point is unstable. And then for most initial
conditions we should not get convergence to a fixed point. Try
e.g. f(x) = exp(-kx) where k > e^2.
--
Robert Israel isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

.