数值计算方法总复习_图文

1、总复习截断误差、舍入误差误差、误差限有效数字误差的传播! 3! 2132xxxex! 7! 5! 3sin753xxxxx! 4! 3! 2)1ln(432xxxxx如:若将前若干项的部分和作为函数值的近似公式,由于以后各项都舍弃了,自然产生了误差。Taylor展开截断误差14159265.3414213562. 12 166666666. 061! 311415927. 34142136. 12 16666667. 0! 31 舍入误差 绝对误差、绝对误差限*xx工程上常记为x15251000 y15*x1000*y2)(*x5)(*y 误差、误差限例如 相对误差、相对误差限例1解:0020

2、00. 06102|*er28718. 2102628718. 2102661071. 0*2.718 28,e *e已知近似值为:精确值为:求 绝对误差、相对误差绝对误差相对误差*|re 或 有效数字x0.a1a2an10ma10annm 10用科学计数法，记其中nm.xx 1050|*x若则称有n 位有效数字，精确到 。，的截取按四舍五入规则有4位有效数字有6位有效数字65592141. 359141. 3*142. 3*7592141. 3*有8位有效数字例 2 数据误差的传播121( )*(,)()innixiyyyfxxxx12112( ,)( )( )( )( ,)innxiiin

3、fx xxyyxxyf x xx绝对误差为：相对误差为：称为 f 的条件数，其绝对值的大小可反映函数值对数据的敏感程度 误差的传播利用上面的误差估计公式，可以得到两个数的和、差、积、商的误差估计(x1x2) 12(x1x2) x21x12(x1/x2) 1/x22x1/x22(x1x2) x1x1x21x2x1x22(x1x2) 12(x1/x2) 12 误差的控制、算法的稳定性基本概念 局部收敛、全局收敛 收敛阶算法及其收敛性 二分法 简单迭代法 牛顿法及其简单变形上面定理所涉及的收敛性，即在根邻域的收敛性称为上面定理所涉及的收敛性，即在根邻域的收敛性称为局部收敛性局部收敛性，具有局部收敛性

4、质的迭代法通常对初值，具有局部收敛性质的迭代法通常对初值的要求很高，使用起来不太方便。因而，人们通常希的要求很高，使用起来不太方便。因而，人们通常希望迭代算法对相对大的范围的初始点具有收敛性，这望迭代算法对相对大的范围的初始点具有收敛性，这种收敛性称为种收敛性称为全局收敛性全局收敛性。定义定义 设迭代过程设迭代过程 收敛于收敛于 的的根根 . . 如果迭代误差如果迭代误差 满足下列关系满足下列关系则称该迭代序列是则称该迭代序列是p 阶收敛的阶收敛的( ( 时要求时要求 ) )。1p 1|lim(0),|kpkkcckkx1()kkxx( )xx1c 当当p p=1=1时，称为线性收敛；时，称为

5、线性收敛；当当p p11时，称为超线性收敛；时，称为超线性收敛；当当p p=2=2时，称为平方收敛或二次收敛。时，称为平方收敛或二次收敛。显然，显然，迭代序列的收敛阶越高，它的收敛速度就越快迭代序列的收敛阶越高，它的收敛速度就越快。()1()lim.!pkpkkp ( )( )xxx中的定理2迭代函数在不动点如附.2.4果近满足：( )xp(1)存在 阶导数且连续；(1)( )(2)( )( ).( )0,( )0.pp 1 ()kkxxp则迭代法为 阶收敛且有补充算法的基本思想：算法的基本思想：将区间对分，保留有根的区间，舍去无根的区间。将区间对分，保留有根的区间，舍去无根的区间。如此往复，

6、以逐步逼近方程的根。如此往复，以逐步逼近方程的根。 ( ) , ( ) ( )0.f xa bf a f b 假设在上连续且基本条件：基本条件：二分法二分法 00000000(1)., , ().2 ()0( ) , ()0ababa bxf xf xf xa bf x令，取中点，求若，则得到在上的一个零点；若，则作下一步。01100101()()0()()0.fxfaaabxfxfbaxbb(2).若， 则 令，；若， 则 令，1100 ( )0,f xa bab这样，我们得到 的一个新的含根区间，其长度是原区间长度的一半。算法的步骤,( )kkabfx(3).对新的含根区间重复上述步骤，我

7、们可以得到一个区间序列，序列中的每一个区间都是函数的含根区间且区间的程度依次减半。a x0 b( )f x a1 b111 , ,.,.kka ba ba b二分法产生一个含根区间序列：11,11 ().().22kkkkkkka bbababa其中区间的长度为： k (2)kkkf xabx因此，当 足够大时，我们可以用作为函数的一个根 的近似值。1.22kkkkbabax此时有误差估计误差估计：常用来估计k的值算法的收敛性1.22kkkkbabax,21abk.2ln2ln)ln(abk用二分法求方程用二分法求方程 3( )1 0f xxx 在在1,1.5内的实根内的实根， 要求要求 0.

8、005.解解111.5 1|0.00522kkkb ax 6.k 即可推出所需的迭代次数满足即可推出所需的迭代次数满足 在区间在区间1,1.51,1.5上至少存在一个根。上至少存在一个根。 ( )(1)1 0,( )(1.5) 0.875 0,f aff bf 其具体过程如下：其具体过程如下： 例例由于由于因而因而( )0f x 由误差估计式由误差估计式( )kf x 的符号0 01.00001.00001.50001.50001.25001.2500- -1 11.25001.25001.50001.50001.3751.375+ +2 21.25001.25001.3751.3751.31

9、251.3125- -3 31.31251.31251.3751.3751.34381.3438+ +4 41.31251.31251.34381.34381.32811.3281+ +5 51.31251.31251.32811.32811.32031.3203- -6 61.32031.32031.32811.32811.32421.3242- -kakbkxk61.5 11.32420.0039. 0.00572x等价变换等价变换( )xx( )0f x ( ) 0f x 的根( ) x的不动点原理：原理： 且连续简单迭代迭代格式：迭代格式：1()kkxx，满满足足如如下下条条件件：设设

10、迭迭代代函函数数,)(baCx ;,)(,)1(baxbax 时时当当.| )()(|, 1)2(成成立立都都有有使使对对任任意意存存在在正正数数yxLyxbayxL 有有误误差差估估计计式式，并并收收敛敛于于产产生生的的迭迭代代序序列列迭迭代代格格式式且且对对任任意意上上有有唯唯一一解解在在则则方方程程 )(,)(10kkkxxxbaxbaxx .101xxLLxkk 收敛性：压缩映像保证迭代不中断Lipschitz条件定理的条件定理的条件(2)不容易得到不容易得到,由微分中值定理：由微分中值定理：满满足足条条件件：设设,)(1baCx ;)(,)1(bxabax 时时当当.1| )(|,

11、1)2(成成立立都都有有使使存存在在正正数数 LxbaxL 迭迭代代过过程程近近似似值值且且对对任任意意初初始始上上有有唯唯一一解解在在则则方方程程,)(0baxbaxx , 2 , 1 , 0),(1 kxxkk 且且收收敛敛,)()()(,)(1yxyxbaCx则则若若不难得到如下推论。不难得到如下推论。.101xxLLxkk |)(|1kkkkxxxx|)()()(|kkxx |1 kkxx |kkxLx | )1(kxL 从而，有如下误差估计：从而，有如下误差估计：在推论的条件下，有误差估计式在推论的条件下，有误差估计式, 2 , 1 , 0|,|11|1 kxxLxkkk ., 2

12、, 1 , 0|,|1|01 kxxLLxkk 注注 由于定理中条件由于定理中条件(1)(1)一般难于验证，而且在大区间一般难于验证，而且在大区间上，这些条件也不一定都成立。所以实际使用迭代法上，这些条件也不一定都成立。所以实际使用迭代法总是在根的邻近进行总是在根的邻近进行。*( )( ,)( )1.xOx 如果函数在其不动点 的一邻域定内连理2.2.2续可微，且*01, ()kkxxx 则存在正数使得对任意，由迭代格式产生的迭代序列收敛于 ，且其误差估计式与定理2.2.1中的相同。|( )| 1 实际上只要即可表明收敛性与初值的选择有关！例例2 ( )9sin10 f xxx 求在0,1内的

13、一个根。解解 (0)10, (1)8sin 10 0,1 ff 由 于，因 而为 有 根 区 间 。1sin1.31( )sin1. 3110sin 01( )sin111,331| cos|1( ).66sin1xxxxxxxx将方程化为等价方程：此时，在区间0,1上，且0010,10,()1Pkkxxxx根据定理，任取，由简单迭代格式所产生的迭代序列收敛于方程在中的根。比如取0.4，计算结果见书 28表2.2.2.也可化为等价方程也可化为等价方程 . .但此时定理条件不成立，迭代序但此时定理条件不成立，迭代序列不能保证收敛。列不能保证收敛。2arcsin(91)xx将将非线性方程线性化非线

14、性方程线性化，以线性方程的解逐步逼，以线性方程的解逐步逼近非线性方程的解。近非线性方程的解。基本思想基本思想Newton迭代方法1()()kkkkf xxxfx迭代格式迭代格式)()()(kkkxxxfxfxf Newton迭代法的计算步骤迭代法的计算步骤000(),().0 xf xfxk123输入精度 , ，最大迭代次数N，初值 ，计算令第一步：；()|kkfx3如果N或|，则输出算法失败标志，并终第二步：止迭代；1()()kkkkf xxxfx第计算三步：；111()|:1kkkkxxf xxkk12如果|,或|,则终止迭代，并取；否则，并转第四步：第二步。1( ) 0( )0( )Ne

15、wton()()( )0kkkkfff xf xxxfxf设 ，且在 邻域内具有二阶连续导数，则由法产生的迭代序列局部定理2.3.1收敛到 ，且收敛阶至少为2。又当时，收敛阶恰为2。缺点：缺点：对初值要求较高，计算量较大。优点优点：收敛速度快，精度高，格式简单，应用广泛。 优点与缺点优点与缺点 局部收敛性局部收敛性 全局收敛性全局收敛性( )Newtonf x如果函数在某一个含根区间满足一定的单调性和凸凹性，则得到迭代法的全局收敛性。定理定理 2( ) , f xC a b设函数且满足如下条件：0001)( ) ( )0;2)( ) , ;3)( ) , ()()0.f a f bfxa bf

