《计算方法》定理公式总结归纳

xxxxxxree||*)(*)(rxxxxre*)(第一章1.设某量的准确值为x，近似值为x*，则称e(x*)=x-x*为近似值x*的绝对误差；|e(x*)|=|x-x*|≤ε,称ε为x*的绝对误差限；称为x*的相对误差；εr为x*的相对误差限。2.对数学问题而言，如果输入数据有微小扰动，引起输出数据（即数学问题的解）有很大扰动，则称数学问题是病态问题，否则称为良态问题。3.。为为该问题的条件数，记则称满足如果能找到一个数相对误差假设，，对应的函数值为，设两个不同的数据))(((,)()()(,re.0)(,0),()(xfCondmrmeRmxfxfxfRxxxxfxxfxfxx4.定义：一个算法如果输入数据有扰动（即有误差），而计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定的。（误差的定性分析法：即研究算法的数值稳定性）5.数值计算中值得注意的问题：（1）防止相近的两数相减(2)防止大数吃小数(3)防止接近零的数做除数(4)注意计算步骤的简化,减小运算次数6.误差的来源：1、模型误差2、观测误差3、截断误差4、舍入误差实际问题的真解与数学模型之间有误差，这种误差称为模型误差(描述误差)由于测量工具的精度、观测方法或客观条件的限制,使数据含有测量误差,这类误差叫做观测误差或数据误差在数值求解数学问题时，常常用有限过程逼近无限过程，用能计算的问题代替不能计算的问题。这种精确公式用近似公式代替时,所产生的误差叫截断误差。由于计算机字长有限，一般实数不能精确存储，于是产生舍入误差。第二章6.如果在区间[a,b]内方程f(x)=0只有一个根，称[a,b]为隔根区间。求隔根区间有两种方法有描图法和逐步搜索法。7.二分法就是将方程的有根区间对分，然后再选择比原来区间缩小一半的有根区间，如此继续下去，直到得到满足精度要求的根为止的一种简单的区间方法。定理2.1：f(x)在[a,b]内连续，α是方程f(x)在隔根区间[a,b]内的根，则由二分法产生的数列{xn}收敛于方程的根α,且有误差估计式),1,0(2||nabxnn二分法控制误差ε常用的方法有(1)先计算对分次数再对分。由kab2计算得abn2log得到满足误差要求的最少对分次数。(2)事后误差估计法,先对分再判断所得中点是否满足误差要求(3)由于nnnnabxxx2||||1故可用||1nnxx来判断误差。8.迭代法的求解步骤(1)建立迭代公式。由公式f(x)=0出发将其分解为等价形式x=φ(x),式中φ(x)叫做方程的迭代函数.(2)进行迭代计算。由初值x0出发，按迭代函数进行计算),2,1,0)((1nxxnn称为迭代公式。数列{xn},称为迭代序列。该过程称为迭代过程.9若从任何可取的初值出发都能保证收敛，则称它为大范围收敛。如若为了保证收敛性必须选取初值充分接近于所要求的根，则称它为局部收敛。定理2.2（收敛定理）：设方程x=φ(x)，如果设方程x=φ(x)，如果(1)迭代函数φ(x)在区间[a,b]可导；(2)当x[a,b]时，φ(x)[a,b]；(3)对于任意的x[a,b]，有1|)(|Lx。则有①方程x=φ(x)在区间[a,b]上有唯一的根α；②对于任意的初值x0[a,b]，由迭代公式)2,1,0)((1nxxnn产生的数列{xn}收敛于方程的根α。③||1||1nnnxxLLx④误差估计||1||01xxLLxnn定理2.3（迭代法的局部收敛定理）：设α是方程x=φ(x)的根，如果(1)迭代函数φ(x)在α的邻域可导；(2)在α的某个邻域S={x:|x-α|≤δ},对于任意的xS有1|)(|Lx则对于任意的初值x0S，迭代公式xn+1=φ(xn)产生的数列{xn}，收敛于方程的根α。（这时称α的S领域具有局部收敛性。）收敛法控制误差ε的方法有：(1)先计算满足误差要求的迭代次数n，再迭代。由||1||01xxLLxnn可得LxxLnln||)1(ln01(2)事后误差估计法。由于||1||1nnnxxLLx因而可用|xn-xn-1|≤ε来控制迭代过程。10.迭代-加速公式：nnnnnxqqxqxnxx1~11),2,1,0)((~111埃特金加速公式:nnnnnnnnnnnxxxxxxxxxnxx122121121~2~)~(),2,1,0)((~定理2.4：如果由迭代公式xn+1=φ(xn)产生的数列{xn}满足(1)收敛于根α；(2))2,1,0(0),10(lim1nxecceennnnx则由埃特金加速公式产生的数列{xn}比数列}{nx较快地收敛于根α，即0limnnxxx11.牛顿迭代公式：)()(1nnnnxfxfxx定理2.5（牛顿迭代法的局部收敛定理）设α是方程f(x)=0的根，如果(1)函数f(x)=0在α的邻域有连续的二阶导数(2)在α的邻域f’(x)≠0则存在α的某个邻域}|:|{xxS，对于任意的初始值Sx0，由牛顿迭代公式产生的数列收敛于根α。定理2.6（牛顿迭代法收敛定理）设α是方程f(x)=0在隔根区间[a,b]内的根，且满足bax,,)(),(xfxf连续且不变号；(2)选取初始值bax,0使0)()(00xfxf。则由牛顿迭代公式产生的数列收敛于根α。12.定义:设数列}{nx收敛于α,令误差nnxe,如果存在某个实数1p及正常数C，使Ceepnnn||||lim1则称数列}{nxp阶收敛，也称相应的迭代法为p阶方法。当1p且10C时，称数列}{nx为线性收敛.当p=2时，称数列}{nx平方收敛（或二阶收敛）.当p1时，称数列}{nx为超线性收敛。定理2.7:（1）在定理2.3的条件下，且在根α的某个邻域内有0)(x，则迭代法是线性收敛的。（2）在定理2.6的条件下，牛顿迭代法是平方收敛的。13.单点弦截法迭代公式:)()()(00001xfxfxfxxxxnnn；双点弦截法迭代公式：),2,1()()()()()()()(111111nxfxfxfxxfxxfxfxfxxxxnnnnnnnnnnnnn定理2.8:设α是方程f(x)=0在隔根区间[a,b]内的根，且满足(1))(),(,,xfxfbax连续且不变号；(2)选取初始值bax,0，使0)()(00xfxf。选定a，b中的一个，则x1为另一个。则有单点弦截迭代法公式产生的数列收敛于根α。（单点弦截法的收敛阶为1）。定理2.9:设方程f(x)=0，如果(1)f(x)在根α的某个邻域具有连续的二阶导数，且f’(x)≠0;(2)任取x0,x1属于该邻域。则由双点弦截迭代法公式产生的数列收敛于根α。（双点弦截法是超线性收敛，收敛阶为(1+√5)/2）第三章14.高斯消元法的求解过程可大致分为两个阶段:(1)把原方程组化为上三角形方程组,称之为“消元”过程;(2)用逆次序逐一求出上三角方程组(原方程组的等价方程组)的解,称之为“回代”过程.15.定义3.1:设A为n阶矩阵，L为n阶下三角阵，U为n阶上三角阵。如果A=LU，则说明矩阵A实行了三角分解或LU分解。16.定义3.2:如果L为单位下三角阵，U为上三角阵，则称该三角分解为杜里特（Doolittle）分解；如果L为下三角阵，U为单位上三角阵，则称A=LU为克劳特（Crout）分解。定理3.1：n阶（n≥2）矩阵A有唯一杜里特分解（或克劳特分解）的充要条件是A的前n-1个顺序主子式都不为零。定理3.2:设A为对称正定矩阵，则有非奇异下三角阵L，使A=LLT;当限定L的对角元全为正时，这种分解是唯一的。17.直接三角分解法公式（Doolittle）：),,3,2(),,1(),,1,(),,3,2(),2,1(1111111111nknkiauulalnkkjaulauniualnjauikkkkmmkimikikkjkmmjkmkjkjiijj18.平方根法求解公式：),,3,2;,,2,1()(1),,3,2(1111211111111nknkkjllalllalnklalalkmjmkmjkkkjkkmkmkkkkjj19.追赶法的分解形式及公式：11111211122111122211nnnnnnnnnnbacbacbacb＝)1,,3,2(),,3,2(,,111111niniiiiiiiiiicbacb20.定义3.3设迭代矩阵B为n阶矩阵，)(Bi为矩阵B的特征值，称)(max)(1BBini为矩阵B的谱半径。定理3.3：设简单迭代公式为),2,1,0()()1(kgBxxkk对于任意的初始向量)0(x和g，该简单迭代法都收敛的充要条件是：1)(B定理3.4：设简单迭代公式为),2,1,0()()1(kgBxxkk如果1max111niijnjbB或1max11njijnibB，则简单迭代法对任意初始向量)0(x和g都收敛。21.定义3.4设nmijaA)(，如果矩阵A满足条件),,2,1(1niaanijiijii或者),,2,1(1niaanijiijjj即A的每一行（列）对角线上的元素的绝对值都严格大于同行（列）其它元素绝对值之和，则称A为严格对角占优矩阵。定理3.5：如果线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111的系数矩阵A是严格对角占优矩阵，则雅克比迭代法对任意的初始向量)0(x和g都收敛。定理3.6：设有赛德尔迭代公式gxBxBxkkk)(2)1(1)1(记矩阵nnijbBBB)(21。如果1max111niijnjbB或1max11njijnibB，则简单迭代法对任意初始向量)0(x和g都收敛。22.定义：设V是数域F上的线性空间，Vx，若存在唯一实数x与其对应，且满足以下三条公理，(1)正定性：0x0,0xx且(2)齐次性：Fkxkkx,(3)三角不等式：Vyxyxyx,,则实数x称为向量x的范数。把定义了范数的线性空间称为赋范线性空间。23.。常用的范数有如下三种,),,,(:21nTnnRxxxxR（1）向量的1-范数：niix11x;(2)向量的2-范数：21212)(xniix;(3)向量的∞范数：inix1maxx。均可表示为p范数的形式：一般可表示为,,2,1,)(11pxxpnipiP。（定理：有限维空间中的范数等价。）24.定义：设向量序列Vunn1}{，若存在Vu，使得0lim),(limuuuunnnn称向量序列Vunn1}{收敛于ulim,nnuu25.定义：基本迭代法gBxxkk)()1(产生的迭代序列}{)(kx，如果对任取初始向量)0(x都有xlim)(kkx，则称此迭代法是收敛的，否则是发散的。（在Rn中，点列的收敛等价于每个分量的收敛。即，），，，（，对nT*n*2*1*)()(2)(1)(Rxxxx),,,(Tknkkkx