研一课程笔记-数值分析4-6

非线性方程迭代解法

n次方程根的个数与次数相同（实根或者复根）

设有非线性方程

$$f(x)=0\tag{4.1}$$

其中 $f(x)$ 是一元非线性函数。若常数 $s$ 使 $f(s)=0$,则称 $s$ 是方程(4.1)的根，又称 $s$ 是函数 $f(x)$的零点。若 $f( x)$ 能分解为

$$f(x)=(x-s)^m\varphi(x)$$

其中 $m$ 是正整数，$\varphi(s)\neq0$ ，则称 $s$ 是方程(4.1)的 $m$ 重根和 $f(x)$ 的 $m$ 重零点。当 $m=1$ 时，$s$ 称为方程(4.1)的单根和 $f(x)$ 的单零点。

二分法

用 $C[a,b]$ 和 $C(a,b)$ 分别表示在闭区间 $[a,b]$ 和开区间 $(a,b)$ 上连续的函数集合。

设 $f(x)\in C[a,b]$且 $f(a)f(b)<0$，根据连续函数的介值定理，在区间$(a,b)$内至少有一实数 $s$，使 $f(s)=0$。现假定在$(a,b)$内只有一个实数 $s$ 使 $f(s)=0$,并要把 $s$ 求出来。用对分法求这个 s 的算法如下：

令$a_0=a,b_0=b$。

对于$k=0,1,\cdotp\cdotp\cdotp,M$ 执行

(1)计算 $x_k=\frac {a_k+b_k}2$

(2) 若 $b_k-a_k\leqslant\varepsilon$ 或$|f(x_k)|\leqslant\eta$,则停止计算，取 $s\approx x_k$ 否则转(3)。

(3)若 $f(a_k)f(x_k)<0$,则令 $a_k+1=a_k,b_{k+1}=x_k$ 若 $f(a_k)f(x_k)>0$，则令 $a_k+1=x_k,b_{k+1}=b_k$ 。

(4)若$k=M$，则输出$M$次迭代不成功的信息；否则继续。

迭代终止条件

一般通过 $\begin{vmatrix}x_{k+1}-x_k\end{vmatrix}<\varepsilon_1$ 或者 $\begin{vmatrix}f(x)\end{vmatrix}<\varepsilon_2$ 来作为迭代的终止条件，一般我们选择前者，因为后者可能会有梯度非常小的情况

简单迭代法及其收敛性

把 $f(x)=0$ 转化为等价的方程

$$x=\varphi(x) \tag{4.2}$$

从而 $f( s) = 0$ 等价于 $s= \varphi ( s)$ 。$s$ 叫 $\varphi(x)$ 的不动点。

选定$s$的初始近似值$x_0$，用递推公式

$$x_{k+1}=\varphi(x_k)\quad(k=0,1,\cdotp\cdotp\cdotp)\tag{4.3}$$

产生序列 $\left\{x_k\right\}$ ，在一定条件下，序列 $\left\{x_k\right\}$ 收敛于 $s$。在 $\left\{x_k\right\}$ 收敛的情况下，当 $k$ 足够大时就可取 $x_k$ 作为方程(4.1)的近似根。迭代公式(4.3)被称为求解方程(4.1)的简单迭代法，其中 $\varphi(x)$称为迭代函数。

对于任意的式(4.1)可构成多种简单选代法，它们的迭代函数各不相同。为求同一个根，它们所产生的序列$\left\{x_k\right\}$，有的可能收敛，有的可能不收敛；有的会收敛得快，有的会收敛得慢。这一切都取决于送代函数 $\varphi(x)$在有根区间内的性态。

大范围收敛性定理

设函数 $\varphi(x)\in C[a,b]$，在($a,b)$内可导，且满足两个条件：

1. 当$x\in[a,b]$时，$\varphi(x)\in[a,b];$
2. 当 $x\in(a,b)$时，$|\varphi^\prime(x)|\leqslant L<1$，其中$L$ 为一常数。

则有如下结论：

1. 方程(4.2)在区间[a,b]上有唯一的根 $s$ ;
2. 对任取的 $x_0\in[a,b]$，简单迭代法(4. 3)产生的序列 $\{x_k\}\subset[a,b]$ 且收敛于 $s$;
3. 成立误差估计式

$$\mid s-x_k\mid\leqslant\frac{L^k}{1-L}\mid x_1-x_0\mid \tag{4.4}$$

$$\mid s-x_k\mid\leqslant\frac L{1-L}\mid x_k-x_{k-1}\mid \tag{4.5}$$

1）令 $F(x)=x-\varphi(x)$，则 $F(x)\in C[a,b]$，并由条件(1)可知

$$F(a)=a-\varphi(a)\leqslant0,\quad F(b)=b-\varphi(b)\geqslant0$$

若上面两个不等式中有一个等号成立，则方程(4.2)有根 $s=a$ 或$s=b$。若两个都是严格不等式，则根据连续函数的介值定理，必存在 $s\in(a,b)$，使 $F(s)=s-\varphi(s)=0$，即方程(4.2)有根$s\in(a,b)$。今设有两个不同的 $s_1,s_2\in[a,b]$使 $s_1=\varphi(s_1),s_2=\varphi(s_2)$，则由微分中值定理以及条件(2)，有

$$\mid s_1-s_2\mid=\mid\varphi(s_1)-\varphi(s_2)\mid=\mid\varphi^{\prime}(\xi)\mid\mid s_1-s_2\mid\leqslant L\mid s_1-s_2\mid<\mid s_1-s_2\mid$$

其中 $\xi$ 在 $s_1$ 与 $s_2$ 之间，因而 $\xi\in(a,b)$。上式出现的矛盾证实$s_1=s_2$ 。

---

2）因 $x_0\in[a,b]$，由条件(1)可知，$\{x_k\}\subset[a,b]$。又由条件(2)，得

$$\mid x_k-s\mid=\mid\varphi(x_{k-1})-\varphi(s)\mid=\mid\varphi^{\prime}(\xi_k)\mid\cdot\mid x_{k-1}-s\mid\leqslant L\mid x_{k-1}-s\mid\leqslant\cdotp\cdotp\cdotp\leqslant L^k\mid x_0-s\mid$$

其中 $\xi_k$ 在 $x_k-1$ 与 $s$ 之间，因而 $\xi_k\in(a,b)$。因 0$\leqslant L<1$，故有 $\lim_{k\to\infty} x_k=s$。

