数值分析总结范数迭代逼近数值微积分

数值分析总结_范数、迭代、逼近、数值微积分数值分析总结_范数、迭代、逼近、数值微积分数值分析总结_范数、迭代、逼近、数值微积分

考试题型一、填空题其目的是考核同学们对数值分析中基本概念、基本定理的理解；主要考核内容为基本概念、基本定理、定理或算法应用条件等内容例如：误差配置原则中的内容；收敛条件等二、计算题需要掌握算法的内容、应用条件、误差分析等内容。计算过程可以使用计算器，但是要求同学要具备计算熟练性2023/1/122第一章数值计算中的误差1误差(1)绝对误差(限)、相对误差(限)(2)有效数字2算术运算中的误差加法(减法)、乘法3误差的来源及分类(舍入误差和截断误差)4误差分配原则与处理方法2023/1/1231.1绝对误差及相对误差绝对误差设A是精确值，a是近似值，则定义两者之差=a-A为近似数a的绝对误差绝对误差限||=|a-A|<(上界)，称为绝对误差限相对误差绝对误差及精确值之比A=

/A为相对误差相对误差限|A|=|/A|<η(上界)，称为相对误差限绝对误差和相对误差有关系：=aA2023/1/1241.2有效数字舍入方法将无限位字长的精确数处理成有限位字长近似数的处理方法称为舍入方法截断法四舍五入法四舍五入法的|Δ|≤0.5x10-n，在a的最末一位上有半个单位误差实际应用中按四舍五入的原则取近似值是使用最广的取近似值的方法。用四舍五入获得的近似值，可用有效数字来刻画2023/1/1251.2有效数字如果近似数a的绝对误差是某一位的半个单位，且该位直到a的第一位非零数字一共有n位，则称近似数a有n位有效数字，a为具有n位有效数字的有效数。x*=

…

…最左边不为零的数误差不超过该位数的半个单位n个有效数字例如：表示：近似值0.003400准确到小数点后第5位，有3位有效数字。绝对误差限、相对误差限和有效数字的关系2023/1/1262.算术运算中的误差要求明确数据误差在算术运算中的传播规律并对结果误差进行估计估计方法设x为x*的近似值，y为y*的近似值，则Δx=x-x*,Δy=y-y*。实际中常取误差的主部,采用微分方式表达，即dx≈Δx,dy≈Δy，对于算术运算中的结果误差可按微分公式近似估算2023/1/1272.算术运算中的误差加减的绝对误差限等于各数的绝对误差限之和C=xy dC|dxdy|

|dx|+|dy|

x+y,乘积运算的相对误差为各乘数的相对误差之和，其相对误差限等于各乘数相对误差限之和2023/1/128模型误差观测误差截断误差求解数学模型所用的数值计算方法如果是一种近似的方法，那么得到的是数学模型的近似解，由此产生的误差称为截断误差。舍入误差由于计算机的字长有限，参加运算的数据以及运算结果在计算机上存放会产生误差。这种误差称舍入误差或者计算误差。3误差的来源及分类2023/1/1294误差的分配原则及处理方法误差配置原则计算模型的近似解相对于参数模型精确解的总误差=截断误差+舍入误差,即=R+R误差的处理方法1.给定运算误差，确定参及运算的数值字长2.近似式的项数已定而字长待定3.总误差给定，要求确定项数和数值字长.4.数值字长已定，待定近似式项数=R+R2023/1/1210第二章方程(组)的迭代解法1.根的初值确定方法2.迭代解法(1)迭代法的计算步骤(2)迭代解法的几何意义(3)迭代法的收敛性（φ’(x)|q<1）3.迭代公式的改进（减小q的值）：(1)埃特肯法(2)牛顿迭代法(3)牛顿下山法(4)弦截法2023/1/12111.根的初值确定方法迭代法求解非线性方程或非线性方程组较为有效的方法，它是递归的应用某一计算公式来决定未知量，并使之逐步逼近真解的一种方法求方程根的问题，就几何上讲,是求曲线y=f(x)及x轴交点的横坐标。定理2.1设f(x)为区间[a,b]上的单值连续函数，如果f(a)·f(b)<0，则[a,b]中至少有一个实根。如果f(x)在[a,b]上还是单调地递增或递减，则仅有一个实根确定根所在区间的方法：(1)画图法：f(x)=0分解为1(x)=2(x)的形式，1(x)与2(x)两曲线交点的横坐标所在的子区间为含根区间(2)扫描法(3)对分法2023/1/12122.迭代解法迭代法的计算步骤归纳如下：(1)选取初值x0，(画图法、扫描法、对分法)(2)确定方程f(x)=0的等价形式x=φ(x),判断收敛性|φ’(x)|q

