数值计算(上)

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

+++info 课程章节

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

误差

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

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

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

绝对误差

近似值：$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 有三位有效数字。

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

设近似值 $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$ 位有效数字。
举例说明：
- 若近似值 $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$ 发生很大的变化，那么这个线性方程组就是病态的。

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

二、条件数

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

对于++线性方程组++$Ax = b$，矩阵 $A$ 的条件数定义为 $\|A\|\|A^{-1}\|$，其中 $\|\cdot\|$ 表示矩阵的某种范数。
- 条件数越大，说明问题越病态，解对数据的微小变化就越敏感。
- 条件数越小，问题的病态程度就越低，解相对比较稳定。
例如，当条件数非常大时，即使右端项 $b$ 只有很小的误差，解 $x$ 可能会产生很大的误差。而当条件数较小时，数据的微小误差对解的影响相对较小。

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

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

++计算函数值问题的条件数++定义为：相对误差比值 $\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}$。
如果条件数 $C_{p}$ 很大，即使自变量相对误差一般不大，也会引起函数值相对误差很大。出现这种情况的问题被称为病态问题。
一般情况下，当条件数 $C_{p}\geq10$ 时，就认为是病态问题，并且条件数越大，病态越严重。

+++info 病态问题

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

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}

::: info

定义 1：若 $n$ 次多项式 $l_j(x)(j = 0,1,\cdots,n)$ 在 $n + 1$ 个节点 $x_0\lt x_1\lt\cdots\lt x_n$ 上满足条件：

l_{j}\left(x_{k}\right)=\begin{cases}1, & k = j; \\ 0, & k\neq j.\end{cases}\ (j, k = 0,1,\cdots, n)\ (2.7)

就称这 $n + 1$ 个 $n$ 次多项式 $l_0(x),l_1(x),\cdots,l_n(x)$ 为节点 $x_0,x_1,\cdots,x_n$ 上的 $n$ 次插值基函数。

:::

三、计算步骤

确定插值节点：给定一组互异的节点 $(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)$。
计算拉格朗日基函数：对于每个 $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)}$。
计算插值多项式：将节点的函数值 $y_i$ 和对应的基函数 $L_i(x)$ 代入插值多项式公式，得到 $L_n(x)=\sum_{i = 0}^{n}y_il_i(x)$。

四、特点和应用

特点：
- 拉格朗日插值多项式在节点处与给定的函数值完全相等，具有较高的精度。
- ++当节点增加时，需要重新计算整个插值多项式，计算量较大++。
- 对于高次插值，可能会出现龙格现象，即在插值区间的两端，插值多项式的波动较大，与原函数的差异较大。
应用：
- 函数逼近：可以用拉格朗日插值多项式来逼近一个未知的函数。
- 数据拟合：当只有离散的数据点时，可以通过拉格朗日插值得到一个连续的函数表达式。
- 数值积分和数值微分：可以利用插值多项式进行数值积分和数值微分的计算。

+++primary 例题

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

首先确定插值基函数：
- 对于三个节点，$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}$。
然后构造插值多项式：
- 插值多项式为
$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}：设 $f^{(n)}(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)$.

这个公式可以用来估计插值的误差。当 $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.$
从误差估计可以看出以下几点：
- 插值多项式的次数 $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}

二、性质

对称性：差商的值与节点的顺序无关。即对于任意的置换 $\sigma$，有 $f[x_{\sigma(0)},x_{\sigma(1)},\cdots,x_{\sigma(n)}]=f[x_0,x_1,\cdots,x_n]$。
可通过 差商表 计算：可以通过构造差商表来方便地计算高阶差商。差商表是一个二维表格，其中第一列是节点，其余列是对应节点的差商。从低阶到高阶逐步计算差商，可以提高计算效率。
若 $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!}$。

三、应用

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

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})

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

数值微分：可以利用差商来近似计算函数的导数。例如，一阶导数可以近似为一阶差商，即 $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}$。

牛顿插值

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

牛顿插值多项式的形式
- 设给定 $n + 1$ 个互异的节点 $(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)$，牛顿插值多项式 为：
$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})$
牛顿插值法的步骤
- 首先计算差商表：从一阶差商开始，逐步计算高阶差商，形成一个差商表。
- 然后根据差商表中的数据构建牛顿插值多项式：从最低阶的项开始，依次加入高阶差商项，直到得到所需的插值多项式。

[以下是通过差商表达式迭代推出牛顿插值公式的过程]{.red}：