16、xa bxf xfx在上不等于零在上恒正或恒负;4)初值满足条件Newton( )0 , .kxf xa b则由迭代法产生的序列单调收敛于在区间内的惟一根保证了根的存在性保证了根的存在性 函数单调，根惟一函数单调，根惟一函数图形的凸向不变函数图形的凸向不变 , ( ) , xa bxa b保证时，例例2Newton 9sin10 xx 用迭代求在0,1内的一个根。解解21 ( )9sin1 (1)0, ( )0 31,13f xxxff由于满足，且在区间上满足条件( )18cos610( )18sin180fxxxfxx，000001 ,1()()03()0NewtonNewtonPxf xf

17、xf xx故由定理可知：当初值满足，即时，迭代法收敛。取0.4，按迭代格式计算，计算结果见书 33表2.3.1.简化简化NewtonNewton法法10().()kkkf xxxfx 迭代格式迭代格式 进一步简化进一步简化1().kkkf xxxc 收敛性与收敛速度收敛性与收敛速度推广的简化Newton法只有线性收敛速度。 迭代格式迭代格式 收敛性与收敛速度收敛性与收敛速度 迭代格式迭代格式 收敛性与收敛速度收敛性与收敛速度NewtonNewton下山法下山法1(),()kkkkkf xxxfx01kk其中称为。通过适当选取下山下山因子因子，使得1|()|()|kkf xf xNewtonNe