---

3）设 $m>k$，则有

$$x_m-x_k=\sum_{i=k}^{m-1}(x_{i+1}-x_i)$$

而

$$\begin{aligned}\mid x_{i+1}-x_i\mid&=\mid\varphi(x_i)-\varphi(x_{i-1})\mid\leqslant\\&L\mid x_i-x_{i-1}\mid\leqslant\ldots\leqslant L^i\mid x_1-x_0\mid\end{aligned}$$

于是有：

$$\mid x_m-x_k\mid\leqslant\sum_{i=k}^{m-1}\mid x_{i+1}-x_i\mid\leqslant\sum_{i=k}^{m-1}L^i\mid x_1-x_0\mid=L^k\frac{1-L^{m-k}}{1-L}\mid x_1-x_0\mid$$

$$x_m-x_k=x_m-x_{m-1}+x_{m-1}\cdots-x_k$$

然后使用绝对值不等式

令 $m\to\infty$,由于 0$\leqslant L<1$，故由上式得到式(4.4)。

又由

$$\mid x_{i+1}-x_i\mid\leqslant L\mid x_i-x_{i-1}\mid\leqslant\cdots\leqslant L^{i-k+1}\mid x_k-x_{k-1}\mid$$

得

$$\mid x_m-x_k\mid\leqslant\sum_{i=k}^{m-1}\mid x_{i+1}-x_i\mid\leqslant\sum_{i=k}^{m-1}L^{i-k+1}\mid x_k-x_{k-1}\mid=L\frac{1-L^{m-k}}{1-L}\mid x_k-x_{k-1}\mid$$

令$m\to\infty$，由上式得到式(4.5)。证毕。

局部收敛性定理

注：定理4.2并没有给出邻域 $\delta$ 具体是什么，怎么计算，仅仅要求该邻域存在，也即迭代的起始点 $x_0$ 足够接近 $s$ 时 。总能得到收敛于 $s$ 的迭代序列。

简单迭代法收敛速度

这里 $\theta$ 相当于一个仿射变换，此外证明得到的 $\lim_{k\to\infty}\mid\varphi^{\prime}(s-\theta e_{k})\mid=\mid\varphi^{\prime}(s)\mid$ ，也就是说常数 $c=\mid\varphi^{\prime}(s)\mid$

证明中一个非常关键的点是连续性

牛顿法

用简单送代法求方程(4.1)的根 $s$，十分重要的问题是构造迭代函数 $\varphi(x)$。为了使收敛速度的阶高一些，应尽可能使 $\varphi(x)$ 在 $x=s$ 处有更多阶导数等于零。

现在令 $\varphi(x)=x+h(x)f(x)$，$h(x)$ 为待定函数，但 $h(s)\neq0$，代入简单迭代法 $\varphi(x)=x$，则方程(4.1)与方程

$$x=x+h(x)f(x)$$

有共同的根 $s$。现用条件 $\varphi^{\prime}(s)=0$ 确定 $h(x)$。由 $f(s)=0$，则：

$$\varphi^\prime(s)=1+h^\prime(s)f(s)+h(s)f^\prime(s)=1+h(s)f^\prime(s)=0$$

知 $h(x)$ 必须满足 $h(s)=\frac{-1}{f^{\prime}(s)}$。显然，取 $h(x)=-\frac1{f^{\prime}(x)}$ 就具备这个条件，并且也满反 $h(s)\neq0$。于是，$\varphi(x)$ 被确定为

$$\varphi(x)=x-\frac{f(x)}{f^{\prime}(x)}$$

它满足 $\varphi^\prime(s)=0$。由此得出下面的特殊的简单迭代法

$$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime}(x_k)}\quad(k=0,1,\cdotp\cdotp\cdotp)\tag{4.7}$$

式(4.7)所表示的迭代法称为 Newton(牛顿)法。

Newton 法可求方程(4.1)的实数根和复数根。当求实数根时，Newton 法有明显的几何意义。当获得 $x_k$ 之后，过曲线 y$=f(x)$上的点$(x_k,f(x_k))$作该曲线的切线，此切线与 $x$ 轴相交的交点横坐标就是 Newton 法迭代序列的第$k+1$个元素$x_{k-1}$。因此 Newton 法(4.7)又称为切线法。

局部收敛性

定理 4.6 设 $s$ 是方程(4.1)的根，在包含 s 的某个开区间内 $f^\prime(x)$ 连续且 $f^{\prime}(x)\neq0$，则存在 $\delta{>}0$，当 $x_0\in[s-\delta,s+\delta]$时，由 Newton 法(4.7)产生的序列 $\{x_k\}$ 收敛于 $s$；若 $f^\prime(s)\neq0$ 且 $x_0\neq s$，则序列 $\left\{x_k\right\}$ 是平方收敛的。

---

Newton 法(4.7)的迭代函数 $\varphi(x)$为