首先从一阶差商开始：

已知 $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)$。

接着引入二阶差商：
- $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)$。
然后引入三阶差商：
- $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)$。
以此类推：
- 最终可以得到牛顿插值公式
  $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)$，求牛顿插值多项式。

计算差商表：
- 首先列出数据点：
  $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$。
- 计算二阶差商：

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

$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$

构建牛顿插值多项式：
- 根据差商表，牛顿插值多项式为：
$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!}$ 为二项式展开系数。
另{.red}
$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}$

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

一般地有
$f [x_k,\cdots, x_{k + m}] =\frac{1}{m!}\frac{1}{h^{m}}\Delta^{m}f_{k}$
由上述关系和前面的公式又可得到差分与导数的关系：
$\Delta^{n}f_{k}= h^{n}f^{(n)}(\xi)$
其中 $\xi\in(x_k,x_{k + n})$。

::: primary

牛顿前插公式可以简单的理解为将 等距均差/差商 替换为 前向差分

:::

分段插值

函数逼近

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

内积空间

一、定义

设 $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]$ 构成一个内积空间。

二、性质

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

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

范数

一、定义

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

$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}$。
无穷范数：
- $f(x)$ 的无穷范数定义为 $\|f\|_{\infty}=\max_{a\leq x\leq b}|f(x)|$。

二、性质

正定性：对于任意函数 $f(x)$，$\|f\|\geq0$，且 $\|f\|=0$ 当且仅当 $f(x)=0$。
齐次性：对于任意实数 $\alpha$ 和函数 $f(x)$，$\|\alpha f\|=|\alpha|\|f\|$。
三角不等式：对于任意函数 $f(x)$ 和 $g(x)$，$\|f + g\|\leq\|f\|+\|g\|$。
平行四边形定理：$\|f + g\|_2^{2}+\|f - g\|_2^{2}=2(\|f\|_2^{2}+\|g\|_2^{2})$。
+++primary 证明如下：
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}$$
接着计算 $\|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}$
最后计算 $\|f + g\|_2^{2}+\|f - g\|_2^{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})$

向量矩阵

一、向量范数

定义：
- 对于一个 $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}\|$。
常见的向量范数：
- $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|$。
应用：
- 用于衡量向量的大小和长度，在数值分析、优化问题、机器学习等领域有广泛应用。例如，在优化算法中，向量范数可以用来衡量迭代过程中解的变化程度。

二、矩阵范数

定义：
- 对于一个 $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}\|$。
常见的矩阵范数：
- 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)$ 正交。

三、性质

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

最佳一致逼近

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

一、基本概念

设 $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)$ 偏差最小的那个值。

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

最佳平方逼近

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

一、基本概念

对于函数 $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]$ 上的 平方误差积分 最小。
若 $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)$，可以根据不同的需求对不同点的误差进行加权。

二、求解方法

问题归结为 求系数 $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}$
由此得到法方程：

\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$。

三、性质与意义

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

\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)$。

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

数值积分

+++info imphasis

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

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

自适应求积的基本思想

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

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

插值求积与代数精度

一、插值求积

基本概念
- 插值求积是基于插值多项式来近似计算定积分的方法。其核心思想是先利用已知节点上的函数值构造一个插值多项式，然后对这个插值多项式进行积分来近似原函数的定积分。
具体方法
- 设给定区间$[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$的近似值。

二、代数精度

定义
- 若一个数值求积公式对于所有次数不超过$m$的多项式都能准确成立，而对于某个$m+1$次多项式不成立，则称该求积公式具有$m$次代数精度。
意义
- 代数精度是衡量数值求积公式准确性的一个重要指标。代数精度越高，说明该求积公式在对多项式函数进行积分时的准确性越高。
- 通过确定求积公式的代数精度，可以评估不同求积公式的优劣，为选择合适的求积方法提供依据。
与插值求积的关系
- 对于插值求积法，其代数精度与所使用的插值多项式的次数有关。一般来说，插值多项式的次数越高，插值求积公式的代数精度也越高。
- 例如，梯形公式是基于一次插值多项式的求积公式，其代数精度为 1；辛普森公式是基于二次插值多项式的求积公式，其代数精度为 3。

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

插值基函数：

$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$时，则称求积公式为插值求积公式。

求积公式推导：
- 对于积分$\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$，此时求积公式为插值型求积公式。

插值求积公式的余项

余项表达式：
- 设插值求积公式的余项为$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]$。
当$f(x)$是次数不高于$n$的多项式时，$f^{(n + 1)}(x)=0$，$R(f)=0$，求积公式能成为准确的等式。

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

