# Solving a nonlinear recurrence relation

All of that being said, while trying to come up with a computational algorithm to solve a particular nonlinear PDE, using the method of finite differences, I ran into a nonlinear recursion.

The actual problem I'm considering is 5-dimensional, but if I fix all but one of the indeces (which would require constructing function values over the grid in 5 nested "for" loops), then I can reduce myself to the following recursion (or actually, a system of 5 such recursions):

$(a_{n+1})^2 - a_{n+1} + a_{n} = 0$

I haven't read a lot in the theory of nonlinear recurrence relations, so I'm not really aware of any simple solutions to this. Assuming that $a_0\neq 0$ is given, then I can type this into Wolfram Alpha, but before implementing this particular method into my algorithm, a more explicit form would be useful.

The second question is one of computational stability (as this would require large numbers of iterations in order to construct solutions in space-time).

Admittedly, this was a first approach to this problem that seemed like the most obvious to try, since it was the simplest to formulate, and I'd like to try to follow it through to see what, if any, insight into my problem I can gain from it. That being said, if there are any other numerical methods which are better suited to nonlinear PDE's, I'm would appreciate any suggestions.

(I apologize ahead of time if this particular recurrence relation has appeared here before but after doing a quick search, I didn't find anything, so I figured I'd ask. Also, my apologies if the tags are wrong, but I am not totally certain where this belongs.)

-

Two problems are: 1) if you solve the equation for $a_{n+1}$ you get $a_{n+1}=\frac 12 (1 \pm \sqrt{1-4a_n})$. If $a_n \gt \frac 14$ you go off into the complex plane. Maybe that's not so bad. 2) you have two values for $a_{n+1}$ that satisfy the equation-which do you pick? Your sequence is not well defined.

-
That was actually my fear. The original recurrence was $$(u_{n+1}- u_n)^2 - u_{n+1} = u_{n-1} - 2 u_n$$ but I'm not sure if that actually would change anything. – Nicholas Stull Mar 1 '13 at 4:20
@NicholasStull: It is still quadratic in $u_{n+1}$ and therefore has two solutions. Do you have a way to pick the right one? Something about the original problem may give you that. marty cohen's answer about $a_n$ (in the original question) going to zero is hopeful-maybe that is the behavior you want. – Ross Millikan Mar 1 '13 at 4:26
Unfortunately, I don't think there is a way to pick the right one. The fact that it is bounded and goes to $0$ is perhaps useful, but does not provide quite enough, unless the difference between the two roots is extremely small. That being said, it seems that it might be prudent to abandon this method and try to find something more suited to nonlinear problems. – Nicholas Stull Mar 1 '13 at 4:33
All of this being said, thank you for your insight. – Nicholas Stull Mar 1 '13 at 4:34

As a quick hack, complete the square to get $(a_{n+1}-1/2)^2 = a_{n+1}^2-a_{n+1}+1/4 = -a_n+1/4 = -(a_n-1/2)-1/2+1/4 = -(a_n-1/2)-1/4$.

Letting $b_n = a_n-1/2$, this becomes $b_{n+1}^2 = -b_n-1/4$.

If any $b_n > -1/4$, this cannot hold in the reals.

If $b_n \to L$, $L^2+L+1/4 = 0$ or $(L+1/2)^2 = 0$ or $L=-1/2$.

This seems to imply that $a_n \to 0$. Is this what you had in mind?

-
This much, I was able to figure out rather quickly. Basically, I can prove that the sequence goes to zero (albeit rather slowly). But now that there is a question of well-definedness, as brought up by Ross, I think I will have to look for a different method. – Nicholas Stull Mar 1 '13 at 4:24