查看“︁高中数学/不等式与数列/不动点法”︁的源代码

== 阅读指南 ==
[[File:Crystal Clear app gnome.png | Crystal Clear app gnome | 50px]]

在前面[[高中数学/不等式与数列/一阶递推数列及通项公式的求解|一阶递推关系的求解]]章节中我们已经知道，对于<math>a_{n+1} = 2 a_n + 3</math>这样的数列，我们可以将其改写为<math>a_{n+1} + 1 = 2(a_n + 2)</math>，从而将<math>\{a_n + 2\}</math>整体地当作一个等比数列套用公式。如果系数更麻烦一点，比如对于<math>a_{n+1} = 2 a_n + 4</math>这样的数列，原则上还是可以拆分常数，然后在等号的左右两边分别构造出等比数列。但是此时的常数如何拆分不那么容易直接尝试出来。一个比较容易想到的办法是采用待定系数法，先提前假设构造好的数列具有<math>a_{n+1} + d = 2(a_n + d)</math>的形式，初步化简后再和原来的<math>a_{n+1} = 2 a_n + 4</math>放在一起，比较各对应项的数值，即可确定与原关系式匹配的d值。

本节介绍的不动点法则是确定这个待定构造系数的更直接、简便的方法。不动点法可以解决形如<math>a_{n+1} = p a_n + q</math>的非齐次一阶常系数线性递推关系式的构造，也可以解决形如<math>a_{n+1} = \frac{A a_n + B}{C a_n + D}</math>的一阶常系数分式线性递推关系式的构造。除了这2种类型的递推式之外，少数可以转换为这2种情形的特例也可以使用不动点法求解构造系数。

这类不动点法的主要特点就是：
* 适用条件容易判断
* 用起来爽（对于不少常见情况而言）
* 解释起来很麻烦

本节花费了不少篇幅提及这些方法背后的由来，其中多半不可避免地会介绍一些来自后续数学课程中的背景知识。如果读者对于不动点法的使用完全没有经验，建议先接触一些应用不动点解题的例题。了解不动点法解题的大致流程后，再根据需要了解其背后的由来，不然容易对其中的一些推敲思路产生困惑。

=== 考试要求 ===
不动点法并不被列入普通高中的考试大纲，因此在常规的高中考试中不能直接声明是在借助不动点法解题。但是利用不动点法的确可以快速求出所需的待定系数，识别适合使用不动点的问题并能快速地在草稿纸上用此方法求出所需的系数还是比较有必要掌握的。

== 基础知识 ==
=== 不动点的概念 ===
<blockquote style="padding: 1em; border: 2px dotted;">
<font color="#008000">定义：对于1个给定的函数<math>f(x)</math>，能使<math>f(x) = x</math>成立的自变量取值<math>x = x_0</math>叫做该函数的'''不动点（fixed point）'''。<ref name="梁训果_最后一题">{{cite book |title=高考数学最后一题 |author1=梁训果 |author2=王永明 |editor= |publisher=重庆出版集团 |series=万试无忧系列丛书 |edition=5 |isbn=978-7-5366-8521-5 |section=第一部分 数列相关问题 |pages= |language=zh-cn |date=2011}}</ref><ref name="蔡小雄_高妙_2009_不动点法">{{cite book |title=更高更妙的高中数学思想与方法 |author=蔡小雄 |editor1=董德耀 |editor2=沈国明 |publisher=浙江大学出版社 |location=中国杭州天目山路148号 |series= |edition=1 |isbn=978-7-308-06993-9 |section=第4章“用竞赛策略优化高考解题”第4.1节“熟悉递推方法”第4.1.3小节“不动点法” |pages=241-243 |language=zh-cn |date=2009}}</ref>

与递推式形式一致的函数也被叫做递推关系式的'''特征函数'''（'''characteristic function'''）或'''背景函数'''<ref name="梁训果_最后一题" />。递推式特征函数的不动点也叫做递推式的不动点。不动点在对应函数图象上的对应点也叫做'''函数图象的不动点'''<ref name="蔡小雄_高妙_2009_不动点法" />。
</font>
</blockquote>

