数值分析复习学习教案

1、会计学1数值数值(shz)分析复习分析复习第一页，共181页。第三章 线性方程组的直接(zhji)法第四章 线性方程组的迭代法第一章 绪论(xln)第二章 非线性方程(fngchng)求根第五章 函数插值第六章 函数逼近第七章 数值积分数值微分第八章 常微分方程数值解法第九章 特征值特征向量内容提要第1页/共181页第二页，共181页。第2页/共181页第三页，共181页。第3页/共181页第四页，共181页。第4页/共181页第五页，共181页。第5页/共181页第六页，共181页。第一章第一章 要点要点(yodin)回顾回顾1 误差误差(wch)的概念的概念绝对误差、相对误差、有效数字定义

2、及相互(xingh)关系：2 误差的传播（数值运算的误差估计）误差的传播（数值运算的误差估计）一元函数、多元函数误差的近似泰勒估计：3 误差定性分析误差定性分析条件数、算法的数值稳定性。4 算法设计注意事项算法设计注意事项第6页/共181页第七页，共181页。算法设计要点数值方法的稳定性数值方法的收敛性算法多元函数一元函数传播有效数字相对误差（限）绝对误差（限）度量截断误差舍入误差误差的产生误差误差与算法第7页/共181页第八页，共181页。第一章第一章 重点重点(zhngdin)掌握掌握 绝对误差绝对误差(ju du w ch) (ju du w ch) 设设x x* *是准确值是准确值x