$$\varphi(x)=x-\frac{f(x)}{f^{'}(x)},\quad\varphi^{'}(x)=\frac{f(x)f^{''}(x)}{[f^{'}(x)]^2}$$

因 $f^\prime(x)$连续且 $f^\prime(x)\neq0$，故 $\varphi^{\prime}(x)$在包含 $s$ 的某个开区间内连续，并且有

$$\varphi(s)=s,\varphi^\prime(s)=0$$

根据定理 4.2，必存在 $\delta>0$，当 $x_0\in[s-\delta,s+\delta]$时，由送代法(4.7)产生的序列 $\{x_k\}\subset[s-\delta,s+\delta]$，且收敛于 $s$。

由 Taylor 公式以及 $f(s)=0$，有

$$f(s)=f(x_k)+f^{\prime}(x_k)(s-x_k)+\frac{f^{\prime\prime}(\xi_k)}{2!}(s-x_k)^2=0$$

$$x_{k+1}-s=x_k-\frac{f(x_k)}{f^{\prime}(x_k)}-s=\frac{f^{\prime\prime}(\xi_k)}{2f^{\prime}(x_k)}(s-x_k)^2$$

其中 $\xi_k$ 在 $x_k$ 与 $s$ 之间。因 $f^\prime(s)\neq0$ 以及 $f^{\prime}(x)$ 的连续性，故可设当 $x\in[s-\delta,s+\delta]$ 时 $f^{\prime\prime}(x)\neq0$。因而当 $x_0\in[s-\delta,s+\delta]$ 且 $x_0\neq s$ 时$,x_k\neq s(k=1,2,...)$。于是有

$$\lim_{k\to\infty}\frac{\mid x_{k+1}-s\mid}{\mid x_k-s\mid^2}=\left|\frac{f^{\prime\prime}(s)}{2f^{\prime}(s)}\right|>0$$

故序列 $\left\{x_k\right\}$ 是平方收敛的。

证毕。

定理 4.6 是 Newton 法的局部收敛性定理。如果 $f(x)$ 只满足此定理的条件，则在一般情况下，初值 $x_{0}$ 要比较靠近所要求的根 $s$，Newton 法才能收敛，也就是定理结论中的 $\delta$ 要比较小。

大范围收敛性（收敛的充分条件

定理 4.7 设函数 $f(x)$ 在区间 $[a,b]$上存在二阶连续导数，且满足条件：

1. $f( a) f( b) {< }0$ ;（根存在）

2. $f^{\prime\prime}(x)$ 在区间 $[a,b]$ 上不变号；（根唯一）

3. 当 $x\in[a,b]$ 时，$f^\prime(x)\neq0;$（$f^\prime(x)\neq0$，根唯一）

4. $x_{0}\in [ a, b] , f( x_{0}) f^{\prime \prime }( x_{0}) > 0$ 。

则由 Newton 法(4.7)产生的序列$\{ x_k \}$ 单调收敛于方程(4.1) 在 $[a, b]$ 内唯一的根 $s$，并且至少是平方收敛的。

插值与逼近

代数插值

给定 $n+1$ 个互异的实数 $x_0, x_1, \cdots , x_n$，实值函数 $f( x)$ 在包含 $x_0,x_1,\cdots,x_n$ 的某个区间 $[a,b]$ 内有定义。设函数组

$$\{\varphi_k(x)(k=0,1,\cdots,n)\}$$

是次数不高于 $n$ 的多项式组，且在点集 $\left\{x_0,x_1,\cdots,x_n\right\}$ 上线性无关。

现在提出如下的问题：在次数不高于 $n$ 的多项式集合

$$\mathscr{D}_n=\mathrm{Span}\{\varphi_0,\varphi_1,\cdots,\varphi_n\}$$

中寻求多项式

$$p_n(x)=\sum_{k=0}^nc_k\varphi_k(x)\tag{5.1}$$

使其满足条件

$$p_n(x_i)=f(x_i)\quad(i=0,1,\cdots,n)\tag{5.2}$$

此问题称为一元函数的代数插值问题。$x_0,x_1,\cdotp\cdotp\cdotp,x_n$ 称为插值节点；$f(x)$ 称为被插值函数； $\varphi_k(x)(k=0,1,\cdots,n)$ 称为插值基函数；条件(5.2)称为插值条件；满足插值条件(5.2)的多项式(5.1)称为 n 次插值多项式。

由于插值基函数组 $\{\varphi_k(x)(k=0,1,\cdots,n)\}$ 在点集 $\left\{x_0,x_1,\cdots,x_n\right\}$ 上线性无关，所以满足插值条件(5.2)的 $n$ 次插值多项式 $p_n(x)$ 是存在且唯一的。

又由于插值基函数组限定为次数不高于$n$的多项式组，所以对于不同的插值基函数组，只要满足同一插值条件(5.2)，则所得的$n$次插值多项式也是唯一的。

对于 $n+1$ 个插值点， $p_n(x_i)=f(x_i)$ 有 $n+1$ 个方程：$p(x_i)=\sum^n_{j=0}a_jx_i^j=f(x_i)$

最后可以化为矩阵 $X\cdot A=F$ （分别是 列向量 $x_i$，值 $a_i,f(x_i)$ 构成的矩阵）

拉格朗日插值

取插值基函数

$$l_k(x)=\prod_{j=0}^n\frac{x-x_j}{x_k-x_j}\quad(k=0,1,\cdotp\cdotp\cdotp,n) \tag{5.3}$$

显然，$l_k(x)(k=0,1,...,n)$ 都是 $n$ 次多项式，且具有下列性质

$$l_k(x_i)=\begin{cases}1,&i=k\\0,&i\neq k\end{cases}$$

显然，通过这种方式得到的 $l_k(x_i)$ 仅第 $i$ 个分量为1，所以彼此一定会线性无关

因此，函数组 $\left\{l_k(x)(k=0,1,\cdotp\cdotp\cdotp,n)\right\}$ 必在点集 $\left\{x_0,x_1,\cdotp\cdotp\cdotp,x_n\right\}$ 上线性无关，并且

$$p_n(x)=\sum_{k=0}^nl_k(x)f(x_k)\tag{5.4}$$

由 $c_kl(x_k)=0,k\neq j$

$p_n(x_j)=\sum c_i l(x_i)=c_jl(x_j)=c_j=f(x_j)$

或

$$p_n(x)=\sum_{k=0}^n\Big(\prod_{j=0}^n\frac{x-x_j}{x_k-x_j}\Big)f(x_k)\tag{5.5}$$

就是满足插值条件(5.2)的 $n$ 次插值多项式。

牛顿插值

拉格朗日插值在计算过程中若需要改变节点或增加节点时， 全部基函数 $l_k(x)$ 都需要重新计算 ，这在实际计算中很不方便

目标是寻找新的基函数，使得每加一个节点时，只附加一项 上去 ，而不必重新计算全部基函数

Newton 插值多项式的构造

基函数如下：

$$\{\varphi_k(x)\}=\{1,x-x_0,(x-x_0)(x-x_1),\ldots,(x-x_0)(x-x_1)\ldots(x-x_{n-1})\}$$

$$\begin{pmatrix}\varphi_0(x_0),\varphi_1(x_0),\ldots,\varphi_n(x_0)\\\varphi_0(x_1),\varphi_1(x_1),\ldots,\varphi_n(x_1)\\\vdots&\vdots&\vdots\\\varphi_0(x_n),\varphi_1(x_n),\ldots,\varphi_n(x_n)\end{pmatrix}=\begin{pmatrix}1&0&0&0\\1&x_1-x_0&0&0\\1&x_2-x_0&(x_2-x_0)(x_2-x_1)&\vdots\\\vdots&\vdots&\vdots&0\\\\1&x_n-x_0&(x_n-x_0)(x_n-x_1)&\prod_{j=0}^{n-1}(x_n-x_j)\end{pmatrix}$$

所以这组函数线性无关，故插值函数为：

$$\begin{aligned}p_{n}(x)&=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)\\&+\cdots+c_n(x-x_0)(x-x_1)\cdots(x-x_{n-1})\end{aligned}$$

由$p_n(x_i)=f(x_i)\quad(i=0,1,\cdots,n)$：

$$\begin{cases}&f(x_0)=p_n(x_0)=c_0\\&f(x_1)=p_n(x_1)=c_0+c_1(x_1-x_0)\\&f(x_2)=p_n(x_2)=c_0+c_1(x_2-x_0)+c_2(x_2-x_0)(x_2-x_1)\\&f(x_3)=p_n(x_3)=c_0+c_1(x_3-x_0)+c_2(x_3-x_0)(x_3-x_1)\\&f(x_n)=p_n(x_n)=c_0+c_1(x_n-x_0)+c_2(x_n-x_0)(x_n-x_1)+\cdots+c_n(x_n-x_0)\cdots(x_n-x_{n-1})\end{cases}$$

可得 $c_k=f[x_0,x_1,\cdots,x_k]$

k 阶差商

一阶差商：$f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}$

二阶差商：$f[x_0,x_1,x_2]=\frac{f[x_0,x_2]-f[x_0,x_1]}{x_2-x_1}$

k阶插商：

$$f[x_0,x_1,\cdots,x_k]=\frac{f[x_0,x_1,\cdots,x_{k-2},x_k]-f[x_0,x_1,\cdots,x_{k-1}]}{x_k-x_{k-1}}$$

牛顿插值公式利用差商可简单地表为

$$\begin{aligned} &N_0(x)=f(x_0) \\ &N_1(x)=f(x_0)+f[x_0,x_1](x-x_0) \\ & \quad \quad \quad =N_0(x)+f[x_0,x_1](x-x_0) \\ &N_2(x)=N_1(x)+f[x_0,x_1,x_2](x-x_0)(x-x_1) \\ &...... \\ &N_{k+1}(x)=N_k(x)+\underbrace{f[x_0,\cdots,x_{k+1}](x-x_0)(x-x_1)\cdots(x-x_k)} \end{aligned}$$

因此, 每增加一个结点， Newton 插值多项式只增加一项（即括号标注的一项）

插值余项

设 $x_0, x_1, \cdots , x_n$ 是互异实数，对给定的实数$x$，实值函数$f( x)$ 在区间 $I_x$ 上有 $n+ 1$ 阶导数，则拉格朗日插值多项式与牛顿插值多项式有相同的插值余项：

$$R_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i).$$

罗尔定理的推论：若 $\varphi ( x)$ 充分光滑，且 $\phi ( x_1) = \cdots = \phi ( x_n) = 0\Rightarrow$ 存在 $n-l$ 个 $\xi \in \tilde{I}$ 使得 $\varphi ^{( l) }( \xi ) = 0$

此外，过 $n +1$ 个点的 $n$ 次多项式是唯一的：$N_n(x)\equiv L_n(x)$

$R_n(x)$ 有 $n+1$ 个根 $x_0$~$x_n$

证明：

由于 $R_n( x_i) = 0$ , $\boldsymbol{i}= 0, 1, . . . , n$ $\Rightarrow$ $R_{n}(x)=u(x)\prod_{i=0}(x-x_{i})=f(x)-p_{n}(x)$

任意固定$x\neq x_i$ $( i= 0, . . . , n)$，构造辅助函数

$$g(t)=R_n(t)-u(x)\prod_{i=0}^n(t-x_i)=f(t)-p_n(t)-u(x)\prod_{i=0}^n(t-x_i)\tag{1}$$

则 $g( t)$ 有 $n+ 2$ 个不同的根 $x, x_0, \ldots , x_n$ 反复使用Rolle定理，可得存在 $\xi\in\tilde{I}_x$，使得：

$$g^{(n+1)}(\xi)=0,\xi\in\tilde{I}_{x}$$

$$\Rightarrow u(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\Rightarrow R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i).\tag{2}$$

显然 $\xi$ 和 $x$ 有关

对 (1) 式求导，由于 $p_n(t)$ 为 $n$ 次多项式，所以 $p_n^{(n+1)}(t)=0$，$[u(x)\prod_{i=0}^n(t-x_i)]^{(n+1)}=u(x)(n+1)!$ ，所以：

$$g^{(n+1)}(t)=f^{(n+1)}(t)-u(x)(n+1)!$$

即可得到 (2) 式

正交多项式

权函数

定义 权函数 在区间($a,b)$上，若非负函数$\rho ( x)$ 满足

1. 对一切整数$n\geq0,\int_a^bx^n\rho(x)dx$ 存在；

2. 对 $( a, b)$ 上的非负连续函数 $f( x)$，若 $\int _{a}^{b}\rho ( x) f( x) dx= 0$，则在区间 $( a, b)$上 $f( x) \equiv 0.$

那么，称 $\rho(x)$ 为 $(a,b)$ 上的权函数。

常见的权函数：$\rho ( x) \equiv 1, a\leq x\leq b;$

内积

给定 $f( x) , g( x) \in C[ a, b] , \rho ( x)$ 是 $(a,b)$ 上的权函数，称

$$(f,g)=\int_a^b\rho(x)f(x)g(x)dx$$

为 $f$,$g$ 在 $[a,b]$ 上的内积.

内积的性质

1. $\left(f,\:g\right)=\left(\:g,\:f\right);$

2. $(kf,g)=(f,kg)=k(f,g),k$ 为常数，$k\in R;$

3. $\left(f_{1}+f_{2},\:g\right)=\left(f_{1},g\:\right)+\left(f_{2},g\:\right);$

4. 若在 $[a,b]$ 上 $f(x)\not\equiv0$，则 $(f,f)>0.$

正交与正交函数系

若内积

$$(f,g)=\int_a^b\rho(x)f(x)g(x)dx=0$$

则称 $f$, g 在 $[a,b]$ 上带权 $\rho(x)$ 正交.

正交函数系

定义 若函数系 $\{\varphi_0(x),\varphi_1(x),...,\varphi_n(x),...\}$ 满足

$$(\varphi_i,\varphi_j)=\int_a^b\rho(x)\varphi_i(x)\varphi_j(x)dx=\begin{cases}0, i\neq j\\a_i>0,i=j\end{cases}$$

则称 $\{\varphi_n(x)\}$ 是 $[a,b]$ 上带权 $\rho(x)$ 的正交函数系.

• $[a,b]$ 上带权 $\rho(x)$ 的正交函数系必是线性无关的函数系，而不论 $\rho(x)$ 是什么函数.

  • 这里函数系线性无关与前面插值里的线性无关不是一个概念

• 设 $\varphi_k(x)$ 是最高项系数不为零的 $k$ 次多项式，$k=0,1,2,\ldots;$ 则 $\{\boldsymbol{\varphi}_k(x)\}$ 是 $[a,b]$ 上带权 $\rho(x)$的正交多项式系

  $\Leftrightarrow$(充分必要条件)

  对任何次数不高于 $k-1$ 的多项式 $q(x)$，总有

  $$(q,\varphi_k)=\int_a\rho(x)q(x)\varphi_k(x)dx=0,k=1,2,\cdots.$$

性质

1. (结构)设 $\{\varphi_k(x)\}$ 是 $[a,b]$ 上带权 $\rho(x)$ 的正交多项式系，则$\left\{c_k\varphi_k(x)\right\}$也是$[a,b]$上带权 $\rho(x)$的正交多项式系。其中，$c_k$是非零常数.

2. (唯一性){$\varphi_k(x)\}$是区间$[a,b]$上带权 $\rho(x)$的正交多项式系，若各个$\varphi_k(x)$的最高次项系数是1，则这样的$\{\varphi_k(x)\}$是唯一的.
   证 设 $\{\varphi_k(x)\},\{g_k(x)\}$ 为性质2中要求正交多项式系，
   $k=0$时，$\varphi_0(x)\equiv1\equiv g_0(x).$
   $k\geq 1$ 时，$g_k- \varphi _k$ 是次数不高于 $k- 1$的多项式，由定理5.6知，

   $$\begin{aligned}&(\:g_k-\varphi_k,\:\varphi_k\:)=(\:g_k-\varphi_k,\:g_k\:)=0\\&\Leftrightarrow(g_k-\varphi_k,g_k-\varphi_k)=0,\\&\Leftrightarrow g_k-\varphi_k\equiv0,\quad g_k(x)\equiv\varphi_k(x)_,a\leq x\leq b\end{aligned}$$

3. (正交多项式的根)若 ${\varphi_k(x)}$ 是 $[a,b]$ 上带权 $\rho(x)$ 的 正交多项式系，则 $k\geq1$时，$k$ 次正交多项式 $\varphi_k(x)$ 在 $(a,b)$ 内有 $k$ 个互异的实根.

   事实上，可以证明 $k$ 次正交多项式有$k$ 个单根.

4. 设{$\varphi_k(x)\}$是区间$[a,b]$上带权 $\rho(x)$的正交多项式系，则 $k\geq1$时，有如下的递推关系式：

$$\phi_{k+1}(x)=\frac{a_{k+1}}{a_k}(x-\beta_k)\phi_k(x)-\frac{a_{k+1}a_{k-1}}{a_k^2}\lambda_{k-1}\phi_{k-1}(x)$$

其中，$a_k$ 是 $\varphi_k(x)$ 的最高次项系数，且

$$\beta_{k}=\frac{(x\varphi_{k},\varphi_{k})}{(\varphi_{k},\varphi_{k})},\quad\lambda_{k-1}=\frac{(\varphi_{k},\varphi_{k})}{(\varphi_{k-1},\varphi_{k-1})}.$$

函数的最佳平方逼近

函数的最佳逼近问题：对函数类 $A$ 中给定的函数 $f( x)$，需要在另一类较简单的便于计算的函数类 $B$ $( B\in A)$ 中，找一个函数$P( x)$，使 $P(x)$ 与 $f (x)$ 之差在某种度量意义下达到最小。

函数$f(x)$ 称为被逼近函数；$P( x)$ 称为逼近函数，两者之差称为逼近误差。

函数类 $A$ 通常是区间 $[a,b]$ 上的连续函数，记作 $C[a,b]$；函数类 $B$ 通常是代数多项式，有理多项式 ，三角多项式，分段多项式等容易计算的函数。

常用度量标准

1. 一致逼近(均匀逼近)以 $\max _a\leq x\leq b| f( x) - p( x) |$ 作为度量误差 $f(x)-P( x)$ 的“大小” 标准

2. 平方逼近(均方逼近)以 以 $\int_a^b[f(x)-p(x)]^2dx$ 作为度量误差 $f(x)-P( x)$ 的“大小” 标准

最佳平方逼近的概念与解法

$H_n= \operatorname { Span} \{ \varphi _0( x) , \varphi _1( x) , . . . , \varphi _n( x) \}$ 是 $\varphi_i(x)$ 张成的线性空间

定理5.7 设$f(x)\in C[a,b],p^*(x)\in H_n$，在 $H_n$ 中，$p^* ( x)$ 是 $f( x)$ 最佳平方逼近的函数$\Leftrightarrow(f-p^*,\varphi_j)=0,j=0,1,...,n$ 其中，$\{ \varphi _0( x) , \varphi _1( x) , . . . , \varphi _n( x) \}$ 为子空间 $H_n$ 的一组基

$( \Rightarrow )$$p^*(x)=\sum c_i^*\varphi _i(x)$ 代入 $(f-p^*,\varphi_j)=0$ 得 $(f-\sum c_i^*\varphi _i,\varphi_j)=0$

则 $(f,\varphi_j)=(\sum c_i^*\varphi _i,\varphi_j)=\sum c_i^*(\varphi_i,\varphi_j)$

即：

$$\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}c_0^*\\c_1^*\\\vdots\\c_n^*\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix}$$

