Rational difference equation

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.

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.

Solving a first-order equation

First approach

One approach 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 approach 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 is

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 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.