数值计算方法-数值分析课件

中国石油大学（华东）理学院程序设计上机计算设计高效、可靠的数值方法数值问题求解近似结果输出重点讨论用计算机解决科学计算问题的过程：实际问题建立数学模型数学问题设计数值计算方法的原则收敛性：方法的可行性稳定性：初始数据等产生的误差对结果的影响可以（计算机）编程实现：有限性计算量要小：时间复杂度要小，运行时间要短存贮量要尽量小：空间复杂度要小可靠性分析计算复杂性误差估计：误差的分析和度量面向计算机便于（计算机）编程实现：逻辑复杂度要小简言之：既“快”又“准”•运算少；•易编程；•存储少；•精度高。§1误差/*Error*/一、误差的来源与分类/*Source&Classification*/1、从实际问题中抽象出数学模型——模型误差/*ModelingError*/2、通过观测得到模型中某些参数（或物理量）的值——观测误差/*MeasurementError*/3、数学模型与数值算法之间的误差求近似解——方法误差(截断误差/*TruncationError*/)4、由于机器字长有限，原始数据和计算过程会产生新的误差——舍入误差/*RoundoffError*/二、误差分析的基本概念/*BasicConcepts*/设为真值（精确值），为的一个近似值称为近似值的绝对误差，简称误差。xxxxexx注：误差可正可负，常常是无限位的绝对误差限/*accuracy*/——绝对值的上界exx如：5314159110314159262.(.)绝对误差还不能完全表示近似值的好坏（绝对误差/*absoluteerror*/）11.Def近似值的误差与准确值的比值：xexexxxx称为近似值的相对误差，记作reexx注：实际计算时，相对误差通常取rexxexx12.Def（相对误差/*relativeerror*/）相对误差也可正可负rexxxx13.Def（有效数字/*SignificantDigits*/）相对误差限——相对误差的绝对值的上界r/*relativeaccuracy*/如：31415926.314.3141592.3位21102e6位51102e若近似值与准确值的误差绝对值不超过某一位的半个单位，该位到的第一位非零数字共有位，则xxnxn称有位有效数字注：0.2300有4位可能有效数字，而00023只有2位有效数字。12300如果写成0.123105，则表示只有3位有效数字。数字末尾的0不可随意省去！3.1415926535897932;3.1415例1：问：有几位有效数字？请证明你的结论。*10501050*and103141504131..π||π,.π*证明：有位有效数字，精确到小数点后第位。43有效数字与相对误差和绝对误差之间关系密切！例3计算下列多项式的值nnnaxaxaxp10)(为已知数据01,,,naaax分析：输入数据为，输出数据为，若直接由算出，再乘相应的系数并相加，则要做次乘法和次加法，占用个存储单元。0,,,naaxx)(xpnxx,,2021,,,aaann12()nnn12n秦九韶方法，也称为Horner算法用递推公式表示为nnaxaxaxaxp))(()(11000abxbabiii1ni,,2,1)(xpbnn只用次乘法和次加法，并占用个存储单元n2nn三、数值算法及稳定性/*NumericalAlgorithmandStability*/新冲旧：ibabxni,,2,1大家一起猜？dxe2x1011/e解法之一：将作Taylor展开后再积分2xe91!4171!3151!21311)!4!3!21(10864210dxxxxxdxe2xS4R4/*Remainder*/,104Sdxe2x取则111!5191!414R称为截断误差/*TruncationError*/005091!414.R这里7430024010333014211013114....S0010200050..|舍入误差/*RoundoffError*/|006000100050102...dxe-x的总体误差计算=0.747……由截去部分/*excludedterms*/引起由留下部分/*includedterms*/引起例4近似计算210xedx10333333.100238042.一个算法如果输入数据有扰动（即误差），而计算过程中舍入误差不增长,则称此算法是数值稳定的，否则此算法就称为不稳定的。14.Def（数值稳定性/*NumericalStability*/）对数学问题本身如果输入数据有微小扰动，引起输出数据（即问题真解）的很大扰动，这就是病态问题。15.Def（病态问题/*ill-posedproblem*/）它是数学问题本身性质所决定的，与算法无关，也就是说对病态问题，用任何算法（或方法）直接计算都将产生不稳定性。此公式精确成立80001050.IIE记为*0I632120560111100.edxeeIx则初始误差111111110010nI)e(ndxexeIdxexennnn101091110121113121413151411036787944............110008812800111003059200112063289600113722764801149495942411514233914II.II.II.II.II.II.II.????!!!Whathappened?!例5计算101012,,,,......nxnIxedxne11101011[]nxnxnnIxenxedxnIe公式一：考察第n步的误差nE11|||||(1)(1)|nnnnnEIInInI||!01En||Enn我们有责任改变。造成这种情况的是不稳定的算法/*unstablealgorithm*/迅速积累，误差呈递增趋势。初始的小扰动801050||.E)1(1111nnnnInIInI公式二：注意此公式与公式一在理论上等价。方法：先估计一个IN,再反推要求的In(nN)。11)1(1NINeN1112(1)1NNIIeNN可取0*NNNIIEN,时当()()()()()()1514151314121311121011121110042746233216161100638169181511006687022014110071779214131100773517321211008387711511110367879442I.eII.II.II.II.II.II.()01110632120561II.取考察反推一步的误差：()()1111||11||NNNNEIIENNN以此类推，对nN有：||)1(...)1(1||NnEnNNE误差逐步递减,这样的算法称为稳定的算法/*stablealgorithm*/在我们今后的讨论中，误差将不可回避，算法的稳定性将会是一个非常重要的话题。§2误差分析的方法和原则/*ErrorAnalysis*/一、误差分析的方法1、向前误差分析法：利用误差限，随着计算过程逐步向前进行分析，直至估计出最后的结果。（例4）1212()()()xxxx121221()()()xxxxxx12211222()()()xxxxxxx注：两个近似数，四则运算得到的误差限分别为12,xx（1）（2）对于函数y=f(x)，若用x*取代x，将对y产生什么影响？分析：e*(y)=f(x*)f(x)e*(x)=x*xMeanValueTheorem()()fxxx*与x非常接近时，可认为，则有：()()ffx()()()eyfxex即：产生的误差经过作用后被放大/缩小了倍。故称为放大/缩小因子/*amplificationfactor*/或绝对条件数/*absoluteconditionnumber*/.xf()fx()fx()|()|()reyeyfx()|()|rexexx()()()()()()()rrfxfxxxxeyxxfxxxfxexfx相对误差条件数/*relativeconditionnumber*/f的条件数在某一点是小\大，则称f在该点是好条件的/*well-conditioned*/\坏条件的/*ill-conditioned*/。注：关于多元函数可类似讨论.)...,(21nx,x,xfy()()()fxexfx例7105%x设,试求函数的相对误差限.()nfxx解：由题设知:近似值为,绝对误差限为10x()5%x1111()()nnfxxxnnx()()()()0.005()()()reffxexexeffxfxnxn2、向后误差分析法：把舍入误差的累积与导出的已知量的某种摄动（微小误差）等价起来，A12,,,nxxx即令1122(,,,)nnAfxxx利用摄动理论，由的界估计出最后的舍入误差界。i3、区间分析法：把参加运算的数都看成区间量，根据区间运算规则求得最后结果的近似值和误差限。4、概率分析法：利用概率统计方法，将数据和运算中的舍入误差视为适合某种分布的随机变量，然后确定计算结果的误差分布。二、几点注意事项/*Remarks*/1、避免相近二数相减例：a1=0.12345，a2=0.12346，各有5位有效数字。而a2a1=0.00001，只剩下1位有效数字。几种经验性避免方法：;xεxεxεx;1lnlnlnxεxεx当|x|1时：;2sin2cos12xx...6121112xxxex2、避免小分母:分母小会造成浮点溢出/*overflow*/3、避免大数吃小数例：用单精度计算的根。010)110(992xx精确解为110291x,x算法1：利用求根公式aacbbx242在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1的指数部分须变为1010，则：1=0.00000000011010，取单精度时就成为：109+1=0.100000001010+0.000000001010=0.100000001010大数吃小数024,102422921aacbbxaacbbx算法2：先解出再利用9211024)(aacbbsignbx11010991221xacxacxx注：求和时从小到大相加，可使和的误差减小。例：按从小到大、以及从大到小的顺序分别计算1+2+3+…+40+1094、先化简再计算，减少步骤，避免误差积累。一般来说，计算机处理下列运算的速度为exp,,5、选用数值稳定的算法。称为尾数，j为阶§3计算机的数系结构/*StructureofNumberSystem*/计算机的数系是一个不完整的数系。计算机只能表示有限个数，即