学术：浅谈特征方程

引入

我们都熟悉斐波那契数列。

为了求数列的第项，我们知道的递归求法，我们知道的线性递推，我们还知道的矩阵快速幂解法。但是以上方法都是直接或间接的使用了前面的几项，而不能够优化到的直接计算第项本身。

而特征方程，就是处理这类问题的有力工具。

前排提示，本文中“数列”“函数”的区别是较为模糊的，因为我们注意他们的共同点。

数列其实就是函数上的离散选点，所以讲解和理解以函数为主。

介绍

为了方便理解和讲解，下面以二阶常系数线性齐次递推式作为模版。这个名字里涉及一些需要解释的内容：

二阶，指依赖前两项；
常系数，指为常数；
线性，指项均为一次项；
齐次，指不含常数项，均为一次项；
递推式，给定的是递推关系，通常给定要求的起始状态，但是方法不要求有起始状态；

我们解决的问题即为，已知递推关系与起始状态：

求的通项公式。

先看一个最简单的例子：斐波那契递推。

指数函数有一个性质，就是其某一点导数与该点函数值呈正比。其中最著名的，就是，他不仅成正比，而且就为它自己，这也就是的定义。
同样的，这类递推，包括斐波那契，都是类似“变化量正比于值”的，所以可以用指数函数对其进行刻画。
如果我们找到一个函数满足，我们就成功找到了一个底数使他的指数函数符合斐波那契的递推关系。
此时，我们在这个函数（或者某一个衍生的函数）上离散选点，就可以构造出这样一个满足递推关系的数列。如果选点的初始值满足的话，那么这就是标准的斐波那契数列。

所以问题就来到找出，这时特征方程开始发力了。

解得：

读者可以自己写个简单的程序验证一下，就像这样：

#include<bits/stdc++.h>
#define dwb double

using namespace std;

dwb r1 = (1.0 + sqrt(5.0)) / 2.0;
dwb r2 = (1.0 - sqrt(5.0)) / 2.0;

inline void test1() {
    cout << "--- test1 ---\n";
    dwb ans1 = 1.0;
    dwb ans2 = 1.0;
    while (ans1 <= 100000) {
        ans1 = ans1 * r1;
        printf("%.2lf\n", ans1);
    }
    while (fabs(ans2) >= 0.001) {
        ans2 = ans2 * r2;
        printf("%.2lf\n", ans2);
    }
    cout << '\n';
    return;
}

可以发现正是我们想要的，符合递推关系的底数，又被叫做特征根。但是我们无法得到标准的斐波那契数列，怎么办？

下面的内容强烈建议搭配的《线性代数的本质》最后一集，《抽象向量空间》食用。

我们都知道，函数就是一个无穷维的向量，而求导又是线性算子；
同理，数列也是一个向量，数列的差分也是线性算子；

这意味着，因为得到了两个线性无关函数，我们就可以通过他们的线性组合，制造出无穷多个函数，而这些函数又全部都满足斐波那契的递推性质的。

在这个空间之内，函数就是向量，而我们通过特征方程找到的就是一组基，这组基的核心就在于特征根。或许这就是“特征”这个名字的由来吧。

好，让我们回到数列上来回看我们的问题。现在就变成了，找到要求的数列的，也就是在这个向量空间内的一个向量。这个求解是很容易的，把边界值带入就可以了。

例题

若，求。

化简递推式：

设，得到特征方程：

解得：

设，由边界条件，代入得：

所以：

拓展

重根下解空间

刚刚的方程有两个实根，在一个二阶线性常系数齐次递推式的讨论范围内，足够提供一组基，来支持任意一个满足递推式的数列。但是如果有重根，只有一个基向量，怎么办？

直观来看，如果只定义了递推关系，其实是有无穷个符合的数列的，因为你可以任意指定初始状态，其本质上是对的任意指定。所以其实一定是有至少一对线性无关的的。

证明：如果为一个特征根，则一定是一个符合递推的，且与线性无关的函数。

证明确实是一个解

一个有重根的递推关系，其特征方程必然是 $²$ ，对应于递推关系： $²$ 。

将代入：

证毕。

证明和是线性无关的

$原命题$

由于，我们可以两边同除以，得到：
$₁ ₂$
$₁ ₂ ₁ ₁ ₂ ₁ ₂$

因此， $₁ ₂$ 是唯一解，故和线性无关。