从而求解系数 $c_i^*$

$( \Leftarrow )$若$( f- p^*, \varphi _j) = 0, j= 0, 1, . . . , n$ 成立，对任意的 $p( x) \in H_n$，有

$$\begin{aligned}(f-p,f-p)&=(f-p^*+p^*-p,f-p^*+p^*-p)\\&=(f-p^*,f-p^*)+2(f-p^*,p^*-p)+(p^*-p,p^*-p)\end{aligned}$$

由于 $\left ( f- p^* , p^* - p\right ) = \sum _{j= 0}^n\left ( c_j^* - c_j\right ) \left ( f- p^* , \varphi _j\right ) = 0$ 及 $( p^* - p, p^* - p) \geq 0$，故 $(f-p,f-p)\geq(f-p^*,f-p^*).$

$p^*$ 在 $H_n$ 中是对 $f$ 的最佳平方逼近函数

即设 $f(x)\in C[a,b],p^*(x)\in H_n$，在 $H_n$ 中，$p^* ( x)$ 是对 $f( x)$ 最佳平方逼近的函数$\Leftrightarrow$对任意的 $p( x) \in H_n$ 均有

$$(f-p^*,p)=0$$

定理5.8 设 $f( x) \in C[ a, b]$ 在子空间 $H_n$中，对 $f( x)$ 最佳平方逼近的函数是唯一的

