数值分析知识与思想梳理

何谓数值分析？

众所周知现实生活中科学技术上面的问题大多数都能够通过建立对应的数学模型把实际问题转化成一个数学问题，但是往往很多的实际问题即便建立了相对应的数学模型仍然无法有效的通过常规手法求得其解，或者求解的方法十分的复杂，为了简化计算有效的求其解或者是近似解从而解决实际问题从而催生出了数值分析这一门课程。数值分析按我自己的理解就是通过有效的科学的手段简便的求解数学模型的方式方法。因此数值分析也叫科学计算。同时随着计算机的发展解放了人类的劳动力把许多数学工作者从繁复的计算中解脱了出来，计算机本来一开始就是为数学而生的，我们人类不是万能的有其固有的局限性，随着人类社会科学技术的发展越来越多的科学技术问题仅仅靠人力来计算无疑是痴人说梦异想天开的，有了计算机我们期待能够把许多的数学模型都设置成一套算法放在计算机上面跑，把复杂的机械化的事情都交给计算机去做，而数值分析恰恰就是面向计算机的一门实用性很强的一门学科。用计算机求解科学技术问题通常经历以下步骤：

根据实际问题建立数学模型
由数学模型给出数值计算方法
根据计算方法编制算法程序在计算机上得出结果
第一步建立数学模型通常是应用数学的范畴，第二三步就是数值分析与科学计算的范畴

数值分析与科学计算树.png

数值分析思维导图如下

由于人类的局限性与抽象模型与现实世界的差异所造成的误差

误差的分类：

模型误差：要建立数学模型就需要对现实世界进行抽象，既然是
抽象那么误差就会必然的产生误差
观测误差：所谓观测误差顾名思义就是观测不准造成的误差，这主要是由于人类生理上的局限性造成的
阶段误差或者方法误差：这主要是人类智力上局限性造成的误差，在解决数学问题的过程中大多数我们不能够通过已有的方法得到精确解只能得到近似解，比如可微函数用泰勒多项式展开就必然会有余项即截断误差
舍入误差：这是由于计算机的字长有限把一个超过字长的数输入计算机就会溢出从而得到不精确的数值。
既然由于各种各样的局限性造成的误差的是不可避免的，我们要想克服我们人类自身的局限性就必须学会如何去控制误差，如果把误差控制合理的范围内，使得其对实际问题的影响微乎其微，得到一个与精确解近似的近似解，这又何尝不是身为万物之灵的人类征服自然超越自我的一种体现

误差的基本概念

绝对误差：
$x^*为x的一个近似值那么称e^*=x^*-x为近似值的绝对误差$
相对误差：
相对性是自然界中普遍存在的真理，任何事情都是相对的，误差也不例外，误差的大小需要参考真实值的大小，因此 $\frac {x^*-x}{x}$ 就称为相对误差，但是在实际问题中真实值 $x$ 的大小我们通常是不知道的因此就用 $\frac{x^*-x}{x^*}$ 来代替相对误差。
相对误差限：
相对误差绝对值的上界就叫做相对误差限。
数值运算的误差估计：
$当f为多元函数时例如计算A=f(x_1,x_2,\cdots,x_n),如果x_1,x_2,\cdots,x_n的近似值为x_1^*,x_2^*,\cdots,x_n^*时候，A的近似值为A^*=f(x_1^*,x_2^*,\cdots,x_n^*)$ 于是由泰勒展开得到 $e(A^*)=A^*-A=f(x_1^*,x_2^*,\cdots,x_n^*)-f(x_1,x_2,\cdots,x_n) \approx \sum\limits^n_{k=1}(\dfrac {\partial f(x_1^*,x_2^*,\cdots,x_n^*)}{\partial x_k})(x^*_k-x_k)=\sum\limits^n_{k=1}(\dfrac {\partial f}{\partial x_k})^*e^*_k$ $于是误差限\varepsilon(A^*)\approx\sum\limits^n_{k=1}|(\dfrac {\partial f}{\partial x_k}^*)|\varepsilon (x^*_k),相对误差限为\varepsilon^*_r=\dfrac {\varepsilon(A^*)}{|A|^*}\approx\sum\limits^n_{k=1}|(\dfrac{\partial f}{\partial x_k})^*|\dfrac {\varepsilon(x^*_k)}{|A^*|}$

如何尽量减少误差：

尽量减少运算次数
设计算法尽量保证误差不在计算过程中增长太快以及要避免出现病态问题
要尽量使得计算公式避免或者减少有效数字的损失

迭代法与开方求值

