# 大 O、小 o 与牛顿误差的追问

[[MCS/day7/00 学习指南|day7 学习指南]] · [[MCS/00 MCS学习总览|十一天总览]] · [[MCS/day7/阅读核验与疑问|阅读核验与疑问]] · 上一篇：[[MCS/day7/01 牛顿法与优化进阶|牛顿法与优化进阶]]

> 来源：[[MCS/day7高阶无穷小|day7高阶无穷小]]。用途：问答。原有推导、追问与解答保留；阅读时请结合本日核验说明。

一、小 $o$
$$f(x) = o(g(x)) \quad (x \to x_0)$$
意思是：
$$
\lim_{x \to x_0} \frac{f(x)}{g(x)} = 0$$
标准叫法：
| 小 $o$ 符号，读作“小 $o$”。
它表示 $f$ 是比 $g$ 高阶的无穷小。
所以你说的没错：
小 $o$ 叫高阶无穷小符号。


二、大 $O$
$$f(x) = O(g(x)) \quad (x \to x_0)$$
意思是：存在常数 $C > 0$，当 $x$ 足够接近 $x_0$ 时，
$$
|f(x)| \leq C |g(x)|$$
标准叫法：
- 大 $O$ 符号，读作“大 $O$”。
- 它表示 $f$ 是 $g$ 的同阶无穷小或更低阶无穷小。



$$f(x) = O(g(x)),$$
表示 $f$ 和 $g$ 同阶或更低阶。

这里的主语是 $f$，参照物是 $g$。

- “同阶”：$f$ 和 $g$ 差不多大；
- “更低阶”：$f$ 比 $g$ 小，也就是 $f$ 相对于 $g$ 是低阶。

注意：

| 低阶 = 更小 |
| 高阶 = 更小得更多 |

这两个词容易绕晕，因为“高阶”听起来像“更大”，但在无穷小里，“高阶”其实是“更小”。
“更低阶”是相对于参照物说的，意思是比参照物小。

“高阶”是”小得多”。

所以高阶一定是更低阶，但更低阶不一定是高阶。
在大 $O$  里，同阶或更低阶=同阶或更小。


一、定义是一样的
大 $O$ 的标准定义（两边通用）：
存在常数 $C > 0$ 和 $x_0$，使得当 $x \geq x_0$（或 $x \to x_0$）时，
$$|f(x)| \leq C|g(x)|$$
$$
\left|  \frac{f(x)}{g(x)}\right| \le L
$$

就记作：
$$
f(x) = O(g(x))$$
这个定义在算法分析和数学分析里完全一致。
二、算法分析里的大 $O$：渐进上界
算法分析里：
$$T(n) = O(g(n))$$
表示：
当输入规模 $n$ 足够大时，算法运行时间 $T(n)$ 不会超过 $g(n)$ 的常数倍。
例如：
$$
T(n) = 3n^2 + 5n + 2 = O(n^2)$$

意思是：
- 当 $n$ 很大时，$3n^2 + 5n + 2$ 和 $n^2$ 同阶；
- 更准确地说，$T(n)$ 不超过 $Cn^2$。
这里大 $O$ 是渐进上界，只关心增长趋势，不关心常数和低阶项。
三、数学分析里的大 $O$：同阶或更低阶
数学分析里：
$$f(x) = O(g(x)) \quad (x \to x_0)$$
表示：
- $f(x)$ 和 $g(x)$ 同阶，或者比 $g(x)$ 更低阶。
例如：
$$
\sin x = O(x) \quad (x \to 0)$$
因为：
$$\left| \frac{\sin x}{x} \right| \leq 1$$

这里大 $O$ 也是上界，但更强调局部行为 $(x \to x_0)$，而不是 $n \to \infty$。

四、两者异同

