首页 数学 数值分析

一些关于数值分析的笔记。采用的教材是 Numerical Analysis, Richard L. Burden 与 J. Douglas Faries 著。本篇笔记是一些预备的知识。

# 数学基础

在高等数学中，我们有一些基本的定理，用来解决下面几个基本问题。

# 介值定理

若 f∈C[a,b]f \in C[a,b] 且 K∈(f(a),f(b))K \in (f(a),f(b)), 则 ∃c∈(a,b)\exists c \in (a,b) 使得 f(c)=Kf(c) = K. 该定理称为介值定理 (Intermediate Value Theorem)，是解决方程解的存在性问题的基础。

# 中值定理

# 罗尔定理

若 f∈C[a,b]f \in C[a,b] 且 ff 在 (a,b)(a,b) 上可微，且 f(a)=f(b)f(a) = f(b), 则 ∃c∈(a,b)\exists c \in (a,b) 使得 f′(c)=0f'(c) = 0. 该定理称为罗尔定理 (Rolle's Mean Value Theorem)。

对于罗尔中值定理，我们有一个显然的推论：

设 f∈C[a,b]f \in C[a,b] 且在 (a,b)(a,b) 上 nn 次可微，若 ∃x0<x1<⋯<xn\exists x_0 < x_1 < \dots < x_n 使得 f(xi)=0,i=0,1,…,nf(x_i) = 0, i=0,1,\dots,n，则∃c∈(x0,xn)\exists c \in (x_0,x_n) 使得f(n)(c)=0f^{(n)}(c) = 0。该定理称为一般罗尔定理 (Generalized Rolle's Theorem)。

显然，连续使用 nn 次罗尔定理即可证明。

# 拉格朗日中值定理

若 f∈C[a,b]f \in C[a,b] 且 ff 在 (a,b)(a,b) 上可微，则 ∃c∈(a,b)\exists c \in (a,b) 使得 f′(c)=f(b)−f(a)b−af'(c) = \frac{f(b) - f(a)}{b-a}. 该定理称为拉格朗日中值定理 (Lagrange's Mean Vakue Theorem)。

# 柯西中值定理

若f,g∈C[a,b]f,g \in C[a,b] 且f,gf,g 均在(a,b)(a,b) 上可微，则∃c∈(a,b)\exists c \in (a,b) 使得(g(b)−g(a))f′(c)=(f(b)−f(a))f′(c)(g(b)-g(a))f'(c) = (f(b) - f(a))f'(c)。特别地，若g′(c)≠0g'(c) \neq 0 且g(a)≠g(b)g(a) \neq g(b)，则可以写成f′(c)g′(c)=f(b)−f(a)g(b)−g(a)\frac{f'(c)}{g'(c)} = \frac{f(b) - f(a)}{g(b) - g(a)}，该定理称为柯西中值定理 (Cauchy's Mean Value Theorem)。

# 极值定理

若f∈C[a,b]f \in C[a,b]，则∃c1,c2\exists c_1,c_2 使得∀x∈[a,b]\forall x \in [a,b]，满足f(x)∈[f(c1),f(c2)]f(x) \in [f(c_1), f(c_2)]。若ff 在(a,b)(a,b) 上可微，则c1,c2c_1,c_2 是[a,b][a,b] 的端点或是使ff 在此处导数为00 的点。

# 泰勒定理

设 f∈Cn[a,b]f \in C^n[a,b], f(n+1)f^{(n+1)} 在 [a,b][a,b] 上存在，且 x0∈[a,b]x_0 \in [a,b], 则对 ∀x∈[a,b]\forall x \in [a,b], 存在 x0x_0 与 xx 间的数 ξ(x)\xi (x) 使得

f(x)=∑k=0nf(k)(xk)k!(x−x0)k+f(n+1)(ξ(x))(n+1)!(x−x0)n+1f(x) = \sum_{k=0}^n\frac{f^{(k)}(x_k)}{k!}(x-x_0)^k+\frac{f^{(n+1)}(\xi(x))}{(n+1)!}(x-x_0)^{n+1}