最佳平方逼近的求解

$$ (f,g)=\int_a^b\rho(x)f(x)g(x)dx $$ 一般来说权函数默认 $\rho(x)=1$

正交函数系在最佳平方逼近中的应用

对于正交函数系，$(\varphi_{k},\varphi_{j})=\int\rho(x)\varphi_{k}(x)\varphi_{j}(x)dx=0,k\neq j$

$$\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}c_0\\c_1\\\vdots\\c_n\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix}$$

$$\Rightarrow\begin{bmatrix}(\varphi_0,\varphi_0)\\&(\varphi_1,\varphi_1)\\&&\ddots\\&&&(\varphi_n,\varphi_n)\end{bmatrix}\begin{bmatrix}c_0\\c_1\\\vdots\\c_n\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix}$$

$$\Rightarrow c_k=\frac{(f,\varphi_k)}{(\varphi_k,\varphi_k)},\quad k=0,1,2,...,n$$

曲线拟合

与插值的一个非常大的区别就是曲线拟合的函数 $y^*(x)$ 不要求经过所有数据点。

最小二乘问题

最小二乘问题的矩阵表示

最小二乘解的特征

最小二乘法的精度

正交多项式用于曲线拟合

数值积分

目的是求一些牛顿-莱布尼茨积分公式无法求解的积分函数

