数值分析总结.docx

《数值分析总结.docx》由会员分享，可在线阅读，更多相关《数值分析总结.docx（37页珍藏版）》请在三一办公上搜索。

1、数值分析总结数值分析复习总结 第二章 数值分析基本概念 教学内容： 1. 误差与有效数字 误差、误差限、相对误差、相对误差限和有效数字的定义及相互关系； 误差的来源和误差的基本特性； 误差的计算的基本方法。 2. 算法的适定性问题 数值分析中的病态和不稳定性问题介绍； 病态问题和不稳定算法的实例分析。 3. 数值计算的几个注意问题 避免相近二数相减； 避免小分母； 避免大数吃小数； 选用稳定的算法。 1.数值分析简介 数值分析的任务 数值分析是研究求解各类数学问题的数值方法和有关理论的学科 数值分析的过程 构造算法、使用算法、分析算法 2. 数值计算的基本概念 l 误差概念和分析 误差的定义：

2、 设x是精确值，p是近似值，则定义两者之差是绝对误差: Da=x-p由于精确值一般是未知的,因而不能求出来,但可以根据测量误差或计算情况估计它的上限 |x-p|ee称为绝对误差限。相对误差定义为绝对误差与精确值之比 Dr=DaxDr=Dahx称为相对误差限 误差的来源： 舍入误差 将无限位字长的精确数处理成有限位字长近似数的处理方法称为舍入方法。带来舍人误差。 有效数字 对于 a=a0 a1 am . am+1 am+n(a00) 的近似数， 若|0.5x10-n， 则称a为具有m+n+1位有效数字的有效数，其中每一位数字都叫做a的有效数字。有效数和可靠数的最末位数字称为可疑数字 有效数位的多

3、少直接影响到近似值的绝对误差与相对误差的大小。 推论1 对于给出的有效数，其绝对误差限不大于其最末数字的半个单位。 x=0.a1a2Lan10m1D=x-x*10m-n2x=0.a1a2Lan10m5Dr(x)10-na1推论2 对于给出的一个有效数，其相对误差限可估计如下： 例:计算y = ln x。若x 20，则取x的几位有效数字可保证y的相对误差 0.1% ? 截断误差 用数值法求解数学模型时，往往用简单代替复杂,或者用有限过程代替无限过程所引起的误差。 l 数值计算的算法问题 “良态”问题和“病态”问题 在适定的情况下，若对于原始数据很小的变化X，对应的参数误差y也很小，则称该数学问题

4、是良态问题；若y很大，则称为病态问题。 病态问题中解对于数据的变化率都很大，因此数据微小变化必将导致参数模型精确解的很大变化。 数学问题的性态完全取决于该数学问题本身的属性，在采用数值方法求解之前就存在，与数值方法无关。 稳定算法和不稳定算法 如果用数值方法计算时,舍入误差对结果影响小的算法称为稳定算法。否则称为不稳定算法。 l 数值计算应注意的问题 第三章 线性方程组求解的数值方法 教学内容： 1. 高斯消元法 消元法的实现过程； 主元问题。 2. 矩阵分解 矩阵LU分解的一般计算公式； 利用LU分解的线性方程组求解方法； Cholesky分解； Matlab的Cholesky分解函数。 3

5、. 向量范数与矩阵范数 向量范数及其性质； 矩阵函数及其性质； 常用范数形式。 4. 线性方程组的迭代法求解 迭代求解的思路； Jacobi迭代法； 高斯_赛德尔迭代法； 松弛法； 迭代法的收敛性。 5. 方程组的病态问题与误差分析 线性方程组解的误差分析； 条件数和方程组的病态性。 消元法： 问题： 消去法是按照系数矩阵的主对角线上的元素进行消元。从而可能出现： 某个主元为零，导致消元过程无法进行。 当某个主元的绝对值很小时，计算结果误差很大。 定理： 若A的所有顺序主子式 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。 全主元消去法 每一步选绝对值最大的元素为主元素。 |aikjk

