数值计算，即数值分析，是一门研究各种数学问题数值解法及其理论的学科。在实际中，当精确解析法难以求解数学问题时，数值计算发挥重要作用。它涵盖函数逼近与插值、数值积分与微分、线性方程组求解、非线性方程（组）求解以及常微分方程初值问题数值解法等方面。通过各种特定的方法，如插值法、最小二乘法、梯形法、辛普森法、高斯消元法、迭代法、牛顿法、欧拉法、龙格 - 库塔法等，为科学与工程领域，包括物理学、工程学、计算机科学、经济学等提供强大的解决复杂实际问题的工具，进行模拟、预测和优化。

课程章节

• CH1 数值计算方法绪论。
• CH2 插值法。
• CH3 函数逼近与曲线拟合。
• CH4 数值积分与数值微分。
• CH5 线性方程组的直接解法。
• CH6 线性方程组的迭代解法。
• CH7 非线性方程（组）的数值解法。
• CH8 常微分方程初值问题数值解法。
• CH9 深度学习中的数值问题。

# 误差

在数值计算中可能产生的误差主要有：

• 模型误差
• 观测误差
• 截断误差
• 舍入误差

在数值计算中将着重研究 截断误差、舍入误差，并对它们的传播与积累作出分析

---

# 绝对误差

近似值：$x^*$ ；准确值：$x$

绝对误差：近似值与准确值之差

$e^* = x^* - x$

绝对误差限：误差绝对值的上界

\begin{align} |e^*|&=|x^*-x|\le \epsilon^*\\ x&= x^*\pm \epsilon^* \end{align}

# 相对误差

相对误差：误差与准确值的比值

$$e^*_r =\frac{e^*}{x}\approx\frac{e^*}{x^*}=\frac{x^*-x}{x^*}$$

相对误差限：相对误差绝对值的上界 $\epsilon^*_r$ , 即 $|e^*_r| \le \epsilon^*_r$

$$\epsilon^*_r = \frac{\epsilon^*}{|x^*|}$$

$\epsilon^*$ 是绝对误差限

# 有效数字

一、有效数字的定义

在数值计算中，若一个近似值 $x$ 的误差限是其某一位上的 半个单位 ，且从该位到 $x$ 的左边第一个非零数字一共有 $n$ 位，则称近似值 $x$ 有 $n$ 位有效数字。

例如，取圆周率 $\pi$ 的近似值为 3.14，它的误差限不超过 0.005，从左边第一个非零数字 3 到最后一位数字 4 一共有三位，则近似值 3.14 有三位有效数字。

二、有效数字和相对误差限的关系

1. 设近似值 $x$ 表示为 $x=\pm0.a_1a_2\cdots a_n\times10^{m}$，其中 $a_1,a_2,\cdots,a_n$ 是 0 到 9 中的数字，$a_1\neq0$，$m$ 为整数。若 $x$ 有 $n$ 位有效数字，则其相对误差限为：

   • $\delta\leq\frac{1}{2a_1}\times10^{-(n - 1)}$。

   反过来，如果已知近似值 $x$ 的相对误差限满足上述条件，也可以确定 $x$ 具有 $n$ 位有效数字。

2. 举例说明：

   • 若近似值 $x = 0.00324$ 有三位有效数字，从左边第一个非零数字 3 开始，到最后一位数字 4 一共有三位。此时 $a_1 = 3$，$n = 3$，代入相对误差限公式可得：

     $\delta\leq\frac{1}{2\times3}\times10^{-(3 - 1)}=\frac{1}{6}\times10^{-2}=0.00167$。

   • 若已知一个近似值的相对误差限为 $0.005$，假设这个近似值为 $x=\pm10^{m}\times0.a_1a_2\cdots a_n\times10^{m}$，根据相对误差限公式 $\delta\leq\frac{1}{2a_1}\times10^{-(n - 1)}$，当 $a_1 = 1$ 时，$0.005=\frac{1}{2\times1}\times10^{-(n - 1)}$，通过求解可得 $n = 2$，即该近似值有两位有效数字。

# 病态问题和条件数

一、病态问题

当一个数学问题的解对数据的微小变化非常敏感时，就称这个问题为病态问题。

例如，考虑线性方程组 $Ax = b$，其中 $A$ 是系数矩阵，$x$ 是未知向量，$b$ 是右端项。如果系数矩阵 $A$ 的微小变化会导致解 $x$ 发生很大的变化，那么这个线性方程组就是病态的。

病态问题在实际计算中会带来很大的困难，因为数据的测量或计算过程中不可避免地会存在误差，而对于病态问题，这些误差可能会被极大地放大，使得计算结果的可靠性大大降低。

二、条件数

条件数是用来衡量一个问题病态程度的指标。

1. 对于线性方程组$Ax = b$，矩阵 $A$ 的条件数定义为$cond_v = \|A\|_v\|A^{-1}\|_v$，其中 $\|\cdot\|$ 表示矩阵的$v$ 范数.

   • 条件数越大，说明问题越病态，解对数据的微小变化就越敏感。
   • 条件数越小，问题的病态程度就越低，解相对比较稳定。

2. 例如，当条件数非常大时，即使右端项 $b$ 只有很小的误差，解 $x$ 可能会产生很大的误差。而当条件数较小时，数据的微小误差对解的影响相对较小。

在数值计算中，了解问题的病态程度是非常重要的，可以通过分析条件数来判断问题是否病态，并采取相应的措施来减少误差的影响，比如使用更稳定的算法、提高数据的精度等。

矩阵为方阵且满秩则存在逆矩阵

---

1. 计算函数值问题的条件数定义为：相对误差比值 $\left|\frac{f(x)-f\left(x^{*}\right)}{f(x)}\right| /\left|\frac{\Delta x}{x}\right| \approx\left|\frac{x f^{\prime}(x)}{f(x)}\right|$，记为 $C_{p}$。
2. 如果条件数 $C_{p}$ 很大，即使自变量相对误差一般不大，也会引起函数值相对误差很大。出现这种情况的问题被称为病态问题。
3. 一般情况下，当条件数 $C_{p}\geq10$ 时，就认为是病态问题，并且条件数越大，病态越严重。

病态问题

1. 病态问题在数值计算中会带来很大的挑战。因为在实际计算中，数据往往存在一定的误差，而对于病态问题，这些误差会被极大地放大，导致计算结果的可靠性降低。
2. 为了应对病态问题，可以采取一些措施。例如，使用更稳定的算法、提高数据的精度、进行数据预处理以减少误差等。
3. 在实际应用中，判断一个问题是否为病态问题是非常重要的。可以通过计算条件数来初步判断问题的病态程度。如果条件数较大，就需要更加谨慎地处理问题，以避免误差的过度放大。
4. 不同的问题可能具有不同程度的病态性。有些问题可能在特定的参数范围内是病态的，而在其他参数范围内则是良态的。因此，在分析问题时，需要综合考虑各种因素，以确定问题的病态程度。
5. 除了计算函数值问题，在其他数值计算问题中，也可以类似地定义条件数来衡量问题的病态程度。例如，在求解线性方程组、插值问题、数值积分等问题中，都可以通过分析条件数来判断问题的稳定性和可靠性。

additional : 数值稳定性

# 插值

# 拉格朗日插值

一、基本概念

给定 $n+1$ 个互异的节点 $(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)$，其中 $x_i$ 互不相同，$y_i$ 为对应的函数值。拉格朗日插值的目的是构造一个次数不超过 $n$ 的多项式 $L_n(x)$，使得在这些节点上，$L_n(x_i)=y_i$，即多项式在给定的节点处与函数值相等。

二、插值多项式的形式

拉格朗日插值多项式的形式为：

$$L_n(x)=\sum_{i = 0}^{n}y_il_i(x)$$

其中 $L_i(x)$ 为拉格朗日基函数，定义为：

$$l_i(x)=\prod_{j = 0, j\neq i}^{n}\frac{x - x_j}{x_i - x_j}$$

三、计算步骤

1. 确定插值节点：给定一组互异的节点 $(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)$。
2. 计算拉格朗日基函数：对于每个 $i$，计算 $L_i(x)$。
   • 例如，当 $n = 2$ 时，假设有三个节点 $(x_0,y_0),(x_1,y_1),(x_2,y_2)$，则：
     • $l_0(x)=\frac{(x - x_1)(x - x_2)}{(x_0 - x_1)(x_0 - x_2)}$；
     • $l_1(x)=\frac{(x - x_0)(x - x_2)}{(x_1 - x_0)(x_1 - x_2)}$；
     • $l_2(x)=\frac{(x - x_0)(x - x_1)}{(x_2 - x_0)(x_2 - x_1)}$。
3. 计算插值多项式：将节点的函数值 $y_i$ 和对应的基函数 $L_i(x)$ 代入插值多项式公式，得到 $L_n(x)=\sum_{i = 0}^{n}y_il_i(x)$。

四、特点和应用

1. 特点：

   • 拉格朗日插值多项式在节点处与给定的函数值完全相等，具有较高的精度。
   • 当节点增加时，需要重新计算整个插值多项式，计算量较大。
   • 对于高次插值，可能会出现龙格现象，即在插值区间的两端，插值多项式的波动较大，与原函数的差异较大。

