数值分析-全部-知识点.docx

Charpter1其中t（字长）是正整数； b一般取为2,8,10和16；C（阶码）是整数，LcU，L和U为固定整数；称为尾数；数x称为t位b进制浮点数。计算机对数的运算处理 1.加减法先对阶，后运算，再舍入；2.乘除法先运算，再舍入。定义1.1 设x是准确值，x*是x的一个近似值，称差 x*x为近似值x*的绝对误差，简称误差，记为e*或e (x*) ，即e (x*)= x*x定义1.2 称满足的正数e *为近似值x*的误差限。该范围常用表示。定义1.3 设x是准确值，x*是x的近似值，称为近似值x*的相对误差，记为e*r或er(x*)，即称满足的正数*为x*的相对误差限。，m为整数，k为不小于正整数n的整数。若有关系式 则称近似数x*有n位有效数字。1.已知近似数x*有5位有效数字，试求其相对误差限。解 因为x*有5位有效数字，可以设于是有n=5和考虑x*的相对误差故有x*相对误差限为0.510 -4 。若x*有n位有效数字，则有若x*的相对误差则x*有n位有效数字。例 1.6 为保证某算式的计算精度，要求参与计算的的近似值x*的相对误差小于0.1%，请确定x*至少要取几位有效数字才能达到要求。解先将写成浮点数。因为得到a1=2。假设x*至少要取n位有效数字才能保证相对误差小于0.1%，由定理1.3的1.5式的最小整数n即可。由得，有，故x*至少要取4位有效数字才能达到相对误差小于0.1%的要求。例1.9选用一个数值稳定方法计算数列的直接推导有递推公式故其带有误差的对应计算公式为为考察其数值稳定性，二式相减得该公式由开始，依次可计算出其在每次计算过程中，都将上次计算的误差放大5倍。记则可知：计算In时的误差为初始误差的5n倍！因此该算法不是数值稳定算法。下面采用逆序计算方式给出一个数值稳定的计算公式将转换为该式由开始，依次计算出，其舍入误差关系为这说明，在每次计算过程中，都将上次计算的舍入误差缩小5倍，因此该算法是数值稳定算法。该算法的关键是取计算的初值,这里采用如下定积分估计的方法选取：因为取均值其初始误差为 用此做递推计算，依次算出，它们值所有误差会超过。Chapter2则称的收敛阶为p或方法具有p阶敛速, p1且C1时称方法超线性收敛。二分法基本思想：利用连续函数零点定理，将含根区间逐次减半缩小，构造点列来逼近根x*。于是当时，由得到说明由二分法产生的数列总是收敛于根x*的,其具有二阶收敛。简单迭代法基本思想：利用对方程做等价变换根不发生变化的特点，将方程等价变形为，获得迭代计算公式由它算出逼近根x*的数列。判别收敛的充分条件。定理2.1 设迭代函数满足两个条件1.当时，有；2.，存在常数满足则有1.在中有唯一的不动点;迭代公式对任取，产生的数列都收敛于。证明存在性易证迭代函数。作辅助函数显然。由条件1知由中值定理，至少存在一个，使，即，这说明在上有不动点。唯一性如果在上还有一个不动点，有，利用条件2，有矛盾，这就证明了满足定理条件的在中有唯一的不动点，记为。的收敛性由是不动点、迭代格式及条件2，有注意到，在上式中令，可得，有 ，因而有定理得证。推论2.1 设迭代函数满足1当时，有，定理2.2 设是迭代函数的不动点，且在点处连续，则若，迭代局部收敛；若，迭代发散，证明 只给出1的证明。由和在点处连续性，存在一个正实数L1和的某个闭邻域，使时有成立。注意到，当时，由及中值定理有所以时，有，由推论2.1可知迭代产生的数列4对任意都收敛于不动点，故迭代格式局部收敛。例2.4用简单迭代法求方程在附近的根，计算结果准确到4位有效数字。解：令因为，在时，故原方程在内有唯一的根。将原方程改写得迭代函数 。为观察在内的取值，注意到，故在单调下降。由，有。于是有当时，。此外，易得当时由推论2.1，可得迭代格式对任取产生的数列都收敛。由，得计算结果准确到4位有效数字时应有误差限。取进行迭代计算， 所以取 。注意到本题准确根为 1.3688081，显然以上算出的近似根满足要求。定理2.4 设是迭代函数的不动点，m为正整数，且在的邻域内连续，并有关系：，则有产生的数列在上是m阶收敛的，且有 （2.9）Newton迭代法基本思想：将函数做线性化处理（即将在某点展开为Taylor级数后，取其线性部分代替），把方程转化为对应的近似方程，再从中构造迭代公式。定理5 设，且在的领域内有二阶连续导数，则Newton迭代格式至少是平方收敛的（Newton不动点方程）。证明 由条件知在成立Taylor公式：，在与之间将代入，设，用同除上式两端，并利用Newton迭代公式，整理后可得所以有证毕。定理6 设，满足下列3个条件；存在且不变号。例2.8 用Newton迭代法求例2.4中非线性方程在附近的根，计算到。解 令 考虑区间，由及在内有，满足定理6的条件，要，取，用Newton迭代法计算：有 所以即为所求。Chapter 3线性方程组的迭代解法基本思想（与简单迭代法类比）将线性方程组等价变形为以构造向量迭代格式用算出的向量迭代序列去逼近解。1）Jacobi迭代法构造原理将上式写成迭代格式(Jacobi迭代格式): 3）取定初始向量，代入，可逐次算出向量序列，这里。Seidel迭代格式:Sor法的迭代格式对线性方程组先将其写成不动点方程组由 得Sor迭代 Ax=b，将系数矩阵A作如下分解 Jacobi迭代的向量迭代格式Seidel向量迭代格式，。Sor法的向量迭代格式n维向量空间矩阵空间连续函数空(1)的向量范数1) 2) 3) (2) 的矩阵范数矩阵范数要满足如下四条1），有,且；2），有；3），有4），有（相容性）定义3.3 设矩阵，称为矩阵A的算子范数。例：设为矩阵的算子范数，证明若，则为非奇异矩阵，且证：用反证法。若为奇异矩阵，则其对应的方程组有非零解，即有，使，得出两边取范数并作范数运算，矛盾，得非奇异。常用的矩阵范数有如下4种1）列范数：2）行范数：3）F范数：4）2范数：，是最大特征值。定理3.2 。式中是上任何一种范数。定理3.3 设为任意算子范数，则有；证明 设是A的任意一个特征值，为对应的特征向量，则有取范数，得因为，上式同除，得由k的任意性可得。1）收敛条件，定理：线性迭代格式对任意初始向量都收敛的充要条件是迭代矩阵谱半径。证明 必要性，设，在中令，得，两式相减并把k+1记为k，得由及的任意性，有。再由引理，可得。充分性，因为，则有I-B非奇异（这里I为单位矩阵），从而线性方程组有唯一解，即有展开有。类似必要性处理，有由引理，由有，上式取极限，得。定义3.6，设1）如果A的主对角元素满足 则称矩阵A是严格行对角占优阵；2）如果A的主对角元素满足则称矩阵A是严格列对角占优。定理 严格对角占优阵是非奇异矩阵。证明 不妨设矩阵是严格行对角占优阵。用反正法。若A是奇异的，则由矩阵理论可知，齐次线性方程组有非零解，即存在，满足。记将的第m个等式写为等式两边取绝对值有因为，上式同除，有此与A是严格行对角占优阵矛盾。故若A是非奇异的。l 判别条件设矩阵A是严格对角占优阵，则线性方程组的Jacobi迭代和Seidel迭代对任意初始向量都收敛。证明 只对A是行对角占优情况证之。设矩阵A是严格行对角占优阵，则有， Jacobi迭代矩阵，故有由判别条件，可得Jacobi迭代的收敛性。对Seidel迭代，其迭代矩阵，设是矩阵的任一特征值，则有特征方程因，故矩阵的特征方程变为这个行列式方程对应的矩阵如果，利用矩阵A的行对角占优定义，可以得出如下不等式这说明矩阵也是行严格对角占优阵，由定理，有。矛盾，故应有成立。由的任意性有谱半径，于是可得Seidel迭代的收敛性。例3.1 用Jacobi 迭代法解线性方程组 5x1+2x2+3x3= -12x1+4x2+2x3= 202x1-3x2+10x3= 3要求误差解 本题的Jacobi迭代格式为它的Jacobi迭代矩阵为。因为，故本题的Jacobi迭代格式对任意初值都收敛。取初值进行迭代计算如下故所求近似解为。（准确解为）Gauss构造原理Gauss消元法的求解过程分为两个:“消元”：把原方程组化为上三角方程组；“回代”：求上三角方程组的解。例3.4 研究下面线性方程组的Gauss消元法求解结果，假设计算在4位浮点十进制数的计算机上求解。当将方程组输入计算机后，计算机中记录为可以进行Gauss消元法计算。因为，做第一步Gauss消元法，有类似有，得方程组回代，求得解，但这个解不满足原方程组，求出的解是错误的！若将本例的方程组调换方程的次序，变为在同一个计算机上再用Gauss消元法计算，可得到解，它与原方程组的准确解，相差不多，是可以接受的解，主要是舍入误差造成的。LU分解法：基本思想：将方程组的系数矩阵A分解为下三角矩阵L与上三角矩阵U的乘积，即，使求解的问题变为求解两个三角矩阵和的问题。即 Doolittle分解算法A可以进行Doolittle分解的条件，定理3.11：非奇异矩阵A的Doolittle分解是唯一的。定理3.12设，且A的各阶顺序主子式，则A有唯一的Doolittle分解。即：能进行Gauss消元法就能做Doolittle分解。Doolittle分解的紧凑格式按下图方式存贮和计算的格式称为Doolittle分解的紧凑格式。例3.6用LU分解法求解线性方程组解 因为没有指定用哪种LU分解，这里使用Doolittle分解法做之。用紧凑格式计算。紧凑格式故，求解解得求解得所求解为定义3.8 设非奇阵，称为矩阵A的条件数。条件数值越大，解对系数越敏感方程组越病态。Chapter4幂法：基本思想:利用矩阵的特征值与特征向量的关系构造迭代向量序列来求矩阵按模最大的特征值及其相应规范化幂法算法1.输入矩阵A、初始向量，误差eps，实用中一般取；2.k13.计算V(k) Au(k-1)4.mk max(V(k), mk-1 max(V(k-1)5.u(k) V(k)/mk 6.如果|mk - mk-1|eps,则显示特征值mk 和对应的特征向量u(k),终止7kk+1,转3；Jacobi方法：基本思想：将实对称矩阵进行一系列的相似正交变换使其约化成一个近似对角矩阵，然后利用相似正交变换的关系来求全部特征值和特征向量。QR方法，基本思想：利用矩阵的QR分解，通过逆序相乘产生对原矩阵的一系列正交相似变换，使其变化为一个近似的上三角矩阵来求全部特征值。这里QR分解是指将矩阵化为一个正交矩阵Q和一个上三角矩阵R左乘的形式。QR算法 对作QR分解，得到矩阵。 逆序相乘的分解矩阵， 判别是否为主对角线为1*1或2*2的子块形式的分块上三角形矩阵，若是对角线上各子块的特征值为所求特征值，终止，否则k+1k，转。定义4.2 设非零向量，则称矩阵为Householder矩阵，式中。例4.3 设向量，试构造一个镜面反射矩阵P，使，式中。解 ，得所求镜面反射矩阵。Chapter 5 Lagrange插值：基本思想将待求的n次多项式插值函数改写成用已知函数值为系数的n+1个待定n次多项式的线性组合型式，再利用插值条件和函数分解技术确定n+1个待定n次多项式形式求出插值多项式。构造原理已知数表 设n次插值多项式式中是与无关的n次多项式。由插值条件（5.1），有由于与无关，可得为确定，注意到是n次多项式，由式可知式中a为待定常数，由确定，于是有 代入式（5.3），有定理3. 设函数在a,b上有n+1阶导数，是满足插值条件的n次插值多项式，则有对任何成立式中。 证明 因为，故有于是Rn（x）可分解为为求出k(x)，做辅助函数则有在时，g(t)=0，即g(t)在a,b上有n+2个零点，显然g(t)在由组成的n+1个小闭区间上满足Rolle中值定理，故g(t) 在a,b上有n+1个零点。类似的有g(t) 在a,b上有n个零点，反复运用Rolle中值定理，有在a,b上有1个零点，设为x，则有。在上式两边对t求n+1阶导数，有将t =x 代入上式，代入式（5.8），即得定理结果。例1 已知的函数表为x3.03.13.23.33.4y=f(x)1.0986121.1314021.1631511.1939221.223775试用线性插值和抛物线插值分别计算的近似值，并估计相应的误差。解 线性插值需要两个节点，内插比外推好，因为，故选，由的Lagrange 插值公式，有所以有为保证内插，对抛物线插值，选取三个节点为由n=2的Lagrange 插值公式，有故有考虑误差.当时，有，所以线性插值计算的误差估计为而当时，故抛物线插值计算的误差估计为例2在上给出的等距节点函数表，若想用二次插值来计算的近似值，并要求截断误差不超过，问此函数表的步长h应为多少？解 设为上的等距节点。二次插值需要三个节点，为满足一般性，这里取三个相邻的节点构造二次插值函数。设是上的任何三个相邻节点，则当时，有注意到。利用n=2的Lagrange余项定理，有函数在的插值余项为因为,所以 要，只需，得取h=0.0057可满足要求.由得，故造表时取1405个等距节点来计算函数值即可。2.Newton 插值，基本思想：Newton插值也是n次多项式函数作为新基底，将待求的n次插值多项式Pn(x)改写成新基底的线性组合形式，然后利用插值条件确定Pn(x)的待定系数来求插值函数。定义 已知函数f(x)在互异节点上的值分别为，记式中是中互不相同的k+1个节点，称为f(x)关于节点的k阶差商。表.1 差商表xf(x)一阶差商二阶差商n阶差商.例3 给定数表x124568f(x)028121828试用二次和四次Newton插值多项式计算的近似值。解 作差商表xf(x)一阶差商二阶差商三阶差商四阶差商五阶差商1021/301/30-1/602231/31/6-1/124841-1/35126-1/36185828用二阶Newton插值近似计算，应选与5.8最近的3个节点。由表中行数据有所以有。要用来计算，取与5.8最近的5个节点由表中行数据有 所以。3.Hermite插值例4设有四阶导数，且1）求函数的一个插值多项式，并用此近似函数来计算的近似值2）给出你所得插值多项式的误差关系式，估计近似计算的误差。解 仿照Lagrange插值函数的构造方法来做之。给定4个数据信息，选择3次多项式作为的插值多项式。令的3次插值多项式为式中都是与无关的3次多项式。插值的特点是插值函数要与给定的关于的所有数据相等，即满足插值条件由此可得有关的一组值利用这组数据，可得函数分解形式并求出。为求，找到与之有关的数据由该数据可知x=2是的二重根，且是3次多项式，故可设的分解形式为由，可以求出式中的a,b，最后求得类似地可以求出其它3个待定函数故有所求插值函数从而有，为求其余项，令由，有可分解为基本思想仿照Lagrange插值函数的构造方法，先设定函数形式，再利用插值条件求出插值函数。例 5已知函数的4个数值为1试求的一个插值多项式，这里满足插值条件。 写出的误差估计式。解 因为有4个值，故取P（x）为三次多项式，令式中都是三次多项式。由插值条件有，当时，得当x=2时，可得利用的4个值，及是三次多项式，可设由，得c = -1；由，得b = -1；由，得a =-1,于是有同理可设由在x =1,x =2的值可得于是所求观察余项在x=1，x=2的信息，可写出误差关为分段多项式插值：基本思想将被插函数的插值节点由小到大排序，以每对相邻的两个节点为端点获得若干个小区间，然后在每个小区间上都用的m次插值多项式作为的近似函数。定理 8 假设出现在如下不等式中的函数的高阶导数存在，记，则有1. 分段线性插值的误差估计为2. 分段三次Hermite插值函数的误差估计为证明 只对结果2给出证明，结果1可类似证明。由两点的Hermite插值余项可知，在区间上，分段三次Hermite插值函数与被插值函数的误差关系式又因为故对k= 0，1，n有 注意到上式右端与x属于哪个小区间无关，这就证明了结果2。5.4曲线拟合法，基本思想：根据给定的数据点，选择合适的拟合函数类M，再利用最小二乘法确定具体的拟合函数。法方程组为例7给定数据表xi-3-1013yi-1.21.31.51.92求二次拟合曲线。解 求二次拟合曲线就是求2次最小二乘多项式，由于没给出权系数，可选。下面用两种方法求解。取基函数，则二次拟合曲线函数形式为本题有5对数据，故，计算得法方程组解之得 ，故所求二次拟合曲线为例8为试验某种新药的疗效，医生对某人用快速静脉注射方式一次注入该药300mg后，在一定的时期采取血样，测得血药浓度数据如下0.250.511.52346819.2118.1515.3614.1012.899.327.455.243.01试确定血药浓度C与时间t的关系。解 在平面坐标上画出散点图并观察此图形状，发现其呈现负指数曲线特点，故选择拟合模型为 两边取对数，得 令，则有线性模型本题没有强调某次注射具有不同的重要程度，因此可以认为权。于是有的法方程组为求解得，从而故血药与时间的关系为。例 9 ，求在上关于权函数的二次最佳平方逼近多项式。解 有题意知 ，即，设所求最佳平方逼近多项式为其对应的法方程组分别计算系数解得故所求的最佳平方逼近多项式为。Chapter 6，例 6.1确定求积公式的代数精度。解 故本题求积公式代数精度为1。例 6.2确定下面求积公式的参数A，B，C，使它具有尽可能高的代数精度，并指出相应的代数精度。解 本题要先求出具体的求积公式，然后再判断所求公式的代数度。公式有3个待定参数，h不是求积公式的参数，故利用