6、|=max|aij|0;ki,jn列主元消去法 省去换列的步骤，每次仅选一列中最大的元。 |aik,k|=max|aik|0kin矩阵三角分解法 由： 由 Gauss 消去法加上列主元 ( 或全主元）有 LU 分解：A=LU1l211L= l31l321LLln1ln2u11 U= ln(n-1)1uu12222nLLLunnLL1nuua11a21a31a41u11=l21u11l31u11l41u11aaaa2112223242aaaa121213233343aaaa22222214124=l21l3134l414401ll3242001l430u11000010uu122200uuu13

7、23330uuuu141444344444ulu+ulu+lulu+lu311232411242ulu+ulu+lu+ulu+lu+lu132113233113322341134223433333ulu+ulu+lu+ulu+lu+lu+u1421243114322434411442244334得到计算公式： 算法： 对 k=2, 3, L, n 计算k-1m=1k-1u=a , j=1, L,nl=au , i=2, L, n1j1ji1i111 ukj=akj-lkmumj j=k , L , n lik=(aik-limumk )/ukk i=k+1 , L , nm=1(1) 解 Y：

8、 y=b11 yi=bi-lijy , i=2, 3, L, n j=1jni-1(2) 解 x： x=yunnni+1 xi=y-uijxjij=n i=n-1, L, 1 uii , Cholesky分解： 回顾对称正定矩阵的定义和性质。 由对称性推出： 定理： 设矩阵A对称正定，则存在非奇异下三角阵L使得Matlab中的Cholesky分解函数： chol 向量和矩阵的范数 为了研究线性方程组近似解的误差估计和迭代法的收敛性，引进向量的范数的概念。 向量范数 定义： %TA=LLA=LLT 。若限定L对角元为正，则分解唯一。 ,yR Rn空间的向量范数 | | 对任意 x满足下列条件：v

9、vvv(1)|x|0;|x|=0x=0vvn|A|1=max|aij|1jnni=1|A|2=lmax(ATA)谱半径： 矩阵A的谱半径记为 r (A) =maxili，其中li为A的特征根。 定理： 对任意算子范数 | | 有 定理： r(A)|A|若A对称，则有 A2=r(A) 定理： 若矩阵B对某个算子范数满足 |B| 1，则必有 (1)(IB)可逆。(IB)-111-|B|解线性方程组的迭代法 研究内容： l l l l 如何建立迭代公式？ 收敛速度？ 向量序列的收敛条件？ 误差估计？ 思路： 对线性方程组 Ax=b 其中A=(aij)nn非奇异矩阵，b=(b1,L,bn)T 构造其形

10、如 x=Mx+g的同解方程组，其中M为n阶方阵，gRn。任取初始向量x(0)Rn,代入迭代公式 x(k+1)=Mx(k)+g (k=0,1,2,L)产生向量序列x(k)，当k充分大时，以x(k)作为方程组Ax=b的近似解，这就是求解线性方程组的单步定常线性迭代法。 M称为迭代矩阵。收敛问题： 定义：设A(k)为n阶方阵序列，A为n阶方阵，如果 limA(k)-A=0k其中为矩阵范数，则称序列A(k)收敛于矩阵A，记为 limA(k)=Ak(k) 定理：设A(k)=(aij)(k=1,2,L),A=(aij)均为n阶方阵，则矩阵序列A(k)收敛于矩阵A的充要条件为(k) limaij=aij (

11、i,j=1,2,L,n)k 证明略。 定理表明，向量序列和矩阵序列的收敛可以归结为对应分量或对应元素序列的收敛。 若按x(k+1)=Mx(k)+g产生的向量序列x(k)收敛于向量x,则有 x=limx(k+1)=limMx(k)+g=Mx+gkk即x是方程组Ax=b的解。雅可比(Jacobi)迭代法 高斯塞德尔迭代法 迭代法的收敛性 定理：设A为 n阶方阵，则limAk=0的充要条件为r(A)1。k 证：必要性： 若limAk=0 k由矩阵收敛的定义知 limAk=0 又因 r(A)A k 0r(Ak)=r(A)kAk由极限存在的准则，有 limr(A)0 所以r(A)0,由上一定理2知，存在

12、一种矩阵范数，使得 充分性。若r(A)1，取e= Ar(A)+e=kk1+r(A)12kkk而AkA,limAklimA=0limAk=0. 推论2 松弛法收敛的必要条件是0w2。 证：设松弛法的迭代矩阵M有特征值l1,l2,L,ln。因为 det(M)=l1l2Llnr(M)n由定理，松弛法收敛必有 det(M)1又因为 det(M)=(D-wL)-1(1-w)D+wU (D-wL)-11=a11a22Lann (1-w)D+wU=(1-w)na11a22Lanndet(M)=(1-w)n10w2。 迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及右端项无关。对同一方程组，由于不同的迭代

13、法迭代矩阵不同，可能出现有的方法收敛，有的方法发散的情形。 设有线性方程组Ax=b,下列结论成立：1.若A为严格对角占优阵或不可约弱对角占优阵，则Jacobi迭代法和Gauss-Seidel迭代法均收敛。2.若A为严格对角占优阵，0w1,则松弛法收敛。3.若A为对称正定阵，则松弛法收敛的充要条件为0w2。10-1-22-10B=-12-1上两例中： A=-110-2-1-150-12A为严格对角占优阵，故Jacobi与Gauss-Seidel迭代均收敛。B为非严格对角占优阵，但为对称正定阵，w=1.4故松弛法收敛。误差估计： 定理：设有迭代格式x(k+1)=Mx(k)+g,若M1,x收敛于x,

14、则有误差估计式(k)* x(k)-x*Mk1-Mx(1)-x(0) 证：因r(M)M1,故I-M0,于是(I-M)-1存在，方程组x=Mx+g有唯一解x*，且x*=(I-M)-1g。从而有 x(k)-x*=M(x(k-1)-x*)=Mk(x(0)-x*) =Mkx(0)-(I-M)-1g =Mk(I-M)-1(I-M)x(0)-g =Mk(I-M)-1x(0)-x 定理：设有迭代格式x(k+1)=Mx(k)+g,若M1,x收敛于x,则有误差估计式(k)* x(k)-x*M1-M-Mx(k-1)x(k)-x(k-1)证：因 x(k)-x*=M(x(k-1)-x*)=Mx(k-1)-(I-M)-1

15、g=M(I-M)x-1(k-1)-g=M(I-M)(x-1(k-1)-x)(k)x(k)-x*M(I-M)-1x(k-1)-x(k)M1-Mx(k)-x(k-1). 当M不太接近1时，可用x(k)-x(k-1)j结论 通过n+1个节点的n阶插值多项式唯一存在。 一次和二次插值公式： 一次基函数 lk(x)=x-xk+1xk-xk1x-xkxk+1-xklk+1(x)=二次基函数 lk-1(x)=lk(x)=(x-xk)(x-xk+1)(xk-1-xk)(xk-1-xk+1)(x-xk-1)(x-xk+1)(xk-xk-1)(xk-xk+1)(x-xk-1)(x-xk)(xk+1-xk-1)(x

16、k+1-xk)lk+1(x)=拉格朗日插值多项式的一般形式： n+1个基函数l0(x),l1(x),.ln(x),满足：1li(x)是n次多项式。(2)li(xi)=1,且li(xk)=0,(ki)li(x)=插值公式： (x-x0).(x-xi-1)(x-xi+1).(x-xn)(xi-x0).(xi-xi-1)(xi-xi+1).(xi-xn)Pn(x)=y0l0(x)+y1l1(x)+.+ynln(x)=yklk(x)k=0n插值的误差分析： 设函数y=f(x)的n阶导数f(n)(x)在a,b上连续，f(n1)(x)在存在，节点ax0x1.xnb,Pn(x)是n次拉格朗日插值多项式，则对

17、任意的xa,b, 插值余项f(n1)(x)Rn(x)=f(x)-Pn(x)=wn+1(x)(n+1)!思考： 是否插值的节点越多，多项式插值越精确？ 是否多项式的阶数越高，多项式插值越精确？ 演示：多项式插值的Runge现象 分段低次插值 随着插值结点数增加，插值多项式的次数也相应增加，而对于高次插值容易带来剧烈振荡，带来数值不稳定。为了既要增加插值结点，减小插值区间，以便更好的逼近被插值函数，又要不增加插值多项式的次数以减少误差，我们可以采用分段插值的办法。 分段线性插值 Ih(x)=x-xk+1x-xkfk+fk+1xk-xk+1xk+1-xkn(xkxxk+1)若用插值基函数表示，则：I

18、h(x)fjlj(x)j=0xa,b其中：lj(x)满足lj(xk)=djkx-xj-1xj-xj-1x-xj+1lj(x)=xj-xj+10收敛性： xj-1xxjxjxxj+1xxj-1,xj+1f(x)-Ih(x)lk(x)f(x)-fk+lk+1(x)f(x)-fk+1(lk(x)+lk+1(x)w(hk)w(h)其中，w(h)=maxf(x)-f(x)x-xhh0当f(x)Ca,b,则limw(h)=0limIh(x)=f(x)h0因此，只要f(x)Ca,b，埃尔米特插值 求解的思路： H2n+1(x)=a0+a1x+.+a2n+1x2n+1 求插值基函数ai(x),bi(x),(i

19、=0,1,.,n)满足：1ai(x),bi(x)是2n+1次多项式。(2)(3)于是：H2n+1(x)=yiai(x)+mibi(x)i=0nai(xk)=di,k,且ai(xk)=0,(i,k=0,1,.,n)bi(xk)=di,k,且bi(xk)=0,(i,k=0,1,.,n) 利用拉格朗日插值基函数 li(x)=得到 (x-x0).(x-xi-1)(x-xi+1).(x-xn)(xi-x0).(xi-xi-1)(xi-xi+1).(xi-xn)n1ai(x)=1-2(x-xi)k=0xi-xkkil2(x) i同理，由bi(x)在xk(ik)处函数族和导数值均为0，且bi(xi)=0,故

20、bi(x)c(x-xi)li2(x)由于bi(xi)=1,有bi(xi)=cli2(xi)=1bi(x)(x-xi)li2(x)H2n+1(x)=yiai(x)+mibi(x)i=0nHermite插值的唯一性： Hermite插值的余项 函数y=f(x)的2n2阶导数f(2n2)(x)在存在，对任意的xa,b,Hermite插值余项f(2n2)(x)2R(x)=f(x)-H2n+1(x)=wn+1(x)(2n+2)!分段Hermite插值： 三次样条插值 第五章 数值积分 1. 插值型求积公式 线性和二次求积公式； 求积公式的代数精度； 求积公式的误差分析； 复合求积公式； 高斯求积公式；

21、MATLAB中的数值积分函数。 2. 积分方程的数值求解 积分方程的数值求解的思路分析； 积分方程的数值求解方法介绍。 n次代数精度nbaf(x)dxAkf(xk) k=0对于任意不超过n次的代数多项式都准确成立, 而对某一个m+1次代数多项式不成立,。 梯形公式 a辛普森公式 bf(x)dxb-a2f(a)+f(b) 3(b-a)截断误差： R1f=f(h)12(ahb) S=复化求积公式： 复化梯形公式 b-aa+bf(a)+4f+f(b)62： n-1h=f(a)+f(b)+2f(a+kh)Tn2 k=1截断误差： RN(f)b-a2hM2， Mmaxf(x) axb122复化辛普森公式

22、 n-1n-1hSn=f(a)+4f(xk+1/2)+2f(xk)+f(b) 6k=0k=0截断误差： RNf 高斯求积公式 定义 b-a2880h4M4，M4=maxf(4)(x) axb求积公式 f(x)dxAkf(xk) 含有2n+2个ak=0bn待定参数xk,Ak(k=0,1,L,n),适当选择这些参 数使其具有2n+1次代数精度。这类求积公式称为高斯公式。xk(k=0,1,L,n)是高斯点。高斯求积公式 nba, f(x)dxAkf(xk) k=01dn(x2-1)n 节点为 Pn(x)=n2n!dxn的零点(高斯点) f(2n+2)(x)b2 其余项：Rn(x)=wn+1(x)dx

23、 (2n+2)!aMatlab 积分函数 函数名 quad quad8 功能 采用Simpson计算积分。精度高，较常用 采用8样条Newton-Cotes公式计算积分。精度高，最常用 trapz 采用梯形法计算积分。精度差，速度快 积分方程的数值求解 Fredholm积分方程：by(t)=lk(t,s)y(s)ds+f(t)a求解思路 用数值积分代替积分 bn由k(x,s)y(s)ds=Ak(x,x)y(x) kkkak=1y(x)=lAkk(x,xk)y(xk)+f(x) k=1ny(xk)=lAkk(xk,xk)y(xk)+f(xk) k=1nrr(I-lK)y=f 第六章 常微分方程初

24、值问题 1. 欧拉方法 基本理论和方程离散化； 欧拉方法 2. 教学要点： 欧拉公式： 稳定性与收敛性分析 y(xk+1)yk+1=yk+hf(xk,yk)(k=0,1,2,.,n-1) x=x+kh0k2局部截断误差是O(h). 改进欧拉公式： 预报值 校正值或表示成： yk+1=yk+hf(xk,yk)yk+1 h=yk+f(xk,yk)+f(xk+1,yk+1)2hhyk+1=yk+f(xk,yk)+f(xk+1,yk+f(xk,yk) 22 平均形式： yp=yk+hf(xk,yk) yc=yk+hf(xk+1,yp) yk+1=1(yp+yc)2 局部截断误差是O(h). 龙格库塔方法 3一般地，RK方法设近似公式为pyn+1=yn+hciKii=1K1=f(xn,yn)i-1Ki=f(xn+aih,yn+hbijKj)(i=2,3L,p)j=1其中ai，bij,ci都是参数，确定它们的原则是使近似公式在(xn,yn)处的Taylor展开式与y(x)在xn处的Taylor展开式的前面项尽可能多地重合。