2. 应用：

   • 函数逼近：可以用拉格朗日插值多项式来逼近一个未知的函数。
   • 数据拟合：当只有离散的数据点时，可以通过拉格朗日插值得到一个连续的函数表达式。
   • 数值积分和数值微分：可以利用插值多项式进行数值积分和数值微分的计算。

例题

假设有三个数据点 $(1,2)$、$(2,5)$、$(3,10)$，要求通过拉格朗日插值法构造一个插值多项式来逼近函数关系。

1. 首先确定插值基函数：

   • 对于三个节点，$n = 2$。
   • 当 $j = 0$ 时，$x_0 = 1$，对应的基函数 $l_0(x)=\frac{(x - x_1)(x - x_2)}{(x_0 - x_1)(x_0 - x_2)}=\frac{(x - 2)(x - 3)}{(1 - 2)(1 - 3)}=\frac{(x - 2)(x - 3)}{2}$.
   • 当 $j = 1$ 时，$x_1 = 2$，对应的基函数 $l_1(x)=\frac{(x - x_0)(x - x_2)}{(x_1 - x_0)(x_1 - x_2)}=\frac{(x - 1)(x - 3)}{(2 - 1)(2 - 3)}=(x - 1)(x - 3)$.
   • 当 $j = 2$ 时，$x_2 = 3$，对应的基函数 $l_2(x)=\frac{(x - x_0)(x - x_1)}{(x_2 - x_0)(x_2 - x_1)}=\frac{(x - 1)(x - 2)}{(3 - 1)(3 - 2)}=\frac{(x - 1)(x - 2)}{2}$。

2. 然后构造插值多项式：

   • 插值多项式为

     $$L_2(x)= y_0l_0(x)+y_1l_1(x)+y_2l_2(x)$$

   • 已知 $y_0 = 2$，$y_1 = 5$，$y_2 = 10$. 则

     $$L_2(x)= 2\times\frac{(x - 2)(x - 3)}{2}+5\times(x - 1)(x - 3)+10\times\frac{(x - 1)(x - 2)}{2}.$$

   • 化简可得：$L_2(x)=x^2 + 2x - 1$。 这个插值多项式 $L_2(x)$ 在给定的三个节点处与函数值相等，即 $L_2(1)=2$，$L_2(2)=5$，$L_2(3)=10$。它可以用来逼近这三个数据点所代表的函数关系。

   • 事实上如果这是一个 2 次函数，则二次拉格朗日插值得到的就是 原函数 。

     在拉格朗日插值中，利用余项表达式（2.12）可知，若被插函数 $f(x)\in H_n$，由于 $f^{(n + 1)}(x)=0$，故 $R_n(x)=f(x)-L_n(x)=0$，即它的插值多项式 $L_n(x)=f(x)$。

在拉格朗日插值中，插值余项与误差估计是评估插值效果的重要指标。

五、插值余项

若在区间 $[a,b]$ 上用 $L_n(x)$ 近似 $f(x)$，则截断误差 $R_n(x)=f(x)-L_n(x)$ 被称为插值多项式的余项。

六、误差估计

定理 2.red}：设({(n)) $f(x)$ 在 $[a,b]$ 上连续，$f^{(n + 1)}(x)$ 在 $(a,b)$ 内存在，节点 $a\leq x_0\lt x_1\lt\cdots\lt x_n\leq b$，$L_n(x)$ 是满足特定条件的插值多项式，则对任何 $x\in[a,b]$，插值余项

$$R_{n}(x)= f(x)-L_{n}(x)=\frac{f^{(n + 1)}(\xi)}{(n + 1)!}\omega_{n + 1}(x).$$

这里 $\xi\in(a,b)$ 且依赖于 $x$，$\omega_{n + 1}(x)=\prod_{j = 0}^{n}(x - x_j)$.

1. 这个公式可以用来估计插值的误差。当 $f^{(n + 1)}(x)$ 在区间上有界时，可以通过余项公式得到误差的上界。

   • 例如，如果能确定 $f^{(n + 1)}(x)$ 的一个上界 $M$，即对于所有的 $x\in(a,b)$，有

     $$\vert f^{(n + 1)}(x)\vert\leq M​$$

     那么误差

     $$\vert R_n(x)\vert =\vert\frac{f^{(n + 1)}(\xi)}{(n + 1)!}\omega_{n + 1}(x)\vert\leq\frac{M}{(n + 1)!}\vert\omega_{n + 1}(x)\vert.$$

2. 从误差估计可以看出以下几点：

   • 插值多项式的次数 $n$ 越高，理论上误差可能会越小。因为分母 $(n + 1)!$ 随着 $n$ 的增大而增大。

   • 然而，在实际应用中，高次插值并不一定总是能得到更好的结果。这是因为高次插值可能会出现龙格现象，即在插值区间的两端，插值多项式的波动较大，与原函数的差异较大。

   • 插值节点的分布也会影响误差。如果插值节点分布不均匀或者过于密集，可能会导致误差增大。

# 差商

一、定义

设有函数 $f(x)$ 以及一系列互不相等的点 $x_0,x_1,\cdots,x_n$，则 $f$ 在这些点处的一阶差商定义为：

$$f [x_i, x_{i + 1}] =\frac{f(x_{i + 1})-f(x_i)}{x_{i + 1}-x_i}$$

二阶差商定义为：

$$f [x_i, x_{i + 1}, x_{i + 2}] =\frac{f [x_{i + 1}, x_{i + 2}]-f [x_i, x_{i + 1}]}{x_{i + 2}-x_i}$$

以此类推，$n$ 阶差商定义为：

$$f [x_0, x_1,\cdots, x_n] =\frac{f [x_1, x_2,\cdots, x_n]-f [x_0, x_1,\cdots, x_{n - 1}]}{x_n - x_0}$$

二、性质

1. 对称性：差商的值与节点的顺序无关。即对于任意的置换 $\sigma$，有 $f[x_{\sigma(0)},x_{\sigma(1)},\cdots,x_{\sigma(n)}]=f[x_0,x_1,\cdots,x_n]$。

2. 可通过 差商表 计算：可以通过构造差商表来方便地计算高阶差商。差商表是一个二维表格，其中第一列是节点，其余列是对应节点的差商。从低阶到高阶逐步计算差商，可以提高计算效率。

3. 若 $f(x)$ 在 $[a,b]$ 上存在 $n$ 阶导数，且节点 $x_0,x_1,\cdots,x_n\in[a,b]$，则 $n$ 阶均差与导数关系如下：

   $f[x_0,x_1,\cdots,x_n]=\frac{f^{(n)}(\xi)}{n!}$，$\xi\in[a,b]$.

   这公式可直接用罗尔定理证明。

   设 $q(x)=f[x,x_0,\cdots,x_n](x - x_0)(x - x_1)\cdots(x - x_n)$，$q(x)$

   在 $x_0,\cdots,x_n$ 处均为零，所以 $q(x)$ 在 $[a,b]$ 上有 $n + 1$ 个零点。

   根据罗尔定理，$q'(x)$ 在 $q(x)$ 的两个零点间至少有一个零点，故 $q'(x)$ 在 $[a,b]$ 内至少有 $n$ 个零点；反复应用罗尔定理，可知 $q^{(n)}(x)$ 在 $[a,b]$ 内至少有 $1$ 个零点，记为 $\xi\in[a,b]$，使

   $q^{(n)}(\xi)=f^{(n)}(\xi)-n!f[x_0,\cdots,x_n]=0$，

   所以 $f[x_0,\cdots,x_n]=\frac{f^{(n)}(\xi)}{n!}$。

三、应用

1. 牛顿插值：差商在牛顿插值法中起着关键作用。牛顿插值多项式的形式为：

$$N_n(x)= f(x_0)+f [x_0, x_1](x - x_0)+f [x_0, x_1, x_2](x - x_0)(x - x_1)+\cdots+f [x_0, x_1,\cdots, x_n](x - x_0)(x - x_1)\cdots(x - x_{n - 1})$$

通过差商可以确定插值多项式的系数，从而实现对函数的逼近。

2. 数值微分：可以利用差商来近似计算函数的导数。例如，一阶导数可以近似为一阶差商，即 $f^\prime(x)\approx\frac{f(x + h)-f(x)}{h}$，其中 $h$ 是一个小的增量。

四、差商表计算

以下是升序下标的差商表示例：

$x_k$	$f(x_k)$	一阶差商	二阶差商	三阶差商	四阶差商	$\cdots$	$n$ 阶差商
$x_0$	$f(x_0)$					$\cdots$
$x_1$	$f(x_1)$	$f[x_0,x_1]$				$\cdots$
$x_2$	$f(x_2)$	$f[x_1,x_2]$	$f[x_0,x_1,x_2]$			$\cdots$
$x_3$	$f(x_3)$	$f[x_2,x_3]$	$f[x_1,x_2,x_3]$	$f[x_0,x_1,x_2,x_3]$		$\cdots$
$x_4$	$f(x_4)$	$f[x_3,x_4]$	$f[x_2,x_3,x_4]$	$f[x_1,x_2,x_3,x_4]$	$f[x_0,x_1,x_2,x_3,x_4]$	$\cdots$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$
$x_n$	$f(x_n)$	$f[x_{n - 1},x_n]$	$f[x_{n - 2},x_{n - 1},x_n]$	$f[x_{n - 3},x_{n - 2},x_{n - 1},x_n]$	$f[x_{n - 4},x_{n - 3},x_{n - 2},x_{n - 1},x_n]$	$\cdots$	$f[x_0,x_1,\cdots,x_n]$

其中一阶差商计算公式为：

$f[x_i,x_{i + 1}]=\frac{f(x_{i + 1}) - f(x_i)}{x_{i + 1}-x_i}$；

二阶差商计算公式为：$f[x_i,x_{i + 1},x_{i + 2}]=\frac{f[x_{i + 1},x_{i + 2}] - f[x_i,x_{i + 1}]}{x_{i + 2}-x_i}$，

以此类推，$n$ 阶差商计算公式为：$f[x_0,x_1,\cdots,x_n]=\frac{f[x_1,x_2,\cdots,x_n]-f[x_0,x_1,\cdots,x_{n - 1}]}{x_n - x_0}$。

# 牛顿插值

牛顿插值法是一种数值插值方法，它通过差商来构建插值多项式。与拉格朗日插值法不同，牛顿插值法在增加新的插值节点时，不需要重新计算整个插值多项式，只需要计算新节点对应的差商项并加入到原有的多项式中即可。

1. 牛顿插值多项式的形式
   • 设给定 $n + 1$ 个互异的节点 $(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)$，牛顿插值多项式 为：

   $$$$

   $$$$

   • 首先计算差商表：从一阶差商开始，逐步计算高阶差商，形成一个差商表。
   • 然后根据差商表中的数据构建牛顿插值多项式：从最低阶的项开始，依次加入高阶差商项，直到得到所需的插值多项式。

以下是通过差商表达式迭代推出牛顿插值公式的过程：

1. 首先从一阶差商开始：

• 已知 $f[x,x_0]= \frac{f(x)-f(x_0)}{x - x_0}$，变形可得 $f(x)=f(x_0)+f[x,x_0](x - x_0)$。

2. 接着引入二阶差商：

   • $f[x,x_0,x_1]=\frac{f[x,x_0]-f[x_0,x_1]}{x - x_1}$，将 $f[x,x_0]=\frac{f(x)-f(x_0)}{x - x_0}$ 代入可得：
   • $f[x,x_0,x_1]=\frac{\frac{f(x)-f(x_0)}{x - x_0}-f[x_0,x_1]}{x - x_1}=\frac{f(x)-f(x_0)-(x - x_0)f[x_0,x_1]}{(x - x_0)(x - x_1)}$。
   • 进一步变形得到 $f(x)=f(x_0)+f[x_0,x_1](x - x_0)+f[x,x_0,x_1](x - x_0)(x - x_1)$。

3. 然后引入三阶差商：

   • $f[x,x_0,x_1,x_2]=\frac{f[x,x_0,x_1]-f[x_0,x_1,x_2]}{x - x_2}$，把前面得到的 $f[x,x_0,x_1]$ 表达式代入可得：
   • $f[x,x_0,x_1,x_2]=\frac{\frac{f(x)-f(x_0)-(x - x_0)f[x_0,x_1]}{(x - x_0)(x - x_1)}-f[x_0,x_1,x_2]}{x - x_2}=\frac{f(x)-f(x_0)-(x - x_0)f[x_0,x_1]-(x - x_0)(x - x_1)f[x_0,x_1,x_2]}{(x - x_0)(x - x_1)(x - x_2)}$。
   • 进而得到 $f(x)=f(x_0)+f[x_0,x_1](x - x_0)+f[x_0,x_1,x_2](x - x_0)(x - x_1)+f[x,x_0,x_1,x_2](x - x_0)(x - x_1)(x - x_2)$。

4. 以此类推：

   • 最终可以得到牛顿插值公式

     $$N_n(x)= f(x_0)+f [x_0, x_1](x - x_0)+f [x_0, x_1, x_2](x - x_0)(x - x_1)+\cdots+f [x_0, x_1,\cdots, x_n](x - x_0)(x - x_1)\cdots(x - x_{n - 1})$$

已知三个数据点 $(1,2)$、$(2,5)$、$(3,10)$，求牛顿插值多项式。

1. 计算差商表：
   • 首先列出数据点：

     $x$	$y$
     1	2
     2	5
     3	10

   • 计算一阶差商：
     • $f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}=\frac{5 - 2}{2 - 1}=3$。
     • $f[x_1,x_2]=\frac{f(x_2)-f(x_1)}{x_2-x_1}=\frac{10 - 5}{3 - 2}=5$。
   • 计算二阶差商：

