在讨论收敛性之前，先介绍 局部截断误差,整体截断误差 的定义及其他们之间的关系
8.1.3 单步法的收敛性和稳定性
(Convergency and Stability)
一、单步法的收敛性求解初值问题
0
(,),
()
y f x y a x b
y a y
的一般显式单步法可以写成如下形式：
1、局部截断误差
1
1
(,,),
( ) [ ( ) (,( ),) ]
i i i i
i i i i
y y h x y h
y x y x h x y x h
i+1
对于数值方法局部截断误差定义为:
e
定义 在假设 yi = y(xi),即第 i 步计算是精确的前提下,
考虑的截断误差 Ri = y(xi+1)? yi+1 称为 局部截断误差
/* local truncation error */。
假定,yi = y(xi)”称为 局部化假定
2、整体截断误差
1
1 1 1 1
(,,)
( ) ( ) [ (,,) ],
i i i i
i i i i i i i
y y h x y h
E y x y y x y h x y h
对 于 数 值 方 法
=
其 整 体 截 断 误 差 定 义 为
1
1
1
1
( ) ( )
10
8.1.4,( )
0
(,,) (,,),,.
[ 1 ],
p
i
p
i
p
L b a L b a
i
e O h
e M h L
x y h x y h L y y y y R
Mh
E e E e
L
若 单 步 法 (35) 的 局 部 截 断 误 差截 断 误 差 满 足定 理
( 即 ),且 使 得则 (35) 的 整 体
3、局部截断误差与整体截断误差的关系
1 1,
1 1 1
1
1
1
( ) ( ) (,( ),)
()
( ) [ (,( ),) (,,) ],
( 1 )
i i i i i
i i i
i i i i i i i
p
ii
y x y x h x y x h e
E y x y
y x y h x y x h x y h e
E hL E M h
证,
与 (35) 相 减 得 到再利用引理 1就可得到结论：若单步法的局部截断误差为 O（ hP+1)
整体截断误差为 O（ hP)
条件：满足 Lipschitz条件定义 若某算法对于任意固定的 x = xi = x0 + i h,当
h?0 ( 同时 i) 时有 yi? y( xi),则称该算法是 收敛 的 。
单步法的收敛性定义结论 1：收敛 整体截断误差 Ei 0
结论 2：只要单步法 (35)式是高于零阶的方法，
判断单步法 (35)式的收敛性就归结为验证其增量函数?(x,y,h)是否满足对 y的 Lipschitz条件例 5 Euler方法是收敛的,
证明,由于 Euler方法是一阶方法，且其增量函数?(x,y,h) =f (x,y),而初值问题是要求函数 f (x,y)对 y满足 Lipschitz条件的，
故 Euler方法收敛,
例 6 改进 Euler方法是收敛的,
证明 改进 Euler方法是二阶方法，其增量函数为
下面证明，当 f (x,y)满足对 y的 Lipschitz条件时,(42)
式中的?(x,y,h)也满足对 y的 Lipschitz条件,
由 (42)式有
假定 h? h0(h0为定数 )，并记,则有
即?(x,y,h)满足对 y的 Lipschitz条件，故改进的
Euler方法是收敛的,
二、单步法的稳定性上面讨论单步法的收敛性，是假定 (35)式的每一步计算都是准确的，即不考虑计算中的舍入误差．然而这一假定是不切合实际的，用 (35)式进行实际数值计算时，
每一步都不可避免地含有舍入误差稳定性就是讨论计算过程中的舍入误差对最终结果的影响！
定义 4如果一种数值方法在节点 xi的值 y i有大小为?i的扰动，而由这个扰动引起以后各节点上值 y i (j >i )的偏差?j均满足 |?j | ≤ |?i |,
则称该数值方法是 绝对稳定的,
考虑一般的单步法 (35)式．
若值 y i有一个扰动?i，那么用 (35)式计算，得到的值
yi+1就会产生一个偏差?i+1,若记则可将 yi+1视为单步法公式的准确结果用 (43)式减去 (35)式，得或由此可知，单步法 (35)式绝对稳定的条件是由于增量函数?与微分方程的右端 f 有关，从而给考察单步法的稳定性带来了困难．为了简化讨论，通常是用试验方程
y’ =? y
(? 为复常数 )来检验数值方法的稳定性！
（ 1）首先考察 Euler方法的稳定性,
此时增量函数?(x,y,h) =f (x,y)=y,因而有因此对于试验方程 (46),Euler方法稳定的条件是
|1 +?|? 1 (47)
由于?可以是复数，故在 h的平面上,(47)式表示以点 -1为中心的单位圆及其内部区域．这个区域称为 Euler方法的绝对稳定区域,
（ 2）讨论改进 Euler方法的稳定性,此时增量函数改进 Euler方法的稳定性条件为
（ 3）经典 Runge-Kutta方法的稳定性,
此时增量函数代入后得于是有由此得出经典 Runge-Kutta方法的稳定性条件为如果仅限于讨论?是实数的情形，则上述几个单步法的稳定性条件可分别简化为
Euler法稳定性条件,?2 h? 0，
改进 Euler法稳定性条件,?2 h? 0，
经典 Runge-Kutta法稳定性条件,?2.785 h? 0.
由上面的讨论可以看到，如果方法的绝对稳定区域或区间是有限的，那么，步长 h的选取要受绝对稳定性的约束,
例 7 对初值问题取 h = 0.1和 0.2，用经典 Runge-Kutta方法求解,
解 本例中? =?20,?h分别为 -2和 -4．前者属绝对稳定区间 [-2.785,0]，后者不属此区间．问题的准确解为 y =e?20x,计算结果误差见表 8-6
隐式单步法的稳定性讨论,
（ 1）考察向后 Euler方法,
对于试验方程 (46)，其向后 Euler法的公式为
yi+1 = y i + h? yi+1
解出 yi+1,有,从而得到误差 (扰动 )
公式为由此得到绝对稳定的条件为其绝对稳定区域是以 1为半径、以 1为中心的圆外部，如图 8-5所示,
（ 2）讨论梯形法的稳定性．
对于试验方程 (46)，相应的梯形法公式为解出 yi+1,有由此得出绝对稳定的条件为其绝对稳定区域为 Re (h?)? 0 的整个复平面．
当?为实数时，其绝对稳定区间为 <? h? 0.
从以上的分析讨论可以看到，隐式方法的稳定性比显式方法好，这也是隐式方法的主要优点！
8.1.4 线性多步法
求解初值问题的数值方法都是“步进式”的，即求解过程从初值 y0开始，顺着节点的排列次序，一步一步地向前推进．所以，在计算 yi+1 时，前面的 i + 1 个值 y0,
y1,?,y i 都是已知的．如果在计算 yi+1 时能充分利用这些已有的信息，而不是像单步法中那样，只用其前一步的值 y i,则可望构造出精度高，但计算量小的求解公式．线性多步法就是基于这一思想发展起来的，其计算公式可表示为
其中，,而?j,?j 都是常数,
线性多步法 (50)式的实质是用若干节点处的函数值及导数值的线性组合来逼近 y(xi+1)的值．由于在计算 yi+1时需要用到其前 k + 1个值,y i,yi?1,yi?2,?,y i?k,故多步法 (50)式又称为 k + 1步法，且当1 = 0时，此 k + 1步法是显式的，而在1?0时，此 k + 1步法是隐式的,
原则上，一切形如 (50)式的多步法都可用 Taylor级数展开的方法来导出 (即确定其中的系数?j,?j ),但有些多步法也可用数值积分法来构造．下面讨论实际中较为常用的几种线性多步法,
一,Adams外插法
1．公式的推导
对方程 y0 = f (x,y)的两边从 xi到 xi+1积分，得
为了近似计算 (51)式中的积分，我们以 xi?k,xi?k+1,?,xi?1,
xi 为插值节点，作函数 f (x,y (x)) 的 k 次插值多项式 p k
(x),从而有
f (x,y (x) ) = p k (x) + R (x),
其中,R (x)为插值余项．将上式代入 (51)式，得
略去积分余项 R (x) d x,并用 y i代替 y (xi ),可得到计算公略去积分余项 R (x) d x,并用 y i代替 y (xi ),可得到计算公式
注意，这里的 与 p k (x)不同，它是将插值多项式 p k (x)中用到的函数值 f (xi,y (xi ))均以近似值 f i = f
(xi,y i )代替后所得到的表达式,
由于 (52)式的积分是在区间 [xi,xi+1]上进行的，而
的插值区间却为 [xi?k,xi],即插值点 x? [xi,xi+1]，
位于插值区间之外，故称 (53)式为外插公式,
考虑到插值点 x靠近区间 [xi?k,xi ]的最后一个节点 xi，
我们采用 Newton向后插值公式，于是有
其中,而 ▽ 为向后差分算子,即,
等,
将 (54)式代入 (53)式并作变量代换，得
其中
(55)式称为 Adams外插公式 (亦有称 Adams-Bashforth公式 )．不难看出，这是一类 k + 1步显式方法,
由 (56)式容易计算出 b j,它的前几个值见表 8-7.
2,Adams外插公式的局部截断误差
注意到，若假定 y i?j = y (xi?j ),j = 0,1,?,k精确成立，
则有,因此,Adams外插公式 (55)的局部截断误差为
其中
而?i是介于 xi?k与 xi+1之间的某个值,
由 (57)式可知,Adams外插公式 (55)是一类 k + 1步 k
+1阶的显式方法,
几个常用的 Adams外插公式如下：
① 单步法 (k=0)
② 二步法 (k=1)
③ 三步法 (k=2)
④ 四步法 (k=3)
二,Adams内插法
现在以 k +2个节点 x?k,xi?k+1,?,xi,xi+1作为插值节点，作函数 f (x,y (x) )的 k + 1次插值多项式 pk+1(x),从而有
其中 R (x)为插值余项．去掉上式中的积分余项，得
同样，采用 Newton向后插值公式，并重复 Adams外插公式的推导过程，可得
其中
表 8-8列出了 d j的前几个值,
由于插值点 x 现在是落在积分区间 [xi,xi+1]之内，所以称公式 (60)为 Adams内插公式 (亦称 Adams-Moutton公式 )．容易看出，这是一类 k + 1步隐式方法,
由 (59)式可知，公式 (60)的局部截断误差为
其中
而?i是介于 xi?k与 xi+1之间的某个值．所以,Adams内插公式 (60)是一类 k + 1步 k + 2阶的隐式方法,
几个常用的 Adams内插值公式如下：
① 单步法 (k=0)
② 二步法 (k=1)
③ 三步法 (k=2)
从上面所列的公式可以看到，步数相同的 Adams内插公式比外插公式在精度上要高一阶，而阶数相同的内插公式的截断误差也比外插值公式的截断误差小许多，这是内插法的优点．但内插法是隐式的，求解用迭代法，因而计算量较大，这是它的缺点,
例 8 对初值问题
分别用四步四阶 Adams外插法和三步四阶 Adams内插法求解,
解取步长 h = 0.1,即 N = 10.
四步四阶 Adams外插法的公式为
将 f (x,y) = 2x + y,h = 0.1,xi = 0.1i 代入，得
三步四阶 Adams内插法的公式为
将 f (x,y) = 2x + y,h = 0.1,xi = 0.1i 代入，得
本例可以解出 yi+1 使其成为显式
本例的精确解为 y (x) = 3ex?2x?2,利用此精确解求出 y1 = y(x1),y2 = y(x2),y3 = y(x3),并用 y0,y1,y2,y3 作为上述外插公式的起步值，计算结果见表 8-9.
从表 8-9可以看到,Adams内插法比同阶的外插法精确,
8.1.3 单步法的收敛性和稳定性
(Convergency and Stability)
一、单步法的收敛性求解初值问题
0
(,),
()
y f x y a x b
y a y
的一般显式单步法可以写成如下形式：
1、局部截断误差
1
1
(,,),
( ) [ ( ) (,( ),) ]
i i i i
i i i i
y y h x y h
y x y x h x y x h
i+1
对于数值方法局部截断误差定义为:
e
定义 在假设 yi = y(xi),即第 i 步计算是精确的前提下,
考虑的截断误差 Ri = y(xi+1)? yi+1 称为 局部截断误差
/* local truncation error */。
假定,yi = y(xi)”称为 局部化假定
2、整体截断误差
1
1 1 1 1
(,,)
( ) ( ) [ (,,) ],
i i i i
i i i i i i i
y y h x y h
E y x y y x y h x y h
对 于 数 值 方 法
=
其 整 体 截 断 误 差 定 义 为
1
1
1
1
( ) ( )
10
8.1.4,( )
0
(,,) (,,),,.
[ 1 ],
p
i
p
i
p
L b a L b a
i
e O h
e M h L
x y h x y h L y y y y R
Mh
E e E e
L
若 单 步 法 (35) 的 局 部 截 断 误 差截 断 误 差 满 足定 理
( 即 ),且 使 得则 (35) 的 整 体
3、局部截断误差与整体截断误差的关系
1 1,
1 1 1
1
1
1
( ) ( ) (,( ),)
()
( ) [ (,( ),) (,,) ],
( 1 )
i i i i i
i i i
i i i i i i i
p
ii
y x y x h x y x h e
E y x y
y x y h x y x h x y h e
E hL E M h
证,
与 (35) 相 减 得 到再利用引理 1就可得到结论：若单步法的局部截断误差为 O（ hP+1)
整体截断误差为 O（ hP)
条件：满足 Lipschitz条件定义 若某算法对于任意固定的 x = xi = x0 + i h,当
h?0 ( 同时 i) 时有 yi? y( xi),则称该算法是 收敛 的 。
单步法的收敛性定义结论 1：收敛 整体截断误差 Ei 0
结论 2：只要单步法 (35)式是高于零阶的方法，
判断单步法 (35)式的收敛性就归结为验证其增量函数?(x,y,h)是否满足对 y的 Lipschitz条件例 5 Euler方法是收敛的,
证明,由于 Euler方法是一阶方法，且其增量函数?(x,y,h) =f (x,y),而初值问题是要求函数 f (x,y)对 y满足 Lipschitz条件的，
故 Euler方法收敛,
例 6 改进 Euler方法是收敛的,
证明 改进 Euler方法是二阶方法，其增量函数为
下面证明，当 f (x,y)满足对 y的 Lipschitz条件时,(42)
式中的?(x,y,h)也满足对 y的 Lipschitz条件,
由 (42)式有
假定 h? h0(h0为定数 )，并记,则有
即?(x,y,h)满足对 y的 Lipschitz条件，故改进的
Euler方法是收敛的,
二、单步法的稳定性上面讨论单步法的收敛性，是假定 (35)式的每一步计算都是准确的，即不考虑计算中的舍入误差．然而这一假定是不切合实际的，用 (35)式进行实际数值计算时，
每一步都不可避免地含有舍入误差稳定性就是讨论计算过程中的舍入误差对最终结果的影响！
定义 4如果一种数值方法在节点 xi的值 y i有大小为?i的扰动，而由这个扰动引起以后各节点上值 y i (j >i )的偏差?j均满足 |?j | ≤ |?i |,
则称该数值方法是 绝对稳定的,
考虑一般的单步法 (35)式．
若值 y i有一个扰动?i，那么用 (35)式计算，得到的值
yi+1就会产生一个偏差?i+1,若记则可将 yi+1视为单步法公式的准确结果用 (43)式减去 (35)式，得或由此可知，单步法 (35)式绝对稳定的条件是由于增量函数?与微分方程的右端 f 有关，从而给考察单步法的稳定性带来了困难．为了简化讨论，通常是用试验方程
y’ =? y
(? 为复常数 )来检验数值方法的稳定性！
（ 1）首先考察 Euler方法的稳定性,
此时增量函数?(x,y,h) =f (x,y)=y,因而有因此对于试验方程 (46),Euler方法稳定的条件是
|1 +?|? 1 (47)
由于?可以是复数，故在 h的平面上,(47)式表示以点 -1为中心的单位圆及其内部区域．这个区域称为 Euler方法的绝对稳定区域,
（ 2）讨论改进 Euler方法的稳定性,此时增量函数改进 Euler方法的稳定性条件为
（ 3）经典 Runge-Kutta方法的稳定性,
此时增量函数代入后得于是有由此得出经典 Runge-Kutta方法的稳定性条件为如果仅限于讨论?是实数的情形，则上述几个单步法的稳定性条件可分别简化为
Euler法稳定性条件,?2 h? 0，
改进 Euler法稳定性条件,?2 h? 0，
经典 Runge-Kutta法稳定性条件,?2.785 h? 0.
由上面的讨论可以看到，如果方法的绝对稳定区域或区间是有限的，那么，步长 h的选取要受绝对稳定性的约束,
例 7 对初值问题取 h = 0.1和 0.2，用经典 Runge-Kutta方法求解,
解 本例中? =?20,?h分别为 -2和 -4．前者属绝对稳定区间 [-2.785,0]，后者不属此区间．问题的准确解为 y =e?20x,计算结果误差见表 8-6
隐式单步法的稳定性讨论,
（ 1）考察向后 Euler方法,
对于试验方程 (46)，其向后 Euler法的公式为
yi+1 = y i + h? yi+1
解出 yi+1,有,从而得到误差 (扰动 )
公式为由此得到绝对稳定的条件为其绝对稳定区域是以 1为半径、以 1为中心的圆外部，如图 8-5所示,
（ 2）讨论梯形法的稳定性．
对于试验方程 (46)，相应的梯形法公式为解出 yi+1,有由此得出绝对稳定的条件为其绝对稳定区域为 Re (h?)? 0 的整个复平面．
当?为实数时，其绝对稳定区间为 <? h? 0.
从以上的分析讨论可以看到，隐式方法的稳定性比显式方法好，这也是隐式方法的主要优点！
8.1.4 线性多步法
求解初值问题的数值方法都是“步进式”的，即求解过程从初值 y0开始，顺着节点的排列次序，一步一步地向前推进．所以，在计算 yi+1 时，前面的 i + 1 个值 y0,
y1,?,y i 都是已知的．如果在计算 yi+1 时能充分利用这些已有的信息，而不是像单步法中那样，只用其前一步的值 y i,则可望构造出精度高，但计算量小的求解公式．线性多步法就是基于这一思想发展起来的，其计算公式可表示为
其中，,而?j,?j 都是常数,
线性多步法 (50)式的实质是用若干节点处的函数值及导数值的线性组合来逼近 y(xi+1)的值．由于在计算 yi+1时需要用到其前 k + 1个值,y i,yi?1,yi?2,?,y i?k,故多步法 (50)式又称为 k + 1步法，且当1 = 0时，此 k + 1步法是显式的，而在1?0时，此 k + 1步法是隐式的,
原则上，一切形如 (50)式的多步法都可用 Taylor级数展开的方法来导出 (即确定其中的系数?j,?j ),但有些多步法也可用数值积分法来构造．下面讨论实际中较为常用的几种线性多步法,
一,Adams外插法
1．公式的推导
对方程 y0 = f (x,y)的两边从 xi到 xi+1积分，得
为了近似计算 (51)式中的积分，我们以 xi?k,xi?k+1,?,xi?1,
xi 为插值节点，作函数 f (x,y (x)) 的 k 次插值多项式 p k
(x),从而有
f (x,y (x) ) = p k (x) + R (x),
其中,R (x)为插值余项．将上式代入 (51)式，得
略去积分余项 R (x) d x,并用 y i代替 y (xi ),可得到计算公略去积分余项 R (x) d x,并用 y i代替 y (xi ),可得到计算公式
注意，这里的 与 p k (x)不同，它是将插值多项式 p k (x)中用到的函数值 f (xi,y (xi ))均以近似值 f i = f
(xi,y i )代替后所得到的表达式,
由于 (52)式的积分是在区间 [xi,xi+1]上进行的，而
的插值区间却为 [xi?k,xi],即插值点 x? [xi,xi+1]，
位于插值区间之外，故称 (53)式为外插公式,
考虑到插值点 x靠近区间 [xi?k,xi ]的最后一个节点 xi，
我们采用 Newton向后插值公式，于是有
其中,而 ▽ 为向后差分算子,即,
等,
将 (54)式代入 (53)式并作变量代换，得
其中
(55)式称为 Adams外插公式 (亦有称 Adams-Bashforth公式 )．不难看出，这是一类 k + 1步显式方法,
由 (56)式容易计算出 b j,它的前几个值见表 8-7.
2,Adams外插公式的局部截断误差
注意到，若假定 y i?j = y (xi?j ),j = 0,1,?,k精确成立，
则有,因此,Adams外插公式 (55)的局部截断误差为
其中
而?i是介于 xi?k与 xi+1之间的某个值,
由 (57)式可知,Adams外插公式 (55)是一类 k + 1步 k
+1阶的显式方法,
几个常用的 Adams外插公式如下：
① 单步法 (k=0)
② 二步法 (k=1)
③ 三步法 (k=2)
④ 四步法 (k=3)
二,Adams内插法
现在以 k +2个节点 x?k,xi?k+1,?,xi,xi+1作为插值节点，作函数 f (x,y (x) )的 k + 1次插值多项式 pk+1(x),从而有
其中 R (x)为插值余项．去掉上式中的积分余项，得
同样，采用 Newton向后插值公式，并重复 Adams外插公式的推导过程，可得
其中
表 8-8列出了 d j的前几个值,
由于插值点 x 现在是落在积分区间 [xi,xi+1]之内，所以称公式 (60)为 Adams内插公式 (亦称 Adams-Moutton公式 )．容易看出，这是一类 k + 1步隐式方法,
由 (59)式可知，公式 (60)的局部截断误差为
其中
而?i是介于 xi?k与 xi+1之间的某个值．所以,Adams内插公式 (60)是一类 k + 1步 k + 2阶的隐式方法,
几个常用的 Adams内插值公式如下：
① 单步法 (k=0)
② 二步法 (k=1)
③ 三步法 (k=2)
从上面所列的公式可以看到，步数相同的 Adams内插公式比外插公式在精度上要高一阶，而阶数相同的内插公式的截断误差也比外插值公式的截断误差小许多，这是内插法的优点．但内插法是隐式的，求解用迭代法，因而计算量较大，这是它的缺点,
例 8 对初值问题
分别用四步四阶 Adams外插法和三步四阶 Adams内插法求解,
解取步长 h = 0.1,即 N = 10.
四步四阶 Adams外插法的公式为
将 f (x,y) = 2x + y,h = 0.1,xi = 0.1i 代入，得
三步四阶 Adams内插法的公式为
将 f (x,y) = 2x + y,h = 0.1,xi = 0.1i 代入，得
本例可以解出 yi+1 使其成为显式
本例的精确解为 y (x) = 3ex?2x?2,利用此精确解求出 y1 = y(x1),y2 = y(x2),y3 = y(x3),并用 y0,y1,y2,y3 作为上述外插公式的起步值，计算结果见表 8-9.
从表 8-9可以看到,Adams内插法比同阶的外插法精确,