结论

即使特征方程有重根，二阶递推关系的解空间依然是二维的。我们并没有失去一个解，共同构成了该解空间的一组完整的基。

这与二阶常系数齐次线性微分方程中出现重根的情况是完全平行的，那里的两个线性无关的解是 $ʳ ˣ$ 和 $ʳ ˣ$ 。离散数列中的完美地对应了连续函数中的。

复数根下解空间

没有实数根，代表有一对共轭复数根：

解的形式：

但是我们选择使用复数的三角表示法：

根据欧拉公式和棣莫弗定理，化简得实数通解形式：

（请不要问我这个，我不会他们的具体内容）

我们理解一下这个式子：

描述这个解的振荡，包括他的相位、频率；
是一个系数，描述这个解的指数增长和衰减：
- ，振幅指数级变大；（受迫？）
- ，振幅稳定，会形成周期；（简谐？）
- ，振幅指数级衰减；（阻尼？）

下面来一个例子，理解一下：

考虑；
算出特征方程为，没有实根；
共轭复数根：；
则有，振幅稳定，形成周期；
计算辐角；
通解：；
如果初始状态：，得到的结果就是：

这呈现出明显的周期，周期为。

下面是两个 AI 给出的振动增强和减弱的例子：

振荡增强

$ₙ ₙ ₋ ₁ ₙ ₋ ₂$

我们设 $₀$ , $₁$ 。

计算前几项：

$₂ ₁ ₀$
$₃ ₂ ₁$
$₄ ₃ ₂$
$₅ ₄ ₃$
$₆ ₅ ₄$
$₇ ₆ ₅$
$₈ ₇ ₆$

序列是：

虽然数列在正负之间来回摆动，但振动的幅度（绝对值）在不断变大。

特征方程： $²$
求解特征根：使用求根公式 $²$
计算模 R： $² ²$
结论：因为模。

振荡减弱

$ₙ ₙ ₋ ₁ ₙ ₋ ₂$

我们设 $₀$ , $₁$ 。

计算前几项：

$₂ ₁ ₀$
$₃ ₂ ₁$
$₄ ₃ ₂$
$₅ ₄ ₃$
$₆ ₅ ₄$
$₇ ₆ ₅$
$₈ ₇ ₆$

序列是：

数列同样在正负之间摆动，但振动的幅度在不断缩小，并逐渐趋近于0。

特征方程： $²$
求解特征根：
计算模 R： $² ²$
结论：因为模。

系统行为	例子	$ⁿ$ 项的行为	直观感受
振荡增强	$ₙ ₙ ₋ ₁ ₙ ₋ ₂$	指数级增长	不稳定，发散，像失控的反馈
稳定振荡	$ₙ ₙ ₋ ₁ ₙ ₋ ₂$	保持为 1	稳定，周期性，像无摩擦的摆锤
振荡减弱	$ₙ ₙ ₋ ₁ ₙ ₋ ₂$	指数级衰减	稳定，收敛，像有阻尼的弹簧

从二阶推广到 k 阶

一个 k 阶线性常系数齐次递推关系具有以下一般形式：
$ₙ ₁ ₙ ₋ ₁ ₂ ₙ ₋ ₂ ₖ ₙ ₋ ₖ$

这里的 $ₙ$ 由它前面的项唯一确定。

1. 特征方程：
我们仍然假设存在等比数列形式的解 $ₙ ⁿ$ 。代入上式得到：
$ⁿ ₁ ⁿ ⁻ ¹ ₂ ⁿ ⁻ ² ₖ ⁿ ⁻ ᵏ$
两边同除以 $ⁿ ⁻ ᵏ$ (假设 x ≠ 0)，得到一个 k 次多项式方程：
$ᵏ ₁ ᵏ ⁻ ¹ ₂ ᵏ ⁻ ² ₖ$
这就是 k 阶递推关系的特征方程。

2. 求解特征根：
根据代数基本定理，这个 k 次方程在复数范围内恰好有 k 个根（计算重数）。这些根决定了系统的所有基本行为模式。

3. 构建通解：
解空间现在是一个 k 维向量空间。我们需要找到 k 个线性无关的解（基），然后将它们线性组合起来。每个根（或每组根）对通解的贡献如下：