<1

(3)按公式xn+1=φ(xn)计算xn+1的值(4)迭代终止判断.如果|xn+1-xn|<则停止计算，否则继续迭代收敛条件定理2.2：|φ’(x)|q

<1是迭代序列收敛的充分条件在实际应用时，可用|φ’(x0)|q

<1收敛速度|φ’(x)|误差估计及迭代过程终止的条件2023/1/12133.迭代公式的改进(1)埃特肯法2023/1/1214(2)牛顿迭代法(3)判断如果|xn+1-xn|<，则迭代终止，否则n增加1，转(2)牛顿迭代法计算步骤：(1)选取初值x0(2)对于n=0,1,2,3…计算f(xn)和f’(xn)，以及2023/1/1215(3)牛顿下山法引进参数λ，并用尝试法修改λ值大小(即改变原切线的斜率)，使达到|f(x0)|>|f(x1)|>…单调下降的目的。称|f(xn+1)|<|f(xn)|为下山条件,这种算法为下山法.2023/1/1216(3)牛顿下山法牛顿下山法取λ=1在xn基础上用切线法计算xn+1是否满足精度要求是是停止迭代检查下山条件是否满足否修改λ值,算出新的近似值xn+1否λ为下山因子在[1,1]内选值.可依次取1,1/2,1/4,1/2r>12023/1/1217(4)弦截法双点弦截法yx0xn-1xnxn+12023/1/1218第二章方程求根的迭代解法收敛的充分条件定理2.5设f(x)在[a,b]上二阶导数存在，且满足：1)f(a)f(b)<02)f’(x)≠0,

3)f’’(x)不变号4)初值x0满足f(x0)

f’’(x0)>0则牛顿迭代法收敛。定理2.6设f(x)在[a,b]上二阶导数存在,且满足(1)f(a)f(b)<0(2)f’(x)≠0(3)f’’(x)不变号(4)不动点x0满足f(x0)f’’(x0)>0,x1及x0的函数值相异 则单点弦截法收敛定理2.7当f(x)在区间[a,b]上有直至二阶的连续导数，且满足f(a)f(b)<0且f’(x)≠0时,双点弦截法对任意x0,x1∈[a,b]都收敛。2023/1/1219习题二2.求方程x3-x2-1=0在x0=1.5附近的根，设建立下列相应的迭代公式，分析收敛性，并求近似根解：(x)|‘(x)|=|-2x31|=-21.531|x0=1.5=0.59<1(收敛)|‘(x)|=|312x|==0.4557<1(收敛)|‘(x)|=|21=1.4142>1(不确定收敛)2023/1/1220习题二3.用埃特肯法求方程x3-x2-1=0在1.5附近的根,=10-4x0=1.5=1.48125=1.47271x1==1.46557=1.46557=1.46557x=1.46562023/1/1221习题二x0=1.5=1.44444=1.479585x1==1.46597=1.46532=1.465732023/1/1222习题二x2==1.46557=1.465572023/1/1223习题二5.分别用迭代法、牛顿法、双点弦截法（x0=2,x1=1.9）求方程x3-3x-1=0在x=2附近的根解：（1）迭代法因为x3=