定理：

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

证明：
- 必要性：若求积公式为插值型求积公式，求积系数为$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{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$，此时求积公式为插值型求积公式。

代数精度：若求积公式至少具有$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次代数精度

一、牛顿-柯特斯公式

梯形公式：
- 对于区间 $[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)]$
中矩形公式：
$\int_{a}^{b}f(x)dx\approx(b-a)f(\frac{a+b}{2})$
辛普森公式：
- 将区间 $[a,b]$ 分为三部分，用二次抛物线来近似代替曲线 $f(x)$。辛普森公式为：
  $\int_{a}^{b}f(x)dx\approx\frac{b - a}{6}[f(a)+4f(\frac{a + b}{2})+f(b)]$
牛顿-柯特斯公式一般形式：
- 对于 $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}$。

二、高斯型求积公式

基本思想：

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

公式形式：
$\int_{a}^{b}f(x)dx\approx\sum_{k = 1}^{n}A_{k}f(x_{k})$
其中 $x_{k}$ 是求积节点，$A_{k}$ 是求积系数。

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

复化求积公式

复化梯形公式：

将区间 $[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$。

复化辛普森公式：
- 类似地，将区间分成 $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

梯形公式的余项

梯形公式（4.1.1）的余项为
$R_{T}=I - T=\int_{a}^{b}\frac{f''(\xi)}{2}(x - a)(x - b)dx$
取的左右端点，做的一阶插值
由于积分的核函数$(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 公式的余项

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

积分核$(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}

自适应求积

一、基本思想

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

二、变步长梯形公式

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

对于区间$[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$。

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

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

计算两次近似值的差异：
- 可以得到
$T_{2n}=\frac{1}{2}T_n+\frac{h}{2}\sum_{i = 1}^{n}f(x_{i+\frac{1}{2}})$

三、变步长辛普森公式

类似地，可以从辛普森公式出发，逐步减小步长进行计算。
辛普森公式为
$S(h)=\frac{h}{6}[f(a)+f(b)+4\sum_{i = 1}^{n - 1}f(x_{2i - 1})+2\sum_{i = 1}^{n - 1}f(x_{2i})]$
递推公式为
$S_{2n}=\frac{S_n}{2}+\frac{h}{4}\sum_{i=0}^{n-1}\left[f(x_{2i+\frac{1}{2}})+f(x_{2i+\frac{3}{2}})\right]$

Romberg 算法

龙贝格

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

一、龙贝格算法计算步骤

按变步长梯形公式计算积分近似值：
- 对于区间$[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$。
按加速公式求加速值：
- 梯形公式加速：$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}$。

二、公式推导过程

从柯特斯公式的误差公式进一步导出龙贝格公式：$R_{n}=\frac{64}{63}C_{2n}-\frac{1}{63}C_{n}$。
考察 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}$。
用梯形法二分前后两个积分值$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 值、柯特斯值和龙贝格值，将收敛缓慢的梯形值序列加工成收敛迅速的龙贝格值序列。

例题

计算向量 $x=(1, -2, 3)^T $ 的各种范数 []{.gap}{.quiz .fill}
$\parallel x \parallel_1 = 6$, $\parallel x \parallel_\infin = 3$, $\parallel x \parallel_2 = \sqrt{14}$
题目：设 $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$。
试确定一个至少具有 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)$。
试确定求积系数 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 次代数精度。
考察求积公式$\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 次代数精度，因为不是插值型的。
给定求积式$\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}$。
- 由插值型求积公式的定义知，所给的求积公式是插值型求积公式。
题目：计算定积分$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 公式却有六位有效数字。
题目：用变步长梯形求积公式计算定积分$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 次可得此结果。
题目：用龙贝格算法计算定积分$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$。

误差

绝对误差

相对误差

有效数字

病态问题和条件数

插值

拉格朗日插值

差商

牛顿插值

差分

分段插值

函数逼近

内积空间

范数

向量矩阵

正交

最佳一致逼近

最佳平方逼近

曲线拟合

最小二乘法

数值积分

插值求积与代数精度

求积公式

复化求积公式

低阶求积公式余项

梯形公式的余项

Simpson 公式的余项

Cotes 公式的余项

复化梯形余项

复化辛普森余项

自适应求积

Romberg 算法

例题

未命名

未命名