迭代法是按照同一公式重复计算逐次逼近真实值的算法，是数值计算中普遍使用的方法，比如说开方运算，他不是四则运算，计算机只能处理四则运算因此在计算机上面要想开方就得将开方运算化解为四则运算，这就是迭代法

设使 $a\gt0,求\sqrt a等价与解方程组x^2-a=0现在用简单的方法构造一个迭代公式$

$先取一个x_0\gt0为x真值的一个近似，另x=x_0+\varDelta x,\varDelta x是一个较正量，称为增量于是(x_0+\varDelta x)^2=a$

即得 $x^2_0+2x_0\varDelta x+(\varDelta x)^2=a由于\Delta x是无穷小量，省略高阶无穷小(\Delta x)^2则得：$

$x_0^2+2x_0\Delta x\approx a,即\Delta x\approx\dfrac{1}{2}(\dfrac {a}{x_0}-x_0)$

于是： $x=x_0+\Delta x\approx\dfrac{1}{2}(x_0+\dfrac{a}{x_0})=x_1$

$这里的x_1还不是真值，只是 x_0的进一步近似因此我们把x_1在做进一步的近似重复以上过程就可以得到迭代公式x_{k+1}=\dfrac 12(x_k+\dfrac{a}{x_k})$

将迭代公式两别取极限可得 $\lim\limits_{k\rightarrow \infty} x_k=x^*,x^*=\sqrt a,显然序列{x_k}对任何x_0>0均收敛，且收敛很快$

由上式迭代公式的推导可知道，要想构造迭代公式需要满足迭代公式收敛而且收敛与真值,显然迭代公式是十分适合计算机进行运算的重复的事情机械化的事情是计算机最擅长做的事情，我们把迭代公式输入计算机，就相当于给了计算机一个运算规则，计算机根据这个规则就懂得如何求值

以直代曲的牛顿迭代法

牛顿迭代法是由求根公式构造出来的,现有一个函数 $y=f(x)我们要求其根x^*，那么现在x^* 附近取一个点(x_k,f(x_k))$

$过这一点做f(x)的切线求得切线与x轴的交点x_{k+1}，显然x_{k+1}是x_k相对于x^*的一个近似,重复做切线与x轴的交点极限值就是x^*$

$f(x)在(x_k,f(x_k))点的切线方程为y=f(x_k)+f^\prime(x_k)(x-x_k),令y=0 得到的根x_{k+1}就是x_k的进一步近似$

$x_{k+1}=x_k-\dfrac{f(x_k)}{f^\prime(x_k)} 即为著名的牛顿迭代公式$

求重根的Newton迭代法

$当x^*为f(x)=0的m重根的时候，Newton迭代格式仅是线性收敛的，收敛的比较慢，这时候可以将迭代格式修正为：$

$x_{k+1}=x_k-m\dfrac{f(x_k)}{f^\prime(x_k)}能够证明此迭代格式至少是2阶收敛的$

事实上若 $x^*是f(x)的m重根则x^*是方程的u(x)=\dfrac{f(x)}{f^\prime(x)}的单根还可对u(x)=0应用Newton迭代公式具有2阶收敛性$

线性代数方程组的数值解法

在高等代数中我们学过界限行方程组如果其系数行列式不为零那么方程组有唯一解，则可以用Cramer法则求出唯一解但是Cramer法则计算量太大因此以现有的计算机的运算速度是吃不消的，因此必须研究其它数值解法。

Gauss消去法解线性方程组：

高等代数中学过如果一个矩阵非奇异，则其上三角举证有唯一解如果把一个线性方程组的系数矩阵用Gauss消元法化成一个上三角举证无疑会减少大量的计算量使得计算机的负荷没那么大，(注意：高斯消去法的前提条件是消去法所形成的主元素均不为零，当n阶矩阵的所有顺序主子式都不为零时候条件满足)

追赶法：

主要运用在三对角矩阵中运用Gauss消去法将对角线元素下的元素小消去

列主元Gauss消去法：

主要是为了防止舍入误差给值带来的负面影响，当Gauss消元进行到第K步的时候如果第K行的元素相对于其他行元素来说过于小的化当第K行乘上一个数加到其他行消元的时候会放大误差，因此在消元的时候往往通过调换主元来控制误差

矩阵的直接分解法：