根的类型	根的形式	对通解的贡献（基）
简单实数根		$ⁿ$
m 重实数根	(出现m次)	$ⁿ$ , $nrⁿn²rⁿnᵐ⁻¹*rⁿ$ (共 m 个基)
简单共轭复数根	(或 )	$ⁿ$ , $ⁿ$ (共 2 个基)
m 重共轭复数根	(出现m次)	$ⁿ$ , $nRⁿcos(nθ)nᵐ⁻¹Rⁿcos(nθ)Rⁿsin(nθ)nRⁿsin(nθ)nᵐ⁻¹Rⁿsin(nθ)$ (共 2m 个基)

4. 确定特解：
通解是这 k 个基的线性组合：
$ₙ ₁ 基 ₁ ₂ 基 ₂ ₖ 基 ₖ$
为了求解 $₁ ₂ ₖ$ 这 k 个系数，我们需要 k 个初始条件，通常是 $₀ ₁ ₖ ₋ ₁$ 。

三阶例子

1. 递推关系： $ₙ ₙ ₋ ₁ ₙ ₋ ₂ ₙ ₋ ₃$

初始条件： 设 $₀$ , $₁$ , $₂$ 。

2. 建立特征方程：
$³ ²$

3. 求解特征根：

试试：，所以是一个因子。
$³ ² ²$ 。
对二次部分因式分解： $²$ 。
得到了三个简单实根： $₁$ , $₂$ , $₃$ 。

4. 构建通解：
因为我们有三个不同的实数根，所以解空间的三个基是 $ⁿ$ , $ⁿ$ , $ⁿ$ 。
通解为：
$fₙ = A * (1)ⁿ + B * (2)ⁿ + C * (3)ⁿ = A + B2ⁿ + C3ⁿ$

5. 利用初始条件求解系数 A, B, C：
我们需要解一个三元一次方程组：

: $A + B2⁰ + C3⁰ = A + B + C = f₀ = 1$ (方程 I)
: $A + B2¹ + C3¹ = A + 2B + 3C = f₁ = 2$ (方程 II)
: $A + B2² + C3² = A + 4B + 9C = f₂ = 6$ (方程 III)

解方程组：

(II) - (I): (方程 IV)
(III) - (II): => (方程 V)
(V) - (IV):
将代入 (IV): =>
将代入 (I): =>

6. 得出特解：
我们求得了系数。所以满足初始条件的唯一解是：
$ₙ ⁿ ⁿ$

验证一下：

$₀ ⁰ ⁰$ 。（正确）
$₁ ¹ ¹$ 。（正确）
$₂ ² ²$ 。（正确）
我们来预测：
- 根据递推式： $₃ ₂ ₁ ₀$ 。
- 根据通项公式： $₃ ³ ³$ 。（完全吻合！）

将二阶的思想推广到更高阶，其实一致：找到 k 个根，构建 k 个基，然后用 k 个初始条件确定 k 个系数。

适用范围

特征方程法是一个非常强大但适用范围极其有限的工具。它能完美解决的问题必须同时满足以下三个条件：

线性：递推关系中的每一项 $ₙ ₙ ₋ ₁$ 都必须是一次方。不能有 $ₙ ₋ ₁ ²$ , $ₙ ₋ ₁ ₙ ₋ ₂$ , $ₙ ₋ ₁$ 或 $ₙ ₋ ₂$ 等形式。因为特征方程建立在向量空间基础上，特征的本质就是基，如果非线性，就不存在解与解之间的组合关系，不可能用基来找到所有可能的解。
常系数： $ₙ ₋ ₁ ₙ ₋ ₂$ 前面的系数 $₁ ₂$ 必须是常数，不能随变化。例如， $ₙ ₙ ₋ ₁$ 虽然是线性的，但不是常系数，不能直接用这个方法。常系数时，我们的目标就是先求基，然后求系数，系数代表的组合就是解，所以没有常函数，自然没有办法处理。
齐次：方程整理后，等式右边必须为 0。例如 $ₙ ₙ ₋ ₁ ₙ ₋ ₂$ 就是非齐次的，这个时候我们需要先用特征方程法求解齐次部分，然后用其他方法求出非齐次特解，这个不是仅仅使用特征方程能够解决的，而且常常需要更高阶的内容，不要为难蒟蒻了 QAQ。

总结：特征方程法是为“线性常系数齐次递推关系”量身定做的。

如果不是线性的，又该怎么办？

该部分由 AI 生成。