此时称

Pn(x)≔∑k=0nf(k)(xk)k!(x−x0)kP_n(x) \coloneqq \sum_{k=0}^n\frac{f^{(k)}(x_k)}{k!}(x-x_0)^k

为 nn 阶 泰勒多项式 (Taylor polynomial)，称

Rn(x)≔f(n+1)(ξ(x))(n+1)!(x−x0)n+1R_n(x) \coloneqq \frac{f^{(n+1)}(\xi(x))}{(n+1)!}(x-x_0)^{n+1}

为与 PnP_n 相关的余项 (remainder term) 或截断误差 (truncation error)。

若 n→∞n\to \infty, 称此时得到的无穷级数为泰勒级数 (Taylor series)。

# 误差分析基础

在数值分析中，计算的两个目标是找到近似值和确定逼近的精度。由此，就产生了误差分析的想法。在数值计算中，误差常包括以下两类：

  1. 截断误差 (truncation error)：采用有限和估计无穷级数产生的误差。
  2. 舍入误差 (round-off error)：采用近似数代替原数产生的误差。

# 舍入误差的相关概念

# 绝对误差和相对误差

若 p∗p^* 是 pp 的近似数，那么称 ∣p−p∗∣|p-p^*| 为绝对误差 (absolute error)，称 ∣p−p∗∣∣p∣\frac{|p-p^*|}{|p|} 是相对误差 (relative error)。

# 有效数字

若 tt 是最大的自然数，使得

∣p−p∗∣∣p∣≤5×10−t\frac{|p-p^*|}{|p|} \leq 5\times 10^{-t}

则称数 p∗p^* 称为逼近到 pp 的 tt 位有效数字 (significant digits)。

# 一些常见的减小误差的方法

常见的减小误差的方法包括有理化 (rationalization) 和嵌套算法 (nested arithmetic)。例如，秦九韶算法 (Horner algorithm) 是嵌套算法的应用。

# 算法和收敛性

# 算法

由于数值分析是给出近似估计方法，同时考虑计算机计算精度和速度的学科，于是在数值分析中，我们一般需要给出具体的算法 (常以伪代码的形式)。在数值分析的算法中，我们的输入除已知参数值外，一般还包括精度要求TOLTOL 和最大迭代次数MM。这两项是算法终止的判断标志。

# 收敛性

收敛性和分析中的定义相同。

设{βn}n=1∞\{\beta_n\}_{n=1}^\infty 是收敛于00 的已知序列，{αn}n=1∞\{\alpha_n\}_{n=1}^\infty 收敛于α\alpha，若∃K∈R+,N∈N+\exists K \in \mathbb{R}_+, N \in \mathbb{N}_+ 使得

∣αn−α∣≤K∣βn∣|\alpha_n-\alpha| \leq K|\beta_n|

对∀n≥N\forall n \geq N 成立，则称{αn}\{\alpha_n\} 以收敛速度O(βn)O(\beta_n) 收敛于α\alpha，记作αn=α+O(βn)\alpha_n = \alpha + O(\beta_n). 我们常使用的比较对象βn=1np\beta_n=\frac{1}{n^p}, p∈R+p\in\mathbb{R}_+.

如果不采用辅助数列进行收敛速度定义，我们可以定义收敛阶的概念。

设{pn}n=1∞\{p_n\}_{n=1}^\infty 收敛于pp，且∀n,pn≠p\forall n, p_n \neq p，则若存在λ,α∈R+\lambda,\alpha\in\mathbb{R}_+ 使得

lim⁡n→∞∣pn+1−p∣∣pn−p∣m=λ\lim_{n \to \infty}\frac{|p_{n+1}-p|}{|p_n-p|^m} = \lambda

成立，则称{pn}\{p_n\} 以阶 (order)α\alpha 收敛于pp，且渐近误差常数 (asymptotic error constant) 为λ\lambda.