| 方面 | 算法分析 | 数学分析 |
| --- | --- | --- |
| 定义 | 相同 | 相同 |
| 变量 | 通常是 $n \to \infty$ | 通常是 $x \to x_0$ 或 $x \to \infty$ |
| 关注点 | 增长趋势、复杂度 | 局部近似、误差阶 |
| 含义 | 渐进上界 | 同阶或更低阶 |
| 常数 | 不关心 | 不关心 |
| 低阶项 | 忽略 | 忽略 |

算法分析和数学分析里的大 $O$ 定义完全相同，都是“不超过常数倍”的上界。区别只在于：  
• 算法分析：$n \to \infty$，关注增长趋势；  
• 数学分析：$x \to x_0$，关注局部近似。  

所以它们是同一个大 $O$，只是应用场景不同。


一般关系

$$o(g)\subseteq O(g)$$

 小 $o$ 是大 $O$ 的子集。



具体例子
因为：
$$e_n^3 = o(e_n^2)$$
所以：
$$
O(e_n^3) \subseteq o(e_n^2)$$
这里大 $O$ 反而更精确，因为它告诉你余项是 $e_n^3$ 级别，而小 $o(e_n^2)$ 只说“比 $e_n^2$ 高阶”，不够具体。


三、为什么误差分析里常写成大 $O$？
在数值分析、误差估计里，我们关心的是收敛阶，不关心具体常数。这时写成大 $O$ 更方便：
$$f(x_n) = f'(x^*)e_n + \frac{f''(x^*)}{2}e_n^2 + O(e_n^3)$$

这里的 $O(e_n^3)$ 表示：

余项和 $e_n^3$ 同阶（或更低阶），也就是至少是三次项级别。

写成大 $O$ 的好处是：

1. 不需要极限过程，只说明显级；
2. 方便做误差估计，直接看阶数；
3. 在数值分析里，通常只关心“误差是 $e_n^2$ 级别”，不关心它是不是严格比 $e_n^2$ 高阶。
4.



四、两者在泰勒展开里的关系
如果我们展开到二次项：
$$f(x_n) = f(x^*) + f'(x^*)(x_n - x^*) + \frac{f''(x^*)}{2}(x_n - x^*)^2 + \frac{f'''(\xi)}{6}(x_n - x^*)^3$$
那么余项是：
$$
\frac{f'''(\xi)}{6}e_n^3$$
这个余项：
- 写成小 $o$：$o(e_n^2)$，因为它比它 $e_n^2$ 高阶；
- 写成大 $O$：$O(e_n^3)$，因为它和 $e_n^3$ 同阶。

两个写法都对，只是关注点不同：


| 写法 | 含义 | 关注点 |
|------|------|--------|
| $o(e_n^2)$ | 比 $e_n^2$ 高阶 | 极限意义 |
| $O(e_n^3)$ | 和 $e_n^3$ 同阶 | 量级大小 |


• 如果你在写泰勒公式的标准形式，用皮亚诺余项：
$$o((x - x_0)^n)$$
• 如果你在做数值分析的误差估计，关心收敛阶：
$$
O(e_n^p)$$
所以：
泰勒公式本身的标准余项是小 $o$；
误差分析里常写成大 $O$，是为了直接看出阶数。

f(x)与 f'(x)的展开

一、两者是独立的泰勒展开
前者：把 $f(x)$ 在 $x^*$ 处展开
$$f(x_n) = f(x^*) + f'(x^*)(x_n - x^*) + \frac{f''(x^*)}{2}(x_n - x^*)^2 + \cdots$$
这是对函数 $f$ 本身做泰勒展开。
后者：把 $f'(x)$ 在 $x^*$ 处展开
$$
f'(x_n) = f'(x^*) + f''(x^*)(x_n - x^*) + \frac{f'''(\xi)}{2}(x_n - x^*)^2$$
这是对导函数 $f'$ 做泰勒展开。
所以它是 $f'(x_n)$ 自己的泰勒展开，而不是对前者求导。
但这只是形式上巧合。严格说：
- 前者是 $f$ 的泰勒展开；
- 后者是 $f'$ 的泰勒展开；
- 它们各自独立成立，不是“前者求导得到后者”。