在解决高中数列递推问题时，我们讨论的不动点都是可逆函数的不动点。可逆函数的不动点有以下特点：
* 如果<math>(x_0, y_0)</math>是可逆函数<math>y = f(x)</math>的不动点，等价于<math>(y_0, x_0)</math>是其反函数<math>x = f^{-1}(y)</math>的不动点。换句话说，可逆函数的不动点与其反函数的不动点是一一对应的。
* 函数的不动点坐标具有<math>(x_0, x_0)</math>的形式，即不动点一定是函数图象与特殊直线<math>y = x</math>的交点。
* 如果把可逆函数<math>y = f(x)</math>与其反函数<math>x = f^{-1}(y)</math>的图象画在同一个直角坐标系中，则它们的图象交点都是不动点。<!--  不一定，比如
 f(x)=(1/16)^x 
與其反函數
有 （1/4, 1/2) (1/2, 1/4) 之交點 -->

不动点本身是[[w:拓扑学|拓扑学]]的知识点，表示物体或空间在某种拓扑变换的作用下，仍保持固定不动的点。它的几何意义是函数图象与恒等变换直线<math>y = x</math>交点的横坐标。但是它也出现在有关数列的解题方法中。

=== 利用不动点简化一阶常系数线性递推关系式的通项求解 ===
在从递推式<math>a_{n+1} = p a_n + q \quad (p \neq 1)</math>构造等比数列的过程中，使用待定系数法所求的需要分配到等式两边的数值，刚好就可以用对应函数<math>f(x) = p x + q</math>的不动点来确定。我们先给出用不动点法解决这类数列的通用解题步骤，然后结合例题说明它的具体运用。

<blockquote style="padding: 1em; border: 2px dotted;">
[[File:Crystal Project Warehause.png |Crystal Project Warehause | 50px]]
用不动点法可以求出一阶线性递推数列<math>a_{n+1} = p a_n + q</math> (其中p和q为常数，且<math>p \neq 1</math>)的通项的一般式<ref name="李世杰_2008_不动点法">{{cite book |title=递推与递推方法 |author=李世杰 |editor1=黄娟琴 (责任编辑) |editor2= 许佳颖 (文字编辑) |publisher=浙江大学出版社 |location=中国杭州天目山路148号 |series=高中数学竞赛专题讲座 |edition=1 |isbn=978-7-308-06087-5 |section=第2章“递推数列”第1节“递推数列的定义” |pages=26 |language=zh-cn |year=2008}}</ref>。其主要步骤为：<br />
(1) 写出与<math>a_{n+1} = p a_n + q</math>对应的特征函数<math>f(x) = p x + q</math><br />
(2) 求出函数<math>f(x)</math>的不动点<math>x_0</math>，即求解方程<math>f(x_0) = x_0 \Rightarrow p x_0 + q = x_0</math>，解得：<math>x_0 = \frac{q}{1-p}</math><br />
(3) 在原始<math>a_{n+1} = p a_n + q</math>的等号两边同时减去刚才求出的不动点<math>x_0</math>，即：<br />
:<math>a_{n+1} - x_0 = p a_n + q - x_0 \quad \Rightarrow \quad a_{n+1} - x_0 = p (a_n + \frac{q - x_0}{p}) \quad \Rightarrow \quad a_{n+1} - x_0 = p (a_n - x_0)</math><br />
(4) 将<math>a_n - x_0</math>整体地看作一个等比数列求解，求出<math>a_n - x_0</math>的表达式后，<math>a_n</math>的表达式自然也就知道了。
</blockquote>

可以证明，这样求得的最终结果形式为<math>a_n = a_1 p^{n-1} + \frac{q(1-p^{n-1})}{1-p}</math><ref name="李世杰_2008_不动点法" />。但是实际上，解题时并不需要记住这个最终形式，只需要记住上面的几个关键步骤即可。

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：如果求出的不动点形式比较复杂（例如算出的解带着根号跑），此时使用不动点法对于简化数列构造时的系数运算也无法提供太多帮助。求解兔子数列的通项公式问题就是一个例子。

=== 一阶常系数线性递推关系式的不动点解法由来 ===
关于在一阶常系数线性递推关系式的通项求解中，为什么会与不动点的概念产生联系，我们在这里给予一个比较简单的论证。

