数值分析笔记期末复习

1、第一章引论1、数值分析研究对象：数值分析是计算数学的一个主要部分，计算数学是数学科学的一个分支，它研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现。2、数值分析特点：面向计算机，要根据计算机特点设计切实可行的有效算法有可靠的理论分析，能任意逼近并达到精度要求，对近似计算要保证收敛性和数值稳定性要有好的计算复杂性，时间复杂性好是指节省时间，空间复杂性好是指节省存贮量，这也是建立算法要研究的问题。要有数值试验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验证明是行之有效的。3、数值分析实质：是以数学问题为研究对象，不像纯数学那样只研究数学本身的理论，而是把理论与计算紧密结

2、合，着重研究数学问题的数值方法及理论。4、用计算机解决科学计算问题通常经历以下过程实际问题-数学模型（应用数学）-数值计算方法-程序设计-上机计算结果（计算数学）5、误差来源及分类1.模型误差从实际问题中抽象出数学模型 2.观测误差通过测量得到模型中参数的值 （通常根据测量工具的精度，可以知道 这类误差的上限值。）3.截断误差当数学模型得不到精确解时，要用数值计算方法求它的近似解，由此产 生的误差称为（截断误差）或（方法误差）4.舍入误差由于计算机字长有限，原始数据的输入及浮点数运算过程中都有可能产 生误差，这样产生的误差称为舍入误差6、五个关于误差的概念1.绝对误差2.绝对误差限3.相对误差

3、4.相对误差限（1）定义：设某一量的准确值为x，近似值为x*，则x*与x之差叫做近似值x*的绝对误差(简称误差)，记为（2）性质：(1)绝对误差e(x*) 可正可负 (2) |e(x*) |的大小标志着x*的精确度 (3) 绝对误差e(x*) 未知（3）判断：绝对误差是误差的绝对值？（错）（1）定义：若指定一个适当小的正数，使则称为近似值 x* 的绝对误差限。(有时用表示近似值x*的精度或准确值的所在范围。)（2）性质：(1)在实际问题中，绝对误差一般是有量纲的，绝对误差限也是有量纲的。(2)绝对误差限是正的，有无穷多个【则比大的任意正数均是绝对误差限】（1）定义：绝对误差与准确值之比称为x*

4、的相对误差。（2）性质：(1)相对误差是个无量纲量。值小者精度高。(2)由于准确值x未知，故实际问题中，当 | 较小时，常取（1）定义：若指定一个适当小的正数 ，使则称为近似值 x*的相对误差限。（2）性质：当|较小时，可用下式计算5.有效数字（1）定义：若近似值x*的绝对误差限是某一位的半个单位，该位到x*的第一位非零数字一共有n位，则称近似值x*有n位有效数字，或说x*精确到该位。注意：近似值后面的零不能随便省去！（2）例题：取x1*= 3作为的近似值，则：一个有效数字 取 x2* =3.14 作为的近似值，则：三个有效数字 取 x3* =3.1416作为的近似值，则：五个有效数字 它们的

5、误差都不超过末位数字的半个单位。（3）性质：(1)有效数字越多，则绝对误差越小 (2)有效数字越多，则相对误差越小 有效数字的位数可刻画近似数的精确度！6、一元函数的误差估计问题：设y=f(x)，x的近似值为x*，则y的近似值 y*的误差如何计算？故相应的误差限计算如下7、二元函数的误差估计问题：设y=f(x1, x2)， x1, x2的近似值为x1*, x2* ，则y的误差如何计算？ 故绝对误差限为8、多元函数的误差估计9、加减乘除运算的误差估计加法减法乘法除法绝对误差绝对误差限相对误差相对误差限10、算法的数值稳定性概念及运算（1）定义：初始数据的误差或计算中的舍入误差在计算过程中的传播，