Gauss消去法的过程实际上是对方程组的增广矩阵实行行变换也就是左乘以n-1个矩阵(如果是n阶矩阵的话)，左乘的n-1个矩阵的乘积是一个下三角矩阵，因此矩阵A如果可以运用Gauss消元法的话就可以把A化为一个上三角矩阵以及一个下三角矩阵的乘积形式即 $A=LU,L为一个下三角矩阵，U为一个上三角矩阵(如果矩阵A的各阶顺序主子式均不为零则对A可做唯一的LU分解)$

一个线性方程组的增广矩阵 $A做LU分解如下：$

$A=\begin{pmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}&{a_{1,n+1}}\\{a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}&{a_{2,n+1}}\\{\vdots}&{\vdots}&{}&{\vdots}&{\vdots}\\{a_{n1}}&{a_{n2}}&{\cdots}&{a_{nn}}&{a_{n,n+1}}\end{pmatrix}=\begin{pmatrix}{1}&&&&&\\{l_{21}}&{1}\\{l_{31}}&{l_{32}}&{1}\\{\vdots}&{\vdots}&{\vdots}&{1}\\{l_{n-1,1}}&{l_{n-1,2}}&{l_{n-1,3}}&{\cdots}&{1}\\{l_{n,1}}&{l_{n,2}}&{l_{n,3}}&{\cdots}&{l_{n,n-1}}&{1}\end{pmatrix}$ $\times\begin{pmatrix}{u_{11}}&u_{12}&u_{13}&{\cdots}&u_{1n}&u_{1,n+1}\\&u_{22}&u_{23}&{\cdots}&u_{2n}&u_{2,n+1}\\&&u_{33}&{\cdots}&u_{3n}&u_{3,n+1}\\&&&{\ddots}&{\vdots}&{\vdots}\\&&&&u_{nn}&u_{n,n+1}\end{pmatrix}$

根据矩阵的乘法法则比较两边第一行和第一列的元素有

$a_{1j}=u_{1j}$ $(j=1,2,\cdots,n+1)$

$a_{i1}=l_{i1}u_{11}$ $(i=2,3,\cdots,n)$

即得： $l_{i1}=\dfrac{a_{i1}}{a_{11}}$ $(i=2,3,\cdots,n)$

由已给出的 $L的前k-1列与U的前k-1行来确定L的第K列和U的第K行其公式如下：$

$a_{kj}=\sum\limits^n_{q=1}l_{kq}u_{qj}=\sum\limits^{k-1}_{q=1}l_{kq}u_{qj}+u_{kj}$ $(j=k,k+1,\cdots,n+1)$

$a_{ik}=\sum\limits^{n}_{q=1}l_{iq}u_{qk}=\sum\limits^{k-1}_{q=1}l_{iq}u_{qk}+l_{ik}u_{kk}$ $(i=k,k+1,\cdots,n+1)$

对称矩阵的直接分解法：

对于对称矩阵而言由上面的计算公式可以推的 $l_{ik}=\dfrac{u_{ki}}{u_{kk}}因此公式计算更为简单$

迭代法：

$对于线性方程组Ax=b,其中A非奇异,b\neq 0,因吃他有唯一解x^*构造与线性方程组同解的线性方程组$

$x=Bx+f,任取一跟个向量x^{(0)}作为线性方程组的近视解，用迭代公式$

$x^{(k+1)}=Bx^{(k)}+f若\lim\limits_{k\rightarrow \infty}x^{(k)}=x^*则等式两边取极限可得x^*=Bx^*+f于是x^*也是Ax=b的解$

几个常用的迭代格式：

$Jacobi迭代格式$

由线性方程组 $\begin{cases}a_{11}x_1+a_{12}x_2+{\cdots}+a_{1n}x_n=b_1\\a_{21}x_1+a_{22}x_2+{\cdots}+a_{2n}x_n=b_2\\{\vdots}\\a_{n1}x_1+a_{n2}x_2+{\cdots}+a_{nn}x_n=b_n\end{cases}$

$\begin{cases}x_1=[b_1-(a_{12}x_2+{\cdots}+a_{1n}x_n)]/a_{11}\\x_2=[b_2-(a_{21}x_1+{\cdots}+a_{2n}x_n)]/a_{22}\\{\vdots}\\x_n=[b_n-(a_{n1}x_1+a_{n2}x_2+{\cdots}+a_{n,n-1}x_{n-1})]/a_{nn}\end{cases}$

建立迭代格式