18、wtonNewton下山法当1时，只有线性收敛速度，但对初值的选取却放得很宽。某一个初值对迭代不收敛，对下山法却可能收敛得很好。 迭代格式迭代格式 收敛性与收敛速度收敛性与收敛速度弦割法弦割法 迭代格式迭代格式111()().()()kkkkkkkf xxxxxf xf x 收敛性与收敛速度收敛性与收敛速度2( )( )0( )0.f xCf xf 设函数 - , + ， 其中 为的根， 为某正数。假设定理2.3.310111,1.618xx 则存在正数，当时，弦割法将至少按阶1+ 5p2收到根敛.100()().()()kkkkkf xxxxxf xf x 单点弦割法单点弦割法 单点弦割法的

19、局部收敛性单点弦割法的局部收敛性由简单迭代的一般收敛性理论可以推出：单点弦割法是局部收敛的且一般只有线性收敛速度。 单点弦割法的全局收敛性单点弦割法的全局收敛性定理定理 2( ) , f xC a b设函数且满足如下条件：0100011)( ) ( )0;2)( ) , ;3)( ) , ()()0,.f a f bfxa bfxa bxxf xfxxx在上不等于零在上恒正或恒负;4)初值, 满足条件( )0 , .kxf xa b则由单点弦割法产生的迭代序列收敛于在区间内的惟一根基本概念 向量范数、矩阵范数、条件数 严格对角占优矩阵、对角占优矩阵、不可约矩阵算法及其收敛性 高斯消元法 矩阵的

