复习-数值计算方法

数值计算方法复习第一章误差要求掌握：误差的基本概念和性质，绝对误差及绝对误差限、相对误差和相对误差限和有效数字之间的关系。了解误差的来源及传播，并会由此分析算法的收敛性及数值稳定性，理解在算法设计中应注意的事项。第一章误差绝对误差和绝对误差限*)(xxxe*()exxx*()rxxexx**xxx**()rrxxexx相对误差和相对误差限概念一：绝对误差、相对误差和有效数字nxx1021*则说x*近似表示x准确到小数后第n位，并从这第n位起直到左边的第一个非零数字之间的一切数字都称为有效数字，并把有效数字的位数称为有效位数。0000926.01415.3有效数位为4位若准确值x经过四舍五入得到近似数a，则自左向右的第一个非零数字到四舍五入得到的最末一个数字称为近似数a的有效数字。概念一：绝对误差、相对误差和有效数字nxx1021*则说x*近似表示x准确到小数后第n位，并从这第n位起直到左边的第一个非零数字之间的一切数字都称为有效数字，并把有效数字的位数称为有效位数。0000926.01415.3有效数位为4位一般的，如果近似值x*的规格化形式为x*=±0.a1a2…an…×10mnmxx1021*例x*=1452.046是具有7位有效数字的近似值，则它的误差限为3*1021xx概念一：绝对误差、相对误差和有效数字X*具有n位有效数字概念二：误差的传播和累积),...,(**)(**1nxxdfyyye)(),...,(*1**1iiniinxxxxxf)(),...,(*1**1iniinxexxxf)(ln**)(*)(fdyyeyer),...,()(),...,(**1*1**1niiniinxxfxxxxxf),...,()(),...,(**1*1**1niniinxxfxexxxf)(),...,(),...,(***1*1**1irniniinxexxfxxxxf和、差、积、商的误差限为)()()()()(*2*****12121xexexexexxe)()()()()(******212121xexexexexxerrrrr)()()()()(******212121xexexexexxerrrrr例设y=xn，求y的相对误差与x的相对误差之间的关系例假定运算中数据都精确到两位小数，试求x*=1.21×3.65-9.81的绝对误差限和相对误差限，计算结果有几位有效数字习题1：为了保证计算球体体积时的相对误差不超过1%，问测量半径R时允许的相对误差限是多少？34()3VfRR解：球体的体积计算公式为'()()(())()()rrfReVefReRfR23'()4()()()*()4/3rrfRReVeReRRfRR()3()0.01rreVeR()0.01/3reR数值计算中应该注意的一些原则1．要使用数值稳定的算法2．要避免两个相似数相减例：求（n=0,1,2,…,8）的值。10dx5xxInnxxy1的值。当x=1000，y的准确值为0.01580例:求3.绝对值太小的数不宜作除数掌握确定方程有根区间的方法，能正确使用逐步搜索法或二分法求方程具有足够精度的近似解。掌握迭代法求方程根的基本思想、几何意义及相关理论和概念，会构造方程求根的迭代格式，并进行迭代格式的收敛性判断和收敛阶的确定。本章重点是Newton迭代法，要求熟练掌握Newton法求根公式的几何解释、局部收敛性和收敛阶。了解弦截法求根过程。第二章非线性方程的数值求解一、简单迭代法(基本迭代法)--------(2)将非线性方程(1)化为一个同解方程)(xx为连续函数并且假设)(x得的右端代入任取一个初值,)2(,0x)(01xx)(12xx)(1kkxx继续--------(3)),2,1,0(k称(3)式为求解非线性方程(2)的简单迭代法xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1定理2.且满足上连续在设迭代函数,],[)(bax;)(,],[)1(bxabax时当有且满足存在一正数],,[,10,)2(baxLLLx|)(|*],[)(.1xbaxxo内有唯一解在方程则*)(],,[.210xxxbaxkko均收敛于迭代法对于任意初值11*.3kkkoxxLLxx011*.4xxLLxxkko--------(5)--------(6)--------(7)定理3：如果函数ψ(x)在x*的一邻域O(x*,δ*)内可导连续，x*为方程x=ψ(x)的根，且|ψ’(x*)|1，则存在正数δ，(δδ*)，使得对任意，迭代序列xn+1=ψ(xn)(n=0,1,2…)收敛于x*。**0,xxx迭代过程的收敛速度设由某方法确定的序列{xk}收敛于方程的根x*，如果存在正实数p，使得Cxxxxpkkk*1*lim（C为非零常数）定义：则称序列{xk}收敛于x*的收敛速度是p阶的，或称该方法具有p阶敛速。当p=1时，称该方法为线性（一次）收敛；当p=2时，称方法为平方（二次）收敛；当1p2时，称方法为超线性收敛。如何判断迭代函数的收敛速度呢？设迭代函数ψ(x)在x*的邻域有r阶连续导数(r≥2)，且x*=ψ(x*)，ψ(k)(x*)=0(k=1,…,r-1),ψ(r)(x*)≠0，则迭代公式所产生的序列{xn}是r阶收敛的。若0|ψ’(x*)|1，则迭代序列是线性收敛的。定理4：4.5Newton迭代法（Newton-Raphson）如果将非线性方程0)(xf)()(xfxkxx0)(xk且令)()()(xfxkxx)()()()(1)(xfxkxfxkx,0)(*的根为设xfx则收敛速度越快附近越小在,*|)(|xx化为等价方程如果0*)(xf*)(*)(*)(*)(1xfxkxfxk00*)(x令*)(1*)(xfxk即则于是取)(1)(xfxk)()()(xfxfxx--------(10)--------(11)式构造迭代法由取初值)11(,0x)()(1kkkkxfxfxx),2,1,0(k--------(12)(12)式称为Newton迭代法,0*)(xf只要Newton迭代法至少平方收敛局部收敛性注：Newton法的收敛性依赖于x0的选取。x*x0x0x0牛顿法收敛性示意图•与二分法不同，牛顿法一般不在x轴的有限范围内求根，因此其二次收敛是有限制的，在最坏的情况下会出现迭代发散现象，一般用于求解良性函数。牛顿法的收敛性牛顿法收敛性示意图)()(1kkkkxfxfxxNewton迭代法需要求每个迭代点处的导数)(kxf复杂！得中的近似替代用,)(0kkxxfx)()(01xfxfxxkkk--------(12)--------(13)这种格式称为简化Newton迭代法精度稍低)(kxf如果用数值导数代替11)()()(kkkkkxxxfxfxfNewton迭代法的变形则Newton迭代法变为)()()()(111kkkkkkkxxxfxfxfxx--------(14)这种格式称为弦截法收敛阶约为1.6181kx11)()(,kkkkABxxxfxfKAB的斜率为如图11)()(tankkkkxxxfxf*x)(xfy1kxkxAB)()()()(111kkkkkkkxxxfxfxfxx)(cotkkxfx)(cotkxf几何意义习题1：能不能用迭代法求解下列方程？如果不能，试将方程改写成能用迭代法求解的形式(1)(cossin)/4;xxx解题思路：判断方程x=Φ(x)能否用迭代法求根，最关键的是：Φ(x)在根的邻域能否满足(2)42xx'()1xL习题2：证明已知x*是f(x)=0的m重根，则可用下面迭代法1()()kkkkfxxxmfx如果未知x*是f(x)=0的几重根，则可用下面迭代法'12''()()[()]()()kkkkkkkfxfxxxfxfxfx得到至少二阶收敛的解序列。1*lim0*kkkxxxx解题思路：要证明迭代序列至少二阶收敛及证明习题3：试确定常数p，q，r，使迭代公式2251//kkkxpxqaxrax解：要是的上述迭代格式具有尽可能高的收敛阶次，迭代函数应满足：产生的序列收敛到，并使其收敛阶尽可能高。kx3a****(),'()0,''()0xxxx由此三式可确定p,q,r应该满足的方程组。解得22515/95/9/1/9/kkkxxaxax习题4：设φ（x）是一个连续可微函数，若迭代格式(1)()()kkxx解：要使得上述迭代格式具有尽可能高的收敛阶次，新的迭代函数应满足更高阶的导数值为0。是局部线性收敛的，对于，构造新的迭代格式R(1)()()1()11kkkxxx问：如何选取λ使得新的迭代格式有更高的收敛阶。第三章线形方程组理解高斯消去法的基本原理及实现条件，理解按列选主元策略的原因，掌握消去法的计算过程，熟练使用高斯消去法解线性方程组。理解高斯消去法对应的矩阵操作。熟练掌握矩阵的三角分解法，LU分解法。能够利用其求解线性方程组。掌握向量和矩阵泛数的定义及其性质，会计算常用的3种泛数。了解矩阵条件数的定义，明确条件数与方程组性态的关系，能够进行初步的扰动分析。列主元消元法在Gauss消元第k步之前，做如下的事情：||||max)()(kjkkiknikaa若交换k行和j行例：211111091,112xx11021111102119行的交换，不改变方程组的解，同时又有效地克服了Gauss消元地缺陷。LU分解设A为n阶方阵，若A的顺序主子式Ai均不为零，则矩阵存在唯一的LU(Doolittle杜利特尔）分解。11121n21222n313212(1)nn(111U1nnnnGaussLUALULuuuluulllllu由消去法加上列主元或全主元）有分解：用LU分解法解方程组1391444321131243301024321xxxx72510A7251013914443211312433010272510139142432211312423301021rju1ja11111ualii41372510139142432211312423301021r72201013911624311321217121123301022r11rkkjrkrjrjulaurrrkkrikiriruulal1172201013911624311321217121123301022r11rkkjrkrjrjulaurrrkkrikiriruulal1171117201013911621