• $f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}=\frac{5 - 3}{3 - 1}=1$。

差商表如下：

$x$	$y$	一阶差商	二阶差商
$x_0=1$	$y_0=1$
$x_1=2$	$y_1=5$	$f[x_0,x_1]=3$
$x_2=3$	$y_2=10$	$f[x_1,x_2]=5$	$f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}=1$

2. 构建牛顿插值多项式：
   • 根据差商表，牛顿插值多项式为：

   $$N_2(x)= f(x_0)+f [x_0, x_1](x - x_0)+f [x_0, x_1, x_2](x - x_0)(x - x_1)$$

   • 代入数据点的值和差商：

   $$N_2(x)= 2 + 3(x - 1)+1(x - 1)(x - 2)$$

   • 化简得：

   $$N_2(x)= 2 + 3x - 3 + x^2 - 3x + 2 = x^2 + 1$$

所以，对于给定的三个数据点，牛顿插值多项式为 $N_2(x)=x^2 + 1$.

# 差分

以下是对上述内容的总结：

一、等距节点下的牛顿插值公式简化

在实际应用中常遇到等距节点的情形，即 $x_k = x_0 + kh$（$k = 0,1,\cdots,n$），其中 $h$ 为常数步长。此时插值公式可以进一步简化且计算更简单。

二、差分的定义与计算

对于等距节点，设 $x_k$ 点的函数值为 $f_k = f(x_k)$。

• 称 $\Delta f_k = f_{k + 1}-f_k$ 为 $x_k$ 处以 $h$ 为步长的一阶（向前）差分。
• 类似地，$\Delta^2 f_k=\Delta f_{k + 1}-\Delta f_k$ 为 $x_k$ 处的二阶差分。
• 一般地，$\Delta^{n} f_{k}=\Delta^{n - 1} f_{k + 1}-\Delta^{n - 1} f_{k}$ 为 $x_k$ 处的 $n$ 阶差分。

三、引入算子符号

为了表示方便，引入两个常用算子符号

• $I$ 为不变算子，$If_k = f_k$。

• $E$ 为步长为 $h$ 的移位算子，$Ef_k = f_{k + 1}$。

由此可得

• $$\Delta f_k = Ef_k - If_k =(E - I)f_k$$

进一步有

• $$\Delta^{n} f_{k}=(E - I)^{n}f_{k}=\sum_{j = 0}^{n}(-1)^{j}\binom{n}{j}E^{n - j}f_{k}=\sum_{j = 0}^{n}(-1)^{j}\binom{n}{j}f_{n + k - j}$$

其中 $\binom{n}{j}=\frac{n(n - 1)\cdots(n - j + 1)}{j!}$ 为二项式展开系数。

另

$$f_{n + k}= E^{n}f_{k}=(I+\Delta)^{n}f_{k}=\left [\sum_{j = 0}^{n}\binom{n}{j}\Delta^{j}\right] f_{k}$$

$$f [x_{k}, x_{k + 1}] =\frac{f_{k + 1}-f_{k}}{x_{k + 1}-x_{k}}=\frac{\Delta f_{k}}{h}$$

$$f [x_{k}, x_{k + 1}, x_{k + 2}] =\frac{f [x_{k + 1}, x_{k + 2}]-f [x_{k}, x_{k + 1}]}{x_{k + 2}-x_{k}}=\frac{1}{2h^{2}}\Delta^{2}f_{k}$$

四、差分与差商的关系及与导数的关系

1. 一般地有

   $$f [x_k,\cdots, x_{k + m}] =\frac{1}{m!}\frac{1}{h^{m}}\Delta^{m}f_{k}$$

2. 由上述关系和前面的公式又可得到差分与导数的关系：

   $$\Delta^{n}f_{k}= h^{n}f^{(n)}(\xi)$$

   其中 $\xi\in(x_k,x_{k + n})$。

# 分段插值

# 函数逼近

• 插值：在节点处函数值相等
• 拟合：在数据点处误差平凡和最小

# 内积空间

一、定义

设 $C[a,b]$ 是区间 $[a,b]$ 上所有连续函数构成的集合。对于任意的 $f(x),g(x)\in C[a,b]$，定义内积为：
$(f,g)=\int_{a}^{b}f(x)g(x)dx$。

在这个定义下，$C[a,b]$ 构成一个内积空间。

二、性质

1. 对称性：$(f,g)=\overline{(g,f)}$，其中 $\overline{(g,f)}$ 表示 $(g,f)$ 的共轭。对于实函数，即 $(f,g)=(g,f)$。
2. 线性性：对于任意的函数 $f(x),g(x),h(x)\in C[a,b]$ 和实数 $\alpha,\beta$，有 $(\alpha f+\beta g,h)=\alpha(f,h)+\beta(g,h)$。
3. 正定性：$(f,f)\geq0$，且 $(f,f)=0$ 当且仅当 $f(x)=0$。

在数值计算中，函数的范数是一个重要的概念。

# 范数

一、定义

设 $f(x)$ 是定义在区间 $[a,b]$ 上的函数，函数的范数通常有以下几种定义：

