数值计算

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

+++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$ $a_1\neq0$ $m$ $x$ $n$ 位有效数字，则其相对误差限为：
- $\delta\leq\frac{1}{2a_1}\times10^{-(n - 1)}$ 。
$x$ $x$ $n$ 位有效数字。
举例说明：
- $x = 0.00324$ $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 次函数，则二次拉格朗日插值得到的就是 原函数。
  $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 $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}\|$ 。
常见的矩阵范数：
- $\|\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$ .
- $\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)$ $\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 公式的余项

$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}$ 。
三次代数精度 $H(x)$ $\int_{a}^{b}H(x)dx=\frac{b - a}{6}[H(a)+4H(c)+H(b)]$ $S$ 。
$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 公式的余项

$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}$ （此处以整理后的正确公式为准，图片中可能有误）。
- $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}$ 。
$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}$ $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$ 。
$\int_{0}^{4}f(x)dx\approx Af(0)+Bf(1)+Cf(3)$ 。
- $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)$ 。
$\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$ 时：
  - $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 算法

数值计算(下)

未命名