$\begin{cases}x_1^{(k+1)}=[b_1-(a_{12}x_2^{(k)}+{\cdots}+a_{1n}x_n^{(k)})]/a_{11}\\x_2^{(k+1)}=[b_2-(a_{21}x_1^{(k)}+{\cdots}+a_{2n}x_n^{(k)})]/a_{22}\\{\vdots}\\x_n^{(k+1)}=[b_n-(a_{n1}x_1^{(k)}+a_{n2}x_2^{(k)}+{\cdots}+a_{n,n-1}x_{n-1}^{(k)})]/a_{nn}\end{cases}$

Guss-Seidel迭代格式
仔细观察就能够发现 $Jacobi$ 迭代公式当计算出了 $x_i^{(k+1)}后在计算x_{i+1}^{(k+1)}的时候没有用到已经计算出来的x_i^{(k+1)}依旧在用x_i^{(k)}$ 因此我们可以对 $Jacobi$ 做适当的改进利用已经计算出的值来计算下一个的值因为理论上来讲已经经过计算了的值更加的精确
$\begin{cases}x_1^{(k+1)}=[b_1-(a_{12}x_2^{(k)}+{\cdots}+a_{1n}x_n^{(k)})]/a_{11}\\x_2^{(k+1)}=[b_2-(a_{21}x_1^{(k+1)}+{\cdots}+a_{2n}x_n^{(k)})]/a_{22}\\{\vdots}\\x_n^{(k+1)}=[b_n-(a_{n1}x_1^{(k+1)}+a_{n2}x_2^{(k+1)}+{\cdots}+a_{n,n-1}x_{n-1}^{(k+1)})]/a_{nn}\end{cases}$
这就是Guss-Seidel迭代格式
前面已经说过要想知道构造的迭代公式使用与否，要看迭代公式是否收敛,那么如何判断迭代公式是否收敛嘞？
我们可以把 $Ax=b$ 中的系数矩阵A拆分为一个对角元素为零的下三角矩阵 $L$ ,一个对角元素为零的上三角矩阵 $U$ ,以及一个除对角元素部位零外其余元素都为零的矩阵 $D$ 的和即 $A=L+U+D,(L+U+D)x=b$
由此可以推得迭代格式 $x^{k+1}=Jx^{k}+f$ 其中 $J=-D^{-1}(L+U),f=D^{-1}b$
同理可以推得Guss-Seidel的迭代格式为
$x^{(k+1)}=Gx^{(k)}+F$
$G=-(D+L)^{-1}U,F=(D+L)^{-1}b$
迭代格式的收敛性：
$Jacobi$ 迭代格式收敛的充分必要条件是 $\rho(J)<1$ (即 $J$ 的特征根的最大值小于1)由 $J=-D^{-1}(L+U),f=D^{-1}b$ 可以推得矩阵 $J$ 的特征方程为A的主对角元素乘上一个 $\lambda$ 后行列式等于零的解
同理 $Gauss-Seidel$ 迭代格式收敛的充分必要条件是 $\rho(G)<1$ $G=-(D+L)^{-1}U,F=(D+L)^{-1}b$ 可以推得G的特征方程为A的主对角线上以及以下的元素乘上 $\lambda$ 后行列式等于零的解。

插值与逼近

在许多的科学问题中，经常要研究变量与函数之间的关系 $y=f(x)$ ,如果 $f(x)$ 的函数表达式很复杂或者 $f(x)$ 只能够得到有效的几个点 $(x_1,f(x_1)),(x_2,f(x_2)),\cdots,(x_n,f(x_n))$ 这都给研究问题带来困难，因此我们希望用一个简单的函数 $p(x)$ 去近似的代替 $f(x)$ 用以满足实际问题的需要。但是由于近似度量标准的不同也就构成了插值与逼近。插值主要是用几个已知条件去构造一个较为简单的多项式函数来代替已知函数，而逼近是用一个函数去逼近已知的函数。

Lagrange插值函数

设函数 $f(x)$ 在区间 $[a,b]$ 上由 $n+1$ 个互异的节点 $x_0,x_1,x_2,x_3,\cdots,x_n$ 如果存在一个不超过 $n$ 次的多项式 $p(x)使得p(x_i)=f(x_i)$ , $(i=0,1,2,\cdots,n)$ 则 $p(x)为f(x)的n次插值多项式$ ：

一般而言我们通过 $n+1$ 个条件各已通过解线性方程组来确定 $n$ 次多项式的系数从而确定多项式但是通过线性方程组解方程求系数过于麻烦因此我们希望有通过插值节点来构造插值多项式的公式

插值多项式有如下形式

$p_n(x)=\sum\limits_{k=0}^{n}l(x)f(x_k)$

$l(x)=\begin{cases}1\quad\quad x=x_k\\0\quad\quad x\neq x_k\end{cases}$