20、三角分解及其应用 迭代法TnnnxxxxCR),(,)(21设中在向量空间x常用的向量的范数有:2x2122221)(nxxx2x范数的或欧氏范数1xnxxx211x范数的或平均范数xinix1maxx 范数最大范数切比的或或雪夫范数-(1)-(2)-(3)2( , )xx xxxpxppnppxxx121)(,1xpp 范数的-(4)显然显然1212pxxxpp由于和是当和时的特例，并且由于并且由于ppnppxxx121)(inix1maxppinixn11)max(inipxn11max)(max1pxinix所以的特例也是px),(时pxxp1121nxxxx且例例 求下列向量的各种常用

21、范数求下列向量的各种常用范数Tx)1,3 ,4 , 1(解解1x421xxx92x21242221)(xxx3327 xiix41max4根据向量的常用范数可以得到常用的矩阵算子范数1101max)1(xAxAxniijnja11max,A的每列绝对值之和的最大值A称为 的列范数xAxAx0max)2(njijnia11max,A的每行绝对值之和的最大值A称为 的行范数2202(3)maxxAxAx)(maxAATmax()TTA AA A为的特征值的绝对值的最大值，2A称为 的范数-(10)-(11)-(12)证明见书P70例例求矩阵A的各种常用范数110121021A解解1Aniijnja

22、11max25234252 ,5 ,2max1njAnjijnia11max42 ,4 ,3max1ni2A)(maxAAT由于的特征值因此先求AATAAT120121011110122011211190102特征方程为)det(AAIT2111901020的特征值为可得AAT9361. 0,9211. 2,1428. 93211428. 9)(maxAAT2A)(maxAAT0237. 3FA)(AAtrT2926056. 31AA2AFA容易计算计算较复杂对矩阵元素的变化比较敏感不是从属范数较少使用(理论上)使用最广泛性质较好定义定义称的特征值为设,21nnnRA,max)(21nAA为矩

23、阵 的谱半径-(13)矩阵的谱半径矩阵的谱半径显然，由定义可知2A)(maxAAT)(AAT实特征值为绝对值，复特征值为模定义定义称为非奇异矩阵设,A,.A为 的其中为某条件种算子范数数1)(AAAcond矩阵的条件数矩阵的条件数矩阵A的条件数与所取范数有关。通常记1111( )condAAA1( )condAAA1222( )condAAAm axm in()()TTAAAA显然，当A对称时，max2min( )( )( )AcondAA2( )AcondA。当对称正定时，它的谱条条件数通件数是最常称为谱条件数小的条件数。1(),1, 2,ijnijiijjinAaaainA若阶 方 阵满

24、足则 称定 义 3.4.2按 行 严 格 对矩 阵角 占 优 ；1,1, 2,nijjjiijaajnA按 列 严 格 对若则 称 矩 阵角 占 优 。严格对角占优矩阵严格对角占优矩阵1(),1, 2,ijnijiijjinAaaainA若阶 方 阵满 足且 上 述 不 等 式 中 至 少 有 一 个 成 立 严 格 不 等 号 ，则 称 矩定 义 3.4.3按阵行 对 角 占 优 ；1,1,2,nijjjiijaajnA若且上述不等式中至少有一个成立严格不等号按列对，则称矩阵角占优。对角占优矩阵对角占优矩阵1112112222 0AAAAAAAAA定义3.4如果矩阵 能通过行的互换和相应的列

25、互换成为形式，其中，为方阵，则称矩阵 为；否则，称矩阵 为.4可约矩阵不可约矩阵。 131,2,3110210 110011012011 P ITIJAPAP 例： 不可约矩阵不可约矩阵21121121121112112111容易验证下面矩阵按行（或列）都不严格对角占优，但它是不可约按行（或列）对角占优的。虽然不可约，但不按行（或列）对角占优。而矩阵GaussGauss消元法消元法11112211211222221122. . .nnnnnnnnnnna xa xa xba xa xa xba xa xa xb先将 阶线性方程组：1111221122222. . . nnnnnnnngb xb

26、 xb xgb xb xgb x转化为等价的（同解的）上三角形方程组：11 ,.,nnxxx上述过程称为。 然后逐次计算出，这一过程称消元过程回为代过程。基本思想：基本思想：Gauss消元法的运算量消元法的运算量MD3323nnn)(323nOn数级很大时当n3323nnnMD33n不必选主元的情况： 当系数矩阵A对称正定对称正定或严格对角占优严格对角占优或不可不可约对角占优约对角占优时，可不必选主元。Gauss消元法是不稳定的算法，其中小主元是不稳定的根源。因而在Gauss消元法中要避免小主元的出现。这就需要采用“选主元”的技术。所谓选主元，简单地说就是选取绝对值最大的元素作主元（全选主元或

27、列选主元）。算法的稳定性：算法的稳定性：框框第第框框第第框框第第框框第第nkulllllluuulluuuuluuuuunnnknnikiiknkjkkkknjknjk2121212122222211111211按上图逐框求出矩阵按上图逐框求出矩阵A的的LU分解分解,紧凑格式法紧凑格式法。上一页上一页 下一页下一页 返回返回 .,nkkjulaukqqjkqkjkj111.,nkkiuulalkkkqqkiqikik2111定理定理 若矩阵若矩阵A非奇异非奇异, 则则A能分解为能分解为LU 的充分必要条件是的充分必要条件是A的的所有顺序主子式所有顺序主子式 均不为均不为0.定理定理 若非奇异矩

28、阵若非奇异矩阵A有有LU 分解分解,则此分解是唯一的则此分解是唯一的.定理定理 设设n阶对称正定矩阵阶对称正定矩阵A，则存在唯一的单位下三角阵，则存在唯一的单位下三角阵L及对及对角阵角阵D 使得使得 。TDLLA 称为矩阵称为矩阵A 的的乔累斯基分解乔累斯基分解上一页上一页 下一页下一页 返回返回 定理定理 设矩阵设矩阵A对称正定，则存在唯一的对角元为正的下三角阵对称正定，则存在唯一的对角元为正的下三角阵 L，使得，使得 。TLLA 称为对称正定矩称为对称正定矩阵阵A 的的乔累斯基分解乔累斯基分解 利用利用乔累斯基（乔累斯基（Cholesky）分解）分解式来求解式来求解Ax=b的方法的方法也称

29、也称Cholesky方法或方法或平方根法平方根法)(2121TTLDLDLDLA 又又例：利用系数矩阵的例：利用系数矩阵的LU分解分解, 求解方程组求解方程组 4514126731161234312111114321xxxx解：解：LU分解的紧凑格式为分解的紧凑格式为111u上一页上一页 下一页下一页 返回返回 113u112u114u11121l41431l61641l111222u011123 u211324u1141332l51611142l214233u2325061343l12141134)(u2152315261744)(u 21512201111112356114111LU迭代法

30、的一般形式及其收敛性迭代法的一般形式及其收敛性1 ()(,) Tijn nnAabbbAxb对线性方程组其中是非奇异矩阵， nxBxgngR构造其形如的同解方程组，其中B为 阶方阵，。迭代法迭代法(0)( )(1)( ) (k=0,1,2,) nkkkxxRxAxbBgx 若对任何初始向量，由迭代公式产生的迭代序列均收敛于方程组的解，则称迭代格式是收敛的；否则，称迭代格式是发散的。这种方法称为求解线性方程组定义3.4.1简单迭。代法的0 (1,2, )iiain若系数矩阵非奇异且，则有1111221n12112222n2n11n12nn nnnnna x a xa xba x a xa xba

31、 x a xa xb设 元线性代数方程组几种古典迭代算法几种古典迭代算法112213311221123322n112233 nnnnnnnngxb xb xb xgxb xb xb xgxb x b xb x,(, ,1,2, ),(1,2, ).ijiijiiiiiabbij i jnginaa 其中( )(1)( )( )( )112213311(1)( )( )221123322(1)(n11 kkkkknnkkknnkngxb xb xb xgxb xb xb xxb x)( )( )2211kkknnnnngb xbx建立迭代格式：建立迭代格式：() .kxBxg(k+1)则 迭 代

32、 格 式 可 简 记 为12131 111212321221231 000nnnnnnnnnnbbbbgbbbbgBgbbbbg 若记UDLA 记 nnaaD0011 000001121nnnaaaL 000001112nnnaaaUv Jacobi迭代的矩阵形式迭代的矩阵形式bxUDL )(bxULDx )(bDxULDx11)( 1gD b易知，易知，Jacobi 迭代迭代有有,)(11ADIULDBBJ 1231231231027210283542xxxJacobixxxxxx用迭例3.4.代法求解1(0)(0)(2)(1)(9)(0,0,0) ,(7.2,8.3,8.4)(9.71,1

33、0.70,11.5)(10.9994,11.9994,12.9992)(11,12,13) .TTJTJTxxB xgxB xgxx(1)取代入迭代式，得精确解为11 100101 0 0101200.1 0.210 1 0001 1020.100.2100 0 11150.2 0.201005 (7.2,8.3,8.4)JTBID AgD b 解( )(1)kkJacoxxbi同时保留两个因此，在迭代法的计算过程中，需。若把迭代近似解向量和公式改写成(1)( ) (0,1,2,)kkxBxg k迭代公式用方程组表示为(1)( )( )( )112213311(1)( )( )( )22112

34、3322(1)( )(1122 kkkknnkkkknnkkknnngxb xb xb xgxb xb xb xxb xb)( ),11 kn nnngxbx(1)( )( )( )112213311(1)(1)( )( )221123322(1)(1)112 kkkknnkkkknnkknnngxb xb xb xgxb xb xb xxb x(1)(1)2,11 kkn nnngb xbxv GaussGaussSeidelSeidel迭代的矩阵形式迭代的矩阵形式)()()1(1)1(bUxLxDxkkk bDUxDxLDIkk1)(1)1(1)( bLDUxLDxkk1)(1)1()()

