主讲：
西北工业大学网络教育学院主讲：
西北工业大学网络教育学院主讲：
西北工业大学网络教育学院第一章 绪论第二章 求方程根的近似方法第三章 线性代的方程组解法第四章 矩阵特征值和特征向量计算第五章 插值法计算方法
§ 1.1计算方法的任务与特点第一章,绪论实际问题 数学问题 提供计算方法程序设计 上机计算 结果分析计算方法基本的数学问题,
1.大型线性代数方程组 Ax=b求解 ;
2.矩阵 A的特征值和特征向量计算 ;
3.非线性方程 求解 (求根 );
4.积分 计算 ;
5.常微分方程初值问题求解 ;
6.其它。
0)(?xf
dxxfba? )(
求精确解 (值 )一般非常困难。例如：
1,方程组阶数 n很大，例如 n=20,计算机运算速度
1亿次 /秒,用不好的方法,大约需算 30多万年 ;
好方法不到一分钟。另外，有计算结果可靠性问题。
2,特征值定义
)0( xxAx?
0 xAx 0)( xIA
0|| IA?
3,形式复杂时求根和求积分很困难。
4.线性微分方程易解,如非线性方程难解，如
)( xf
12 '" yyy 1)0()0( ' yy
1s i n 2" yyye y 1)0()0( ' yy
希 望,求近似解，但方法简单可行，行之有效
（计算量小，误差小等）。以计算机为工具，易在计算机上实现。
计算机运算,只能进行加，减，乘，除等算术运算和一些逻辑运算。
计算方法,把求解数学问题转化为按一定次序只进行加，减，乘，除等基本运算 ——
数值方法。
§ 1.2 误差基础知识
,..,,.,
!5!3
s i n
53
xxxx
..,.,.
!5
)
!3
(s in
53
xxxx
一,误差来源（分类）
1,模型误差。
2,观测误差。
3,截断误差，如右端是截断误差。
4,舍入误差。计算机字长有限，一般实数不能精确存储，于是产生舍入误差。例如：在 10位十进制数限制下：
舍入误差很小，本课程将研究它在运算过程中是否能有效控制。
3333333333.031 ）本应?33 3 3 3 3 3 3 3 3 3.031(
00 0 0 0 0 4.1)0 0 0 0 0 2.1( 2
）
）本应（
12
2
10404000 000 000 0.0
000 004.104000 004 000 0.1
000 004.1000 002.1(
二．误差基本概念
1．绝对误差。设 —— 准确值,—— 近似值。
称 为 的绝对误差。
为 的绝对误差限。
2,相对误差 。 称 为 的相对误差 。
实用中,常用 表示 的相对误差 。
称 为 的相对误差限 。
x *x
** )( xxxe
|)(| *xe
*x
*x
x
xx
r
ee *)(*)(? *x
*
*)(
x
xe
rxre*)(
*x
*x
3,有效数字设若 (1.1)
则说 具有 n位有效数字,分别是若,则称 为有效数 。
)21.0(10* pnm aaaax ),0( 1 pa
nmxx 10
2
1*
*x
naaa,,,21
pn? *x
例 1.1
设 =0.0270是某数 经,四舍五入,所得,
则误差 不超过 末位的半个单位,即：
又,故该不等式又可写为由有效数字定义可知,有 3位有效数字,分别是 2,7,0。
*x
*)(xe *x
410
2
1* xx
)270.0(10* 1x
3110
2
1* xx
*x
x
例 1.2
= 32.93,= 32.89,
故 有 3位有效数字,分别是 3,2,8。
由于 中的数字 9不是有效数字,故 不是有效数 。
x
110
2
105.004.0* xx
3210
2
1* xx
*x*x
*x
*x
三,有效数位与误差的关系
1,有效数位 n越多，则绝对误差 越小
(由定义 1.1)
2,定理 1.1 若近似数 具有 n位有效数字,则
(1.2)
反之,若 则至少有 n位有效数字 。
*)( xe
n
r axe
1
*)( 102 1
1
n
r axe
1
1
*)( 102 1
1
*x
*x
两边除以 得
(1.3)和（ 1.4）给出了由自变量的误差引起的函数值的误差的近似式（误差传播）。
四,数值运算的误差估计
1,一元函数情形设 则,由 Taylor展开公式),( xfy?
*)* ) ((*)()(**)( xxxfxfxfyyye
*)(*)(*)( xexfye
*)(**)( *)('*)( xrxxf xfyr ee?
)( ** xfy?
(1.4)
*)(*)( *)('* *)(*)(
* xeee
rxf
xfx
y
yy
r
)( ** xfy?
（ 1.3）
2,多元函数情形设,),,,(
21 nxxxfy *),*,*,(* 21 nxxxfy
*)(*),*,*,(*)( 21
1
in
n
i
i xexxxfye
*)(**),*,*,( *),*,*,(*)(
21
21
1
iri
n
ni
n
i
r xexxxxf xxxfye
2121 ),( xxxxf
2
1
21,x
xxx
)(21)21( *** m ax irir xexxe
21,xx
)2()1()21( **** xexexxe rrr
)( *2)1()2()1()*
2
*
1( *** xexexexe
x
xe
rrrrr
则，
由多元函数的 Taylor展开公式类似可得
（ 1.5）
（ 1.6）
在（ 1.6）式中，分别取,可得同号 ) （ 1.7）
（ 1.8）
（ 1.9）
(
,
例 1.3,测得某桌面的长 a的近似值 a*=120cm,宽 b的近似值 b*=60cm。若已知 |e(a*)|≤0.2cm,
|e(b*)|≤0.1cm 。 试求近似面积 s*=a*b*
的绝对误差限与相对误差限。
2
241.01 2 02.060
|*)(||*||*)(||*||*)(|
*)(**)(*
*)(
*)*,(
*)(
*)*,(
*)(
cm
beaaebse
beaaeb
be
b
bas
ae
a
bas
se
解,面积 s=ab,在公式（ 1.5）中,将换为 s=ab,则
),( 21 xxfy?
相对误差限为 %33.0
601 2 0
24|
*
*)(||*)(|?
s
sese
r
§ 1.3 选用算法应遵循的原则
1.尽量简化计算步骤，减少乘除运算的次数,
例如，计算多项式通常运算的乘法次数为若采用递推算法,
则乘法次数仅为 n,又如
nnn xaxaaxp,...,.)( 10
2
)1(.,,,,,21 nnn
0
1
)(
)0121(
uxp
,,,,n-n-kaxuu
au
n
kkk
nn
1 0 0 1
11)
1
11(
)1(
11 0 0 0
1
1 0 0 0
1
n n nnnn
2.防止大数,吃掉,小数当 |a|>>|b|时，尽量避免 a+b 。例如，假设计算机只能存放 10位尾数的十进制数，则
3.尽量避免相近数相减例如，当 x很大时，应
8998 1040 0 0 0 0 0 0 0 0 0.0101.01004.010
1
11
xxxx
)1(
1
1
11
xxxx
，
2c o s1
s i n
s i n
c o s1 xtg
x
x
x
x 或
当 x接近于 0时，应
4.避免绝对值很小的数做分母当 |b|<<|a|时，应尽量避免 。
5,选用数值稳定性好的算法，以控制舍入误差高速增长例如若 （误差 ）则计算时误差扩大了 倍,而
b
a
n
n
n Indxx
xI 51
5
1
0
1823.056ln0I 41021 100I
1005
)1(511 nn InI
（ n=1,2,… ）
是稳定的。
基本要求：
1.熟悉计算方法在解决实际问题中所处的地位，熟悉计算方法是以计算机为工具求近似解的数值方法；
2.熟悉绝对误差（限），相对误差（限）及有效数字概念；
3.熟悉公式（ 1.2） --（ 1.9）；
4.熟悉选用算法应遵循的原则；
作业：
作业集（ A）第一章
1,2,3,4,5,6,7,8
计算方法
f(x)=0根或 f(x)零点，当 f(x)复杂时，很难求
（找近似有效简单方法）。
第二章 求方程根的近似方法
§ 2.1 区间二分法理 论,f(x) ∈ C[a,b],单调,f(a)f(b)<0
f(x)=0在 (a,b)有惟一根。
根分离：画草图，试算,多项式方程根的模的上下界。
例 2.1 用二分法求在 (1,2)内的根，要求绝对误差不超过解,
f(1)=-5<0 有根区间 中点
f(2)=14>0 -(1,2)+
f(1.25)<0 (1.25,1.5)
f(1.375)>0 (1.25,1.375)
f(1.313)<0 (1.313,1.375)
f(1.344)<0 (1.344,1.375)
f(1.360)<0 (1.360,1.375)
f(1.368)>0 (1.360,1.368)
0104 23 xx
210
2
1
f(1.5)>0 (1,1.5)
nx
1.51?x
3 6 4.1
3 6 8.1
3 6 0.1
3 4 4.1
3 1 3.1
3 7 5.1
25.1
8
7
6
5
4
3
2
x
x
x
x
x
x
x
364.18* xx若取近似根
2* 10
2
10 0 4.0)3 6 0.13 6 8.1(
2
1|| xx
81,10212|| 21* nabxx n 解出对分次数先验估计：
优点：条件简单,
缺点：收敛慢,
不易求偶数重根,
如图
,则
（ 事后估计 ）
x
y
§ 2.2 迭代法连续），，改写建立 fxxxf ()( 0)(:.1
0
1
,.,,)2,1,0( )(
x
nxx nn
取定初值
，则若收敛，设极限为则产生数列
..,,,,.,.,,121?nn xxxx
一,迭代法的建立与收敛性
)( )(lim1lim nnnn xx
可作为近似值充分大时之根，故当是即 1,0)( nxnxf?
)2l g (2100210
)(
xxxx
x
xx 或形式不唯一，如：问题,?
收敛性不同。计算结果见表取取
4.2
3 )2l g (
3 210
01
01
xxx
xx
nn
x
n
n
2.收敛定理（定理 2.2）
],[)( bax 在设?
为常数）LLxbax (1|)('|],,[)2(
01
10
1
||3
(],,[2
],[)(1
xx
L
L
x
xxbax
baxx
n
n
nn
）（
）收敛到）（；有唯一根在）方程则：（;)(1 bxabxa时，）当（
,
)(,0)('1)('
,0)(
],,[
,0)()(,0)()(
),()(( 1 )
唯一故根递增，又使故至少有则设证：
xgxxg
g
ba
bbbgaaag
xxxg
(2)
1nx
，故收敛。
)(
00112
时当
n
xLxL nn
中值定理
n
nnnn
xL
xxx ))((')()(1
(＊ )1
－－
）式（由（＊）
（＊）
－
式）由（＊）
（＊） 中值定理
011
2
1
111
11
11
11
2
3
1
1
)1(
1 (
)()(
2))(('
)()(
xx
L
L
xx
L
L
xx
L
x
xLxLx
xxxxxx
xxLxx
xxxx
n
nn
nnn
nnn
nnnnnn
nnnnn
nnnn
(3)
注,L越小，收敛越快。
3．编程停机判断
)(1 nn xx （取定初值
0x
）计算，当
nn xx 1
时，由（＊） 3 式知
L1 1－nx
比较小，此时停机,1n x?
二、迭代加速公式（略）
由
§ 2.3 Newton 迭代法一 Newton 迭代法
1.迭代公式建立
)(xf 在
nx
点 Taylor展开
)()(')()(
)(
!2
)(
)()(')()( 2
nnn
n
n
nnn
xxxfxfxf
xx
xf
xxxfxfxf
—— Taylor展开线性化（重要思想）
0)(?xf 近似于 0)()(')( nnn xxxfxf
解出 记为
1?nx
，则
)1.2(),2,1,0(
)('
)(
1 nxf
xfxx
n
n
nn
1?nx
将
x
2.Newton迭代法的几何意义过 ))(,(
nn xfx
切线
)()(')( nnn xxxfxfy
与 0?y 求交点，解出
1 nxx
,则
)('
)(
1
n
n
nn xf
xfxx
3,Newton迭代法收敛定理（定理 2.6）
0)(?xf 在ba,有根 α,且 )(xf 在ba,
（ 1） )("),(' xfxf 连续，且分别不变号；
bax,0?,使则 Newton 迭代法（ 2.1）产生的数列
1?nx
的收敛到根 α 。
0)(,0)(",0)(' 0 xfxfxf
为例证明（其它情况类似）
（ 2） 取初值设
0)(")( 00?xfxf
证,以将 在)(?f
nx
处 Taylor展开
1
2
1
2
2
)(
)('2
)("
)(
)('2
)("
)('
)(
0)(
!2
)("
))((')()(
nn
n
n
nn
n
n
n
n
n
n
n
nnn
xx
xf
f
xx
xf
f
xf
xf
x
x
f
xxfxff
说明数列
1?nx
有下界 α
又
n
n
n
nn xxf
xfxx
)('
)(
1
故
1?nx
单调递减。
1 nx 收敛。设 xx nn 1l i m
则由（ 2.1），
xxf
xf
xfxx,0)(,
)('
)(
，
例 2.2
解：设,0,2 cxcx 则取 cxxf 2)(,则由（ 2.1）
)(
2
1
2
2
1
n
n
n
n
nn
x
c
x
x
cx
xx
)0(?cc
用 Newton 迭代法求基本要求
1.熟悉区间＝分法；
2.熟悉迭代法的建立，会使用收敛定理；
3.熟悉 Newton迭代法及其几何意义和收敛条件。
作业：
作业集（ B）第二章
1,2,3,4,6
计算方法二,迭代法的收敛阶 (收敛速度 )
1.定义,设,lim
nn
x 若有实数 p>0,使
)0(
||
||
l i m 1
cc
x
x
p
n
n
n?
则称 xn p阶收敛,相应的迭代法称为 p阶方法,
特别,p=1时叫线性收敛,
p=2时叫平方收敛,
p越大越好 (why?)
2.定理 2.7
线性收敛；则（且）（若
。的根收敛到设
)(,0)
)(),2,1,0()( (1 )
1
1
1
xx
xx
nn
nn
cx
xxn
至少二阶收敛。（即的单根迭代法求则
)0)('
0)(
f
xfN e w t o n
的条件成立）设定理（ 6.22
所以，此时 Newton法至少二阶收敛,
线性收敛
） 证：（
)(
0)('
))((')()(1
1
'
1
1
1
nn
n
n
n
nnnn
xx
a
x
x
xxx
(2)由 2.6的证明有：
故,)()('2 )(" 21 n
n
n
n xxf
fx
)('2
)("
)('2
)("
2
1
f
f
xf
f
x
x
n
n
n
n
0)(")(0
0)(")(0
f
f
若大于二阶收敛若二阶收敛
3,Newton法改进：
则重根有设 )2(0)( mmxf
§ 2.4 弦截法 —— (略 )
)('
)(
1 x
xxx
n
n
nn f
fm
。收敛时至少是二阶收敛第三章 线性代数方程组解法解线性方程组 bAx?
x解向量列迭代法：格式，无穷序误差，有限步，精确解直接法：理论，无舍入
一,Gauss 消去法设 有
1,2211
1,2211
)1.3(
1,22222121
1,11212111
nnnnnnn
nininii
nnn
nnn
axaxaxa
axaxaxa
axaxaxa
axaxaxa
行。行，加到第第把化为零；将用
1
),,2(
11
1
111
i
a
a
niaa
i
i
以后各步类似。或题：问?00 1111 aa
线性代数：方法不好时工作量非常大，
工作量小的方法是 Gauss 消去法。
消 元：
§ 3.1直接法二 列主元素消去法 ---计算结果可靠
j
j
rj
jr
jj
i
ni
r
ac
aa
ca
raar
1
1
1
3
2
1
1m a x)1(
1
1
11
1
11
行：，对调使找行号
)1n,1,2,j(
）；（
个元素成为行第第行加到第行 第为消消元：用
1,,2,1,,3,2
,1
:0
11
1
1
11
1
111
njnia
a
a
aa
jii
a
a
aa
ij
i
jij
i
i
到此原方程组化为
1,22
1,22
1,22222
1,11212111
nnnnnn
ninini
nnn
nnn
axaxa
axaxa
axaxa
axaxaxa
到此原方程组化为
.2m a x)2( 22222 2 行，对调，使找 raar inir
），；，（
行，则第行第
消为把消元：用
1,3,2,4,3
2
:),,4,3( 0
22
2
2
22
2
222
njnia
a
a
aa
i
a
a
niaa
ij
i
jij
i
i
1,33
1,33333
1,22323222
1,11313212111
nnnnnn
nnn
nnn
nnn
axaxa
axaxa
axaxaxa
axaxaxaxa
（ 3.3) 是回代过程 。
(上三角方程组 ) （ 3.2)
1,
1,22222
1,11212111
nnnnn
nnn
nnn
axa
axaxa
axaxaxa
(n) 回代求解公式
(n-1) 原方程组化为以上为消元过程。
（ 3.3)
1,
)1,.,,,2,1(
][
1
1
1,
1,
nnnnn
axa
nnk
xaa
a
x
a
a
x
n
kj
jkjnk
kk
k
nn
nn
n
三,Gauss 全主元消去法：
优点 ------计算结果更可靠；
缺点 ------挑主元花机时更多，
次序有变动，程序复杂。
说明：
(1)也可采用无回代的列主元消去法 (叫 Gauss-
--Jordan消去法 ),但比有回代的列主元消去法的乘除运算次数多 。
(2)有回代的列主元消去法所进行的乘除运算次数为,量很小 。
nnn 3131 23
nxx,,1?
四,应用
（ 1） 求行列式
（ 2） 求逆矩阵
(以上过程都应选主元 )
nn
m
nn
nm
nnn
n
bb
b
bb
aa
aa
...)1(......
...
)1(...
...
.........
...
11
111
1
111
)(.,,)( 1 AEEA
uALLLL
gubALLLL
gubA
KK
kk
121
121 )|()|(
)1|()|()|(
uLLLLA KK 1121 )(
记 1
1 )( LLL K?,则
LUA? 上三角）（下三角? （三角因子分解）
Gauss消元，初等行变换，化原方程组为上三角型。
五．矩阵三角分解法定义 3.1 LUA? 叫 A 的三角（因子）分解，其中 是L
是上三角。
U
下三角,
L 为单位下三角阵（对角元全为 1），
U
为上三角阵，则称 LUA? 为 Doolittle分解 ;
L若 是下三角,U 是单位上三角，则称 LUA?
定理 3.1 n阶阵
)2(?nA
有唯一 Doolittle分解 (Crout）
A? 的前 n-1个顺序主子式不为 0.（证略）
三角分解不唯一,为此引入定义 3.2 若为 Crout分解。
为什么要讨论三角分解？若在消元法进行前能实现三角分解 LUA?,则
bxLUbAx )(
上三角方程组）
下三角方程组）
(
(
yUx
bLy
容易回代求解回代求解很容易，如
2,1 )1,-n(k
n),2,3,(k
1
1
1
1
11
1
1
2
1
2
1
21
2221
11
kk
n
kj
jkjkk
nnnn
k
j
jkjk
kk
k
nnnnnn
uxubx
uyx
ylb
l
y
l
b
y
b
b
b
y
y
y
lll
ll
l
练习：
基本要求：
1,熟悉收敛阶的定义；
2,熟悉 Newton法及改进方法的收敛阶；
3,熟悉列主元消去法解线性方程组的计算过程；
4,熟悉矩阵三角分解中 Doolittle分解和
Crout分解定义；
5,熟悉利用三角分解来求解线性方程组的思路；
作业,作业集（ A） 第三章 1,2．
nnnn
n
n
aaa
aaa
aaa
21
22221
11211
计算方法
1．直接三角分解法（以 Doolittle分解为例）设
1
1
1
21
21
nn ll
l
nn
n
n
u
uu
uuu
222
11211
＝
由矩阵乘法
22121222222121
1212222121
11
1
11111
1111
/)(
n),3,4,2i22)
1
n),2,j22)1 )2(
),,3,2(
n),2,3,1L12)
n),1,2,(j u 1,
n),1,2,1)1 )1(
uulalaulul
iuLL
ulauauul
juLu
ni
u
a
laul
iuiL
aua
jjuLu
iiiiii
jjjjjj
i
iii
jjjj
（列的第行的第列：用的第求
（列的第行的第行：用的第求列（的第行的第列：用的第求
（列的第的第一行行：用的第求
………………………
(k)
1
1
1
1
2
1
,
2
,
1
1
0
0
)0,0,(
n),1,kk,(j1
k
m
mjkmkjkjkjkj
k
m
mjkm
kj
jj
kj
j
j
kkkk
ulauauul
a
u
u
u
u
lll
jukLku
，
列的第行的第行：用的第求
kk
k
m
mkimikik
ikkkik
k
m
mkim
ikkk
k
k
kkiki
uulal
aulul
au
u
u
lll
kuiLkL
1
1
1
1
2
1
,,,
1
0
0
)00(
n),1,k(i2
，即列的第行的第列：用的第求
),,3,2(
),,1(
),,1,(
),,3,2(
),2,1(
1
1
1
1
1111
11
nk
nkiauulal
nkkjaulau
niual
njau
D o o l i t t l e
ikkk
k
m
mkimikik
kj
k
m
mjkmkjkj
ii
jj
分解公式例 3,1
12/)126(
23/)06(,1
1
1
1
6
6
123
0 3 2
2 1 2
5
18
6
536
4 5 4
2 1 2
231
323
xxx
xxx
所以
－ － －
－
选主元的三角分解法（略）
2．平方根法定理 3.2 设 A对称正定，则有非奇异下三角阵 L，使
TLLA?
---- 理论基础 (证略）
分解方法：设
jiij
nn
n
n
nnnnnnnn
n
n
aa
l
ll
lll
lll
ll
l
aaa
aaa
aaa
其中
222
12111
21
2221
11
21
22221
11211
( choleskey分解 )
22
1212
222222121
21
22
22222221
11
1
111111
11111111
n),3,4,(j j2L )2
22L 1) )2(
n),2,(j j1L )2
)( )1 )1(
222
2
l
lla
laallll
L
lalall
L
l
a
laall
L
alal
jj
jjjjj
T
T
j
jjjj
T
列第行第列第行第列第行第取正由矩阵乘法及其改进分解。缺点：开方运算。
主元。平方根法稳定，不必先受到控制 舍入误差的放大所以说的最大元的值不会超过程中 这说明在分解过故列,第行、第
、计算量小 优点：
） （
,可得：
T
km
kk
nk
km
kk
nk
kkkm
k
m
kmkk
k
m
jmkmjk
kk
jm
k
m
kmkkkk
l
al
aal
lakk
nkj
lla
l
llalk
L D L
,A
m a x
m a x
2
1
,,1
1
)(
2
1
1
2
1
2
1
1
1
1
2
六、解三对角方程组 —— 追赶法
1
1
1
1
1,,2
22
1
2
1
11
22
1
111
222
11
11
1
2
1
1
2
1
111
222
11
n
nn
nn
nn
nnn
nniii
n
n
n
n
nn
nnn
ba
cba
cba
cb
niabcabcb
f
f
f
f
x
x
x
x
ba
cba
cba
cb
＝设有分解
） （， ,且按行严格对角占优：
（三对角方程组）给定
( Crout分解 )
列得：第行 第
＝ ，＝ ，＝
＝ ，＝＋ ，＝
＝，＝＝ ，＝） （
由矩阵乘法
1,,1)(
1)2(
211
2
2
2122222
222221222
1
1
11111111
iiiii
c
ba
cba
c
bcb
00 00 i i
11
1
1
1
iii
i
i
i
i 1?
,1.,1,1 iiiiii ba,,c iii
故有
,
,
1
1
1
111
i
i
i
iiiiii
c
ba
c
b
),,3,2( ni (3.1)
fL U xfAx （二对角方程组） 二对角方程组） ( yUx fLy
)1,,3,2( ni?
解
n)2,3,(i,1
1
1
1
y
i
iii
i
yff
y
fLy 设解 得 yUx?
1)1,-n(i,1xyxyx iiiinn?
(3.1) — (3.3) 叫追赶法，工作量小，非常有效。
(3.2)
（ 3.3）
基本要求
1.会矩阵的直接三角分解法的过程（不记公式）；
2.熟悉平方根法的计算过程（不记公式）及其优缺点。
作业：
作业集（ A） 第三章 3.
bAx?
一,简单迭代法
1.迭代法建立,考虑
gBxxbAx (矩阵 B不唯一 )
对应写出
)0(
)()1( )4.3( ),2,1,0(
x
kgBxx kk
取定初始向量
§ 3.2 解线性方程组的迭代法计算方法产生向量序列,,,,,)1()()2()1(?kk xxxx
若收敛,记 xx k
k?
)1(lim
则于 (3.4)两端取极限有：
,gxBx
上式说明,是解向量,从而当 k充分大时
)1( kx
注意,迭代阵 B不唯一,影响收敛性。
解向量
(1)叫简单迭代法,B叫迭代矩阵。
2.收敛性,
定义 3.3 称 |)(|m a x)(
1 BB ini
为矩阵 B的谱半径。
定理 3.3 简单迭代法
（证略））（
都收敛对任意初始向量
1
)0()()1(
B
xgBxx kk
x
x
都不收敛”。时不能说“对任意）（注意 )0(1,xB
收敛。则其对任意或若对迭代法
)0(
1
1
1
1
1
)()1(
1||m a x|||| 1||m a x||||
,),2,1,0(
x
bBbB
kgBxx
n
j
ij
ni
n
i
ij
nj
kk
定理 3.4
),,2,1( ||||||
|,|m a x
||||m a x||||||
)(
)4.3(1||||
)1(
)(
1
k
1
)(
1
1
)()1(
1
)()1(
niBxx
xx
xxbxxbxx
xxbxx
gBxxB
ki
k
i
j
k
j
nj
n
j
j
k
jij
ni
n
j
j
k
jiji
k
i
n
j
j
k
jiji
k
i
则记相减有与为例。将证：以收敛列解 (i=1,2,…,n)
)( 001 1 时当 kBB kkk
klim
||m a x )1(1 xx ikini x ki )1(? xi即 =0,
例 3.2 设有方程组 ( 其中 ) Ax=b,即aii 0?
a11 bxaxax nn 111
212
bxaxaxa nn 22222121
bxaxaxa nnnnnn2211
(3.5)
作等价变形xaxaxb
ax nn121211111 0 1
xaxxabax nn221212
22
2 0
1
xaxabax nnnn
nn
n 0 211
1
(3.6)
----------Jacobi迭代法
].,,,,,,,,,0[1 )(1)(212)(11
11
)1(
1
k
nn
kkk xaxaxb
ax
].,,,,,,,,,0[1 )(2)(2)(1212)1(2
22
k
nn
kkk xaxxab
ax
]0.,,,,,,,,,[1 )()(22)(11)1( knknknn
nn
k
n xxaxabax
于是有迭代公式
(k=0,1,2,… )
(3.7)
矩阵形式为：
nn
n
k
k
k
nn
n
nn
n
n
n
k
n
k
k
a
b
a
b
a
b
x
x
x
a
a
a
a
a
a
a
a
a
a
a
a
x
x
x
22
2
11
1
2
2
1
21
22
2
22
21
11
1
11
12
)1(
)1(
2
)1(
1
0
0
0
.)7.3(
,1||||1||||)2(
1)()7.3()1(
:
)0(
1
)0(
)()1(
收敛对任意迭代法则或若收敛对任意迭代法迭代法收敛性简记为
xJ a c o b i
BB
BxJ a c o b i
J a c o b i
gxBx
JJ
J
k
J
k
(3)设方程组 （ 3.5） 的系数矩阵 A按行严格对角占优即：
n),1,2,(i
,1
n
ijj
ijii aa
n),1,2,(j
,1
n
jii
ijjj aa
或按列严格对角占优，即二,迭代法设有简单迭代法 即
Seidel
,)()1( gB xx kk
xbxbxbx
xbxbxbx
xbxbxbx
k
nnn
k
n
k
n
k
n
k
nn
kkk
k
nn
kkk
)()(
22
)(
1
1
)1(
)(
2
)(
2
22
)(
121
)1(
2
)(
1
)(
212
)(
1
11
)1(
1
(3.8)
)( )7.3( )0( 证明留作练习收敛对任意迭代法则 xJ a c o b i
称如下迭代法
(3.9)
xbxbxbx
xbxbxbx
xbxbxbx
k
nnn
k
n
k
n
k
n
k
nn
kkk
k
nn
kkk
)()1(
22
)1(
11
)1(
)(
2
)(
222
)1(
121
)1(
2
)(
1
)(
212
)(
111
)1(
1
为与 (3.8)对应的 迭代法,其迭代矩阵可用,代入法,求得 。Seidel
Bs
（ 1） 迭代法 (3.9)对任意 收敛
（ 2） 若 则 迭代法 (3.9)对任意 收敛；
（ 3） 若简单迭代法 (3.8)的迭代矩阵 满足 或,则相应的 Seidel迭代法
(3.9)对任意 收敛 （ 证略 ）
Seidel
Seidel x )0( ;1)( B s?
,111BB ss 或 Seidel
x)0(
)( bB ij nn
11?B 1B
x)0(
迭代法 (3.9)的收敛性例 3.3 迭代方法
（ 3.10）
)()1(
22
)1(
11
)1(
)(
2
)(
2
)1(
1212
22
)1(
2
)(
1
)(
212
)(
11
11
)1(
1
0
1
0
1
0
1
k
n
k
n
k
nn
nn
k
n
k
nn
kkk
k
nn
kkk
xxaxab
a
x
xaxxab
a
x
xaxaxb
a
x
称为与 Jacobi迭代法 （ 3.7） 对应的 Seidel方法,
其收敛情况如下：
(1)使用一般的 Seidel方法 （ 3.9） 的收敛性判别法
(2)若系数矩阵 A对称正定,则求解方程组 （ 3.5） 的与 Jacobi迭代法对应的 Seidel方法 （ 3.10） 对任意收敛 。 （ 证略 ）)0(x
— 松弛因子,=1 即 Seidel方法 (3.10)
(3)若系数矩阵 A按行 （ 或按列 ） 严格对角占优,则求解 （ 3.5） 的与 Jacobi方法对应的 Scidel方法
（ 3.10） 对任意 收敛,（ 练习 ）)0(x
(3.11)是一种加权平均。
1)1(
1
1 1
)()1()()1(?
i
j
n
ij
k
jij
k
jiji
ii
k
i
k
i xaxabaxx
三,逐次超松弛迭代法 (SOR法 )
( 3,11 ) ),,2,1( ni
SOR方法的收敛性如下（不加证明）：
(1)SOR方法对任意 都收敛的必要条件是：
(2)若系数矩阵 A对称正定,则 时 SOR方法求解 对任意 收敛；
(3)若系数矩阵 A按行 （ 或按列 ） 严格对角占优,
则 时 SOR方法对任意 收敛 。
最佳松弛因子 选取问题 。
20
bAx? )0(x
10
opt?
20
)0(x
)0(x
例 3.4 用 Seidel迭代法求解方程组
10
15
3
521
1102
1210
3
2
1
x
x
x
Tx )0,0,0()0(? 10m a x 3)()1(
31
||
xx kiki
i
解,因为系数矩阵严格对角占优，故 Seidel方法对任意 收敛。
取初始向量,要求时迭代终止。
Seidel迭代格式为)0(x
24.02.0
,2,1,0 5.11.02.0
3.01.02.0
)1(
2
)1(
1
)1(
3
)(
3
)1(
1
)1(
2
)(
3
)(
2
)1(
1
kkk
kkk
kkk
xxx
kxxx
xxx
计算结果可列表如下
T
T
T
T
T
T
T
)(
3
)(
2
)(
1
)(
2,99 9 98 ) 1,99 9 98 ( 0,9 99 966
2,99 9 88 ) 1,99 9 85 ( 0,9 99 705
2,99 9 14 ) 1,99 8 94 ( 0,9 97 824
2,99 3 75 ) 1,99 2 24 ( 0,9 84 283
2,95 3 87 ) 1,94 4 48 ( 0,8 80 402
2,68 4 00 ) 1,56 0 00 ( 0,3 00 001
0) 0 0(0
),,(
Tkkkk
xxxxk?
注意：未必 Seidel方法一定比 Jacobi方法好 。
99998.2,99998.1,99996.0
,)321( 10||
321
63)5()6(
xxx
x,,ixx ii 为近似解，即故因为 ）（
1 熟悉简单迭代法及其收敛条件的使用；
2 熟悉 Jacobi迭代法及其相应的 Seidel迭代法的计算公式以及它们的收敛条件；
3 熟悉 SOR方法的计算公式及其收敛条件；
作业：
作业集 (A) 第三章 4,5,6,7
基本要求：
复习,线代：
1.定义：若 则 叫 A的特征值,叫其相应的特征向量 。
说明 还是特征向量 。
2.求法十分困难 ;应寻求近似解法,且简单,
可行,有效 。
)0( )( xxxA
x
x?
0)( 0|| xEAEA
0 )()( xxA又计算方法第四章 矩阵特征值和特征向量计算设 A的特征值特征向量
||||||,2121 nn 且
),,2,1( A
,,,n21
nixx
xxx
ii?
§ 4.1乘幂法与反幂法一．乘幂法 —— 求 A的主特征值（按模最大者）及其相应的特征向量
（假定 线形无关 ）
n
k
nn
kk
kk
n
nn
n
nn
n
n
xxxuu
xxxuu
xxxuu
xxxu
A
A
A
2
22
1
11
1
2
2
2
22
1
2
110
2
22
2
1
110
1
2
2
1
1
0
,0 则有线性表示初始向量
)1.4()( 0)(
12
1
111
设
i
kn
i
i
i xxu
k
k
的近似特征向量。就是故充分大时，）显然知由（
，充分大时，故
＝
个分量，则的第为记
1
1
11
1
1
1
1
1
1
2
1
1
1
1
2
1
1
1
1
1
,01.4
),,2,1(l i m
)2.4(
x
xx
xx
k
j
k
j
k
j
k
j
k
k
j
k
n
i
i
i
j
j
kn
i
i
i
j
j
k
j
k
k
j
k
u
k
nj
u
u
k
u
u
u
u
juu
)(
)(
)(
,)3(
..,,)3,2,1()2(
0)1(
1
0
11
0
常数充分大时若固定一个分量标号计算按
c
u
u
kjj
kuAu
u
jk
jk
kk
说明,;,0.1 ~ 01 u也可换另外初始向量概率很小
,)(.2 1 为零 若算法中分母 jku
.,1 征向量就是相应的一个近似特而则取 u kc
)(
)(
)(
)( 01
1
1(
1
1
1
jj
jk
jk
jk
u
uu?
计算分量则选择另一个不为零的有算法：;)(
)()(
,
)
)(
,
,,)(,1||;
)(,1||,,)1.4(.3
m i nm a x
m i n
m a x
1
1
(
最小分量的绝对值最大的分量和分别表示向量和这里继续迭代代替或如用作一次规范化步后对实用中常常是迭代为防止此现象发生分量绝对值过小时当可能很大分量绝对值则若充分大时当可知 由
m
mm
m
m
m
k
u
uu
u
u
u
v
u
u
v
u
u
u
m
m
m
m
m
k
m
K
.;
,||,)1.4(.4
1
2
参考书高加速法
，由此提示了原点平移法该比值越小收敛越快有关乘幂法的速度与比值知 由
R a y l e i g h
n
ri
j
ki
i
r
i
ji
r
i
nrr
r
ii
n
ri
ji
ki
iii
jk
jk
xx
x
x
u
u
1
1
1
1
1
1
1
211
)()()(
)2.4(|,|||||
,.,,,,,.5
1
1
1
)()()(
)(
)(
得则由是重特征值 若主特征值
与前述算法相同。同样有,.,.,.,)3,2,1(
1 )(
)(
l i m
j
jk
k
k
u
u
向量。个不同的线性无关特征的可能得到出发只不过此时从不同的
n
u
1
0
6.几何解释
1u?
4u?
3u?
2u?
1u?1?
x
11
511212-
24321-
6126
A 1.4 及的求例?
00 0.458)40 99 71 5.2 0 520 52 53 2.3 0 ( - 26 68,14 0
98 8.4444,98 8 ) 22,94 7 ( - 0.4 62
1) 0,52 6 ( - 0.0 25
08 7.4541 01 93 72 )- 21 59 22 51- ( 1 02 35 165
00 0.3643 2)- 35 1- ( 2 162
12 )- 21- ( 6,1
0) 0 1(0
)(
)(
T
T
T
T
T
T
T
3
1
3)(
11
u
u
uu
k
k
k
kk
Ak
解：
0 0 0.451
二．反幂法 —— 求 A的按摸最小的特征值 。
xxAxxA 1 1
的近似值。—反幂法，可得—用乘幂法故对的按模最大特征值，一定是则设
n
n
nn
A
A
1
1
,||||||
1
1
11
设 A可逆，由
,2
,
1
,
)(
)(
( 3 )
),3,2,1( )2(
0 1
1
nn
1
1
1
0
uAA
c
ck
k
uu
u
u
u
uAu
u
kk
k
jk
jk
kk
三角分解注：实际计算相对特征向量。就是则充分大后若
）算法步骤：（
对实对称矩阵 A的全部特征值及特征向量
—— Jacobi旋转法基本思想：
n
T
k
TT
k RRRRRR
A
2
1
2112
求一般矩阵全部特征值和特征向量的 QR方法
—— 参考书。
§ 4.2 Jacobi旋转法
1,熟悉特征值和特征向量的定义；
2,熟悉乘幂法求主特征值的计算过程；
3.了解反幂法的思路；
基本要求,
作业：
作业集（ A）第四章 1.
计算方法叫截断误差叫插值结点插值法插值条件使被插函数近似代替插值函数用简单函数望希只知离散数据求知存在实际中问题提出
)()()(,
)()(
,)(
)(:
)..,..2.1.0( )(
,,)(:.1
xxfxRx
xxf
xf
x
nixfy
xfy
i
ii
ii
)(
)(
或多项式插值代数插值多项式函数或者三角插值三角函数通常取
x?
第五章 插值法存在且唯一的多项式的次数不超过处满足插值条件互异个在定理性插值多项式的存在唯一
)(
),..,..,2,1,0( )()(
1:1.5
.2
xpn
nkxfxp
xnn
n
kkn
k
)(..,.,,
..,..,.,..,....,.,..,....,.,..,....,.,..,.,
)(..,.,,
)(..,.,,
,
...,.,.)(:
10
11110
00010
10
n
n
nnn
n
n
n
n
n
nn
xfxaxaa
xfxaxaa
xfxaxaa
xaxaaxp
代入插值条件得设证存在唯一系数即多项式该方程组解存在唯一法则知故由系数行列式
)(
,,
0)(
1
1
1
:
0
11
00
G r am m e r
xx
xx
xx
xx
nij
ji
n
nn
n
n
注,不用待定系数法 --- (1)计算量大 ;(2)不易讨论误差 ;
二次多项式插值 --- 过两点直线 ;
三次多项式插值 --- 过三点抛物线 ;
3,几何意义一,插值基函数,
i
k
xn
nkxlnn
1
).,,,,2.1.0( )( 1:5,1
个结点在次多项式个若定义
§ 5.1 Lagrange插值公式
)())(()(
)())(()(
)(
0
1
)(
110
110
nkkkkkk
nkk
k
ik
xxxxxxxx
xxxxxxxx
xl
ki
ki
xl
然：显则称其为插值基函数。
当当上满足二,Lagrange插值多项式
的线性组合。故可表为基函数多项式为次数注意：
这是因为的多项式显然为的次数满足插值条件
10
1100
,,,
,P|)(P)(P)(
n),0,1,2,(k)()(
)1.5( )()()()(
:n
n),0,1,2,(k )(
n
nnnn
kkkkkn
nnn
k
kn
lll
nxxxL
yyxLxL
yxlyxlyxlxL
xL y
三 截断误差：
)(m a x,)(
)!1(
)(R
2.53.5
)!1(
)(
)(
0)!1()()(0)(),,(
)(,,,
),()()()()()()(
)3.5()())(()(
)n,,1,0i(0)(
)2.5(
)2.5)(()(
!1
)(
)()()(
)1(
0
11
1
)1(
)1()1(
0
,
10
10
0
0
11
11
)1(
xf
xxx
Mx
n
M
x
n
f
xk
nxkfxx
R o l l exxxx
xtxtxtxktltft
xxxxxkxR
xR
xxx
n
f
xlxfxR
n
n
nn
n
n
nn
n
n
nn
n
i
i
i
n
nn
n
n
误差限
））即得（，代入（故
，即使有反复使用定理为零。故由显然在引入故有形式 方法值的学习，因证：
定理
一．差商
阶差商定义的。阶差商，是由的在叫一般的二阶差商在叫的一阶差商在叫的一阶差商（均差）在叫
1,,
,,,,,
,,,
....,.,..,....,.,..,....,.,..,..
,,
,,
,,
....,.,..,....,.,..,....,.,..,..
,
((
,
,
((
,
0
0
1110
10
210
20
2110
210
21
2
)
2
)
1
2
10
10
)
1
)
0
10
k-kxxf
xx
xxfxxxf
xxxf
xxxf
xx
xxfxxf
xxxf
xxf
x
xfxf
xxf
xxf
xx
xfxf
xxf
k
k
kk
k
§ 5.2Newton插值公式
1.定义
式故差商是微商的离散形
性质性）与结点排列无关（对称 性质略，归纳法）的线性组合形式。（证可表为值性质
),(',
0
)()(
,3
,,,,,,,,.2
)(
)('
)(
,,,.1.2
00
0
0
0
0
1
10
l i ml i m xfxxf
xxx
xfxf
xx
xxfxxf
xf
x
xf
xxxf
ijji
j
k
j
jk
i
k
3.造差商表 (实用 )
33
22
11
00
fx
fx
fx
fx
3
,
2
2
,
1
1
,
0
xxf
xxf
xxf
3,2,1
2,1,0
xxxf
xxxf
3,2,1,0 xxxxf?
二,Newton插值公式
( 5,4 ) )(n
)()()(],,,[
)()(],,[)(],[)()(
)())((],,,[
)()()(],,,[
))(](,,[)(],[)(
)()(],,,[
)()(],,[)(],[)(
)()(],,[)(],[)(
)(],[)()(
..(),,1,0()()(
11010
102100100
1010
11010
0100
20210
122100100
10100100
0010
10210
次多项式记由差商定义）的多项式 求满足
nn
n
nn
nn
niin
xxxxxxxxxf
xxxxxxxfxxxxfxfxN
xxxxxxxxxf
xxxxxxxxxf
xxxxxxxfxxxxfxf
xxxxxxxxf
xxxxxxxfxxxxfxf
xxxxxxxfxxxxfxf
xxxxfxfxf
xNnixfxN
( 5,5 ) ),(
!
)(
],,,[
)!1(
)(
],,,[
),(R)(
.( 2 );( 5,4 )( 1 ),
)(
),,1,0( )()(R)()( )(R)()(
)()()(],,,,[)(R
0
)(
10
)1(
0
1010
n
n
n
n
n
n
iniinin
nn
xx
n
f
xxxf
n
f
xxxf
xxR
xN
nixNxxNxfxxNxf
xxxxxxxxxxfx
间的关系故得差商与导数之故由惟一性，
有关系相邻次数的插值多项式易得到中各项系数由差商表容注求多项式。满足插值条件；故为欲说明：该且，
，则
1 2 0 1 6 5 6 4 4.0e
)23)(13(
)21.2)(11.2(
e
)32)(12(
)31.2)(11.2(
e
)31)(21(
)31.2)(21.2(
)1.2(e
e
)23)(13(
)2)(1(
e
)32)(12(
)3)(1(
e
)31)(21(
)3)(2(
)(
.e
0 4 9 7 8 7 0 6 8.01 3 5 3 3 5 2 8 3.03 6 7 8 7 9 4 4 1.0e
321
3,2,1e 5,1
3-
2--1
2
2,1-
3-2--1
2
2,1-
x-
-x
L
xxxxxx
xL
L a g r a n g e
x
x
二次插值多项式为：解计估差误的近似值，并进行插值公式求试用二次的值如下在已知例
0 0 6 0 7 0 0 1.0
)31.2()21.2()11.2(
!2
)1.2()1.2(
,''' m a x
1
2
2,1-
1
21
e
LeR
ee x
x
故有误差估计因的近似值。插值公式求用数值表如下：已知例
)596.0(
0 2 6 5 2.18 8 8 1 1.06 9 6 7 5.05 7 8 1 5.04 1 0 7 5.0)(
90.080.065.055.040.0
)()( 2.5
fN e w t o n
xf
x
xshxf
k
k
解：先造差商表
6 3 1 9 2.0)5 9 6.0()5 9 6.0(
5 9 6.0
)80.0)(65.0)(55.0)(40.00,0 3 4 (
)65.0)(55.0)(40.00,1 9 7 (
)55.0)(40.00,2 8 0 0 (
)40.0(1 1 6 0.14 1 0 7 5.0
4
4
Nf
x
xxxx
xxx
xx
xN
代入得：将由 Newton公式得四次插值多项式为：
1,熟悉插值法的含义及其几何意义；
2,熟悉 Lagrange插值公式及其余项的使用；
3,会造差表，并熟悉 Nenton插值公式的使用；
4,熟悉差商与导数的关系式 (5.5)。
基本要求：
作业：
作业集（ B）第五章
1,2,4,5．
牛顿基本插值公式对结点是否等矩没有限制,不过当结点等距时前述牛顿插值公式可进行简化,为此先介绍差分概念,
计算方法
§ 5.3 等矩结点插值公式
1.定义 设
nh
xxxx n
ni
0h n ),,0,1,(i i
yyy 210 为 )( xfy? 在 x0 的以 h为 步长一阶向前差分
x 1121 yyy
x 0 0102 yyy……
xyyy iimimim 111 m阶一,差分叫步长称
……
一般,
一阶二阶
(1) 差分可表为函数值的线性组合 (证略 )
h
yxxxx
n
n
n nf !],,,,[
0
210
(2)
),( )( 0)(0 xxfhy nnnn(3)
2.性质,
(2) (证明用归纳法,略 )
3,差分表 (实用 )
yyyyx
yyyx
yyx
yx
yx
ii
0
3
1
2
233
0
2
122
011
00
三阶差分二阶差分一阶差分二 等矩结点插值公式,
,n ),t(0
00
hiht xxxx i
将 Newton插值公式
)())(](,,,[
))(](,,[)](,[)()(
1010
102100100
xxxxxx
xxxxxxxxxN
nn
n
xxxf
xxfxffx
中的差商用性质 (2)换为差分,可整理为如下的
Newton向前插值公式
y
yyxxNN
n
nn
n
nttt
tt
tfthx
0
0
2
000
!
)1()1(
!2
)1(
)()()(
设
（ 5.6）
截断误差可表示为
)()!1( )()1()()( )1(10?fhx nnn ntttthRxR(5.7)
)()1(
)!1(
)()(
1
nt0
1
0
Ma x
h
nttt
n
thRxR
h
M
x
n
n
Newton向后插值公式及 Bessel 插值公式
—— 参考文献
§ 5.4 Hermite插值简介两曲线有公共交点几何上,
n),0,1,(i )()( xxP iin f
前述插值问题,要求被插函数与插值多项式在结点取相同值,
Lagrange型插值条件然而,实际许多问题还常常要求两曲线进一步有共同切线,插值条件为,求一次数 12 n 多项式 )(12 xH n?
,使之满足给定的 Hermite型插值条件
mxH
yxH
iin
iin
)(
)(
12
12
),,1,0( ni (5.8)
y
x0 x0 xi xn
求 )(12 xH n? 不用待定系数法,可设
myH jn jjn
j j
n xxx )()()(
00
12
其中 p n
jj xx
12)(),(,且
—— 插值基函数表示法 （ 5.9）
0)(' ji 0 ji 1)( j xx iij 当当
（ 5.10）
j 0
ji 1)(' 0)(
j?
ixx iij 当当 （ 5.11）
满足条件（ 5.10）和（ 5.11）的多项式（ 5.9）
一定满足（ 5.8），故即为所求所以主要是求插值基函数 )(),( xx
jj
可借用 Lagrange插值基函数 )(xlj 得公式 （ 5.37）
)(
)!22(
)(
)()()( 2 1
)22(
12 xnxxfxR n
n
n
fH
—— 有规律余项易验证：
例 5.3 给定函数值表如下,
3)(
1242)(
321
`
i
i
i
xf
xf
x
.)()()(
)2(,)3,2,1( )()(
:
),(3
3
'
33
3
的表达式并写出截断误差使之满足如下条件的多项式求一次数不超过
xfxHxR
HiifiH
xH
61592)(.
.2:,3)2(
)3)(2)(1()()(
:
673)(
23
3
3
23
2
2
xxxxH
kH
xxxkxpxH
xxxp
故得由条件设所求多项式为得的二次多项式先求满足插值条件方法解
,)3,2,1()()(
,1,
2 iifip
61592
)2)(2)(1(2)2)(1(1)1(22
)(
,
2
5
1
8
3
2
123
42
42
21
,2
23
3
xxx
xxxxxx
xH
N e w t o n 插值公式得由造重节点差商表方法
)3,1( ),3()2)(1(
)!4(
)(
)(
,
)(.3
2
)4(
xxx
f
xR
截断误差为略插值基函数表示法方法问题：结点增多，多项式次数增高，逼近精度越好？未必！多结点高次插值往往在局部误差更大 —— kunge现象。
实用：采用分段低次插值有分段线形，分段二次插值等，几何上 ……
5.5三次样条插值简介
1.分段插值法：
缺点：分段插值函数只能保证连续性，
不能保证光滑性。
折线代替曲线分段插值可以得到整体连续函数，但在连接点处一般不光滑，而 Hermite插值虽然在连节点处一阶光滑，但整体插值由于结点多，次数高而有可能发生龙格现象。
2.三次样条插值既想分段插值，又想在结点处保持光滑，
甚至二阶光滑 —— 三次样条。
希望：
样条来源：
1.定义：在 [a,b]上取 n+1个点 bxxxa
n10
若函数 S(x)满足：
ii yxS?)(
—— 此时 S(x)叫插值函数；
(3) 在内结点或在整个区间上具二阶连续导数。
则称 S(x)为 y=f(x )的三次样条插值函数。
(2) 在每个小区间
ii xx,1?
上是三次多项式；
2,构造：有两种方法，导出三对角方程组，用追赶法。
(1)
熟悉差分的定义，会造差分表；
熟悉等距节点的 Newton插值公式的运用及等距节点的插值余项公式的运用；
熟悉简单的带导数条件的插值（如例 5.3）；
熟悉分段插值法的含义。
基本要求：
作业,
作业集 (B) 第五章 6,7
西北工业大学网络教育学院主讲：
西北工业大学网络教育学院主讲：
西北工业大学网络教育学院第一章 绪论第二章 求方程根的近似方法第三章 线性代的方程组解法第四章 矩阵特征值和特征向量计算第五章 插值法计算方法
§ 1.1计算方法的任务与特点第一章,绪论实际问题 数学问题 提供计算方法程序设计 上机计算 结果分析计算方法基本的数学问题,
1.大型线性代数方程组 Ax=b求解 ;
2.矩阵 A的特征值和特征向量计算 ;
3.非线性方程 求解 (求根 );
4.积分 计算 ;
5.常微分方程初值问题求解 ;
6.其它。
0)(?xf
dxxfba? )(
求精确解 (值 )一般非常困难。例如：
1,方程组阶数 n很大，例如 n=20,计算机运算速度
1亿次 /秒,用不好的方法,大约需算 30多万年 ;
好方法不到一分钟。另外，有计算结果可靠性问题。
2,特征值定义
)0( xxAx?
0 xAx 0)( xIA
0|| IA?
3,形式复杂时求根和求积分很困难。
4.线性微分方程易解,如非线性方程难解，如
)( xf
12 '" yyy 1)0()0( ' yy
1s i n 2" yyye y 1)0()0( ' yy
希 望,求近似解，但方法简单可行，行之有效
（计算量小，误差小等）。以计算机为工具，易在计算机上实现。
计算机运算,只能进行加，减，乘，除等算术运算和一些逻辑运算。
计算方法,把求解数学问题转化为按一定次序只进行加，减，乘，除等基本运算 ——
数值方法。
§ 1.2 误差基础知识
,..,,.,
!5!3
s i n
53
xxxx
..,.,.
!5
)
!3
(s in
53
xxxx
一,误差来源（分类）
1,模型误差。
2,观测误差。
3,截断误差，如右端是截断误差。
4,舍入误差。计算机字长有限，一般实数不能精确存储，于是产生舍入误差。例如：在 10位十进制数限制下：
舍入误差很小，本课程将研究它在运算过程中是否能有效控制。
3333333333.031 ）本应?33 3 3 3 3 3 3 3 3 3.031(
00 0 0 0 0 4.1)0 0 0 0 0 2.1( 2
）
）本应（
12
2
10404000 000 000 0.0
000 004.104000 004 000 0.1
000 004.1000 002.1(
二．误差基本概念
1．绝对误差。设 —— 准确值,—— 近似值。
称 为 的绝对误差。
为 的绝对误差限。
2,相对误差 。 称 为 的相对误差 。
实用中,常用 表示 的相对误差 。
称 为 的相对误差限 。
x *x
** )( xxxe
|)(| *xe
*x
*x
x
xx
r
ee *)(*)(? *x
*
*)(
x
xe
rxre*)(
*x
*x
3,有效数字设若 (1.1)
则说 具有 n位有效数字,分别是若,则称 为有效数 。
)21.0(10* pnm aaaax ),0( 1 pa
nmxx 10
2
1*
*x
naaa,,,21
pn? *x
例 1.1
设 =0.0270是某数 经,四舍五入,所得,
则误差 不超过 末位的半个单位,即：
又,故该不等式又可写为由有效数字定义可知,有 3位有效数字,分别是 2,7,0。
*x
*)(xe *x
410
2
1* xx
)270.0(10* 1x
3110
2
1* xx
*x
x
例 1.2
= 32.93,= 32.89,
故 有 3位有效数字,分别是 3,2,8。
由于 中的数字 9不是有效数字,故 不是有效数 。
x
110
2
105.004.0* xx
3210
2
1* xx
*x*x
*x
*x
三,有效数位与误差的关系
1,有效数位 n越多，则绝对误差 越小
(由定义 1.1)
2,定理 1.1 若近似数 具有 n位有效数字,则
(1.2)
反之,若 则至少有 n位有效数字 。
*)( xe
n
r axe
1
*)( 102 1
1
n
r axe
1
1
*)( 102 1
1
*x
*x
两边除以 得
(1.3)和（ 1.4）给出了由自变量的误差引起的函数值的误差的近似式（误差传播）。
四,数值运算的误差估计
1,一元函数情形设 则,由 Taylor展开公式),( xfy?
*)* ) ((*)()(**)( xxxfxfxfyyye
*)(*)(*)( xexfye
*)(**)( *)('*)( xrxxf xfyr ee?
)( ** xfy?
(1.4)
*)(*)( *)('* *)(*)(
* xeee
rxf
xfx
y
yy
r
)( ** xfy?
（ 1.3）
2,多元函数情形设,),,,(
21 nxxxfy *),*,*,(* 21 nxxxfy
*)(*),*,*,(*)( 21
1
in
n
i
i xexxxfye
*)(**),*,*,( *),*,*,(*)(
21
21
1
iri
n
ni
n
i
r xexxxxf xxxfye
2121 ),( xxxxf
2
1
21,x
xxx
)(21)21( *** m ax irir xexxe
21,xx
)2()1()21( **** xexexxe rrr
)( *2)1()2()1()*
2
*
1( *** xexexexe
x
xe
rrrrr
则，
由多元函数的 Taylor展开公式类似可得
（ 1.5）
（ 1.6）
在（ 1.6）式中，分别取,可得同号 ) （ 1.7）
（ 1.8）
（ 1.9）
(
,
例 1.3,测得某桌面的长 a的近似值 a*=120cm,宽 b的近似值 b*=60cm。若已知 |e(a*)|≤0.2cm,
|e(b*)|≤0.1cm 。 试求近似面积 s*=a*b*
的绝对误差限与相对误差限。
2
241.01 2 02.060
|*)(||*||*)(||*||*)(|
*)(**)(*
*)(
*)*,(
*)(
*)*,(
*)(
cm
beaaebse
beaaeb
be
b
bas
ae
a
bas
se
解,面积 s=ab,在公式（ 1.5）中,将换为 s=ab,则
),( 21 xxfy?
相对误差限为 %33.0
601 2 0
24|
*
*)(||*)(|?
s
sese
r
§ 1.3 选用算法应遵循的原则
1.尽量简化计算步骤，减少乘除运算的次数,
例如，计算多项式通常运算的乘法次数为若采用递推算法,
则乘法次数仅为 n,又如
nnn xaxaaxp,...,.)( 10
2
)1(.,,,,,21 nnn
0
1
)(
)0121(
uxp
,,,,n-n-kaxuu
au
n
kkk
nn
1 0 0 1
11)
1
11(
)1(
11 0 0 0
1
1 0 0 0
1
n n nnnn
2.防止大数,吃掉,小数当 |a|>>|b|时，尽量避免 a+b 。例如，假设计算机只能存放 10位尾数的十进制数，则
3.尽量避免相近数相减例如，当 x很大时，应
8998 1040 0 0 0 0 0 0 0 0 0.0101.01004.010
1
11
xxxx
)1(
1
1
11
xxxx
，
2c o s1
s i n
s i n
c o s1 xtg
x
x
x
x 或
当 x接近于 0时，应
4.避免绝对值很小的数做分母当 |b|<<|a|时，应尽量避免 。
5,选用数值稳定性好的算法，以控制舍入误差高速增长例如若 （误差 ）则计算时误差扩大了 倍,而
b
a
n
n
n Indxx
xI 51
5
1
0
1823.056ln0I 41021 100I
1005
)1(511 nn InI
（ n=1,2,… ）
是稳定的。
基本要求：
1.熟悉计算方法在解决实际问题中所处的地位，熟悉计算方法是以计算机为工具求近似解的数值方法；
2.熟悉绝对误差（限），相对误差（限）及有效数字概念；
3.熟悉公式（ 1.2） --（ 1.9）；
4.熟悉选用算法应遵循的原则；
作业：
作业集（ A）第一章
1,2,3,4,5,6,7,8
计算方法
f(x)=0根或 f(x)零点，当 f(x)复杂时，很难求
（找近似有效简单方法）。
第二章 求方程根的近似方法
§ 2.1 区间二分法理 论,f(x) ∈ C[a,b],单调,f(a)f(b)<0
f(x)=0在 (a,b)有惟一根。
根分离：画草图，试算,多项式方程根的模的上下界。
例 2.1 用二分法求在 (1,2)内的根，要求绝对误差不超过解,
f(1)=-5<0 有根区间 中点
f(2)=14>0 -(1,2)+
f(1.25)<0 (1.25,1.5)
f(1.375)>0 (1.25,1.375)
f(1.313)<0 (1.313,1.375)
f(1.344)<0 (1.344,1.375)
f(1.360)<0 (1.360,1.375)
f(1.368)>0 (1.360,1.368)
0104 23 xx
210
2
1
f(1.5)>0 (1,1.5)
nx
1.51?x
3 6 4.1
3 6 8.1
3 6 0.1
3 4 4.1
3 1 3.1
3 7 5.1
25.1
8
7
6
5
4
3
2
x
x
x
x
x
x
x
364.18* xx若取近似根
2* 10
2
10 0 4.0)3 6 0.13 6 8.1(
2
1|| xx
81,10212|| 21* nabxx n 解出对分次数先验估计：
优点：条件简单,
缺点：收敛慢,
不易求偶数重根,
如图
,则
（ 事后估计 ）
x
y
§ 2.2 迭代法连续），，改写建立 fxxxf ()( 0)(:.1
0
1
,.,,)2,1,0( )(
x
nxx nn
取定初值
，则若收敛，设极限为则产生数列
..,,,,.,.,,121?nn xxxx
一,迭代法的建立与收敛性
)( )(lim1lim nnnn xx
可作为近似值充分大时之根，故当是即 1,0)( nxnxf?
)2l g (2100210
)(
xxxx
x
xx 或形式不唯一，如：问题,?
收敛性不同。计算结果见表取取
4.2
3 )2l g (
3 210
01
01
xxx
xx
nn
x
n
n
2.收敛定理（定理 2.2）
],[)( bax 在设?
为常数）LLxbax (1|)('|],,[)2(
01
10
1
||3
(],,[2
],[)(1
xx
L
L
x
xxbax
baxx
n
n
nn
）（
）收敛到）（；有唯一根在）方程则：（;)(1 bxabxa时，）当（
,
)(,0)('1)('
,0)(
],,[
,0)()(,0)()(
),()(( 1 )
唯一故根递增，又使故至少有则设证：
xgxxg
g
ba
bbbgaaag
xxxg
(2)
1nx
，故收敛。
)(
00112
时当
n
xLxL nn
中值定理
n
nnnn
xL
xxx ))((')()(1
(＊ )1
－－
）式（由（＊）
（＊）
－
式）由（＊）
（＊） 中值定理
011
2
1
111
11
11
11
2
3
1
1
)1(
1 (
)()(
2))(('
)()(
xx
L
L
xx
L
L
xx
L
x
xLxLx
xxxxxx
xxLxx
xxxx
n
nn
nnn
nnn
nnnnnn
nnnnn
nnnn
(3)
注,L越小，收敛越快。
3．编程停机判断
)(1 nn xx （取定初值
0x
）计算，当
nn xx 1
时，由（＊） 3 式知
L1 1－nx
比较小，此时停机,1n x?
二、迭代加速公式（略）
由
§ 2.3 Newton 迭代法一 Newton 迭代法
1.迭代公式建立
)(xf 在
nx
点 Taylor展开
)()(')()(
)(
!2
)(
)()(')()( 2
nnn
n
n
nnn
xxxfxfxf
xx
xf
xxxfxfxf
—— Taylor展开线性化（重要思想）
0)(?xf 近似于 0)()(')( nnn xxxfxf
解出 记为
1?nx
，则
)1.2(),2,1,0(
)('
)(
1 nxf
xfxx
n
n
nn
1?nx
将
x
2.Newton迭代法的几何意义过 ))(,(
nn xfx
切线
)()(')( nnn xxxfxfy
与 0?y 求交点，解出
1 nxx
,则
)('
)(
1
n
n
nn xf
xfxx
3,Newton迭代法收敛定理（定理 2.6）
0)(?xf 在ba,有根 α,且 )(xf 在ba,
（ 1） )("),(' xfxf 连续，且分别不变号；
bax,0?,使则 Newton 迭代法（ 2.1）产生的数列
1?nx
的收敛到根 α 。
0)(,0)(",0)(' 0 xfxfxf
为例证明（其它情况类似）
（ 2） 取初值设
0)(")( 00?xfxf
证,以将 在)(?f
nx
处 Taylor展开
1
2
1
2
2
)(
)('2
)("
)(
)('2
)("
)('
)(
0)(
!2
)("
))((')()(
nn
n
n
nn
n
n
n
n
n
n
n
nnn
xx
xf
f
xx
xf
f
xf
xf
x
x
f
xxfxff
说明数列
1?nx
有下界 α
又
n
n
n
nn xxf
xfxx
)('
)(
1
故
1?nx
单调递减。
1 nx 收敛。设 xx nn 1l i m
则由（ 2.1），
xxf
xf
xfxx,0)(,
)('
)(
，
例 2.2
解：设,0,2 cxcx 则取 cxxf 2)(,则由（ 2.1）
)(
2
1
2
2
1
n
n
n
n
nn
x
c
x
x
cx
xx
)0(?cc
用 Newton 迭代法求基本要求
1.熟悉区间＝分法；
2.熟悉迭代法的建立，会使用收敛定理；
3.熟悉 Newton迭代法及其几何意义和收敛条件。
作业：
作业集（ B）第二章
1,2,3,4,6
计算方法二,迭代法的收敛阶 (收敛速度 )
1.定义,设,lim
nn
x 若有实数 p>0,使
)0(
||
||
l i m 1
cc
x
x
p
n
n
n?
则称 xn p阶收敛,相应的迭代法称为 p阶方法,
特别,p=1时叫线性收敛,
p=2时叫平方收敛,
p越大越好 (why?)
2.定理 2.7
线性收敛；则（且）（若
。的根收敛到设
)(,0)
)(),2,1,0()( (1 )
1
1
1
xx
xx
nn
nn
cx
xxn
至少二阶收敛。（即的单根迭代法求则
)0)('
0)(
f
xfN e w t o n
的条件成立）设定理（ 6.22
所以，此时 Newton法至少二阶收敛,
线性收敛
） 证：（
)(
0)('
))((')()(1
1
'
1
1
1
nn
n
n
n
nnnn
xx
a
x
x
xxx
(2)由 2.6的证明有：
故,)()('2 )(" 21 n
n
n
n xxf
fx
)('2
)("
)('2
)("
2
1
f
f
xf
f
x
x
n
n
n
n
0)(")(0
0)(")(0
f
f
若大于二阶收敛若二阶收敛
3,Newton法改进：
则重根有设 )2(0)( mmxf
§ 2.4 弦截法 —— (略 )
)('
)(
1 x
xxx
n
n
nn f
fm
。收敛时至少是二阶收敛第三章 线性代数方程组解法解线性方程组 bAx?
x解向量列迭代法：格式，无穷序误差，有限步，精确解直接法：理论，无舍入
一,Gauss 消去法设 有
1,2211
1,2211
)1.3(
1,22222121
1,11212111
nnnnnnn
nininii
nnn
nnn
axaxaxa
axaxaxa
axaxaxa
axaxaxa
行。行，加到第第把化为零；将用
1
),,2(
11
1
111
i
a
a
niaa
i
i
以后各步类似。或题：问?00 1111 aa
线性代数：方法不好时工作量非常大，
工作量小的方法是 Gauss 消去法。
消 元：
§ 3.1直接法二 列主元素消去法 ---计算结果可靠
j
j
rj
jr
jj
i
ni
r
ac
aa
ca
raar
1
1
1
3
2
1
1m a x)1(
1
1
11
1
11
行：，对调使找行号
)1n,1,2,j(
）；（
个元素成为行第第行加到第行 第为消消元：用
1,,2,1,,3,2
,1
:0
11
1
1
11
1
111
njnia
a
a
aa
jii
a
a
aa
ij
i
jij
i
i
到此原方程组化为
1,22
1,22
1,22222
1,11212111
nnnnnn
ninini
nnn
nnn
axaxa
axaxa
axaxa
axaxaxa
到此原方程组化为
.2m a x)2( 22222 2 行，对调，使找 raar inir
），；，（
行，则第行第
消为把消元：用
1,3,2,4,3
2
:),,4,3( 0
22
2
2
22
2
222
njnia
a
a
aa
i
a
a
niaa
ij
i
jij
i
i
1,33
1,33333
1,22323222
1,11313212111
nnnnnn
nnn
nnn
nnn
axaxa
axaxa
axaxaxa
axaxaxaxa
（ 3.3) 是回代过程 。
(上三角方程组 ) （ 3.2)
1,
1,22222
1,11212111
nnnnn
nnn
nnn
axa
axaxa
axaxaxa
(n) 回代求解公式
(n-1) 原方程组化为以上为消元过程。
（ 3.3)
1,
)1,.,,,2,1(
][
1
1
1,
1,
nnnnn
axa
nnk
xaa
a
x
a
a
x
n
kj
jkjnk
kk
k
nn
nn
n
三,Gauss 全主元消去法：
优点 ------计算结果更可靠；
缺点 ------挑主元花机时更多，
次序有变动，程序复杂。
说明：
(1)也可采用无回代的列主元消去法 (叫 Gauss-
--Jordan消去法 ),但比有回代的列主元消去法的乘除运算次数多 。
(2)有回代的列主元消去法所进行的乘除运算次数为,量很小 。
nnn 3131 23
nxx,,1?
四,应用
（ 1） 求行列式
（ 2） 求逆矩阵
(以上过程都应选主元 )
nn
m
nn
nm
nnn
n
bb
b
bb
aa
aa
...)1(......
...
)1(...
...
.........
...
11
111
1
111
)(.,,)( 1 AEEA
uALLLL
gubALLLL
gubA
KK
kk
121
121 )|()|(
)1|()|()|(
uLLLLA KK 1121 )(
记 1
1 )( LLL K?,则
LUA? 上三角）（下三角? （三角因子分解）
Gauss消元，初等行变换，化原方程组为上三角型。
五．矩阵三角分解法定义 3.1 LUA? 叫 A 的三角（因子）分解，其中 是L
是上三角。
U
下三角,
L 为单位下三角阵（对角元全为 1），
U
为上三角阵，则称 LUA? 为 Doolittle分解 ;
L若 是下三角,U 是单位上三角，则称 LUA?
定理 3.1 n阶阵
)2(?nA
有唯一 Doolittle分解 (Crout）
A? 的前 n-1个顺序主子式不为 0.（证略）
三角分解不唯一,为此引入定义 3.2 若为 Crout分解。
为什么要讨论三角分解？若在消元法进行前能实现三角分解 LUA?,则
bxLUbAx )(
上三角方程组）
下三角方程组）
(
(
yUx
bLy
容易回代求解回代求解很容易，如
2,1 )1,-n(k
n),2,3,(k
1
1
1
1
11
1
1
2
1
2
1
21
2221
11
kk
n
kj
jkjkk
nnnn
k
j
jkjk
kk
k
nnnnnn
uxubx
uyx
ylb
l
y
l
b
y
b
b
b
y
y
y
lll
ll
l
练习：
基本要求：
1,熟悉收敛阶的定义；
2,熟悉 Newton法及改进方法的收敛阶；
3,熟悉列主元消去法解线性方程组的计算过程；
4,熟悉矩阵三角分解中 Doolittle分解和
Crout分解定义；
5,熟悉利用三角分解来求解线性方程组的思路；
作业,作业集（ A） 第三章 1,2．
nnnn
n
n
aaa
aaa
aaa
21
22221
11211
计算方法
1．直接三角分解法（以 Doolittle分解为例）设
1
1
1
21
21
nn ll
l
nn
n
n
u
uu
uuu
222
11211
＝
由矩阵乘法
22121222222121
1212222121
11
1
11111
1111
/)(
n),3,4,2i22)
1
n),2,j22)1 )2(
),,3,2(
n),2,3,1L12)
n),1,2,(j u 1,
n),1,2,1)1 )1(
uulalaulul
iuLL
ulauauul
juLu
ni
u
a
laul
iuiL
aua
jjuLu
iiiiii
jjjjjj
i
iii
jjjj
（列的第行的第列：用的第求
（列的第行的第行：用的第求列（的第行的第列：用的第求
（列的第的第一行行：用的第求
………………………
(k)
1
1
1
1
2
1
,
2
,
1
1
0
0
)0,0,(
n),1,kk,(j1
k
m
mjkmkjkjkjkj
k
m
mjkm
kj
jj
kj
j
j
kkkk
ulauauul
a
u
u
u
u
lll
jukLku
，
列的第行的第行：用的第求
kk
k
m
mkimikik
ikkkik
k
m
mkim
ikkk
k
k
kkiki
uulal
aulul
au
u
u
lll
kuiLkL
1
1
1
1
2
1
,,,
1
0
0
)00(
n),1,k(i2
，即列的第行的第列：用的第求
),,3,2(
),,1(
),,1,(
),,3,2(
),2,1(
1
1
1
1
1111
11
nk
nkiauulal
nkkjaulau
niual
njau
D o o l i t t l e
ikkk
k
m
mkimikik
kj
k
m
mjkmkjkj
ii
jj
分解公式例 3,1
12/)126(
23/)06(,1
1
1
1
6
6
123
0 3 2
2 1 2
5
18
6
536
4 5 4
2 1 2
231
323
xxx
xxx
所以
－ － －
－
选主元的三角分解法（略）
2．平方根法定理 3.2 设 A对称正定，则有非奇异下三角阵 L，使
TLLA?
---- 理论基础 (证略）
分解方法：设
jiij
nn
n
n
nnnnnnnn
n
n
aa
l
ll
lll
lll
ll
l
aaa
aaa
aaa
其中
222
12111
21
2221
11
21
22221
11211
( choleskey分解 )
22
1212
222222121
21
22
22222221
11
1
111111
11111111
n),3,4,(j j2L )2
22L 1) )2(
n),2,(j j1L )2
)( )1 )1(
222
2
l
lla
laallll
L
lalall
L
l
a
laall
L
alal
jj
jjjjj
T
T
j
jjjj
T
列第行第列第行第列第行第取正由矩阵乘法及其改进分解。缺点：开方运算。
主元。平方根法稳定，不必先受到控制 舍入误差的放大所以说的最大元的值不会超过程中 这说明在分解过故列,第行、第
、计算量小 优点：
） （
,可得：
T
km
kk
nk
km
kk
nk
kkkm
k
m
kmkk
k
m
jmkmjk
kk
jm
k
m
kmkkkk
l
al
aal
lakk
nkj
lla
l
llalk
L D L
,A
m a x
m a x
2
1
,,1
1
)(
2
1
1
2
1
2
1
1
1
1
2
六、解三对角方程组 —— 追赶法
1
1
1
1
1,,2
22
1
2
1
11
22
1
111
222
11
11
1
2
1
1
2
1
111
222
11
n
nn
nn
nn
nnn
nniii
n
n
n
n
nn
nnn
ba
cba
cba
cb
niabcabcb
f
f
f
f
x
x
x
x
ba
cba
cba
cb
＝设有分解
） （， ,且按行严格对角占优：
（三对角方程组）给定
( Crout分解 )
列得：第行 第
＝ ，＝ ，＝
＝ ，＝＋ ，＝
＝，＝＝ ，＝） （
由矩阵乘法
1,,1)(
1)2(
211
2
2
2122222
222221222
1
1
11111111
iiiii
c
ba
cba
c
bcb
00 00 i i
11
1
1
1
iii
i
i
i
i 1?
,1.,1,1 iiiiii ba,,c iii
故有
,
,
1
1
1
111
i
i
i
iiiiii
c
ba
c
b
),,3,2( ni (3.1)
fL U xfAx （二对角方程组） 二对角方程组） ( yUx fLy
)1,,3,2( ni?
解
n)2,3,(i,1
1
1
1
y
i
iii
i
yff
y
fLy 设解 得 yUx?
1)1,-n(i,1xyxyx iiiinn?
(3.1) — (3.3) 叫追赶法，工作量小，非常有效。
(3.2)
（ 3.3）
基本要求
1.会矩阵的直接三角分解法的过程（不记公式）；
2.熟悉平方根法的计算过程（不记公式）及其优缺点。
作业：
作业集（ A） 第三章 3.
bAx?
一,简单迭代法
1.迭代法建立,考虑
gBxxbAx (矩阵 B不唯一 )
对应写出
)0(
)()1( )4.3( ),2,1,0(
x
kgBxx kk
取定初始向量
§ 3.2 解线性方程组的迭代法计算方法产生向量序列,,,,,)1()()2()1(?kk xxxx
若收敛,记 xx k
k?
)1(lim
则于 (3.4)两端取极限有：
,gxBx
上式说明,是解向量,从而当 k充分大时
)1( kx
注意,迭代阵 B不唯一,影响收敛性。
解向量
(1)叫简单迭代法,B叫迭代矩阵。
2.收敛性,
定义 3.3 称 |)(|m a x)(
1 BB ini
为矩阵 B的谱半径。
定理 3.3 简单迭代法
（证略））（
都收敛对任意初始向量
1
)0()()1(
B
xgBxx kk
x
x
都不收敛”。时不能说“对任意）（注意 )0(1,xB
收敛。则其对任意或若对迭代法
)0(
1
1
1
1
1
)()1(
1||m a x|||| 1||m a x||||
,),2,1,0(
x
bBbB
kgBxx
n
j
ij
ni
n
i
ij
nj
kk
定理 3.4
),,2,1( ||||||
|,|m a x
||||m a x||||||
)(
)4.3(1||||
)1(
)(
1
k
1
)(
1
1
)()1(
1
)()1(
niBxx
xx
xxbxxbxx
xxbxx
gBxxB
ki
k
i
j
k
j
nj
n
j
j
k
jij
ni
n
j
j
k
jiji
k
i
n
j
j
k
jiji
k
i
则记相减有与为例。将证：以收敛列解 (i=1,2,…,n)
)( 001 1 时当 kBB kkk
klim
||m a x )1(1 xx ikini x ki )1(? xi即 =0,
例 3.2 设有方程组 ( 其中 ) Ax=b,即aii 0?
a11 bxaxax nn 111
212
bxaxaxa nn 22222121
bxaxaxa nnnnnn2211
(3.5)
作等价变形xaxaxb
ax nn121211111 0 1
xaxxabax nn221212
22
2 0
1
xaxabax nnnn
nn
n 0 211
1
(3.6)
----------Jacobi迭代法
].,,,,,,,,,0[1 )(1)(212)(11
11
)1(
1
k
nn
kkk xaxaxb
ax
].,,,,,,,,,0[1 )(2)(2)(1212)1(2
22
k
nn
kkk xaxxab
ax
]0.,,,,,,,,,[1 )()(22)(11)1( knknknn
nn
k
n xxaxabax
于是有迭代公式
(k=0,1,2,… )
(3.7)
矩阵形式为：
nn
n
k
k
k
nn
n
nn
n
n
n
k
n
k
k
a
b
a
b
a
b
x
x
x
a
a
a
a
a
a
a
a
a
a
a
a
x
x
x
22
2
11
1
2
2
1
21
22
2
22
21
11
1
11
12
)1(
)1(
2
)1(
1
0
0
0
.)7.3(
,1||||1||||)2(
1)()7.3()1(
:
)0(
1
)0(
)()1(
收敛对任意迭代法则或若收敛对任意迭代法迭代法收敛性简记为
xJ a c o b i
BB
BxJ a c o b i
J a c o b i
gxBx
JJ
J
k
J
k
(3)设方程组 （ 3.5） 的系数矩阵 A按行严格对角占优即：
n),1,2,(i
,1
n
ijj
ijii aa
n),1,2,(j
,1
n
jii
ijjj aa
或按列严格对角占优，即二,迭代法设有简单迭代法 即
Seidel
,)()1( gB xx kk
xbxbxbx
xbxbxbx
xbxbxbx
k
nnn
k
n
k
n
k
n
k
nn
kkk
k
nn
kkk
)()(
22
)(
1
1
)1(
)(
2
)(
2
22
)(
121
)1(
2
)(
1
)(
212
)(
1
11
)1(
1
(3.8)
)( )7.3( )0( 证明留作练习收敛对任意迭代法则 xJ a c o b i
称如下迭代法
(3.9)
xbxbxbx
xbxbxbx
xbxbxbx
k
nnn
k
n
k
n
k
n
k
nn
kkk
k
nn
kkk
)()1(
22
)1(
11
)1(
)(
2
)(
222
)1(
121
)1(
2
)(
1
)(
212
)(
111
)1(
1
为与 (3.8)对应的 迭代法,其迭代矩阵可用,代入法,求得 。Seidel
Bs
（ 1） 迭代法 (3.9)对任意 收敛
（ 2） 若 则 迭代法 (3.9)对任意 收敛；
（ 3） 若简单迭代法 (3.8)的迭代矩阵 满足 或,则相应的 Seidel迭代法
(3.9)对任意 收敛 （ 证略 ）
Seidel
Seidel x )0( ;1)( B s?
,111BB ss 或 Seidel
x)0(
)( bB ij nn
11?B 1B
x)0(
迭代法 (3.9)的收敛性例 3.3 迭代方法
（ 3.10）
)()1(
22
)1(
11
)1(
)(
2
)(
2
)1(
1212
22
)1(
2
)(
1
)(
212
)(
11
11
)1(
1
0
1
0
1
0
1
k
n
k
n
k
nn
nn
k
n
k
nn
kkk
k
nn
kkk
xxaxab
a
x
xaxxab
a
x
xaxaxb
a
x
称为与 Jacobi迭代法 （ 3.7） 对应的 Seidel方法,
其收敛情况如下：
(1)使用一般的 Seidel方法 （ 3.9） 的收敛性判别法
(2)若系数矩阵 A对称正定,则求解方程组 （ 3.5） 的与 Jacobi迭代法对应的 Seidel方法 （ 3.10） 对任意收敛 。 （ 证略 ）)0(x
— 松弛因子,=1 即 Seidel方法 (3.10)
(3)若系数矩阵 A按行 （ 或按列 ） 严格对角占优,则求解 （ 3.5） 的与 Jacobi方法对应的 Scidel方法
（ 3.10） 对任意 收敛,（ 练习 ）)0(x
(3.11)是一种加权平均。
1)1(
1
1 1
)()1()()1(?
i
j
n
ij
k
jij
k
jiji
ii
k
i
k
i xaxabaxx
三,逐次超松弛迭代法 (SOR法 )
( 3,11 ) ),,2,1( ni
SOR方法的收敛性如下（不加证明）：
(1)SOR方法对任意 都收敛的必要条件是：
(2)若系数矩阵 A对称正定,则 时 SOR方法求解 对任意 收敛；
(3)若系数矩阵 A按行 （ 或按列 ） 严格对角占优,
则 时 SOR方法对任意 收敛 。
最佳松弛因子 选取问题 。
20
bAx? )0(x
10
opt?
20
)0(x
)0(x
例 3.4 用 Seidel迭代法求解方程组
10
15
3
521
1102
1210
3
2
1
x
x
x
Tx )0,0,0()0(? 10m a x 3)()1(
31
||
xx kiki
i
解,因为系数矩阵严格对角占优，故 Seidel方法对任意 收敛。
取初始向量,要求时迭代终止。
Seidel迭代格式为)0(x
24.02.0
,2,1,0 5.11.02.0
3.01.02.0
)1(
2
)1(
1
)1(
3
)(
3
)1(
1
)1(
2
)(
3
)(
2
)1(
1
kkk
kkk
kkk
xxx
kxxx
xxx
计算结果可列表如下
T
T
T
T
T
T
T
)(
3
)(
2
)(
1
)(
2,99 9 98 ) 1,99 9 98 ( 0,9 99 966
2,99 9 88 ) 1,99 9 85 ( 0,9 99 705
2,99 9 14 ) 1,99 8 94 ( 0,9 97 824
2,99 3 75 ) 1,99 2 24 ( 0,9 84 283
2,95 3 87 ) 1,94 4 48 ( 0,8 80 402
2,68 4 00 ) 1,56 0 00 ( 0,3 00 001
0) 0 0(0
),,(
Tkkkk
xxxxk?
注意：未必 Seidel方法一定比 Jacobi方法好 。
99998.2,99998.1,99996.0
,)321( 10||
321
63)5()6(
xxx
x,,ixx ii 为近似解，即故因为 ）（
1 熟悉简单迭代法及其收敛条件的使用；
2 熟悉 Jacobi迭代法及其相应的 Seidel迭代法的计算公式以及它们的收敛条件；
3 熟悉 SOR方法的计算公式及其收敛条件；
作业：
作业集 (A) 第三章 4,5,6,7
基本要求：
复习,线代：
1.定义：若 则 叫 A的特征值,叫其相应的特征向量 。
说明 还是特征向量 。
2.求法十分困难 ;应寻求近似解法,且简单,
可行,有效 。
)0( )( xxxA
x
x?
0)( 0|| xEAEA
0 )()( xxA又计算方法第四章 矩阵特征值和特征向量计算设 A的特征值特征向量
||||||,2121 nn 且
),,2,1( A
,,,n21
nixx
xxx
ii?
§ 4.1乘幂法与反幂法一．乘幂法 —— 求 A的主特征值（按模最大者）及其相应的特征向量
（假定 线形无关 ）
n
k
nn
kk
kk
n
nn
n
nn
n
n
xxxuu
xxxuu
xxxuu
xxxu
A
A
A
2
22
1
11
1
2
2
2
22
1
2
110
2
22
2
1
110
1
2
2
1
1
0
,0 则有线性表示初始向量
)1.4()( 0)(
12
1
111
设
i
kn
i
i
i xxu
k
k
的近似特征向量。就是故充分大时，）显然知由（
，充分大时，故
＝
个分量，则的第为记
1
1
11
1
1
1
1
1
1
2
1
1
1
1
2
1
1
1
1
1
,01.4
),,2,1(l i m
)2.4(
x
xx
xx
k
j
k
j
k
j
k
j
k
k
j
k
n
i
i
i
j
j
kn
i
i
i
j
j
k
j
k
k
j
k
u
k
nj
u
u
k
u
u
u
u
juu
)(
)(
)(
,)3(
..,,)3,2,1()2(
0)1(
1
0
11
0
常数充分大时若固定一个分量标号计算按
c
u
u
kjj
kuAu
u
jk
jk
kk
说明,;,0.1 ~ 01 u也可换另外初始向量概率很小
,)(.2 1 为零 若算法中分母 jku
.,1 征向量就是相应的一个近似特而则取 u kc
)(
)(
)(
)( 01
1
1(
1
1
1
jj
jk
jk
jk
u
uu?
计算分量则选择另一个不为零的有算法：;)(
)()(
,
)
)(
,
,,)(,1||;
)(,1||,,)1.4(.3
m i nm a x
m i n
m a x
1
1
(
最小分量的绝对值最大的分量和分别表示向量和这里继续迭代代替或如用作一次规范化步后对实用中常常是迭代为防止此现象发生分量绝对值过小时当可能很大分量绝对值则若充分大时当可知 由
m
mm
m
m
m
k
u
uu
u
u
u
v
u
u
v
u
u
u
m
m
m
m
m
k
m
K
.;
,||,)1.4(.4
1
2
参考书高加速法
，由此提示了原点平移法该比值越小收敛越快有关乘幂法的速度与比值知 由
R a y l e i g h
n
ri
j
ki
i
r
i
ji
r
i
nrr
r
ii
n
ri
ji
ki
iii
jk
jk
xx
x
x
u
u
1
1
1
1
1
1
1
211
)()()(
)2.4(|,|||||
,.,,,,,.5
1
1
1
)()()(
)(
)(
得则由是重特征值 若主特征值
与前述算法相同。同样有,.,.,.,)3,2,1(
1 )(
)(
l i m
j
jk
k
k
u
u
向量。个不同的线性无关特征的可能得到出发只不过此时从不同的
n
u
1
0
6.几何解释
1u?
4u?
3u?
2u?
1u?1?
x
11
511212-
24321-
6126
A 1.4 及的求例?
00 0.458)40 99 71 5.2 0 520 52 53 2.3 0 ( - 26 68,14 0
98 8.4444,98 8 ) 22,94 7 ( - 0.4 62
1) 0,52 6 ( - 0.0 25
08 7.4541 01 93 72 )- 21 59 22 51- ( 1 02 35 165
00 0.3643 2)- 35 1- ( 2 162
12 )- 21- ( 6,1
0) 0 1(0
)(
)(
T
T
T
T
T
T
T
3
1
3)(
11
u
u
uu
k
k
k
kk
Ak
解：
0 0 0.451
二．反幂法 —— 求 A的按摸最小的特征值 。
xxAxxA 1 1
的近似值。—反幂法，可得—用乘幂法故对的按模最大特征值，一定是则设
n
n
nn
A
A
1
1
,||||||
1
1
11
设 A可逆，由
,2
,
1
,
)(
)(
( 3 )
),3,2,1( )2(
0 1
1
nn
1
1
1
0
uAA
c
ck
k
uu
u
u
u
uAu
u
kk
k
jk
jk
kk
三角分解注：实际计算相对特征向量。就是则充分大后若
）算法步骤：（
对实对称矩阵 A的全部特征值及特征向量
—— Jacobi旋转法基本思想：
n
T
k
TT
k RRRRRR
A
2
1
2112
求一般矩阵全部特征值和特征向量的 QR方法
—— 参考书。
§ 4.2 Jacobi旋转法
1,熟悉特征值和特征向量的定义；
2,熟悉乘幂法求主特征值的计算过程；
3.了解反幂法的思路；
基本要求,
作业：
作业集（ A）第四章 1.
计算方法叫截断误差叫插值结点插值法插值条件使被插函数近似代替插值函数用简单函数望希只知离散数据求知存在实际中问题提出
)()()(,
)()(
,)(
)(:
)..,..2.1.0( )(
,,)(:.1
xxfxRx
xxf
xf
x
nixfy
xfy
i
ii
ii
)(
)(
或多项式插值代数插值多项式函数或者三角插值三角函数通常取
x?
第五章 插值法存在且唯一的多项式的次数不超过处满足插值条件互异个在定理性插值多项式的存在唯一
)(
),..,..,2,1,0( )()(
1:1.5
.2
xpn
nkxfxp
xnn
n
kkn
k
)(..,.,,
..,..,.,..,....,.,..,....,.,..,....,.,..,.,
)(..,.,,
)(..,.,,
,
...,.,.)(:
10
11110
00010
10
n
n
nnn
n
n
n
n
n
nn
xfxaxaa
xfxaxaa
xfxaxaa
xaxaaxp
代入插值条件得设证存在唯一系数即多项式该方程组解存在唯一法则知故由系数行列式
)(
,,
0)(
1
1
1
:
0
11
00
G r am m e r
xx
xx
xx
xx
nij
ji
n
nn
n
n
注,不用待定系数法 --- (1)计算量大 ;(2)不易讨论误差 ;
二次多项式插值 --- 过两点直线 ;
三次多项式插值 --- 过三点抛物线 ;
3,几何意义一,插值基函数,
i
k
xn
nkxlnn
1
).,,,,2.1.0( )( 1:5,1
个结点在次多项式个若定义
§ 5.1 Lagrange插值公式
)())(()(
)())(()(
)(
0
1
)(
110
110
nkkkkkk
nkk
k
ik
xxxxxxxx
xxxxxxxx
xl
ki
ki
xl
然：显则称其为插值基函数。
当当上满足二,Lagrange插值多项式
的线性组合。故可表为基函数多项式为次数注意：
这是因为的多项式显然为的次数满足插值条件
10
1100
,,,
,P|)(P)(P)(
n),0,1,2,(k)()(
)1.5( )()()()(
:n
n),0,1,2,(k )(
n
nnnn
kkkkkn
nnn
k
kn
lll
nxxxL
yyxLxL
yxlyxlyxlxL
xL y
三 截断误差：
)(m a x,)(
)!1(
)(R
2.53.5
)!1(
)(
)(
0)!1()()(0)(),,(
)(,,,
),()()()()()()(
)3.5()())(()(
)n,,1,0i(0)(
)2.5(
)2.5)(()(
!1
)(
)()()(
)1(
0
11
1
)1(
)1()1(
0
,
10
10
0
0
11
11
)1(
xf
xxx
Mx
n
M
x
n
f
xk
nxkfxx
R o l l exxxx
xtxtxtxktltft
xxxxxkxR
xR
xxx
n
f
xlxfxR
n
n
nn
n
n
nn
n
n
nn
n
i
i
i
n
nn
n
n
误差限
））即得（，代入（故
，即使有反复使用定理为零。故由显然在引入故有形式 方法值的学习，因证：
定理
一．差商
阶差商定义的。阶差商，是由的在叫一般的二阶差商在叫的一阶差商在叫的一阶差商（均差）在叫
1,,
,,,,,
,,,
....,.,..,....,.,..,....,.,..,..
,,
,,
,,
....,.,..,....,.,..,....,.,..,..
,
((
,
,
((
,
0
0
1110
10
210
20
2110
210
21
2
)
2
)
1
2
10
10
)
1
)
0
10
k-kxxf
xx
xxfxxxf
xxxf
xxxf
xx
xxfxxf
xxxf
xxf
x
xfxf
xxf
xxf
xx
xfxf
xxf
k
k
kk
k
§ 5.2Newton插值公式
1.定义
式故差商是微商的离散形
性质性）与结点排列无关（对称 性质略，归纳法）的线性组合形式。（证可表为值性质
),(',
0
)()(
,3
,,,,,,,,.2
)(
)('
)(
,,,.1.2
00
0
0
0
0
1
10
l i ml i m xfxxf
xxx
xfxf
xx
xxfxxf
xf
x
xf
xxxf
ijji
j
k
j
jk
i
k
3.造差商表 (实用 )
33
22
11
00
fx
fx
fx
fx
3
,
2
2
,
1
1
,
0
xxf
xxf
xxf
3,2,1
2,1,0
xxxf
xxxf
3,2,1,0 xxxxf?
二,Newton插值公式
( 5,4 ) )(n
)()()(],,,[
)()(],,[)(],[)()(
)())((],,,[
)()()(],,,[
))(](,,[)(],[)(
)()(],,,[
)()(],,[)(],[)(
)()(],,[)(],[)(
)(],[)()(
..(),,1,0()()(
11010
102100100
1010
11010
0100
20210
122100100
10100100
0010
10210
次多项式记由差商定义）的多项式 求满足
nn
n
nn
nn
niin
xxxxxxxxxf
xxxxxxxfxxxxfxfxN
xxxxxxxxxf
xxxxxxxxxf
xxxxxxxfxxxxfxf
xxxxxxxxf
xxxxxxxfxxxxfxf
xxxxxxxfxxxxfxf
xxxxfxfxf
xNnixfxN
( 5,5 ) ),(
!
)(
],,,[
)!1(
)(
],,,[
),(R)(
.( 2 );( 5,4 )( 1 ),
)(
),,1,0( )()(R)()( )(R)()(
)()()(],,,,[)(R
0
)(
10
)1(
0
1010
n
n
n
n
n
n
iniinin
nn
xx
n
f
xxxf
n
f
xxxf
xxR
xN
nixNxxNxfxxNxf
xxxxxxxxxxfx
间的关系故得差商与导数之故由惟一性，
有关系相邻次数的插值多项式易得到中各项系数由差商表容注求多项式。满足插值条件；故为欲说明：该且，
，则
1 2 0 1 6 5 6 4 4.0e
)23)(13(
)21.2)(11.2(
e
)32)(12(
)31.2)(11.2(
e
)31)(21(
)31.2)(21.2(
)1.2(e
e
)23)(13(
)2)(1(
e
)32)(12(
)3)(1(
e
)31)(21(
)3)(2(
)(
.e
0 4 9 7 8 7 0 6 8.01 3 5 3 3 5 2 8 3.03 6 7 8 7 9 4 4 1.0e
321
3,2,1e 5,1
3-
2--1
2
2,1-
3-2--1
2
2,1-
x-
-x
L
xxxxxx
xL
L a g r a n g e
x
x
二次插值多项式为：解计估差误的近似值，并进行插值公式求试用二次的值如下在已知例
0 0 6 0 7 0 0 1.0
)31.2()21.2()11.2(
!2
)1.2()1.2(
,''' m a x
1
2
2,1-
1
21
e
LeR
ee x
x
故有误差估计因的近似值。插值公式求用数值表如下：已知例
)596.0(
0 2 6 5 2.18 8 8 1 1.06 9 6 7 5.05 7 8 1 5.04 1 0 7 5.0)(
90.080.065.055.040.0
)()( 2.5
fN e w t o n
xf
x
xshxf
k
k
解：先造差商表
6 3 1 9 2.0)5 9 6.0()5 9 6.0(
5 9 6.0
)80.0)(65.0)(55.0)(40.00,0 3 4 (
)65.0)(55.0)(40.00,1 9 7 (
)55.0)(40.00,2 8 0 0 (
)40.0(1 1 6 0.14 1 0 7 5.0
4
4
Nf
x
xxxx
xxx
xx
xN
代入得：将由 Newton公式得四次插值多项式为：
1,熟悉插值法的含义及其几何意义；
2,熟悉 Lagrange插值公式及其余项的使用；
3,会造差表，并熟悉 Nenton插值公式的使用；
4,熟悉差商与导数的关系式 (5.5)。
基本要求：
作业：
作业集（ B）第五章
1,2,4,5．
牛顿基本插值公式对结点是否等矩没有限制,不过当结点等距时前述牛顿插值公式可进行简化,为此先介绍差分概念,
计算方法
§ 5.3 等矩结点插值公式
1.定义 设
nh
xxxx n
ni
0h n ),,0,1,(i i
yyy 210 为 )( xfy? 在 x0 的以 h为 步长一阶向前差分
x 1121 yyy
x 0 0102 yyy……
xyyy iimimim 111 m阶一,差分叫步长称
……
一般,
一阶二阶
(1) 差分可表为函数值的线性组合 (证略 )
h
yxxxx
n
n
n nf !],,,,[
0
210
(2)
),( )( 0)(0 xxfhy nnnn(3)
2.性质,
(2) (证明用归纳法,略 )
3,差分表 (实用 )
yyyyx
yyyx
yyx
yx
yx
ii
0
3
1
2
233
0
2
122
011
00
三阶差分二阶差分一阶差分二 等矩结点插值公式,
,n ),t(0
00
hiht xxxx i
将 Newton插值公式
)())(](,,,[
))(](,,[)](,[)()(
1010
102100100
xxxxxx
xxxxxxxxxN
nn
n
xxxf
xxfxffx
中的差商用性质 (2)换为差分,可整理为如下的
Newton向前插值公式
y
yyxxNN
n
nn
n
nttt
tt
tfthx
0
0
2
000
!
)1()1(
!2
)1(
)()()(
设
（ 5.6）
截断误差可表示为
)()!1( )()1()()( )1(10?fhx nnn ntttthRxR(5.7)
)()1(
)!1(
)()(
1
nt0
1
0
Ma x
h
nttt
n
thRxR
h
M
x
n
n
Newton向后插值公式及 Bessel 插值公式
—— 参考文献
§ 5.4 Hermite插值简介两曲线有公共交点几何上,
n),0,1,(i )()( xxP iin f
前述插值问题,要求被插函数与插值多项式在结点取相同值,
Lagrange型插值条件然而,实际许多问题还常常要求两曲线进一步有共同切线,插值条件为,求一次数 12 n 多项式 )(12 xH n?
,使之满足给定的 Hermite型插值条件
mxH
yxH
iin
iin
)(
)(
12
12
),,1,0( ni (5.8)
y
x0 x0 xi xn
求 )(12 xH n? 不用待定系数法,可设
myH jn jjn
j j
n xxx )()()(
00
12
其中 p n
jj xx
12)(),(,且
—— 插值基函数表示法 （ 5.9）
0)(' ji 0 ji 1)( j xx iij 当当
（ 5.10）
j 0
ji 1)(' 0)(
j?
ixx iij 当当 （ 5.11）
满足条件（ 5.10）和（ 5.11）的多项式（ 5.9）
一定满足（ 5.8），故即为所求所以主要是求插值基函数 )(),( xx
jj
可借用 Lagrange插值基函数 )(xlj 得公式 （ 5.37）
)(
)!22(
)(
)()()( 2 1
)22(
12 xnxxfxR n
n
n
fH
—— 有规律余项易验证：
例 5.3 给定函数值表如下,
3)(
1242)(
321
`
i
i
i
xf
xf
x
.)()()(
)2(,)3,2,1( )()(
:
),(3
3
'
33
3
的表达式并写出截断误差使之满足如下条件的多项式求一次数不超过
xfxHxR
HiifiH
xH
61592)(.
.2:,3)2(
)3)(2)(1()()(
:
673)(
23
3
3
23
2
2
xxxxH
kH
xxxkxpxH
xxxp
故得由条件设所求多项式为得的二次多项式先求满足插值条件方法解
,)3,2,1()()(
,1,
2 iifip
61592
)2)(2)(1(2)2)(1(1)1(22
)(
,
2
5
1
8
3
2
123
42
42
21
,2
23
3
xxx
xxxxxx
xH
N e w t o n 插值公式得由造重节点差商表方法
)3,1( ),3()2)(1(
)!4(
)(
)(
,
)(.3
2
)4(
xxx
f
xR
截断误差为略插值基函数表示法方法问题：结点增多，多项式次数增高，逼近精度越好？未必！多结点高次插值往往在局部误差更大 —— kunge现象。
实用：采用分段低次插值有分段线形，分段二次插值等，几何上 ……
5.5三次样条插值简介
1.分段插值法：
缺点：分段插值函数只能保证连续性，
不能保证光滑性。
折线代替曲线分段插值可以得到整体连续函数，但在连接点处一般不光滑，而 Hermite插值虽然在连节点处一阶光滑，但整体插值由于结点多，次数高而有可能发生龙格现象。
2.三次样条插值既想分段插值，又想在结点处保持光滑，
甚至二阶光滑 —— 三次样条。
希望：
样条来源：
1.定义：在 [a,b]上取 n+1个点 bxxxa
n10
若函数 S(x)满足：
ii yxS?)(
—— 此时 S(x)叫插值函数；
(3) 在内结点或在整个区间上具二阶连续导数。
则称 S(x)为 y=f(x )的三次样条插值函数。
(2) 在每个小区间
ii xx,1?
上是三次多项式；
2,构造：有两种方法，导出三对角方程组，用追赶法。
(1)
熟悉差分的定义，会造差分表；
熟悉等距节点的 Newton插值公式的运用及等距节点的插值余项公式的运用；
熟悉简单的带导数条件的插值（如例 5.3）；
熟悉分段插值法的含义。
基本要求：
作业,
作业集 (B) 第五章 6,7