一旦递推关系变为非线性，我们就进入了一个完全不同的世界。这里没有普适的、保证能成功的解法。线性世界的“优雅”和“简洁”不复存在，取而代之的是“复杂”、“混沌”和“不可预测”。

为什么非线性问题如此困难？

根本原因在于线性叠加原理失效了。如果 $ₙ$ 和 $ₙ$ 是 $ₙ ₙ ₋ ₁ ²$ 的两个解， $ₙ ₙ$ 绝不会是解。这意味着我们无法再像搭积木一样，用几个“基”来组合出所有可能的解。每一个解都可能是独一无二的，其行为与其它解毫无关系。

尽管没有万能钥匙，但数学家们发展出了一些策略来应对非线性问题：

1. 寻找变换，将其线性化

这是最理想的情况。有时，一个看似非线性的问题可以通过一个巧妙的变量代换变成线性的。

例子： $ₙ ₙ ₋ ₁ ²$ ，初始条件 $₀$ 。
这是一个非线性递推。序列是：2, 4, 16, 256, …

变换：我们对两边取对数，令 $ₙ ₂ ₙ$ 。
$₂ ₙ ₂ ₙ ₋ ₁ ² ₂ ₙ ₋ ₁$
代入新变量： $ₙ ₙ ₋ ₁$
这是一个我们非常熟悉的线性常系数齐次递推关系！它的通解是 $ₙ ⁿ$ 。
利用初始条件 $₀ ₂ ₀ ₂$ ，得到。所以 $ₙ ⁿ$ 。
换回原变量： $₂ ₙ ⁿ$ => $ₙ ⁿ$ 。
这个解法非常漂亮，但只适用于极少数可以被“驯服”的非线性问题。

2. 分析长期行为：不动点、周期点和混沌

当无法求出精确的通项公式时，数学家们会退而求其次：研究系统的定性行为。也就是说，“我们虽然不知道每一步具体在哪，但我们知道它最终会走向哪里”。

例子：逻辑斯蒂映射 (Logistic Map)
这是一个极富传奇色彩的非线性递推关系，常用于模拟种群增长：
$ₙ ₊ ₁ ₙ ₙ$

这里的 $ₙ$ 是 0 到 1 之间的一个值，是一个参数。这个公式里包含了 $ₙ ²$ 项，所以是非线性的。

这个方程没有通用的通项公式解。但是，它的行为完全取决于参数：

当较小 (如 r=2.5)：无论从哪个 $₀$ 开始，序列最终都会稳定在一个不动点 (Fixed Point) 上。
当增大 (如 r=3.2)：序列最终不会停在一点，而是在两个值之间来回振荡，形成一个周期为 2 的循环。
当继续增大 (如 r=3.5)：序列会在 4 个值之间循环（周期为 4），然后是 8, 16, 32… 发生倍周期分岔。
当足够大 (如 r=4)：序列的行为变得完全不可预测，初始值的微小差异会导致最终结果的巨大不同。这就是混沌 (Chaos)。

对于这类问题，研究方法不再是解方程，而是动力系统理论，使用相图、蛛网图等工具来分析其长期趋势。

3. 数值模拟

对于绝大多数实际应用中的非线性问题，解析解（通项公式）是不存在的。最直接、最有效的方法就是用计算机进行模拟。给定初始条件，一步一步地计算下去，观察序列的行为。这无法给出优雅的数学公式，但能为科学和工程问题提供具体的数值结果。

总结

特性	线性常系数齐次递推	非线性递推
核心工具	特征方程法 (线性代数)	没有统一工具 (动力系统、变换、数值模拟)
解的结构	解构成向量空间，可由基线性组合得到	叠加原理失效，解的行为孤立且多样
可预测性	完全可预测，行为模式由特征根决定	行为复杂，可能出现稳定、周期、混沌等
求解目标	寻找精确的通项公式 (解析解)	通常是分析长期定性行为或进行数值计算

结语

递推，在 OI 中随处可见，操作与原理背后有一个幽灵，一个线性代数的幽灵。这个空间，规则，统一，广泛，无处不在。这也许就是线代的美吧。

特征方程是一个处理线性常系数齐次递推式的有力工具，他有他的限制，但是功能强大，用法简单，确实值得学习。当然，其他问题也有另一个更加强大但是也更难的工具：生成函数。（这是次回予告吗？）

Do not go gentle into that good night.