西安石油大学计算方法课件1-5章

1、1主讲：爨莹主讲：爨莹2第一章第一章 绪论绪论第二章求方程根的近似方法第二章求方程根的近似方法第三章线性代的方程组解法第三章线性代的方程组解法第五章插值法第五章插值法第六章最小二乘法与曲线拟合第六章最小二乘法与曲线拟合第七章数值积分与数值微分第七章数值积分与数值微分第八章常微分方程初值问题的数值解法第八章常微分方程初值问题的数值解法计计算算方方法法31.11.1计算方法的任务与特点计算方法的任务与特点第一章第一章:绪论绪论实际问题数学问题提供计算方法实际问题数学问题提供计算方法程序设计上机计算结果分析程序设计上机计算结果分析计算方法计算方法 4基本的数学问题基本的数学问题: :1.大型线性代数

2、方程组大型线性代数方程组Ax=b求解求解; 2.矩阵矩阵A的特征值和特征向量计算的特征值和特征向量计算;3.非线性方程非线性方程 求解求解(求根求根);4.积分积分 计算计算;5.常微分方程初值问题求解常微分方程初值问题求解;6.其它。其它。0)( xfdxxfba )(5求精确解求精确解( (值值) )一般非常困难。例如：一般非常困难。例如： 1. 1. 方程组阶数方程组阶数n n很大，例如很大，例如n=20,n=20,计算机运算速度计算机运算速度 1 1亿次亿次/ /秒秒, ,用不好的方法用不好的方法, ,大约需算大约需算3030多万年多万年; ; 好方法不到一分钟。另外，有计算结果可靠性

3、好方法不到一分钟。另外，有计算结果可靠性 问题。问题。2. 2. 特征值定义特征值定义)0(xxAx0 xAx 0)( xIA0| IA63. 3. 形式复杂时求根和求积分很困难。形式复杂时求根和求积分很困难。 4.4.线性微分方程易解，线性微分方程易解， 如如 非线性方程难解，如非线性方程难解，如 )(xf12 yyy1)0()0( yy1sin2 yyyey 1)0()0( yy 希希 望：望： 求近似解，但方法简单可行，行之有效求近似解，但方法简单可行，行之有效 （计算量小，误差小等）。以计算机为工（计算量小，误差小等）。以计算机为工 具，易在计算机上实现。具，易在计算机上实现。计算机运

4、算计算机运算: 只能进行加，减，乘，除等算术运只能进行加，减，乘，除等算术运 算和一些逻辑运算。算和一些逻辑运算。计算方法：计算方法： 把求解数学问题转化为按一定次序只把求解数学问题转化为按一定次序只 进行加，减，乘，除等基本运算进行加，减，乘，除等基本运算 数值方法。数值方法。71.2 1.2 误差基础知识误差基础知识, .!5!3sin53 xxxx.!5)! 3(sin53xxxx一一 .误差来源（分类）误差来源（分类） 1. 模型误差。模型误差。 2. 观测误差。观测误差。 3. 截断误差，如截断误差，如 右端是截断误差。右端是截断误差。84. 4. 舍入误差。计算机字长有限，一般实数

5、不能精确舍入误差。计算机字长有限，一般实数不能精确存储，于是产生舍入误差。例如：在存储，于是产生舍入误差。例如：在1010位十进位十进制数限制下：制数限制下： 舍入误差很小，本课程将研究它在运算过程中舍入误差很小，本课程将研究它在运算过程中 是否能有效控制。是否能有效控制。3333333333.031 ）本应本应33333333333. 031( 0000004. 1)000002. 1(2 ）本本应应（122104040000000000. 0000004. 1040000040000. 1000004. 1000002. 1( 9二误差基本概念二误差基本概念1 1绝对误差。设绝对误差。设

6、准确值，准确值， 近似值。近似值。 称称 为为 的绝对误差。的绝对误差。 为为 的绝对误差限。的绝对误差限。 2 2相对误差。称相对误差。称 为为 的相对误差。的相对误差。 实用中，常用实用中，常用 表示表示 的相对误差。的相对误差。 称称 为为 的相对误差限的相对误差限。x*x*)(xxxe |)(|*xe*x*xxxxree*)(*)( *x*)(xxerxre *)(*x*x103 3有效数字有效数字设设 若若 (1.1)(1.1)则说则说 具有具有n n位有效数字，分别是位有效数字，分别是 若若 ，则称，则称 为有效数。为有效数。)21.0(10*pnmaaaax ), 0(1 pan

7、mxx 1021*xnaaa,21 pn *x11例例1 1. .1 1 设设 =0.0270=0.0270是某数是某数 经经“四舍五入四舍五入”所得，所得，则则 误差误差 不超过不超过 末位的半个单位，即：末位的半个单位，即： 又又 , ,故该不等式又可写为故该不等式又可写为 由有效数字定义可知由有效数字定义可知, , 有有3 3位有效数字，分别位有效数字，分别 是是2,72,7，0 0。*x*)(xe*x41021* xx)270. 0(10*1 x311021* xx*xx12例例1.2 1.2 = 32.93, = 32.89, = 32.93, = 32.89, 故故 有有3 3位有

8、效数字，分别是位有效数字，分别是3,23,2，8 8。由于由于 中的数字中的数字9 9不是有效数字，故不是有效数字，故 不是有不是有效数。效数。 x1102105. 004. 0* xx321021* xx*x*x*x*x13三、有效数位与误差的关系三、有效数位与误差的关系1. 1. 有效数位有效数位n n越多，则绝对误差越多，则绝对误差 越小越小 ( (由定义由定义1.1)1.1)2.2. 定理定理1.1 1.1 若近似数若近似数 具有具有n n位有效数字，则位有效数字，则 (1.2) (1.2) 反之，反之， 若若 则则 至少有至少有n n位有效数字。位有效数字。*)(xenraxe 1*

9、)(10211 nraxe 11*)(10211*x*x14 两边除以两边除以 得得 (1.3)(1.3)和（和（1.41.4）给出了由自变量的误差引起的函）给出了由自变量的误差引起的函 数值的误差的近似式（误差传播）。数值的误差的近似式（误差传播）。四、数值运算的误差估计四、数值运算的误差估计 1. 1. 一元函数情形一元函数情形 设设 则则 ，由，由TaylorTaylor展开公式展开公式 ),(xfy *)*)(*)()(*)(xxxfxfxfyyye *)(*)(*)(xexfye *)(*)(*)( *)(xrxxfxfyree )(*xfy (1.4)(1.4)*)(*)(*)(

10、*)(*)(*xeeerxfxfxyyyr )(*xfy （1.3）152. 2. 多元函数情形多元函数情形 设设 ，),(21nxxxfy *),*,*,(*21nxxxfy *)(*),*,*,(*)(211inniixexxxfye *)(*),*,*,(*),*,*,(*)(21211irinninirxexxxxfxxxfye 2121),(xxxxf 2121,xxxx)(21)21(*maxirirxexxe 21, xx)2()1()21(*xexexxerrr )(*2)1()2()1()*2*1(*xexexexexxerrrrr 则，则，由多元函数的由多元函数的Taylo

11、rTaylor展开公式类似可得展开公式类似可得 （1.51.5） （1.61.6）在（在（1.61.6）式中，分别取）式中，分别取, ,可得可得同号) )（1.71.7） （1.81.8） （1.91.9）(,16例例1.31.3：测得某桌面的长测得某桌面的长a a的近似值的近似值a a* *=120cm,=120cm,宽宽b b的的 近似值近似值b b* *=60cm=60cm。若已知。若已知|e(a|e(a* *)|0.2cm, )|0.2cm, |e(b |e(b* *)|0.1cm)|0.1cm。 试求近似面积试求近似面积s s* *=a=a* *b b* * 的绝对误差限与相对误差限

12、。的绝对误差限与相对误差限。2241 . 01202 . 060|*)(|*|*)(|*|*)(|*)(*)(*)(*)*,(*)(*)*,(*)(cmbeaaebsebeaaebbebbasaeabasse 解解: : 面积面积s=ab,s=ab,在公式（在公式（1.51.5）中）中, ,将将 换为换为 s=abs=ab, , 则则),(21xxfy 相对误差限为相对误差限为%33. 06012024|*)(|*)(| sseser17 1.3 1.3 选用算法应遵循的原则选用算法应遵循的原则1.1.尽量简化计算步骤，减少乘除运算的次数尽量简化计算步骤，减少乘除运算的次数. . 例如，计算多

13、项式例如，计算多项式 通常运算的乘法次数为通常运算的乘法次数为 若采用递推算法若采用递推算法, , 则乘法次数仅为则乘法次数仅为n. n. 又如又如 nnnxaxaaxp .)(102)1(.21 nnn01)()0121( uxp,n-n-kaxuuaunkkknn 100111)111() 1(11000110001 nnnnnn182.2.防止大数防止大数“吃掉吃掉”小数小数 当当|a|b|a|b|时，尽量避免时，尽量避免a+b a+b 。例如，假设计算机。例如，假设计算机 只能存放只能存放1010位尾数的十进制数，则位尾数的十进制数，则3.3.尽量避免相近数相减尽量避免相近数相减 例如

14、，当例如，当x x很大时，应很大时，应 89981040000000000. 0101 . 01004. 010 111 xxxx)1(1111 xxxx， 2cos1sinsincos1xtgxxxx或或 当当x x接近于接近于0 0时，应时，应19 4. 4.避免绝对值很小的数做分母避免绝对值很小的数做分母 当当|b|a|b|a|时，应尽量避免时，应尽量避免 。5. 5. 选用数值稳定性好的算法，以控制舍入误差高速选用数值稳定性好的算法，以控制舍入误差高速 增长增长 例如例如 若若 （误差（误差 ）则计算）则计算 时误差扩大了时误差扩大了 倍倍, ,而而ba nnnIndxxxI51510

15、 1823. 056ln0 I41021 100I1005)1(511nnInI （n=1,2,n=1,2,） 是稳定的。是稳定的。20基本要求：基本要求：1.1.熟悉计算方法在解决实际问题中所处的地位，熟熟悉计算方法在解决实际问题中所处的地位，熟悉计算方法是以计算机为工具求近似解的数值方悉计算方法是以计算机为工具求近似解的数值方法；法；2.2.熟悉绝对误差（限），相对误差（限）及有效数熟悉绝对误差（限），相对误差（限）及有效数字概念；字概念；3.3.熟悉公式（熟悉公式（1.21.2）-（1.91.9）；）；4.4.熟悉选用算法应遵循的原则；熟悉选用算法应遵循的原则；作业：作业： 作业集（作业

16、集（A A）第一章）第一章1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 821 计算方法计算方法 f(x)=0 f(x)=0根或根或f(x)f(x)零点，当零点，当f(x)f(x)复杂时，很难求复杂时，很难求 （找近似有效简单方法）。（找近似有效简单方法）。 第二章第二章 求方程根的近似方法求方程根的近似方法 2.1 2.1 区间二分法区间二分法理理 论论 : f(x) Ca,b,: f(x) Ca,b,单调，单调， f(a)f(b)0 f(a)f(b)0 f(x)=0 f(x)=0在在(a,b)(a,b)有惟一根。有惟一根。根分离：画草图，试算根分离：画草图，试算. . 多项式

17、方程根的模多项式方程根的模 的上下界。的上下界。 22 例例2.1 2.1 用二分法求用二分法求 在在(1,2)(1,2)内的根，要求绝对误差不超过内的根，要求绝对误差不超过 解解： f(1)=-50 -(1,2)+ f(1.25)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.368) 010423 xx21021 f(1.5)0 (1,1.5) nx 1.51 x364. 1368. 1360. 1344. 1313. 1375. 125. 18765432 xxxxxxx2

