特殊的通项公式:二次非线性递推
By 苏剑林 | 2014-11-12 | 60393位读者 |特殊的通项公式 #
对数学或编程感兴趣的读者,相信都已经很熟悉斐波那契数列了
0, 1, 1, 2, 3, 5, 8, 13, ...
它是由
$$a_{n+2}=a_{n+1}+a_n,\quad a_0=0,a_1=1$$
递推所得。读者或许已经见过它的通项公式
$$a_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]$$
这里假设我们没有如此高的智商可以求出这个复杂的表达式出来,但是我们通过研究数列发现,这个数列越来越大时,相邻两项趋于一个常数,这个常数也就是(假设我们只发现了后面的数值,并没有前面的根式)
$$\beta=\frac{1 + \sqrt{5}}{2}=1.61803398\dots$$
因此,我们会想到用等比数列$\alpha \beta^n$近似表示这个数列,并且通过数值计算,发现$\alpha$确实趋于一个常数,它就是
$$\alpha=\frac{1}{\sqrt{5}}=0.4472135\dots$$
后来我们就发现,斐波那契数列的通项可以表示为
$$a_n=\left[\alpha \beta^n\right]$$
其中$\left[x\right]$表示对$x$进行四舍五入,这结果当然可以严格地证明。但是我们只留意这里出现的一些新奇的东西,它表明,有些数列的通项可以表示为某个无理数列的取整,这是一种比较奇特的通项公式。下面我们考虑非线性递推
$$a_{n+1}=a_n^2+c$$
其中$a_0$和$c$都为正数,我们将会发现,这将导致一个类似的取整通项。
二次非线性递推 #
可以看到,如果$c=0$,那么通项是很容易的,我们有$a_n=a_0^{2^n}$,这是一个快速增长的数列($a_0 > 1$时),如果$c$不为0,那么这将是一个递增得非常快的数列(指数的指数,像费马数一般),比如$a_0=1,c=1$时,我们有
1, 2, 5, 26, 677, 458330, 210066388901, ...
在$n$比较大的时候,$a_n^2+c$与$a_n^2$的差别是微不足道的。于是还是可以认为,存在某个常数$k$,使得$a_n\sim k^{2^n}$,本文的研究思路正是基于此,而计算主要来自数学研发论坛的kastin大神。
设$x_n=\ln a_n$,那么
$$x_{n+1}=2x_n+\ln\left(1+\frac{1}{a_n^2}\right)$$
迭代得
$$\begin{aligned}x_n=&2^n x_0 +\sum_{i=0}^{n-1} 2^{n-i}\ln\left(1+\frac{1}{a_i^2}\right)\\
=&2^n x_0+\sum_{i=0}^{\infty}2^{n-1-i}\ln\left(1+\frac{1}{a_i^2}\right) -\sum_{i=n}^{\infty}2^{n-1-i}\ln\left(1+\frac{1}{a_i^2}\right)\\
=&2^n\left(x_0+\sum_{i=0}^{\infty}\frac{1}{2^{i+1}}\ln\left(1+\frac{1}{a_i^2}\right)\right) -2^{n-1}\sum_{i=n}^{\infty}\frac{1}{2^{i}}\ln\left(1+\frac{1}{a_i^2}\right)\end{aligned}$$
从$a_n$的增长速度可以看出,第一个无穷级数必然收敛,于是我们就可以(目前还只能通过数值方法)求出它的(近似)极限值。然后我们估计第二个级数的影响。于是
$$\begin{aligned}a_n=&\exp(x_n)\\
=&\exp(-r_n)k^{2^n}\end{aligned}$$
其中
$$\begin{aligned}&k=\exp\left[x_0+\sum_{i=0}^{\infty}\frac{1}{2^{i+1}}\ln\left(1+\frac{1}{a_i^2}\right)\right]\\
&r_n=2^{n-1}\sum_{i=n}^{\infty}\frac{1}{2^{i}}\ln\left(1+\frac{1}{a_i^2}\right) < \ln\left(1+\frac{1}{a_n^2}\right)\end{aligned}$$
那么
$$a_n > \exp\left(-\ln\left(1+\frac{1}{a_n^2}\right)\right)k^{2^n}$$
即
$$a_n+\frac{1}{a_n} > k^{2^n}$$
同理,有
$$r_n > -\ln\left(1+\frac{1}{a_n^2}\right)$$
所以
$$a_n < \exp\left(\ln\left(1+\frac{1}{a_n^2}\right)\right)k^{2^n}$$
即
$$k^{2^n}> a_n \left/\left(1+\frac{1}{a_n^2}\right)\right. > a_n - \frac{1}{a_n}$$
从而
$$\left|a_n-k^{2^n}\right| < \frac{1}{a_n} < \frac{1}{2}\quad (n\geq 1)$$
也就是说$a_n$是最接近$k^{2^n}$的整数,于是得到通项公式
$$a_n=\left[k^{2^n}\right]$$
实际上,可以进一步得到,该取整符号总是下取整的(只有四舍,没有五入)。这是Aho和Sloane在1973年得到的结果。
编程计算 #
下面编程计算$k$,Python代码
from math import log,exp
n=6 # 计算6步已经很精确了。
x=1
l=[log(1+1/x**2)/2]
for i in range(n):
x=x**2+1
l.append(log(1+1/x**2)/2**(i+2))
k=exp(sum(l))
print(k)
算得
k=1.5028368010497564...
要注意,原则上来说,精确计算$k$需要知道所有的$a_n$,不然计算出来的近似的$k$,只能用于计算前几项,后面的误差就大了,于是这项工作看来是本末倒置了,从这里可以看出,如果要计算$a_n$的具体值,最好的方法还是老老实实递归吧。然而,对于一个数列,我们要做的事情,不仅仅是要计算每一项,还要分析它的性态等。写出这个形式的解,就有助于让我们看出它是如何增长的——基本上按照$k$为底的指数的指数增长!
方法评述 #
可以看出,我们求二次非线性递推通项的主要思路就是发现数列是递增的,然后就可以认为在很大的时候,常数的影响很小,因此近似于没有常数的情况,从而可以退化为没常数的情况,并且估计通项公式。类似地,该方法可以推广到三次甚至更高次的情况,思路和计算都是类似的,主要是在$n$很大的时候,通项几乎只取决于最高次项。事实上,上例中的常数$k$,可以更简洁表述为
$$k=\lim_{n\to\infty}\left(a_n\right)^{2^{-n}}$$
同时对比斐波那契数列,我们可以写出斐波那契数列数列的取整形式的通项公式,它与非取整形式的通项公式相比,就多出了另外一项(负数幂),通过另外一项来“填补”取整那部分。这是不是意味着:二次非线性递推,也可能存在另外一项,来补充取整的那部分,从而去掉取整符号?让人惊喜的是,对于某些二次非线性递推,确实是这样子的!不过这我们将在以后再谈到了。
然而,还有一些其他的非线性递推问题,比如离散阻滞增长模型,其递推是
$$a_{n+1}-a_n=\alpha a_n-\beta a_n^2$$
其中$\alpha,\beta$都是正数,且一般来讲$\alpha \gg \beta$,这样的情况解的性态是很良好的(那条S型曲线),但是我们并没有很好地写出它的显式解来——哪怕只是高于一阶的近似。因此,如果有兴趣的话,可以往这个方向研究下去。
参考: #
http://mathworld.wolfram.com/QuadraticMap.html
转载到请包括本文地址:https://kexue.fm/archives/3064
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Nov. 12, 2014). 《特殊的通项公式:二次非线性递推 》[Blog post]. Retrieved from https://kexue.fm/archives/3064
@online{kexuefm-3064,
title={特殊的通项公式:二次非线性递推},
author={苏剑林},
year={2014},
month={Nov},
url={\url{https://kexue.fm/archives/3064}},
}
July 17th, 2016
不好意思,试一试tex
July 17th, 2016
如何删除我的留言?
不好意思,游客是不能删除自己的评论的。你要练习latex,可以直接到http://kexue.fm/LaTeX.html
July 26th, 2020
棒棒的