计算方法复习重点

1、1. 算法设计与选择时应遵循的若干原则 （5条）2. 误差、有效数字概念。第一章第一章 nkkknxlyxL0)()(1. n次拉格朗日插值多项式次拉格朗日插值多项式第二第二 章章 插值与拟合插值与拟合 nkjjjkjkxxxxxl0)()()(其中其中1(1)( )( )( )( )(1)!( )nnnnfRxf xLxnx,( , )a b01( )niinxxx Lagrange插值余项插值余项32. 差商的计算差商的计算-差商表差商表ix0 x1x2x3x4x( )if x1()f x2()f x3()f x4()f x0()f x01,f x x12 ,f x x23,f x x34

2、,f x x012,f x x x123 ,f x x x234,f x x x0123,f x x x x1234 ,f x x x x01234 , , ,f x x x x x40001(),( )()nf xf xxNxxx10210()(,)xf x x xxxx0011(,()nnxxfxx xxxn次次牛顿插值多项式牛顿插值多项式5. ), 1 , 0)(,( )( 3. 010miyxxaxaxaaxPniinkknnnk 拟拟合合一一组组数数据据次次多多项项式式用用则naaa,10满足法方程组miinimiiimiinminiminiminiminimiimiiminimii

3、yxyxyaaaxxxxxxxxm00010020100102000164. 可化为直线拟合的情形(0)bxyaea所求拟合函数为指数函数lnlnbxyaeyabx 令令ln;lnyy aa yabx 则所求拟合函数转化为iyix1x1ln y2x2ln ymxlnmy由线性由线性拟合拟合方法可得到方法可得到 和和 ，从而，从而得得到到 和和ababiyix1x1y2x2ymxmy原数据表原数据表原数据表变为原数据表变为8梯梯形形公公式式 )()(2)()(bfafabdxxffIba )(Simpson 公公式式抛抛物物线线公公式式 )()2(4)(6)(bfbafafabfI梯形公式 1

4、次代数精度辛甫生公式 3 次代数精度柯特斯公式 5 次代数精度第第3 3章章 数值积分和数值微分数值积分和数值微分11( )( )( )2()2nbknakhf x dxf af bf xT 复合梯形公式 定理: 求积公式至少有n次代数精度的充要条件是它是插值型求积公式。0()()nbkkakfx dxA fx bahn 其其中中11021222()nnnkkbaTTf xn 复合梯形公式的递推公式243nnnTTS 梯形加速公式：Simpson加速公式：21615nnnSSC Cotes加速公式：26463nnnCCR 222441nnSS 323441nnCC 244 1nnTT 图3.3

5、.1计算停止准则:同一行或同一列相邻两数之差的绝对值不超过预先给定的误差. Romberg 算法：201102()()()()f xf xfxhxxh 其其中中中点中点公式公式4 3 .Th考虑方程 x = (x), (x)在a,b上存在，若( I ) 当 xa, b 时， (x)a, b；( II ) 0 L 1 使得 对 xa, b 成立。则 方程x=(x)在a,b上有唯一根x*; 任取 x0a, b，由 xk+1 = (xk) 得到的序列 收敛于x*。 0kkx1( )xL （整体收敛性定理）第四章 非线性方程的数值解法 定理定理 设设 (x)在方程在方程x= (x)的根的根x* *邻近

6、有一阶连续邻近有一阶连续的导数的导数. . 若若 (x* *) 1, 则迭代过程则迭代过程xk+1= (xk)具有局部收敛性具有局部收敛性 若若 (x* *) 1,则迭代过程则迭代过程xk+1= (xk)发散发散. .注: 若x*在x0附近,则可用|(x0)|1代替|(x*)|1, 用 |(x0)| 1代替|(x*)| 1.（局部收敛性定理） 1*( )*( )()kkxxxxxpxx 设为方程的根，在的邻域内有连续的 阶导数，那么对于迭代格式*(1)*( )*(1)01 (2) ()=()=()0,()0 pp|x|xxxxxxp* 当 ()时, 该迭代格式在 邻近线性收敛。当时，该迭代格式

7、在 邻近 阶收敛。定理10 1 2(), , ,()kkkkf xxxkfx Newton 迭代公式有根根唯一产生的序列单调有界保证收敛定理 （非局部收敛定理）若f(x)在a,b上满足下列条件(1) f (a) f (b) 0；(2) 在整个a, b上 不变号且 ；(3) 选取 x0 a, b 使得 ；则Newton迭代法产生的序列 xk 收敛于方程的唯一根f 0( )fx 000()()f xfx , xa b Newton迭代法收敛性依赖于x0 的选取。一、一、 矩矩阵的直接三角分解阵的直接三角分解111211112121212222221,112,1 11nnnnnn nnnnnnnAL

8、Uaaauuulaaauullaaau 即即第五章第五章 线性代数方程组的数值解法线性代数方程组的数值解法L、U元素元素计算公式计算公式n , 2,i , n, 1,j , 111111 ualauiijj 计算量与计算量与 Gauss Gauss 消去法同消去法同. .1111 2, 3, , , , ( )/ 1 , , kkjkjkqqjqkikikiqqkkkqknjkniknual ulal uu 对对计计算算 21二二 解三对角线性方程组的解三对角线性方程组的11112222211111nnnnnnnnnbcxdabcxdAabcxdabxd 则则A分解分解为：为：LU 11111

9、211122111122211nnnnnnnnnnaaabacbacbacb111/,1,1,2,3,iiiiiiibcinbain 23(1)()11()(1,2, )nkkiiijjjiijixba xina Jacobi 迭代公式迭代公式：1(1)(1)( )111()(1,2, )inkkkiiijjijjjj iiixba xa xina Gauss-Seidel 迭代公式迭代公式.三三 迭代迭代 逐次逐次超松弛超松弛( (SOR) )迭代法的迭代法的分量分量形式：形式：1111111 2()( )()( )(), ,inkkiijjijjjj ikkiiiiba xa xxxain

10、 利用高斯利用高斯-塞德尔迭代法求得塞德尔迭代法求得:(1)( )(0)()( )1.kkxBxfxB 迭迭代代法法收收敛敛的的充充要要条条件件迭迭代代格格式式对对任任意意初初始始向向量量都都收收敛敛的的充充分分必必要要条条件件是是定定理理1 1121,2,( )max(,)n ninBRinBB 定定义义：设设的的特特征征值值为为 ()()，称称为为 的的谱谱半半径径。 推论推论设设 ，bAx 其中其中 为非奇异矩阵为非奇异矩阵ADLU且且 非奇异，则非奇异，则 D (1) (1) 解方程组的雅可比迭代法收敛的充要条件是解方程组的雅可比迭代法收敛的充要条件是 ，() 1JB1().JBDL

11、U其中其中 (2)解方程组的高斯解方程组的高斯- -塞德尔迭代法收敛的充要条件是塞德尔迭代法收敛的充要条件是()1,G SB其中其中 (3) 解方程组的解方程组的SORSOR方法收敛的充要条件是方法收敛的充要条件是 ，() 1SORB其中其中 1() (1)SORBDwLw DwU1()G SBLDU 1112121222120nnnnnnJacobiaaaaaaaaa迭代矩阵的特征方程为1112121222120nnnnnnGaussSeidelaaaaaaaaa迭代矩阵的特征方程为11(1,2,)(1,2,)niiijjjinjjijiijAaainaajnA 定定 义义 ： 设设 矩矩 阵阵满满 足足或或则则 称称为为 严严