6、因算法不同而异。一个算法，如果计算结果受误差的影响小，就称该算法具有较好的数值稳定性11、设计算法的五个原则(一) 要避免相近两数相减(二) 要防止大数“吃掉”小数，注意保护重要数据求和时从小到大相加，可使和的误差减小。若干数相加，采用绝对值较小者先加的算法，结果的相对误差限较小(三) 注意简化计算步骤，减少运算次数，避免误差积累（秦九韶）(四) 要避免绝对值小的数作除数(五) 设法控制误差的传播许多算法具有递推性。递推法运算过程较规律，但多次递推必然导致误差的积累。 第二章 逼近问题1，函数逼近1、插值问题： 求一条曲线严格通过数据点2、曲线拟合问题： 求一条曲线在一定意义下靠近数据点 2，

7、插值问题1、定义：求一个简单函数(x)作为f(x)的近似表达式，以满足我们称这样的问题为插值问题； 并称(x)为 f (x)的插值函数； f (x)为被插函数， x0 , x1, x2, , xn是插值节(基)点；是插值原则.3，插值多项式1、定义：求一个次数不超过n的多项式使满足插值原则(条件)称Pn(x)为 f (x)的n次插值多项式2、定理：在n+1个互异节点处满足插值原则且次数不超过n的多项式Pn(x)存在并且唯一。注：若不将多项式次数限制为 n ，则插值多项式不唯一。也是一个插值多项式，其中可以是任意多项式。4,插值问题拉格朗日差值牛顿插值二次插值基函数一阶差商k阶差商零阶差商1.差

8、商与节点的排列次序无关，称为差商的对称性2.高阶差商可由低阶差商反复作一阶差商得到，计算具有递推性3.若f(x)在a, b上存在n阶导数，则为了使得|n+1(x)|尽可能小一些，插值基点的选取原则是：使x尽可能位于区间Ix的中部，这里Ix是包含x以及所用基点的最小闭区间。1.计算量省，便于程序设计2.具有承袭性的插值公式，便于理论分析埃尔米特差值插值条件中除函数值插值条件外，还有导数值插值条件，即已知：2n+2个条件求:一个次数不超过2n+1的多项式H2n+1(x)解法1：基函数法解法2：承袭法分段低次插值原因：当插值基点无限加密时，Pn(x)也只能在很小范围内收敛，这一现象称为龙格(Rung

9、e)现象，它表明通过增加基点来提高逼近程度是不宜的。定义：设在a,b上给出插值条件：求一个折线插值函数Ih(x)满足xix0x1xnf(xi)f0f1fn1°Ih(x)是a,b上的连续函数2°Ih(xk)=fk，k = 0,1,n3°Ih(x)在每个小区间xk,xk+1上是线性函数则称Ih(x)为分段线性插值函数数学表达： 性质：1°分段线性插值多项式是分段函数；2°可以预见，但n充分大时，Ih(x)能很好逼近f(x)。3°Ih(x)有一个缺点：在插值点处有尖点，即一阶导数不连续，不够光滑。解决办法：三次埃尔米特插值三次样条插值两种构

10、造方法5，最小二乘法1、 定义：已知：一组实验数据（xi，yi）(i=0,1,m)，且观测数据有误差求：自变量x与因变量y之间的函数关系y=F(x) ，不要求y=F(x)经过所有点，而只要求在给定点上误差按某种标准最小。2、 度量标准：(1)使残差的最大绝对值为最小 (2)使残差的绝对值之和为最小 (3)使残差的平方和为最小 3、最小二乘法多项式拟合已知：一组数据（xi，yi）(i = 0,1,m) 求：在次数不超过n的多项式中找一个函数，使误差平方和最小，即这里：解： 故： 解得：4、最小二乘法非多项式拟合参数线性 已知：一组数据（xi，yi）(i = 0,1,m)求：在函数类中找一个函数

11、，使误差平方和最小，即这里：已知：一组数据（xi，yi），且每个点对应权因子wi >0, (i=1,2,m).求：在函数类中找一个函数 ，使误差平方和最小，即这里：最小二乘法非多项式拟合参数非线性 第三章 定积分1，求解定积分问题方法：（求曲边梯形面积）旧：（1）牛顿莱布尼兹公式 【需要寻求原函数的困难】【已知点离散】新：（2）机械求积公式 【多项式机械求积公式】*【解决原函数的困难】【中矩形公式】*【解决原函数的困难】【梯形公式】*【解决原函数的困难】【插值型求积公式】*【解决离散问题】2，代数精度 （1）目的：数值求积方法是近似方法，为了保证精度，我们自然希望公式能对“尽可能多”的函

