Substitution Iteration in Matlab

Hi, I am facing some problem in iterating my equations. Basically, here how it should work.

x(i) = x(i+1) + x(i+2)

starting from i =6

x(6) = x(5) +x(4), while x(5)= x(4)+ x(3)...etc

I would like to use loop to do this automatically as x(6) and x(-6) is known and I need to find x(0). But I have no idea how to do it. Can anyone help me in this?

[Joseph Cheng]

Are there any more constrains to the question (all positive) what happens when you get down to i<2? also i think you mean that x(i) = x(i-1) + x(i-2);

for example the Fibonacci sequence has some sort of starting criteria since it starts with [1 1 2]. where the first 2nd position has different rules (unless you think pos 0 is 0. then pos 1 has different rule as x(1) = x(0)+x(-1) which we don't have or is not specified.

[zhe yi soo]

Thank you for the comment. I forgot about that. There is one more known value which is x(-6). So basically, what I am trying to do is to keep substituting the first equation until I get only one unknown. And by keep doing this, I will need to determine x(0) by the end.

[Joseph Cheng]

Okay, so if i can dumb it down a bit. "we" have the first and last values in an array. the middle portions fit the x(i)=x(i-1)+x(i-2) format. I think this is doable.

Answer 1

[Roger Stafford]

Here is an alternative method of solving your problem. For the fibonacci iteration, x(i) = x(i-1) + x(i-2), we can solve the quadratic equation

 t^2 = t + 1

to get t = (1+sqrt(5))/2 or t = (1-sqrt(5))/2, and we can conclude that x must satisfy

 x(n) = A*((1+sqrt(5))/2)^n + B*((1-sqrt(5))/2)^n

for some constant values A and B. This must hold for n = 6 and n = -6 which gives two equations and the two unknowns A and B.

 A*((1+sqrt(5))/2)^6    + B*((1-sqrt(5))/2)^6    = x(6)
 A*((1+sqrt(5))/2)^(-6) + B*((1-sqrt(5))/2)^(-6) = x(-6)

Their solution using matlab's backslash operator is

 AB = [((1+sqrt(5))/2)^6   ,((1-sqrt(5))/2)^6   ;...
          ((1+sqrt(5))/2)^(-6),((1-sqrt(5))/2)^(-6)] \ [x(6):x(-6)];
 A = AB(1); B = AB(2);

Then

 x(0) = A+B;

(Note: You can't actually have a matlab vector x indexed with 0 or -6, so you must name x(6), x)-6), and x(0) in the above in other ways, such as x6, xm6, and x0.)

[zhe yi soo]

Thank you so much for that. I was wondering if this could work on my original question as my original question is

A(i)= B(i) + B(i-1）

B(i)= A(i) + A(i-2)

A(i)= B(i-1) + A(i-2)

B(i)= B(i-1) + A(i-2)

i can be any number from n to -n, and 0 need to be determined.

[Roger Stafford]

I have the feeling you have made some error on these iterative relationships. If they are all to hold simultaneously, the only solution is for A(i) and B(i) to both be zero for all i. Perhaps you mean something else?

Combining the third and fourth equalities leads to the conclusion that A(i) = B(i), and applying this in the first equality implies B(i-1) = 0. Hence A and B are always zero.

[zhe yi soo]

Hi, I am sorry that I simplified all the equations by ignoring the coefficients as there are constant coefficient for all variables of the four equations. Hence, A(i) is not equal to B(i). But basically it is right that all the equations are in that form where x1,x2,x3,x4,x5,x6,x7,and x8 are all known constansts.

A(i)= x1*B(i) + x2*B(i-1)

B(i)= x3*A(i) + x4*A(i-2)

A(i)= x5*B(i-1) + x6*A(i-2)

B(i)= x7*B(i-1) + x8*A(i-2)

Thanks

[Roger Stafford]

@Zhe Yi Soo. I have considered your modified set of iterative equations and have tentatively concluded that in order to have a non-zero solution for the A and B sequences it is necessary in general that the constants x1, x2, x3, ..., x8 satisfy two particular equalities. That is to say, the eight constants have only six degrees of freedom in their choice.

The analysis to establish this is sufficiently complicated that I am reluctant to burden this thread with a lengthy explanation of the reasoning behind this claim, so I pose this question. Given that there is such a restriction on the eight coefficients, is this something you still want to follow up on? If so, I would suggest you open up a new "Answers" thread and pose this modified question concerning the eight-parameter four-equation iterative relationship.

Answer 2

[Joseph Cheng]

Well there are a few ways to do it. if you lay out the equations substitutions you can get it such that xn = B*x2+A*x1; so if i say the first few array values are [a b c d e f g h ...] then

 c = b+a;
 d = c+b = 2b+a
 e = d+c = 3b+2a
 f = e+d = 5b+3a
 g = f+e = 8b+5a
 and so on..

so if we keep is simple and do x1 =50 and x6 = 400 then based on this 400 = 5*x2+3*50 gives x2=50 and then you can find any of the other middle values.

if you want to brute force it then

x1 = 1;
xn = 4050;

iter = 35;
possiblex2 =[];
xdiff = [];
for x2 = x1:round(xn/2)
    xtemp = x2;
    xm2 = x1;
    x = [x1 x2];
    for it = 3:iter

        xtemp = xtemp + xm2;
        xm2 = xtemp-xm2;
        x = [x xtemp];
      end
      if xtemp == xn
          possiblex2 = [possiblex2 x2];
         disp(['possible x2 =' num2str(x2)]); 
         disp([x]); 

      else
          xdiff = [xdiff xtemp-xn]; 
      end 
  end

[zhe yi soo]

Hi, thank you so much for the solution. But, would you mind explaining more on your solution as I am a newbie to Matlab or coding as I started to use it ffor academic purposes only. Thank you so much as this will be really useful for my research now.

[Joseph Cheng]

Usually i would say most people learn Matlab for academic purposes (but figure out how COOL it is and continue to use it, mostly because personal licenses are extremely expensive so we get to use it at work.) anyways. with your addition to the original question it just falls to the Fibonacci sequence so the equation portion i have above would be simple enough to figure out the problem and can easily be done.

I'll comment the brute force check.

x1 = 10;  %define initial value
xn = 130; %define last value  

iter = 7; %set number of iterations 
possiblex2 =[];  %store the possibilities, if there are any

 %cycle through each possibility starting from the first then half of the final value.  THis is because if it is more than half it probably won't equal your final value after 1 iteration.  
  for x2 = x1:round(xn/2) 
      xtemp = x2; %store the x-1 value
      xm2 = x1;  %store the x-2 value
      x = [x1 x2];  %keep a running log of the values
      for it = 3:iter %now just do the sequence of events
          xtemp = xtemp + xm2;  %add x-1 to x-2.  
          xm2 = xtemp-xm2;  %x-1 now becomes x-2.  
          x = [x xtemp];  %store the current x value into the array.
        end
  %now that the sequence has been complete we check if the last value calculated matches the desired last value.
        if xtemp == xn
            possiblex2 = [possiblex2 x2];
           disp(['possible x2 =' num2str(x2)]); 
           disp([x]); 
        end 
    end

[Joseph Cheng]

Also for the equation based portion here is what you can do..

x1 = 10;
iter = 7;
xiter = 130;
fib = ones(1,7);
for i =3:7
   fib(i) = fib(i-1)+fib(i-2); 
end

% c = b+a;
% d = c+b = 2b+a
% e = d+c = 3b+2a
% f = e+d = 5b+3a
% g = f+e = 8b+5a
% and so on..

coeff1 = fib(iter-1);
coeff2 = fib(iter-2);

%solve for x2
x2 = (xiter-coeff2*x1)/coeff1;

%then to check something in the middle.
%how about iter = 4?
x4 = fib(4-1)*x2+fib(4-2)*x1;
%here x4=30 which matches index 4.  [10 10 20 30....] hurray!

[zhe yi soo]

Thank you so much, your explanation is very clear and this will be very useful to me. I am trying to implement this to my original question which is

A(i)= B(i) + B(i-1)

B(i)= A(i) + A(i-2)

A(i)= B(i-1) + A(i-2)

B(i)= B(i-1) + A(i-2) :)

[zhe yi soo]

Hi, I met a trouble as I couldn't predict the coefficient of my questions. As mentioned above my equations are

A(i)= B(i) + B(i-1)

B(i)= A(i) + A(i-2)

A(i)= B(i-1) + A(i-2)

B(i)= B(i-1) + A(i-2)

Assume i is 7 and A(7),A(0),B(7),B(0) are known. (Just for easier calculation here, so that my iteration will be from 7 to 0)

Starting from

A(7) = B(6) + A(5)

    =B(5)+A(4) + B(4)+A(3) (using equation 3 and 4)

    =B(4)+A(3) + B(3)+A(2) + B(3)+A(2) + B(2)+A(1) (using equation 3 and 4)

    =B(3)+A(2) + B(2)+A(1) + B(2)+A(1) + B(1)+A(0) + B(2)+A(1) + B(1)+A(0)         
     + B(1)+A(0) + B(1)+B(0)  (using equation 1,3,4. When it comes to A(1),    
     we have to switch to equation 1 to prevent A(-1)) 

    =B(2)+A(1) + B(1)+A(0) + B(1)+A(0) + B(1)+B(0) + B(1)+A(0) + B(1)+B(0) 
     + B(1) + A(0) + B(1)+A(0) + B(1)+B(0) + B(1) + A(0) + B(1) + A(0) +B(1)
     + B(0)

    = 12B(1)+7A(0)+5B(0)

Using the same way,

A(6)=8B(1)+4A(0)+3B(0)

A(5)=3B(1)+3A(0)+2B(0)

A(4)=3B(1)+2A(0)+B(0)

A(3)=2B(1)+A(0)+B(0)

A(2)=B(1)+A(0)

Originally my idea was trying to iterate in the way that when i of A(i) or B(i) is bigger than 1, then it will substitute in equation 3 and 4. While i is equal to 1, then it will substitute in equation 1 and 2. This process will keep iterating until the equation is left with one unknown.

[Joseph Cheng]

Are you sure about that last line of B(i)=B(i-1)+A(i-2)? then that would mean that A(i)=B(i)?

also based on equations 1 and 2 then A(i-2) = -B(i-1).

[zhe yi soo]

Hi, I am sorry that I simplified all the equations by ignoring the coefficients as there are constant coefficient for all variables of the four equations. Hence, A(i) is not equal to B(i). But basically it is right that all the equations are in that form where x1,x2,x3,x4,x5,x6,x7,and x8 are all known constansts.

A(i)= x1*B(i) + x2*B(i-1)

B(i)= x3*A(i) + x4*A(i-2)

A(i)= x5*B(i-1) + x6*A(i-2)

B(i)= x7*B(i-1) + x8*A(i-2)

Thanks