三、为什么不能简单说“后者是前者的求导”？
因为泰勒展开是在固定点 $x^*$ 处展开的。
- 对 $f(x_n)$ 关于 $x_n$ 求导，得到的是 $f'(x_n)$，这没问题；
- 但你不能对泰勒级数逐项求导来“证明” $f'$ 的泰勒展开，因为那需要额外的收敛性条件。
更准确的说法是：


$$f'(x_n) \text{ 的泰勒展开，就是把 } f' \text{ 当作一个新函数，在 } x^* \text{ 处做泰勒展开。}$$

en 的计算

一、先看 $f(x_n)$ 的展开
把 $f(x)$ 在 $x^*$ 处展开：
$$f(x_n)=f(x^*)+f'(x^*)(x_n-x^*)+\frac{f''(x^*)}{2}(x_n-x^*)^2+\frac{f'''(\xi)}{6}(x_n-x^*)^3$$
因为：
$$
f(x^*)=0,\quad x_n-x^*=e_n$$
所以：
$$f(x_n)=f'(x^*)e_n+\frac{f''(x^*)}{2}e_n^2+\frac{f'''(\xi)}{6}e_n^3$$
最后这一项：
$$
\frac{f'''(\xi)}{6}e_n^3$$
就是 $O(e_n^3)$，因为它它是 $e_n$ 的三阶项。
所以：
$$f(x_n)=f'(x^*)e_n+\frac{f''(x^*)}{2}e_n^2+O(e_n^3)$$

这里出现 $O(e_n^3)$，是因为我们展开了 $f$ 本身，保留到二次项，下一项就是三次项。

二、再看 $f'(x_n)$ 的展开
现在展开的是导函数 $f'(x)$，不是 $f(x)$。
把 $f'(x)$ 在 $x^*$ 处展开：
$$f'(x_n) = f'(x^*) + f''(x^*)(x_n - x^*) + \frac{f'''(\xi)}{2}(x_n - x^*)^2$$
代入 $x_n - x^* = e_n$：
$$
f'(x_n) = f'(x^*) + f''(x^*)e_n + \frac{f'''(\xi)}{2}e_n^2$$
最后这一项：
$$\frac{f'''(\xi)}{2}e_n^2$$
是 $e_n$ 的二次项，所以记作 $O(e_n^2)$。
因此：
$$
f'(x_n) = f'(x^*) + f''(x^*)e_n + O(e_n^2)$$
这里出现 $O(e_n^2)$，是因为我们展开的是 $f'$，保留到一次项，下一项就是二次项。
 五、补充：为什么这样保留是合理的？

因为我们最终要算：

$$\frac{f(x_n)}{f^{\prime}(x_n)}$$

分子保留到 $e_n^2$,分母保留到 $e_n$,相除后：

