数值分析复习资料 56页

数值分析复习资料一、重点公式第一章非线性方程和方程组的数值解法1）二分法的基本原理，误差：2）迭代法收敛阶：，若则要求3）单点迭代收敛定理：定理一：若当时，且，，则迭代格式收敛于唯一的根；定理二：设满足：①时，，②则对任意初值迭代收敛，且：定理三：设在的邻域内具有连续的一阶导数，且，则迭代格式具有局部收敛性；定理四：假设在根的邻域内充分可导，则迭代格式是P阶收敛的ó（Taylor展开证明）4）Newton迭代法：，平方收敛5）Newton迭代法收敛定理：设在有根区间上有二阶导数，且满足：①：；②：；③：\n④：初值使得；则Newton迭代法收敛于根。6）多点迭代法：收敛阶：7）Newton迭代法求重根（收敛仍为线性收敛），对Newton法进行修改①：已知根的重数r，（平方收敛）②：未知根的重数：，为的重根，则为的单根。8）迭代加速收敛方法：当不动点迭代函数在的某个邻域内具有二阶导数，平方收敛9）确定根的重数：当Newton迭代法收敛较慢时，表明方程有重根10）拟Newton法\n其中11）秩1拟Newton法：Broyden秩1方法第二章线性代数方程组数值解法1）向量范数：①：非负性：，且的充要条件是；②：齐次性：③：三角不等式：1范数：2范数：范数：p范数：2）矩阵范数：①：非负性：，且的充要条件是；②：齐次性：③：三角不等式：\n④：乘法不等式：F范数：1范数：，列和最大范数：，行和最大2范数：，其中，为的特征值，3）Gauss消元法（上三角阵）：；Gauss-Jordan消元法（对角阵）：；列选主元消元法：在消元之前进行行变换，将该列最大元素换置对角线主元位置；（可用于求逆矩阵）全选主元消元法：全矩阵搜索矩阵最大元素进行行变换和列变换至其处于对角线主元位置；4）三角分解法：①：Doolittle分解法：A=LU，L单位下三角阵，U上三角阵②：Crout分解法：A=LU，L下三角阵，U单位上三角阵③：Cholesky分解法：A对称正定，，L为单位下三角阵④：改进的Cholesky分解法：A对称正定，，L为单位下三角阵，D为对角阵⑤：追赶法：Crout分解法解三对角方程5）矩阵的条件数，谱条件数：6）如果，则为非奇异阵，且7）迭代法基本原理：①：迭代法：\n②：(ó，迭代格式收敛)③：至少存在一种矩阵的从属范数，使8）Jacobi迭代：9）Gauss-Seidel迭代：10）超松弛迭代法11）二次函数的一维搜索：12）最速下降法：选择方向进行一维搜索：，其中13）共轭梯度法：第一步：最速下降法，，，第二步：过选择的共轭方向，其中，过以为方向的共轭直线为，进行二次函数的一维搜索14）一般的共轭梯度法：第三章插值法与数值逼近1）Lagrange插值：，余项：2）Newton插值：差商表\n余项3）反插值4）Hermite插值（待定系数法）其中余项：5）分段线性插值：插值基函数：余项：分段余项6）有理逼近：反差商表有理逼近函数式：\n7）正交多项式的计算：定理：在上带权函数的正交多项式序列，若最高项系数唯一，它便是唯一的，且由以下的递推公式确定其中定理3.88）连续函数的最佳平方逼近：在上，法方程为，其中，均方误差：最大误差：9）离散函数的最佳平方逼近（曲线的最小二乘拟合）：法方程其中第四章数值积分1）代数精度的概念及应用：对r次多项式的精确成立，以及代入法求解系数。2）Lagrange插值代入Lagrange插值基函数，其中误差：定理：数值积分公式具至少有n次代数精度ó其是差值型的\n3）等距节点的Newton-Cotes公式将拉格朗日差值积分公式中的差值节点即可，其中；，令（Cotes系数）则：N-C公式的数值稳定性：当同号时是稳定的，否则不稳定，（其中）N-C公式至少具有n次代数精度，若n为偶数，则其代数精度可提高到n+1次；余项：当n为偶数时，当n为奇数时，4）复化的N-C公式复化的梯形公式：将积分区间n等分，然后在每个区间上应用梯形公式复化的Simpson公式：将积分区间n等分，然后在每个区间上应用Simpson公式5）Romberg积分法\n逼近的阶为6）求积节点为n+1的机械求积公式的代数精度<=2n+1；7）Gauss求积公式在[a，b]上与所有次数<=n的多项式带权正交ó上式为Gauss求积公式、8）Gauss-Legendre求积公式给出公式：、、······给出区间[1,-1]上的求积公式，取的零点为求积节点①取零点为0②取零点为\n对于区间[a,b]上的Gauss求积公式，令，，则：余项：第五章乘幂法1）基本定理：定理一：若为A的特征值，为某一多项式，则矩阵的特征值是。特别地，的特征值是。定理二：如果A为实对称矩阵，则A的所有特征值均为实数，且存在n个线性无关的特征向量；不同特征值所对应的特征向量正交。定理三：设A与B为相似矩阵，即存在非奇异阵P，使，则A与B有相同的特征值。定理四：如果A有n个不同的特征值，则存在一个相似变换矩阵P，使得，其中D是一个对角矩阵，它的对角线元素就是A的特征值。定理五：对于任意方阵A，存在一个酉变矩阵Q，使得，其中T是一个上三角矩阵，是是共轭转置矩阵。推论：如果A是实对称矩阵，则存在一个正交矩阵Q，使，其中D是对角矩阵，它的对角线元素是A的特征值，而Q的各列即为A的特征向量，并且。定理六：设是以为中心的一些圆，其半径为，设，则A的所有特征值都位于区域内。推论：的谱半径满足。定理七：设A为对称正定阵，则有，，其中，x是任意复向量，表示x的共轭转置。\n定理八：对任意非奇异矩阵A，有，其中为A的任一特征值。2）求按模最大的特征值和对应的特征向量，3）第六章常微分方程的数值解法（差分法）1）离散化方法：Taylor展开、差商代替求导、数值积分2）Euler公式：Euler隐式（1阶）改进的Euler公式（2阶精确解）3）截断误差和P阶精确解：截断误差4）S级Runge-Kuta法2级Runge-Kuta法（2阶精度）的取值1/2（中点公式）、2/3（Heun公式）、1（改进的Euler方法）5）单步法（*）相容性：则（*）式与初值问题相容收敛性：对于固定的当时有则称（*）式收敛\n数值稳定性：若一数值方法在上有扰动而于以后的各节点值上产生的偏差均不超过，则称该方法绝对收敛试验方程：用以求解绝对稳定区间绝对收敛：用单步法求解试验方程，若绝对收敛则称该方法绝对稳定6）线性多步法德一般格式：局部阶段误差（系数通过Taylor展开构造）其中线性多步法的阶数通过误差系数来判断，最高阶数7）线性多步法的收敛性判断：称线性多步法相容满足根条件：第一特征多项式，第二特征多项式当第一特征多项式所有根的模均不大于1，且模为1的根均是单根，称满足根条件收敛ó相容且满足根条件8）数值稳定性判断：稳定多项式（特征多项式）令，是稳定多项式的根，①：若对任意有，且当时，为单根，则称为相对稳定区间；①若对任意有，则称为绝对稳定区间\n二、典型例题第一章典型例题例3ln2=0.69314718…，精确到10－3的近似值是多少？解精确到10－3＝0.001，即绝对误差限是e＝0.0005,故至少要保留小数点后三位才可以。ln2»0.693第二章典型例题例1用顺序消去法解线性方程组解顺序消元于是有同解方程组回代得解x3=－1,x2=1,x1=1,原线性方程组的解为X＝(1,1,－1)T例2取初始向量X(0)=(0,0,0)T,用雅可比迭代法求解线性方程组解建立迭代格式\n(k=1,2,3,…)第1次迭代,k=0X(0)＝0，得到X(1)＝(1,3,5)T第2次迭代，k=1X(2)＝(5,－3,－3)T第3次迭代，k=2X(3)＝(1,1,1)T第4次迭代，k=3X(4)＝(1,1,1)T例4证明例2的线性方程组，雅可比迭代法收敛，而高斯－赛德尔迭代法发散。证明例2中线性方程组的系数矩阵为A＝\n于是D＝D－1＝D雅可比迭代矩阵为B0＝得到矩阵B0的特征根，根据迭代基本定理4，雅可比迭代法收敛。高斯－赛德尔迭代矩阵为G＝－＝－解得特征根为l1=0，l2,3=2。由迭代基本定理4知，高斯－赛德尔迭代发散。例5填空选择题：1.用高斯列主元消去法解线性方程组作第1次消元后的第2，3个方程分别为。\n答案：解答选a21=2为主元，作行互换，第1个方程变为：2x1+2x2+3x3=3，消元得到是应填写的内容。3.用高斯－赛德尔迭代法解线性方程组的迭代格式中＝(k=0,1,2,…)答案：解答：高斯－赛德尔迭代法就是充分利用已经得到的结果，求x2的值时应该用上x1的新值。第三章典型例题例1已知函数y=f(x)的观察数据为xk－2045yk51－31试构造拉格朗日插值多项式Pn(x)，并计算f(－1)的近似值。[只给4对数据，求得的多项式不超过3次]解先构造基函数\n所求三次多项式为P3(x)=＝＋－＋＝f(－1)»P3(－1)＝例3设是n+1个互异的插值节点，是拉格朗日插值基函数，证明：(1)(2)证明(1)Pn(x)=y0l0(x)+y1l1(x)+…+ynln(x)=当f(x)º1时，1＝由于，故有(2)对于f(x)=xm,m=0,1,2,…,n，对固定xm(0£m£n),\n作拉格朗日插值多项式，有当n>m－1时，f(n+1)(x)=0，Rn(x)=0，所以注意：对于次数不超过n的多项式,利用上结果，有==上式正是Qn(x)的拉格朗日插值多项式。可见，Qn(x)的拉格朗日插值多项式就是它自身，即次数不超过n的多项式在n+1个互异节点处的拉格朗日插值多项式就是它自身。例5已知数据如表的第2，3列，试用直线拟合这组数据。解计算列入表中。n=5。a0,a1满足的法方程组是kxkykxkyk11414224.5493369184481632\n558.52542.5S153155105.5解得a0=2.45,a1=1.25。所求拟合直线方程为y=2.45+1.25x例6选择填空题1.设y=f(x),只要x0,x1,x2是互不相同的3个值，那么满足P(xk)=yk(k=0,1,2)的f(x)的插值多项式P(x)是(就唯一性回答问题)答案：唯一的3.拉格朗日插值多项式的余项是(),牛顿插值多项式的余项是()(A)(B)f(x,x0,x1,x2,…,xn)(x－x1)(x－x2)…(x－xn－1)(x－xn)(C)(D)f(x,x0,x1,x2,…,xn)(x－x0)(x－x1)(x－x2)…(x－xn－1)(x－xn)答案：(A)，(D)。见教材有关公式。第四章典型例题例1试确定求积公式的代数精度。[依定义，对xk(k=0,1,2,3,…)，找公式精确成立的k数值]解当f(x)取1,x,x2,…时，计算求积公式何时精确成立。(1)取f(x)=1,有\n左边＝,右边＝(2)取f(x)=x,有左边＝,右边＝(3)取f(x)=x2,有左边=,右边=(4)取f(x)=x3,有左边=,右边=(5)取f(x)=x4,有左边=,右边=当k£3求积公式精确成立，而x4公式不成立，可见该求积公式具有3次代数。例5试确定求积公式中的参数a，并证明该求积公式具有三次代数精度。解公式中只有一个待定参数a。当f(x)=1,x时，有,即h=h,不能确定a，再令f(x)=x2,代入求积公式，得到,即得.求积公式为将f(x)=x3代入上求积公式，有\n可见，该求积公式至少具有三次代数精度。再将f(x)=x4代入上公式中，有所以该求积公式具有三次代数精度。例6选择填空题1.牛顿－科茨求积公式与高斯型求积公式的关键不同点是。解答：牛顿－科茨求积公式的节点和求积系数确定后，再估计其精度；高斯型求积公式是由精度确定其节点和求积系数。第五章典型例题例1证明方程1－x－sinx＝0在区间[0,1]内有一个根，使用二分法求误差不超过0.5×10－4的根要迭代多少次？证明令f(x)＝1－x－sinx∵f(0)=1>0，f(1)=－sin1<0∴f(x)=1－x－sinx=0在[0，1]有根。又f¢(x)=1－cosx>0(xÎ[0，1]),故f(x)＝0在区间[0，1]内有唯一实根。给定误差限e＝0.5×10－4，有只要取n＝14。例2用迭代法求方程x5－4x－2＝0的最小正根。计算过程保留4位小数。\n[分析]容易判断[1，2]是方程的有根区间。若建立迭代格式，此时迭代发散。建立迭代格式，此时迭代收敛。解建立迭代格式(可任取1，2之间的值)1.43101.50511.51651.51821.5185取1.5185例3试建立计算的牛顿迭代格式，并求的近似值，要求迭代误差不超过10－5[分析]首先建立迭代格式。确定取几位小数,求到两个近似解之差的绝对值不超过10－5。解令，求x的值。牛顿迭代格式为迭代误差不超过10－5，计算结果应保留小数点后6位。当x=7或8时，x3=343或512，,取x0=8,有\n7.4780787.4399567.4397607.439760于是，取7.439760例4用弦截法求方程x3－x2－1＝0，在x=1.5附近的根。计算中保留5位小数点。[分析]先确定有根区间。再代公式。解f(x)=x3－x2－1，f(1)=－1，f(2)=3，有根区间取[1,2]取x1=1,迭代公式为(n=1,2,…)1.376621.488811.46348\n1.46553取1.46553，f(1.46553)»－0.000145例4选择填空题1.设函数f(x)在区间[a,b]上连续，若满足，则方程f(x)=0在区间[a,b]一定有实根。答案：f(a)f(b)<04．牛顿切线法是用曲线f(x)上的与x轴的交点的横坐标逐步逼近f(x)＝0的解；而弦截法是用曲线f(x)上的与x轴的交点的横坐标逐步逼近f(x)＝0的解。答案：点的切线；两点的连线解答：见它们的公式推导.三、复习资料一、用牛顿法求解方程的解，，收敛精度\n一、应用列主元素消元法求解的解，保留4位有效数字二、应用雅可比迭代法求解下列方程组，收敛精度求解过程如表：012345600.720.9711.0571.08531.09511.098300.831.0701.15711.18531.19511.198300.841.1501.24821.28281.29411.29800.840.310.09820.03460.01130.0039\n一、设，应用幂法求解其最大特征值，以及对应的特征向量\n一、用拉格朗日差值法构造三次多项式，求解处的函数值x0.460.470.480.49y0.4846550.4937450.502750.511668要求小数点后4位\n一、已知如下表的函数，试用最小二乘法求二次多项式来拟合这组数据x-1.00-0.75-0.5-0.2500.250.50.751y-0.22090.32950.88261.43922.00032.56453.13343.70614.2836二、用龙贝格求积公式计算积分的近似值，要求收敛精度\n\n用预测-校正的改进欧拉法求解如下常微分方程，取步长为0.1，计算到1.0各阶段计算结果如下：00.10.20.30.40.5000.01600.04370.08410.137800.00550.02190.05010.09090.14500.60.70.80.91.00.20550.28770.38890.49760.62630.21290.29540.39290.50590.6348四、复习总结第二章数值分析基本概念教学内容：1.误差与有效数字误差、误差限、相对误差、相对误差限和有效数字的定义及相互关系；误差的来源和误差的基本特性；误差的计算（估计）的基本方法。2.算法的适定性问题数值分析中的病态和不稳定性问题；病态问题和不稳定算法的实例分析。\n1.数值计算的几个注意问题数值计算的基本概念l误差概念和分析误差的定义：设x是精确值，p是近似值，则定义两者之差是绝对误差:由于精确值一般是未知的,因而Δ不能求出来,但可以根据测量误差或计算情况估计它的上限相对误差定义为绝对误差与精确值之比l误差的来源：舍入误差将无限位字长的精确数处理成有限位字长近似数的处理方法称为舍入方法。带来舍人误差。\n截断误差用数值法求解数学模型时，往往用简单代替复杂,或者用有限过程代替无限过程所引起的误差。l有效数字对于a=a0a1…am.am+1…am+n(a0≠0)的近似数，若|Δ|≤0.5x10-n，则称a为具有m+n+1位有效数字的有效数，其中每一位数字都叫做a的有效数字。有效数和可靠数的最末位数字称为可疑数字有效数位的多少直接影响到近似值的绝对误差与相对误差的大小。推论1对于给出的有效数，其绝对误差限不大于其最末数字的半个单位。推论2对于给出的一个有效数，其相对误差限可估计如下：\n例:计算y=lnx。若x»20，则取x的几位有效数字可保证y的相对误差<0.1%?l数值计算的算法问题“良态”问题和“病态”问题在适定的情况下，若对于原始数据很小的变化δX，对应的参数误差δy也很小，则称该数学问题是良态问题；若δy很大，则称为病态问题。病态问题中解对于数据的变化率都很大，因此数据微小变化必将导致参数模型精确解的很大变化。数学问题的性态完全取决于该数学问题本身的属性，在采用数值方法求解之前就存在，与数值方法无关。稳定算法和不稳定算法\n如果用数值方法计算时,误差在计算过程中不扩散的算法称为稳定算法。否则称为不稳定算法。l数值计算应注意的问题避免相近二数相减；避免小分母；避免大数吃小数；选用稳定的算法。绝对误差的运算：\n第三章线性方程组求解的数值方法教学内容：1.高斯消元法消元法的实现过程；主元问题。2.矩阵分解矩阵LU分解的一般计算公式；利用LU分解的线性方程组求解方法；Cholesky分解；Matlab的Cholesky分解函数。3.向量范数与矩阵范数向量范数及其性质；矩阵函数及其性质；常用范数形式。4.线性方程组的迭代法求解迭代求解的思路；Jacobi迭代法；高斯_赛德尔迭代法；迭代法的收敛性。\n1.方程组的病态问题与误差分析线性方程组解的误差分析；条件数和方程组的病态性。消元法：问题：消去法是按照系数矩阵的主对角线上的元素（主元）进行消元。从而可能出现：（1）某个主元为零，导致消元过程无法进行。（2）当某个主元的绝对值很小时，计算结果误差很大。定理：若A的所有顺序主子式均不为0，则高斯消元无需换行即可进行到底，得到唯一解。全主元消去法每一步选绝对值最大的元素为主元素。列主元消去法省去换列的步骤，每次仅选一列中最大的元。\n矩阵三角分解法计算公式：算法：\nCholesky分解：定理：设矩阵A对称正定，则存在非奇异下三角阵L使得。若限定L对角元为正，则分解唯一。Matlab中的Cholesky分解函数：chol（）向量和矩阵的范数为了研究线性方程组近似解的误差估计和迭代法的收敛性，引进向量（矩阵）的范数的概念。向量范数定义：空间的向量范数||·||对任意满足下列条件：(齐次性)（三角不等式)（正定性)常用范数：\n矩阵范数定义：空间的向量范数||·||对任意满足下列条件：(4)*||AB||£||A||·||B||常用矩阵范数：Frobenius范数：\n由向量范数||·||p导出关于矩阵AÎRn´n的p范数:特别有：（行和范数）（列和范数）（谱范数）谱半径：矩阵A的谱半径记为r(A)=，其中li为A的特征根。定理：对任意算子范数||·||有定理：若A对称，则有定理：\n若矩阵B对某个算子范数满足||B||<1，则必有解线性方程组的迭代法研究内容：l如何建立迭代公式？　l收敛速度？l向量序列的收敛条件？l误差估计？思路：收敛问题：\n雅可比(Jacobi)迭代法高斯—塞德尔迭代法迭代法的收敛性谱半径小于1.迭代法的误差估计：误差分析：\n问题的提出：lb有扰动，A无扰动lA有扰动，b有扰动lA有扰动，b有扰动定义：\n条件数:cond(A)=||A–-1||||A||条件数的性质：结论：当条件数很大时,方程组Ax=b是病态问题;当条件数较小时,方程组Ax=b是良态问题。\n第四章函数的数值逼近1.代数多项式插值问题插值多项式的存在唯一性；插值基函数和插值多项式的一般形式；插值的误差分析；多项式插值的Runge现象。2.分段低次插值分段线性插值；Hermite插值和分段Hermite插值。3.三次样条插值样条插值的定义；三次样条函数的计算；Matlab中的插值函数。4.曲线拟合的最小二乘法曲线拟合的最小二乘法法；多项式拟合方法；Matlab中的多项式拟合函数；5.最佳平方逼近权内积；\n正交多项式的最佳平方逼近。插值问题：函数解析式未知，或计算复杂，用函数p(x)去近似代替它，使得p(xi)=yi(i=0,1,2,…,n)函数p(xi)称为插值函数。x0,x1,…xn称为插值节点或简称节点。插值节点所界的区间称为插值区间。p(xi)=yi称为插值条件。多项式的插值问题构造n次多项式Pn(x)=a0+a1x+a2x2+…+anxn使满足Pn(xi)=yi(i=0,1,2,…,n)，讨论的主要内容：l如何求出插值函数；l插值函数的存在性；l收敛性和误差估计。\n拉格朗日插值插值多项式的存在唯一性：结论通过n+1个节点的n阶插值多项式唯一存在。一次基函数二次基函数拉格朗日插值多项式的一般形式：插值公式：\n插值的误差分析：分段低次插值分段线性插值收敛性：\n埃尔米特插值利用拉格朗日插值基函数得到\nHermite插值的余项三次样条插值\n第五章数值积分1.插值型求积公式线性和二次求积公式；求积公式的代数精度；求积公式的误差分析；复合求积公式；高斯求积公式；MATLAB中的数值积分函数。2.积分方程的数值求解积分方程的数值求解的思路分析；积分方程的数值求解方法介绍。n次代数精度对于任意不超过n次的代数多项式都准确成立,而对某一个m+1次代数多项式不成立,。梯形公式\n辛普森公式：复化梯形公式截断误差：，M2＝复化辛普森公式截断误差：½RN[f]½，高斯求积公式定义高斯点的确定方法\nMatlab积分函数函数名功能quad采用Simpson计算积分。精度高，较常用quad8采用8样条Newton-Cotes公式计算积分。精度高，最常用trapz采用梯形法计算积分。精度差，速度快积分方程的数值求解求解思路用数值积分代替积分\n第六章常微分方程初值问题1.求解方法欧拉方法；龙格—库塔方法2.稳定性与收敛性分析欧拉公式：局部截断误差是O(h2).改进欧拉公式：或表示成：平均形式：局部截断误差是O(h3).龙格—库塔方法\n第七章非线性方程求解教学内容：1.二分法2.收敛性分析3.牛顿法二分法：1.准备：计算端点值f(a),f(b)2.二分：计算中点值f((a+b)/2)3.判断：若f((a+b)/2)=0，(a+b)/2是根；若f((a+b)/2)f(a)<0,用(a+b)/2代替b;否则，用(a+b)/2代替a，转向（2）\n收敛性：二分法的收敛性一般迭代法的收敛性：几个收敛定理牛顿迭代法：