1. $L_p$ 范数：

   • 对于 $p\geq1$，$f(x)$ 的 $L_p$ 范数定义为 $\|f\|_{L_p}=\left(\int_{a}^{b}|f(x)|^{p}dx\right)^{\frac{1}{p}}$。
   • 当 $p = 2$ 时，称为 $L_2$ 范数，也记为 $\|f\|_{2}=\sqrt{\int_{a}^{b}f(x)^{2}dx}$。

2. 无穷范数：

   • $f(x)$ 的无穷范数定义为 $\|f\|_{\infty}=\max_{a\leq x\leq b}|f(x)|$。

二、性质

1. 正定性：对于任意函数 $f(x)$，$\|f\|\geq0$，且 $\|f\|=0$ 当且仅当 $f(x)=0$。

2. 齐次性：对于任意实数 $\alpha$ 和函数 $f(x)$，$\|\alpha f\|=|\alpha|\|f\|$.

3. 三角不等式：对于任意函数 $f(x)$ 和 $g(x)$，$\|f + g\|\leq\|f\|+\|g\|$.

4. 平行四边形定理：$\|f + g\|_2^{2}+\|f - g\|_2^{2}=2(\|f\|_2^{2}+\|g\|_2^{2})$.

   证明如下

   1. 首先计算 $\|f + g\|_2^{2}$:

      $$\|f + g\|_2^{2}=\int_{a}^{b}(f(x)+g(x))^{2}dx =\int_{a}^{b}(f(x)^{2}+2f(x)g(x)+g(x)^{2})dx =\int_{a}^{b}f(x)^{2}dx+\int_{a}^{b}2f(x)g(x)dx+\int_{a}^{b}g(x)^{2}dx =\|f\|_2^{2}+2\int_{a}^{b}f(x)g(x)dx+\|g\|_2^{2}$$

   2. 接着计算 $\|f - g\|_2^{2}$：

      $$\|f - g\|_2^{2}=\int_{a}^{b}(f(x)-g(x))^{2}dx =\int_{a}^{b}(f(x)^{2}-2f(x)g(x)+g(x)^{2})dx =\int_{a}^{b}f(x)^{2}dx-\int_{a}^{b}2f(x)g(x)dx+\int_{a}^{b}g(x)^{2}dx =\|f\|_2^{2}-2\int_{a}^{b}f(x)g(x)dx+\|g\|_2^{2}$$

   3. 最后计算 \|f + g\|_2^{2}+\|f - g\|_2^

      $$\|f + g\|_2^{2}+\|f - g\|_2^{2}=(\|f\|_2^{2}+2\int_{a}^{b}f(x)g(x)dx+\|g\|_2^{2})+(\|f\|_2^{2}-2\int_{a}^{b}f(x)g(x)dx+\|g\|_2^{2})= 2(\|f\|_2^{2}+\|g\|_2^{2})$$

# 向量矩阵

一、向量范数

1. 定义：
   对于一个 $n$ 维向量 $\boldsymbol{x}=(x_1,x_2,\cdots,x_n)$，向量范数是一个非负实数 $\|\boldsymbol{x}\|$，满足以下三个性质：

   • 正定性：$\|\boldsymbol{x}\|\geq0$，且 $\|\boldsymbol{x}\|=0$ 当且仅当 $\boldsymbol{x}=\boldsymbol{0}$。
   • 齐次性：对于任意实数 $\alpha$，有 $\|\alpha\boldsymbol{x}\|=|\alpha|\|\boldsymbol{x}\|$。
   • 三角不等式：对于任意两个向量 $\boldsymbol{x}$ 和 $\boldsymbol{y}$，有 $\|\boldsymbol{x}+\boldsymbol{y}\|\leq\|\boldsymbol{x}\|+\|\boldsymbol{y}\|$.

2. 常见的向量范数：

   • $p$ - 范数：$\|\boldsymbol{x}\|_p=\left(\sum_{i = 1}^{n}|x_i|^p\right)^{\frac{1}{p}}$，其中 $p\geq1$。当 $p = 2$ 时，称为欧几里得范数或 $2$ - 范数，$\|\boldsymbol{x}\|_2=\sqrt{\sum_{i = 1}^{n}x_i^2}$。
   • $1$ - 范数：$\|\boldsymbol{x}\|_1=\sum_{i = 1}^{n}|x_i|$。
   • $\infty$ - 范数：$\|\boldsymbol{x}\|_{\infty}=\max_{1\leq i\leq n}|x_i|$。

3. 应用：

   • 用于衡量向量的大小和长度，在数值分析、优化问题、机器学习等领域有广泛应用。例如，在优化算法中，向量范数可以用来衡量迭代过程中解的变化程度。

二、矩阵范数

1. 定义：
   对于一个 $m\times n$ 的矩阵 $\boldsymbol{A}$，矩阵范数是一个非负实数 $\|\boldsymbol{A}\|$，满足以下四个性质：

   • 正定性：$\|\boldsymbol{A}\|\geq0$，且 $\|\boldsymbol{A}\|=0$ 当且仅当 $\boldsymbol{A}=\boldsymbol{0}$。
   • 齐次性：对于任意实数 $\alpha$，有 $\|\alpha\boldsymbol{A}\|=|\alpha|\|\boldsymbol{A}\|$。
   • 三角不等式：对于任意两个矩阵 $\boldsymbol{A}$ 和 $\boldsymbol{B}$，有 $\|\boldsymbol{A}+\boldsymbol{B}\|\leq\|\boldsymbol{A}\|+\|\boldsymbol{B}\|$。
   • 相容性：对于任意两个矩阵 $\boldsymbol{A}$ 和 $\boldsymbol{B}$，有 $\|\boldsymbol{A}\boldsymbol{B}\|\leq\|\boldsymbol{A}\|\|\boldsymbol{B}\|$。

2. 常见的矩阵范数：

   • Frobenius 范数：$\|\boldsymbol{A}\|_F=\sqrt{\sum_{i = 1}^{m}\sum_{j = 1}^{n}|a_{ij}|^2}$，其中 $a_{ij}$ 是矩阵 $\boldsymbol{A}$ 的第 $i$ 行第 $j$ 列元素。
   • 诱导范数：由向量范数诱导而来，对于给定的向量范数 $\|\cdot\|$，矩阵 $\boldsymbol{A}$ 的诱导范数定义为 $\|\boldsymbol{A}\|=\max_{\boldsymbol{x}\neq\boldsymbol{0}}\frac{\|\boldsymbol{A}\boldsymbol{x}\|}{\|\boldsymbol{x}\|}$。例如，由 $2$ - 范数诱导的矩阵范数也称为谱范数，$\|\boldsymbol{A}\|_2=\sqrt{\lambda_{\max}(\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A})}$，其中 $\lambda_{\max}(\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A})$ 表示矩阵 $\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A}$ 的最大特征值。

# 正交

在数值计算中，带权正交是内积空间中一种特殊的正交关系。

一、定义

设 $C[a,b]$ 是区间 $[a,b]$ 上所有连续函数构成的内积空间，对于任意的 $f(x),g(x)\in C[a,b]$，定义带权内积为 $(f,g)_w=\int_{a}^{b}w(x)f(x)g(x)dx$，其中 $w(x)$ 是一个在区间 $[a,b]$ 上的非负函数，称为权函数。

如果两个函数 $f(x)$ 和 $g(x)$ 满足 $(f,g)_w=0$，则称函数 $f(x)$ 与 $g(x)$ 在带权内积空间中带权 $w(x)$ 正交。

二、举例

例如，在区间 $[-1,1]$ 上，取权函数 $w(x)=1-x^2$，函数 $f(x)=x$，$g(x)=x^2$。

$(f,g)_w=\int_{-1}^{1}(1-x^2)x\cdot x^2dx=\int_{-1}^{1}(x^3 - x^5)dx=\left[\frac{x^4}{4}-\frac{x^6}{6}\right]_{-1}^{1}=\frac{1}{4}-\frac{1}{6}-\left(\frac{1}{4}-\frac{1}{6}\right)=0$。

所以在这个带权内积空间中，函数 $x$ 与函数 $x^2$ 带权 $w(x)$ 正交。

三、性质

1. 性质：
   • 带权正交也具有类似普通正交的一些性质，如对称性（若 $f$ 与 $g$ 带权正交，则 $g$ 与 $f$ 也带权正交）、线性性（若 $f_1$ 与 $g$ 带权正交，$f_2$ 与 $g$ 带权正交，则 $\alpha f_1+\beta f_2$ 与 $g$ 也带权正交，其中 $\alpha,\beta$ 为实数）等。
   • 零函数与任何函数在带权内积空间中都带权正交。

# 最佳一致逼近

最佳一致逼近是数值分析中的一个重要概念。

一、基本概念

1. 设 $f(x)\in C[a,b]$，即 $f(x)$ 是区间 $[a,b]$ 上的连续函数。$p_n(x)\in H_n$，其中 $H_n$ 是次数不超过 $n$ 的多项式集合。

   $$\Delta(f, p_n)=\|f - p_n\|_{\infty}=\max_{a\leq x\leq b}|f(x)-p_n(x)|$$

   被称为 $f(x)$ 与 $p_n(x)$ 在 $[a,b]$ 上的偏差。

   这个偏差衡量了多项式 $p_n(x)$ 与函数 $f(x)$ 在区间 $[a,b]$ 上的最大差异程度.

   $$E_n =\inf_{p_n\in H_n}\{\Delta(f, p_n)\}=\inf_{p_n\in H_n}\max_{a\leq x\leq b}|f(x)-p_n(x)|$$

   称为 $f(x)$ 在 $[a,b]$ 上的最小偏差。也就是要在所有次数不超过 $n$ 的多项式中，找到与 $f(x)$ 偏差最小的那个值。