很自然的 $l(x)$ 有形式 $\dfrac{(x-x_0)(x-x_1)\cdots(x-x_{k-1})(x-x_{k+1})\cdots(x-x_n)}{(x_k-x_0)(x_k-x_1)\cdots(x_k-x_{k-1})(x_k-x_{k+1})\cdots(x_k-x_n)}$

显然这样的形式满足上面的条件，因此 $p_n(x)$ 就是 $f(x)$ 的n阶插值多项式而且插值多项式式唯一的

Newton插值多项式与差分，差商

牛顿插值多项式的提出是在拉格朗日多项式的基础上的，上面提到的拉格朗日插值多项式由于在构造插值多项式的时候插值节点式确定的，因此如果我们希望在多加几个插值节点构造更高次的插值多项式那么我们就需要把拉格朗日的插值系数推倒从来很不灵活没有插值公式的重用性，众所周知我们在计算几种输入代码的时候我们也希望提高代码的重用性用以减轻编程人员的负担，而牛顿插值多项式的提出恰好弥补了拉格朗日插值多项式的不足，使得插值公式更加的灵活，在之前节点数插值公式的基础上可以只要经过适当的修正就可以得到新的插值多项式。

Newton插值多项式的思想

假设有已经构造出的 $k$ 个节点的 $k-1$ 次的插值多项式 $L_{k-1}$ 我们希望通过 $L_{k-1}$ 推导出增加了一个节点的插值多项式 $L_{k}$ 设 $g(x)=L_{k}-L_{k-1}$ 显然根据插值多项式的定义 $g(x)$ 有 $k$ 个零点，因此 $g(x)$ 有形式

$g(x)=a_k(x-x_0)(x-x_1)(x-x_2)\cdots(x-x_{k-1})$