3x+1|‘(x)|=|313|==0.27<1x0=2=1.91293=1.88883=1.88203x4=1.88014x5=1.87960x6=1.87945x7=1.87940x8=1.87939x9=1.879392023/1/1224习题二（2）牛顿法f(x0)=23-3*2-1=1f’’(x0)=(f’(x0))’=(3(x2-1))’=6x=6*2=12ff’’|x0=2>0取初值x0=2=1.88889x2=1.87945x3=1.87938x4=1.87938第一步：形成迭代函数第二步：确定初值第三步：迭代计算2023/1/1225习题二（3）双点弦截法x0=2,x1=1.9x0=2f(x0)=23-3*2-1=1x1=1.9f(x1)=1.93-3*1.9-1=0.159=2*0.159-1.9*10.159-1=1.8811f(x2)=0.0130x3=1.9*0.0130-1.8811*0.1590.0130-0.159=1.8794f(x3)=0.0001x4=1.8811*0.0001-1.8794*0.01300.0001-0.0130=1.87942023/1/1226第三章解线性方程组的直接法§1消元法1.1消元法的描述1.2高斯消元法1.3克劳特消元法1.4平方根法1.5追赶法1.6消元法的应用条件§2选主元的高斯消元法2.1列主元素法2.2全主元素法2023/1/12271消元法u11x1+u12x2+…+u1nxn=z1

u22x2+…+u2nxn=z2…….(2)unnxn=zn消元x1=…x2=………xn=…回代思路:通过组合方程的方法实现逐步消元,达到将原方程组化为三角形方程组的目的,然后用回代法解此三角形方程组即可获得原方程组的解.2023/1/1228消元法综述2023/1/1229消元法计算公式2023/1/1230常用消元法lii选值的不同会影响到计算量及舍入误差的大小高斯消元法：取lii=1克劳特消元法l11=a11(0)=a11,

l22=a22(1),l33=a33(2),…,lnn=ann(n-1)uii=1平方根法取lii=uii,有lij=uji2023/1/12313.消元法的应用条件2023/1/12323.消元法的应用条件定理3.1:若A的各阶主子式均不为0，即|A1|

=|a11|0,定理3.2若A为实对称正定矩阵，则lii0,uii0(i=1,2,…,n)定理3.3若A为严格对角占优矩阵，则lii0,uii0(i=1,2,…,n)2023/1/1233主元素法原因lij=分子/ujj，uij=分子/lii，zi=分子/lii，xi=分子/uii公式likukj，分母为零提出主元素法是为控制舍入误差交换原则：使在对角线位置上获得绝对值尽可能大的系数作为uij，称这样的uij为主元素，并称使用主元素的消元法为主元素法根据主元素选取范围分为：列主元素法、全主元素法2023/1/1234习题三1.用高斯消元法解解：lii=1

u11=3u12=2u13=5z1=6l21=-13l31=13=-0.33333=0.33333u22=4-(-0.33333)*21=4.66667l32=-1-(-0.33333)*24.66667=-0.35714u23=3-(-0.33333)*51=4.66665u33=3-0.33333*5-(-0.35714)*4.66665=3.00000z2=5-(-0.33333)*6=6.99998z3=1-0.33333*6-(-0.35714)*6.99998=1.499993x1+2x2+5x3=64.66667x2+4.66665x3=6.999983.00000x3=1.49999x3=0.50000x2=1.00000x1=0.500002023/1/1235习题三2.用克劳特消元法解2023/1/1236习题三x1－0.33333x2+1.33333x3=2.33333

x2–0.40000x3=0.80000