2. 若存在 $p_n^*(x)\in H_n$，使得 $\Delta(f,p_n^*)=E_n$，则称 $p_n^*(x)$ 是 $f(x)$ 在 $[a,b]$ 上的 $n$ 次最佳一致逼近多项式，也称为最小偏差逼近多项式或最佳逼近多项式。它是在次数不超过 $n$ 的多项式中最接近函数 $f(x)$ 的那个多项式。

# 最佳平方逼近

最佳平方逼近是一种重要的函数逼近方法。

一、基本概念

1. 对于函数 $f(x)\in C[a,b]$，如果存在一个 $n$ 次多项式 $s^*(x)=\sum_{j = 0}^{n}a_j\varphi_j$（其中 $\varphi_j$ 是一组基函数），使得

   $$\int_{a}^{b}[f(x)-s^*(x)]^{2}dx =\min_{s(x)\in H_n}\int_{a}^{b}[f(x)-s(x)]^{2}dx$$

   那么称 $s^*(x)$ 为 $f(x)$ 在区间 $[a,b]$ 上的 $n$ 次最佳平方逼近多项式。

   • 这里的目标是找到一个多项式，使得它与原函数 $f(x)$ 在区间 $[a,b]$ 上的 平方误差积分 最小。

2. 若 $f(x)\in C[a,b]$，$\Phi=\text{span}\{\varphi_0,\cdots,\varphi_n\}\subset C[a,b]$，存在 $s^*(x)\in\Phi$ 满足

   $$\int_{a}^{b}\rho(x)[f(x)-s^*(x)]^{2}dx =\min_{s(x)\in\Phi}\int_{a}^{b}\rho(x)[f(x)-s(x)]^{2}dx$$

   则称 $s^*(x)$ 为函数 $f(x)$ 在集合 $\Phi$ 上的最佳平方逼近函数。

   • 这里引入了权函数 $\rho(x)$，可以根据不同的需求对不同点的误差进行加权。

二、求解方法

1. 问题归结为 求系数 $a_j$ 使得

   $$I(a_0,\cdots, a_n)=\int_{a}^{b}\rho(x)[f(x)-\sum_{j = 0}^{n}a_j\varphi_j]^2dx$$

   取得极小值.

   对 $I$ 关于 $a_k$ 求偏导，并令偏导数为 $0$，得到：

   $$\frac{\partial I}{\partial a_{k}}(a_0,\cdots, a_n)= 2\int_{a}^{b}\rho(x)[f(x)-\sum_{j = 0}^{n}a_j\varphi_j]\varphi_{k}dx = 0.$$

   将积分转为内积的形式得到
   $\sum_{j = 0}^{n}a_j\varphi_j\varphi_{k}$

2. 由此得到法方程：

$$\begin{bmatrix}(\varphi_0,\varphi_0)&(\varphi_0,\varphi_1)&\cdots&(\varphi_0,\varphi_n)\\(\varphi_1,\varphi_0)&(\varphi_1,\varphi_1)&\cdots&(\varphi_1,\varphi_n)\\\vdots&\vdots&\cdots&\vdots\\(\varphi_n,\varphi_0)&(\varphi_n,\varphi_1)&\cdots&(\varphi_n,\varphi_n)\end{bmatrix}\begin{bmatrix}a_0\\a_1\\\vdots\\a_n\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix}$$

• 其中 $(\varphi_k,\varphi_j)=\int_{a}^{b}\rho(x)\varphi_k(x)\varphi_j(x)dx$，$(f,\varphi_j)=\int_{a}^{b}\rho(x)f(x)\varphi_j(x)dx$。

三、性质与意义

1. 由于 $\varphi_0,\cdots,\varphi_n$ 线性无关，所以法方程系数行列式 $G_n\neq0$，法方程有唯一解。这意味着可以确定唯一的最佳平方逼近函数。

2. 平方误差为：

   $$\parallel\delta(x)\parallel_{2}^{2}=(f-s^*, f-s^*)=(f, f)-(f, s^*)=\parallel f(x)\parallel_{2}^{2}-\sum_{k = 0}^{n}a_k^{*}(f,\varphi_k).$$

# 曲线拟合

# 最小二乘法

最小二乘法是一种曲线拟合方法，用于在给定的数据点集上找到一个最佳的拟合函数。

一、误差度量

首先定义误差的不同度量方式，包括

• 无穷范数误差

  $\parallel\delta\parallel_{\infty}=\max_{i}\vert\delta_{i}\vert=\max_{i}\vert S(x_{i}) - f(x_{i})\vert$

• 1 - 范数误差

  $\parallel\delta\parallel_{1}=\sum_{i = 0}^{n}\vert\delta_{i}\vert=\sum_{i = 0}^{n}\vert S(x_{i}) - f(x_{i})\vert$.

• 2 - 范数误差 $\parallel\delta\parallel_{2}=\left(\sum_{i = 0}^{n}\delta_{i}^{2}\right)^{\frac{1}{2}}=\left\{\sum_{i = 0}^{n}[S(x_{i}) - f(x_{i})]^{2}\right\}^{\frac{1}{2}}$

• 其中 $\delta_{i}=S(x_{i}) - f(x_{i})$ 表示在点 $x_{i}$ 处拟合函数 $S(x)$ 与实际函数 $f(x)$ 的偏差。最小二乘法要求 2 - 范数误差平方最小，即 $\parallel\delta\parallel_{2}^{2}=\sum_{i = 0}^{n}\delta_{i}^{2}=\sum_{i = 0}^{n}[S(x_{i}) - f(x_{i})]^{2}$ 最小。

二、一般提法

对于给定的数据 $(x_{i},y_{i})(i = 0,1,\cdots,m)$，要求在给定函数类 $\Phi=\text{span}\{\varphi_{0},\cdots,\varphi_{n}\}$ 中找一函数 $s^{*}(x)=\sum_{j = 0}^{n}a_{j}^{*}\varphi_{j}$，其中 $n\lt m$，使得 $s^{*}(x)$ 满足

$$\parallel\delta\parallel_{2}^{2}=\sum_{i = 0}^{m}\delta_{i}^{2}=\sum_{i = 0}^{m}[s^{*}(x_{i}) - f(x_{i})]^{2}=\min_{s(x)\in\Phi}\sum_{i = 0}^{m}[s(x_{i}) - f(x_{i})]^{2}$$

三、更一般提法

更一般地，要求 $\parallel\delta\parallel_{2}^{2}=\sum_{i = 0}^{m}\omega(x_{i})\delta_{i}^{2}=\sum_{i = 0}^{m}\omega(x_{i})[s^{*}(x_{i}) - f(x_{i})]^{2}=\min_{s(x)\in\Phi}\sum_{i = 0}^{m}\omega(x_{i})[s(x_{i}) - f(x_{i})]^{2}$，其中引入了权重函数 $\omega(x_{i})$，可以根据不同的数据点重要性进行调整。

四、问题归结

将最小二乘法问题归结为求 $s(x)=\sum_{k = 0}^{n}a_{k}\varphi_{k}(x)$ 的系数 $a_{k}$，使得

$$I(a_{0},\cdots, a_{n})=\sum_{i = 0}^{m}\omega(x_{i})[\sum_{k = 0}^{n}a_{k}\varphi_{k}(x_{i}) - f(x_{i})]^{2}$$

取得极小值。

引入内积记号

$$(\varphi_{k},\varphi_{j})=\sum_{i = 0}^{m}\omega(x_{i})\varphi_{k}(x_{i})\varphi_{j}(x_{i})$$

和

$$(f,\varphi_{j})=\sum_{j = 0}^{m}\omega(x_{i})f(x_{i})\varphi_{j}(x_{i})$$

五、多项式拟合及法方程

常用多项式拟合，即 $\Phi=\text{span}\{\varphi_{0},\cdots,\varphi_{n}\}=\text{span}\{1,x,\cdots,x^{n}\}$, $s^{*}(x)=\sum_{k = 0}^{n}a_{k}^{*}x^{k}$. 此时可以得到法方程为：

$$\left[\begin{array}{ccccc} \sum\omega_{i} & \sum\omega_{i}x_{i} & \cdots & \sum\omega_{i}x_{i}^{n}\\ \sum\omega_{i}x_{i} & \sum\omega_{i}x_{i}^{2} & \cdots & \sum\omega_{i}x_{i}^{n + 1}\\ \vdots & \vdots & \cdots & \vdots\\ \sum\omega_{i}x_{i}^{n} & \sum\omega_{i}x_{i}^{n + 1} & \cdots & \sum\omega_{i}x_{i}^{2n} \end{array}\right]\left[\begin{array}{c} a_{0}\\ a_{1}\\ \vdots\\ a_{n} \end{array}\right]=\left[\begin{array}{c} \sum\omega_{i}y_{i}\\ \sum\omega_{i}x_{i}y_{i}\\ \vdots\\ \sum\omega_{i}x_{i}^{n}y_{i} \end{array}\right]$$

通过求解这个法方程，可以得到多项式拟合的系数 $a_{k}$，从而确定最小二乘解 $s^{*}(x)$。