18、3 364.18* xx若若取取近近似似根根2*1021004. 0)360. 1368. 1(21| xx81,10212|21* nabxxn解解出出对对分分次次数数先先验验估估计计：优点：条件简单优点：条件简单. .缺点：收敛慢缺点：收敛慢. . 不易求偶数重根不易求偶数重根. . 如图如图，则则 （事后估计事后估计）xy24 2.2 2.2 迭代法迭代法连连续续），改改写写建建立立 fxxxf()( 0)(:. 1 01 ,.)2 , 1 , 0( )(xnxxnn取取定定初初值值 ，则则若若收收敛敛，设设极极限限为为则则产产生生数数列列 .,., 121 nnxxxx 一一. 迭代法

19、的建立与收敛性迭代法的建立与收敛性)( )(lim1lim nnnnxx25可作为近似值可作为近似值充分大时充分大时之根，故当之根，故当是是即即1,0)( nxnxf )2lg(2100210)( xxxxxxx或或形式不唯一，如：形式不唯一，如：问题：问题： 收敛性不同。收敛性不同。计算结果见表计算结果见表取取取取4 . 2 3 )2lg(3 2100101 xxxxxnnxnn262.2.收敛定理（定理收敛定理（定理2.22.2）,)(bax 在在设设 为为常常数数）LLxbax(1| )( |,)2( 01101|3 (,2 ,)(1xxLLxxxbaxbaxxnnnn ）（）收收敛敛到

20、到）（；有有唯唯一一根根在在）方方程程则则：（;)(1bxabxa 时时，）当当（27. )(,0)( 1)( ,0)( , ,0)()(,0)()( ),()(1) 唯唯一一故故根根递递增增，又又使使故故至至少少有有则则设设证证： xgxxggbabbbgaaagxxxg 28(2) (2) 1nx，故收敛。，故收敛。 )(00112时时当当 nxLxLnn 中中值值定定理理 nnnnnxLxxx)( )()(1 ( )129）式式（由由（）（）式式）由由（）（）中中值值定定理理01121111111111 2 311)1( 1 ()()( 2)( )()(xxLLxxLLxxLxxLxLx

21、xxxxxxxxLxxxxxxnnnnnnnnnnnnnnnnnnnnnnnn (3)(3) 注：注：L L越小，收敛越快。越小，收敛越快。303 3编程停机判断编程停机判断)(1nnxx （取定初值（取定初值0 x）计算，当）计算，当 nnxx1时，由（）时，由（） 3 3 式知式知 L11 nx 比较小，此时停机，比较小，此时停机，1n x 二、迭代加速公式（略）二、迭代加速公式（略） 由由31 2.32.3Newton Newton 迭代法迭代法一一 Newton Newton 迭代法迭代法 1.1.迭代公式建立迭代公式建立)(xf 在在nx 点点TaylorTaylor展开展开 )(

22、)( )()()(! 2)()( )( )()(2nnnnnnnnxxxfxfxfxxxfxxxfxfxf TaylorTaylor展开线性化（重要思想）展开线性化（重要思想）0)( xf近似于近似于0)()( )( nnnxxxfxf解出解出 记为记为1nx，则，则) 1 . 2(), 2 , 1 , 0( )( )(1 nxfxfxxnnnn1 nx 将将x322.Newton2.Newton迭代法的几何意义迭代法的几何意义 过过) )(,(nnxfx 切线切线 )()( )(nnnxxxfxfy 与与 0 y求交点，解出求交点，解出1 nxx , 则则)( )(1nnnnxfxfxx 3

23、33. Newton3. Newton迭代法收敛定理（定理迭代法收敛定理（定理 2.62.6）0)( xf在在 ba,有根有根，且，且)(xf在在 ba,（1 1）)(),( xfxf连续，且分别不变号；连续，且分别不变号； bax,0 , ,使使则则 Newton Newton 迭代法（迭代法（2.12.1）产生的数列）产生的数列 1 nx的收敛到根的收敛到根。0)(, 0)(, 0)( 0 xfxfxf 为例证明（其它情况类似）为例证明（其它情况类似） （2 2） 取初值取初值设设0)()(00 xfxf 证：证：以以34将将在在)( f nx处处TaylorTaylor展开展开12122

24、)()( 2)()()( 2)()( )(0)(! 2)()( )()( nnnnnnnnnnnnnnnnxxxffxxxffxfxfxxfxxfxff 说明数列说明数列1nx 有下界有下界 又又nnnnnxxfxfxx )( )(1 故故 1 nx单调递减。单调递减。 1 nx收敛。设收敛。设xxnn 1lim则由（则由（2.12.1），）， xxfxfxfxx, 0)(,)( )(，35例例2.22.2 解：设解：设, 0,2 cxcx则则取取cxxf 2)(，则由（，则由（2.12.1）)(21221nnnnnnxcxxcxxx )0( cc用用 Newton Newton 迭代法求迭代

25、法求36基本要求基本要求1.1.熟悉区间分法；熟悉区间分法；2.2.熟悉迭代法的建立，会使用收敛定理；熟悉迭代法的建立，会使用收敛定理；3.3.熟悉熟悉NewtonNewton迭代法及其几何意义和收敛条件。迭代法及其几何意义和收敛条件。作业：作业： 作业集（作业集（B B）第二章）第二章1 1、2 2、3 3、4 4、6 637 计算方法计算方法二二. .迭代法的收敛阶迭代法的收敛阶( (收敛速度收敛速度) ) 1. 1.定义定义: :设设.lim nnx 若有实数若有实数p0,p0,使使)0( |lim1 ccxxpnnn 则称则称xn p p阶收敛阶收敛, ,相应的迭代法称为相应的迭代法称

26、为p p阶方法阶方法. . 特别特别, , p=1p=1时叫线性收敛时叫线性收敛, ,p=2p=2时叫平方收敛时叫平方收敛. . p p越大越好越大越好(why?)(why?)382.2.定理定理2.72.7线性收敛；线性收敛；则则（且且）（若若。的根的根收敛到收敛到设设)(, 0)(), 2 , 1 , 0()( (1)111xxxxnnnncxxxn 至至少少二二阶阶收收敛敛。（即即的的单单根根迭迭代代法法求求则则)0)( 0)( fxfNewton 的的条条件件成成立立）设设定定理理（6 .2239 所以，此时所以，此时NewtonNewton法至少二阶收敛法至少二阶收敛. . 线性收敛

27、线性收敛）证：（证：（)(0)( )( )()(11111nnnnnnnnnxxaxxxxx (2)(2)由由2.62.6的证明有：的证明有：故故,)()( 2)(21nnnnxxffx )( 2)()( 2)(21 ffxffxxnnnn 0)()(00)()(0 ff若若大大于于二二阶阶收收敛敛若若二二阶阶收收敛敛403. Newton3. Newton法改进：法改进：则则重根重根有有设设)2(0)( mmxf2.4 2.4 弦截法弦截法( (略略) ) )( )(1xxxxnnnnffm 。收敛时至少是二阶收敛收敛时至少是二阶收敛41第三章第三章 线性代数方程组解法线性代数方程组解法解线

28、性方程组解线性方程组 bAx x解解向向量量列列迭迭代代法法：格格式式，无无穷穷序序误误差差，有有限限步步，精精确确解解直直接接法法：理理论论，无无舍舍入入42一、一、 GaussGauss消去法消去法设设 有有1,22111,2211)1 .3(1,222221211,11212111 nnnnnnnnininiinnnnnnaxaxaxaaxaxaxaaxaxaxaaxaxaxa行行。行行，加加到到第第第第把把化化为为零零；将将用用 1),2(111111iaaniaaii 以以后后各各步步类类似似。或或题题：问问?001111 aa线性代数：方法不好时工作量非常大，线性代数：方法不好时工

29、作量非常大， 工作量小的方法是工作量小的方法是 Gauss Gauss 消去法。消去法。消消 元：元： 3.13.1直接法直接法43二二 列主元素消去法列主元素消去法-计算结果可靠计算结果可靠jjrjjrjjiniracaacaraar1113211max)1(1111111 行行：，对对调调使使找找行行号号)1n,1,2,j( ）；（个个元元素素成成为为行行第第第第行行加加到到第第行行第第为为消消消消元元：用用1,2 , 1,3 ,2,1:01111111111 njniaaaaajiiaaaaijijijii44到此原方程组化为到此原方程组化为1,22 1,22 1,222221, 112

30、12111 nnnnnnninininnnnnnaxaxaaxaxaaxaxaaxaxaxa 45 到此原方程组化为到此原方程组化为.2max)2(222222行行，对对调调，使使找找raarinir ），；，（行行，则则第第行行第第消消为为把把消消元元：用用1,3 , 2,4 , 3 2:), 4 , 3( 02222222222 njniaaaaaiaaniaaijijijii1,33 1,33333 1,223232221,11313212111 nnnnnnnnnnnnnnnaxaxaaxaxaaxaxaxaaxaxaxaxa46（3.3) 3.3) 是回代过程。是回代过程。( (上三

31、角方程组上三角方程组) ) （3.2)3.2)1, 1,222221, 11212111 nnnnnnnnnnnaxaaxaxaaxaxaxa(n) (n) 回代求解公式回代求解公式 (n-1) (n-1) 原方程组化为原方程组化为以上为消元过程。以上为消元过程。 （3.3)3.3)1, )1,.,2, 1(1 11,1, nnnnnaxannkxaaaxaaxnkjjkjnkkkknnnnn47三、三、 Gauss Gauss 全主元消去法：全主元消去法： 优点优点-计算结果更可靠；计算结果更可靠； 缺点缺点-挑主元花机时更多，挑主元花机时更多， 次序有变动，程序复杂。次序有变动，程序复杂。

32、说明：说明： (1)(1)也可采用无回代的列主元消去法也可采用无回代的列主元消去法( (叫叫Gauss-Gauss- -Jordan -Jordan消去法消去法) )，但比有回代的列主元消，但比有回代的列主元消 去法的乘除运算次数多。去法的乘除运算次数多。 (2)(2)有回代的列主元消去法所进行的乘除运算有回代的列主元消去法所进行的乘除运算 次数为次数为 ，量很小。，量很小。nnn313123 nxx,148 四、应用四、应用 （1）求行列式）求行列式 （2）求逆矩阵）求逆矩阵 ( (以上过程都以上过程都应选主元应选主元) ) nnmnnnmnnnnbbbbbaaaa.) 1(.) 1(.11

33、1111111 )(.)(1 AEEA49 uALLLLgubALLLLgubAKKkk 121121)|()|()1|()|()|(uLLLLAKK1121)( 记记11)( LLLK，则，则LUA 上上三三角角）（下下三三角角 （三角因子分解）（三角因子分解） Gauss Gauss消元，初等行变换，化原方程组为上三角型。消元，初等行变换，化原方程组为上三角型。五矩阵三角分解法五矩阵三角分解法50定义定义3.13.1 LUA 叫叫A的三角（因子）分解，其中的三角（因子）分解，其中 是是L是上三角。是上三角。U下三角下三角, , L为单位下三角阵（对角元全为为单位下三角阵（对角元全为1 1）

34、，），U为上三角阵，则称为上三角阵，则称LUA 为为DoolittleDoolittle分解分解; ;L若若 是下三角，是下三角，U 是单位上三角，则称是单位上三角，则称LUA 定理定理3.1 n3.1 n阶阵阶阵)2( nA 有唯一有唯一DoolittleDoolittle分解分解( (CroutCrout）A 的前的前n-1n-1个顺序主子式不为个顺序主子式不为0 0. .（证略）（证略）三角分解不唯一三角分解不唯一, ,为此引入为此引入定义定义3.2 3.2 若若 为为CroutCrout分解。分解。51 为什么要讨论三角分解？若在消元法进行前能实为什么要讨论三角分解？若在消元法进行前能

35、实 现三角分解现三角分解LUA ， 则则 bxLUbAx)(上三角方程组）上三角方程组）下三角方程组）下三角方程组）( ( yUxbLy 容易回代求解容易回代求解52回代求解很容易，如回代求解很容易，如 2,1)1,-n(k n),2,3,(k 1 1111111212121222111 kknkjjkjkknnnnkjjkjkkkknnnnnnuxubxuyxylblylbybbbyyyllllll练练习习：53基本要求：基本要求： 1. 1. 熟悉收敛阶的定义；熟悉收敛阶的定义； 2. 2. 熟悉熟悉NewtonNewton法及改进方法的收敛阶；法及改进方法的收敛阶； 3. 3. 熟悉列主

36、元消去法解线性方程组的计算熟悉列主元消去法解线性方程组的计算 过程；过程； 4. 4. 熟悉矩阵三角分解中熟悉矩阵三角分解中DoolittleDoolittle分解和分解和 CroutCrout分解定义；分解定义； 5. 5. 熟悉利用三角分解来求解线性方程组的熟悉利用三角分解来求解线性方程组的 思路；思路；作业：作业：作业集（作业集（A A） 第三章第三章 1 1，2 2 54nnnnnnaaaaaaaaa212222111211计算方法计算方法1 1直接三角分解法（以直接三角分解法（以DoolittleDoolittle分解为例）设分解为例）设1112121nnlllnnnnuuuuuu2

37、2211211 55由矩阵乘法由矩阵乘法221212222221211212222121111111111111/ )( 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(uulalaululiuLLulauauuljuLuniualauliuiLauajjuLuiiiiiijjjjjjiiiijjjj （列列的的第第行行的的第第列列：用用的的第第求求（列列的的第第行行的的第第行行：用用的的第第求求列列（的的第第行行的的第第列列：用用的的第第求求（列列的的第第的的第第一一行行行

38、行：用用的的第第求求56 (k) 111121,2,1100)0 ,0,(n),1,kk,(j1kmmjkmkjkjkjkjkmmjkmkjjjkjjjkkkkulauauulauuuullljukLku，列列的的第第行行的的第第行行：用用的的第第求求57 kkkmmkimikikikkkikkmmkimikkkkkkkikiuulalaululauuulllkuiLkL 111121,100)00(n),1,k(i2，即，即列列的第的第行行的第的第列：用列：用的第的第求求58), 3 , 2(), 1( ), 1,( ), 3 , 2( ), 2 , 1( 1111111111nknkiau

39、ulalnkkjaulauniualnjauDoolittleikkkkmmkimikikkjkmmjkmkjkjiijj 分解公式分解公式59例例3 31 112/ )126(23/ )06(, 111 1661230 3 22 1 251865364 5 42 1 2231323 xxxxxx所以所以选主元的三角分解法（略）选主元的三角分解法（略）602 2平方根法平方根法定理定理3.23.2 设设A A对称正定，则有非奇异下三角阵对称正定，则有非奇异下三角阵L L，使，使TLLA - - 理论基础理论基础 ( (证略）证略）分解方法：设分解方法：设jiijnnnnnnnnnnnnnnaa

40、llllllllllllaaaaaaaaa 其其中中 2221211121222111212222111211( choleskey( choleskey分解分解) )6122121222222212121222222222111111111111111111 n),3,4,(j j2L )2 22L 1) )2( n),2,(j j1L )2 )( )1 )1(2222lllalaallllLlalallLlalaallLalaljjjjjjjTTjjjjjT 列列第第行行第第列列第第行行第第列列第第行行第第取取正正由由矩矩阵阵乘乘法法62及及其其改改进进分分解解。缺缺点点：开开方方运运算算

41、。主主元元。平平方方根根法法稳稳定定，不不必必先先受受到到控控制制舍舍入入误误差差的的放放大大所所以以说说的的最最大大元元的的值值不不会会超超过过程程中中这这说说明明在在分分解解过过故故列列：第第行行、第第、计计算算量量小小优优点点：）（，可可得得：TkmkknkkmkknkkkkmkmkmkkkmjmkmjkkkjmkmkmkkkklalaallakknkjllalllalkLDL,A maxmax21, 11)(21121211112 63六、解三对角方程组六、解三对角方程组追赶法追赶法 1111 1, 2 2212111221111222111112112111122211nnnnnnn

42、nnnnniiinnnnnnnnnbacbacbacbniabcabcbffffxxxxbacbacbacb 设设有有分分解解）（，且且按按行行严严格格对对角角占占优优：（三三对对角角方方程程组组）给给定定( Crout分解分解 )64列得：列得：第第行行第第，）（由矩阵乘法由矩阵乘法1, 1)(1)2(2112221222222222212221111111111 iiiiicbacbacbcb 65 00 00i i 11111 iiiii ii1 ,1 .,1 .1iiiiiiba , ,ciii 故有故有 ,111111 iiiiiiiiicbacb ), 3 , 2(ni (3.1)

43、 fLUxfAx （二二对对角角方方程程组组）二二对对角角方方程程组组） ( yUxfLy )1, 3 , 2( ni66解解n)2,3,(i , 1111y iiiiiyffyfLy设设解解得得 yUx 1)1,-n(i ,1 xyxyxiiiinn (3.1) (3.1) (3.3) (3.3) 叫追赶法，工作量小，非常有效。叫追赶法，工作量小，非常有效。(3.2)(3.2)（3.33.3）67基本要求基本要求1.1.会矩阵的直接三角分解法的过程（不记公式）；会矩阵的直接三角分解法的过程（不记公式）；2.2.熟悉平方根法的计算过程（不记公式）及其优缺熟悉平方根法的计算过程（不记公式）及其优

44、缺 点。点。作业：作业： 作业集（作业集（A A） 第三章第三章 3.3.68bAx 一一. .简单迭代法简单迭代法 1.1.迭代法建立迭代法建立. . 考虑考虑gBxxbAx ( (矩阵矩阵B B不唯一不唯一) )对应写出对应写出 )0()()1()4 . 3( ), 2 , 1 , 0( xkgBxxkk取取定定初初始始向向量量 3.2 3.2 解线性方程组的迭代法解线性方程组的迭代法 计算方法计算方法产生向量序列产生向量序列,)1()()2()1( kkxxxx若收敛若收敛, ,记记xxkk )1(lim69则于则于(3.4)(3.4)两端取极限有：两端取极限有：, gxBx 上式说明：

45、上式说明： 是解向量是解向量 , ,从而当从而当k k充分大时充分大时 )1(kx注意注意: : 迭代阵迭代阵B B不唯一不唯一, ,影响收敛性。影响收敛性。 解向量解向量(3.4)(3.4)叫简单迭代法叫简单迭代法,B,B叫迭代矩阵。叫迭代矩阵。 2.2.收敛性收敛性. . 定义定义3.3 3.3 称称| )(|max)(1BBini 为矩阵为矩阵B B的谱半径。的谱半径。定理定理3.3 3.3 简单迭代法简单迭代法（证证略略）（都都收收敛敛对对任任意意初初始始向向量量 1 )0()()1( BxgBxxkk xxx70都都不不收收敛敛”。时时不不能能说说“对对任任意意）（注注意意)0(1:

46、xB 收收敛敛。则则其其对对任任意意或或若若对对迭迭代代法法)0(11111)()1( 1|max| 1|max|, ),2, 1 ,0( xbBbBkgBxxnjijniniijnjkk 定理定理3.43.4 ),2 , 1( | |,|max |max| )( )4 .3(1|)1()(1k1)(11)()1(1)()1(niBxxxxxxbxxbxxxxbxxgBxxBkikijkjnjnjjkjijninjjkjijikinjjkjijiki 则则记记相相减减有有与与为为例例。将将证证：以以71 收敛列解收敛列解 (i=1,2,(i=1,2,n),n)( 0011时时当当 kBBkkk

47、 klim|max)1(1xxikini xki)1( xi即即=0,=0, 例例3.2 3.2 设有方程组设有方程组( ( 其中其中 ) Ax=b,) Ax=b,即即 aii0 a11bxaxaxnn111212 bxaxaxann22222121 bxaxaxannnnnn 2211(3.5)(3.5) 作等价变形作等价变形 xaxaxbaxnn1212111110 1 xaxxabaxnn2212122220 1 xaxabaxnnnnnnn0 2111 (3.6)(3.6)72-Jacobi-Jacobi迭代法迭代法.01)(1)(212)(1111)1(1knnkkkxaxaxbax

48、 .01)(2)(2)(1212)1(222knnkkkxaxxabax 0.1)()(22)(11)1(knknknnnnknxxaxabax 于是有迭代公式于是有迭代公式(k=0,1,2,(k=0,1,2,) )(3.7)(3.7)73矩阵形式为：矩阵形式为： nnnkkknnnnnnnnknkkabababxxxaaaaaaaaaaaaxxx2221112212122222211111112)1()1(2)1(1 000.)7 . 3(, 1|1|)2(1)()7 . 3()1(:)0(1)0()()1(收收敛敛对对任任意意迭迭代代法法则则或或若若收收敛敛对对任任意意迭迭代代法法迭迭代代

49、法法收收敛敛性性简简记记为为xJacobiBBBxJacobiJacobigxBxJJJkJk 74 (3) (3)设方程组（设方程组（3.53.5）的系数矩阵）的系数矩阵A A按行严格对角占优即：按行严格对角占优即： n),1,2,(i , 1 nijjijiiaan),1,2,(j , 1 njiiijjjaa 或按列严格对角占优，即或按列严格对角占优，即二、二、 迭代法迭代法 设有简单迭代法设有简单迭代法 即即Seidel,)()1(gBxxkk nknnnknknknknnkkkknnkkkgggxbxbxbxxbxbxbxxbxbxbx )()(22)(11)1(2)(2)(222)

50、(121)1(21)(1)(212)(111)1(1(3.8)(3.8) )( )7 . 3( )0(证证明明留留作作练练习习收收敛敛对对任任意意迭迭代代法法则则xJacobi75 称如下迭代法称如下迭代法 (3.9)(3.9)nknnnknknknknnkkkknnkkkgggxbxbxbxxbxbxbxxbxbxbx )()1(22)1(11)1(2)(2)(222)1(121)1(21)(1)(212)(111)1(1 为与为与(3.8)(3.8)对应的对应的 迭代法，其迭代矩阵迭代法，其迭代矩阵 可用可用 “ “代入法代入法”求得。求得。SeidelBs76 （1 1） 迭代法迭代法(

51、3.9)(3.9)对任意对任意 收敛收敛（2 2）若）若 则则 迭代法迭代法(3.9)(3.9)对对 任意任意 收敛；收敛；（3 3）若简单迭代法）若简单迭代法(3.8)(3.8)的迭代矩阵的迭代矩阵 满满 足足 或或 ，则相应的，则相应的SeidelSeidel迭代法迭代法 (3.9)(3.9)对任意对任意 收敛（证略）收敛（证略） SeidelSeidelx)0(; 1)( Bs , 111 BBss或或Seidelx)0()(bBijnn 11 B1 Bx)0(迭代法迭代法(3.9)(3.9)的收敛性的收敛性77 例例3.3 3.3 迭代方法迭代方法 （3.103.10） )()1(22

52、)1(11)1()(2)(2)1(121222)1(2)(1)(212)(1111)1(10 1 0 10 1knknknnnnknknnkkkknnkkkxxaxabaxxaxxabaxxaxaxbax 称为与称为与JacobiJacobi迭代法（迭代法（3.73.7）对应的）对应的SeidelSeidel方法方法, , 其收敛情况如下：其收敛情况如下：(1)(1)使用一般的使用一般的SeidelSeidel方法（方法（3.93.9）的收敛性判别法）的收敛性判别法(2)(2)若系数矩阵若系数矩阵A A对称正定，则求解方程组（对称正定，则求解方程组（3.53.5）的）的 与与JacobiJac

53、obi迭代法对应的迭代法对应的SeidelSeidel方法（方法（3.103.10）对任意）对任意 收敛。收敛。 （证略）（证略）)0(x78 松弛因子松弛因子, =1 , =1 即即SeidelSeidel方法方法(3.10)(3.10)(3)(3)若系数矩阵若系数矩阵A A按行（或按列）严格对角占优，按行（或按列）严格对角占优， 则求解（则求解（3.53.5）的与）的与JacobiJacobi方法对应的方法对应的ScidelScidel 方法方法(3.10(3.10）对任意）对任意 收敛收敛. . （练习）（练习）)0(x (3.11)(3.11)是一种加权平均。是一种加权平均。 1)1(

54、111)()1()()1( ijnijkjijkjijiiikikixaxabaxx 三三. .逐次超松弛迭代法逐次超松弛迭代法(SOR(SOR法法) )(3.11) ),2,1(ni 79SORSOR方法的收敛性如下（不加证明）：方法的收敛性如下（不加证明）：(1)SOR(1)SOR方法对任意方法对任意 都收敛的必要条件是：都收敛的必要条件是： (2)(2)若系数矩阵若系数矩阵A A对称正定，则对称正定，则 时时SORSOR方法方法 求解求解 对任意对任意 收敛；收敛；(3)(3)若系数矩阵若系数矩阵A A按行（或按列）严格对角占优，按行（或按列）严格对角占优， 则则 时时SORSOR方法对

55、任意方法对任意 收敛。收敛。最佳松弛因子最佳松弛因子 选取问题。选取问题。20 bAx )0(x10 opt 20 )0(x)0(x80 例例3.4 3.4 用用SeidelSeidel迭代法求解方程组迭代法求解方程组 1015352111021210321xxxTx)0 , 0 , 0()0( 10max3)()1(31| xxkikii解解：因为系数矩阵严格对角占优，故因为系数矩阵严格对角占优，故SeidelSeidel方方 法对任意法对任意 收敛。收敛。取初始向量取初始向量, ,要求要求 时迭代终止。时迭代终止。 Seidel Seidel迭代格式为迭代格式为)0(x 24 . 02 .

56、 0, 2 , 1 , 0 5 . 11 . 02 . 03 . 01 . 02 . 0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1 kkkkkkkkkxxxkxxxxxx81计算结果可列表如下计算结果可列表如下TTTTTTT)(3)(2)(1)(2.99998) 1.99998 (0.9999662.99988) 1.99985 (0.9997052.99914) 1.99894 (0.9978242.99375) 1.99224 (0.9842832.95387) 1.94448 (0.8804022.68400) 1.56000 (0.3000010) 0 0(0)

57、,(Tkkkkxxxxk 注意：未必注意：未必SeidelSeidel方法一定比方法一定比JacobiJacobi方法好。方法好。99998. 2 , 99998. 1 , 99996. 0, )321( 10|32163)5()6( xxxx,ixxii为为近近似似解解，即即故故因因为为）（821 1 熟悉简单迭代法及其收敛条件的使用；熟悉简单迭代法及其收敛条件的使用；2 2 熟悉熟悉JacobiJacobi迭代法及其相应的迭代法及其相应的SeidelSeidel迭代法的迭代法的 计算公式以及它们的收敛条件；计算公式以及它们的收敛条件；3 3 熟悉熟悉SORSOR方法的计算公式及其收敛条件；

58、方法的计算公式及其收敛条件；作业：作业：作业集作业集(A) (A) 第三章第三章 4 4，5 5，6 6，7 7基本要求：基本要求：83 计算方法计算方法 叫叫截截断断误误差差叫叫插插值值结结点点插插值值法法插插值值条条件件使使被被插插函函数数近近似似代代替替插插值值函函数数用用简简单单函函数数望望希希只只知知离离散散数数据据但但未未知知存存在在连连续续实实际际中中问问题题提提出出)()()(,)()(,)()(:),.,2, 1 ,0( )(, ,)(,:.1xxfxRxxfxxfxnixfyxfyiiiii )()()(多多项项式式插插值值代代数数插插值值为为多多项项式式函函数数或或者者取

59、取三三角角插插值值为为三三角角函函数数通通常常取取xx 第五章第五章 插值法插值法84.)( ),.,2 , 1 , 0( )()( 1:1 . 5 . 2存存在在且且唯唯一一的的多多项项式式的的次次数数不不超超过过处处满满足足插插值值条条件件节节点点互互异异个个在在定定理理性性插插值值多多项项式式的的存存在在唯唯一一xpnnkxfxpxnnkknk )(. . )(. )(. : .)(:10111100001010nnnnnnnnnnnnxfxaxaaxfxaxaaxfxaxaaxaxaaxp 代代入入插插值值条条件件得得设设证证85.)( , 0)(111 :01100存存在在唯唯一一系

60、系数数即即多多项项式式该该方方程程组组解解存存在在唯唯一一法法则则知知故故由由系系数数行行列列式式Grammerxxxxxxxxnijjinnnnn 注注: :一次多项式插值一次多项式插值 - - 过两点直线过两点直线; ; 二次多项式插值二次多项式插值 - - 过三点抛物线过三点抛物线; ; 不用待定系数法不用待定系数法 - (1)- (1)计算量大计算量大;(2);(2)不易讨论误差不易讨论误差; ;3. 几何意义：两条曲线有交点（公共点）几何意义：两条曲线有交点（公共点）86一一. .插值基函数插值基函数. .上上满满足足个个结结点点在在次次多多项项式式个个若若定定义义ikxnnkxln