35、( .)(,)(11bLDgULDBBG 1231231231027210283542xxxGaussSeidelxxxxxx用例3迭代.4 3法求解.(0)1(0)(0)12311(1)(0)21321(1)(1)3123(5)(0,0,0) ,11 (2)727.2000101011 (2)(7.200083)9.0200101011 ()7.20009.020042)11.644055(10.9989,11.Txxxxbxxxbxxxbx（ ）（ ）（ ）仍取代入迭解代式，得（如此继续下去，9993,12.9996)(11,12,13) .Tx 精确解为(1)( )(1)12( )1(1

36、)( )1 (,), 1 (),1,2, .Tkkknkinkkiiiijjijjjj iiiiiGaussSeidelxxxxxxxGaussSeidelrxba xa xinaa 为迭代法加速:记其中由迭代公式得到。于是有(1)( ).kkkxGaussSeidekxxlxx可以把看作迭代的修正项，即第 次近似解以此项修正后得到新的近似解 (1)() .kkxxxx即将乘上一个参数因子作为修正项而得到新的近似解，具体公式为11S R1OAxbGaussSeidel按上式计算的近似解序列的方法称为，其中称为松弛因子。当时，称为次(逐次超松弛迭代法（迭代亚)松弛因子；时，称为完全松弛因子，此时

37、即为迭代；时，称为超）松弛因子。为了获得更好的收敛效果，我们在修正量前乘一个参数因子，通过调节此因子来获得更快的收敛效果。(1)1(1)( )11 ( , 1,2, .1)()kkiiiinkkkiiijjijjjj iiixxxxba xa xain 亦即(0)12123231.4(1,1,1)SOR21 2021.8Txxxxxxxx取，用例3.迭代法解方程组4.71(1)(1)( )11(1)( )( )112(1)( )(1)( )2213(1)( )(1)332(0) (1)()0.40.7(1)0.40.7()(0,1,2,)0.40.7(1.8)(1,1,1)inkkkkiiii