可以通过线性变换将非线性拟合转化为线性拟合

# 数值积分

imphasis

插值型求积公式的概念，求积系数及相关性质

掌握基本的数值求积公式，中矩形求积公式，梯形求积公式，辛普森公式及对应的复化求积公式

自适应求积的基本思想

掌握龙贝格求积的思想及龙贝格求积公式

针对具体的问题会计算代数精度，会用具体的求积公式进行计算求解

# 插值求积与代数精度

一、插值求积

1. 基本概念

   • 插值求积是基于插值多项式来近似计算定积分的方法。其核心思想是先利用已知节点上的函数值构造一个插值多项式，然后对这个插值多项式进行积分来近似原函数的定积分。

2. 具体方法

   • 设给定区间$[a,b]$ 上的$n+1$ 个节点$x_0,x_1,\cdots,x_n$ 及对应的函数值$f(x_0),f(x_1),\cdots,f(x_n)$。
   • 通过这些节点构造一个插值多项式$L_n(x)$，使得$L_n(x_i)=f(x_i)$，$i = 0,1,\cdots,n$。
   • 然后计算插值多项式的积分$\int_{a}^{b}L_n(x)dx$ 作为原函数定积分$\int_{a}^{b}f(x)dx$ 的近似值。

二、代数精度

1. 定义

   • 若一个数值求积公式对于所有次数不超过$m$ 的多项式都能准确成立，而对于某个$m+1$ 次多项式不成立，则称该求积公式具有$m$ 次代数精度。

2. 意义

   • 代数精度是衡量数值求积公式准确性的一个重要指标。代数精度越高，说明该求积公式在对多项式函数进行积分时的准确性越高。
   • 通过确定求积公式的代数精度，可以评估不同求积公式的优劣，为选择合适的求积方法提供依据。

3. 与插值求积的关系

   • 对于插值求积法，其代数精度与所使用的插值多项式的次数有关。一般来说，插值多项式的次数越高，插值求积公式的代数精度也越高。
   • 例如，梯形公式是基于一次插值多项式的求积公式，其代数精度为 1；辛普森公式是基于二次插值多项式的求积公式，其代数精度为 3。

一、插值求积公式的表达式与性质

1. 插值基函数：

• $l_{k}(x)=\prod_{\substack{j = 0\\j\neq k}}^{n}\frac{x - x_{j}}{x_{k}-x_{j}}$（$k = 0,1,\cdots,n$）

  • 插值求积公式定义：

    求积公式

    $$\int_{a}^{b}f(x)dx\approx\sum_{k = 0}^{n}A_{k}f(x_{k})$$

    其系数$A_{k}=\int_{a}^{b}l_{k}(x)dx$ 时，则称求积公式为插值求积公式。

2. 求积公式推导：
   • 对于积分$\int_{a}^{b}l_{k}(x)dx=\sum_{j = 0}^{n}A_{j}l_{k}(x_{j})$，其中$l_{k}(x_{j})=\delta_{kj}=\begin{cases}1&k = j\\0&k\neq j\end{cases}$。
   • 取$f(x)=l_{k}(x)$ 时，$\int_{a}^{b}f(x)dx=\int_{a}^{b}l_{k}(x)dx=\sum_{j = 0}^{n}A_{j}l_{k}(x_{j})$，所以有$A_{k}=\int_{a}^{b}l_{k}(x)dx$，此时求积公式为插值型求积公式。

插值求积公式的余项

1. 余项表达式：

   • 设插值求积公式的余项为$R(f)$，由插值余项定理得

     $$R(f)=\int_{a}^{b}[f(x)-P(x)]dx=\int_{a}^{b}\frac{f^{(n + 1)}(\xi)}{(n + 1)!}\omega(x)dx$$

     其中$\xi\in[a,b]$。

2. 当$f(x)$ 是次数不高于$n$ 的多项式时，$f^{(n + 1)}(x)=0$，$R(f)=0$，求积公式能成为准确的等式。

插值型求积公式的充要条件与代数精度

1. 定理：

• $n + 1$ 个节点的求积公式$\int_{a}^{b}f(x)dx\approx\sum_{k = 0}^{n}A_{k}f(x_{k})$ 为插值型求积公式的充要条件是公式至少具有$n$ 次代数精度。

2. 证明：

   • 必要性：若求积公式为插值型求积公式，求积系数为$A_{k}=\int_{a}^{b}l_{k}(x)dx$。又$f(x)=P(x)+R(x)$，当$f(x)$ 为不高于$n$ 次的多项式时，$f(x)=P(x)$，其余项$R(f)=0$，因而这时求积公式至少具有$n$ 次代数精度。

   • 充分性：若求积公式至少具有$n$ 次代数精度，则对$n$ 次多项式

     l_{k}(x_{j})=\delta_{kj}=\begin{cases}1&k = j\\0&k\neq j\end

     精确成立.$f(x)=l_{k}(x)$ 时，$\int_{a}^{b}f(x)dx=\int_{a}^{b}l_{k}(x)dx=\sum_{j = 0}^{n}A_{j}l_{k}(x_{j})$，所以有$A_{k}=\int_{a}^{b}l_{k}(x)dx$，此时求积公式为插值型求积公式。

代数精度：若求积公式至少具有$n$ 次代数精度，则对$n$ 次多项式，可得方程组

$$\begin{cases}A_{0}+A_{1}+\cdots+A_{n}=b - a\\A_{0}x_{0}+A_{1}x_{1}+\cdots+A_{n}x_{n}=\frac{b^{2}-a^{2}}{2}\\\cdots\cdots\\A_{0}x_{0}^{n}+A_{1}x_{1}^{n}+\cdots+A_{n}x_{n}^{n}=\frac{b^{n + 1}-a^{n + 1}}{n + 1}\end{cases}$$

这是关于$A_{k}$ 的线性方程组，其系数矩阵是范得蒙矩阵，当$x_{k}(k = 0,1,\cdots,n)$ 互异时非奇异，故$A_{k}$ 有唯一解。

四、求积系数与定义

$$A_{k}=\int_{a}^{b}l_{k}(x)dx=\int_{a}^{b}\frac{\omega(x)}{(x - x_{k})\omega'(x_{k})}dx$$

称为求积系数。

# 求积公式

梯形和中矩形只有 1 次代数精度，辛普森有 3 次代数精度

一、牛顿 - 柯特斯公式

1. 梯形公式：

   • 对于区间 $[a,b]$ 上的定积分 $\int_{a}^{b}f(x)dx$，将区间分为两部分，用连接两点 $(a,f(a))$ 和 $(b,f(b))$ 的直线（即梯形的上下底）来近似代替曲线 $f(x)$，得到梯形公式：

   $$\int_{a}^{b}f(x)dx\approx\frac{b - a}{2}[f(a)+f(b)]$$

2. 中矩形公式：

   $$\int_{a}^{b}f(x)dx\approx(b-a)f(\frac{a+b}{2})$$

3. 辛普森公式：

   • 将区间 $[a,b]$ 分为三部分，用二次抛物线来近似代替曲线 $f(x)$。辛普森公式为：

     $$\int_{a}^{b}f(x)dx\approx\frac{b - a}{6}[f(a)+4f(\frac{a + b}{2})+f(b)]$$

4. 牛顿 - 柯特斯公式一般形式：

   • 对于 $n+1$ 个节点的牛顿 - 柯特斯公式为， $\int_{a}^{b}f(x)dx\approx(b - a)\sum_{k = 0}^{n}C_{k}^{(n)}f(x_{k})$ 其中 $C_{k}^{(n)}$ 是柯特斯系数，$x_{k}=a + k\frac{b - a}{n}$。

二、高斯型求积公式

1. 基本思想：

• 高斯型求积公式是在积分区间上选取适当的节点和权系数，使得求积公式具有尽可能高的代数精度。

2. 公式形式：

   $$\int_{a}^{b}f(x)dx\approx\sum_{k = 1}^{n}A_{k}f(x_{k})$$

   其中 $x_{k}$ 是求积节点，$A_{k}$ 是求积系数。

代数精度：插值积分至少有 n 次精度

# 复化求积公式

1. 复化梯形公式：

   将区间 $[a,b]$ 分成 $n$ 个子区间，在每个子区间上应用梯形公式，然后将结果相加。复化梯形公式为：

   $$\int_{a}^{b}f(x)dx\approx\frac{h}{2}[f(a)+2\sum_{i = 1}^{n - 1}f(x_{i})+f(b)]$$

   其中 $h=\frac{b - a}{n}$，$x_{i}=a + ih$。

2. 复化辛普森公式：

   类似地，将区间分成 $n$ 个子区间，在每个子区间上应用辛普森公式，然后相加。复化辛普森公式为：

   $$\int_{a}^{b}f(x)dx\approx\frac{h}{6}[f(a)+4\sum_{i = 0}^{n - 1}f(x_{i+\frac{1}{2}})+2\sum_{i = 1}^{n - 1}f(x_{i})+f(b)]$$

# 低阶求积公式余项

具有 n 阶代数精度的求积公式都可认为是 n 阶的插值求积公式

$$R=I - I^*=\int_a^bS-S^*dx=\int_a^bR_sdx=\int_{a}^{b}\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x) dx$$

# 梯形公式的余项