先设<math>a_{n+1} = k a_n + d</math><br />
再假设我们期待的构造好的等比数列形式<math>a_{n+1} - p = k (a_n - p)</math><br />
用后一式的两端同时对前一式的两端作差，可得：<br />
<math>
\begin{array}{l}
(a_{n+1} - p) - a_{n+1} = k (a_n - p) - (k a_n + d) \\
\Rightarrow - p = - k p - d \quad \Rightarrow \quad p = k p + d
\end{array}
</math><br />
最后一个式子显然说明所需要的常数p就是函数<math>f(x) = k x + d</math>的不动点。

从几何上讲，从截距不为零的一次函数（对应于上述非齐次一阶线性递推关系式）变形为正比例函数（对应于构造出来的等比数列满足的关系式）的变换就是一种图象平移操作，而此类函数的不动点提供了同时沿y轴方向和x轴方向进行图象平移的距离参考值。

=== 一阶常系数分式线性递推关系式的概念及其通项的待定系数解法 ===
形如<math>a_{n+1} = \frac{A a_n + B}{C a_n + D}</math>的一阶常系数分式线性递推关系式的构造也可以借助不动点的求解实现<ref name="蔡小雄_高妙_2009_不动点法" />。

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：我们先在本小节简述如何使用待定系数法求这类分式线性递推式通项的大体思路，再在后面的小节介绍基于不动点法的优化和解题实例，最后谈谈在这类情形下可以使用不动点法的原理。

<blockquote style="padding: 1em; border: 2px dotted;">
<font color="#008000">定义：具有以下形式的递推式<math>a_{n+1} = f(a_n)</math>叫做'''常系数分式线性递推关系'''：<br />
<math>a_{n+1} = \frac{A a_n + B}{C a_n + D} \quad (n \in \mathbb{N}^+, A, B, C, D \in \mathbb{R}, AD - BC \neq 0)</math>
</font>
</blockquote>

=== 利用不动点简化一阶常系数分式线性递推关系式的通项求解 ===
我们接下来从不动点的角度，指出这种常系数分式线性递推关系的通项公式求解方法。

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：本小节前半部分展示的代数变形过程比较冗长罗嗦，主要就是讲述了2种情况下最基本的分类讨论，外加上常见优化步骤的思路由来。没有耐心的读者可以先看结论和具体例题，然后有时间再回过头来大致浏览一下这些纯字母化的运算和论证。

设函数<math>f(x) = \frac{A x + B}{C x + D}</math>满足<math>x, A, B, C, D \in \mathbb{C}, AD - BC \neq 0</math>，其不动点为<math>x = \lambda</math>。
其不动点满足的方程<math>\lambda = \frac{A \lambda + B}{C \lambda + D}</math>可能只有1个解，也可能有2个不同的解（不同的实数根或不同的虚数根）<ref name="钟玉泉_2004_分式线性变换" />。

如果<math>x_0</math>为以上方程的任何一个根（从而<math>x_0</math>也是函数的不动点），那么可以先对原递推式两边同时减去不动点：<br />
<math>a_{n+1} - x_0 = \frac{A a_n + B}{C a_n + D} - x_0 = \frac{(A - Cx_0)(a_n - x_0)}{C a_n + D}</math><br />
再对上式两侧同时颠倒可得：<br />
<math>\frac{1}{a_{n+1} - x_0} = \frac{C a_n + D}{(A - Cx_0)(a_n - x_0)} = \frac{C x_0 + D}{A - C x_0} \frac{1}{a_n - x_0} + \frac{C}{A - C x_0}</math><br />
由上式可知此时<math>\{\frac{1}{a_n - x_0}\}</math>整体来说是一个一阶常系数线性递推数列，且包含有取值为常数的非齐次项。

