non linear recurrence equations
in [Math]
|
From: Panita Gomez on 11 Jul 2010 19:40 On 11 juil, 17:10, Robert Israel <isr...(a)math.MyUniversitysInitials.ca> wrote: > Panita Gomez <gatitablan...(a)gmail.com> writes: > > On 11 juil, 13:39, Panita Gomez <gatitablan...(a)gmail.com> wrote: > > > On 10 juil, 19:54, Ray Vickson <RGVick...(a)shaw.ca> wrote: > > > > > On Jul 10, 9:17=A0am, Panita Gomez <gatitablan...(a)gmail.com> wrote: > > > > > > I'm serching to solve this non linear recurrence equations of this > > > > > form with no hope :(. > > > > > Anyone has an idea how to solve this kind of equations? > > > > > > a+ b X_{i-1} +c X_{i} + d X_{i+1} + e X_{i-1} X_{i+1}=3D0 > > > > > > without the last term, I can use the guassian elimination method to > > > > > solve it. But when the last term appear I don't know how to deal with > > > > > the multiplication between two reccurence anymore. help appreciated. > > > > > Thank you > > > > > Panita. > > > > > If you know X_0 and X_1 you can get all the X_i: re-write the > > > > recursion as > > > > X_{i+1} =3D -[a + b*X_{i-1}+c*X_i]/[d + e*X_{i-1}]. You can get X_2, > > > > then X_3, ... . > > > > > R.G. Vickson > > > > Dear Ray, > > > Thank you very much for your help. That cheer me up that it is > > > possible to solve the equations. However, I forgot to precise at the > > > beginning that I do not know the two first terms. I only the first > > > term and the last term > > > a[0]=3D0 and a[n]=3D0.5. > > > In the =A0case that we know the first and the last recurrence, is it > > > still possible to solve the rest of the terms? Thank you very much > > > Actually, I calculated it wrong. I know only the first and the last > > recurrence > > a[0]=3D0 and a[n+1]=3D0 > > the other terms are unknown :( > > Then it's very unlikely that you could get a closed-form solution. You > could try expressing the a[j] in terms of the unknown a[1], and solving > the resulting equation a[n+1] = 0 for a[n], but this will require solving a > (probably irreducible) high-degree polynomial. > -- > Robert Israel isr...(a)math.MyUniversitysInitials.ca > Department of Mathematics http://www.math.ubc.ca/~israel > University of British Columbia Vancouver, BC, Canada Dear Robert, I tried to calculate it for n<5, I can find a set of solutions. But as n grows, it becomes really complicated :-(. I guess I'll have to find a way to optimise this. Thank you very much for your help.
From: Ray Vickson on 12 Jul 2010 06:05 On Jul 11, 4:40 pm, Panita Gomez <gatitablan...(a)gmail.com> wrote: > On 11 juil, 17:10, Robert Israel > > > > <isr...(a)math.MyUniversitysInitials.ca> wrote: > > Panita Gomez <gatitablan...(a)gmail.com> writes: > > > On 11 juil, 13:39, Panita Gomez <gatitablan...(a)gmail.com> wrote: > > > > On 10 juil, 19:54, Ray Vickson <RGVick...(a)shaw.ca> wrote: > > > > > > On Jul 10, 9:17=A0am, Panita Gomez <gatitablan...(a)gmail.com> wrote: > > > > > > > I'm serching to solve this non linear recurrence equations of this > > > > > > form with no hope :(. > > > > > > Anyone has an idea how to solve this kind of equations? > > > > > > > a+ b X_{i-1} +c X_{i} + d X_{i+1} + e X_{i-1} X_{i+1}=3D0 > > > > > > > without the last term, I can use the guassian elimination method to > > > > > > solve it. But when the last term appear I don't know how to deal with > > > > > > the multiplication between two reccurence anymore. help appreciated. > > > > > > Thank you > > > > > > Panita. > > > > > > If you know X_0 and X_1 you can get all the X_i: re-write the > > > > > recursion as > > > > > X_{i+1} =3D -[a + b*X_{i-1}+c*X_i]/[d + e*X_{i-1}]. You can get X_2, > > > > > then X_3, ... . > > > > > > R.G. Vickson > > > > > Dear Ray, > > > > Thank you very much for your help. That cheer me up that it is > > > > possible to solve the equations. However, I forgot to precise at the > > > > beginning that I do not know the two first terms. I only the first > > > > term and the last term > > > > a[0]=3D0 and a[n]=3D0.5. > > > > In the =A0case that we know the first and the last recurrence, is it > > > > still possible to solve the rest of the terms? Thank you very much > > > > Actually, I calculated it wrong. I know only the first and the last > > > recurrence > > > a[0]=3D0 and a[n+1]=3D0 > > > the other terms are unknown :( > > > Then it's very unlikely that you could get a closed-form solution. You > > could try expressing the a[j] in terms of the unknown a[1], and solving > > the resulting equation a[n+1] = 0 for a[n], but this will require solving a > > (probably irreducible) high-degree polynomial. > > -- > > Robert Israel isr...(a)math.MyUniversitysInitials.ca > > Department of Mathematics http://www.math.ubc.ca/~israel > > University of British Columbia Vancouver, BC, Canada > > Dear Robert, > I tried to calculate it for n<5, I can find a set of solutions. But as > n grows, it becomes really complicated :-(. I guess I'll have to find > a way to optimise this. Thank you very much for your help. This is true. However, in a purely numerical example you can try something like Newton's method in order to try to make F = X[n+1] = 0. Regard the X[i] as functions of r = X[i] (holding X[0]=0); that is, look at X[i](r), obtained from the recursion X[i+1](r) = -[a + b*X[i-1](r)+c*X[i](r)]/[d+e*X{i-1](r)]. If you assign a numerical value to r, you can quickly get F(r) = X[n+1] (r) even for large n (although you might need to worry about effects of roundoff errors in the recursion). Typically you will not have F(r) near 0, so must try a new value of r. You could use a gradient-based method to help with this, because we can also compute recursively the derivatives dX[i](r)/dr for i <= n+1. If we let D[i](r) = dX[i](r)/dr, we see from the recursion that D[i+1](r) = {-b*d*D[i-1](r) - c*d*D[i](r) - c*e*D[i](r)*X[i-1](r) + a*e*D[i-1](r) + c*e*D[i-1](r)*X[i](r) }/[d + e*X[i-1](r)]^2, so while iterating to get X[i+1](r) we can also iterate to get D[i+1] (r) (starting from D[0](r) = 0 and D[1](r) = 1). Again, though, roundoff errors might be a serious issue. A Newton-type step would be to use the values of F(r) and dF(r)/dr to suggest a better value of r that one hopes is nearer the root of F(r) = 0. Best of luck. R.G. Vickson
From: Alois Steindl on 12 Jul 2010 06:06 Panita Gomez <gatitablanca3(a)gmail.com> writes: > > Actually, I calculated it wrong. I know only the first and the last > recurrence > a[0]=0 and a[n+1]=0 > the other terms are unknown :( Hello, it is hard to guess from your formulation of the question, where to begin with the answer. From the above it seems that a==0 should yield a solution. Otherwise it looks as if your recurrence equation is obtained by discretizing a differential equation. You try to solve a boundary value problem. Since the equation is nonlinear, it seems that analytic methods become quite complicated really soon. You might try to apply methods from discrete dynamical systems: Search for periodic solutions, investigate their stability, calculate invariant manifolds, ... What's the context of your problem? Research, homework, ...? What are you assumed to know? Alois
From: Alois Steindl on 12 Jul 2010 07:59 Panita Gomez <gatitablanca3(a)gmail.com> writes: > > Dear Robert, > I tried to calculate it for n<5, I can find a set of solutions. But as > n grows, it becomes really complicated :-(. I guess I'll have to find > a way to optimise this. Thank you very much for your help. Hello, it is hard to guess from your formulation of the question, where to begin with the answer. It looks as if your recurrence equation is obtained by discretizing some differential equation. You try to solve a boundary value problem. Since the equation is nonlinear, it seems that analytic methods become quite complicated really soon. You might try to apply methods from discrete dynamical systems: Search for periodic solutions, investigate their stability, calculate invariant manifolds, ... What's the context of your problem? Research, homework, ...? What are you assumed to know? Alois
From: OwlHoot on 13 Jul 2010 12:44 On Jul 10, 5:17 pm, Panita Gomez <gatitablan...(a)gmail.com> wrote: > > I'm serching to solve this non linear recurrence equations of this > form with no hope :(. > Anyone has an idea how to solve this kind of equations? > > a+ b X_{i-1} +c X_{i} + d X_{i+1} + e X_{i-1} X_{i+1}=0 > > without the last term, I can use the guassian elimination method to > solve it. But when the last term appear I don't know how to deal with > the multiplication between two reccurence anymore. help appreciated. If e != 0 you can simplify it a bit by dividing the other coefficients by e and (symbolically) taking e = 1. (This might not be a good idea in practice, if you are working on it numerically, for example if e is very small compared with the other coefficients.) Assuming e = 1, you can factor it as follows: (X_{i-1} + d) (X_{i+1} + b) + c X_{i} + a - b d = 0 In this if c = 0 then you effectively have two separate recurrences of opposite parity, each a continued fraction. Otherwise you can divide throughout by c^2 and then taking X_i = c Y_i gives: (Y_{i-1} + A) (Y_{i+1} + B} + (Y_i + C) = 0 where A, B, C are rational functions of a, b, c, d. Next defining Z_i = Y_i + B gives the following with C', A' = C - B, A - B : Z_{i+1} = (Z_i + C') / (Z_i + A') That looks a bit neater, and you could probably plot convergence rates on the "0AC" plane and get a nice swirly fractal pattern ;-) Again, it represents a continued fraction, because one can write: Z_{i+1} = 1 + (C' - A') / Z_i + A' This can be written explicitly as a continued fraction in the following form with u, v = C' - A', 1 + A' : t = 1 + u ----- v + u ----- v + u ---- v + .. The limit, if any, of this can easily be found by solving the quadratic obtained from t - 1 = u / v + t - 1. But that doesn't help with the convergents. So I suggest you flick through a book on analytic continued fractions and try and find one like this. Cheers John Ramsden
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 Prev: Time change of Brownian motion Next: Stupid Italiian Math |