1. 梯形公式（4.1.1）的余项为

   $$R_{T}=I - T=\int_{a}^{b}\frac{f''(\xi)}{2}(x - a)(x - b)dx$$

   取的左右端点，做的一阶插值

2. 由于积分的核函数$(x - a)(x - b)$ 在区间$[a,b]$ 上保号（非正），应用积分中值定理，在$(a,b)$ 内存在一点$\eta$，使得

$$R_{T}=\frac{f''(\eta)}{2}\int_{a}^{b}(x - a)(x - b)dx=-\frac{f''(\eta)}{12}(b - a)^{3},\quad \eta\in(a,b)$$

# Simpson 公式的余项

1. Simpson 公式（4.2.3）的余项$R_{S}=I - S=\int_{a}^{b}[f(x)-H(x)]dx$，其中$H(x)$ 是构造的次数不大于三的多项式，满足

   $H(a)=f(a)$，$H(b)=f(b)$，$H(c)=f(c)$，$H'(c)=f'(c)$，$c=\frac{a + b}{2}$ 。

2. 由于 Simpson 公式具有三次代数精度，对于这样构造出的三次式$H(x)$ 是准确的，即$\int_{a}^{b}H(x)dx=\frac{b - a}{6}[H(a)+4H(c)+H(b)]$ ，上式右端实际上等于按 Simpson 公式（4.2.3）求得的积分值$S$。

3. 对于满足条件（4.2.6）的多项式$H(x)$，其插值余项

   $f(x)-H(x)=\frac{f^{(4)}(\xi)}{4!}(x - a)(x - c)^{2}(x - b)$，

   所以

$$R_{S}=\int_{a}^{b}\frac{f^{(4)}(\xi)}{4!}(x - a)(x - c)^{2}(x - b)dx$$

4. 积分核$(x - a)(x - c)^{2}(x - b)$ 在$[a,b]$ 上保号（非正），用积分中值定理有

$$R_{S}=\frac{f^{(4)}(\eta)}{4!}\int_{a}^{b}(x - a)(x - c)^{2}(x - b)dx=-\frac{b - a}{180}\left(\frac{b - a}{2}\right)^{4}f^{(4)}(\eta)$$

# Cotes 公式的余项

Cotes 公式（4.2.4）的积分余项仅列出结果为

$$R_{C}=I - C=-\frac{2(b - a)}{945}\left(\frac{b - a}{4}\right)^{6}f^{(6)}(\eta)$$

# 复化梯形余项

$$R_n=I-T_n=-\frac{b - a}{12}\left(\frac{b-a}{n}\right)^2f''(\xi)$$

# 复化辛普森余项

$$R_n=-\frac{b - a}{180}\left(h\right)^{4}f^{(4)}(\xi), \quad h=\frac{b-a}{n}$$

# 自适应求积

一、基本思想

1. 从一个较粗的积分步长开始，计算积分的近似值。
2. 然后将积分步长减半，再次计算积分近似值。
3. 比较两次计算结果的差异，如果差异较大，则继续减小步长进行计算，直到满足一定的精度要求。

二、变步长梯形公式

1. 首先用梯形公式计算积分的近似值：

• 对于区间$[a,b]$ 上的定积分$\int_{a}^{b}f(x)dx$，梯形公式为$T(h)=\frac{h}{2}[f(a)+f(b)]+\sum_{i = 1}^{n - 1}hf(x_{i})$，其中$h=\frac{b - a}{n}$，$x_{i}=a + ih$。

2. 将步长减半，得到新的近似值：