3、x的一个近似，称的一个近似，称 xxxe*)(为 x* 近似(jn s)x的绝对误差，简称为误差。在不引起混淆时，简记符号 为 )(*xe*e)(*x如果存在着的正数使得有绝对误差 *xxe则称 *为x*近似x的一个绝对误差限绝对误差限，简称误差限。第8页/共181页第九页，共181页。相对误差相对误差 设设x*是准确值是准确值x 的一个的一个(y )近似，称近似，称 xxxxer*)(为x* 近似(jn s)x的相对误差。因)()(2*rexxexxxxexexexee)()(1122*r*eOxexe 称数值 的上界为相对误差限相对误差限，记为 *re*r第9页/共181页第十页，共181

4、页。有效数字有效数字 设设x的近似值的近似值x* 有如下有如下(rxi)标准形式标准形式 ia 0,1,2,9其中m为整数， 且 1a0,np 如果(rgu)有nm21*10e xx*则称x* 为x的具有n位有效数字位有效数字的近似数， 121100.mnnpxa aa aa 第10页/共181页第十一页，共181页。定理定理 设设x的近似的近似(jn s)数数x*具有标准形式：具有标准形式：111102*nrea121100.mnnpxa aa aa 若x*具有(jyu)n位有效数字，则相对误差 若相对误差 111102(1)*nrea则x*至少具有n位有效数字。第11页/共181页第十二页

5、，共181页。用用TaylorTaylor公式分析公式分析(fnx)(fnx)误差传播规律误差传播规律 *1x*2x*nx当 ， ， 很好地近似了相应的真值时，利用多元函数的一阶Taylor公式可求得y* 的绝对误差和相对误差分别为 设可微函数中 的自变x1、x2、xn是相互独立的。函数值y的近似值为),(*2*1*nxxxfy),(*2*1nxxxfy第12页/共181页第十三页，共181页。n1ii*i*n*1i*)(,()(xxxxfyyyen1i*i*n*1i)(),(xexxfn1i*i*i*n*1i*i*)(),()()(xxexxfyxyyeyern1i*i*n*1i*i)(),

6、(xexxfyxr第13页/共181页第十四页，共181页。用算术运算的误差用算术运算的误差(wch)估计估计)()()(*2*1*2*1xxxx)()()(*2*1*1*2*2*1xxxxxx)0()()()(*22*2*2*1*1*2*2*1xxxxxxxx算术运算的绝对误差算术运算的绝对误差(ju du w ch)(ju du w ch)传播传播第14页/共181页第十五页，共181页。算术运算的相对误差算术运算的相对误差(xin du w ch)传播传播),0(),(),(max)(*2*1*2*1*2*1xxxxxxrrr),0(),()()(*2*1*2*1*2*1xxxxxxrr

7、r),0(),()()(*2*1*2*1*2*1xxxxxxrrr第15页/共181页第十六页，共181页。,) 1(1111xxxx,111xxxx,1lnln) 1ln(xxxx。)1ln()1ln(22xxxx第16页/共181页第十七页，共181页。例1 已知数 x=2.718281828.,取近似值 x*=2.7182,那麽x具有(jyu)几位有效数字解；*31 42.7182818282.71820.00008182110.0005101022exx故有四位(s wi)有效数 点评；考查的有效数字的概念。第17页/共181页第十八页，共181页。*1233.105,0.001,0.

8、100 xxx *123xxx例2有效数试确定的相对误差限。*123123*123333()()()()1111010102220.00049933.1050.001 0.100re xe xe xe xxxxxx解： 点评(din pn)；此题考查相对误差的传播。*1()()()nrriiiifeye xxyx*112233123123*123123()()()()()()()rrrrexxexxexxe xe xe xe xxxxxxxxx第18页/共181页第十九页，共181页。例3sin1有2位有效数字(yu xio sh z)的近似值的相对误差限是 .解法1：根据有效数字(yu xi

9、o sh z)与相对误差限的关系 2 111110100.006252 816r 解法2：相对误差(xin du w ch)限的概念 2*1100.840.00595242rx点评；此题考查相对误差与有效数字关系第二种按定义得到的结果更好第19页/共181页第二十页，共181页。*nx*x例例4的相对误差为的相对误差为的相对误差的的相对误差的-倍。倍。*1()()()nrriiiifeye xxyx*1(*)(*)()/*nnnrrexxe x xxn解：根据误差解：根据误差(wch)传播公式传播公式则有则有 点评；考查一元函数相对误差(xin du w ch)传播。第20页/共181页第二十

10、一页，共181页。第21页/共181页第二十二页，共181页。第二章第二章 要点要点(yodin)回顾回顾1 二分法二分法二分法计算二分法计算(j sun)过程、二分法先验误差：过程、二分法先验误差：2 不动点迭代法（普通不动点迭代法（普通(ptng)迭代法）迭代法）不动点格式构造不动点格式构造：3 牛顿迭代法牛顿迭代法牛顿迭代公式牛顿迭代公式不动点收敛性不动点收敛性：（局部收敛性、全局收敛性）：（局部收敛性、全局收敛性）不动点加速不动点加速：Aiteken加速加速牛顿迭代的局部收敛性和全局收敛性；牛顿迭代的局部收敛性和全局收敛性；牛顿迭代公式的变形（非重点）牛顿迭代公式的变形（非重点）第22

11、页/共181页第二十三页，共181页。非线性方程数值解法基本概念（单根、重根、收敛阶）求根方法二分法及其收敛性二分法及其收敛性简单迭代法简单迭代法简单迭代法的加速简单迭代法的加速Newton迭代法迭代法Newton迭代法的变形迭代法的变形重根Newton迭代法Newton下山法割线法迭代格式收 敛 性 定理误差估计迭代格式收 敛 性 定理误差估计知识(zh shi)结构图第23页/共181页第二十四页，共181页。方程 的解 称为方程 的根或称为 的零点，若 其中m为正整数， 满足 ，则显然 这时称 为 的m重零点，或称 为 的m重根。 0 xf*x 0 xf xf xgxxxfm* xg 0

12、 xg 0*xf*x xf*x 0 xf定理：若 只有m阶连续导数，则 是的m重零点的充要条件为： ， xf*x xf 0*xf0)(0)(0)(*)(*)1(*xfxfxfmm第二章第二章 重点重点(zhngdin)掌握掌握第24页/共181页第二十五页，共181页。二分法执行二分法执行(zhxng)步骤步骤1计算计算f (x)在有解区间在有解区间(q jin)a, b端点处的值，端点处的值，f (a)，f (b)。2计算计算(j sun)f (x)在区间中点处的值在区间中点处的值f (x1)。3判断若判断若f (x1) = 0，则则x1即是根，否则检验即是根，否则检验：（1）若若f (x1

13、)与与f (a)异号异号，则知解位于区间则知解位于区间a, x1， b1=x1, a1=a;（2）若若f (x1)与与f (a)同号同号，则知解位于区间则知解位于区间x1, b， a1=x1, b1=b。反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：(a, b), (a1, b1), , (ak, bk), 第25页/共181页第二十六页，共181页。4、当当11kkab时时)(211kkkbax5、则、则即为根的近似即为根的近似), 2 , 1()(211*1kabxxkk先验误差先验误差(wch)估计：估计：理论理论(lln)基础：基础：定理定理1 1：设函

14、数：设函数 f (x) f (x) 在区间在区间a, ba, b上连续，如果上连续，如果f (a) f (a) f (b) 0 f (b) 0， 则方程则方程(fngchng) f (x) = 0 (fngchng) f (x) = 0 在在a, ba, b内至少有一实根内至少有一实根x x* *。 第26页/共181页第二十七页，共181页。简单简单(jindn)(jindn)迭代法迭代法f (x) = 0 x = g (x)等价变换等价变换构造迭代构造迭代(di di)(di di)格式格式x = g (x)(1kkxgx则对于任意的初值x0S，迭代公式 产生的序列 必收敛于方程的根 。*

15、x11(),0,1,2kkxg xkkx( )g x|*xxxS（1）迭代函数(hnsh) 在 的邻域可导；定理定理2.（局部收敛定理）设 是方程 的根，满足：( )xg x( )1g xL（2）在 的某个邻域 ，对于任意xS，有*x*x*x第27页/共181页第二十八页，共181页。定理：如果定理：如果 (x) (x)满足下列条件满足下列条件（1 1）当）当x xa, ba, b时，时，(x)(x)a, ba, b（2 2）当任意）当任意x xa, ba, b，存在，存在0 L 10 L1)阶阶导函数连续，则当初值导函数连续，则当初值x0 0充分靠近充分靠近时，时，迭代法迭代法为为p 阶收敛

16、的充要条件是阶收敛的充要条件是0)(, 0)()()()()1( pp第29页/共181页第三十页，共181页。)()(1kkkkxfxfxx 牛顿牛顿(ni dn)(ni dn)法法x*x0 x1x2xyf(x)第30页/共181页第三十一页，共181页。牛顿牛顿(ni dn)法的收敛性法的收敛性定理定理(dngl)： 设设f (x)在在a, b上满足下列条件：上满足下列条件：（1）f (a) f (b) 0则由（）确定的牛顿迭代序列则由（）确定的牛顿迭代序列xk收敛于收敛于f (x)在在a, b上的唯一根上的唯一根x*。第31页/共181页第三十二页，共181页。定理（定理（Newton迭

17、代法局部收敛性迭代法局部收敛性）：）：设 为 的根，如果：（1）函数f(x)在 的邻域具有连续的二阶导数；（2）在 的邻域 。*x0)(xf0)( xf*x*x*|xxxS*x则存在 的某个邻域 ，对于任意的初始值x0S，由由NewtonNewton迭代公式产生的数列收敛于根迭代公式产生的数列收敛于根 。)(,)(2)()()(12kkxxxxxxxxxxSteffensen迭代(di di)格式第32页/共181页第三十三页，共181页。Newton法的变形法的变形(bin xng)重根时的牛顿重根时的牛顿(ni dn)迭代法迭代法)()()(xfxfmxxx)()(1kkkkxfxfmxx

18、使用牛顿法对具有单重零点 0)( , )()()(xxfxfxNewton下降下降(xijing)法法)()(1kkkkkxfxftxx,.1 , 0k第33页/共181页第三十四页，共181页。( )f x( )xf x例例1设设可微，求可微，求根的牛顿迭代公式根的牛顿迭代公式-。解；化简得到解；化简得到 ( )0 xf x根据牛顿迭代根据牛顿迭代(di di)格式格式 ), 2, 1, 0()( )(1kxfxfxxkkkk则相应则相应(xingyng)的得到的得到 1()(0, 1, 2,)1()kkkkkxf xxxkfx( )f xsinxx例例2设设可微，求可微，求根的牛顿迭代公式

19、根的牛顿迭代公式-。第34页/共181页第三十五页，共181页。例例2： 求方程求方程(fngchng)01)(3xxxf在区间在区间1, 1.5内的实根。要求内的实根。要求(yoqi)准确到小数点后第准确到小数点后第2位。位。解：预先估计一下解：预先估计一下(yxi)二分的次数：按误差估计式二分的次数：按误差估计式)(21111*ababxxkkkk解得解得k = 6，即只要二分，即只要二分6次，即达所求精度。计算结果如下表：次，即达所求精度。计算结果如下表：kakbkxkf (xk)的符的符号号011.51.25-11.251.51.375+21.251.3751.3125-31.3125

20、1.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-第35页/共181页第三十六页，共181页。例例3：求方程：求方程0210)(xxxf的一个根的一个根解：因为解：因为(yn wi)f (0) = 10 f (1) = -7 0）的迭代公式，并用以上公式求）的迭代公式，并用以上公式求78265. 0解：设解：设 cxxf2)(（x 0）则）则c就是就是f (x) =0的的正根。正根。 由为由为f (x) = 2x，所以得迭代公式，所以得迭代公式kkkkxcxxx221由于由于x 0时，时，f (x)

21、0，且，且f (x) 0，根据，根据(gnj)定理知：定理知：cx 0，所确定的迭代序列所确定的迭代序列xk必收敛于必收敛于取任意初取任意初值值取初值取初值x = 0.88，计算结果见表，计算结果见表kxk00.8810.8846920.8846830.8846888468. 078265. 0故可取故可取 第37页/共181页第三十八页，共181页。第38页/共181页第三十九页，共181页。第39页/共181页第四十页，共181页。第40页/共181页第四十一页，共181页。第41页/共181页第四十二页，共181页。例例7 7：设：设)5()(2xaxx要使得迭代局部收敛于要使得迭代局部

22、收敛于5*x求求a a的取值范围。的取值范围。)(xx*x13)( x)(x)(xg)(1kkxgx*x例例8 8 已知方程已知方程在在a,ba,b内有根内有根，且在，且在a,ba,b，利用，利用构造一个迭代函数构造一个迭代函数，使得，使得局部收敛于局部收敛于上满足上满足解：解： 由由)(xx可得可得xxxx3)(3)()3)(21xgxxx由于由于(yuy) (yuy) 13)(21)3)(21)(xxxg故迭代公式故迭代公式)3)(21)(1kkkkxxxgx局部收敛。局部收敛。第42页/共181页第四十三页，共181页。第三章第三章 要点要点(yodin)回顾回顾1 Guass消去法消去

23、法Guass消去法、消去法、2 矩阵三角矩阵三角(snjio)分解法分解法LU分解分解(fnji)法法平方根法（对称正定矩阵），追赶法（三对角方程）平方根法（对称正定矩阵），追赶法（三对角方程）向量范数和矩阵范数（三个）；向量范数和矩阵范数（三个）；向量范数的连续性和等价性，向量收敛性定义向量范数的连续性和等价性，向量收敛性定义Guass选主元消去法（列选主元，全选主元）选主元消去法（列选主元，全选主元）2 方程组的性态和误差估计方程组的性态和误差估计矩阵条件数，病态方程组矩阵条件数，病态方程组第43页/共181页第四十四页，共181页。知识(zh shi)结构图线性方程组线性方程组数值解法数

24、值解法直接法直接法迭代法迭代法高斯消去法高斯顺序消去法高斯主元素消去法矩阵三角分解法LU分解平方根分解(对称正定矩阵)追赶法 (三对角方程组)向量与矩阵的范数迭代法的基本思想Jacobi迭代法迭代格式收敛条件充要条件：充分条件：3个Gauss-Seidel迭代法迭代格式收敛条件充要条件：充分条件：5个SOR迭代法迭代格式收敛条件充要条件：充分条件：3个必要条件：列主元消去法全主元消去法分解条件分解算法第44页/共181页第四十五页，共181页。)2()2()2(2)2(3)2(32)2(32)2(2)2(22)2(22)1(1)1(12)1(121)1(11.nnnnnnnnnnnnbxaxa

25、bxaxabxaxabxaxaxa第一步：第一步： 若若 令令 , ,用用 乘乘 第一个方程加到第第一个方程加到第 个方程个方程 ，并保留第，并保留第一一式，则得式，则得, 0)1(11ai)1(11)1(11aalii),.3 , 2(ni ),.3 , 2(ni 1 ilGaussGauss消去法消去法)1(1)1()2(ijiijijalaa),.3 , 2,(nji其中)1 (11)1 ()2(blbbiii),.3 , 2,(nji第45页/共181页第四十六页，共181页。 若若 令令 ， 乘第二个方程加到第乘第二个方程加到第i个方程个方程 ，则得，则得, 0)2(22a2il)2

26、(22)2(22aalii),.4 , 3,(nji),.,3 , 2(ni 用用第二步第二步: :)3()3(3)3(3)3(3)3(33)3(33)2(2)2(22)2(22)1(1)1(12)1(121)1(11.nnnnnnnnnnnbxaxabxaxabxaxabxaxaxa)2(22)2()3(blbbiii),.4 , 3,(nji)2(22)2()3(jiijijalaa),.4 , 3,(nji其中其中第46页/共181页第四十七页，共181页。按上述按上述(shngsh)(shngsh)做法，做完做法，做完n-1n-1步，原方程可化为同解的步，原方程可化为同解的上三角方程组

27、。上三角方程组。)()()2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbxabxaxabxaxaxa 最后，设最后，设 ，逐步回代为原方程组的解：，逐步回代为原方程组的解：0)(nnna)()(nnnnnabx )(1)()()(iiinijiiijiiiaxabx定理：用高斯顺序消去法能够求解方程组用高斯顺序消去法能够求解方程组 A A 的解之的解之充要条件为充要条件为A A的各项顺序主子式均不为零。的各项顺序主子式均不为零。 bx第47页/共181页第四十八页，共181页。)2()2()2()2(22)2(2)2(2)2(2)2(22)2(1)1

28、(1)1 (12)1 (11bAbaabaabaaannnn在第一列中选取绝对值最大的元素在第一列中选取绝对值最大的元素, ,如若如若 = 调换第一行与第调换第一行与第i行，这时的行，这时的 1 ,1iani1max1 ia)1(11a1 ,1ia去法的第一步，即去法的第一步，即消消行行就是原来的就是原来的 , ,再进再进)2(A再考虑再考虑 右下角矩阵，选取绝对值最大的元素作右下角矩阵，选取绝对值最大的元素作为主元素为主元素, ,经过行的对换和列的对经过行的对换和列的对换把主元素移到换把主元素移到， )2(22a再按消元公式计算再按消元公式计算 （i,j=3,i,j=3,n n）。）。)3(

29、ijaGaussGauss列选主元消去法列选主元消去法第48页/共181页第四十九页，共181页。直接直接(zhji)(zhji)三角分解三角分解法法 设设A=LU 即即nnnnnnnnnnnnnuuuuuullllllaaaaaaaaa222112113213231212122221112111111第一步：第一步： 比较第一行元素：比较第一行元素：), 2 , 1(11njuajj比较第一列元素：比较第一列元素：1111ulaii), 3 , 2(1111niaalii解出解出第49页/共181页第五十页，共181页。第二步： 比较第二行元素： ), 3 , 2(21212njuulajj

30、j算出： jjjulau12122nj. 3 . 2比较第二列的元素： 222222ululaiiii得出：222222uulaliiiini4 . 3nmkmnkmmjkmkkkjmjkmmjimkjulluulula1111一般的，第k步及R之行，L的第k-1列已求出，则列元素 比较第k第50页/共181页第五十一页，共181页。算出： mjkmkmkjkjulau11.1,nkkj比较第k列元素(ik 即行指标列指标，为算 , ik) iklnmkmmkmmkimkkikikmkimmkimikuluululula111算出: nmkmnkmmkimkkikmkimmkimikululu

31、lull111算出:kkkmmkimikikuulal11., 1nki第51页/共181页第五十二页，共181页。这组公式(gngsh)可用下图记忆:nnnnnnnullluuuluuuu32122322211131211的求y过程为:bxAyxUbyL第52页/共181页第五十三页，共181页。追赶(zhugn)法设nnnnnnnniiibbbxxxcbacbacbacbacbacb212111133322211第53页/共181页第五十四页，共181页。niiiininnnucucuculllbaccbacb1111213221111111即 1111iiiiiiiclbuualbuni

32、3 , 2第54页/共181页第五十五页，共181页。由 得 nnnbbyyyll1212111111iiiiylbybyni. 3 . 2由 得 nnnnyyxxxucucu1211211iiiiinnnaxcyxuyx11 , 2. 1 ni第55页/共181页第五十六页，共181页。第三章 典型(dinxng)例题第56页/共181页第五十七页，共181页。例例2：用直接三角：用直接三角(snjio)分解法解分解法解201814513252321321xxx解：（解：（1 1）对于）对于(duy)r = 1(duy)r = 1，利用计算公式，利用计算公式111u212u313u 3 23

33、121ll（2 2）对于）对于(duy)r = 2(duy)r = 2， 222221 1252 21ual u 232321 1322 34ual u 51)231 ()(2212313232uulal第57页/共181页第五十八页，共181页。（2 2）对于）对于r r = 3 = 3， 333331133223()24ual ul u 于是于是LUA2441321153121（4 4）回代求解）回代求解(qi ji)(qi ji)： 72101423213133121221ylylbyylbyybLy3333223322211221331113()2()1Uxyyxuyu xxuyu x

34、u xxuTx)3, 2, 1 (第58页/共181页第五十九页，共181页。123012001L100030212U， 第59页/共181页第六十页，共181页。第60页/共181页第六十一页，共181页。第61页/共181页第六十二页，共181页。第62页/共181页第六十三页，共181页。第63页/共181页第六十四页，共181页。第64页/共181页第六十五页，共181页。第65页/共181页第六十六页，共181页。例例5 5 对矩阵对矩阵A A进行进行(jnxng)LDL(jnxng)LDL分解和分解和LLLL分解，分解，并求解方程组并求解方程组32122484548416321xx

35、x解解 对对A A进行进行LLLL分解分解16484412454122384222333对对A A进行进行LDLLDL分解分解121144164816314541414284229312142第66页/共181页第六十七页，共181页。回代解方程组回代解方程组321332214321yyy得得7083. 1875. 025. 0Ty再解再解1234120.25230.87531.7083xxx 0.5451 1.29160.5694Tx 得得第67页/共181页第六十八页，共181页。第四章第四章 要点要点(yodin)回顾回顾1 简单简单(jindn)迭代法迭代法简单简单(jindn)迭代法

36、构造迭代法构造2 G-S迭代法迭代法G-S迭代法的构造思想迭代法的构造思想 G-S迭代法的收敛性分析迭代法的收敛性分析Jacobi方法方法基于基于Jacobi方法的方法的G-S迭代法迭代法简单迭代法的收敛性分析简单迭代法的收敛性分析2 常用迭代法常用迭代法逐次超松弛迭代法逐次超松弛迭代法第68页/共181页第六十九页，共181页。简单(jindn)迭代法的构造 将该方程组等价变形为 构造简单迭代格 式 ， 。若 收敛于确定的向量 ，则 就是方程组的解。此时称简单迭代法 ， 关于初始向量 收敛。gxBx)(kx, 1 , 0kgxBxkk)()1(*x*xgxBxkk)()1(, 1 , 0k)

37、0(x设要求解的线性方程组为 ，其中 为非奇异矩阵， 为向量。bxAbA第69页/共181页第七十页，共181页。简单(jindn)迭代法的收敛性0lim)(kkBa.1)(Bb. 迭代矩阵的谱半径1. 收敛(shulin)的充要条件 定理1.简单迭代法 ， ，对 任意初始向量 都收敛的充要条件是：)0(xgxBxkk)()1(nk1 , 0简单迭代法为 .gxBxkk )1()()()(*)0(*)1(*)(xxBxxBxxkkk故 设 有唯一解 ，*xgxBx第70页/共181页第七十一页，共181页。几种几种(j zhn(j zhn) )常见的迭代常见的迭代法法 一一.Jacobi.Ja

38、cobi迭代法迭代法 设 , i=1,2,n0iia)(1)(1)(1)(11.)(22)(11)1(2)(2)(323)(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax迭代迭代(di di)格式格式第71页/共181页第七十二页，共181页。1)(JB 2.收敛收敛(shulin)条件条件 b.充分条件充分条件(chn fn tio jin)：（j=1,2,n）(按按列列)nijijijijaa,（按行）（按行） ,（i=1,2,n）njijijiiaa, 1（II）设系数矩阵

39、）设系数矩阵 严格对角占优，严格对角占优，nnijaA)(或或则则Jacobi迭代法关于任意初始向量迭代法关于任意初始向量 收敛收敛)0(x（I）若）若 则则Jacobi方法关于任意初始向量方法关于任意初始向量 都都 收敛。收敛。1JB)0(x即即 a.a.充要条件充要条件：第72页/共181页第七十三页，共181页。 二.与Jacobi迭代法相应(xingyng)的Gauss-Seidel法1.1.迭代迭代(di di)(di di)格式格式. .)(1)(1)(1)1(11.)1(22)1(11)1(2)(2)(323)1(12122)1(21)(1)(313)(21211)1(1nknn

40、nknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax第73页/共181页第七十四页，共181页。 2.收敛收敛(shulin)条件条件. G-S法关于任意初始向量法关于任意初始向量 都都 收敛的充要条件是收敛的充要条件是 .1)(sB)0(xa.充要条件：充要条件：b.充分条件充分条件(chn fn tio jin)：若若 则则G-S方法关于任意初始向量方法关于任意初始向量 都收都收敛敛. .1sB)0(x关于任意初始向量关于任意初始向量 收敛。收敛。设系数矩阵设系数矩阵 严格对角占优，则严格对角占优，则G-S方法方法)(ijaA )0(x第74页/

41、共181页第七十五页，共181页。SOR方法(fngf)11)()1(ijijiiikikiabaxx）nijkjijkjxax)()1(ni,.2 , 1)()1()1 (kikixx11ijijiiiaba（）nijkjijkjxax1)()1(第75页/共181页第七十六页，共181页。第76页/共181页第七十七页，共181页。例例2 2：用雅克比迭代法和高斯：用雅克比迭代法和高斯( (o s)o s)赛得尔迭代法赛得尔迭代法解线性方程组解线性方程组877901081119321xxx解：所给线性方程组的系数矩阵按行严格对角占优，解：所给线性方程组的系数矩阵按行严格对角占优，故雅克比迭

42、代法和高斯故雅克比迭代法和高斯(o s)赛得尔迭代法都收敛。赛得尔迭代法都收敛。009/1008/19/19/101ADI9/78/79/71bD雅克比迭代雅克比迭代(di di)法的迭代法的迭代(di di)公式为：公式为：9/78/79/7009/1008/19/19/10)()1(kkXX第77页/共181页第七十八页，共181页。取取X(0) = (0, 0, 0)X(0) = (0, 0, 0)，由上述，由上述(shngsh)(shngsh)公式得逐次近似值如下：公式得逐次近似值如下：0008889. 08750. 07778. 09753. 09723. 09738. 09993.

43、 09993. 09942. 09993. 09993. 09993. 0X (i)43210k高斯高斯(o s)赛得尔迭代法：赛得尔迭代法： 8091781791)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx0009753. 09722. 07778. 09993. 09993. 09942. 00000. 10000. 19998. 0000. 1000. 1000. 1k01234x(i)第78页/共181页第七十九页，共181页。112233131232axbaxbaxb例例3 3设有方程组设有方程组1.1.当参数当参数a a满足

44、什么条件时，雅可比方法满足什么条件时，雅可比方法(fngf)(fngf)对任意的对任意的初始初始(ch sh)向量都收敛。向量都收敛。2.2.写出与雅可比方法对应的高斯写出与雅可比方法对应的高斯( (o s)o s)赛德尔迭代公式。赛德尔迭代公式。解：当解：当a不等于零时，雅可比方法的迭代矩阵为不等于零时，雅可比方法的迭代矩阵为0/2/3/20/1/3/10aaaaaaB可以解出可以解出B的特征值的特征值第79页/共181页第八十页，共181页。,2,2, 0221iaia可知可知(k zh)B的谱半径的谱半径12)(aB由此得出由此得出 时，雅可比方法收敛。时，雅可比方法收敛。2a)023(

45、1)20(1)30(13)1(2)1(1)1(2)(3)1(1)1(21)(3)(2)1(1bxxaxbxxaxbxxaxkkknkkkkkk与雅可比方法与雅可比方法(fngf)对应的方法对应的方法(fngf)为为第80页/共181页第八十一页，共181页。例设有方程组例设有方程组111211111112321xxx证明该方程组对应雅可比方法证明该方程组对应雅可比方法(fngf)(fngf)发散，而发散，而G-SG-S方方法法(fngf)(fngf)收敛。收敛。解：雅可比方法的迭代矩阵为解：雅可比方法的迭代矩阵为02/12/11012/12/10B设其特征值为设其特征值为 ，则，则453BI,

46、25,25, 0321ii由于由于125)(B故雅可比方法发散故雅可比方法发散第81页/共181页第八十二页，共181页。解：解：G-S的迭代的迭代(di di)矩阵为矩阵为0102121002/12/1001000111)(11ULIBSG210021210212100102121012111121,21, 0321由于由于121)(SGB故故G-S方法收敛方法收敛第82页/共181页第八十三页，共181页。第五章第五章 要点要点(yodin)回顾回顾1 插值问题插值问题(wnt)与插值多项式的唯一性与插值多项式的唯一性2 拉格朗日型插值方法拉格朗日型插值方法(fngf)Lagrange插值

47、法插值法 牛顿插值法牛顿插值法 （差商、差分的定义）（差商、差分的定义）完全导数形式的完全导数形式的hermite插值（构造方法、余项）插值（构造方法、余项） 不完全导数形式的不完全导数形式的hermite插值插值（待定系数，重节点差商）（待定系数，重节点差商）3 Hermite型插值方法型插值方法 插值误差分析（拉格朗日余项，差商型余项）插值误差分析（拉格朗日余项，差商型余项）4 分段插值和三次样条插值分段插值和三次样条插值第83页/共181页第八十四页，共181页。三次样条插值插值型插值分段低次插值等距节点插值（差分）差商型余项型余项插值余项插值法插值法构造方法型插值代数插值Hermite

48、HermiteLangrangeNewtonLangrangeLangrange知识(zh shi)结构图第84页/共181页第八十五页，共181页。拉格朗日插值基函数拉格朗日插值基函数(hnsh)一、插值基函数(hnsh)定义定义(dngy)：若：若n次多项式次多项式lk(x)(k=0, 1 , n)在在n+1个插值节点个插值节点x0 x1 xn上满足插值上满足插值条件：条件：), 1 , 0,()(0)(1)(nkikikixlikik则称这则称这n1个个n次多项式次多项式l0(x), l1(x) , ln(x)为插为插值节点值节点x0 ,x1 , , xn上的上的n次次第85页/共181

49、页第八十六页，共181页。拉格朗日插值公式拉格朗日插值公式(gngsh) 将Lagrange插值基函数(hnsh)与函数(hnsh)值线性组合得 可以验证 满足插值条件，即)(xLn)()(1xlyxLnkkkniinkkkinyxlyxL)()(1 i = 0, 1, 2, n上式是不超过(chogu)n次的多项式，称之为Lagrange插值多项式。第86页/共181页第八十七页，共181页。的线性组合。故可将满足插值条件（）的n次多项式写成如下(rxi)形式)()( ,),)( , 1110100nxxxxxxxxxxxx牛顿牛顿(ni dn)插插值的定义值的定义 由线性代数可知，任何(r

50、nh)一个不高于n次的多项式，都可表示成函数)()()(1)(110010nnnxxxxxxaxxaaxN其中 为待定系数。这种形式的插值多项式称为牛顿牛顿Newton插值多项式插值多项式kaaa,10 牛顿插值牛顿插值第87页/共181页第八十八页，共181页。差商的性质差商的性质(xngzh)性质性质(xngzh)1：设设 的的n阶导数阶导数(do sh)存在，存在，则有则有性质性质2 2：,10kxxxf)()(10ikikixxfk=1,2,n性质性质3：k阶差商阶差商 可以表示为函数可以表示为函数值值 的线性组合，即的线性组合，即,10kxxxf差商具有对称性，与插值节点的排差商具有

51、对称性，与插值节点的排列次序无关。列次序无关。)(xf!)(,)(10nfxxxfnn第88页/共181页第八十九页，共181页。 Hermite 插值多项式插值多项式要求函数要求函数(hnsh)值重合，而且要求若干阶导数也重值重合，而且要求若干阶导数也重合。合。即：要求即：要求(yoqi)插值函数插值函数 P (x) 满足满足 在实际问题在实际问题(wnt)(wnt)中，对所构造的插值多项式，不仅中，对所构造的插值多项式，不仅把此类插值多项式称为埃米尔特把此类插值多项式称为埃米尔特（Hermite）插值多项式，记为插值多项式，记为H (x)。 )210( )()()()()()()()(,n

52、,ixfxpxfxpxfxpimimiiii第89页/共181页第九十页，共181页。情形情形(qng xing)1；一阶导数已知；一阶导数已知已知函数已知函数(hnsh)表表nxxxxx210nyyyyy210nyyyyy210求一个插值多项式求一个插值多项式H (x)H (x)，使其满足，使其满足(mnz)(mnz)如下条件：如下条件：插值条件的个数插值条件的个数2n+2, H (x) 的次数：不超过的次数：不超过2n+1次次 iiyxH)(i = 0, 1, 2, n iiyxH)( i = 0, 1, 2, n 第90页/共181页第九十一页，共181页。Hermite插值多项式构造插

53、值多项式构造(guzo) 对于问题1，取n=2，通过一个例子(l zi)来讨论建 立Hermite插值的方法例例：求一个三次多项式 使其满足插值条件3( )Hx.)( ,)(;)( ,)(113003113003mxHmxHyxHyxH分析分析；依照拉格朗日插值的思路，如果构造四个不超过3次的插值多项式0101( ),( ),( ),( )xxxx使它们分别满足第91页/共181页第九十二页，共181页。. 1)( , 0)( , 0)( , 0)(; 0)( , 1)( , 0)( , 0)(; 0)( , 0)( , 1)( , 0)(; 0)( , 0)( , 0)( , 1)(1101

54、1101100010001101110110001000 xxxxxxxxxxxxxxxx(1)300110011( )( )( )( )( )Hxx yx yx mx m现在需要(xyo)考虑的问题是这些基函数的构造问题。 0)( , 0)(1010 xx假设2210001( )() ( )()xxxAxB lxAxBxx可验证条件 自动满足现利用另外的两个条件则满足插值条件的多项式可以写成如下(rxi)形式第92页/共181页第九十三页，共181页。01)(2)(1)(10000000 xxBAxAxBAxx00101221xABxxxx ，20100101( )12xxxxxxxxx求解

55、可得 于是有同理可得21111010( )1 2xxxxxxxxx(2)(3)第93页/共181页第九十四页，共181页。假设(jish)可验证条件 自动(zdng)满足现利用(lyng)另外的两个条件2210001( )() ( )()xxxCxD lxCxDxx0)( , 0)(1010 xx11)(2)(0)(10000000 xxDCxCxDCxx求解可得 于是有同理可得01CDx ，210100)()(xxxxxxx201011)()(xxxxxxx(4)(5)第94页/共181页第九十五页，共181页。将函数(hnsh)(2)到(5)代入式(1)，得到插值多项式 001130101

56、0110100100110110( )1 21 2()()xxxxxxxxHxyyxxxxxxxxxxxxxxmxxmxxxx上式称为三次(sn c)Hermite插值多项式，其余项为(4)2233011( )( )( )( )() ()4!R xf xp xfxxxx),max(),(min(1010 xxxx第95页/共181页第九十六页，共181页。情形情形(qng xing)2；导数值不完全；导数值不完全已知函数已知函数(hnsh)表表myyyyy210求一个插值多项式求一个插值多项式H (x)H (x)，使其满足如下，使其满足如下(rxi)(rxi)条件：条件：插值条件的个数插值条件

57、的个数m+n+2, H (x) 的次数：不超过的次数：不超过m+n+1次次 iiyxH)(i = 0, 1, 2, n iiyxH)( i = 0, 1, 2, m nmyyyyyy210nmxxxxxx210第96页/共181页第九十七页，共181页。2( )px002112002)( ,)( ,)(mxpyxpyxp例例 试确定试确定(qudng)(qudng)一个不超过二次的一个不超过二次的多项式多项式使其满足如下插值条件先利用前两个插值条件，构造一个1次的插值多项式011010110( )xxxxp xyyxxxx第97页/共181页第九十八页，共181页。定义(dngy)2101(

58、)( )()()pxp xc xxxx这里c是一个(y )常数，无论它取何值，插值条件200211() ()pxypxy和自然满足，再利用导数条件(tiojin)确定常数c1001010()yyc xxmxx从上式解出c，回代到 得到)(2xp0011201001011001011( )() ()()xxyyxxpxyymxxxxxxxxxxxx第98页/共181页第九十九页，共181页。33( )( ),( )( ),Haf a H bf b33, 2222ababababHfHf 243( )( )( )()() ( )4!2fabf xHxxaxxbaxb( )f x , a b若在上有

59、连续的四阶导数，试证明满足以下插值条件)(3xH的插值多项式的截断误差为第99页/共181页第一百页，共181页。2323(4)( )( )( )( )()() ()2,2( )( )( )( )()() ()2( ),( )()( )0,()022Rolle,( )0abR xf xHxk x xa xxbabxababg tf tH tk x ta ttbg tababg agg bgxg证明：设余项当 不同于 ， 和时 构造如下关于的函数于是函数也是充分光滑的 并且有如下零点多次使用定理知 至少存在一个依赖于 的点 ，使得有(4)(4)23.( )( ),4!( )( )( )( )()

60、() ()4!2fk xfabR xf xHxxa xxb从而可得从而有截断误差第100页/共181页第一百零一页，共181页。)()()(10nxxxxxxxf,10kxxxfkxxx,102 设函数设函数 求差商求差商之值，其中之值，其中是互异节点是互异节点nk 0)(jxfkj, 1 , 0解解 (1(1）当）当根据公式根据公式 kjjnjkxxfxxxf0110)()(,故有故有0,10kxxxf（2 2）当）当 1 nk时，考虑差商与导数的关系式时，考虑差商与导数的关系式 !)(,)(10kfxxxfkk1 nk)!1()()( nfk故此时故此时1,10kxxxf 1 nk0)()