http://www.mathworks.com/matlabcentral/newsreader/view_thread/245824
MATLAB Central Newsreader  2 dimensional recurrence equation
Feed for thread: 2 dimensional recurrence equation
enus
©19942014 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Tue, 03 Mar 2009 20:57:23 +0000
2 dimensional recurrence equation
http://www.mathworks.com/matlabcentral/newsreader/view_thread/245824#632242
g.n.mueller@gmail.com
Hi<br>
<br>
Does anyone know how to solve 2 dim. recurrence equations in Matlab?<br>
I have a table and I can fill it in by hand but I want a closed form<br>
for the<br>
entry (m,n). However, trying to derive the closed form has not led to<br>
any<br>
results yet...<br>
Thanks<br>
<br>
Gloria

Tue, 03 Mar 2009 21:30:24 +0000
Re: 2 dimensional recurrence equation
http://www.mathworks.com/matlabcentral/newsreader/view_thread/245824#632254
Matt Fig
Not all recursion relations are reducible to a closed form equation. If your relation is not linear, you may very well not be able to find a closed form equation for the nth term.<br>
<br>
<a href="http://mathworld.wolfram.com/RecurrenceEquation.html">http://mathworld.wolfram.com/RecurrenceEquation.html</a><br>
<br>
<br>
<br>
<br>
<br>
<br>
[kbQM[a,kkWrkQkkNrEeQ`ZN\XT[X`MQY9yMkM`UU[T1MYS\[MOM[&akOTZ

Wed, 04 Mar 2009 06:30:58 +0000
Re: 2 dimensional recurrence equation
http://www.mathworks.com/matlabcentral/newsreader/view_thread/245824#632347
g.n.mueller@gmail.com
<br>
<br>
Matt Fig schrieb:<br>
> Not all recursion relations are reducible to a closed form equation. If your relation is not linear, you may very well not be able to find a closed form equation for the nth term.<br>
><br>
> <a href="http://mathworld.wolfram.com/RecurrenceEquation.html">http://mathworld.wolfram.com/RecurrenceEquation.html</a><br>
><br>
<br>
<br>
Hi Matt<br>
<br>
Thanks. And assuming that it is linear  how can I "type it into<br>
Matlab"?<br>
Or are you saying that because termination is not guaranteed Matlab<br>
can't solve it?<br>
Thanks,<br>
<br>
Gloria

Wed, 04 Mar 2009 08:44:01 +0000
Re: 2 dimensional recurrence equation
http://www.mathworks.com/matlabcentral/newsreader/view_thread/245824#632364
Roger Stafford
g.n.mueller@gmail.com wrote in message <481501c7ae484c2fa9d0dc374434d1b0@a12g2000yqm.googlegroups.com>...<br>
> .......<br>
> Thanks. And assuming that it is linear  how can I "type it into<br>
> Matlab"?<br>
> .......<br>
<br>
Much depends on the form of your twodimensional iteration equations and the boundary values. If, for example, the iteration is linear of the form<br>
<br>
f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)<br>
<br>
where a and b are certain known constants, and if f(m,0) and f(0,n) are all equal to some constant for all m and n, then the general solution for the m,nth value is of the form<br>
<br>
f(m,n) = A*x^m + B*y^n<br>
<br>
where x and y can be determined uniquely from the iteration equation and the constants A and B from the boundary conditions at m=0 and n=0.<br>
<br>
However, that is just a wild guess. You may be faced with something entirely different.<br>
<br>
Roger Stafford

Wed, 04 Mar 2009 12:09:51 +0000
Re: 2 dimensional recurrence equation
http://www.mathworks.com/matlabcentral/newsreader/view_thread/245824#632411
g.n.mueller@gmail.com
<br>
<br>
Roger Stafford schrieb:<br>
> g.n.mueller@gmail.com wrote in message <481501c7ae484c2fa9d0dc374434d1b0@a12g2000yqm.googlegroups.com>...<br>
> > .......<br>
> > Thanks. And assuming that it is linear  how can I "type it into<br>
> > Matlab"?<br>
> > .......<br>
><br>
> Much depends on the form of your twodimensional iteration equations and the boundary values. If, for example, the iteration is linear of the form<br>
><br>
> f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)<br>
><br>
> where a and b are certain known constants, and if f(m,0) and f(0,n) are all equal to some constant for all m and n, then the general solution for the m,nth value is of the form<br>
><br>
> f(m,n) = A*x^m + B*y^n<br>
><br>
> where x and y can be determined uniquely from the iteration equation and the constants A and B from the boundary conditions at m=0 and n=0.<br>
><br>
> However, that is just a wild guess. You may be faced with something entirely different.<br>
><br>
> Roger Stafford<br>
<br>
<br>
<br>
<br>
Hi Roger<br>
<br>
<br>
Yes, I have f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)<br>
<br>
I know that for 1 dim. in MAPLE the method used to solve it is called<br>
rsolve and the syntax would be sth. like this:<br>
rsolve( {f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n), f(0,0)=10}, f(m,n))<br>
<br>
However, Maple fails to solve recurrence relations with more than 1<br>
dim.<br>
So my question here, now given that Matlab can solve > dim:<br>
what is the corresponding code in Matlab in order to get f(m,n) ?<br>
Thanks for your help!<br>
<br>
Gloria

Wed, 04 Mar 2009 13:07:01 +0000
Re: 2 dimensional recurrence equation
http://www.mathworks.com/matlabcentral/newsreader/view_thread/245824#632428
John D'Errico
g.n.mueller@gmail.com wrote in message <00fd426ed5f34745b683ff04841036a5@e18g2000yqo.googlegroups.com>...<br>
> <br>
> <br>
> Roger Stafford schrieb:<br>
> > g.n.mueller@gmail.com wrote in message <481501c7ae484c2fa9d0dc374434d1b0@a12g2000yqm.googlegroups.com>...<br>
> > > .......<br>
> > > Thanks. And assuming that it is linear  how can I "type it into<br>
> > > Matlab"?<br>
> > > .......<br>
> ><br>
> > Much depends on the form of your twodimensional iteration equations and the boundary values. If, for example, the iteration is linear of the form<br>
> ><br>
> > f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)<br>
> ><br>
> > where a and b are certain known constants, and if f(m,0) and f(0,n) are all equal to some constant for all m and n, then the general solution for the m,nth value is of the form<br>
> ><br>
> > f(m,n) = A*x^m + B*y^n<br>
> ><br>
> > where x and y can be determined uniquely from the iteration equation and the constants A and B from the boundary conditions at m=0 and n=0.<br>
> ><br>
> > However, that is just a wild guess. You may be faced with something entirely different.<br>
> ><br>
> > Roger Stafford<br>
> <br>
> <br>
> <br>
> <br>
> Hi Roger<br>
> <br>
> <br>
> Yes, I have f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)<br>
> <br>
> I know that for 1 dim. in MAPLE the method used to solve it is called<br>
> rsolve and the syntax would be sth. like this:<br>
> rsolve( {f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n), f(0,0)=10}, f(m,n))<br>
> <br>
> However, Maple fails to solve recurrence relations with more than 1<br>
> dim.<br>
> So my question here, now given that Matlab can solve > dim:<br>
> what is the corresponding code in Matlab in order to get f(m,n) ?<br>
> Thanks for your help!<br>
<br>
The problem is, the simple linear recurrence relation<br>
in one variable has a simple solution, almost trivial<br>
in some respects. At least it is not at all nasty, as<br>
this is something an undergrad might be taught.<br>
The solution to the difference equation is quite<br>
similar in style to the solution of the related second<br>
order linear differential equation. (Think of the<br>
Fibonacci sequence. It has a simple solution as a<br>
sum of two terms.)<br>
<br>
However, it is more difficult in the 2d realm. Even<br>
for as simple a problem as the linear one you<br>
describe,<br>
<br>
f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)<br>
<br>
you must supply more than merely f(0,0). If that<br>
is the only piece of information supplied, there<br>
will be infinitely many potential solutions. As said<br>
by Roger, you must supply the value for all f(0,n)<br>
and all f(m,0) for a unique solution to exist. An<br>
alternative is to define the values of<br>
<br>
f(1,n) = f(m,1) = 0 <br>
<br>
for all m and n. If you do this, then the recurrence<br>
becomes a separable one, reducing to a pair of<br>
linear 1d recurrences along each axis. Thus<br>
<br>
f(m+1,0) = a*f(m,0)<br>
<br>
and <br>
<br>
f(0,n+1) = a*f(0,m)<br>
<br>
with f(0,0) given as some fixed constant. Now<br>
the solution is indeed trivial, as we have<br>
<br>
f(m,n) = f(0,0)*a^n*b^n<br>
<br>
As Roger pointed out, there are other solutions.<br>
For example, if we define f(m,0) = f(0,n) = f(0,0),<br>
constant for all n and m, then we see a different<br>
form for the solution.<br>
<br>
Look at the relation for m = 0. It reduces to the<br>
linear, first order inhomogeneous difference<br>
equation in n.<br>
<br>
f(1,n+1)  b*f(1,n) = a*f(0,0)<br>
<br>
Again, the solution can be found in textbooks,<br>
and we can get a hint of the general solution.<br>
<br>
My point in all of this is the general solution<br>
can get messy in 2d, but also that you must<br>
supply more information, nor do I know that<br>
the solver will handle your problem.<br>
<br>
John