Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
2 dimensional recurrence equation

Subject: 2 dimensional recurrence equation

From: g.n.mueller@gmail.com

Date: 3 Mar, 2009 20:57:23

Message: 1 of 6

Hi

Does anyone know how to solve 2 dim. recurrence equations in Matlab?
I have a table and I can fill it in by hand but I want a closed form
for the
entry (m,n). However, trying to derive the closed form has not led to
any
results yet...
Thanks

Gloria

Subject: 2 dimensional recurrence equation

From: Matt Fig

Date: 3 Mar, 2009 21:30:24

Message: 2 of 6

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.

http://mathworld.wolfram.com/RecurrenceEquation.html






[kbQM[a,kkWrkQkkNrEeQ`ZN\XT[X`MQY9yMkM`UU[T1MYS\[MOM[&akOTZ

Subject: 2 dimensional recurrence equation

From: g.n.mueller@gmail.com

Date: 4 Mar, 2009 06:30:58

Message: 3 of 6



Matt Fig schrieb:
> 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.
>
> http://mathworld.wolfram.com/RecurrenceEquation.html
>


Hi Matt

Thanks. And assuming that it is linear - how can I "type it into
Matlab"?
Or are you saying that because termination is not guaranteed Matlab
can't solve it?
Thanks,

Gloria

Subject: 2 dimensional recurrence equation

From: Roger Stafford

Date: 4 Mar, 2009 08:44:01

Message: 4 of 6

g.n.mueller@gmail.com wrote in message <481501c7-ae48-4c2f-a9d0-dc374434d1b0@a12g2000yqm.googlegroups.com>...
> .......
> Thanks. And assuming that it is linear - how can I "type it into
> Matlab"?
> .......

  Much depends on the form of your two-dimensional iteration equations and the boundary values. If, for example, the iteration is linear of the form

 f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)

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,n-th value is of the form

 f(m,n) = A*x^m + B*y^n

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.

  However, that is just a wild guess. You may be faced with something entirely different.

Roger Stafford

Subject: 2 dimensional recurrence equation

From: g.n.mueller@gmail.com

Date: 4 Mar, 2009 12:09:51

Message: 5 of 6



Roger Stafford schrieb:
> g.n.mueller@gmail.com wrote in message <481501c7-ae48-4c2f-a9d0-dc374434d1b0@a12g2000yqm.googlegroups.com>...
> > .......
> > Thanks. And assuming that it is linear - how can I "type it into
> > Matlab"?
> > .......
>
> Much depends on the form of your two-dimensional iteration equations and the boundary values. If, for example, the iteration is linear of the form
>
> f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)
>
> 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,n-th value is of the form
>
> f(m,n) = A*x^m + B*y^n
>
> 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.
>
> However, that is just a wild guess. You may be faced with something entirely different.
>
> Roger Stafford




Hi Roger


Yes, I have f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)

I know that for 1 dim. in MAPLE the method used to solve it is called
rsolve and the syntax would be sth. like this:
  rsolve( {f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n), f(0,0)=10}, f(m,n))

However, Maple fails to solve recurrence relations with more than 1
dim.
So my question here, now given that Matlab can solve > dim:
what is the corresponding code in Matlab in order to get f(m,n) ?
Thanks for your help!

Gloria

Subject: 2 dimensional recurrence equation

From: John D'Errico

Date: 4 Mar, 2009 13:07:01

Message: 6 of 6

g.n.mueller@gmail.com wrote in message <00fd426e-d5f3-4745-b683-ff04841036a5@e18g2000yqo.googlegroups.com>...
>
>
> Roger Stafford schrieb:
> > g.n.mueller@gmail.com wrote in message <481501c7-ae48-4c2f-a9d0-dc374434d1b0@a12g2000yqm.googlegroups.com>...
> > > .......
> > > Thanks. And assuming that it is linear - how can I "type it into
> > > Matlab"?
> > > .......
> >
> > Much depends on the form of your two-dimensional iteration equations and the boundary values. If, for example, the iteration is linear of the form
> >
> > f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)
> >
> > 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,n-th value is of the form
> >
> > f(m,n) = A*x^m + B*y^n
> >
> > 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.
> >
> > However, that is just a wild guess. You may be faced with something entirely different.
> >
> > Roger Stafford
>
>
>
>
> Hi Roger
>
>
> Yes, I have f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)
>
> I know that for 1 dim. in MAPLE the method used to solve it is called
> rsolve and the syntax would be sth. like this:
> rsolve( {f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n), f(0,0)=10}, f(m,n))
>
> However, Maple fails to solve recurrence relations with more than 1
> dim.
> So my question here, now given that Matlab can solve > dim:
> what is the corresponding code in Matlab in order to get f(m,n) ?
> Thanks for your help!

The problem is, the simple linear recurrence relation
in one variable has a simple solution, almost trivial
in some respects. At least it is not at all nasty, as
this is something an undergrad might be taught.
The solution to the difference equation is quite
similar in style to the solution of the related second
order linear differential equation. (Think of the
Fibonacci sequence. It has a simple solution as a
sum of two terms.)

However, it is more difficult in the 2-d realm. Even
for as simple a problem as the linear one you
describe,

 f(m+1,n+1) = a*f(m,n+1) + b*f(m+1,n)

you must supply more than merely f(0,0). If that
is the only piece of information supplied, there
will be infinitely many potential solutions. As said
by Roger, you must supply the value for all f(0,n)
and all f(m,0) for a unique solution to exist. An
alternative is to define the values of

f(-1,n) = f(m,-1) = 0

for all m and n. If you do this, then the recurrence
becomes a separable one, reducing to a pair of
linear 1-d recurrences along each axis. Thus

f(m+1,0) = a*f(m,0)

and

f(0,n+1) = a*f(0,m)

with f(0,0) given as some fixed constant. Now
the solution is indeed trivial, as we have

f(m,n) = f(0,0)*a^n*b^n

As Roger pointed out, there are other solutions.
For example, if we define f(m,0) = f(0,n) = f(0,0),
constant for all n and m, then we see a different
form for the solution.

Look at the relation for m = 0. It reduces to the
linear, first order inhomogeneous difference
equation in n.

f(1,n+1) - b*f(1,n) = a*f(0,0)

Again, the solution can be found in textbooks,
and we can get a hint of the general solution.

My point in all of this is the general solution
can get messy in 2-d, but also that you must
supply more information, nor do I know that
the solver will handle your problem.

John

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us