12、数准确成立，这就提出了所谓代数精度的概念。（2）定义：若某个求积公式对于次数m的多项式均能够准确成立，但对于m+1次多项式就不一定准确，则称该求积公式有m次代数精度。若某个求积公式对于1, x, xm 均能够准确成立，但对于xm+1就不准确成立，则称该求积公式有m次代数精度。（3）定理：当n为偶数时，牛顿柯特斯公式至少有n+1次代数精度。注：在实际应用时，出于对计算复杂性和计算速度的考虑，我们常常使用低阶偶数求积公式，代替高一阶的奇数求积公式。3，插值求积公式（1）定理：具有n+1个求积节点的机械求积公式至少有n次代数精度的充分必要条件是，它是插值型的。试总结证明机械求积公式是插值型求积公式的

13、方法。（2）求积公式的余项若求积公式的代数精度为m，则余项形如其中K是不依赖于f(x)的待定参数。3，牛顿柯特斯求积公式梯形，辛普森，柯特斯1、 定义【牛顿柯特斯】梯形公式辛甫生(Simpson)公式柯特斯(Cotes)公式一阶【2次代数精度】令f(x)=x2二阶【3次代数精度】令f(x)=x4四阶【5次代数精度】4，复化求积公式1、 定义：为了提高精度通常可把积分区间分成若干子区间，再在每个子区间上用低阶求积公式。这种方法称为复化求积法。 复化求积法就是先用低阶的牛顿柯特斯公式求得每个子区间xk, xk+1上的积分 Ik，然后再求和，用 作为所求积分I的近似值。即复化梯形公式复化辛甫生公式复

14、化柯特斯公式 复化辛甫生公式精度优于复化梯形公式5，高斯求积公式1、 定义：机械求积公式含有2n+2个待定参数：若适当选择这些参数使求积公式具有2n+1次代数精度，则这类公式称为高斯公式。中矩形公式是2、 高斯点定义：高斯公式的求积节点称为高斯点。3、 求一点的高斯公式 设一点高斯公式为则其代数精度应为4、 求二点的高斯公式再设两点高斯公式为代数精度应为5、 高斯点的性质：定理：对于插值型求积公式(4.1)，其节点是高斯点的充要条件是以这些点为零点的多项式与任意次数不超过n的多项式P(x)均正交，即【证明看习题】6、 高斯勒让得公式 特别地，取a, b=-1, 1，其上高斯公式为：下面求对应的

15、高斯点。 对于任意求积区间a, b如何求？作变换可以化到区间-1，1上，这时7、 带权的高斯公式1、定义：求积公式若该公式具有2n+1次代数精度，则称这类公式为带权的高斯公式。上述(x)0是权函数。2、定理：是高斯点的充要条件是是区间a, b上关于(x)的正交多项式。3、特别：若a, b = -1，1，权函数是所建立的高斯公式为【切比雪夫高斯公式】【xk是切比雪夫多项式的零点】第四章 解线性方程组1、分类【一般形式】【矩阵形式】 系数矩阵为低阶稠密矩阵（阶数大约不超过150）【直接法】（经过有限步算术运算，可求得方程组的精确解的方法，一般用于解系数矩阵为低阶稠密矩阵）系数矩阵为大型稀疏矩阵（阶

16、数高且零元素较多）【迭代法】（用某种极限过程去逐步逼近精确解的方法，一般用于解系数矩阵为大型稀疏矩阵）2、范数向量范数矩阵范数类型在Rn上的向量x =(x1, xn)TRn在Rn×n上的矩阵A=(aij),定义设对任意向量 xRn，按一定的规则有一实数与之对应，记为x，若x满足则称x为向量的范数设对任意矩阵 ARn×n，按一定的规则有一实数与之对应，记为A，若A满足则称A为矩阵的范数 称为范数或最大范数【绝对值最大的元素】 称为1范数 称为2范数 称为p范数【所有值绝对值的P次方求和，再开P次方】 称为范数或行范数【所有元素绝对值之和最大的一行】 称为1范数或列范数【所有元

