数值分析重点公式

1、第一章非线性方程和方程组的数值解法1）二分法的基本原理，误差：b ax2k 12）迭代法收敛阶：limi1piic0 ，若 p1 则要求 0c13）单点迭代收敛定理：定理一：若当 x a, b 时， (x)a,b 且 (x)l 1， xa, b ，则迭代格式收敛于唯一的根；定理二：设( x) 满足： x a, b 时， ( x)a,b ， x1, x2a, b ,有 ( x1 ) (x2 )l x1 x2 ,0 l 1则对任意初值x0a,b 迭代收敛，且：定理三：设( x) 在的邻域内具有连续的一阶导数，且 ( )1 ，则迭代格式具有局部收敛性；定理四：假设( x) 在根的邻域内充分可导，则迭

2、代格式xi 1( xi ) 是 P 阶收敛的( j ) ( ) 0, j1, ,P 1,(P) ( ) 0 （Taylor 展开证明）4） Newton 迭代法： xi 1xi f ( xi ) ，平方收敛f ( xi )5） Newton 迭代法收敛定理：设 f ( x) 在有根区间a, b 上有二阶导数，且满足： f (a) f (b)0 ；： f (x)0, xa, b ；： f 不变号 , xa, b：初值 x0 a, b 使得 f ( x) f (x)0 ；则 Newton 迭代法收敛于根。6）多点迭代法： xi 1xif ( xi )f (xi ) f (xi 1 )f ( xi

3、)f (xi 1 )xi 1xif (xi ) f (xi 1)f (xi 1 ) f ( xi )xixi 115收敛阶： P27） Newton 迭代法求重根（收敛仍为线性收敛），对Newton 法进行修改：已知根的重数 r ， xi 1xir f ( xi ) （平方收敛）f ( xi )：未知根的重数： xi 1xiu( xi ) ,u( x)f ( x) ，为 f ( x) 的重根，则为 u( x) 的u ( xi )f ( x)单根。8）迭代加速收敛方法：xi xi 2xi21xi 1xixi 22xi 1xi1(xi)xi2(xi 1 ) ( )L1,0当不动点迭代函数( x)

