数值分析复习资料.doc

数值分析^p 复习资料 - 第一章 非线性方程和方程组的数值解法 1〕二分法的根本原理，误差：x-?~b?a k?122〕迭代法收敛阶：limi-?i?1?ip?c?0，假设p?1那么要求0?c?1 3〕单点迭代收敛定理： '定理一：假设当x-a,b?时，?(x)-a,b?且?(x)?l?1，?x-a,b?，那么迭代格式收敛于唯一的根； 定理二：设?(x)满足：①x-a,b?时，?(x)-a,b?， ②?x1,x2-a,b?,有 ?(x1)-(x2)?lx1?x2,0?l?1 那么对任意初值x0-a,b?迭代收敛，且： 1xi?1?xi1?l li-xi?x1?x01?l-xi?定理三：设?(x)在?的邻域内具有连续的一阶导数，且?'(?)?1，那么迭代格式具有部分收敛性； 定理四：假设?(x)在根?的邻域内充分可导，那么迭代格式xi?1-(xi)是P阶收敛的??(j)(?)?0,j?1,,P?1,?(P)(?)?0〔Taylor展开证明〕 4〕Newton迭代法：xi?1?xi?5〕Newton迭代法收敛定理： 设f(x)在有根区间a,b上有二阶导数，且满足： ①：f(a)f(b)?0； ②：f(x)?0,x-a,b?； 'f(xi)，平方收敛 f'(xi)-③：f不变号,x-a,b? ''④：初值x0-a,b?使得f(x)f(x)?0； ''那么Newton迭代法收敛于根?。