17、素绝对值之和最大的一列】 称为2范数【ATA的最大特征值开平方】 称为Frobennius范数【所有元素平方和开平方】性质定义：如果Rn中有两个范数 |x|s 与 |x|t ，存在常数m, M>0，使对任意n维向量x有则称这两个范数等价.性质：对两种等价范数而言，某向量序列在其中一种范数意义下收敛时，则在另一种范数意义下也收敛。定理：Rn上的任意两个范数等价。【注：今后研究向量序列的收敛性时，可在任何一种范数意义下研究。】3、“病态”方程组1、定义：当一个方程组，由于系数矩阵 A 或右端常数项 b 的微小变化，引起方程组Ax=b解的巨大变化，则称此方程组为“病态”方程组，矩阵A称为“病态

18、”矩阵，否则称方程组为“良态”方程 组，A为“良态”矩阵.2、如何划分“病态”的程度：条件数：设A为非奇异阵，称cond(A)v=|A-1|v|A|v (v =1, 2, ) 为矩阵A的条件数。 【b】 【A】则系数矩阵A的条件数刻划了方程组的“病态”程度。条件数愈大，方程组的“病态”程度愈大，也就愈难得到方程组的比较准确的解；当矩阵A的条件数相对地小，则方程组是“良态”的。4、 线性方程组解法向量序列的收敛性矩阵序列的收敛性定义1设 x(k) 为Rn中的向量序列，xRn，如果其中|.|为向量范数，则称序列 x(n)收敛于 x，记为 设 A(k) 为 n 阶方阵序列，A为n阶方阵，如果其中|.

19、|为矩阵范数，则称序列 A(n)收敛于A，记为 定理1Rn中的向量序列 x(k)收敛于Rn中的向量 x 当且仅当设 A(k) = (aij) (k=1, 2, )，A = (aij)均为 n 阶方阵，则矩阵序列A(n)收敛于矩阵A的充要条件为直接消去法高斯直接消去法基本思想：用逐次消去未知数的方法把原来方程组AX=b化为与其等价的三角形方程组，而求解三角形方程组就容易了！高斯消去法的特点：消元和回代不同步！使用高斯消去法的条件：使用高斯消去法要求在每步消元时， 定理：约化的主元素 (i=1,2,n) 的充要条件是矩阵A的顺序主子式 定理6：如果 n 阶矩阵A的所有顺序主子式均不为零，则可通过高

20、斯消去法（不进行交换两行的初等变换），将方程组约化为三角形方程组。定理6：如果A为 n 阶非奇异矩阵，则可通过高斯消去法（及交换两行的初等变换）将方程组 Ax=b 化为三角形方程组。推论：如果A的顺序主子式不等于0，则主元素法在采用高斯消去法解方程组时，小主元可能产生麻烦，故应避免采用绝对值小的主元素。对一般矩阵，最好每一步选取系数矩阵（或消元后的低阶矩阵）中绝对值最大的元素作为主元素，以使高斯消去法具有较好的数值稳定性！列主元素法：选主元时仅考虑按列选取，然后换行使之变到主元位置上，再进行消元计算。列主元消去法的特点：（1）能够得到较高精度要求的 解 ；（2）计算量大大减少完全主元素法：其中

21、y1,y2,yn为未知数x1,x2,xn调换后的次序。【第一步：首先在A中选取绝对值最大的元素作为主元素；然后交换到第一行、第一列的位置；再进行第一次消元，】完全主元素消去法的缺点：在选主元素时要花费较多机器时间。时时纪录x顺序的变化情况高斯约当消去法高斯约当消去法定义：则同时消去对角线上方和下方的元素。高斯约当消去法的特点：(1) 消元和回代同时进行；(2) 乘除法的次数要比高斯消去法大，所以通常用于同时求解系数矩阵相同的多个方程组或求逆矩阵。直接三角法直接三角分解法定理: (矩阵的LU分解)设 A 为 n 阶矩阵，如果 A 的顺序主子式( i = 1,2,n-1)， 则 A 可分解为一个单