如果不动点方程<math>\lambda = \frac{A \lambda + B}{C \lambda + D}</math>的2个根是重根，则有<math>x_1 = x_2 = \frac{A-D}{2C}</math>且<math>\frac{C x_1 + D}{A - C x_1} = 1</math>。此时可以继续化简：<br />
<math>\frac{1}{a_{n+1} - x_0} = \frac{C x_0 + D}{A - C x_0} \frac{1}{a_n - x_0} + \frac{C}{A - C x_0} = \frac{1}{a_n - x_0} + \frac{C}{A - C x_0}</math><br />
即<math>\{\frac{1}{a_n - x_0}\}</math>变为以<math>\frac{1}{a_1 - x_0}</math>为首项、<math>\frac{C}{A - C x_0}</math>为公差的等差数列，易知其通项为：<br />
<math>\frac{1}{a_n - x_0} = \frac{1}{a_1 - x_0} + \frac{2C (n-1)}{A + D}</math>
既然在这种情形下都已经得到<math>\frac{1}{a_n - x_0}</math>的解析式，从而<math>a_n</math>的解析式也容易知道了。

如果不动点方程<math>\lambda = \frac{A \lambda + B}{C \lambda + D}</math>有2个相异的根，那么最直接的想法是只能麻烦一点，针对得到的常系数线性递推式再使用不动点法构造一次：<br />
<math>\frac{1}{a_{n+1} - x_1} + \frac{1}{x_1 - x_2} = \frac{A - C x_1}{A - C x_2} (\frac{1}{a_n - x_1} + \frac{1}{x_1 - x_2})</math><br />
此时<math>\{\frac{1}{a_n - x_1} + \frac{1}{x_1 - x_2}\}</math>构成公比为<math>\frac{A - C x_1}{A - C x_2}</math>的等比数列，即：<br />
<math>
\begin{align}
\frac{1}{a_n - x_1} + \frac{1}{x_1 - x_2} = (\frac{1}{a_n - x_1} + \frac{1}{x_1 - x_2})(\frac{A - C x_1}{A - C x_2})^{n-1} \\
\Rightarrow \frac{1}{a_n - x_1} = (\frac{1}{a_n - x_1} + \frac{1}{x_1 - x_2})(\frac{A - C x_1}{A - C x_2})^{n-1} - \frac{1}{x_1 - x_2} \\
\Rightarrow a_n = \frac{x_2 (a_1 - x_1)(A - C x_1)^{n-1} - x_1 (a_1 - x_2)(A - C x_2)^{n-1}}{(a_1 - x_1)(A - C x_1)^{n-1} - (a_1 - x_2)(A - C x_2)^{n-1}}
\end{align}
</math><br />