求积公式及其代数精度

一求积公式的一般形式：

$$\int_a^bf(x)dx\approx\sum_{k=0}^n\lambda_kf(x_k)\tag{6.1}$$

式中 $x_k( k= 0, 1, \cdots , n)$ 称为求积节点，它们满足 :

$$a\leq x_0<x_1<\ldots<x_n\leq b$$

$\lambda _{k}( k= 0, 1, \cdots , n)$ 称为求积系数，与被积函数无关 。

当求积节点与求积系数确定了以后，求积公式就确定了，因此任务是确定求积节点和求积系数。

截断误差或余项：

$$R_n=\int_a^bf(x)dx-\sum_{k=0}^n\lambda_kf(x_k)$$

代数精度

对求积公式(6.1)，当 $f(x)$ 为任何次数不高于 $m$ 的多项式时都成立，而当 $f(x)$ 为某个 $m+1$ 次多项式时不成立，则称它具有 $m$ 次代

数精度。

如何求解代数精度：对求积公式(6.1)，当 $f(x)$ 为 $1,x,x^2,\cdots,x^n$ 时，求积公式均成立，则对于任何次数不高于 $m$ 的多项式求积公式也必然成立。

差值型求积公式

利用插值多项式 $p_n(x)$ 逼近代替 $f(x)$ 计算积分

在$\left [ a, b\right ]$ 上取 $a\leq x_0< x_1< \ldots < x_m\leq b$ 。构 造 $f$ 的 $n$ 次Lagrange插值基函数

$$p_n(x)=\sum_{k=0}^nl_k(x)f(x_k),l_k(x)=\prod_{i=0}^n\frac{x-x_i}{x_k-x_i},k=0,1,\cdots,n$$

$$\int_a^bf(x)dx\approx\sum_{k=0}^n\left(\int_a^bl_k(x)\mathrm{d}x\right)f(x_k)\tag{6.1.1}$$

$$\lambda_k^{(n)}=\int_a^bl_k(x)\mathrm{d}x=\int_a^b\prod_{i=0\atop i\neq k}^n\frac{x-x_i}{x_k-x_i}\mathrm{d}x,k=0,1,\cdots,n\tag{6.2}$$

其中，$\lambda_k^{(n)}$ 由节点决定与 $f(x)$ 无关。

设函数 $f(x)$ 在区间 $[a,b]$ 上足够光滑,则由定理5.1得

$$f(x)=\sum_{k=0}^nl_k\left(x\right)f(x_k)+\frac{f^{(n+1)}\left(\xi\right)}{\left(n+1\right)!}\prod_{j=0}^n\left(x-x_j\right)$$

其中 $x\in[a,b],\xi=\xi(x)\in(a,b)$ 因此，可得

$$R_n=\int_a^bf(x)\mathrm{d}x-\sum_{k=0}^n\lambda_k^{(n)}f(x_k)=\int_a^b[f(x)-L_n(x)]\mathrm{d}x\\=\sum_{k=0}^n\left(\int_a^bl_k\left(x\right)dx\right)f(x_k)+\int_a^b\frac{f^{(n+1)}\left(\xi\right)}{\left(n+1\right)!}\prod_{j=0}^n\left(x-x_j\right)dx-\sum_{k=0}^n\left(\int_a^bl_k^{\prime}(x)\mathrm{d}x\right)f(x_k)\\=\int_a^b \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{j=0}^n\left(x-x_j\right)dx$$

定理与相关推论

• 定理6.1 $n+1$ 个节点的求积公式(6.1.1)，(6.2) 至少有 $n$ 次代数精度

• 推论 $n+1$个节点的插值型求积公式中的求积系数 $\lambda_k^{(n)}$ 满足

$$\sum_{k=0}^n\lambda_k^{(n)}=b-a$$

其中，$a,b$ 为积分下上限

• 定理6.2 $n+1$个节点的求积公式 (6.1)至少有 $n$ 次代数精度则它一定是插值型求积公式。

Newton-Cotes 求积公式

等距节点插值积分

将积分区间 $[a,b]$ 划分为 $n$ 等份，步长为 $h=\frac{b-a}n$ ，节点等距为 $x_k=a+kh$ 构造出的插值求积公式

$$\int_a^bf(x)dx\approx\sum_{k=0}^n\left(\int_a^bl_k(x)\mathrm{d}x\right)f(x_k)$$

$$\lambda_k^{(n)}=\int_a^bl_k(x)\mathrm{d}x=\int_a^b\prod_{i=0\atop i\neq k}^n\frac{x-x_i}{x_k-x_i}\mathrm{d}x,k=0,1,\cdots,n$$

