数值分析速通 - 非线性问题

插值

插值问题的数学定义: 为区间 上的函数, 为 上 个互不相同的点 (插值结点),

求 满足 , 称为基函数. 不同插值方法的区别在于基函数的选取方式和插值结点的选取方式.

给定基函数和插值结点, 可解线性方程组得到系数

基本多项式插值

很显然, 选取相同的插值结点, 多项式插值的 的符号结果都是相同的, 但不同的算法的数值精度和计算复杂度有差异.

多项式插值

系数矩阵

形式简单, 但是系数矩阵条件数大

Lagrange 插值

构造一组多项式基函数 , 使得 成为对角阵, 便于求解. 条件:

容易得到

满足条件, 可以简单取

Lagrange 插值不用求解 , 但此形式仍然计算复杂度较高.

Newton 插值

希望能够增量计算新的插值节点, 而不改变之前插值结点的系数, 方便计算. 选取基函数

系数矩阵是下三角阵, 可直接回代求解

规定记号

为 阶 Newton 差商, 则回代求解过程可如下表示

差商计算过程

可以滚动数组优化内存

得到系数 后, 的计算可以使用秦九韶算法节约复杂度.

Chebyshev 插值

Motivation

多项式插值误差定理: , 是 上不超过 次的插值多项式, 则

其中

这个形式显然是 Taylor 展开的 Lagrange 余项

Runge 现象, 在区间的两端剧烈震荡

进行高次多项式插值的弊端, 高阶导数 可能巨大. 为了避免区间端点处的震荡, 可以向外拓展插值结点; 也可以通过合理选取插值结点, 尽量减小 项. Chebyshev 多项式给出的插值结点能最小化这一部分的误差.

性质

第一类 阶 Chebyshev 多项式:

Chebyshev 多项式的性质

Chebyshev 多项式的图像

Chebyshev 多项式的零点均匀地分布在圆周上

证明

Chebyshev 多项式是区间上值域最小的首一多项式

说明

反证: 设首一多项式 比 小, 则

是 次多项式且有 个零点, 则恒为零,

在标准区间 上选取 Chebyshev 多项式的根作为插值结点, 误差满足

把标准区间变换到任意区间

误差满足

Hermite 插值

除了插值结点处的函数值, 把一阶导数值等也纳入插值方程. 需要根据选取的方程条件数量确定插值的次数, 防止无解或多解.

Hermite 插值定理：存在唯一的次数至多是 的多项式 满足 个Hermite 插值条件

只有一个插值结点, 条件是 0 至 阶导数值的 Hermite 插值就是 Taylor 展开.

Hermite 插值的 Newton 差商型构造

直接把已知的 次导数值替换掉多出的 次差商(红色部分). 亦可以处理对不同插值节点指定了不同阶数的导数的情况, 见作业题

形式上容易理解

样条插值

高次多项式插值有种种问题, 还是分段用低次多项式近似吧.

节点 上的 次样条满足

1. 在每个子区间 上是 次多项式
2. 在整个区间 上 次连续

零次样条插值即为分段常数函数, 一次样条为分段线性函数, 常用三次样条

也可以用其他方式指定左右边界的二阶导数或一阶导数

数据拟合与最小二乘

数据拟合也是用基函数线性组合, 但不要求精确过每个点, 要求曲线到给定数据点的距离最小

求解最后的矩阵就能得到最小二乘拟合系数. 最后的矩阵可以写作

超定线性方程组最小二乘法

法线方程

最小二乘的几何解释

公式被称作法线方程, 是超定方程 的最小二乘解

对于非线性问题的最小二乘拟合, 需要选取合适的基函数, 还可能需要取对数来线性化.

QR 分解

直接使用法线方程计算最小二乘解数值不稳定. 可利用 QR 分解来求解.

d 的下面部分与 x 无关, 则上面为 0 时模长最小

只需进行完全 QR 分解, 然后求解

数值微分

直接似是而非的去个小量 来近似好了

• 前向差商
• 后向差商
• 中心差商
• 二阶中心差商

用多项式插值的导数近似函数的导数. 两点插值得到的就是前向 / 后向差商, 三点插值得到中心差商

误差分析

通过 Taylor 展开的 Lagrange 余项控制误差的范围. 正确的差商公式都是 Taylor 展开式的变形 (确定插值点, 可以通过 Taylor 展开得到唯一正确的差商公式, 以及余项).

由于数值计算误差的存在, 的选取不是越小越好

Richardson 外推

对任何 的 阶近似 (不仅是数值导数问题)

都能再加一项缩减一半步长

至少是 的 阶近似.

待定系数法

给定插值点, 可以通过 Taylor 展开得到唯一正确的差商公式, 以及余项. 插值点数量已知时, 为了让这个方程有唯一解, Taylor 公式展开的阶数是确定的, 余项的阶数也能确定了. 解线性方程组求出系数后再带回展开式, 可能余项的系数为 0, 这时差商公式会具有更高的阶数.

数值积分

Newton-Cotes 积分

用插值函数的积分来近似原函数的积分, 积分节点等距的插值型数值积分称为 Newton-Cotes 积分. 在区间 上积分, 记 .

数值积分的代数精度, 指可以准确积分的多项式的最高阶数. 给定积分的插值结点, 可以根据插值结点数量确定至少具有的代数精度, 并列线性方程组解出唯一正确的积分系数.

求至少具有 n 数值精度的系数

从插值误差 推导积分误差, 使用积分均值定理, 不变号时存在 中一点

插值误差

一般形式的 Newton-Cotes 积分

为奇数时, Newton-Cotes 具有 阶代数精度. 为偶数时, Newton-Cotes 具有 阶代数精度.

• 梯形法则: 两点一次插值
• Simpson 法则: 三点二次插值
• 中心法则: 使用中点函数值
• 三点开 Newton-Cotes 积分:

复合 Newton-Cotes 积分, 先把 划分为 个等距子区间, 记 , 再在每个子区间上应用 Newton-Cotes 积分, 避免高次插值的 Runge 现象. 对于子区间断点处的函数值, 计算时可以重复利用节约时间. 复合积分的误差, 将原来的 项替换为 项.

• 复合中心法则
• 复合梯形法则
• 复合 Simpson 法则

Romberg 积分

用 Richardson 外推法提高复合梯形法则的精度.

是 的复合梯形法则, 可递推计算, 补充新增的插值点.

实际上是复合 Simpson 法则.

伪代码

Gauss 积分

非均匀地选取插值结点, 使积分值具有尽可能高的数值精度. 可通过正交基构造.

找到 次多项式与 次多项式正交, 用他的根做插值结点就能达到 阶代数精度.

Legendre 多项式是合适的构造.

标准区间上的 Gauss 插值节点

定义映射

把 映射到标准区间