这篇文章上次修改于 612 天前,可能其部分内容已经发生变化,如有疑问可询问作者。
由数列的递推公式求解通项公式是一类常见的数列问题。这篇文章将简单介绍一种求解某些一阶递推数列的通用方法:不动点法。
一个例子
我们先来看一个例题。
已知数列 $\{a_n\}, n=1,2,3,\cdots$ 满足 $a_{n+1}=\frac{4a_n-2}{a_n+1}$ ,其中 $n=1,2,3,\cdots$ ,且 $a_1=4$ ,求 $\{a_n\}$ 的通项公式。
解:注意到 $\frac{a_{n+1}-1}{a_{n+1}-2}=\frac{\frac{4a_n-2}{a_n+1}-1}{\frac{4a_n-2}{a_n+1}-2}=\frac{3}{2}\cdot\frac{a_{n}-1}{a_{n}-2}$ ,故 $\left\{\frac{a_{n}-1}{a_{n}-2}\right\}$ 为以 $\frac{3}{2}$ 为公比的等比数列,又 $\frac{a_1-1}{a_1-2}=\frac{3}{2}$ ,所以 $\frac{a_{n}-1}{a_{n}-2}=\left(\frac{3}{2}\right)^n$ ,即 $a_n=2+\frac{2^n}{3^n-2^n}$ 。
看完这个解答有什么感受?是不是第一步的“注意到”让人一头雾水?
其实,这个“注意到”并不是乱凑出来的,发现这一步的原理就是本文要讲的不动点法。
递推数列与函数迭代
最开始,不动点法是作为求解函数迭代的方法而被研究的。所以在开始之前,我们先介绍一下递推数列与函数迭代的关系。
对于一阶递推数列,我们可以把递推公式看成函数关系 $a_{n+1}=f(a_n)$ 。在我们知道了 $a_1$ 的值之后,就可以依次求出数列每一项的值:
$\begin{align} a_2&=f(a_1)\\ a_3&=f(a_2)=f(f(a_1))\\ a_4&=f(a_3)=f(f(a_2))=f(f(f(a_1)))\\ &\cdots \end{align}$
写到这里,就能发现,求解递推数列和求解函数迭代在本质上是一样的。
我们记 n 次迭代函数 $f^{(n)}(x)=\underbrace{f(f(f(\cdots f}_{n个f}(x))))$ ,并补充定义 $f^{(0)}(x)=x$ ,那么对于递推数列 $a_{n+1}=f(a_n)$ ,我们可以通过求解函数迭代来求解数列的通项公式 $a_n=f^{(n-1)}(a_1)$ 。
于是,求解递推数列的问题就转化为了求解函数迭代。
函数的不动点
对于函数 $f:\mathbb R\rightarrow \mathbb R$ ,我们把满足 $f(x_0)=x_0$ 的 $x_0$ 称为 $f(x)$ 的不动点。
为什么叫“不动点”呢?如果我们把函数看作从 $\mathbb R$ 到 $\mathbb R$ 的一个映射,那么不动点经过这一映射之后,还是它本身,就像固定在数轴上“不动”,所以叫做“不动点”。
不动点有很多奇妙的应用。比如巴拿赫不动点定理,又称压缩映射定理,这个定理指出,如果一张地图的内容包含地图本身所处的位置,那么地图上一定有一个点和它的实际位置重合,也就是“从现实位置到地图位置”这一映射的不动点。再比如数值分析中的不动点迭代法,可以快速求解一个函数的不动点的近似值,进而也就能求解方程的根的近似值。本文主要介绍不动点在求解递推数列及函数迭代中的应用,所以对不动点的其他性质不多加赘述。
不动点和函数迭代有很大的关系。可以发现,一个函数的不动点也是它的任意次迭代函数的不动点,也就是 $f^{(n)}(x_0)=f^{(n-1)}(f(x_0))=f^{(n-1)}(x_0)=\cdots=f(x_0)=x_0$ 。
当然,反过来并不一定成立。迭代函数的不动点不一定是原始函数的不动点。例子很好找,比如 $f(x)=\frac1x$ ,它的二次迭代函数 $f^{(2)}(x)=x$ ,处处都是不动点,但是 $f(x)$ 的不动点只有 $\pm1$ 而已。
换元法与函数相似
换元法可以说是最常用的简化问题的方法了。文章开头的例题也可以看作是换元法的一种应用,也就是令 $b_n=\frac{a_{n}-1}{a_{n}-2}$ ,从而得出 $\left\{ b_n \right\}$ 是等比数列,极大地简化了问题。
既然我们刚才已经找到了数列迭代在函数观点下的写法,那么能不能找到换元法在函数观点下的形式呢?
对于一个函数 $f(x)$ ,我们作换元 $t=\varphi(x)$ 。为了问题简便,我们不妨只考虑 $\varphi(x)$ 是一一映射的情形,这时候就能用反函数来表达 $x=\varphi^{-1}(t)$ ,于是 $f(x)$ 就有了自变量为 $t$ 的形式 $f(\varphi^{-1}(t))$ 。
现在我们来看一个问题:$f(x)$ 的迭代在换元之后的形式下如何表达?
先从二次迭代开始,我们的目标是在 $f(f(x))$ 中凑出$f(\varphi^{-1}(t))$ 这样的形式。
如果我们把二次迭代 $f(f(x))$ 看成一个复合函数,它的外层函数的自变量 $x'=f(x)$ ,我们对这个 $x'$ 也做一次换元: $t'=\varphi(x')=\varphi(f(\varphi^{-1}(t)))$ 。
有没有感觉这个形式和 $x'=f(x)$ 很像?左边都是下一次迭代的自变量,右边都是上一次迭代的自变量。
于是我们令 $g(t)=\varphi(f(\varphi^{-1}(t)))$ ,接着计算 $g(t)$ 的迭代:
$\begin{align} g(g(t))&=\varphi(f(\varphi^{-1}(\varphi(f(\varphi^{-1}(t))))))\\ &=\varphi(f(f(\varphi^{-1}(t)))) \end{align}\\$
也就是说, $g^{(2)}(t)=\varphi(f^{(2)}(\varphi^{-1}(t)))$ 。同理,可以由数学归纳法证明, $g^{(n)}(t)=\varphi(f^{(n)}(\varphi^{-1}(t)))$ 。这就是迭代在换元法下的表达。
接下来,我们总结一下上面的内容,提出函数相似的概念。
对于两个函数 $f(x)$ 和 $g(x)$ ,如果存在一个函数 $\varphi(x)$ 及其反函数 $\varphi^{-1}(x)$ ,使得 $g(x)=\varphi(f(\varphi^{-1}(x)))$ ,则称$f(x)$ 与 $g(x)$ 通过 $\varphi(x)$ 相似,记作 $f\ \mathop{\sim}\limits^{\varphi}\ g $ ,其中 $\varphi(x)$ 称为桥函数。
刚才我们已经证明了函数相似的一个性质:如果 $f\ \mathop{\sim}\limits^{\varphi}\ g $ ,那么 $f^{(n)}\ \mathop{\sim}\limits^{\varphi}\ g^{(n)} $ 。
函数相似还有一个与不动点相关的性质。
对于 $g(x)$ 的不动点 $x_0$ ,有 $x_0=g(x_0)=\varphi(f(\varphi^{-1}(x_0)))$ ,于是 $\varphi^{-1}(x_0)=f(\varphi^{-1}(x_0))$ ,故 $\varphi^{-1}(x_0)$ 是 $f(x)$ 的不动点。这表明,$f(x)$ 与 $g(x)$ 的不动点一一对应。
不动点法
讲了这么多,终于到我们的重头戏了——缝合(误)。
把我们刚才的一系列概念综合起来,就得到了求解函数迭代的不动点法。
当我们要求解一个比较复杂的函数 $f(x)$ 的迭代时,可以去寻找一个与之相似但形式更简单的函数 $g(x)$ ,通过计算 $g^{(n)}(x)$ ,再根据 $g^{(n)}(x)=\varphi(f^{(n)}(\varphi^{-1}(x)))$ ,得出 $f^{(n)}(x)=\varphi^{-1}(g^{(n)}(\varphi(x)))$ 。
那么,为什么这种方法要叫做不动点法呢?因为我们可以通过不动点来构造一些简单的 $g(x)$ 。
什么样的 $g(x)$ 算简单呢?当然是迭代容易计算的函数就是简单函数。最常见的就是两类: $g(x)=x+b$ 和 $g(x)=kx$ (其中 k, b 为常数)。不难发现,这两类函数对应的是等差数列和等比数列的递推公式。
接下来我们分析一下这两类函数的不动点。(这里需要允许一些不太严谨的描述,比如未加定义地引入无穷大及其直观的运算规律。)前者 $g(x)=x+b$ 的不动点是 $\pm\infty$ ,而后者 $g(x)=kx$ 的不动点是 0 和 $\pm\infty$ 。
按照前文所说的函数相似的性质, $f(x)$ 的不动点要和 $g(x)$ 一一对应,也就是对于 $f(x)$ 的不动点 $x_0$ ,有 $\varphi(x_0)$ 是 $g(x)$ 的不动点。如果只考虑不动点之间的对应关系,我们可以这样简单地构造一个 $\varphi(x)$ :
- 如果 $f(x)$ 有唯一不动点 $x_0$ ,令 $\varphi(x)=\frac{1}{x-x_0}$ 。这样 $\varphi(x_0)=\infty$ 是 $g(x)=x+b$ 的不动点。
- 如果 $f(x)$ 有两个不动点 $x_1$ 和 $x_2$ ,令 $\varphi(x)=\frac{x-x_1}{x-x_2}$ 。这样两个不动点分别被映射到 0 和 $\infty$ ,是 $g(x)=kx$ 的不动点。
神奇的是,即使是仅考虑了不动点的情形,这样构造的 $\varphi(x)$ 还是能简化一大类 $f(x)$ (主要是分式函数)。
不动点法在数列中的应用
让我们隐藏掉中间的过程,来看看不动点法应用到数列上是怎样的。
- 找不动点。只需要简单地把递推公式里的 $a_n$ 和 $a_{n+1}$ 都换成 $x$ ,再求解这个方程,得到的结果就是不动点。
- 换元。按照上文的方法构造 $b_n=\frac{1}{a_n-x_0}$ 或者 $b_n=\frac{a_n-x_1}{a_n-x_2}$ ,代入原递推公式,化简得到 $\left\{ b_n \right\}$ 的递推关系,从而解出其通项公式。
- 求解。利用 $a_n$ 和 $b_n $ 之间的关系,解出 $\left\{a_n\right\}$ 的通项公式。
现在在看看开头的例题,是不是明白了许多呢?
不动点法的局限性
不动点法虽然有时候很好用,但是也经常会遇到失灵的情况,包括但不限于:
- 求解不动点时无解。
- 代换之后的数列并没有一个相对简单的形式。
这时候,就说明这个问题并不适合用不动点法解决。
而且,因为不动点法看起来太过于投机取巧,很多问题都会刻意地限制不动点法的套用。这个时候一定要及时更换思路,不能钻牛角尖。
没有评论