求数列通项\(a_{n+1}=2a_{n}^{2}+1\)

dianyancao

\[a_{n+1}=2a_{n}^{2}+1,a_0=c\]
对于任意给定一个常数\(a_0=c\),据说这个数列的通项求不出，如何证明其没有闭式表达？

kastin

非线性映射对于初值非常敏感。混沌理论就是源于此。

特别的，二次映射有相关的研究。对于一些特殊问题是有非传统形式的封闭解的，具体参见http://bbs.emath.ac.cn/forum.php ... 27&fromuid=8865

dianyancao

若\(a_0=1\),如何求解通项？

kastin

根据我在2楼给出的链接，利用类似的方法可以得到相应的结果【见下面的 ` (7)`】。
因为 `a_0=1`，易知 `a_n>0`。可令 `x_n=\log 2a_n`，于是原递推式 `a_{n+1}=2a_{n}^{2}+1` 可改写为$$x_{n+1}=2x_n+g_n \tag{1}$$其中 `\D g_n=\log \left( 1+\frac{1}{2a_n^2}\right)>0`
故$$\begin{aligned}x_n&=2^n\left(x_0+\frac{g_0}{2}+\frac{g_1}{2^2}+\cdots+\frac{g_{n-1}}{2^n}\right)\\
&=X_n-r_n\end{aligned}\tag{2}$$其中$$\begin{align*}X_n&=2^nx_0+\sum_{i=0}^{\oo}2^{n-1-i}g_i\tag{2.1}\\
r_n&=\sum_{i=n}^{\oo}2^{n-1-i}g_i \tag{2.2}\end{align*}$$所以$$2a_n=\exp(x_n)=\exp(X_n-r_n)=A_n\exp(-r_n)\tag{3}$$其中$$\begin{align*}A_n&=\exp(X_n)={k^2}^{^n} \tag{3.1}
\\k&=2a_0\exp\left(\sum_{i=0}^{\oo}\frac{g_i}{2^{i+1}}\right)\tag{3.2}\end{align*}$$
现在来考虑 `\exp(-r_n)` 这一项的影响：
因为 `a_n` 是单调递增数列，故 `g_n` 单调递减，即 `|g_n|>|g_{n+1}|`，因此由 `(2.2)` 可知 `|r_n|<|g_n|`（即 `-|g_n| \lt r_n \lt |g_n|`）。
从而我们有 $$\begin{align*}A_n &= \exp(x_n+r_n) \\
&=2a_n\exp(r_n) \lt 2a_n\exp(|g_n|) =2a_n(1+\frac{1}{2a_n^2})\\ \tag{4}\end{align*}$$并且 $$A_n=2a_n \exp(r_n) \gt 2a_n \exp(-|g_n|) \geqslant 2a_n(1-\frac{1}{2a_n^2})\tag{5}$$
对于任意 `n>1` ，`a_n \gt 2`，结合 `(4)`,`(5)` 可知$$|2a_n-A_n|\lt \frac{1}{2}\tag{6}$$上式说明 `A_n` 是最接近于 `2a_n` 的整数，故$$a_n=\frac{A_n}{2}=\frac{[{k^2}^{_n}]}{2}\tag{7}$$上面的方括号 `[\cdot]` 表示四舍五入。

通过数值计算得出 `k\approx 2.483253536172637\ldots`

Mathematica程序如下：

1. (* 计算底数k *)
   
2. k[n0_] :=
   
3. Module[{a = 0},
   
4.   a = RecurrenceTable[{x[n + 1] == 2 x[n]^2 + 1, x[0] == 1},
   
5.     x, {n, 0, n0}];
   
6.   (* 仅用前n0项代替无穷项来计算k, 因为RecurrenceTable函数对于较大的n0效率会严重下降 *)
   
7.   2 Exp@Total[Log[1 + 1/(2*a^2)]/2^(Range[0, n0] + 1)]];
   
8. results = Round[k[10]^(2^Range[0, 7])]/2
   
9. 
   
10. (* 验证结果 *)
    
11. a = RecurrenceTable[{x[n + 1] == 2 x[n]^2 + 1, x[0] == 1},
    
12.    x, {n, 0, 7}];
    
13. SameQ[a, results]

复制代码

结果：
{1,3,19,723,1045459,2185969041363,9556921299594946409795539,182669489453303118864862198078197846848343568601043}
True

值得注意的是，上面的结果 `(7)` 仅仅是一种形式通项公式，因为 `k` 是无理数，如果不使用无穷精度的话，`n` 取某个较大的整数 `M` 之后的所有整数时，`(7)` 式计算出的 `a_n` 与递推式产生的真值有偏差。

@dianyancao，若是回复某人或在帖子中想提起某人的注意，请使用艾特符号，或者点击帖子中的回复，不然对方不知道 :）。

dianyancao

用无穷级数拟合该数列通项，非常好的估计了误差
如下应该是笔误：
\(k^{2^n},k^{2^n}=2a_0\exp\left(\sum_{i=0}^{\oo}\frac{g_i}{2^{i+1}}\right)\tag{3.2}\)
\(\gt ,A_n=2a_n \exp(r_n) \gt 2a_n \exp(-|g_n|) \gt 2a_n(1-\frac{1}{2a_n^2})\tag{5}\)

dianyancao

我根本不会，现在总算知道链接
http://mathworld.wolfram.com/QuadraticMap.html
说的是什么了
试试@@kastin
@kastin