4、在的某个邻域内具有二阶导数，平方收敛9）确定根的重数：当Newton 迭代法收敛较慢时，表明方程有重根10）拟 Newton 法f1f1f1x1ix2ixnif2f 2f2其中 Ai F ( xi )x1ix2ixnifnf nfnx1ix2ixni11）秩 1 拟 Newton 法：Broyden 秩 1 方法第二章线性代数方程组数值解法1）向量范数：非负性：x0 ，且 x0 的充要条件是x0 ；：齐次性：xx：三角不等式：xyxyn1 范数：x2 范数：x1 xii 1n21(2xi )2i 1范数： xmax xi1innp1p 范数： x p) p(xii12）矩阵范数：非负性：A0，

5、且 A0 的充要条件是 A0 ；：齐次性：AA：三角不等式：ABA B：乘法不等式：AB AB1F范数： Ann22Fi1j 1aijn1范数： A1maxaij1 j ni 1n范数： A1maxaij1 i nj 1，列和最大，行和最大2 范数：A( AH A) ，其中( AH A)maxi，i 为 AH A 的特征值，( A)A21 in3） Gauss 消元法（上三角阵）：M1 n3 ；3Gauss-Jordan 消元法（对角阵）： M1n3 ；2列选主元消元法：在消元之前进行行变换，将该列最大元素换置对角线主元位置；（可用于求逆矩阵）全选主元消元法：全矩阵搜索矩阵最大元素进行行变换和

6、列变换至其处于对角线主元位置；4）三角分解法： Doolittle分解法： A=LU，L 单位下三角阵， U上三角阵： Crout 分解法： A=LU，L 下三角阵， U 单位上三角阵： Cholesky 分解法： A 对称正定， ALLT ，L 为单位下三角阵：改进的Cholesky 分解法： A 对称正定， ALDLT ， L 为单位下三角阵，D为对角阵：追赶法： Crout 分解法解三对角方程5）矩阵的条件数 cond( A)AA 11，谱条件数： cond2(A) A2A126）如果 B 1，则 IB 为非奇异阵，且(IB) 111 B7）迭代法基本原理：迭代法： xi1Bx iK：

7、(B) 1(lim Bi0 ，迭代格式收敛 )i：至少存在一种矩阵的从属范数，使B18） Jacobi 迭代： A L DU9） Gauss-Seidel迭代： xi 1(LD ) 1Uxi(LD ) 1 b10）超松弛迭代法 xi 1xir i 111）二次函数的一维搜索：x2x11 P112）最速下降法：选择方向 Z0gradf ( x0 )r 0bAx0进行一维搜索： x1x00 r 0 ，其中0(r 0 , r 0 )( Ar 0 , r 0 )13）共轭梯度法：第一步：最速下降法，P0r 0 ， r1bAx1 ， (r 0 ,r 1)0第二步：过 x1 选择 P0的共轭方向 P1r

8、1P0 ，其中(r1 , AP0 ) ，过 x1 以 P1为方(P0 , AP0)x2x11P1向的共轭直线为 xx1tP1 ，进行二次函数的一维搜索(r 1, P1 )1( AP1, P1 )14）一般的共轭梯度法：第三章 插值法与数值逼近1） Lagrange 插值： Ln ( x)n( x) f ( xj ) ，l jj0余项： E( x)f (n1) () Pn 1 ( x)( n1)!2） Newton 插值：差商表f (x)f (x0)f x0 x1(xx0)f x0 x1xn(x x0)(x xn 1)f x0 x1xnx(xx0) (x xn) 余项E(x)f x0 x1 xn

9、 x( xx0 )( xxn )f ( n1) ( ) Pn 1( x)(n1)!3）反插值4） Hermite插值（待定系数法）n( x) f ( xjH 2 n 1 (x)j ( x) f ( x j )j)j0其中j ( x)(ax b)l 2j(x), a2l j ( xj ), b12x j l j (x j),l j ( x j )n1j xjk1,kxk余项： E( x)f (2 n 2) () Pn21 ( x)(2 n2)!5）分段线性插值：L j ( x)xx j 1f (x j )xx jf ( x j 1 )x jx j 1x j 1x jxx1 , xx x0, x0

10、x xn 1插值基函数： l 0 ( x)x001xxn 1x1, ln (x), xn 1x xn0, x1x xnxnxn 1余项：分段余项M 2h2 , M 2maxf (2) ( x)86）有理逼近：反差商表有理逼近函数式：f ( x) v0 ( x0 )x x0x x1v1( x1 )x xn 1v2(x2 )vn (xn )7）正交多项式的计算：定理：在 a, b 上带权函数( x) 的正交多项式序列n (x) 0 ，若最高项系数唯一，它便是唯一的，且由以下的递推公式确定其中 ( i , jb(x) ij dx)a定理 3.88）连续函数的最佳平方逼近：在Span1, x, x2

11、, , xn 上，法方程为 H n ad ，其中 H n11 21 (n1)( f , k )f ( x) k dx1 21 31 ( n 2) ， dk101 (n1) 1 (n2)1 (2 n1)22n(P* , f )ai* di均方误差：( f , f )f 2i 1最大误差：maxfP*0 x 19）离散函数的最佳平方逼近（曲线的最小二乘拟合）：法方程n( j ,k ) aj( f , k )j0m( j , k )ij ( xi ) k ( xi )其中i0m( f , k )i f ( xi ) k ( xi )i0第四章数值积分1）代数精度的概念及应用：对r 次多项式的精确成立

12、，以及代入法求解系数。2） Lagrange 插值代入Lagrange 插值基函数l j( x x0 ) ( xx j 1 )( x x j 1 ) ( x xn )( xjx0 ) (x jx j 1 )( xjx j 1 ) (x j xn )bn，其中 H jbH j f ( xj )af (x)dxl j (x)dxj0a误差： E( f )b f ( n 1)( )Pn 1( x)dxa (n 1)!定理：数值积分公式具至少有n 次代数精度其是差值型的3）等距节点的 Newton-Cotes公式将拉格朗日差值积分公式中的差值节点xi a ih 即可，其中 hb a ；n( 1)n j

13、hnnH j（ Cotes 系数）则：H jj !( nj )!(t i )dt ，令 C j0i 0,i jbaN-C 公式的数值稳定性：当 C jnC j （其同号时是稳定的，否则不稳定，(ba)j0中maxj ）0 j nN-C 公式至少具有 n 次代数精度，若 n 为偶数，则其代数精度可提高到n+1 次；余项：当 n 为偶数时，f (n 2)()bE( f )xPn 1 (x)dx(n2)!af (n 1)( )b当 n 为奇数时， E( f )Pn 1 (x)dx( n1)!a4）复化的 N-C 公式复化的梯形公式：将积分区间n 等分，然后在每个区间上应用梯形公式复化的 Simpso

14、n 公式：将积分区间n 等分，然后在每个区间上应用Simpson 公式5） Romberg积分法Tm (h) 逼近 I ( f ) 的阶为 h2( m 1)6）求积节点为n+1 的机械求积公式的代数精度=2n+1；7） Gauss 求积公式Pn 1 (x) 在 a ， b 上与所有次数 =n 的多项式带权1正交上式为 Gauss 求积公式、8） Gauss-Legendre 求积公式给出 Pn1 (x) 公式： P0 ( x) 1、 P1 ( x)x 、(3 x21) Pn (x)1 d n2nP22nn ( x1)2 n! dx给出区间 1,-1上的求积公式，取 Pn ( x) 的零点为求积

15、节点 取 P1 ( x) 零点为 0 取 P2零点为33对于区间 a,b上的 Gauss 求积公式，令 xa2bb a t , ta,b ，f (x) f ( a bba t) g(t ) ，则：222余项：E( f )ba g 2( n 1) ( ) 121(t)(tt0 )(t tn )2(2n 2)!Pn 1 (t)dt , Pn1第五章乘幂法1）基本定理：定理一：若1 ,2 ,n 为A 的特征值，P( x)为某一多项式，则矩阵P( A) 的特征值是P(1), P(2 ), P(n )。特别地，Ak 的特征值是1k ,2k ,nk 。定理二：如果A 为实对称矩阵，则A 的所有特征值均为实

16、数，且存在n 个线性无关的特征向量；不同特征值所对应的特征向量正交。定理三：设A 与B 为相似矩阵，即存在非奇异阵P，使PAP 1B ，则A 与B 有相同的特征值。定理四：如果A 有n 个不同的特征值，则存在一个相似变换矩阵P，使得P 1APD ，其中D 是一个对角矩阵，它的对角线元素就是A 的特征值。定理五：对于任意方阵A，存在一个酉变矩阵Q，使得 Q H AQT ，其中T 是一个上三角矩阵，Q H是 Q 是共轭转置矩阵。推论：如果 A 是实对称矩阵，则存在一个正交矩阵Q，使 Q T AQD ，其中 D 是对角矩阵，它的对角线元素是A 的特征值，而Q 的各列即为 A 的特征向量，并且QTQ

17、QQTI。定理六：设 A( aii)n n ,Ci (i1, n) 是以 aii 为中心的一些圆，其半径为n, n ，设nCi ，则 A 的所有特征值都位于区域riaik, i1,内。k 1,kii1推论： A 1 的谱半径满足1naik ) 。1min( aii( A)1i nk 1,ki定理七：设 A 为对称正定阵，则有( A)maxxH Ax1minx H Ax，其中， xH，1Hx 0xx(A)x 0xx是任意复向量，xH 表示 x 的共轭转置。定理八：对任意非奇异矩阵A，有1i2( AT A) ，其中i 为 A 的任一特(ATA) 1征值。2）求按模最大的特征值和对应的特征向量vm

18、Aum 1Amv0， max(vm )1max(Am 1v0 )3）第六章常微分方程的数值解法（差分法）1）离散化方法： Taylor展开、差商代替求导、数值积分y(xn 1 )y( xn 1 )hf (xn , y(xn )2） Euler 公式：y0Euler 隐式 y( xn 1) y(xn 1 )hf ( xn 1 , y( xn 1 ) （ 1 阶）y0改进的 Euler 公式 y(xn 1 )h, y( xn 1 ) （ 2 阶精确解）y( xn 1 )2 ( f (xn , y(xn ) f ( xn 1y03）截断误差和P 阶精确解：截断误差Tn 1O( hP 1 )4） S

19、级 Runge-Kuta 法2 级 Runge-Kuta 法b111yn 1ynhb1k1 hb2 k22c21k1f (xn , yn )其中 b2（ 2阶精度）2c2k2f (xnc2 h, ynh 21k1c221c2 的取值 1/2 （中点公式）、2/3 （Heun公式）、 1（改进的 Euler 方法）5）单步法yn1ynhf ( xn , yn , h) （ * ）相容性：( xn , yn ,0)f ( xn , yn ) 则（ * ）式与初值问题相容收敛性：对于固定的 xnx0 nh 当 h 0 时有 yny(xn ) 则称（ * ）式收敛数值稳定性：若一数值方法在yn 上有扰动 Sn 而于以后的各节点值 ym (