Newton-Cotes求积公式，式中 $\lambda_{k}^{(n)}$ 称为Newton-Cotes求积系数

• 定理6.3 当 $n$ 为偶数时，$n+1$个节点的 $n$ 阶Newton-Cotes 求积公式的代数精度至少是$n+1$ 次。

收敛性

考察是否对任何在$[ a, b]$ 上 可 积 的 函 数 $f( x)$ 都有

$$\lim_{n\to\infty}\biggl[\sum_{k=0}^n\lambda_k^{(n)}f\biggl(a+k\frac{b-a}n\biggr)\biggr]=\int_a^bf(x)\mathrm{d}x.$$

其中，$\lambda _k^{( n) }$ 是 Newton-Cotes 求积系数。答案是否定的

几个常用公式

常微分方程初值问题的数值解法

一般概念

一常微分方程初值问题

$$\begin{cases}y'=f\left(t,y\right),t_0\leq t\leq T&(7.1)\\y\left(t_0\right)=y_0&(7.2)\end{cases}$$

函数 $f( x)$ 在区域

$$D_0=\left\{\left(t,y\right)|t_0\leq t\leq T,\mid y\mid<\infty\right\}$$

内连续目对变量 $y$ 满足Lipschitz(李普希兹)条件

$$\left|f\left(t,u_1\right)-f\left(t,u_2\right)\right|\leq L\left|u_1-u_2\right|$$

其中$( t, u_1) , ( t, u_2) \in D_0$ 这样初值问题 $( 7. 1) , ( 7. 2)$的解存在且唯一。

额外假设：$\gamma(t),t\in[t_0,T]$ 足够光滑

注意这里只需要对 $y$ 满足李普希兹条件

解的存在性

• 定理1 设函数 $f(t,y)$ 在凸集 $D\subset R^2$ 中有定义，若存在常数 $L$ 对 $\forall(t,y)\in D$ ，有 $\left|\frac\partial f(t,y){\partial y}\right|\leq L$ ，则 $f$ 在 $D$ 内关于 $\gamma$ 满足Lipschtiz条件。

• 定理2 设函数 $f(t,y)$ 在 $D=\left\{(t,y)|t_0\leq t\leq T,-\infty<y<\infty\right\}$ 内连续且在 $D$ 内关于 $y$ 满足 Lipschitz 条件，则初值问题(7.1),(7.2)在区间 $[t_0,T]$ 内存在唯一解。

注：满足定理2条件的初值问题也称良态问题。

数值解法

单步法与多步法

给定步长 $h> 0$ ，取节点 $t_n= t_0+ nh, n= 0, 1, \cdots , M$

其中 $t_M\leq T$ 通过数值方法，求出各个节点处满足 $( 7. 1) , ( 7. 2)$ 的近似值 $y_n\approx y( t_n) , n= 1, \cdots , M$ 如下

$$F( t_n, y_n, y_{n+ 1}, \cdots , y_{n+ k}, h) = 0, n= 0, 1, \cdots , M- k\tag{7.3}$$

上式称为关于 $y_n, n= 0, 1, \cdots , M$ 的差分方程

• 若 $k= 1, F( t_n, y_n, y_{n+ 1}, h) = 0, n= 0, 1, \cdots , M- 1 (7.4)$ 称之为单步法

• $k\geq2$ 则数值解法(7.3)统称为多步法，具体地称为 $k$ 步法

显式法与隐式法

若差分方程(7.3)能表示为如下显函数：

$$y_{n+k}=G(t_n,y_n,y_{n+1},\cdots,y_{n+k-1},h),n=0,1,\cdots,M-k\tag{7.5}$$

称数值解法(7.5)为显式法；否则称为隐式法（即 $G(\cdots)=0$ 的形式）

整体截断误差

设 $y(t)$ 是初值问题(7.1)，(7.2)的解，$y_1,y_2,\cdots,y_M$ 是由数值解法(7.3)解出的初值问题(7.1)，(7.2)的数值解，则称误差

$$\varepsilon_n=y\left(t_n\right)-y_n$$

为数值解法(7.3)在节点 $t_n$ 处的整体截断误差。

显示单步法

Euler折线法

设良态微分方程初值问题

$$\begin{cases}y'=f(t,y),t_0\leq t\leq T\\y(t_0)=y_0\end{cases}$$

解存在且唯一。取等距结点：

$$t_n=t_0+nh,n=0,1,\cdots,M;h=(T-t_0)/M$$

由泰勒公式，有：

$$y(t_{n+1})=y(t_n)+hy^{\prime}(t_n)+\frac{h^2}2y^{\prime\prime}(\xi_n)\\=y(t_n)+hf(t_n,y(t_n))+\frac{h^2}2y^{\prime\prime}(\xi_n)$$

假定 $y_n\approx y(t_n)$ ，并舍去 $h^2$ 项，可构造出Eular折线法

$$\begin{cases}y_0=y(t_0)\\y_{n+1}=y_n+hf(t_n,y_n)\end{cases}\quad n=0,1,\cdots,M$$

几何意义

由于 $f(t_0,y_0)$ 已知，则 $y(t)$ 在 $(t_0,y_0)$ 处必有切线方程，其斜率为\frac{dy}{dt}\Bigg|_{(t_0,y_0)}=f(t_0,y_0)

$$\frac{dy}{dt}\Bigg|_{(t_0,y_0)}=f(t_0,y_0)$$

由点斜式写出切线方程

$$y=y_0+\left(t-t_0\right)\frac{dy}{dt}\Bigg|_{(x_0,y_0)}=y_0+\left(t-t_0\right)f(t_0,y_0)$$

步长为 $h$，则 $t_1-t_0=h$ ，可由切线算出 $y_1=y_0+hf(t_0,y_0)$ 按此逐步计算 $y(t_n)$ ，在 $t_n+1$ 处的值 $y_n+1=y_n+hf(t_n,y_n)$

注意：$y(t_n)$ 为函数真值，$y_n$ 为迭代值

一般形式

显示单步法的一般形式

$$y_{n+1}=y_n+h\varphi\left(t_n,y_n,h\right),n=0,1,\cdots,M-1\tag{7.6}$$

其中，函数 $\varphi(\cdot)$ 与函数 $f$ 有关，称为增量函数

整体截断误差

在 $t_{n+1}$ 处的整体截断误差为：

