【数值计算】数值逼近



2021年06月05日    Author:Guofei

文章归类: 0x55_数值计算    文章编号: 5501

版权声明:本文作者是郭飞。转载随意,但需要标明原文链接,并通知本人
原文链接:https://www.guofei.site/2021/06/05/numerical_calculation_method.html


1. 多项式插值

多项式插值的理论基础是:n+1个不同的点可以唯一确定一个n次多项式。
此多项式有很多计算方法,基本都是基于待定系数法。典型的为 Lagrange法、Newton 法等。
例如,Newton 法是假设一个多项式 $Q(x)=c_0+c_1(x-x_1)+c_2(x-x_1)(x-x_2)+…+c_n(x-x_1)(x-x_2)…(x-x_n)$ 然后把n+1个点的坐标带入进去解出来。
进而推导出用线性代数、差分等方法,来加快运算。

2. 样条插值

多项式插值其实用途很有限,
例如 $f(x)=\dfrac{1}{1+25x^2}$ 在 $[-1,1]$ 上很光滑,但是在0附近插值效果很好,在1附近出现震动,且随着点个数 n 增加,震荡现象更严重。(Runge现象)

三次样条插值,给定分划 $a = x_1 \lt x_2 \lt … \lt x_{n-1} \lt x_n = b$,要找到分段函数 s(x),满足:

  1. s(x) 在每个 $[x_i,x_{i+1}]$ 上都是三次多项式
  2. s(x) 在 $(a,b)$ 上连续、一阶导数连续、二阶导数连续

如何求出 s(x)?

  1. 根据条件一,共有 n-1 个区间,对应 n-1 个三次多项式,每个多项式有4个待定系数。也就是共 4(n-1) 个待定系数
  2. $s_i$ 的左端点和右端点都给定了,$s_i(x_i)=f(x_i), s_i(x_{i+1}) = f(x_{i+1})$ 每个多项式2个方程。也就是共 2(n-1) 个方程
  3. 一阶导数连续。也就是说,相邻两个多项式的一阶导数相等。从 $x_2$ 到 $x_{n-1}$ 可以列 n-2 个方程
  4. 二阶导数连续。类似的,n-2 个方程

从上面的分析发现,还差2个方程,通常有3种“流派”

  1. 要求给定两端的一阶导数值 $s’(x_1), s’(x_n)$,这种情况称为 D1样条
  2. 要求给定两端的二阶导数值 $s’‘(x_1), s’‘(x_n)$,这种情况称为 D2样条。特别的,如果 $s’‘(x_1) = s’‘(x_n) = 0$, 称为 自然样条
  3. 去掉 $s(x_1)=f(x_1),s(x_n)=f(x_n)$ 中的1个,附加3个条件: $s(x_1) = s(x_n), s’(x_1) = s’(x_n), s’‘(x_1) = s’‘(x_n)$,称为 周期样条

之后的很多工作就是如何更快的解方程了。

3. Bezier 曲线

多项式插值和样条插值的思路是,要求n个点在函数图像上,以此建立方程。

还有另一种思路,不要n个点在函数上,而是这n个点作为“隐变量”,来生成一条曲线。

Bezier 曲线有很多优良的性质,例如

  1. 凸包性:如果n个控制点组成的多边形是凸的,那么 Bezier 曲线在这个凸包内。
  2. 对控制点旋转、平移、伸缩有不变形

4. 最佳逼近

前面都是给定了有限的n个点,让我们找一个对应的函数。现在的问题是,给定一个函数 $f(x)$ 在 $[a,b]$ 上连续,能否找到一个多项式,使得 $\min\limits_{p\in P_n} \max\limits_{x\in [a,b]} \mid f(x) - p(x) \mid$

看上面的描述,就知道接下来要引入泛数了。

4.1 最佳多项式逼近

记$C_{[a,b]}$ 是 $[a,b]$ 上所有连续函数构成的无限维线性空间。

存在性是已经证明的(Weierstrass 第一定理):对任意 $f(x) \in C_{[a,b]},\forall \epsilon>0$,都存在一个多项式 $p(x)$,使得 $\mid\mid f(x) - p(x) \mid\mid_\infty \lt \epsilon$
(其中 $P_n$ 是最多n阶的多项式集合)

然后是多种计算方式

4.2 最佳三角多项式逼近

记$C_{0,2\pi]}$ 是所有 $2\pi$为周期的连续函数构成的无限维线性空间

(Weierstrass 第二定理):对任意 $f(x) \in C_{[a,b]},\forall \epsilon>0$,都存在三角多项式 $T(x)$,使得 $\mid\mid f(x) -T(x) \mid\mid_\infty \lt \epsilon$
其中$T(x)$ 是三角函数的线性组合: \(1,\cos x,\sin x,...,\cos nx,\sin nx\)

4.3 最佳平方逼近

最佳多项式逼近、最佳三角多项式逼近,都是在讨论 $\mid\mid .\mid\mid_{\infty}$,最佳平方逼近讨论的是 $\mid\mid . \mid \mid_2$

  1. 最佳正交逼近可以转化为正交系上的讨论,
  2. 最小二乘法是一个特例

5. 数值积分

计算积分值的时候往往遇到一些困难:

  1. 函数的不定积分无法用简单函数表达出来
  2. 甚至函数本身都没有解析式,而是以表格方式给出一些离散的函数值。