22、位下三角矩阵 L 和一个上三角矩阵 U 的乘积，且这种分解是唯一的。注：若A 实现了LU分解，则Ax = b (LU)x=b Ly = b Ux = y单位下三角阵 上三角阵 解得解得平方根法 A=LDLTA=LLT平方根法适用于系数矩阵为对称正定阵的方程组的求解。定理1 (对称阵的三角分解定理)设A为n阶对称阵，且A的所有顺序主子式均不为零，则A可唯一分解为 A=LDLT其中L为单位下三角阵，D为对角阵.定理2 (对称正定阵的三角分解定理)设A为n阶对称阵，且A的所有顺序主子式均大于零，则存在一个非奇异下三角阵 L 使 A=LLT，当限定L的对角元素为正时，这种分解是唯一的。Cholesky

23、分解追赶法A=LU追赶法适用于系数矩阵为三对角阵的方程组的求解。利用系数矩阵的特点，可以将A分解为两个三角阵的乘积，A=LU，其中L为下三角矩阵，U为单位上三角矩阵。 迭代法雅克比迭代法一般形式矩阵形式将方程组记为 Ax = b其中A非奇异且aii 0 (I=1, 2, , n).将A分裂为 A = D 其中高斯塞德尔将方程组记为 Ax = b其中A非奇异且aii 0 (I=1, 2, , n).将A分裂为 A = D 其中 超松弛迭x(k+1) = x(k) + x <1时，称为低松弛； =1时，是G-S法； >1时，称为超松弛法，简称SOR法用分解式 A = D，则可写为注：(

24、1) 松弛法是G-S法的一种加速方法；(2) 具有计算公式简单，程序设计容易；(3) 但需要选择较好的加速因子。5、 迭代法敛散性判断方法预备定义定义1：称迭代公式中的矩阵 B 为迭代矩阵.定义2：设A为n阶方阵，i (i = 1,n)为A的特征值，称特征值模的最大值为矩阵A的谱半径，记为 定义2：称为矩阵A的谱.定义3：Ak = AAA 的谱为 ( k = 1, 2, )定义3：Ak = AAA 的谱半径为已知定理定理1：设A为任意n阶方阵，|.|为任意由向量:范数诱导出的矩阵的范数，则定理2：设A为n阶方阵，则对任意正数，存在一种矩阵范数|.|，使得定理3：设A为n阶方阵，则的充要条件为辅

25、助定义定义：若n阶方阵 A=(aij)满足且至少有一个 i 值，使上式中不等号严格成立，则称A为弱对角占优阵。若对所有 i，不等号均严格成立，则称A为严格对角占优阵。定义：如果矩阵A不能通过行的互换和相应列的互换成为形式其中A11，A22为方阵，则称A为不可约.收敛判断条件设有线性方程组Ax=b，下列结论成立：1. 若A为严格对角占优阵或不可约弱对角占优阵，则Jacobi迭代法和Gauss-Seidel迭代法均收敛。2. 若A为严格对角占优阵，0<1，则松弛法收敛。3. 若A为对称正定阵，0<<2，则松弛法收敛.即：若A是对称正定阵，则松弛法收敛的充要条件为0<<

26、2。推论：若迭代矩阵满足 |M|<1，则迭代公式产生的向量序列x(k)收敛。 定理：对任意初始向量 x(0)和右端项g，由迭代格式x(k+1) = Mx(k) + g产生的向量序列收敛的充要条件为推论：松弛法收敛的必要条件是 0<<2值得注意的是：改变方程组中方程的顺序，即将系数矩阵作行交换，会改变迭代法的收敛性。第五章 解非线性方程组1、定义求 f (x) = 0 的根：f(x)为非线性函数或高次代数方程，若有数x*使f(x*) = 0成立，则称x*为方程f(x) = 0的根(零点)。若f(x)可分解为当m = 1，称x*是单根；当m > 1，称x*是m重根.2、求根