如果方程有2个不等的根<math>x_1</math>和<math>x_2</math>（是不同的实数根或不同的虚数根都行），此时还有一种基于不动点但是构造方向与上述思路有一些差异的解法。先在原递推式的两侧分别减去这2个根，可以得到：<br />
<math>
\left\{
\begin{array}{l}
 a_{n+1} - x_1 = \frac{(A - Cx_1)(a_n - x_1)}{C a_n + D} \\
 a_{n+1} - x_2 = \frac{(A - Cx_2)(a_n - x_2)}{C a_n + D}
\end{array}
\right.
</math><br />
如果观察上述2个式子，可以发现它们的右侧都有相同的分母，且右侧的分子形式非常相似，最好能利用这个相同点去掉它们的分母。于是不妨对上述2个式子的两端同时作商（相除）可得：<br />
<math>\frac{a_{n+1} - x_1}{a_{n+1} - x_2} = k \frac{a_n - x_1}{a_n - x_2}</math>，其中<math>k = \frac{A - C x_1}{A - C x_2}</math>。<br />
易知此时<math>\{\frac{a_n - x_1}{a_n - x_2}\}</math>整体来说是一个以<math>\frac{a_1 - x_1}{a_1 - x_2}</math>为首项、k为公比的等比数列，所以得到<math>\{\frac{a_n - x_1}{a_n - x_2}\}</math>的通项公式：<br />
<math>\frac{a_n - x_1}{a_n - x_2} = \frac{a_1 - x_1}{a_1 - x_2} k^{n-1} = (\frac{A - C x_1}{A - C x_2})^{n-1} \frac{a_1 - x_1}{a_1 - x_2}</math><br />
既然已经得到<math>\frac{a_n - x_1}{a_n - x_2}</math>的解析式，从而<math>a_n</math>的解析式也容易知道了。<br />
这种方法此时可以更快地得到同样的最终结果：<br />
<math>a_n = \frac{x_2 (a_1 - x_1)(A - C x_1)^{n-1} - x_1 (a_1 - x_2)(A - C x_2)^{n-1}}{(a_1 - x_1)(A - C x_1)^{n-1} - (a_1 - x_2)(A - C x_2)^{n-1}}</math>

<blockquote style="padding: 1em; border: 2px dotted;">
[[File:Crystal Project Warehause.png |Crystal Project Warehause | 50px]]
综上所述，我们可以将常系数分式线性递推式的通项求解思路简化如下<ref>{{cite journal |title=用不动点法求分式型递推数列的通项 |author=赵嘉璐 |publisher=数学学习与研究 |pages=107 |language=zh-cn |year=2018 |issue=8月}}</ref>：
* 当只有1个不动点时，可以对原递推式的两边同时减去不动点，然后再同时取倒数，进而转化为等差数列求解。
* 当有2个相异的不动点时，可以先对原递推式的两边同时减去第1个不动点并取倒数，再对原递推式的两边同时减去第2个不动点并取倒数，然后将分别得到的2个式子作商，进而转化为等比数列求解。
</blockquote>

=== 分式线性变换的概念与分式线性递推式的不动点解法由来 ===
<blockquote style="padding: 1em; border: 2px dotted;">
<font color="#008000">定义：具有以下形式的函数<math>f: \mathbb{C} \rightarrow \mathbb{C}</math>叫做'''分式线性变换'''（'''linear fractional transformation'''）：<br />
<math>f(x) = \frac{A x + B}{C x + D} \quad (A, B, C, D \in \mathbb{C}, AD - BC \neq 0)</math>

因为德国数学家[[w:奥古斯特·费迪南德·莫比乌斯|奥古斯特·莫比乌斯]]曾对其进行过大量研究，所以分式线性变换也叫做'''[[w:莫比乌斯变换|莫比乌斯变换]]'''（'''Möbius transformation'''）。<ref name="钟玉泉_2004_分式线性变换">{{cite book |title=复变函数论 |author=钟玉泉 |editor1=王瑜 (策划编辑) |editor2=丁鹤龄 (责任编辑) |others=朱慧芳 (责任校对) |publisher=高等教育出版社 |location=中国北京市西城区德外大街4号 |series= |edition=1 |isbn=7-04-012943-4 |section=第7章“共形映射”第2节“分式线性变换” |pages=283-289 |language=zh-cn |date=2004}}</ref>
</font>
</blockquote>

通过简单的分式分解，易知莫比乌斯函数可以分解为以下形式：
<math>f(x) = \frac{BC - AD}{C} \frac{1}{Cx + D} + \frac A C</math>
由于我们只考虑自变量值取实数的情形，因此可以对于特定的一组系数可以画出函数的图像。而由上述表达式的图象性质可知，分式线性变换是可逆的。

容易验证以下性质：
* 分式线性变换<math>f(x) = \frac{A x + B}{C x + D} \quad (AD - BC \neq 0)</math>的逆变换（即反函数）为<ref name="钟玉泉_2004_分式线性变换" />：
:<math>x = \frac{-Dy + B}{Cy - A}</math>
* 一次函数是特殊的分式线性变换<ref name="钟玉泉_2004_分式线性变换" />。
* 分式线性映射之间的复合结果仍然是分式线性变换<ref name="钟玉泉_2004_分式线性变换" />。
* 如果<math>x = x_0</math>是分式线性变换<math>f(x)</math>的不动点，等价于<math>f(x_0)</math>是其反函数的不动点。这是因为可逆函数的不动点与其反函数的不动点是一一对应的。

我们下面先通过一种计算量较少的思路来说明使用待定系数法时，第一步减去的常数一定是其不动点的原因。<br />
按照待定系数法的思路，假定对分式线性变换解析式的<math>f(x)</math>两侧同时减去某个合适的常数P再同时取倒数后，能得到形式一致的分母。先做第一步减法，得：<br />
<math>a_{n+1} - P = \frac{A a_n + B}{C a_n + D} - P = \frac{A a_n + B - PC a_n - DP}{C a_n + D} = \frac{(A - PC) a_n + (B - DP)}{C a_n + D}</math><br />
要使上面的式子取倒数后的分母满足要求，由于分母取倒数前是位于分子的位置，基于前面的解题实例可知，我们只需要保证上式最左边的量与最右边的分子形式相似即可。<br />
即只需要使<math>a_{n+1} - P</math>与<math>(A - PC) a_n + (B - DP)</math>的对应系数成相同比例即可。即：<br />
<math>\frac{1}{A - PC} = \frac{-P}{B - DP}</math>，解得：<math>P = \frac{B - DP}{CP - A}</math>。<br />
显然，这个所需的P值是<math>f(x)</math>的反函数的不动点。根据前面总结的性质，可知P也是<math>f(x)</math>的不动点。<br />
即对<math>f(x)</math>两侧同时减去其不动点后，再取同时倒数，就一定能构造出一次的常系数非齐次递推式。

=== 从同胚变换的角度理解函数迭代与递推式求解 ===
也可以从函数同胚变换（也就是函数相似变换）的角度出发，来理解函数的多重迭代与分式线性递推式的求解。不动点法在这两类问题中都有登场出现。首先由于一次函数属于特殊的分式线性变换，而且分式线性变换是可逆变化，所以自然想到能否将分式线性递推式还原为某种更简单的一次线性递推式的形式。求出与之相关的一次线性递推式的迭代结果后，再利用逆变换反推出原递推式的多次迭代结果。另一方面，我们已经知道使用不动点法可以简化一次线性递推式的求解，我们希望将不动点也整合到分式线性变换还原为线性递推式的系数配凑过程中。

<blockquote style="padding: 1em; border: 2px dotted;">
<font color="#008000">
使得<math>f(x)</math>可以与另一个函数<math>g(x)</math>建立下列联系的可逆函数<math>T(x)</math>叫做'''桥函数'''
<ref name="小丛书_函数与函数方程">{{cite book |title=函数与函数方程 |author1=熊斌 |author2=朱臻 |author3=苏勇 |editor1=孔令志 (项目编辑) |editor2=朱洪敏 (审读编辑) |publisher=华东师范大学出版社 |location=中国上海市中山北路3663号 |series=数学奥林匹克小丛书·高中卷 |edition=2 |isbn=978-7-5617-9170-7 |section=第6章“函数的迭代”第6.2节“f^n (x)的求法” |pages=86-95 |language=zh-cn |year=2012}}</ref>：<br />
<math>f(x) = T^{-1}(g(T(x)))</math>

此时<math>f(x)</math>和<math>g(x)</math>叫做关于桥函数<math>T(x)</math>的一对'''相似函数'''<ref name="小丛书_函数与函数方程" />，或者说<math>f(x)</math>和<math>g(x)</math>关于桥函数<math>T(x)</math>互为相似函数。用拓扑学术语来说，桥函数是一种'''[[w:同胚|同胚]]'''（'''homeomorphism'''）变换，它建立了<math>f(x)</math>和<math>g(x)</math>之间的'''拓扑共轭'''（'''topological conjugacy'''）。
</font>
</blockquote>

桥函数是计算函数迭代或巧妙构造数列的辅助函数。通过找到合适的桥函数，把不易得到迭代公式的<math>f(x)</math>变为容易得到迭代公式的形式更简单的<math>g(x)</math>，计算完<math>g(x)</math>的n次迭代结果后，再使用桥函数的逆变换即可得到<math>f(x)</math>的n次迭代式。这种思路把函数迭代的问题转化为桥函数的寻找与研究问题。

可以通过数学归纳法验证函数<math>f(x)</math>的上述相似性（也就是拓扑共轭性）满足以下规律（<math>T(x)</math>为<math>f(x)</math>的桥函数，<math>g(x)</math>是其共轭，下标表示迭代计算的次数）<ref name="小丛书_函数与函数方程" />：<br />
<math>f_n (x) = T^{-1} (g_n (T(x)))</math>

[[File:Crystal Clear app kdict.png | Crystal Clear app kdict | 50px]]
知识背景：将函数借助一个可逆的辅助函数，变换到另一个更容易求解或更容易研究的形式，在数学与物理学的许多分支中都是常见思想。[[w:矩阵对角化|矩阵对角化]]、[[w:傅立叶变换|傅立叶变换]]、[[w:Z变换|Z变换]]、[[w:卷积|卷积]]等技巧都是这类思想的体现。用[[w:泛函分析|泛函分析]]的术语来说，函数可以看成抽象空间中的点，如果一个函数直接研究起来不方便，我们就可以用可逆变换将它挪到其它更简单明了的空间中再研究。变换的可逆性保证了函数本身的某些关键特性在某些恰当选取的空间中并不会改变太多，解决问题以后还可以把结果再变回到原来的空间。

了解了桥函数方法的转换思想，下面使用不动点法的动机就是借助不动点套出桥函数可能满足的性质，以便确定所需桥函数中的未知待定系数。只要确定了桥函数的各个细节，就可以通过相似变换的方法巧妙地得到原函数的n次迭代式。

<blockquote style="padding: 1em; border: 2px dotted;">
[[File:Crystal Project Warehause.png |Crystal Project Warehause | 50px]]
假设<math>f(x) = T^{-1}(g(T(x)))</math>，且<math>x_0</math>是<math>f(x)</math>的不动点，那么<math>T(x_0)</math>一定也会是<math>g(x)</math>的不动点<ref name="小丛书_函数与函数方程" />。这说明如果我们求出了<math>f(x)</math>的不动点，并且有了简单可行的<math>T(x)</math>，那么<math>g(x)</math>的不动点也就知道了。

通常为了便于求解<math>g(x)</math>的n次迭代式，可以尝试将<math>g(x)</math>取为下列形式<ref name="小丛书_函数与函数方程" />：
* <math>g(x) = x + a</math>
* <math>g(x) = ax</math>
* <math>g(x) = ax^2</math>
* <math>g(x) = ax^3</math>
对于这几种情况，<math>g(x)</math>的不动点为0或<math>\infty</math>。此时如果<math>f(x)</math>只有唯一的不动点a，可以考虑取<math>g(x) = x-a</math>或<math>g(x) = \frac{1}{x-a}</math>；如果<math>f(x)</math>有2个相异的不动点a和b，则可以考虑取<math>g(x) = \frac{x-a}{x-b}</math>。
</blockquote>

就分式线性变换的例子来说，如果我们先求出了<math>f(x) = \frac{A x + B}{C x + D}</math>的不动点<math>x_0</math>，那么如果还能通过尝试一些特例猜出合适的桥函数具有<math>T(x) = \frac{1}{x - k}</math>的形式，并且目标函数是一次函数，那么<math>p = T(x_0)</math>也一定是一次函数<math>g(x) = x + b</math>的不动点。即有下列关系式成立：<br />
<math>p = g(p) \quad \Rightarrow \quad p = p + b</math><br />
我们先不急着移项。因为我们可以从包含无穷大的[[w:扩展实数线|扩展实数线]]或[[w:扩充复平面|扩充复平面]]上考虑问题，易知从方程<math>\lambda = \lambda + b \quad (b \neq 0)</math>解出的唯一不动点是<math>\lambda = \infty</math>。所以<math>p = \lambda = \infty</math>，即可反推：<br />
<math> T(x_0) = p = \infty \quad \Rightarrow \quad \frac{1}{x_0 - k} = \infty \quad \Rightarrow \quad k = x_0</math><br />
所以所求的关键待定系数k就是原函数<math>f(x)</math>的不动点<math>x_0</math>。

=== 其它可以转换为上述情形的特例 ===
对于二次函数或包含二次项的分式函数，除了恰巧可以用简单的配方法将二次项配凑进某个完全平方式的情形，一般都没有什么好办法获得n次迭代后的简洁表达式<ref name="小丛书_函数与函数方程" />。

=== 分式线性递推的其它方法概述 ===
其它可以解决分式线性递推式的方法还包括[[高中数学/不等式与数列/常系数线性递推数列|转化为二阶常系数线性递推数列]]和[[高中数学/不等式与数列/多元递推关系式|多元递推与矩阵方法]]。

== 计算机求解 ==
=== Mathematica ===
本节介绍的一阶常系数非齐次线性递推式和分式线性递推式都可以用[[w:Wolfram Mathematica|Mathematica软件]]提供的“RSolve”命令求解出通项公式。我们在这里分别用Mathematica展示2种递推式的通项公式求解方法。它的更多递推式求解用法还会在[[高中数学/不等式与数列/常系数线性递推数列|常系数线性递推数列]]章节中继续补充。

求解差分方程<math>a_1 = 1, a_{n+1} = 2 a_n + 3</math>的示例：
<syntaxhighlight lang="Mathematica">
RSolve[{a[n + 1] == 2 a[n] + 3, a[1] == 1}, a[n], n]; (* 在Mathematica中表示相等，需要2个"="在一起连用 *)
</syntaxhighlight>
在新单元格（cell）输入完上述命令后，一般按组合键Shift + Enter即可得到结果。

求解分式线性差分方程<math>a_1 = 1, a_{n+1} = \frac{a_n + 2}{3 a_n + 4}</math>的示例：
<syntaxhighlight lang="Mathematica">
RSolve[{a[n + 1] == (a[n] + 2) / (3 a[n] + 4), a[1] == 1}, a[n], n]; (* 在Mathematica中表示相除，需要使用"/"符号 *)
</syntaxhighlight>
此题的答案很复杂很可怕哦~

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：如果RSolve命令没有输入错误，但是执行后出现“RSolve::deqn: Equation or list of equations expected instead of True in the first argument True.”一类的报错信息，一般是由于没有清除同名[[w:标识符|标识符]]中的已有信息。如果是这种情况：(1)可以先在其它地方输入独立命令“ClearAll[a]”清除标识符a中的内容，然后重新执行RSolve命令；(2)也可以改用除a以外的其它未使用过的标识符来命名要求解的数列。

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：“RSolve”命令中的“R”是递推（recurrence relation）、递归（recursion）的意思。它与“Resolve”命令拼写相似，但功能不同。Resolve是用于化简约束条件的，例如可以求解一些不等式或不等式组。

<!-- 本小节例题1 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题1：
已知在数列<math>\{a_n\}</math>中，满足<math>a_1 = 1, a_{n+1} = 2 a_n + 3</math>，使用Mathematica求它的通项公式。<br />

<div class="collapsible solutions" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243);">
 <p>解答：<br />
 在Mathematica软件中输入命令（因为只有一行命令，分号此时可以不写）：<br />
 <code>RSolve[{a[n + 1] == 2 a[n] + 3, a[1] == 1}, a[n], n];</code><br />
 然后按组合键Shift + Enter即可得到结果为：<math>a_n = \frac 1 2 ((1 - \sqrt{2})^n + (1 + \sqrt{2})^n)</math>。
 </p>
