例 6 设数列 $\{a_n\}$ 满足 $a_1=\frac12$ , $a_{n+1}=\frac{1+a_n}{1-a_n}$ ,求数列 $\{a_n\}$ 的通项公式。其中 $a_{n+1}=\frac{1+a_n}{1-a_n}=\frac{1+\frac{1+a_{n-1}}{1-a_{n-1}}}{1-\frac{1+a_{n-1}}{1-a_{n-1}}}=-\frac1{a_{n-1}}=a_{n-3}$ ,因此数列以 4 为周期。 考虑方程 $x=\frac{1+x}{1-x}\Leftrightarrow x^2+1=0$ ,此时数列也没有不动点 (或者说不动点为复数)。 第一步：尝试手动计算几项来找规律 $\bullet\ a_1=\frac{1}{2}$ $\bullet\ a_2=\frac{1+\frac{1}{2}}{1-\frac{1}{2}}=\frac{\frac{3}{2}}{\frac{1}{2}}=3$ $\bullet\ a_3=\frac{1+3}{1-3}=\frac{4}{-2}=-2$ $\bullet\ a_4=\frac{1+(-2)}{1-(-2)}=\frac{-1}{3}=-\frac{1}{3}$ $\bullet\ a_5=\frac{1+(-\frac{1}{3})}{1+\frac{1}{3}}=\frac{\frac{2}{3}}{\frac{4}{3}}=\frac{1}{2}$ 这很明显就回到了 $a_1=\frac{1}{2}$，后面就会循环出现。这说明这个数列是周期数列，周期为 $4$。 如果我们验证公式：值循环为： $\frac{1}{2}\to 3\to -2\to -\frac{1}{3}\to \frac{1}{2}\to \dots$ 正是如此。 $$ a_n = \begin{cases} \frac{1}{2}, & n \equiv 1 \pmod{4} \\ 3, & n \equiv 2 \pmod{4} \\ -2, & n \equiv 3 \pmod{4} \\ -\frac{1}{3}, & n \equiv 0 \pmod{4} \end{cases}$$ 第二步：推测通项公式 因为周期为 4，我们可以考虑用三角或复数的形式来表示。这里递推式是分式线性变换 $a_{n+1} = \frac{1 + a_n}{1 - a_n}$，它让我想起正切的和角公式： $$\tan\left(\theta + \frac{\pi}{4}\right) = \frac{1 + \tan\theta}{1 - \tan\theta}$$ 这个公式恰好长得一样。 那么如果我们令 $a_n = \tan\theta_n$，就有 于是我们得到： $$\tan\theta_{n+1}=\tan\left(\theta_n+\frac\pi4\right)$$ 关键点来了：两个角的正切值相等，并不能直接推出两个角相等，因为正切函数是周期函数，周期为 $\pi$。 所以严格来说： $$\theta_{n+1}=\theta_n+\frac\pi4+k\pi,\quad k\in\mathbb{Z}$$ 我们取 K=0,就得到: $$ \theta_{n+1} = \theta_n + \frac{\pi}{4}$$ 这说明角度是等差数列。 $$a_{n} = \tan \left( \arctan \frac{1}{2} + \frac{(n - 1)\pi}{4} \right)$$ 不是“直接把 tan 去掉”，而是利用了正切和角公式，让两边形式一致。 然后利用正切的周期性，选择一个合适的分支，使得角度每次增加 π/4。 这种“取分支”的做法在解递推数列时很常见，本质上是把非线性递推转化为线性递推。 二、为什么会想到“往回代一层”？ 这其实是解递推数列的一种常见策略：尝试把递推式复合两次，看能不能消去中间项，得到更简单的跨步关系。 具体来说，有几种动机： 1. 递推式是分式线性变换，复合两次往往有简化 形如 $$a_{n+1} = \frac{\alpha a_n + \beta}{\gamma a_n + \delta}$$ 的递推，复合两次（即算 $a_{n+2}$ 用 $a_n$ 表示）后，经常会现出更简单的形式，甚至可能变成 $a_{n+2} = a_n$ 或 $a_{n+2} = -1/a_n$ 这种。 因为分式线性变换对应矩阵 $$\begin{pmatrix} \alpha & \beta \\ \gamma & \delta \end{pmatrix}$$ 复合两次相当于矩阵平方，而矩阵平方可能变得很简单（比如变成对角阵或单位阵的倍数）。这个题里矩阵是 $$\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}$$ 它的平方是 $$\begin{pmatrix} 0 & 2 \\ -2 & 0 \end{pmatrix}$$ 对应变换 $a \mapsto -1/a$，正是我们看到的中间结果。 所以有经验的人会直觉地想去算“两步复合”。 这是线性代数和分式线性变换（Möbius 变换）之间的联系。简单说：每一个形如 $$f(x) = \frac{ax + b}{cx + d}$$ 的函数，都可以用一个 $2 \times 2$ 矩阵 $$ \begin{pmatrix} a & b \\ c & d \end{pmatrix}$$ 来表示。而且函数的复合对应矩阵的乘法。这个对应关系非常强大，能把复杂的函数迭代问题变成矩阵幂的问题。 一、基本对应关系 设 $$f(x) = \frac{ax + b}{cx + d},\quad g(x) = \frac{ex + f}{gx + h}$$ 那么复合 $g(f(x))$ 是： $$ g(f(x)) = \frac{e \cdot \frac{ax + b}{cx + d} + f}{g \cdot \frac{ax + b}{cx + d} + h} = \frac{e(ax + b) + f(cx + d)}{g(ax + b) + h(cx + d)} = \frac{(ea + fc)x + (eb + fd)}{(ga + hc)x + (gb + hd)}$$ 而右边这个分式的系数，正好是矩阵乘积： $$\begin{pmatrix} e & f \\ g & h \end{pmatrix} \begin{pmatrix} a & b \\ c & d \end{pmatrix} = \begin{pmatrix} ea + fc & eb + fd \\ ga + hc & gb + hd \end{pmatrix}$$ 也就是说： 复合函数 $g \circ f$ 对应的矩阵，就是 $g$ 的矩阵乘以 $f$ 的矩阵。 注意顺序：先作用 $f$，再作用 $g$，对应矩阵乘积是 $M_g \cdot M_f$（右乘先作用的）。 $$f(x) = \frac{a_1x + b_1}{c_1x + d_1}, g(x) = \frac{a_2x + b_2}{c_2x + d_2} \text{, 那么}$$ $$ f(g(x)) = \frac{a_1\frac{a_2x + b_2}{c_2x + d_2} + b_1}{c_1\frac{a_2x + b_2}{c_2x + d_2} + d_1} = \frac{a_1a_2x + a_1b_2 + b_1c_2x + b_1d_2}{c_1a_2x + c_1b_2 + c_2d_1x + d_1d_2} = \frac{(a_1a_2 + b_1c_2)x + (a_1b_2 + b_1d_2)}{(c_1a_2 + c_2d_1)x + (c_1b_2 + d_1d_2)}$$ $$\text{而 } \begin{bmatrix} a_1 & b_1 \\ c_1 & d_1 \end{bmatrix} \begin{bmatrix} a_2 & b_2 \\ c_2 & d_2 \end{bmatrix} = \begin{bmatrix} a_1a_2 + b_1c_2 & a_1b_2 + b_1d_2 \\ a_2c_1 + c_2d_1 & c_1b_2 + d_1d_2 \end{bmatrix}.$$ $$ \text{这就说明了, 分式线性函数的复合和矩阵相乘(忽略标量变换)是同构的。}$$ $$\text{因此, 为了让 } f^{(n)}(x) = x \text{, 就需要让 } f \text{ 的 "矩阵" } \begin{bmatrix} a_1 & b_1 \\ c_1 & d_1 \end{bmatrix} \text{ 的某个整数次幂是标量变换. 后者是线性代数问题。}$$ 确实强，提供了分式迭代的另外一种思路。稍微补充一下.这种理解首先可能没有跟不动点方程关联起来，其次周期数列应该要求的是这个矩阵的 n 次幂是单位阵 当复数解的模为 1 时，才是周期数列 还对幅角有要求，当幅角/2π属于 Q 时，才是周期数列 直观来说，要复数解在单位圆上，旋转若干次以后，能回到出发点 二、应用到本题 本题递推式： $$a_{n+1} = \frac{1 + a_n}{1 - a_n}$$ 对应函数 $$ f(x) = \frac{1 \cdot x + 1}{-1 \cdot x + 1}$$ 对应矩阵： $$M = \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}$$ 那么： - $a_{n+1} = f(a_n)$ 对应矩阵 $M$ - $a_{n+2} = f(f(a_n))$ 对应矩阵 $M^2$ 计算： $$ M^2 = \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 2 \\ -2 & 0 \end{pmatrix}$$ 这个矩阵对应的函数是： $$\frac{0 \cdot x + 2}{-2 \cdot x + 0} = \frac{2}{-2x} = -\frac{1}{x}$$ 这正是我们之前得到的中间结果： $$ a_{n+2} = -\frac{1}{a_n}$$ 再算 $M^4$： $$M^4 = (M^2)^2 = \begin{pmatrix} 0 & 2 \\ -2 & 0 \end{pmatrix}^2 = \begin{pmatrix} -4 & 0 \\ 0 & -4 \end{pmatrix} = -4I$$ 对应的函数是： $$ \frac{-4x + 0}{0 \cdot x + (-4)} = \frac{-4x}{-4} = x$$ 即恒等变换 $f^{(4)}(x) = x$，所以 $$a_{n+4} = a_n$$ 周期为 4。 三、为什么这个对应成立？ 核心原因是：分式线性变换可以看成射影直线上的变换。在射影几何中，实数加上无穷远点构成射影直线 $\mathbb{P}^1$，而分式线性变换正是射影直线上的线性变换。用齐次坐标表示： $$x \mapsto \frac{ax + b}{cx + d} \quad \leftrightarrow \quad \begin{pmatrix} x \\ 1 \end{pmatrix} \mapsto \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ 1 \end{pmatrix} = \begin{pmatrix} ax + b \\ cx + d \end{pmatrix}$$ 然后再把齐次坐标 $\begin{pmatrix} u \\ v \end{pmatrix}$ 还原成 $u/v$，就得到分式。复自然对应矩阵乘法。 四、这个工具的好处 1. 复合变成乘法：多次迭代 $f$ 就变成算 $M^n$，可以用对角化、特征值等方法求通项。 2. 周期判断：如果 $M^n$ 是单位阵的倍数，则 $f^{(n)}$ 是恒等变换，数列周期为 $n$。 3. 求通项：对角化 $M$ 后，可以求出 $f^{(n)}(x)$ 的显式表达式，从而得到数列通项。 比如本题，$M$ 的特征值是 $1 \pm i$，对应旋转 $45^\circ$，所以每 4 步回到原点，周期 4。 五、总结 ·分式线性变换 $f(x)=\frac{ax+b}{cx+d}$ 对应矩阵 $\begin{pmatrix}a&b\\c&d\end{pmatrix}.$ · 函数复合对应矩阵乘法。 · 迭代 $n$ 次对应矩阵 $n$ 次幂。 ·本题中 $M^2$ 对应 $x\mapsto-1/x$, $M^4$ 对应恒等，所以周期 4。 这就是“分式线性变换对应矩阵”的含义。它是解决这类递推数列的一个非常有力的工具。 一、有一个不动点 $x_0$ 时 此时方程 $$x = \frac{ax + b}{cx + d}$$ 有重根 $x_0$，即 $$ cx^2 + (d - a)x - b = 0$$ 的判别式为 0，且 $x_0$ 是唯一不动点。 在递推式两边减去 $x_0$： $$x_{n+1} - x_0 = \frac{ax_n + b}{cx_n + d} - x_0$$ 通分： $$ x_{n+1} - x_0 = \frac{ax_n + b - x_0(cx_n + d)}{cx_n + d} = \frac{(a - cx_0)x_n + (b - dx_0)}{cx_n + d}$$ 因为 $x_0$ 是不动点，所以 $$x_0 = \frac{ax_0 + b}{cx_0 + d}$$ 即 $cx_0^2+(d-a)x_0-b=0$ 由重根条件： $$x_{0}=\frac{a-d}{2 c}$$ 又因为重根，可以对分子因式分解，最终得到： $$x_{n+1}-x_{0}=\frac{a-cx_{0}}{cx_{n}+d}(x_{n}-x_{0})$$ 于是 $$ \frac{1}{x_{n+1}-x_{0}}=\frac{cx_{n}+d}{a-cx_{0}}\cdot\frac{1}{x_{n}-x_{0}}$$ 再把 $cx_{n}+d$ 表示成与 $x_{n}-x_{0}$ 有关的形式： $$cx_{n}+d=c(x_{n}-x_{0})+(cx_{0}+d)$$ 所以 $$ \frac{1}{x_{n+1}-x_{0}}=\frac{c}{a-cx_{0}}+\frac{cx_{0}+d}{a-cx_{0}}\cdot\frac{1}{x_{n}-x_{0}}$$ 由于 $x_{0}$ 是重根，可以证明： $$\frac{cx_{0}+d}{a-cx_{0}}=1$$ 因此 $$ \frac{1}{x_{n+1}-x_{0}}=\frac{1}{x_{n}-x_{0}}+\frac{c}{a-cx_{0}}$$ 所以数列 $$\left\{\frac{1}{x_{n}-x_{0}}\right\}$$ 是等差数列，其公差为 $$ d_{0}=\frac{c}{a-c x_{0}}$$ 也可以利用重根条件化简。 所以 $$ a-c x_{0}=a-c \cdot \frac{a-d}{2 c}=\frac{a+d}{2}$$ 因此公差为 $$d_{0}=\frac{2 c}{a+d}$$ 这就是一个不动点情形下等差数列的公差。 二、有两个不动点 $\alpha, \beta$ 时 此时方程 $$x = \frac{a x + b}{c x + d}$$ 有两个不同实根 $\alpha, \beta$。 分别令 $$ x_{n+1} - \alpha = \frac{a x_n + b}{c x_n + d} - \alpha$$ $$x_{n+1} - \beta = \frac{a x_n + b}{c x_n + d} - \beta$$ 因为 $\alpha, \beta$ 都是不动点，所以可以因式分解得到： $$ x_{n+1} - \alpha = \frac{a - c \alpha}{c x_n + d} (x_n - \alpha)$$ $$x_{n+1} - \beta = \frac{a - c \beta}{c x_n + d} (x_n - \beta)$$ 两式相除： $$ \frac{x_{n+1} - \alpha}{x_{n+1} - \beta} = \frac{a - c \alpha}{a - c \beta} \cdot \frac{x_n - \alpha}{x_n - \beta}$$ 因此数列 $$\left\{\frac{x_n - \alpha}{x_n - \beta}\right\}$$ 是等比数列，其公比为 $$ q = \frac{a - c\alpha}{a - c\beta}$$ $\alpha, \beta$ 是方程 $$ cx^2 + (d - a)x - b = 0$$ 的两根。 由韦达定理： $$\alpha + \beta = \frac{a - d}{c}$$ $$ \alpha \beta = -\frac{b}{c}$$ ---- 三、总结 对于分式递推数列 $$x_{n+1} = \frac{a x_n + b}{c x_n + d}$$ 设不动点方程为 $$ c x^2 + (d - a) x - b = 0$$ 1. 若只有一个不动点 $x_0$ 则 $$\left\{ \frac{1}{x_n - x_0} \right\}$$ 是等差数列，公差为 $$ \frac{c}{a - c x_0}$$ 等价地，若重根为 $x_0 = \frac{a - d}{2c}$，则公差为 $$\frac{2c}{a + d}$$ 2. 若有两个不动点 $\alpha, \beta$ 则 $$\left\{ \frac{x_n - \alpha}{x_n - \beta} \right\}$$ 是等比数列，公比为 $$ \frac{a - c\alpha}{a - c\beta}$$ 所以，公比和公差不需要额外记忆复杂公式，关键是： - 一个不动点：作差后取倒数，得到等差数列，公差由递推系数和不动点决定； - 两个不动点：作差后相除，得到等比数列，公比由两个不动点处的线性因子系数之比决定。 即： $$d = \frac{c}{a - cx_0}$$ $$ q = \frac{a - c\alpha}{a - c\beta}$$ 分式递推 | 找不动点 | ┌──────────────┐ │ 一个根 │ 两个根 │ 取倒数 │ 作比 │ 等差 │ 等比 │ 公差 c/(a-cx 0)│ 公比 (a-cα)/(a-cβ) └──────────────┘ [如果不动点方程无实数解该怎么办，一定是周期数列吗？ - 知乎](https://www.zhihu.com/question/566595014) # 如果不动点方程无实数解该怎么办，一定是周期数列吗？ 设 $a,b,c,d\in \mathbb{R}$，数列 $\{x_n\}$，其首项 $x_1\in \mathbb{R}$，在此考虑的数列是一阶分式递推数列 $^*$，也即满足对任意的正整数 $n$，都有 $$x_{n+1}=\frac{ax_n+b}{cx_n+d}.\tag{1}$$ 公式 (1) 被称为数列 $\{x_n\}$ 的递推式。考虑方程 $$ \frac{ax+b}{cx+d}=x,\tag{2}$$ 方程 (2) 的解称为数列 $\{x_n\}$ 的不动点。注意到 $cx+d\ne 0$，上述方程可以转化为关于的二次方程 $cx^2+(d-a)x-b=0$，从而可以考虑其判别式 $\Delta=(d-a)^2+4bc$。 在本问题中，$\Delta<0$，这个时候方程 (2) 没有实数解，所以数列没有实数不动点。但是方程 (2) 会有两个共轭的复数解，设为 $z_1,z_2\in \mathbb{C}$。我们现在就来想办法处理这种情况。 命题 1 设数列 $\{x_n\}$ 的首项 $x_1\in \mathbb{R}$，满足递推式 (1)，且方程 (2) 有两个共轭的复数解 $z_1,z_2\in \mathbb{C}$，则 $\left\{\frac{x_n-z_1}{x_n-z_2}\right\}\subset \mathbb{C}$ 是等比数列。 证明 此时对 $i=1,2$，都有 $z_i=\frac{az_i+b}{cz_i+d}$，分别与 (1) 相减得 $$x_{n+1} - z_i = \frac{a x_n + b}{c x_n + d} - \frac{a z_i + b}{c z_i + d}$$ $$ = \frac{(a x_n + b)(c z_i + d) - (a z_i + b)(c x_n + d)}{(c x_n + d)(c z_i + d)}$$ $$= \frac{(a d - b c)(x_n - z_i)}{(c x_n + d)(c z_i + d)},$$ 进一步有 $$ \frac{x_{n+1} - z_1}{x_{n+1} - z_2} = \frac{c z_2 + d}{c z_1 + d} \cdot \frac{x_n - z_1}{x_n - z_2},$$ 从而数列 $\left\{ \frac{x_n - z_1}{x_n - z_2} \right\}$ 是首项为 $\frac{x_1 - z_1}{x_1 - z_2} \in \mathbb{C}$，公比为 $\frac{c z_2 + d}{c z_1 + d} \in \mathbb{C}$ 的等比数列，从而是 $\mathbb{C}$ 中的等比数列。 根据上述结论，即可得到这种情形下数列的通项公式的求法。当然上述结果是带有虚单位 $i$ 的。为了进一步展开研究，记此时的 “公比” $$z_0 = \frac{cz_2 + d}{cz_1 + d} = \frac{\overline{cz_1 + d}}{cz_1 + d} = \frac{\left(c\overline{z_1} + d\right)^2}{|cz_1 + d|^2} = \frac{(cz_2 + d)^2}{|cz_1 + d|^2},$$ 则有 $|z_0| = 1$，从而可以将 $z_0$ 表示为 $z_0 = e^{i\theta} = \cos\theta + i\sin\theta$，其中 $\theta = \arg(cz_2 + d)^2$。在复数的情形下，会有什么不一样的地方呢？且看下面的结论。 命题 2 设数列 $\{x_n\}$ 的首项 $x_1 \in \mathbb{R}$，满足递推式 (1)，且方程 (2) 有两个共轭的复数解 $z_1, z_2 \in \mathbb{C}$，记 $\theta = \arg(cz_2 + d)^2$，则 $\{x_n\}$ 是周期数列，当且仅当 $\dfrac{\theta}{\pi}$ 是有理数。 证明 沿用上面的记号。一方面，若 $\dfrac{\theta}{\pi}$ 是有理数，也即存在 $p, q \in \mathbb{Z}$，使得 $\dfrac{\theta}{\pi} = \dfrac{p}{q}$，则有 $$ z_0 = e^{i\frac{p\pi}{q}} = \cos\frac{p\pi}{q} + i\sin\frac{p\pi}{q},$$ 进一步有 $$z_0^{2q} = e^{i2p\pi} = \cos 2p\pi + i\sin 2p\pi = 1.$$ 从而，对任意的正整数 $n$ ，都有 $$\frac{x_{n+2q}-z_1}{x_{n+2q}-z_2}=z_0^{2q}\cdot \frac{x_n-z_1}{x_n-z_2}=\frac{x_n-z_1}{x_n-z_2},$$ 整理得到 $$ (z_2-z_1)(x_{n+2q}-x_n)=0,$$ 其中根据 $z_1,z_2\not\in\mathbb{R}$，知 $z_2=\overline{z_1}\ne z_1$，因此 $x_{n+2q}=x_n$，从而数列 $\{x_n\}$ 是周期为 $2q$ 的周期数列。 另外一方面，若数列 $\{x_n\}$ 是周期数列，也即存在整数 $t$，使得 $x_{n+t}=x_n$，则有 $$\frac{x_{n+t}-z_1}{x_{n+t}-z_2}=z_0^t\cdot \frac{x_n-z_1}{x_n-z_2}=\frac{x_n-z_1}{x_n-z_2}.$$ 其中根据 $x_n\in\mathbb{R}$，$z_1\not\in\mathbb{R}$，知 $x_n\ne z_1$，因此 $$ 1=z_0^t=e^{it\theta}=\cos t\theta+i\sin t\theta.$$ 这说明了存在整数 $n$，使得 $t\theta=2n\pi$，从而 $\dfrac{\theta}{\pi}=\dfrac{2n}{t}$ 是有理数。 例 设数列 $\{x_n\}$ 满足 $x_1=1$，$x_{n+1}=-\frac{1}{x_n+1}$，求数列 $\{x_n\}$ 的通项公式。 解答 考虑方程 $-\frac{1}{x+1}=x \iff x^2+x+1=0$，此时 $\Delta=-3<0$，从而方程没有实数解。但是迭代得 $$x_{n+2}=-\frac{1}{x_{n+1}+1}=-\frac{1}{-\frac{1}{x_n+1}+1}=-1-\frac{1}{x_n},$$ 以及 $$ x_{n+3}=-1-\frac{1}{x_{n+1}}=x_n,$$ 因此 $\{x_n\}$ 是周期为 $3$ 的周期数列，计算得 $x_2=-\frac{1}{2}$，$x_3=-2$，$x_4=1$，以此类推，可得数列 $\{x_n\}$ 的通项公式为 $$x_n= \begin{cases} 1, & n=3k+1, \\ -\frac{1}{2}, & n=3k+2, \\ -1, & n=3k. \end{cases}$$ 感兴趣的同学，也可以试着用复数表示通项公式。 # 牛顿迭代法与数列不动点 及 王萼芳、石生明《高等代数（第五版）》相关知识点 ## 一、牛顿迭代法与数列不动点的关系 ### 1. 核心结论 牛顿迭代法和数列的不动点**有非常密切的关系**。牛顿迭代法可以看作是一种**构造不动点迭代**的方法。 ### 2. 不动点迭代的一般形式 对于数列，不动点迭代是指： $$ x_{n+1} = g(x_n) $$ 如果数列收敛到 $x^*$，则 $x^* = g(x^*)$，即 $x^*$ 是 $g$ 的**不动点**。 ### 3. 牛顿迭代法就是一种特殊的不动点迭代 牛顿迭代法求解 $f(x)=0$： $$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$ 令 $$ g(x) = x - \frac{f(x)}{f'(x)} $$ 则牛顿迭代就是 $x_{n+1} = g(x_n)$ 这一不动点迭代。 **关键点**：如果 $f(x^*)=0$ 且 $f'(x^*)\neq 0$，则 $$ g(x^*) = x^* - \frac{0}{f'(x^*)} = x^* $$ 所以 $f$ 的零点恰好就是 $g$ 的不动点。求 $f(x)=0$ 的根，等价于求 $g(x)=x$ 的不动点。 --- ## 二、例子 ### 例 1：求 $\sqrt{2}$ 即解 $f(x) = x^2 - 2 = 0$。 牛顿迭代： $$ x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right) $$ 这里不动点函数为 $$ g(x) = \frac{1}{2}\left(x + \frac{2}{x}\right) $$ 验证不动点：$x = \frac{1}{2}(x + \frac{2}{x}) \Rightarrow 2x = x + \frac{2}{x} \Rightarrow x^2 = 2 \Rightarrow x = \sqrt{2}$。 取 $x_0 = 1$： - $x_1 = \frac{1}{2}(1+2) = 1.5$ - $x_2 = \frac{1}{2}(1.5 + 1.3333) = 1.41667$ - $x_3 = 1.41422$ - 收敛到 $\sqrt{2} \approx 1.41421$ $\sqrt{2}$ 既是 $f$ 的零点，也是 $g$ 的不动点。 ### 例 2：解 $x = \cos x$ 这个方程本身就是**不动点形式** $x = g(x)$，其中 $g(x)=\cos x$。 若用牛顿法解 $f(x) = x - \cos x = 0$： $$ x_{n+1} = x_n - \frac{x_n - \cos x_n}{1 + \sin x_n} $$ 两种方法都在找同一个不动点 $x^* \approx 0.739085$，但收敛速度不同： - 直接不动点迭代 $x_{n+1}=\cos x_n$：线性收敛（因为 $|g'(x^*)|=|\sin x^*|\approx 0.67$） - 牛顿法：二次收敛（因为 $g'(x^*)=0$） ### 4. 为什么牛顿法收敛更快？ 对牛顿法的不动点函数 $g(x) = x - f(x)/f'(x)$ 求导： $$ g'(x) = 1 - \frac{f'(x)^2 - f(x)f''(x)}{f'(x)^2} = \frac{f(x)f''(x)}{f'(x)^2} $$ 在零点 $x^*$ 处 $f(x^*)=0$，所以 $g'(x^*) = 0$。 **一阶导数为零**正是不动点迭代中**二次收敛**的条件。这解释了为什么牛顿法比普通不动点迭代快得多。 ### 5. 总结表 | 概念 | 关系 | |------|------| | 牛顿迭代 | 一种特殊的不动点迭代 $x_{n+1}=g(x_n)$ | | $f$ 的零点 | 恰是 $g(x)=x-f/f'$ 的不动点 | | 收敛速度 | 因 $g'(x^*)=0$，牛顿法二次收敛 | | 本质 | 牛顿法 = 用导数信息构造一个在根处导数为零的不动点函数 | 所以，牛顿迭代法本质上就是**通过巧妙构造不动点函数，把求根问题转化为不动点问题**，并利用 $g'(x^*)=0$ 获得二次收敛。 --- ### 1. 直接相关的知识点：多项式函数的根 牛顿迭代法本质是**求函数零点**的方法。高等代数中与之最直接对应的是**第一章“多项式”**，特别是 **§7 多项式函数**。 - **理论对应**：多项式函数 $f(x)$ 的**根**（零点），就是牛顿迭代法要找的目标。多项式理论中的**重因式**（§6）与牛顿迭代法在重根处收敛速度退化为线性直接相关。 - **方法关联**：虽然教材主体讲的是代数方法（如辗转相除法求最大公因式），但多项式求根本质上是一个数值分析问题。 ### 2. 深层相关的知识点：特征值与特征向量 **第七章“线性变换”中的 §4 特征值与特征向量**，与“不动点”概念有深层的数学同构关系。 - **本质联系**：在有限维线性空间中，线性变换 $A$ 的特征向量 $v$ 满足 $A v = \lambda v$。当 $\lambda = 1$ 时，方程变为 $A v = v$，这正是**线性变换意义下的“不动点方程”**。 - **概念延伸**：求线性变换的不动点，就是在求特征值为 1 的特征向量。这与“数列不动点”虽处于不同数学分支，但“寻找一个使变换结果等于自身的对象”这一核心思想是相通的。