x3=0.50000x1=2.33333+0.33333*1-1.33333*0.5＝2x2=0.8+0.4*0.5＝1x3=0.52023/1/1237习题三4.用列主元素法解l21=-13=-0.33333l31=23=0.66667(2)-l21(1):[2-(-1)*(-0.33333)]x2+(-2)-4*(-0.33333)x3=2-3*(-0.33333)1.66667x2-0.66668x3=2.99999(4)(3)-l31(1):-2.33333x2-4.66668x3=-7.00001(5)(4)>(5):-2.33333x2-4.66668x3=-7.00001(6)1.66667x2-0.66668x3=2.99999(7)l32=1.66667-2.33333=-0.71429(7)-l32(6):-4.00004x3=-2.00005(8)2023/1/1238习题三-4.00004x3=-2.00005(8)-2.33333x2-4.66668x3=-7.00001(5)3x1-x2+4x3=3(1)x3=0.50001x2=1.99998x1=0.999982023/1/1239第四章解线性方程组的迭代法1.范数定义2.雅克比迭代法3.高斯-赛德尔迭代法4.有关收敛的判别5.松弛迭代法2023/1/12401向量范数,矩阵范数,谱半径1-范数2-范数-范数行范数列范数2-范数向量范数是用来度量向量长度的,它可以看成是二、三维解析几何中向量长度概念的推广2023/1/1241简单迭代法雅克比迭代法(k+1)(k+1)(k+1)(k)(k)(k)(k)(k)(k)(k)(k)(k)迭代矩阵2023/1/1242§2简单迭代法高斯-赛德尔迭代法(k+1)(k+1)(k+1)(k)(k)(k)(k+1)(k)(k)(k+1)(k+1)(k+1)2023/1/12434.有关收敛的判别——迭代矩阵定理4.6对任何初始向量X(0)和常数项N，由迭代公式 X(k+1)=MX(k)+N(k=0,1,2,…) 产生的向量序列{X(k)}收敛的必要充分条件是说明：迭代的收敛性只及迭代矩阵的谱半径有关迭代是否收敛与系数矩阵A及演变方式有关与常数项和初始向量的选择无关。2023/1/12444.有关收敛的判别——迭代矩阵简单迭代法、赛德尔迭代法收敛的三个充分条件||M||=max{i}<1||M||1=max{vi}<12023/1/12454.有关收敛的判别——系数矩阵定理4.9若系数矩阵A不可约且具有对角占优，则雅可比迭代法必定收敛定理4.10若系数矩阵A不可约且具有对角占优，则高斯-赛德尔迭代法必定收敛定理4.11若A对称正定，则高斯-赛德尔迭代法收敛有些线性方程组使用Jacobi迭代法收敛，有些线性方程组使用Gauss-Seidel法收敛；即使使用两种方法都收敛，收敛速度未必相同2023/1/12464.有关收敛的判别定义若矩阵A的对角线元素满足

且至少有一个i值，使上式中有严格不等号成立，则称A具有对角占优。2023/1/1247习题四1.用简单迭代法、赛德尔迭代法解线性方程组解:(1)x1=1.2-0.1x2-0.15x3x2=1.5-0.125(x1+x3)x3=2-0.13333x1+0.2x2x1(k+1)

=1.2-0.1x2(k)

-0.15x3(k)

x2(k+1)

=1.5-0.125(x1(k)

+x3

(k)

)x3(k+1)

=2-0.13333x1(k)

+0.2x2(k)

2023/1/1248习题四x1=0.768,x2=1.139,x3=2.1252023/1/1249习题四解:(2)2023/1/1250习题四6.设线性方程组AX=B的系数矩阵如下，证明雅可比迭代法收敛，高斯赛德尔迭代法发散解:(1)用雅可比迭代法的迭代矩阵是2023/1/1251习题四其特征方程是0=1=2=0，(G)=0,用雅可比迭代法收敛2023/1/1252习题四(2)<方法一>求高斯赛德尔迭代法的迭代矩阵G=-(D+L)-1U(G)=2,用高斯赛德尔迭代法不收敛2023/1/1253习题四(2)<方法二>求高斯赛德尔迭代法的迭代矩阵的特征向量0=0，1=2=2，(G)=2,用高斯赛德尔迭代法不收敛2023/1/12545.松弛法松弛的含义ri=bi-(ai1x1+ai2x2+…+ainxn)(i=1,2,…,n)按|ri|最大实施松弛方法按方程次序实施松弛的方法——逐次松弛法带有松弛因子的逐次松弛法2023/1/12554.1.3带有松弛因子的逐次松弛法例4.5用逐次松弛法解线性方程组解：按照如下形式，建立迭代格式2023/1/12564.1.3带有松弛因子的逐次松弛法当=1时，2023/1/12574.1.3带有松弛因子的逐次松弛法当=1.25时，2023/1/1258第五章插值法不等距条件下的牛顿基本差商公式1.差商2.牛顿基本差商公式3.截断误差估计等距节点下的牛顿基本差商公式1.差分定义2.差分和差商的关系3.牛顿前向插值公式4.牛顿后向插值公式5.中心差分公式2023/1/1259第五章插值法不等距节点下的拉格朗日插值公式1.不等距节点下的拉格朗日插值公式2.拉格朗日公式的舍入误差插值公式的唯一性及其应用反插值 1.使用反函数的插值法 2.利用插值多项式的反插值法埃尔米特插值多项式2023/1/1260第五章插值法1.差商(1)差商定义(2)差商的重要特性——对称性(3)差商表一般的，可定义区间[xi,xi+1,…,xi+n]上的n阶差商为2023/1/1261§1.1差商差商表xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]f[xi,xi+1,xi+2]x0f(x0)f[x0,x1]x1f(x1)f[x0,x1,x2]f[x1,x2]f[x0,x1,x2,x3]x2f(x2)f[x1,x2,x3]f[x2,x3]x3f(x3)………f[x1,x2]-f[x0,x1]x2–x02023/1/12622牛顿基本差商公式Pn(x):牛顿基本差商公式Rn(x)余式xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]f[xi,xi+1,xi+2]x0f(x0)f[x0,x1]x1f(x1)f[x0,x1,x2]f[x1,x2]f[x0,x1,x2,x3]x2f(x2)f[x1,x2,x3]f[x2,x3]x3f(x3)2023/1/1263§1.3牛顿基本差商公式误差估计(2)牛顿基本差商公式误差估计([x0,x1,…,xn])(1)差商及导数的关系2023/1/1264§1.3.2余式的估计例5.3求解：作函数f(x)=取x0=4,x1=9,x2=6.25,建立差商表xf(x)f[xi,xi+1,]f[xi,xi+1,xi+2]42936.252.5P2(7)=2+(7-4)*0.2+(7-4)*(7-9)*(-0.00808)=2.648482023/1/1265§1.3.2余式的估计f3(x)=Rn(x)在区间[4,9]上，余式近似0.5*10-2,P2(7)=2.64848可舍入为2.652023/1/12664.差分(1)差分定义称kyi-1=k-1yi-k-1yi-1为函数f(x)