$$\varepsilon_{n+1}=y\left(t_{n+1}\right)-y_{n+1}\\ =R_{n+1}+\varepsilon_{n}+h\left[\varphi\left(t_n,y\left(t_n\right),h\right)-\varphi\left(t_n,y_n,h\right)\right]\\ =y(t_{n+1})-y(t_n)-h\varphi(t_n,y(t_n),h)+y\left(t_n\right)-y_n+h\left[\varphi\left(t_n,y\left(t_n\right),h\right)-\varphi\left(t_n,y_n,h\right)\right]\tag{7.7}$$

局部截断误差

设 $\gamma(t)$ 是初值问题(7.1)，(7.2)的解，则称：

$$R_{n+1}=y\left(t_{n+1}\right)-y\left(t_n\right)-h\varphi\left(t_n,y\left(t_n\right),h\right)\tag{7.8}$$

为单步法(7.6)的局部截断误差

定义 若单步法(7.6)的局部截断误差(7.8)与 $h^{p+1}$ （ $p$ 为正整数）同阶，即 $R_n+1=O(h^{p+1})$ 。则称单步法(7.6)是 $p$ 阶方法。

定理

定理 1 设增量函数 $\varphi(t,y,h)$ 在区域

$$D=\{(t,y,h)|t_0\leq t\leq T,|y|<\infty,0\leq h\leq h_0\}$$

内对变量 $y$ 满足Lipschitz条件，即存在常数 $K$ 使对 $D$ 内任何两点 $(t,u_1,h),(t,u_2,h)$ ，不等式

$$\begin{vmatrix}\varphi(t,u_1,h)-\varphi(t,u_2,h)\end{vmatrix}\leq K\begin{vmatrix}u_1-u_2\end{vmatrix}$$

成立，那么，若单步法(7.6)的局部截断 $R_{n+1}$ 与 $h^{p+1}(p\geq1)$ 同阶，即

$$R_{n+1}=O(h^{p+1})$$

则单步法(7.6)的整体截断误差 $\varepsilon_{n+1}$ 与 $h^p$ 同阶，即有

$$\varepsilon_{n+1}=O(h^p)$$

证明

由式(7.7)，有

$$\left|\varepsilon_{n+1}\right|\leq \left|R_{n+1}\right|+\left|y(t_n)-y_n\right|+h\left|\varphi(t_n,y(t_n),h)-\varphi(t_n,y_n,h)\right|\\ \leq |R_{n+1}|+|\varepsilon_{n}|+hK|\varepsilon_{n}|\\ =\left|R_{n+1}\right|+\left|\varepsilon_n\right|(1+hK)\\\leq\left|R_{n+1}\right|+\left|R_n\right|(1+hK)+\left|\varepsilon_{n-1}\right|(1+hK)^2\\ \cdots\leq\sum_{k=0}^n\left|R_{n+1-k}\right|(1+hK)^k+\left|\varepsilon_0\right|(1+hK)^{n+1}$$

记 $R=\max_{1\leq n\leq M}|R_n|$，并注意到 $\boldsymbol{\varepsilon}_0=0$ ，就有

$$\left|\varepsilon_{n+1}\right|\leq R\sum_{k=0}^n(1+hK)^k=\frac R{hK}[(1+hK)^{n+1}-1]\leq\\\frac R{hK}(\mathrm{e}^{(n+1)hK}-1)\leq\frac1{hK}O(h^{p+1})(\mathrm{e}^{(t_{n+1}-t_0)K}-1)=O(h^p)$$

这里用到了 $1+x\leq e^x$

由此可知，$\varepsilon_{n+1}$ 可表示为 $\varepsilon_n+1=c(t_{n+1})h^p+O(h^{p+1})$

Runge-Kutta方法

称为显式Runge-Kutta(龙格-库塔)方法，简称R-K方法， 其中正整数 $N$ 称为R-K方法的级，所有$c_i,a_i,b_{ij}$ 都是待定常数。

根据定义(7.8)，$N$ 级R-K方法(7.9)的局部截断误差为

$$R_{n+1}=y(t_{n+1})-y(t_n)-h\sum_{i=1}^Nc_ik_i\tag{7.10}$$

其中 $k_1,k_2,\cdots,k_N$ 中的 $y_n$ 都换成 $y(t_n)$。如果系数 $c_i,a_i,b_{ij}$ 能使局部截断误差(7.10)与 $h^p+1$ 同阶，则相应的 $N$ 级R-K方法就是 $p$ 阶方法。

希望：$N$ 确定时选择一组系数 $c_i,a_i,b_{ij}$，使阶数 $p$ 达到最高

改进的Euler法

取 $c_1=c_2=\frac12,a_2=1$，式(7.14)成为

$$\begin{cases}y_{n+1}=y_n+\frac h2(k_1+k_2)\\k_1=f(t_n,y_n)\\k_2=f(t_n+h,y_n+hk_1)\end{cases}\tag{7.19}$$

方法(7.19)又称为改进的Euler法。

中点公式

取 $c_1=0,c_2=1,a_2=\frac12$ ，则式(7.14)成为

$$\begin{cases}y_{n+1}=y_n+hk,\\k_1=f(t_n,y_n)\\k_2=f(t_n+\frac12h,y_n+\frac12hk_1)\end{cases}\tag{7.20}$$

式(7.20)又称为中点公式。

Heun(休恩)公式

取 $c_1=\frac14,c_2=\frac34,a_2=\frac23$，则式(7.14)成为

$$\begin{aligned}&\begin{cases}y_{n+1}=y_n+\dfrac{h}{4}(k_1+3k_2)\\k_1=f(t_n,y_n)\\k_2=f(t_n+\dfrac{2}{3}h,y_n+\dfrac{2}{3}hk_1)\end{cases}\end{aligned}\tag{7.21}$$

式(7.21)又称为Heun(休恩)公式。

相容性、收敛性和绝对稳定性

$$ e_n=y_n-\tilde{y}_n\\ \begin{align} e_{n+1}&=y_{n+1}-\tilde{y}_{n+1}\\ &=(1+h\lambda)(y_n-\tilde{y}_n)\\ &=(1+h\lambda)e_n \end{align} $$ 当且仅当 $|1+h\lambda|<1$ 时有 $\lim_{n\to\infty} e_n=0$。所以，Euler法(7.13)的绝对稳定区域为

$$|1+h\lambda|<1$$

当 $\lambda$ 为实数时，Euler法的绝对稳定区间 $-2<h\lambda<0$

步长选择