$$\frac{f(x_n)}{f'(x_n)}=\frac{f'(x^*)e_n+\frac{f''(x^*)}{2}e_n^2+O(e_n^3)}{f'(x^*)+f''(x^*)e_n+O(e_n^2)}$$

分母除以 $f^{\prime}(x^*)$ 后变成 $1+O(e_n)$,所以整个分式展开后主项是 $e_n$, 下 一 项 是  $e_n^2$。
为了得到 $e_{n+1}$ 的二阶项 $e_n^2$。分子保留到 $e_n^2$、分母保留到 $e_n$ 就够了，更高阶的项都会被吸讲余项里。


一、牛顿迭代公式
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
设真实根为 $x^*$，满足：
$$
f(x^*) = 0$$
定义误差：
$$e_n = x_n - x^*$$
所以：
$$
x_n = x^* + e_n$$


二、在根 $x^*$ 处泰勒展开 $f(x_n)$
把 $f(x)$ 在 $x^*$ 处展开：
$$f(x_n) = f(x^*) + f'(x^*)(x_n - x^*) + \frac{f''(x^*)}{2}(x_n - x^*)^2 + \cdots$$
因为 $f(x^*) = 0$，且 $x_n - x^* = e_n$，所以：
$$
f(x_n) = f'(x^*)e_n + \frac{f''(x^*)}{2}e_n^2 + O(e_n^3)$$
三、同样展开 $f'(x_n)$
$$f'(x_n) = f'(x^*) + f''(x^*)(x_n - x^*) + \cdots$$
即：
$$
f'(x_n) = f'(x^*) + f''(x^*)e_n + O(e_n^2)$$

四、代入牛顿迭代公式
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
把 $x_n = x^* + e_n$ 代入：
$$
x^* + e_{n+1} = x^* + e_n - \frac{f(x_n)}{f'(x_n)}$$
两边消去 $x^*$：
$$e_{n+1} = e_n - \frac{f(x_n)}{f'(x_n)}$$
五、计算 $\frac{f(x_n)}{f'(x_n)}$
分子：
$$
f(x_n) = f'(x^*)e_n + \frac{f''(x^*)}{2}e_n^2 + O(e_n^3)$$
分母：
$$f'(x_n) = f'(x^*) + f''(x^*)e_n + O(e_n^2)$$

所以：
$$\frac{f(x_n)}{f'(x_n)} = \frac{f'(x^*)e_n + \frac{f''(x^*)}{2}e_n^2 + O(e_n^3)}{f'(x^*) + f''(x^*)e_n + O(e_n^2)}$$
六、化简
分子分母同时除以 $f'(x^*)$（假设 $f'(x^*) \neq 0$）：
$$
\frac{f(x_n)}{f'(x_n)} = \frac{e_n + \frac{f''(x^*)}{2f'(x^*)}e_n^2 + O(e_n^3)}{1 + \frac{f''(x^*)}{f'(x^*)}e_n + O(e_n^2)}$$
利用展开：
$$\frac{1}{1+u} = 1 - u + O(u^2)$$
令：
$$
u = \frac{f''(x^*)}{f'(x^*)}e_n$$
则分母：
$$\frac{1}{1+u} = 1 - u + O(e_n^2)$$
所以：
$$\frac{f(x_n)}{f'(x_n)} = \left(e_n + \frac{f''(x^*)}{2f'(x^*)}e_n^2\right)\left(1 - \frac{f''(x^*)}{f'(x^*)}e_n\right) + O(e_n^3)$$
展开：
$$
= e_n + \frac{f''(x^*)}{2f'(x^*)}e_n^2 - \frac{f''(x^*)}{f'(x^*)}e_n^2 + O(e_n^3)$$
合并 $e_n^2$ 项：
$$= e_n - \frac{f''(x^*)}{2f'(x^*)}e_n^2 + O(e_n^3)$$
二、为什么要用 $\frac{1}{1+u}=1-u+O(u^{2})$？
因为我们要的是误差 $e_{n+1}$ 的表达式，而误差最关键的最低阶项。
分母里有 $1+u$，直接除不好处理，但有一个标准展开：
$$\frac{1}{1+u}=1-u+u^{2}-\cdots$$
当 $u$ 很小时，可以只保留到 $u$ 的一次项：
$$
\frac{1}{1+u}=1-u+O(u^{2})$$
这里 $u=O(e_{n})$，所以 $O(u^{2})=O(e_{n}^{2})$。
于是：
$$\frac{1}{1+u}=1-u+O(e_{n}^{2})$$

这一步的目的就是把分母变成乘法，方便展开。

三、为什么可以只保留到 $e_n^2$?
因为我们最终要的是:
$$e_{n+1} = e_n - \frac{f(x_n)}{f'(x_n)}$$
而我们已经知道 $e_{n+1}$ 的主项是 $e_n^2$，所以:
- 只要把 $\frac{f(x_n)}{f'(x_n)}$ 展开到 $e_n^2$ 项就够了;
- 更高阶的 $e_n^3$、$e_n^4$ 都会被吸进 $O(e_n^3)$，不影响主项。


所以:
$$
\frac{f(x_n)}{f'(x_n)} = \left(e_n + \frac{f''(x^*)}{2f'(x^*)}e_n^2\right)\left(1 - \frac{f''(x^*)}{f'(x^*)}e_n\right) + O(e_n^3)$$

七、代回误差公式
$$
e_{n+1} = e_n - \frac{f(x_n)}{f'(x_n)}$$
代入上面结果：
$$e_{n+1} = e_n - \left(e_n - \frac{f''(x^*)}{2f'(x^*)}e_n^2 + O(e_n^3)\right)$$
所以：
$$
e_{n+1} = \frac{f''(x^*)}{2f'(x^*)}e_n^2 + O(e_n^3)$$

忽略高阶项，就得到：
$$e_{n+1} \approx \frac{f''(x^*)}{2f'(x^*)}e_n^2$$
八、这说明什么？
这个公式说明：
$$
e_{n+1} \propto e_n^2$$
即误差的平方级下降，这就是牛顿法的二阶收敛。
比如：


| 迭代 | 误差 |
|------|------|
| $n$ | $10^{-3}$ |
| $n+1$ | $\approx C\cdot 10^{-6}$ |
| $n+2$ | $\approx C^2\cdot 10^{-12}$ |
有效数字大约每次翻倍，所以牛顿法在根附近收敛极快。

九、前提条件
这个推导用到了：
1. $f'(x^*) \ne 0$
2. $e_n$ 足够小（初值足够接近根）
3. $f$ 在根附近二阶连续可导

如果这些条件不满足，上面的近似就不成立，牛顿法可能不收敛甚至发散。
一句话总结
把 $f(x_n)$ 和 $f'(x_n)$ 在根 $x^*$ 处泰勒展开，代入牛顿迭代公式，化简后保留最低阶项，就得到
$$e_{n+1} \approx \frac{f''(x^*)}{2f'(x^*)}e_n^2$$

它说明牛顿法是二阶收敛的。


下面用 $|f|$ 表示绝对值。
约定 $t\to 0^+$、$g(t)>0$，常数 $c,C>0$ 不随 $t$ 改变。“最终”表示 $t$ 足够接近 $0$ 时。



| 符号            | 定义或判断方式                                     | 含义                 |
| ------------- | ------------------------------------------- | ------------------ |
| $f=O(g)$      | 最终有 $\lvert f(t)\rvert\leq Cg(t)$           | 上界：大小至多是 $g$ 的常数倍  |
| $f=o(g)$      | $\dfrac{f(t)}{g(t)}\to 0$                   | 高阶无穷小：相对于 $g$ 可以忽略 |
| $f\sim g$     | $\dfrac{f(t)}{g(t)}\to 1$                   | 渐近等价：两者之比趋于 $1$    |
| $f=\Omega(g)$ | 最终有 $\lvert f(t)\rvert\geq cg(t)$           | 下界：大小至少是 $g$ 的正常数倍 |
| $f=\Theta(g)$ | 最终有 $cg(t)\leq \lvert f(t)\rvert\leq Cg(t)$ | 紧确界：同时具有同阶的上界和下界   |
例如，当 $t\to 0^{+}$ 时：

| 例子                                   | 说明                                 |
| ------------------------------------ | ---------------------------------- |
| $t^{4}=O(t^{2})$，而且 $t^{4}=o(t^{2})$ | 因为 $t^4/t^2=t^2\to 0$              |
| $t^{2}+t^{4}\sim t^{2}$              | 因为 $(t^2+t^4)/t^2=1+t^2\to 1$      |
| $3t^{2}=\Theta(t^{2})$               | 所以也满足 $O(t^{2})$ 和 $\Omega(t^{2})$ |
| $3t^{2}\not\sim t^{2}$               | 因为比值是 $3$，不是 $1$                   |
这里采用的是按绝对值定义的 $\Omega,\Theta$；算法复杂度中通常直接比较非负函数。


可以，这些符号并不限定 $t \to 0$。它们可以用于
$$t \to a, \quad t \to a^{\pm}, \quad t \to +\infty, \quad t \to -\infty,$$
也可以用于数列 $n \to \infty$。
但是需要区分：定义和一般运算规则仍然适用；具体函数之间的阶数关系，必须根据趋近方向重新判断。
1. 定义不变，“最终”的含义改变
仍假设比较函数 $g(t)$ 在所讨论的范围内为正。



| 趋近方式            | “最终有 $\lvert f(t)\rvert \leq C g(t)$”是什么意思？             |
| --------------- | ------------------------------------------------------- |
| $t \to a$       | 存在 $\delta > 0$，当 $0 < \lvert t - a\rvert < \delta$ 时成立 |
| $t \to +\infty$ | 存在 $T$，当 $t > T$ 时成立                                    |
| $t \to -\infty$ | 存在 $T$，当 $t < T$ 时成立                                    |

因此，不论趋向哪里，都可以定义
$$
f = O(g), \quad f = o(g), \quad f \sim g, \quad f = \Omega(g), \quad f = \Theta(g).$$
其中比值判据始终是
$$f = o(g) \iff \frac{f}{g} \to 0, \quad f \sim g \iff \frac{f}{g} \to 1,$$ 只是极限所对应的趋近方式不同。

1.趋向无穷时，幂次的大小关系会反过来
之前说

$$t^4 = o(t^2)$$
依赖于 $t \to 0$，因为
$$
\frac{t^4}{t^2} = t^2 \to 0.$$
但当 $t \to +\infty$ 时，
$$\frac{t^4}{t^2} = t^2 \to +\infty,$$
所以此时
$$
t^4 \neq O(t^2), \quad t^4 \neq o(t^2).$$
反而有
$$t^2 = o(t^4).$$

同一个表达式，主项也随极限方向改变：
表达式


|               | $t \to 0$   | $t \to +\infty$ |
| ------------- | ----------- | --------------- |
| $t^2 + t^4$   | $\sim t^2$  | $\sim t^4$      |
| $3t^2 + 5t^4$ | $\sim 3t^2$ | $\sim 5t^4$     |

所以，“高次幂更小”只适用于底数趋于零的情况。
3. 趋向任意有限点，用到该点的距离比较阶数
例如 $t \to 3$，趋于零的是 $t-3$，不是 $t$。因此
$$\frac{(t-3)^4}{(t-3)^2} = (t-3)^2 \to 0,$$
于是
$$
(t-3)^4 = o\big((t-3)^2\big).$$
更一般地，若 $\beta > \alpha$，则
$$|t-a|^\beta = o\big(|t-a|^\alpha\big) \quad (t \to a).$$
而直接比较 $t^4$ 与 $t^2$，当 $t \to 3$ 时，比值趋于 9，所以它们是同阶的：
$$
t^4 = \Theta(t^2),$$
却不是等价的

4. 哪些运算规则不依赖趋近方向？
以下规则在任一指定的极限过程中都成立，仍沿用前面的绝对值定义和 $g > 0$ 的约定：
$$O(g) + O(g) = O(g),$$
$$
o(g) + o(g) = o(g),$$
$$O(g) + o(g) = O(g),$$
$$
\Omega(g) + o(g) = \Omega(g),$$
$$\Theta(g) + o(g) = \Theta(g).$$
以及
$$
f \sim g \iff f = g + o(g).$$
原因是这些证明只依赖于上界、下界或比值极限，不依赖自变量具休趋向哪里。但此前
$$O(t^4) \subset o(t^2)$$

属于特定幂函数的比较，必须注明 $t \to 0$，不能直接搬到 $t \to \infty$。