因此 $L_k(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots+a_k(x-x_0)\cdots(x-x_{k-1})$

$L_n(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots+a_n(x-x_0)\cdots(x-x_{n-1})$

如果常数可以确定出来那么我们就可以通过 $L_{k-1}$ 来构造推导 $L_k$

事实上我们通过推导得到的 $a_k=\sum\limits_{m=0}^{k}\dfrac{f(x_m)}{\prod\limits_{i=0,i\neq m}^k(x_m-x_i)}$

然而直接通过公式来推导 $a_k$ 的值式困难的，但是数学家们通过从最简单的推导开始

差分的导出
对于一个插值节点的插值多项式 $L_0(x)=f(x)=a_0=f(x_0)$
对于两个插值节点的插值多项式为线性插值
$L_1(x)=f(x)=f(x_0)+\dfrac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0)=a_0+a_1(x-x_0)$ 即 $a_1=\dfrac{f(x_1)-f(x_0)}{x_1-x_0}$ 称之为一阶差商形式
同样的 $L_2(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)$ , $L_2(x_2)=f(x_2)$ 可以推得 $a_2=\dfrac{\dfrac{f(x_2)-f(x_1)}{x_2-x_1}-\dfrac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_0}$
定义为二阶差商形式
数学家只通过推到了一阶差商和二阶差商，更高阶的推到出来不现实，因此数学家们把 $a_1和a_2$ 所具有的形式称之为差商并且定义出来差商的形式，而且通过数学归纳法的验证 $k$ 阶差商就是 $a_k$ 。
定义 $k$ 阶差商为 $f[x_0,x_1,\cdots,x_{k-1},x_{k}]$ $=$ $\dfrac{f[x_0,x_1,\cdots,x_{k-1}]-[x_1,\cdots,x_{k-1},x_k]}{x_0-x_k}$ $=$ $a_k=\sum\limits_{m=0}^{k}\dfrac{f(x_m)}{\prod\limits_{i=0,i\neq m}^k(x_m-x_i)}$
这就是差商的由来，数学家们先发现从简单的 $a_1，a_2$ 开始然后猜想出 $a_k$ 可能具有哪些形式然后把这种形式称作差商，然后用数学归纳法证明差商就是推到差值公式的系数，这就是差商产生的整个过程，大家不要小看这个过程，很多的数学公式的由来都是与差商推到相类似的思维方式。还有所谓的数学归纳法其实有点类似于大家都知道的多米诺骨牌效应只要证明第一个成立，并且只要前面的满足导致后面的满足，这个就是成立的。就像多米洛骨牌只要推到第一个其他的也会跟着倒下去，老实说笔者刚看书的时候也对这个差商是怎么来的百思不得其解，知道我多找了几本书参考了之后才搞明白这个差商是怎么来的，差商的推到思维过程真的是很有意思嘞。
差商可以通过构造差商表来进行计算是分的方便，放到计算机中只要输入算法，构造插值多项式是一件极其简单的事情

差分及其等距节点的Newton插值多项式：

对于等距节点而言我们可以极大的减少计算差商的计算量，可以将差商形式化解为差分的形式。
等距节点其节点为 $x_i=a+ih$ $(i=0,1,2,\cdots,n)$
因为 $x_i-x_{i-1}$ 的值是固定不变的因此我们可以定义设法化解差商
定义 $\Delta f_i=\Delta f_{i+1}-f_{i}$
类似地，称 $\Delta^kf_i=\Delta^{k-1}f_{i+1}-\Delta^{k-1}f_i$ 称之为 $f(x)$ 在 $x_i$ 处以 $h$ 为步长的 $k$ 阶向前差分，简称 $k阶差分$
然后我们应用数学归纳法可以证明差分与差商的关系如下：
$f[x_i,x_{i+1},\cdots,x_{i+k}]=$ $\dfrac{\Delta^kf_i}{k!h^k}$
因此将差分与 $x=x_0+ht$ 带入 $Newton$ 插值多项式可以得到：
$N_n(x_0+th)=\sum\limits_{k=0}^n\dfrac{\Delta^kf_0}{k!}\prod\limits^{k-1}_{j=0}(t-j)$
称之为 $n此Newton前插公式$

Hermite插值
前面介绍的插值公式都只是考虑到插值多项式在插值节点处取给定的函数值但是往往在实际问题中只要求函数值满足还不够还要要求在这些点上的导数值也相等这即是 $Hermite$ 插值这里不做过多的讨论感兴趣的可以去翻看相关书籍。
高次插值的缺点及其分段插值
在进行高次插值的时候有可能会发生龙格函数函数的状况，即高次插值的插值多项式有可能并不收敛于已知函数 $f(x)$ 为了应对这种清苦保证插值函数一致收敛于已知函数，我们可以把已知函数分成 $N$ 个小区间然后在每个小区间上进行 $Newdon$ 插值或者 $Lagrange$ 插值，但是如果分成的插值小区间过多的时候在每个小区间上面我们其实不要选择过多的插值节点就可以，因为区间小插值函数比较精准，所以一般我们每个小区间上面选取一个到四个插值节点就够了，但是往往我们还要满足插值节点的导数情况这样我们只要知道区间端点的两个函数值及其导数值我们就可以构建每个小区间上的三次插值多项式这就是三次样条插值。
三次样条插值：
设在区间 $[a,b]$ 上给定 $(n+1)$ 个插值节点
$a=x_0\lt x_1 \lt \cdots \lt x_n=b$ 及其相对应的函数值 $f(x_0),f(x_1),\cdots,f(x_n)$
若函数 $S(x)$ 满足：
$(1)$ $S(x_i)=f(x_i)$
$(2)$ $S(x)$ 在每一个小区间 $[x_i,x_{i+1}]$ 上是三次多项式
$(3)$ $S(x)在[a,b]$ 上有连续的二阶导数则称 $S(x)$ 为3次样条插值函数
从定义可知要使得 $S(x)$ 在每个小区间上都是三次多项式则每个小区间上需要 $S(x)$ 满足四个条件才能够构建三次多项式，总共需要4n个条件，有已经知条件有 $n+1$ 个插值节点满足的条件有 $n+1$ 个条件，再加上联结条件
$\begin{cases} S(x_i-0)=S(x_i+0)\\S^\prime(x_i-0)=S^\prime(x_i+0)\\S^{\prime\prime}(x_i-0)=S^{\prime\prime}(x_i+0)\end{cases}$ $i=1,2,\cdots,n-1$
这里有 $3(n-1)$ 个条件，一共就有了 $4n-2$ 个条件
在加上 $2$ 个边界条件：
$(1)$ $S^\prime(x_0)=f^\prime(x_0),S^\prime(x_1)=f^\prime(x_1)$
$(2)$ $S^{\prime\prime}(x_0)=f^{\prime\prime}(x_0),S^{\prime\prime}(x_1)=f^{\prime\prime}(x_1)$
$(3)$ $S^{\prime\prime\prime}(x_0)=f^{\prime\prime\prime}(x_0),S^{\prime\prime\prime}(x_1)=f^{\prime\prime\prime}(x_1)$
其中的一项总共就有 $4n$ 个条件就可以确定唯一的三次样条插值
至于三次样条的求法这里不做过多描叙感兴趣的自己去看书。

最佳一致逼近
之前的多项式插值都是要求在插值节点满足被插值函数的一些条件，在插值节点处误差为零，这是一种近似的度量标准，下面介绍另外的两种近似度量标准，要求在整个区间上插值函数与被插值函数的误差尽可能的小，但不要求相等。
最佳一致逼近多项式
设 $f\in C[a,b]$ 若存在 $p_n\in M_n$ 使得对任意的 $q_n\in M_n$ ( $M_n$ 为所有次数不超过 $n$ 的多项式的集合)
有： $max|f(x)-p_n(x)|\leqslant max|f(x)-q_n(x)|$ $\cdots$ $a\leqslant x \leqslant b$ , 则称 $p_n(x)$ 为 $f(x)$ 的最佳一致逼近多项式。
也就是说最佳一致逼近多项式是所有多项式中函数值与被插值函数的差的最大值最小的插值多项式
最佳一致逼近多项式的构建主要是利用最佳一致逼近多项式存在交错偏差点的性质。
为了求最佳一致逼近多项式以及求最佳近似一致逼近多项式可以引进 $Chebyshev$ 多项式 $T_n(x)=cos(n arccosx)$ ,有最佳一致逼近多项式的定义可知，要求最佳一致逼近多项式也就是求 $p_n(x)-f(x)$ 的最小零偏差问题，而正好 $Chebyshev$ 多项式有在区间 $[0,1]$ 上所有首项为一的 $n$ 次多项式中 $2^{1-n}T_n(x)$ 对零的偏差最小，因此可以借助 $Chebyshev$ 多项式求最佳一致逼近多项式，而且 $Chebyshev$ 多项式有很多的性质，比 $T_n(x)$ 在区间 $[-1,1]$ 有 $n$ 个不同的零点，还有一个交错偏差点组，如果以 $Chebyshev$ 多项式的零点做插值多项式则可以使得插值多项式的余项取得最小，这就是最佳近似一致逼近多项式。如果求不是在区间 $[-1,1]$ 上构建一致逼近多项式，那么可以通过变换把它变为 $[-1,1]$ 上的被插值函数然后做一致逼近。
具体内容请参考相关书籍
最佳平方逼近多项式
最佳一致逼近多项式考虑的是在区间上值的误差的最大值最小，而最佳平方逼近多项式是考虑在整体上误差最小，有些被插值函数仅仅只是在很小的一个区间上波动很大，这样的被插值函数显然用最佳一致逼近多项式去逼近并不合适，因此需要用另外的度量标准去度量近似程度。

离散数据的最佳一致平方逼近
设 $f(x_k)$ $k=0,1,2,\cdots,n$ 若存在 $p_n(x)\in M_n$ 使得对任意的 $q_n(x)\in M_n$ ( $M_n$ 为所有次数不超过 $n$ 的多项式的集合)
有： $\sum\limits^n_{k=0}|f(x_k)-p_n(x_k)|^2\leqslant \sum\limits^n_{k=0}|f(x_k)-q_n(x_k)|^2$ 则称 $p_n(x)$ 为 $f(x)$ 的最佳平方逼近多项式
连续函数在 $[a,b]$ 区间上的最佳一致逼近
$\int_a^b|f(x_k)-p_n(x_k)|^2dx\leqslant \int_a^b|f(x_k)-q_n(x_k)|^2 dx$
则称 $p_n(x)$ 为 $f(x)$ 的最佳平方逼近多项式

数值积分与数值微分

函数求导数与求微分的问题已经在数学分析中得到解决了，但是如果是面对离散的数据时候求导与求积公式都不能使用，而且计算机是不能够处理连续的问题的，因此如果要想把积分法则变成计算机程序就必须把积分变成离散的问题转变为四则运算而后才可以给计算机输入一套算法。
实际上一个函数在某个区间上面的积分本身就可以看做是函数在这个区间上无穷多项的和 $\int_a^bf(x)dx \approx\sum\limits_{k=0}^nA_kf(x_k)$ 我们不妨就设想积分有这样的形式。设给定的一组节点 $a \leqslant x_0\lt x_1\lt x_2\lt \cdots \lt x_n\leqslant b$ 已知函数在这组节点上的值为 $f(x_k)$ 则可以做插值多项式 $L_n(x)=\sum\limits^n_{k=0}f(x_k)l_k(x)$ , $l_k(x)$ 是插值基函数于是得到一个求积公式： $I_n(f)=\int^b_aL_n(x)dx$
得到 $I_n(f)=\sum\limits_{k=0}^nA_kf(x_k)$ , $A_k=\int_a^bl_k(x)dx$ 为求积系数如果求积节点是等距的那么其插值型求积公式为 $Newton-Cotes$ 求积公式求积系数的公式可以推导出来具体请参考相关书籍。

当选取两个求积节点的时候其求积公式如下：
$T(f)=\dfrac{b-a}{2}[f(a)+f(b)]$ 是为梯形公式
当选取三个节点的时候求积公式如下：
$S(f)=\dfrac{b-a}{6}[f(a)+4f(\dfrac{a+b}{2})+f(b)]$ 是为 $Simpson$ 公式
当选取五个等距节点的时候是为Cotes公式，公式略
代数精度的概念
如果求积公式对所有 $m$ 次多项式都精确成立且至少有一个 $m+1$ 次多项式不成立则称求积公式有 $m$ 次代数精度，梯形公式有有2次代数精度， $Simpson公式有3阶代数精度$ ， $Cotes$ 有五阶代数精度。
复化求积公式
所谓复化求积公式是当一个求积区间很大的时候我们可以把这个区间等分成很多分然后对每个小区间用插值型求积公式理论上来讲区间分的越小越精确误差越小
复化梯形公式
$T_n(f)$ = $\dfrac{h}{2}[f(x_0)+2\sum\limits^{n-1}_{k=1}f(x_k)]+f(x_n)$
复化 $Simpson$ 公式
$S_n(f)=\sum\limits_{k=0}^{n-1}\dfrac{h}{6}[f(x_k)]+4f(x_{k+\frac{1}{2}})+f(x_{k+1})$
其他复化公式略。。。

常微分方程的数值解法

在常微分方程中我们学习过常系数线性方程组，变系数微分方程组，与非线性方程组的求解公式，但是在实际科学研究中往往有很多的问题非常的复杂，我们无法运用常规的方法求其公式解或者是即便求出来了也及其的不方便计算，因此我们就只能想办法求其数值解。
Euler方法求解
$Euler$ 方法是求解初值问题的最简单的数值方法
为了求数值解我们需要把区间 $[a,b]$ 离散化为步长为 $h$ 的 $n+1$ 个小区间
讨论关于一阶微分方程的初值问题
$\begin{cases}y^\prime = f(x,y)\\y(a)=\eta\end{cases}$
将方程组一式两边积分移项可得：
$y(x_{i+1})=y(x_i)+\int_{x_i}^{x_{i+1}}(f(x,y(x))dx$
然后运用左矩形公式可得：
$y(x_{i+1})=y(x_i)+hf(x_i,y(x_i))+R$ $R 为余项$
则 $y(x_{i+1}) \approx y(x_i)+hf(x_i,y(x_i))$
则上式成为 $Euler$ 公式实际上欧拉公式就是把函数在第 $i$ 个小区间上的导数都用 $f(x_i,y(x_i))$ 来代替然后运用直线公式求其在节点的函数值，显然这种情况当区间选取足够小的时候才会精确
构造更高精度的求解公式梯形公式
将式 $y(x_{i+1})=y(x_i)+\int_{x_i}^{x_{i+1}}(f(x,y(x))dx$ 左边运用梯形公式可得 $y(x_{i+1}) \approx y(x_i)+\dfrac{h}{2}[f(x_i,y(x_i))+f(x_{i+1},y(x_{i+1}))]$ ,不难想象如果在一个小区间上我们多选取几个点求其斜率值的平均值那么求小区间内求积节点的数值解的准确度会更高，梯形公式就想当与用了两个点的平均斜率做函数在小区间上的斜率值，但是在这里我们的 $y_{i+1}$ 是一个未知值因此我们需要将 $Euler$ 公式与梯形公式合在一起用，先用 $Euler$ 公式求得 $y(x_{i+1})$ 的一个粗糙值， $y^{(p)}_{i+1}=y_i+hf(x_i,y_i)$ 然后将其带入梯形公式
$y(x_{i+1}) \approx y(x_i)+\dfrac{h}{2}[f(x_i,y(x_i))+f(x_{i+1},y^{(p)}_{i+1}(x_{i+1}))]$
求数值解就是把连续的问题，离散化，然后利用递推公式求值

最后编辑于：2019.01.19 22:20:36

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,793评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,567评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,342评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,825评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,814评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,680评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,033评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,687评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,175评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,668评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,775评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,419评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,020评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,206评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,092评论 2赞 351
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,510评论 2赞 343