38、jjijjjj iiikkkkkkkkkkTxxba xa xaxxxxxxxkxxxx 由将解代入上式开(9)(1.200,1.3996,1.6001) (1.2,1.4,1.6) .TTxx始迭代精确解(1)()()1(1)1()1()()1(1)1()1 () (1).kkkkkkkkkxxxxDLxDUxDbxxDLxDUxDb1111(1)1()11,() ()(1)().kkIDLIDLDLxDLDU xDLb因为故（） 与存在，有1( ).(1)BDLDUSOR迭 代 法 的 迭 代 矩 阵 为0 2 ,1.6.SOR迭 代 法 中 的 松 弛 因 子应 在 区 间 （ ，） 内

39、 取值 。松 弛 因 子 的 选 取 对 收 敛 速 度 影 响 极 大 但 目前 尚 无 可 供 实 用 的 计 算 最 佳 松 弛 因 子 的 方 法 。通 常 是 根 据 系 数 矩 阵 的 性 质 及 实 际 经 验 ， 通 过试 算 来 确 定 松 弛 因 子 。 经 验 上 可 取 1.4v SOR迭代的矩阵形式迭代的矩阵形式()JB然而，由于难以计算，这个定理实际应用起来仍有困难。A当系数矩阵为三对角对称正定矩阵时，下述定理给出了最佳松弛因子的计算公式：223 .4 .3 2.11)A) )1JGJBBBo p t设 矩 阵为 三 对 角 对 称 正 定 矩 阵 ， 则（，且 最

