suivant: Differential equations
monter: Linear systems
précédent: Linear system solving: linsolve
Table des matières
Index
Finding linear recurrences : reverse_rsolve
reverse_rsolve takes as argument a vector
v = [v_{0}...v_{2n1}] made of the first 2n terms of a sequence (v_{n})
which is supposed to verify a linear recurrence relation of
degree smaller than n
x_{n}*v_{n+k} + ... + x_{0}*v_{k} = 0
where the x_{j} are n + 1 unknowns.
reverse_rsolve returns the list
x = [x_{n},..., x_{0}]
of the x_{j} coefficients (if x_{n} 0 it is reduced to 1).
In other words reverse_rsolve solves the linear system of
n equations :
x_{n}*v_{n} + ... + x_{0}*v_{0} 
= 
0 

... 



x_{n}*v_{n+k} + ... + x_{0}*v_{k} 
= 
0 

... 



x_{n}*v_{2*n1} + ... + x_{0}*v_{n1} 
= 
0 

The matrix A of the system has n rows and n + 1 columns :
A = [[v_{0}, v_{1}...v_{n}],[v_{1}, v_{2},...v_{n1}],...,[v_{n1}, v_{n}...v_{2n1}]]
reverse_rsolve returns the list
x = [x_{n},...x_{1}, x_{0}] with x_{n} = 1
and x is the solution of the system
A*(x).
Examples
 Find a sequence verifying a linear recurrence of degree at
most 2 whose first elements 1, 1, 3, 3.
Input :
reverse_rsolve([1,1,3,3])
Output :
[1,3,6]
Hence x_{0} =  6, x_{1} =  3, x_{2} = 1 and the recurrence relation is
v_{k+2} 3v_{k+1} 6v_{k} = 0
Without reverse_rsolve, we would write the matrix of the system :
[[1,1,3],[1,3,3]] and use the rref command :
rref([[1,1,3],[1,3,3]])
Output is [[1,0,6],[0,1,3]] hence x_{0} =  6 and x_{1} =  3
(because x_{2} = 1).
 Find a sequence verifying a linear recurrence of degree at
most 3 whose first elements are 1, 1, 3, 3,1, 1.
Input :
reverse_rsolve([1,1,3,3,1,1])
Output :
[1,(1)/2,1/2,1]
Hence so, x_{0} =  1, x_{1} = 1/2, x_{2} =  1/2, x_{3} = 1, the recurrence
relation is
v_{k+3} 
v_{k+2} +
v_{k+1} 
v_{k} = 0
Without reverse_rsolve, we would write the matrix of the system :
[[1,1,3,3],[1,3,3,1],[3,3,1,1]].
Using rref command, we would input :
rref([[1,1,3,3],[1,3,3,1],[3,3,1,1]])
Output is [1,0,0,1],[0,1,0,1/2],[0,0,1,1/2]]
hence x_{0} =  1, x_{1} = 1/2 and x_{2} =  1/2 because x_{3} = 1),
suivant: Differential equations
monter: Linear systems
précédent: Linear system solving: linsolve
Table des matières
Index
giac documentation written by Renée De Graeve and Bernard Parisse