</div>
<div class="collapsible finalAnswer" style="clear both; border: thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243); color: red;">
 <p>答案：<math>a_n = -3 + 2^{1+n}</math>。</p>
</div>

<!-- 本小节例题2 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题2：
已知数列<math>\{a_n\}</math>满足<math>a_1 = 1, a_{n+1} = \frac{2 a_n + 3}{a_n + 4}</math>，使用Mathematica求它的通项公式。<br />

<div class="collapsible solutions" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243);">
 <p>解答：<br />
 命令用法示例：<br />
 <code>RSolve[{a[n + 1] == (2 a[n] + 3) / (a[n] + 4), a[1] == 1}, a[n], n];</code><br />
 然后按组合键Shift + Enter即可得到结果为：<math>a_n = \frac 1 2 ((1 - \sqrt{2})^n + (1 + \sqrt{2})^n)</math>。
 </p>
</div>
<div class="collapsible finalAnswer" style="clear both; border: thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243); color: red;">
 <p>答案：<math>a_n = \frac{3((-1)^n + (-1)^{1+n} 5^{1-n})}{3(-1)^n + (-1)^n 5^{1-n}}</math>。</p>
</div>

== 补充习题 ==
[[File:Crystal Clear app ksirtet.png | Crystal Clear app ksirtet | 50px]]
[[File:Crystal Clear app laptop battery.png | Crystal Clear app laptop battery | 50px]]

== 参考资料 ==
{{Reflist}}

== 外部链接 ==
{{Wikipedia|不动点}}
{{Wikipedia|莫比乌斯变换}}

{{DEFAULTSORT:fixed point method}}
[[category:数列]]
[[category:高中数学]]