40、 佳 松 弛 因 子（为定 理22222)111)11)11).JJJJJGBBBBBBBoptopt此 时 ，（(0(1)( )( ) ( )(0,1,2,1).kkkxxgkxBxgB对任意初始向量和右端项 ，由迭代格式产生的迭代序定理3.4.1 收敛的充要条件列是定理定理 3.4.1定理定理 3.14).(0 )()1( kBgBxxkkk充充要要条条件件是是收收敛敛的的迭迭代代格格式式一般迭代算法的收敛性一般迭代算法的收敛性(1)()()()*()(1)()*(1)(0) 1 (0,1, 2,)3.4.1 1.2 kkkkkkkkBxBxgkxAxbBxxxxBBxxxxB若， 则 由

41、 迭 代 格 式产 生 的 迭 代 序 列收 敛 于 方 程 组的 解且定有 误 差 估 计 式理定理定理 (0)(1)4(1)(0)00.10.207.20.100.2 ,0 ,8.30.20.2008.410, 0.4, 8.4 12.932,13BxxBxxk 例 ： 若则 有即 需 要 迭 代次 才 能 满 足 精 度 。()*(1)(0)(1)(0) .1:(1) ln/ ln1. kkBxxxxBkBkBxx注可估计出由误差估计式根据事先给定的精度 ，迭代的次数(1)( )1kkBxx当 不太接近 时，可用作为终注2止准则。123123123(0)( )20232481223153

42、0(0,0,0)TkxxxGaussSeidelxxxxxxxxx-6用迭代法求解是否收敛？若收敛，取需迭代多少例3.步，才能使123 JacobiGaussSeidel122111112211xxx 分别判断用迭代和迭代求例3.4.解线性代数方程组5的收敛性。 022101 .220JJacobiB 迭代法的迭代矩阵为解322det()det 110.22JIB其特征方程为0,()01.JB123故特征值Jacobi迭代收敛！1100022110001221000100022022110001023 .021000002GB Gauss-Seidel迭代矩阵为222det()det 023(

43、2)0.002GIB 其特征方程为02,()21.JB123故 特 征 值，Gauss-Seidel迭代发散！112233 JacobiGaussSeidel111xbaaaaxbaaxb 例3.分别判断用迭代和迭代求解线性代数方程组4.6的收敛性。 00.0JJacobiaaBaaaa迭 代 的 迭解代 矩 阵 为2det()det() (2 )0.JaaIBaaaaaa其特征方程为,2 ,()| 2 |.JaaBa 123故特征值11,.22aJacobi因此，当时迭代收敛122223231000100010001000010000.100002GaaBaaaaaaaaaaaaaaaaaa

44、aa Gauss-Seidel迭代矩阵为2232232323det()det002(3)0.GaaIBaaaaaaaaaa 其 特 征 方 程 为()1GBa满足的 不易求出!迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及右端项无关。对同一方程组，由于不同的迭代法迭代矩阵不同，可能出现有的方法收敛，有的方法发散的情形。1231231232212223 xxxxxxxxx对方程组讨论Jacobi迭代与Gauss-Seidel迭代例3.4.8的收敛性。1122100 111 010221001000022 100 001220000ADLU求迭代矩阵判别其谱半径是否小于 。解1Jacobi0

45、22 101220JBIDA迭 代 法 的 迭 代 矩 阵 为312322 110220,()01,JacobiJJIBB其 特 征 方 程 为因 此 有于 是所 以迭 代 法 收 敛 。11Gauss-Seidel100100 110 ()110221021100022022()110001023021000002GDLDLBDLU 对迭代，由212322 023(2)00020,2,()21,GGIBB 特征方程特征值为故所以迭代发散。)11.(1JGBBBB判 断 条 件虽 然 给 出 了 判 别 迭 代 收 敛 的 充 要条 件 ， 但 要 求 矩 阵 的 特 征 值 。仅 给 出 了

46、 迭 代收 敛 的 充 分 条 件 ， 许 多 情 形 下 不 能 起 作 用 。 如 上例 ， 两 个 方 法 均 有，1 对一些特殊的系数矩阵可给出几个常用的判别收敛的条件。Axb在用古典迭代法求解线性代数方程组时，下列结论成立。JacobiA2DA定理3.4.若矩阵 为对称正定矩阵，则迭代收敛的充要条件是对6称正定。AJacobiGauss-SeidelA若矩阵 为按行（或列）严格对角占优矩阵，则 非奇定理3.4异，且迭代和迭代.4均收敛。古典迭代法的收敛性古典迭代法的收敛性AJacobiGauss-SeidelA若矩阵为不可约按行（或列）对角占优矩阵，则 非奇定理3.4异，且迭代和迭代

47、.5均收敛。Gauss-Seidel A若矩阵 为对称正定矩阵，则迭定代理3.4.收敛。7AB其中 为严格对角占优阵，故Jacobi与 Gauss-Seidel迭代均收敛。 为非严格对角占优阵，但为对称正定阵, =1.4，故SOR迭代法收敛。SO R02. iiain设0,=1,2, ,若迭代 收 敛 ,则定 理 3.4.8（ Kahan）SOR02. A定若矩阵为对称正定矩阵，则迭代收敛理的充3.4.9要条件是123123123 Jaco b iG au ssS eid el1 027 21 028 354 2xxxxxxxxx分例 3 .别用迭 代 和迭 代4 . 1 ，例 3求 解4 .

48、组.方 程312123231 .4S O R21 2021 .8xxxxxxx取，例 3 .用迭 代 解. 7方 程 组41012210 1 102121115012AB 在前面的例子中，基本概念 插值节点、插值多项式、插值基函数 差商及其性质算法及其收敛性 Lagrange 插值 Newton 插值 分段线性插值满足比如多项式函数),(xP( )0,1,2,.,iiP xyin)()(xfxP近似代替并且用-(1)这就是这就是插值问题插值问题, (1)式为式为插值条件插值条件,( )( )P xf x称函数为函数的插值函数( ),P x如果为多项式函数插则称之为值多项式,0,1,2,., ,

49、ixin点称为插值节点 , a b区间称为插值区间Lagrange插值插值就是选用节点上的函数值作为插值条件，就是选用节点上的函数值作为插值条件，选用代数多项式作为插值函数。选用代数多项式作为插值函数。 Lagrange插值插值已知已知 n+1个互异插值节点个互异插值节点 (xi, f (xi), i= 0, 1, 2, , n 。插值基函数：插值基函数：0110110().()().()( )().()().(),0,1,.,iiniiiiiinnjijjj ixxxxxxxxl xxxxxxxxxxxinxx基函数仅与节点有关基函数仅与节点有关而与被插函数无关！而与被插函数无关！容易验证，

50、容易验证， Ln(xi) = f (xi), i = 0, 1, 2, n.n 次次LagrangeLagrange插值多项式：插值多项式： 00110( )( ) ()( ) ( ) .( ) ()( ) ( )nnnniiiL xl x f xl x f xlx f xl x f x( )nx令()njx则0111()().()().()jjjjjjjnxxxxxxxxxx01()().()nxxxxxx0()njjxx因此因此 n次次LagrangeLagrange插值多项式还可表示成插值多项式还可表示成0( )( )().()()nnjjnjjxL xf xxxx解解 先计算先计算4

51、4个节点上的基函数：个节点上的基函数：1230010203()()()( )()()()(0)(1.00)(2.00)( 2.000)( 2.00 1.00)( 2.002.00)1(1)(2),24xxxxxxlxxxxxxxxxxx xx 0231101213()()()1( )(2)(1)(2),()()()4xxxxxxl xxxxxxxxxx0132202123()()()1( )(2) (2),()()()3xxxxxxl xxx xxxxxxx 三次三次LagrangeLagrange插值多项式为：插值多项式为： 0123303132()()()1( )(2) (1).()()(

52、)8xxxxxxlxxx xxxxxxx3171( )(1)(2)(2)(1)(2)244217(2) (2)(2) (1).38L xx xxxxxxx xxx x f (0.6) L3(0.6) = -0.472. n 次插值多项式的误差次插值多项式的误差定理定理 设 Ln(x)是 a,b 上过插值点(xi, f(xi), i = 0, 1, 2, n的 n 次 Lagrange 插值多项式，节点 xi 两两互异，若 f (x)Cn+1a,b, 则xa,b, 存在=(x)a,b, 使得(1)(1)01( )( )( )()().()( ).(1)!(1)!nnnnnffRxxxxxxxxn

53、nv Lagrange插值的优缺点插值的优缺点 优点：优点：形式整齐、规范，理论上保证插值的存在唯一性。形式整齐、规范，理论上保证插值的存在唯一性。 缺点：缺点：计算量大，计算量大，重复计算多，重复计算多，不具有承袭性。不具有承袭性。 Newton插值插值010201011( )()()().()().()nnP xaa xxaxxxxaxxxxxx具有如下形式设插值多项式)(xP因此，每加一个节点时，只附加一项上去即可因此，每加一个节点时，只附加一项上去即可。01,.,naaa如 何 确 定 系 数？( )()(),0,1,.,iiP xP xf xin应满足插值条件000()()P xf

54、xa有110110()()()P xf xaa xx00()af x10110()()f xf xaxx22012022021()()()()()P xf xaa xxaxxxx20102010221()()()()f xf xf xf xxxxxaxx再继续下去待定系数的形式将更复杂010201011()()()().()().()nnP xaaxxaxxxxaxxxxxx01,.,na aa为了简化的表达形式，我们首先引入函数差商（也称均差）的定义。一阶差商：一阶差商：f (x)关于点关于点x0，x1的一阶差商记为的一阶差商记为 f x0, x1，010101()(),.f xf xf x

55、xxx二阶差商：二阶差商： f (x)关于点关于点x0，x1， x2的二阶差商记为的二阶差商记为 f x0, x1, x2,011201202,.f xxf x xf xx xxx011120110,.,.,.,.kkkkkf xxxf x xxf xxxxxx性质性质1 1 k 阶差商阶差商 f x0, x1, xk可表成节点上函数值可表成节点上函数值 f (x0), f (x1), , f (xk) 的线性组合，即的线性组合，即 0101101,.,().().()().()kkiiiiiiikif xxxf xxxxxxxxx例如例如，k k = 2= 2时，时，011201202012

56、010210122021,()()().()()()()()()f xxf x xf xx xxxf xf xf xxxxxxxxxxxxx0101,.,.,.kkiiif xxxf xxx由性质由性质1 1知，任意改变节点的次序，只改变公式右端求和的知，任意改变节点的次序，只改变公式右端求和的次序，故其值不变。例如次序，故其值不变。例如, ,由定义知，由定义知，01011001()(),.f xf xf xxf x xxx性质性质 3 若若 f (x)为为 n 次多项式，则一阶差商次多项式，则一阶差商 f x, xi为为n 1次次 多项式。多项式。由定义由定义( )() ,.iiif xf

57、xf x xxx令令x = xi , 则分子为则分子为0, 说明分子中含有因子说明分子中含有因子x xi , 与分母约去。与分母约去。(1)01( ) ,.,( , ).(1)!nnff x xxxa bn解解 (7)016( ) ,2 ,2 ,.,2 1,7!ff x(8)017( ) ,2 ,2 ,.,2 0.8!ff x01(1)(2)4 1192 ,2 115,1 21fff例例 对 f (x) = x7x4+3x+1， 求 f 20,21， f x,20,21,26 和 f x,20,21,27。显然， f (7) (x) = 7!, f (8) (x) = 0, 由性质4得i xi

58、 f (xi) 一阶差商一阶差商 二阶差商二阶差商 三阶差商三阶差商 n 阶差商阶差商0 x0 f (x0)1 x1 f (x1) f x0, x12 x2 f (x2) f x1, x2 f x0, x1, x23 x3 f (x3) f x2, x3 f x1, x2, x3 f x0, x1, x2, x3 n xn f (xn) f xn 1, xn f xn 2, xn 1, xn f xn 3, xn f x0, x1, , xnv 差商的计算差商的计算00010101201101( )( ) () , ()() , ,. ()().() , ,.,nnnN xf xx x f x

59、 xx xx x f x x xx xx xx xf x xx 0101010( )()().() ,., ,.,().nnnnniiR xxxxxxxf x x xxf x x xxxx插值误差为：插值误差为：00010101201101( )( ) () , ()() , ,()()() , ,nnnN xf xx x f x xx xx x f x x xx xx xx xf x xx 由插值的唯一性，由插值的唯一性，Ln(x) = Nn(x)。因此，。因此，Newton插值是插值是Lagrange插值的另一种表示插值的另一种表示形式。形式。他们的他们的误差也相同误差也相同，即当，即当

60、f (x)Cn+1a, b时，有时，有(1)0100( ) ,.,()()(1)!nnnniiiiff x x xxxxxxn(1)01( ) , ,., , ,( , )(1)!nnff x x xxxa ba bn 故得差商的性质故得差商的性质4解解 首先列差商表首先列差商表i xi f (xi) f xi 1, xi f xi 2, xi 1, xi f xi 3, xi 2, xi 1, xi0 0 2 171 1 0 1 -80 1 -82 2 1 2 1 31 2 1 33 3 2 19 17 8 2 19 17 8 5/45/42000101012( )()() ,()() ,1