• 令$h'=\frac{h}{2}$，新的梯形公式为$T(h')=\frac{h'}{2}[f(a)+f(b)]+\sum_{i = 1}^{2n - 1}h'f(x_{i}')$。

3. 计算两次近似值的差异：
   • 可以得到

$$T_{2n}=\frac{1}{2}T_n+\frac{h}{2}\sum_{i = 0}^{n-1}f(x_{i+\frac{1}{2}})$$

三、变步长辛普森公式

1. 类似地，可以从辛普森公式出发，逐步减小步长进行计算。

   辛普森公式为

   $$S(h)=\frac{h}{6}[f(a)+f(b)+4\sum_{i = 0}^{n - 1}f(x_{i+\frac{1}{2}})+2\sum_{i = 1}^{n - 1}f(x_{i})]$$

2. 递推公式为

$$S_{2n}=\frac{S_n}{4}+2h\sum_{i=0}^{n-1}\left[f(x_{i+\frac{1}{4}})+f(x_{i+\frac{3}{4}})\right]+\frac{h}{8}\sum_{i=0}^{n-1}f(x_{i})$$

# Romberg 算法

龙贝格

龙贝格算法是一种用于数值积分的高效方法，以下是对图片内容的整理：

一、龙贝格算法计算步骤

1. 按变步长梯形公式计算积分近似值：

   • 对于区间$[a,b]$，先进行区间划分，区间长度$h=\frac{b - a}{n}$（$n = 2^{k}$）。
   • 变步长梯形公式为$T_{2n}=\frac{T_{n}}{2}+\frac{h}{2}\sum_{k = 0}^{n - 1}f(x_{k+\frac{1}{2}})$，其中$x_{k+\frac{1}{2}}=a+(k+\frac{1}{2})h$。

2. 按加速公式求加速值：

   • 梯形公式加速：$S_{n}=T_{2n}+\frac{T_{2n}-T_{n}}{3}$（此处以整理后的正确公式为准，图片中可能有误）。
   • Simpson 加速公式：$C_{n}=S_{2n}+\frac{S_{2n}-S_{n}}{15}$。
   • 龙贝格求积公式：$R_{n}=C_{2n}+\frac{C_{2n}-C_{n}}{63}$。

二、公式推导过程

1. 从柯特斯公式的误差公式进一步导出龙贝格公式：$R_{n}=\frac{64}{63}C_{2n}-\frac{1}{63}C_{n}$。

2. 考察 Simpson 法，其截断误差与$h^{4}$ 成正比，若将步长折半，则误差减至$\frac{1}{16}$，即$\frac{I - S_{2n}}{I - S_{n}}\approx\frac{1}{16}$，由此可得$I=\frac{16}{15}S_{2n}-\frac{1}{15}S_{n}$，可以验证上式右端的值等于$C_{n}$，即$C_{n}=\frac{16}{15}S_{2n}-\frac{1}{15}S_{n}$。

3. 用梯形法二分前后两个积分值$T_{n}$ 和$T_{2n}$ 作线性组合，可得到复化 Simpson 公式计算得到的积分值$S_{n}$，即$S_{n}=\frac{4}{3}T_{2n}-\frac{1}{3}T_{n}$。

三、精度控制

直到相邻两次积分值$\vert R_{2n}-R_{n}\vert<\varepsilon$（其中$\varepsilon$ 为允许的误差限），则终止计算并取$R_{n}$ 作为积分的近似值。

龙贝格算法通过变步长将粗糙的梯形值逐步加工成精度较高的 Simpson 值、柯特斯值和龙贝格值，将收敛缓慢的梯形值序列加工成收敛迅速的龙贝格值序列。

# 例题

1. 计算向量 $x=(1, -2, 3)^T $ 的各种范数

   $\parallel x \parallel_1 = 6$, $\parallel x \parallel_\infin = 3$, \parallel x \parallel_2 = \sqrt

2. 题目：设 $f(x)=\sqrt{1 + x^{2}}$，求在区间 $[0,1]$ 上的一次最佳平方逼近多项式。

   解析：

   1. 首先计算内积：
      • $(f,\varphi_{0})=\int_{0}^{1}\sqrt{1 + x^{2}}dx=\frac{1}{2}\ln(1+\sqrt{2})+\frac{\sqrt{2}}{2}\approx1.147$。
      • $(f,\varphi_{1})=\int_{0}^{1}x\sqrt{1 + x^{2}}dx=\left.\frac{1}{3}(1 + x^{2})^{\frac{3}{2}}\right|_{0}^{1}=\frac{2\sqrt{2}-1}{3}\approx0.609$。
   2. 得到方程组：
      • $\begin{bmatrix}1 & 1/2\\1/2 & 1/3\end{bmatrix}\begin{bmatrix}a_{0}\\a_{1}\end{bmatrix}=\begin{bmatrix}1.147\\0.609\end{bmatrix}$。
   3. 解方程组得：$a_{0}=0.934$，$a_{1}=0.426$。
      • 故一次最佳平方逼近多项式为 $S_{1}^{*}(x)=0.934 + 0.426x$。
   4. 计算平方误差：
      • $\parallel\delta(x)\parallel_{2}^{2}=(f(x),f(x))-(S_{1}^{*}(x),f(x))=\int_{0}^{1}(1 + x^{2})dx - 0.426d_{1}-0.934d_{0}=0.0026$，其中 $d_{0}=(S_{1}^{*}(x),\varphi_{0})$，$d_{1}=(S_{1}^{*}(x),\varphi_{1})$。
   5. 计算最大误差：
      • $\parallel\delta(x)\parallel_{\infty}=\max_{0\leq x\leq1}|\sqrt{1 + x^{2}}-S_{1}^{*}(x)|\approx0.066$。

3. 试确定一个至少具有 2 次代数精度的公式$\int_{0}^{4}f(x)dx\approx Af(0)+Bf(1)+Cf(3)$。

   • 解：要使公式具有 2 次代数精度，则对$f(x)=1,x,x^2$ 求积公式准确成立，即得方程组$\begin{cases}A+B+C=4\\B+3C=8\\B+9C=\frac{64}{3}\end{cases}$，解得$A=\frac{14}{3},B=\frac{4}{3},C=\frac{8}{3}$。因此，所求公式为$\int_{0}^{4}f(x)dx\approx\frac{14}{3}f(0)+\frac{4}{3}f(1)+\frac{8}{3}f(3)$。

4. 试确定求积系数 A、B、C 使$\int_{-1}^{1}f(x)dx\approx Af(-1)+Bf(0)+Cf(1)$ 具有最高的代数精度。

   • 解：分别取$f(x)=1,x,x^2$ 使求积公式准确成立，即得$\begin{cases}A+B+C=2\\-A+C=0\\A+C=\frac{2}{3}\end{cases}$，所得求积公式为$\int_{-1}^{1}f(x)dx\approx\frac{1}{3}f(-1)+\frac{4}{3}f(0)+\frac{1}{3}f(1)$。可验证该求积公式对于$f(x)=1,x,x^2,x^3$ 都准确成立，对于$f(x)=x^4$ 不能准确成立，所以求积公式具有 3 次代数精度。

5. 考察求积公式$\int_{-1}^{1}f(x)dx\approx\frac{1}{2}[f(-1)+2f(0)+f(1)]$ 的代数精度。

   • 解：可以验证，对于$f(x)=1,x$ 时，公式两端相等；再将$f(x)=x^2$ 代入公式，左端为$\int_{-1}^{1}x^{2}dx=\frac{2}{3}$，右端为$\frac{1}{2}[f(-1)+2f(0)+f(1)]=\frac{1}{2}[1+1]=1$，左端不等于右端，所以求积公式具有 1 次代数精度。且三个节点不一定具有 2 次代数精度，因为不是插值型的。

6. 给定求积式$\int_{0}^{1}f(x)dx\approx\frac{1}{3}[2f(\frac{1}{4})-f(\frac{1}{2})+2f(\frac{3}{4})]$，求证此求积公式是插值型求积公式。

   解：

   • 首先计算插值基函数：
     • $l_{0}(x)=\left(x-\frac{1}{2}\right)\left(x-\frac{3}{4}\right)/\left(\frac{1}{4}-\frac{1}{2}\right)\left(\frac{1}{4}-\frac{3}{4}\right)=8\left(x-\frac{1}{2}\right)\left(x-\frac{3}{4}\right)$。
     • $l_{1}(x)=\left(x-\frac{1}{4}\right)\left(x-\frac{3}{4}\right)/\left(\frac{1}{2}-\frac{1}{4}\right)\left(\frac{1}{2}-\frac{3}{4}\right)=-16\left(x-\frac{1}{4}\right)\left(x-\frac{3}{4}\right)$。
     • $l_{2}(x)=\left(x-\frac{1}{4}\right)\left(x-\frac{1}{2}\right)/\left(\frac{3}{4}-\frac{1}{4}\right)\left(\frac{3}{4}-\frac{1}{2}\right)=8\left(x-\frac{1}{4}\right)\left(x-\frac{1}{2}\right)$。
   • 然后计算积分：
     • $\int_{0}^{1}l_{0}(x)dx=8\int_{0}^{1}\left(x^{2}-\frac{5}{4}x+\frac{3}{8}\right)dx=8\left(\frac{1}{3}-\frac{5}{4}\times\frac{1}{2}+\frac{3}{8}\right)=\frac{8}{3}-2=\frac{2}{3}$。
     • $\int_{0}^{1}l_{1}(x)dx=(-16)\int_{0}^{1}\left(x^{2}-x+\frac{3}{16}\right)dx=(-16)\left(\frac{1}{3}-\frac{1}{2}+\frac{3}{16}\right)=\frac{16}{6}-3=-\frac{1}{3}$。
     • $\int_{0}^{1}l_{2}(x)dx=8\int_{0}^{1}\left(x^{2}-\frac{3}{4}x+\frac{1}{8}\right)dx=8\left(\frac{1}{3}-\frac{3}{4}\times\frac{1}{2}+\frac{1}{8}\right)=\frac{8}{3}-2=\frac{2}{3}$。
   • 由插值型求积公式的定义知，所给的求积公式是插值型求积公式。

7. 题目：
   计算定积分$I=\int_{0}^{1}\ln x dx$，依次用$n = 8$ 的复化梯形公式和$n = 4$ 的复化 Simpson 公式进行计算。

   解：

   1. 当$n = 8$ 时：
      • $h=\frac{1}{8}=0.125$。
      • 由复化梯形公式可得计算公式：
        $T_{8}=\frac{1}{16}[f(0)+2f(0.125)+2f(0.25)+2f(0.375)+2f(0.5)+2f(0.625)+2f(0.75)+2f(0.875)+f(1)]=0.9456909$。
   2. 当$n = 4$ 时：
      • 由复化 Simpson 公式可得计算公式：
        $S_{4}=\frac{1}{24}[f(0)+f(1)+2(f(0.25)+f(0.5)+f(0.75))+4(f(0.125)+f(0.375)+f(0.625)+f(0.875))]=0.9460832$。
   3. 积分准确值$I = 0.9460831$。
   4. 两种方法都需要提供 9 个点上的函数值，计算量基本相同，但精度差别较大。与积分准确值比较，复化梯形公式只有两位有效数字，而复化 Simpson 公式却有六位有效数字。

8. 题目：
   用变步长梯形求积公式计算定积分$I=\int_{0}^{1}\frac{\sin x}{x}dx$。

   解：

   1. 先对整个区间$[0,1]$ 用梯形公式：
      • 已知$f(x)=\frac{\sin x}{x}$，$f(0)=1$，$f(1)=0.8410709$。
      • 所以$T_{1}=\frac{1}{2}[f(0)+f(1)]=0.9207355$。
   2. 然后将区间二等分：
      • 由于$f(\frac{1}{2})=0.958851$，故有$T_{2}=\frac{1}{2}T_{1}+\frac{1}{2}f(\frac{1}{2})=0.9397933$。
   3. 进一步二分求积区间，并计算新分点上的函数值：
      • $f(\frac{1}{4})=0.9896158$，$f(\frac{3}{4})=0.9088516$。
      • 有$T_{4}=\frac{1}{2}T_{2}+\frac{1}{4}[f(\frac{1}{4})+f(\frac{3}{4})]=0.9445135$。
   4. 这样不断二分下去，积分准确值为$0.9460831$，从计算结果表中可看出用变步长二分 10 次可得此结果。

9. 题目：用龙贝格算法计算定积分$I=\int_{0}^{1}\frac{4}{1 + x^{2}}dx$，要求相邻两次龙贝格值的偏差不超过$10^{-5}$。

   解：

   1. 已知$a = 0$，$b = 1$，$f(x)=\frac{4}{1 + x^{2}}$。
   2. 首先计算梯形值：
      • $T_{1}=\frac{1}{2}[f(0)+f(1)]=\frac{1}{2}(4 + 2)=3$。
      • $T_{2}=\frac{1}{2}T_{1}+\frac{1}{2}f(\frac{1}{2})=\frac{1}{2}×3+\frac{1}{2}×\frac{16}{5}=3.1$。
      • $T_{4}=\frac{1}{2}T_{2}+\frac{1}{4}[f(\frac{1}{4})+f(\frac{3}{4})]=\frac{1}{2}×3.1+\frac{1}{4}(3.764 + 2.56)=3.13118$。
      • $T_{8}=\frac{1}{2}T_{4}+\frac{1}{8}[f(\frac{1}{8})+f(\frac{3}{8})+f(\frac{5}{8})+f(\frac{7}{8})]=3.13899$。
      • $T_{16}=\frac{1}{2}T_{8}+\frac{1}{16}[f(\frac{1}{16})+f(\frac{3}{16})+f(\frac{5}{16})+f(\frac{7}{16})+f(\frac{9}{16})+f(\frac{11}{16})+f(\frac{13}{16})+f(\frac{13}{16})+f(\frac{15}{16})]=3.1409$。
   3. 然后计算 Simpson 值：
      • $S_{1}=\frac{4}{3}T_{2}-\frac{1}{3}T_{1}=3.1333$。
      • $S_{2}=\frac{4}{3}T_{4}-\frac{1}{3}T_{2}=3.14157$。
      • $S_{4}=\frac{4}{3}T_{8}-\frac{1}{3}T_{4}=3.14159$。
      • $S_{8}=\frac{4}{3}T_{16}-\frac{1}{3}T_{8}=3.14159$。
   4. 接着计算柯特斯值：
      • $C_{1}=\frac{16}{15}S_{2}-\frac{1}{15}S_{1}=3.14212$。
      • $C_{2}=\frac{16}{15}S_{4}-\frac{1}{15}S_{2}=3.14159$。
      • $C_{4}=\frac{16}{15}S_{8}-\frac{1}{15}S_{4}=3.14159$。
   5. 最后计算龙贝格值：
      • $R_{1}=\frac{64}{63}C_{2}-\frac{1}{63}C_{1}=3.14158$。
      • $R_{2}=\frac{64}{63}C_{4}-\frac{1}{63}C_{2}=3.14159$。
   6. 由于$\vert R_{2}-R_{1}\vert\leq0.00001$，于是有$I=\int_{0}^{1}\frac{4}{1 + x^{2}}dx\approx3.14159$.