By 苏剑林 | August 04, 2016
Recently, I have been contemplating some natural language processing problems and some non-linear analysis issues, leaving no time to summarize and publish posts, for which I apologize. What this article discusses is a perturbation scheme for first-order non-linear difference equations (higher-order ones can be treated similarly). Theoretically, this method can provide an explicit asymptotic solution for any first-order non-linear difference equation.
Non-linear Difference Equations
For a general first-order non-linear difference equation
\begin{equation}\label{chafenfangcheng}x_{n+1}-x_n = f(x_n)\end{equation}
Generally, difference equations rarely have analytical solutions; therefore, one must use tools such as asymptotic analysis to investigate the properties of non-linear difference equations. Often, we first consider replacing the difference with a derivative to obtain the differential equation
\begin{equation}\label{weifenfangcheng}\frac{dx}{dn}=f(x)\end{equation}
as an approximation of the difference equation $\eqref{chafenfangcheng}$. Aside from the fact that differential equations have relatively simple explicit solutions, another important reason is that the differential equation $\eqref{weifenfangcheng}$ approximately preserves some fairly important properties of the difference equation $\eqref{chafenfangcheng}$, such as asymptotic behavior. For example, consider a discrete logistic growth model:
\begin{equation}\label{zuzhizengzhang}x_{n+1}=(1+\alpha)x_n -\beta x_n^2\end{equation}
The corresponding differential equation (replacing difference with derivative) is:
\begin{equation}\frac{dx}{dn}=\alpha x -\beta x^2\end{equation}
This equation is solved as
\begin{equation}x_n = \frac{\alpha}{\beta+c e^{-\alpha n}}\end{equation}
where $c$ is an arbitrary constant. The result above already roughly indicates the trend of the solution to the original difference equation $\eqref{zuzhizengzhang}$ and successfully provides the final asymptotic limit $x_n \to \frac{\alpha}{\beta}$. The figure below shows a comparison between the solution of the differential equation and the solution of the difference equation when $\alpha=\beta=1$ and $c=1$ (i.e., $x_0=\frac{1}{2}$).
Perturbation Method for Difference Equations 1
General Format
The question now is: since the solution of the differential equation can serve as a well-behaved approximate solution, can we further incorporate correction terms on the basis of the differential equation solution to improve accuracy? We introduce a parameter $q$ and consider a more general difference equation
\begin{equation}\label{yibanchafenfangcheng}x_{n+q}-x_n = q f(x_n)\end{equation}
When $q=1$, this is exactly the difference equation $\eqref{chafenfangcheng}$ we are considering, and when $q\to 0$, it becomes the differential equation
\begin{equation}\frac{dx}{dn}=f(x)\end{equation}
Note that we have introduced $q$, so the specific form of $x_n$ is related to $q$; in other words, $x_n$ is actually a function of $q$, which we write explicitly as $x_{n,q}$:
\begin{equation}\label{yibanchafenfangcheng2}x_{n+q,q}-x_{n,q}=qf(x_{n,q})\end{equation}
What we ultimately care about is $x_n\equiv x_{n,1}$. To solve this equation step-by-step, we imagine that $x_{n,q}$ can be expanded as a power series in $q$:
\begin{equation}x_{n,q}=\sum_{k=0}^{\infty}a^{(k)}_n q^n\end{equation}
where
\begin{equation}a_n^{(k)} = \frac{1}{k!}\left.\frac{\partial^k x_{n,q}}{\partial q^k}\right|_{q=0},\quad k=0,1,2,\dots\end{equation}
Now the problem is finding each $a_n^{(k)}$.
Step-by-step Expansion
Differentiating both sides of equation $\eqref{yibanchafenfangcheng2}$ with respect to $q$ (the total derivative with respect to $q$), we obtain
\begin{equation}\label{qiudao}\frac{\partial x_{n+q,q}}{\partial n}+\frac{\partial x_{n+q,q}}{\partial q}-\frac{\partial x_{n,q}}{\partial q}=f(x_{n,q})+q\frac{\partial f}{\partial x_{n,q}}\frac{\partial x_{n,q}}{\partial q}\end{equation}
It should be clarified that when we write
\begin{equation}\frac{\partial x_{n+q,q}}{\partial q}\end{equation}
it defaults to differentiating only with respect to the second variable $q$, not with respect to the $q$ within the first variable $n+q$. Now, taking $q=0$, then
\begin{equation}\label{qiudao-q-0}\frac{\partial x_{n,0}}{\partial n}=f(x_{n,0})\end{equation}
This is exactly the differential equation $\eqref{weifenfangcheng}$ as the first approximation.
Next, differentiate $\eqref{qiudao}$ again with respect to $q$:
\begin{equation}\label{qiudao2}\begin{aligned}&\frac{\partial^2 x_{n+q,q}}{\partial n^2}+2\frac{\partial^2 x_{n+q,q}}{\partial n \partial q}+\frac{\partial^2 x_{n+q,q}}{\partial q^2}-\frac{\partial^2 x_{n,q}}{\partial q^2}\\
=&2\frac{\partial f}{\partial x_{n,q}}\frac{\partial x_{n,q}}{\partial q}+q\frac{\partial^2 f}{\partial x_{n,q}^2}\left(\frac{\partial x_{n,q}}{\partial q}\right)^2+q\frac{\partial f}{\partial x_{n,q}}\frac{\partial^2 x_{n,q}}{\partial q^2}\end{aligned}\end{equation}
Letting $q=0$, we obtain
\begin{equation}\label{qiudao2-q-0}\frac{\partial^2 x_{n,0}}{\partial n^2}+2\frac{\partial}{\partial n}\left(\frac{\partial x_{n,0}}{\partial q}\right)=2\frac{\partial f}{\partial x_{n,0}}\frac{\partial x_{n,0}}{\partial q}\end{equation}
The term $\frac{\partial^2 x_{n,0}}{\partial n^2}$ can be calculated by substituting the $x_{n,0}$ obtained in the previous step, so this is a first-order linear differential equation regarding $\frac{\partial x_{n,0}}{\partial q}$, which is also solvable. This process can be continued to progressively improve accuracy. The subsequent forms are too tedious to write down; they can be computed using Mathematica.
Discrete Logistic Growth Model
A specific example makes the process easier to explain. Reconsidering the logistic growth model $\eqref{zuzhizengzhang}$, after introducing the parameter $q$, the equation is written as
\begin{equation}x_{n+q,q}-x_{n,q}=q\alpha x_{n,q}-q\beta x_{n,q}^2\end{equation}
Here $f(x)=\alpha x - \beta x^2$, and the corresponding equation $\eqref{qiudao-q-0}$ is
\begin{equation}\frac{\partial x_{n,0}}{\partial n}=\alpha x_{n,0}-\beta x_{n,0}^2\end{equation}
The solution has already been found as
\begin{equation}x_{n,0}=\frac{\alpha}{\beta+c e^{-\alpha n}}\end{equation}
This is the zero-order approximation. Correspondingly, the corresponding equation $\eqref{qiudao2-q-0}$ is
\begin{equation}\frac{\partial^2 x_{n,0}}{\partial n^2}+2\frac{\partial}{\partial n}\left(\frac{\partial x_{n,0}}{\partial q}\right)=2(\alpha-2\beta x_{n,0})\frac{\partial x_{n,0}}{\partial q}\end{equation}
The solution is (found using Mathematica and manually organized, setting $\frac{\partial x_{0,0}}{\partial q}=0$ here):
\begin{equation}\frac{\partial x_{n,0}}{\partial q}=\left(\frac{\alpha}{\beta+ce^{-\alpha n}}\right)^2\left(\frac{1}{2}\alpha n-\ln \frac{\beta+c}{\beta+ce^{-\alpha n}}\right)ce^{-\alpha n}\end{equation}
Therefore, we have
\begin{equation}x_{n,q}\approx \frac{\alpha}{\beta+c e^{-\alpha n}}+q\left(\frac{\alpha}{\beta+ce^{-\alpha n}}\right)^2\left(\frac{1}{2}\alpha n-\ln \frac{\beta+c}{\beta+ce^{-\alpha n}}\right)ce^{-\alpha n}\end{equation}
and
\begin{equation}x_n\equiv x_{n,1}\approx \frac{\alpha}{\beta+c e^{-\alpha n}}+\left(\frac{\alpha}{\beta+ce^{-\alpha n}}\right)^2\left(\frac{1}{2}\alpha n-\ln \frac{\beta+c}{\beta+ce^{-\alpha n}}\right)ce^{-\alpha n}\end{equation}
This is its first-order approximation. The figure below compares the zero-order and first-order approximate solutions with the exact values when $\alpha=\beta=1$ and $c=1$ (i.e., $x_0=\frac{1}{2}$). It can be seen that compared to the zero-order approximation, the first-order approximation almost coincides with the exact values.
Perturbation Method for Difference Equations 2
From this example, one can also see the characteristics of the perturbation method: although the process can be continued and each step is integrable, the integrals may become too complex to be practical.
Further Remarks
Theoretically, this perturbation scheme can be used to find approximate solutions for any first-order difference equation. Of course, whether it is actually useful in practical applications requires case-by-case analysis. First, if the solution to the zero-order differential equation (which is non-linear) is too complex, then it is difficult to proceed with this method. Second, although each step only generates a theoretically solvable first-order non-homogeneous linear differential equation, solving such a differential equation is not simple; often, taking an extra step costs double the time and effort.
Finally, it should be noted that the format for introducing the parameter is not limited to that shown in $\eqref{yibanchafenfangcheng2}$; one can simplify it based on the specific problem. For example, in the case from the article "Implicit Solution of a Non-linear Difference Equation":
\begin{equation}x_{n+1}=x_n+3+\frac{3}{x_n}+\frac{1}{x_n^2},\,x_1=1\end{equation}
The way to introduce the parameter could be
\begin{equation}x_{n+q,q}=x_{n,q}+3+\frac{3q}{x_{n,q}}+\frac{q^2}{x_{n,q}^2},\,x_1=1\end{equation}
This will yield the same asymptotic solution as in the article "Implicit Solution of a Non-linear Difference Equation". This reflects the essence of the perturbation method, which is to identify the order of each term through the parameter $q$, thereby allowing for step-by-step approximation. What defines the "order," much like the choice of the parameter itself, is largely artificial.