西交计算方法总结

计算方法总结目录第1章绪论第2章线性代数方程组第3章数据近似第4章数值微积分第5章非线性方程求解第6章常微分方程数值解法第7章最优化方法简介(基本工具)(误差分析基础)(计算方法应用)第1章绪论1.误差:近似值与真正值之差分为模型误差、数据误差、截断误差、舍入误差2.数制表示1212(),1,0,2,3,,ltjtxtdddxddjt实数可以表示以下形式的进制位有效数字12120.10,0.10,0.510,llttltxdddxdddxxxt有效数字:指一个近似数的有意义的数字的位数若如果则称有位有效数字1(,,,),2(1)(1)1tFtLUUL数系:表示为个数:lU上溢:lL下溢:第1章绪论3.舍入误差:对数进行舍入，得到有t位尾数的浮点数():()xflxxx相对舍入误差11()2tx123:()(1-)()()(1-)()()(1-)()flxyxyflxyxyxxflyy性质浮点运算的注意事项(1)避免产生大结果的运算，尤其是避免小数作为除数参加运算；(2)避免“大”“小”数相加减；(3)避免相近数相减，防止大量有效数字损失；(4)尽可能简化运算步骤，减少运算次数。)(xfl第1章绪论5.方法的稳定性数值稳定:若初始误差导致最终解的误差能被有效地控制6.算法由有限个无二义性法则组成的一个计算过程数值不稳定:若初始误差导致最终解的误差不能被有效地控制4.问题的性态:问题的解对原始数据扰动的敏感性病态问题:数据相对小的扰动引起解的相对大的变化良态问题:数据相对小的扰动不会引起解的相对大的变化,()()()supxfxfxcondfx条件数:当输入数据具有的误差引起问题的结果误差为则算法的特点,描述第1章绪论112.718281828,2.71828325,6xxx例.则的有位有效位数()2.71828225,flx若则有7位有效位数(10,5,-2,3)F例.在中有多少个数?33661),,)1138,,1960169308,19601693083833-8例.下列各式均与等价,在浮点数系F(10,5,-10,10)中3+8哪个公式能获得最准确的结果:(17-68(17+68第1章绪论1-(,,,),-()1()()2tFtLUxflxxxx例.证明在浮点数系中浮点数的相对误差满足,...)3,2(0,1,)(11133221jddddddxjltt其中设211td若lttddddxfl)()(33221有lttdxflx11)(此时lt121tl21lxd1,11有由于txxflx121)(第1章绪论211td，若同理lttddddxfl)1()(33221有lttdxflx11)(lt121tl21lxd1,11有由于txxflx121)(第1章绪论2334610-1-1-1yxxx例.为了使计算的乘除法次数尽可能少,应该式如何计算:_______21610xx例.在浮点数系下,计算的两个根,应如何计算才能使精度较高？(),()fxfx例.对于函数在某个区间上连续可微则求的近似条件数第2章线性代数方程组,,,LULDUGGGauss解法列主元Gauss解法数值解法矩阵分解法:分解分解分解追赶法Jacobi迭代法迭代解法Gauss-Seide线性方l迭代法程组解法32:(),:()onnsoGaus消去的时间复杂度回代消去法32:(),:()onGasnsou消去的时间复列主元消去法杂度回代3:,:,()LUoUnL:单位下三角阵上三角阵时间复杂度分解3:,::,()3nLDULDUo:单位下三角阵对角阵,单位上三角阵时间复杂度分解3(/6),oGnGn:分针对对称正定矩阵,加个解开方运算:三对角阵分带状矩阵分解解,追赶法第2章线性代数方程组:定义,性质.向量与矩阵范数的相范数容性,等价性-1()mcondAAA方程组的条:件数*1*xxbbAAbx(1)当右端向量有扰动***()xxxAACondAAxx(2)当系数矩阵有扰动1,1()AbxxbAkAxbAkAkcondAAA(3)当系数矩阵有扰动右端向量有扰动其中第2章线性代数方程组(1)()kkxGxd迭代:构造,算法判断收敛-111()GDEFIDAdDbJacobi:-11()()GDEFdDEbGauss-Seidel:1,TH2.6收敛G则迭代性判定定理格式收敛,AJacobiTH2.7为严格对角占优格式收敛,-AGaussSeidelTH2.8为严格对角占优格式收敛,-;2-,AGaussSeidelDAJacobiTH2.9对称正定收敛对称正定收敛(1)())1kkxGxdGTH2.10迭代格式收敛的充要条件为(TH2.11迭代格式的误差估计第2章线性代数方程组11,_______,___,___01004AAA11-12例:矩阵A=则113121:12,,1,,TAaGGGaaa例若矩阵可以分解为的形式其中为下三角阵且对角元均为正问的取值范围并请按此要求将此分解36,37PP第2章线性代数方程组1231231235210:242252465-xxxxxxxxxJacobiGaussSeidel例考查方程组的迭代格式,格式的收敛性.123123123:(,,),2323Txxxxxxxxxx例设则是否是范数,是否是范数要证明是否是范数,应验证是否满足范数的三个条件.(P79,14题)要否定一个范数,只需要举一个反例第3章数据近似LagrangeNewtonHermit多项式插值插值连续多项式插值插值插值多项式插值分段一次插值分段多项式插值分段二次插值分段三次样条插值最小二乘近似数据近似第3章数据近似()()()nnfxpxRxTH3.1经过给定插值点的插值多项式唯一多项式插值0()()nniiiLxlxyLagrange插值0()()()()()()niiiiixlxxxxxxx001001201012011()[][,]()[,,]()()++[,,,,]()()()nnnNxyxyxxxxyxxxxxxxyxxxxxxxxxxNewton值插1012011()[,,,,]()()()nnnNxyxxxxxxxxxx差商性质1,对称性()1()[,,...,],[,]!kiiikiikyyxxxxxk差商性质2,第3章数据近似()1()[,,...,]!kiiiikNewtonyxyxxxk个计算带导数条件的插值多项式利用差商性质2,使用插值多项式的思想进行构造Hermit插值插值多项式的误差(1)0013.2()()-()()(),(1)![,,...,,]()nnnnnTHRxyxPxyxxxnyxxxxx(P97)第3章数据近似分段插值多项式2122113.3()max()max8iiaxbiTHEgMMyxxx分段一次多项式的误差3233113.4()max()max12iiaxbiTHEgMMyxxx分段二次多项式的误差222113.5()-()max()max2iiaxbiTHyxsxMMyxxx分段三次样条插值多项式的误差第3章数据近似最小二乘法1112111112112122222122221212()()()()()()()()()nnnnnnnnnnmmnmTTaaabgxgxgxaaabgxgxgxGaaabgxgxgxGGaGy得到方程组或法方程1211221/2221,(1,2,...,)()(1,2,...,),,,...,,(),()()()()(())iiknnnmiiixyimgxknmnpxgxgxgxEpxy给定数据点和一组函数求系数假定使函数满足达到最小1,.()TTaGGGy可以证明最小二乘问题的法方程总有解存在QR分解RQGOTRGQO22222Eh第3章数据近似(4)(),()(),()(),()1[1,2],()12()13()11iiiipxpxfxpxfxfxxpxxfxfx例.求不超过三次的多项式满足条件若求的误差界01210101000122010101()[,],[,],()(2)()()()()()()()()()()()()fxabxxabxxxxxxxxxxxpxfxfxfxxxxxxxRxfxpx例.设在区间上有三阶连续导数,有相应的插值多项式试求此插值多项式的余项的表达式第3章数据近似.(),0,1,2,...,,(,())1(),()()()1(1)kkkknnnkkknxfxxnxfxxxpxpxpxfxxpn例设取以为插值数据点做插值多项式则满足试求534()2009200720062005,2,1,0,1,2()______fxxxxLx例.设则以为插值节点的不超过四次的插值多项式第3章数据近似01010,,...,,()[,,...,]()nniniixxxfxfxxxx例.设节点互异试证明0100,,...,,()()()()()()()nnniiiiiiixxxLagrangexLxlxfxfxxxx解:由节点互异则插值多项式为0()()()()niiiifxxxxx0()()niifxx因此,该多项式最高项的系数为:0100100120101011,,...,,()[,]()[,,]()()[,,,]()()()nnnxxxNewtonNxyyxxxxyxxxxxxxyxxxxxxxxx另一方面,由节点形成的插值多项式为01[,,,]nyxxx该多项式最高项的系数为:因此得证第3章数据近似1010(0,1,,),(0)(1)()nnniiiniixinlxxxxlxLagrange例.设为互异实数试证明其中为插值多项式0()()()()niinifxlxfxRx证明:构造lagrange插值多项式,有110(),(0)0(0)(0)nnniinifxxflxR取(1)01()()()()()()()(1)!nnnfRxxxxxxxxxn101(0)(1)nnnRxxx得证()231234()1.50.20.30.7fxxfx例.给定以下的数据点,利用插值多项式,计算在到之间的根的近似值第3章数据近似--4664()1.060.5671.431.77()sincosxfxpxAxBx例.已知函数f(x)有以下测试数据求形如最小二乘近似解:构造法方程sin()cos()1