A rational difference equation is a nonlinear difference equation of the form
x n + 1 = α + ∑ i = 0 k β i x n − i A + ∑ i = 0 k B i x n − i , {\displaystyle x_{n+1}={\frac {\alpha +\sum _{i=0}^{k}\beta _{i}x_{n-i}}{A+\sum _{i=0}^{k}B_{i}x_{n-i}}}~,}where the initial conditions x 0 , x − 1 , … , x − k {\displaystyle x_{0},x_{-1},\dots ,x_{-k}} are such that the denominator never vanishes for any n.
First-order rational difference equation
A first-order rational difference equation is a nonlinear difference equation of the form
w t + 1 = a w t + b c w t + d . {\displaystyle w_{t+1}={\frac {aw_{t}+b}{cw_{t}+d}}.}When a , b , c , d {\displaystyle a,b,c,d} and the initial condition w 0 {\displaystyle w_{0}} are real numbers, this difference equation is called a Riccati difference equation.5
Such an equation can be solved by writing w t {\displaystyle w_{t}} as a nonlinear transformation of another variable x t {\displaystyle x_{t}} which itself evolves linearly. Then standard methods can be used to solve the linear difference equation in x t {\displaystyle x_{t}} .
Equations of this form arise from the infinite resistor ladder problem.67
Solving a first-order equation
First approach
One approach8 to developing the transformed variable x t {\displaystyle x_{t}} , when a d − b c ≠ 0 {\displaystyle ad-bc\neq 0} , is to write
y t + 1 = α − β y t {\displaystyle y_{t+1}=\alpha -{\frac {\beta }{y_{t}}}}where α = ( a + d ) / c {\displaystyle \alpha =(a+d)/c} and β = ( a d − b c ) / c 2 {\displaystyle \beta =(ad-bc)/c^{2}} and where w t = y t − d / c {\displaystyle w_{t}=y_{t}-d/c} .
Further writing y t = x t + 1 / x t {\displaystyle y_{t}=x_{t+1}/x_{t}} can be shown to yield
x t + 2 − α x t + 1 + β x t = 0. {\displaystyle x_{t+2}-\alpha x_{t+1}+\beta x_{t}=0.}Second approach
This approach9 gives a first-order difference equation for x t {\displaystyle x_{t}} instead of a second-order one, for the case in which ( d − a ) 2 + 4 b c {\displaystyle (d-a)^{2}+4bc} is non-negative. Write x t = 1 / ( η + w t ) {\displaystyle x_{t}=1/(\eta +w_{t})} implying w t = ( 1 − η x t ) / x t {\displaystyle w_{t}=(1-\eta x_{t})/x_{t}} , where η {\displaystyle \eta } is given by η = ( d − a + r ) / 2 c {\displaystyle \eta =(d-a+r)/2c} and where r = ( d − a ) 2 + 4 b c {\displaystyle r={\sqrt {(d-a)^{2}+4bc}}} . Then it can be shown that x t {\displaystyle x_{t}} evolves according to
x t + 1 = ( d − η c η c + a ) x t + c η c + a . {\displaystyle x_{t+1}=\left({\frac {d-\eta c}{\eta c+a}}\right)\!x_{t}+{\frac {c}{\eta c+a}}.}Third approach
The equation
w t + 1 = a w t + b c w t + d {\displaystyle w_{t+1}={\frac {aw_{t}+b}{cw_{t}+d}}}can also be solved by treating it as a special case of the more general matrix equation
X t + 1 = − ( E + B X t ) ( C + A X t ) − 1 , {\displaystyle X_{t+1}=-(E+BX_{t})(C+AX_{t})^{-1},}where all of A, B, C, E, and X are n × n matrices (in this case n = 1); the solution of this is10
X t = N t D t − 1 {\displaystyle X_{t}=N_{t}D_{t}^{-1}}where
( N t D t ) = ( − B − E A C ) t ( X 0 I ) . {\displaystyle {\begin{pmatrix}N_{t}\\D_{t}\end{pmatrix}}={\begin{pmatrix}-B&-E\\A&C\end{pmatrix}}^{t}{\begin{pmatrix}X_{0}\\I\end{pmatrix}}.}Application
It was shown in 11 that a dynamic matrix Riccati equation of the form
H t − 1 = K + A ′ H t A − A ′ H t C ( C ′ H t C ) − 1 C ′ H t A , {\displaystyle H_{t-1}=K+A'H_{t}A-A'H_{t}C(C'H_{t}C)^{-1}C'H_{t}A,}which can arise in some discrete-time optimal control problems, can be solved using the second approach above if the matrix C has only one more row than column.
Further reading
- Simons, Stuart, "A non-linear difference equation," Mathematical Gazette 93, November 2009, 500–504.
References
Skellam, J.G. (1951). “Random dispersal in theoretical populations”, Biometrika 38 196−218, eqns (41,42) ↩
Camouzis, Elias; Ladas, G. (November 16, 2007). Dynamics of Third-Order Rational Difference Equations with Open Problems and Conjectures. CRC Press. ISBN 9781584887669 – via Google Books. 9781584887669 ↩
Kulenovic, Mustafa R. S.; Ladas, G. (July 30, 2001). Dynamics of Second Order Rational Difference Equations: With Open Problems and Conjectures. CRC Press. ISBN 9781420035384 – via Google Books. 9781420035384 ↩
Newth, Gerald, "World order from chaotic beginnings", Mathematical Gazette 88, March 2004, 39-45 gives a trigonometric approach. ↩
Kulenovic, Mustafa R. S.; Ladas, G. (July 30, 2001). Dynamics of Second Order Rational Difference Equations: With Open Problems and Conjectures. CRC Press. ISBN 9781420035384 – via Google Books. 9781420035384 ↩
"Equivalent resistance in ladder circuit". Stack Exchange. Retrieved 21 February 2022. https://physics.stackexchange.com/q/121297 ↩
"Thinking Recursively: How to Crack the Infinite Resistor Ladder Puzzle!". Youtube. Retrieved 21 February 2022. https://www.youtube.com/watch?v=rqckorUt2ck ↩
Brand, Louis, "A sequence defined by a difference equation," American Mathematical Monthly 62, September 1955, 489–492. online /wiki/American_Mathematical_Monthly ↩
Mitchell, Douglas W., "An analytic Riccati solution for two-target discrete-time control," Journal of Economic Dynamics and Control 24, 2000, 615–622. /wiki/Journal_of_Economic_Dynamics_and_Control ↩
Martin, C. F., and Ammar, G., "The geometry of the matrix Riccati equation and associated eigenvalue method," in Bittani, Laub, and Willems (eds.), The Riccati Equation, Springer-Verlag, 1991. ↩
Balvers, Ronald J., and Mitchell, Douglas W., "Reducing the dimensionality of linear quadratic control problems," Journal of Economic Dynamics and Control 31, 2007, 141–159. /wiki/Journal_of_Economic_Dynamics_and_Control ↩