6〕多点迭代法：xi?1?xi?f(xi)f(xi)f(xi?1)?xi?1?xi f(xi)?f(xi?1)f(xi)?f(xi?1)f(xi?1)?f(xi)xi?xi?1收敛阶：P?1?5 2f(xi)〔平方收敛〕 f'(xi)7〕Newton迭代法求重根〔收敛仍为线性收敛〕，对Newton法进展修改 ①：根的重数r，xi?1?xi?r②：未知根的重数：xi?1?xi?根 8〕迭代加速收敛方法： u(xi)f(x)，?为f(x)的重根，那么?为u(x)的单,u(x)?''u(xi)f(x)xixi?2?xi2?1xi?1?xi?2?2xi?1?xixi?1-(xi)xi?2-(xi?1)平方收敛 ?'(?)?L?1,09〕确定根的重数：当Newton迭代法收敛较慢时，说明方程有重根 当不动点迭代函数?(x)在?的某个邻域内具有二阶导数，xixi?2?xi2?1xi?11 r-xi?2?2xi?1?xixi?2?xi?1xi?2?xi?110〕拟Newton法 ?xi?1?xi?Ai?1F(xi)?i?1ii?1i?1?Ai?1(x?x)?F(x)?F(x)假设Ai非奇异，那么Hi?Ai?A?A-Aii?i?1 i?1ii?x?x?HiF(x)?i?1ii?1i?Hi?1(F(x)?F(x))?(x?x)?H?H-Hii?i?1?f1-?f1?f1i-?xi?xi?xn12-?f2-?f2?f2?iii?'i?xn其中Ai?F(x)-x1?x2- --?f?f?fnn-niii-?xn-x1?x2?11〕秩1拟Newton法： ?xi?1?xi?Ai?1F(xi)?iT,其中ri?xi?1?xi,yi?F(xi?1)?F(xi) ?(r)iiA?A?(y?Ar)ii?i?1(ri)Tri?Broyden秩1方法 ?xi?1?xi?HiF(xi)-(ri)THi ii?Hi?1?Hi?(r?Hiy)(ri)THyii?第二章 线性代数方程组数值解法 1〕向量范数： ①：非负性：x?0，且x?0的充要条件是x?0； ②：齐次性：?x-x ③：三角不等式：x?y?x?y 1范数：x1-xi?1ni 122范数：x2?(?xi) i?1?n2?范数：xp范数：x?maxxi 1?i?np?(?xi) i?1np1p2〕矩阵范数： ①：非负性：A?0，且A?0的充要条件是A?0； ②：齐次性：?A-A ③：三角不等式：A?B?A?B ④：乘法不等式：AB?AB F范数：AF?2--?aij? ?i?1j?1?nn1?j?n121范数：A1?max?ai?1nij，列和最大 ?范数：A1?max?aij，行和最大 1?i?nj?1n2范数：A2-(AHA)，其中?(AHA)?max?i，?i为AHA的特征值，?(A)?A 1?i?n3〕Gauss消元法〔上三角阵〕：M? 13n； 313Gauss-Jordan消元法〔对角阵〕：M?n； 2 列选主元消元法：在消元之前进展行变换，将该列最大元素换置对角线主元位置；〔可用于求逆矩阵〕 全选主元消元法：全矩阵搜索矩阵最大元素进展行变换和列变换至其处于对角线主元位置； 4〕三角分解法： ①：Doolittle分解法：A=LU，L单位下三角阵，U上三角阵 ②：Crout分解法：A=LU，L下三角阵，U单位上三角阵 ③：Cholesky分解法：A对称正定，A?LL，L为单位下三角阵 ④：改良的Cholesky分解法：A对称正定，A?LDL，L为单位下三角阵，D为对角阵 ⑤：追赶法：Crout分解法解三对角方程 ?15〕矩阵的条件数cond(A)?AA?1，谱条件数：cond2(A)?ATT2A?1 2?xxCond(A)-AA1?Cond(A)?AA ?16〕假如B?1，那么I?B为非奇异阵，且(I?B)?1 1?B7〕迭代法根本原理： ①：迭代法：xi?1?Bxi?K ii-②：?(B)?1(?limB?0，迭代格式收敛) ③：至少存在一种矩阵的附属范数，使B?1 8〕Jacobi迭代：A?L?D?U xi?1?(I?D?1A)xi?D?1b 9〕Gauss-Seidel迭代：x10〕超松弛迭代法xi?1i?1-(L?D)?1Uxi?(L?D)?1b ?xi-ri?1 11〕二次函数的一维搜索：x2?x1-1P1 12〕最速下降法： 选择方向Z0-gradf(x0)?r0?b?Ax0 (r0,r0)进展一维搜索：x?x-0r，其中?0? (Ar0,r0)10013〕共轭梯度法： 第一步：最速下降法，P?r，r1?b?Ax1，(r0,r1)?0 00(r1,AP0)11P第二步：过x选择P的共轭方向P?r-P，其中-?0，过以为方x0(P,AP)10?x2?x1-1P1?11向的共轭直线为x?x?tP，进展二次函数的一维搜索?(r1,P1) -1?(AP1,P1)?14〕一般的共轭梯度法： 第三章 插值法与数值逼近 1〕Lagrange插值：Ln(x)-l(x)f(x)， jjj?0nlj(x)?(x?x1)(xj?x1)(x?xj?1)(x?xj?1)(xj?xj?1)(xj?xj?1)(x?xn)(xj?xn)?Pn?1(x) (x?xj)Pn'?1(xj)f(n?1)(?)余项：E(x)?Pn?1(x) (n?1)!2〕Newton插值：差商表 x0 f(x0) x1 f(x1) x2 f(x2) x3 f(x3) f[x0 x1] f[x0 x2] f[x0 x3] f[x0 x1 x2] f[x0 x1 x3] f[x0 x1 x2 x3] f(x)?f(x0)?f[x0 x1](x?x0)-f[x0 x1xn](x?x0)(x?xn?1)?f[x0 x1xnx](x?x0)(x?xn)余项E(x)?f[x0 x13〕反插值 xnx](x?x0)f(n?1)(?)(x?xn)?Pn?1(x) (n?1)!第 页 共 页。