在[xi-1,xi+k-1]上的k阶差分。(2)差分表(3)等距节点情况下用差分表示差商nyin!hnnPn(x)=常量2023/1/1267§2.1差分xyy2y3y4yx0y0x1y1x2y2x3y3x4y4y0=y1–y0y1=y2–y1y2=y3–y2y3=y4–y32y0=y1-y02y1=y2-y12y2=y3-y23y0=2y1-2y03y1=2y2-2y14y02023/1/1268§2.2牛顿前插公式xyy2y3y4yx0y0y0x1y12y0y13y0x2y22y14y0y23y1x3y32y2y3x4y42023/1/1269在节点等距情况下，以xnxn-1…x0顺序建立牛顿基本差商公式§2.3牛顿后插公式xyy2y3y4yx0y0y0x1y12y0y13y0x2y22y14y0y23y1x3y32y2y3x4y42023/1/1270习题五5已知函数表，求y(0.05)y(0.42)y(0.75)的近似值xyy2y3y4y0.01.000000.21.221400.41.491820.61.822120.82.225540.221400.270420.330300.403420.049020.059880.073120.010860.013240.00238(1)牛顿前插公式求y(0.05)x=0.05,h=0.2=0.25ny0n!Pn(x)=y0+ty01!+

t(t-1)2y02!+…+t(t-1)…(t-n-1)y(0.05)1.00000+0.25*0.22140+0.25*(0.25-1)*0.04902/2+0.25*(0.25-1)(0.25-2)3!*0.010862023/1/1271习题五=1.05126+0.25*(0.25-1)(0.25-2)(0.25-3)4!*0.00238(2)斯梯林插值公式求y(0.42)x=0.42,h=0.2xyy2y3y4y0.01.000000.21.221400.41.491820.61.822120.82.225540.221400.270420.330300.403420.049020.059880.073120.010860.013240.00238=0.1y(0.42)1.49182+0.11*0.27042+0.330302+0.122*0.05988+0.1*(0.12-1)3!*0.01086+0.013242+0.12*(0.12-1)4!*0.00238=1.521962023/1/1272习题五(3)牛顿后插公式求y(0.75)xyy2y3y4y0.01.000000.21.221400.41.491820.61.822120.82.225540.221400.270420.330300.403420.049020.059880.073120.010860.013240.00238x=0.75,h=0.2=0.75-0.80.2=-0.25y(0.75)2.22554+(-0.25)*0.40342+(-0.25)*(-0.25+1)*0.07312/2+(-0.25)*(-0.25+1)*(-0.25+2)3!*0.01324=2.11702+(-0.25)*(-0.25+1)*(-0.25+2)*(-0.25+3)4!*0.002382023/1/1273§3拉格朗日插值公式f(x)=(x0–x1)(x0–x2)…(x0–xn)(x–x1)(x–x2)…(x–xn)f(x0)+…+(xi–x0)…(xi–xi-1)(xi–xi+1)…(xi–xn)(x–x0)…(x–xi-1)(x–xi+1)…(x–xn)f(xi)+…+(xn–x0)(xn–x1)…(xn–xn-1)(x–x0)(x–x1)…(x–xn-1)f(xn)+Rn(x)=Ln(x)+Rn(x)拉格朗日插值公式ai(x)2023/1/1274§3.2舍入误差估计[yiai(x)+aiyi+aiyi]2023/1/1275例5.8估计用插值法计算lg47时的误差限取x0=45,x1=48,=1.671898401解：应用n=1的拉格朗日插值公式x4548lgx1.65321261.68124132023/1/1276([45,48])2023/1/1277=(0.3333333+1.6532126)*0.5*10-7+(0.6666667+1.6812413)*0.5*10-70.2*10-3对于y=1.671898401可取y=1.672=1.6718984012023/1/1278§5插值公式的唯一性及其应用插值公式的唯一性若插值节点相同，则插值公式是唯一的插值计算中的误差(1)插值公式截断误差的估计(2)插值计算中的舍入误差(拉格朗日插值公式)2023/1/1279§6反插值1.使用反函数的插值法xx0x1…xnyy0y1…ynyy0y1…ynxx0x1…xn2.利用正函数插值公式的反插值法从正插值函数中推出迭代公式2023/1/1280§6.1使用反函数的插值法例5.10给出sinx的函数表，对y=0.98000000利用y=sinx的反函数进行反插值x1.741.761.781.801.82sinx0.985719180.982154320.978196610.97847630.96910913=1.771138202023/1/1281§7埃尔米特插值多项式牛顿型埃米特插值公式降阶型埃米特插值公式拉格朗日型埃米特插值2023/1/12827.1牛顿型埃米特插值公式根据差商和导数的关系：n+1个x0