例如:

  1. 土地丈量时遇到的不规则地块,不知道其边缘曲线对应的函数值
  2. $\int_0^1 e^{x^2}dx$ 不存在原函数

5.1 Newton-Cotes公式

问题:需要求出 $\int_a^b f(x) dx$ 的近似解。

思路:

  1. 先求 $f(x)$ 的 Lagrange 插值多项式 $p(x)$
  2. 计算 $\int p(x)$

(得到一个通用公式)

Newton-Cotes 公式:

  1. 附加假设:给定的点是等距的 $x_k=a+\dfrac{b-a}{n} k,k=0,1,…,n$。
  2. 可以把通用公式大大化简,对应的求积公式就是 Newton-Cotes 公式

几个常用的 Newton-Cotes 公式:

  1. n=1 时:$\dfrac{b-a}2[f(a)+f(b)]$ 就是梯形公式
  2. n=2 时:$\dfrac{b-a}6 [f(a)+4f(\dfrac{a+b}2)+f(b)]$ 是抛物线公式或 Simpson 公式
  3. n=4 时:$\dfrac{b-a}{90} [7f(x_0)+32f(x_1)+12f(x_3)+32f(x_4)+7f(x_5)]$ 称为 Cotes 公式

然后是

  1. 误差分析
  2. 稳定性分析

5.2 复化公式

对于n个给定的等距点 $x_k=a+hi, h=\dfrac{b-a}{n}, i=0,1,…,n$

  1. 每个区间 $[x_i, x_{i+1}]$ 上使用梯形公式,然后累加,得到 $\dfrac{h}{2} \sum\limits_{i=0}^{n-1} [f(x_i)+f(x_{x+1})]$
  2. 每个区间 $[x_i, x_{i+1}]$ 上使用 Simpson 公式,然后累加,得到 $\sum\limits_{i=0}^{n-1} \dfrac{h}{6}[f(x_i)+4(x_{i+0.5})+f(x_{x+1})]$

5.3 特殊积分的处理

对于 震荡函数,看能不能转化为三角形式

对于 反常积分,看能不能用换元法、分布积分法,转化为正常积分

5.4 多重积分

多重积分往往复杂很多,但思路是相似的

6. 快速傅立叶变换

7. 方程求根

7.1 二分法

是找连续函数 $f(x)$ 实根的可靠方法。

step1:找到两个值 $a_1, b_1$,使得 $f(a_1)f(b_1) \lt 0$
step2:开始二分法 $x_1 = (a_1+b_1)/2$
step3:按 $f(x_1)$ 的符号,判断 $a_2=x_1$ or $b_2=x1$ or 结束迭代
step4:反复迭代。

7.2 反插值法

(反插值法这个名字来源:推导过程中先求逆函数,然后用插值公式,然后舍弃高阶项。我觉得这个解释不好,下面我用直线的解释)

二分法 中,我们用 $x_1 = (a_1+b_1)/2$ 来寻找下一次迭代的节点。
我们想,用“$a_1,b_1$组成的直线” 对应的零点作为下一次迭代的 $x_1$。

step1:找到两个值 $a_1, b_1$,使得 $f(a_1)f(b_1) \lt 0$
step2:利用直线公式 $x_1 = a_1-\dfrac{b_1-a_1}{f(b_1)-f(a_1)}f(a_1)$
step3:按 $f(x_1)$ 的符号,判断 $a_2=x_1$ or $b_2=x1$ or 结束迭代
step4:反复迭代。

这在很多情况下会更快的逼近真实值。尤其是当 $f(x)$ 是直线时候,一步就能得到结果结束迭代。

7.3 迭代法

我们要解方程 $F(x)=0$

令 $f(x)=x-F(x)$

问题转化为解方程 $x=f(x)$

迭代法求解的过程:$x_{k+1}=f(x_k), k=0,1,2,…$

下面就是解决这两个问题:

  1. 什么条件下,上面的迭代式可以收敛到方程的解
  2. 收敛速度如何?

TH1:
如果同时满足以下条件

  1. $f(x)$在$[a,b]$上连续
  2. $f([a,b])\subset [a,b]$
  3. f(x) 满足 Lipschitz 条件 $\mid f(x) - f(y) \mid \leq L \mid x-y \mid$
  4. $0 \leq L \lt 1$

那么,有结论:

  1. 迭代收敛到方程的解 $x^\star$
  2. $\mid x_k - x^\star \mid \leq \dfrac{L^k}{1-L}\mid x_0-x_1 \mid$

TH2
如果同时满足以下条件

  1. $f(x)$ 在$[a,b]$ 上连续可导,
  2. $f([a,b])\subset [a,b]$
  3. $\mid f’(x) \mid \leq L \lt 1$

那么结论也成立

7.4 Newton 法

要解方程 $F(x)=0$,

使用迭代 $x_{k+1}=x_k-\dfrac{F(x_k)}{F’(x_k)}$

可以用 1 阶 Taylor 级数导出。

直观理解,就是在 $x_i$ 找一个切线,根据切线和x轴的交点得到 $x_{x+1}$

从 Newton 法出发,同样有一些推广

  1. 什么条件下,上面的迭代式可以收敛到方程的解
  2. 收敛速度如何?
  3. 求导数的过程复杂度较高,如何优化

参考文献

蒋尔雄《数值逼近》,复旦大学出版社


您的支持将鼓励我继续创作!