kastin

dianyancao 发表于 2014-8-26 23:06
我根本不会，现在总算知道链接
http://mathworld.wolfram.com/QuadraticMap.html
说的是什么了

4楼的方法对于合适的形式和适当的初值都是适用的，并且可以推广到三次、四次等情形。

对于二次映射，并不存在一般形式的封闭解。这是因为：
1) 在非线性系统中，初值对于解的形式起到决定性的作用（想想蝴蝶效应吧）。比如偏微分方程中的黎曼问题（如果你学过计算流体力学的话，就是对应于激波间断）——初值条件即使是光滑函数，最终的解也会变成间断的。
2) 根据不动点理论，非线性系统（非线性微分方程或者非线性迭代）经常出现周期解，而且周期不固定，且不止一个（具体参见 非线性动力系统 相关知识）。这些都决定了难以给出一个封闭的通解形式。

更进一步，对于同种类型的非线性方程，哪怕方程中某个参数发生微小的改变，最后解的形态也可能相差十万八千里，这就是非线性迭代中有名的分叉现象。比如，如果将1楼方程递推式中的 `a_n^2` 项前面的系数2，或者后面的常数项1稍微改成其他数，那么4楼的方法就不一定适用了，因为此时解的形式（无论是否存在封闭解）很可能发生了巨大的变化。

由于差分方程是微分方程的离散形式，我们可以考虑重新认识一下1楼的递推关系。
我们重新把它写成标准的差分形式$$a_{n+1}-a_n=2a_n^2-a_n+1$$显然，它的对应的连续形式是黎卡提(Riccati)微分方程（常系数情形）：$$\frac{\dif y}{\dif x}=2y^2-y+1$$由于是常系数，所以这个方程很好解——只需要分离变量即可——如果右端多项式能在实数域内因式分解，那么解的形式是关于 `\exp(x)` 的一次有理分式形式( `\D\frac{a\exp(x)+b}{c\exp(x)+d}`)；否则，解是正弦函数 `\sin f(x)` 或者正切函数 `\tan f(x)` 形式。这就说明，系数至关重要，如果系数2，-1，1发生改变，那么解的形式要么是三角函数（判别式为负），要么是有理式的复合函数（判别式非负）。

从上述事实中可以认识到，非线性系统中参数的改变，的确会影响解的形态。

对于上面的微分方程，因为判别式小于零，故只能是三角函数形式。而配方后常数项和二次项都是正的，因此该微分方程的通解是正切形式。那么相应的离散解 `a_n` 也是这种形式吗？显然不是。因为我们需要特别注意的是， `a_n`并不等于对应连续形式的微分方程的解 `y=f(x)` 在正整数点 `x=n`处的函数值，因为这只是一种定性类比，所以它只能反映变化趋势（比如正切是单调递增的，那么 `a_n`也是递增的）。另外，这种类比方法与线性差分方程解法中的母函数方法也不一样。

回忆欧拉-麦克劳林求和公式，它是连续与离散领域的一座桥梁——将离散的求和与连续的积分、导数的关系联系起来了。而离散的差分与连续的导数是如何联系的呢？这就是泰勒展开所回答的问题$$f(x+1)-f(x)=f'(x)+\frac{f''(x)}{2!}+\frac{f'''(x)}{3!}+\cdots$$所以解如果是在整数点处对应的话，正确的连续形式应该是$$y'+\frac{y''}{2!}+\frac{y'''}{3!}+\cdots=2y^2-y+1$$

282842712474

kastin 发表于 2014-8-26 20:08
根据我在2楼给出的链接，利用类似的方法可以得到相应的结果【见下面的 ` (7)`】。
因为 `a_0=1`，易知 `a_ ...

kastin总是让我大开眼界！

kastin

对于 @dianyancao 的提醒，我想到了Mathematica对于一些特殊有理分式的不定积分处理。比如不定积分$$\int\frac{1}{x^4-x^2+1}\dif x=\arctan(x-\frac{1}{x})-\frac{1}{4\sqrt{3}}\ln\frac{x^2-\sqrt{3}+1}{x^2+\sqrt{3}+1}+c$$而Mathematica给出的是$$\frac{i}{\sqrt{6}}\left(\sqrt{-1-i\sqrt{3}}\arctan\frac{(1-i\sqrt{3})x}{2} - \sqrt{-1+i\sqrt{3}}\arctan\frac{(1+i\sqrt{3})x}{2}\right)+c$$按理说，这里的复变函数应该与上面的是等价的，通过展开后发现确实是等价的，只是相差一个常数，跟复数的幅角有关。

282842712474

说到离散与连续的对应，以前我在学习量子物理的时候，曾经思考过，我们的世界本质是离散的还是连续的，我们现在描述物理现象都是用微分方程，这有没有可能实际上是差分方程的一种近似，比如dx/dt，实际上是$\frac{x(t+\varepsilon)-x(t)}{\varepsilon}$，$\varepsilon$虽小却有限？这样，微分方程可以多取带有$\varepsilon$的项。

另外，引入无穷小的高阶导数项，往往会导致奇点的出现~正如$ax^2+bx+c=0$的求根公式，在$a\to 0$也会出现奇点。

但是，这种技巧却也可能用于消去奇点~也就是说，差分方程由于其不连续性，或许可以跳过奇点。