计算方法选择判断

1. 误差限

精确值为 $x$，其近似值为 $x^∗$

绝对误差限

绝对误差限 $\varepsilon$ ，满足：$|x−x^∗|\leq\varepsilon$

相对误差限

相对误差限 $\varepsilon_r$，满足：

$$\left| \frac{x - x^*}{x} \right| \le \varepsilon_r\ \ \text{或} \ \ \left| \frac{x - x^*}{x^*} \right| \le \varepsilon_r$$

例：$x_1 = 4.8675$ 的绝对误差限为：$\varepsilon(x_1) = 0.5\times 10^{-4}$

绝对误差限公式：

$$\text{和运算：}\varepsilon_z = \varepsilon_x + \varepsilon_y$$

$$\text{积运算：}\varepsilon_z \le \varepsilon_x |y| + |\tilde{x}| \varepsilon_y$$

$$\text{商运算：}\varepsilon_z \le \frac{\varepsilon_x \cdot |\tilde{y}| + |\tilde{x}| \cdot \varepsilon_y}{|y| \cdot |\tilde{y}|}$$

2. 方程求根方法对比

二分法

基本思想：利用连续函数在区间内存在零点的中值定理，逐步缩小区间长度。

收敛性：

• 一定收敛（线性收敛，慢但稳定）；
• 每一步误差减半，误差界为：

$$|x_n - x^*| \le \frac{b - a}{2^n}$$

优点：计算简单，函数性质要求低，连续即可
缺点：不能求偶数重根，不能求复根

不动点迭代法

基本思想：将 $f(x) = 0$ 转化为等价形式 $x = \varphi(x)$，迭代公式为：

$$x_{n+1} = \varphi(x_n)$$

极可能考

收敛条件

设迭代区间为 $[a, b]$：

1. $\varphi(x)$ 在 $[a, b]$ 上连续；
2. $\varphi([a, b]) \subseteq [a, b]$（自映性）；
3. $\exists \lambda < 1$，使得 $\forall x \in [a, b]$ 有 $|\varphi'(x)| \le \lambda$ 。

满足上述条件时，称 $\varphi(x)$ 为收敛函数，迭代一定收敛，且为 线性收敛。

常考陷阱

• 判断公式是否收敛，要看 $\varphi'(x)$ 的最大绝对值是否小于 1。
• 若 $|\varphi'(x^*)| > 1$，则迭代发散；
• $|\varphi'(x^*)| = 1$：无法判断，一般发散；
• 有时函数变形后不满足自映区间，导致迭代跑飞。

牛顿迭代法

基本思想：利用泰勒展开一阶近似，迭代公式为：

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

常考陷阱：

• 初值不合适时会不收敛甚至震荡 ；
• $f'(x_n)$ 不能为 0，否则除零错误；
• 对于重根收敛变为线性；
• 求根速度最快，但对初值和导数要求高。

方法对比总结

方法	收敛阶	是否全局收敛	收敛条件	导数要求	初值敏感性	特点
二分法	线性	是	$f(a)f(b) < 0$ 且 $f$ 连续	否	否	稳定、慢、保守
不动点迭代法	线性	取决于公式	$\varphi'(x^*) < 1$, 自映	一阶	中等	实现简单，容易发散
牛顿法	二阶	否（局部）	$f', f''$ 存在，$f'(x^*) \ne 0$	一阶	敏感	收敛快，需导数，初值重要

考试高频判断/选择知识点

1. 牛顿法一定收敛：错（对初值敏感）
2. 二分法不要求导数：对（只要求函数连续）
3. 若不动点迭代的导函数在迭代区间最大值大于1，则发散：对
4. 不动点迭代一定存在收敛公式：错（变形方式非常关键）
5. 牛顿法在重根处是二阶收敛"：错 是线性收敛，必须改进才能保持二阶）

3. 线性方程组数值解法

1. 高斯消去法的总乘除次数为 $\frac{n^3}{3}+n^2-\frac{1}{3}n$, 总运算量为 $\frac{n^3}{3}$ 数量级
2. 给定方程组，则迭代格式 $x^{(k+1)}=Bx^{(k)}+f$ 对任意初值 $x_0$ 都收敛的充要条件为 $\lambda_{max}(B) < 1$

4. 插值法

1. 插值多项式是存在且唯一的
2. 给定 $x_i$ 的值，要能选出 $l_i(x)$ 的图像。
   • 例：给定 $x_i = i +1, i = 0, 1, 2, 3, 4, 5$. 下面哪个是 $l_2(x)$ 的图像
   • 方法：由 $x_i$ 就能解出拉格朗日插值基函数的表达式。 基函数与结点 $x_i$ 有关，与 $f(x)$ 无关
3. 差商具有对称性，即在 k 阶差商 $f[x_0,x_1,\dots,x_k]$ 中任意调换2个节点 $x_l$ 和 $x_m$ 的顺序，其值不变。
4. k 阶差商和 k 阶导数的关系：

$$f[x_0,x_1,\dots,x_k] = \frac{f^{(k)}}{k!}$$

当 $k\leq n$ 时，k阶差商为 n-k 次多项式；当$k>n$ 时恒为0.
5. 高次插值函数会发生龙格现象，在端点附近剧烈抖动