27、的两个步骤(1)确定根的初始近似值(称之为初始近似根) ，一般为一个包含根的区间，称为“有根区间”【逐步扫描法：原理：设f(x)在a, b连续，且f(a) f(b)<0。则由连续函数的性质知f(x)=0在(a, b)内至少有一个根。若f(x)在a, b上单调，则f(x)=0在(a, b)上有且仅有一个根。】(2)根的精确化。根据根的初始近似值按某种方法逐步精确化，直至满足预先要求的精度为止。【二分法简单迭代法牛顿迭代法弦截法】2、分类二分法原理：若 f ÎCa, b，且 f (a) · f (b) < 0，则 f 在 (a, b) 上必有一根 x*。实施：将方程

28、根的区间平分为两个小区间，然后判断根在哪个小区间，舍去无根的区间，而把有根区间再一分为二，再判断根属于哪个更小的区间，如此周而复始，直到求出满足精度要求的近似根。停止： 或 误差分析：对于给定的精度 e ,可估计二分法所需的步数 k优点：简单; 对f (x) 要求不高(只要连续即可) .缺点：无法求复根及偶重根 收敛慢 简单迭代法基本思想：f(x) = 0【同解变形】x = g(x)【构造公式】xk+1 = g(xk)【给初值x0 ；若xkx*且g(x)连续】x*就是f(x)=0的根区间收敛：设方程 x = g(x)有根x*, g(x)可微，若( I ) 当 xÎa, b 时， g(

29、x)Îa, b；( II ) $ 0 £ L < 1 使得 | g(x) | £ L < 1 对 " xÎa, b 成立。则任取 x0Îa, b，由 xk+1 = g(xk) 得到的序列收敛于g(x) 在a, b上的唯一不动点。注1：定理中的L<1非常重要，否则不能保证收敛，且L越小，收敛越快。注2：为恰当估计 ，可以把有根区间取得适当小。补充：1.迭代是否收敛除了依赖于迭代函数外，还依赖于有根区间。2设方程x=g(x)在区间a,b内有根，若总有,则迭代公式对任意a,b上的初值均发散。局部收敛：定义：设x*是g(x)

30、的不动点，若存在 x* 的某d 邻域 Bd = x | | x - x* | £ d ，对 迭代产生的序列且收敛到x*，则称局部收敛.定理：设x*是g(x)的不动点，若g(x)在 x* 的某 邻域连续，且有| g(x*) | < 1，则迭代法局部收敛。收敛速度：迭代法的收敛阶定义：设迭代 xk+1 = g(xk) 收敛到g(x) 的不动点 x*。设 ek = xk - x*，若则称该迭代为p 阶收敛，其中 C 称为渐进误差常数。特别地： p = 1时：线性收敛， p >1时：超线性收敛， p = 2时：平方收敛 定理：设 x* 为x = g(x) 的不动点，若 ，p &#

31、179; 2；且，则 xk+1 = g(xk) 在内 p 阶收敛。牛顿迭代法原理：将非线性方程线性化泰勒展开局部收敛性设 f ÎC2a, b，若 x* 为 f (x) 在a, b上的根，且 f (x*) ¹ 0，则存在 x* 的邻域使得任取初值Newtons Method产生的序列 xk 收敛到x*，且满足有只要就有 p ³ 2。重根是线性收敛的。注： (1) 牛顿法要求初值充分接近根以保证局部收敛性。(2)牛顿迭代法的主要优点是收敛较快，是平方收敛的缺点是公式中需要求 f(x) 的导数。若 f(x)比较复杂，则使用牛顿公式就大为不便。弦截法针对问题：重根问题问题

32、1: 若，Newtons Method 是否仍收敛？K1: 有局部收敛性，但重数 n 越高，收敛越慢。问题2: 如何加速重根的收敛？K2: 将求 f 的重根转化为求另一函数的单根。令则 f 的重根 = m 的单根。下山法：原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点，使得 l = 1 时就是Newtons Method 公式。当 l = 1 代入效果不好时，将 l 减半计算。 弦截法Newtons Method 一步要计算 f 和 f ，相当于2个函数值，比较费时。现用 f 的值近似 f ，可少算一个函数值。需要 2 个初值 x0 和 x1切线斜率 » 割线斜率弦截法与牛顿法相比较相同之处：都是线性化方法不同之处：牛顿法在计算xk+1时只用到前一步的值xk，故这种方法称为单点迭代法；而弦截法在求xk+1时要用到前两步的值xk和xk-1，因此