2023/1/12837.1牛顿型埃米特插值公式将每一节点的个数增加到导数+1个后，问题可归结为在m+1个互异节点组上的插值问题：2023/1/12847.1牛顿型埃米特插值公式xyy’y’’0341567xy一阶差商二阶差商三阶差商四阶差商03

03

15-6.515

15-23.56-0.54n+1个x0

2023/1/1285第六章数值微分和数值积分§1数值积分1牛顿－科特斯求积公式2复化求积公式3龙贝格法4高斯求积§2数值微分的基本方法1差商型数值微分2插值型数值微分2023/1/1286§2.1牛顿——柯特斯求积公式f(x)Pn(x)Ci(n):牛顿—柯特斯系数牛顿－柯特斯求积公式柯特斯系数具有对称性2023/1/1287§2.1牛顿——柯特斯求积公式当n=1时,C0(1)=C1(1),称为梯形公式：具有1次代数精确度当n=2时,N-C公式称为辛普生公式(Simpson):3次代数精确度2023/1/1288§2.1牛顿——柯特斯求积公式例6.3用n=6牛顿—柯特斯公式计算下列定积分值解：h=(b-a)/n=(1-0)/6=1/6xi=0+i/6=0.69332023/1/1289§2.2复化求积公式1.复化梯形公式hh=(b-a)/Mab(m=M/n)个等分区间2023/1/1290§2.2复化求积公式2.复化辛卜生公式M个小段abn小段M=2mm个等分区间2023/1/1291§1.3复化求积公式例6.2对定积分分别用复化梯形公式或复化辛卜生公式计算时，需要M=?解：f’’(x)<1/3,f(4)(x)<1/5复化梯形公式=167复化辛卜生公式M=2m=62023/1/1292§1.3复化求积公式例6.3利用复化辛卜生公式计算积分解：取M=2m=10,则h=(b-a)/M=(1-0)/10=0.1=0.03333*20.7945=0.69315估计截断误差2023/1/12933龙贝格法当区间[a,b]分为2k等分，步长h=(b-a)/2k,复化梯形递推公式为复化梯形递推公式构成的序列T1T2T4…辛卜生序列S1S2S4…柯特斯序列C1C2C4…龙贝格序列R1R2R4…龙贝格求积法2023/1/12943龙贝格法T1T2S1T4S