第二章：数值计算简介数值计算的基本概念数值算法优劣的判断数值算法内容介绍2010-9-17金融学院－－金融计算22010-9-17金融学院－－金融计算3§1 数值计算的基本概念软件的核心就是算法。

20 世纪最伟大的科学技术发明---计算机计算机是对人脑的模拟，强化了人的思维智能；没有软件的支持，超级计算机只是一堆废铁而已；算法犹如乐谱，软件犹如CD 盘片，而硬件如同CD 唱机。

什么叫算法？算法定义：由基本运算及运算顺序的规定所构成的完算法。

它可以直接转整的解题步骤，称为算法换为计算机程序。

2010-9-17金融学院－－金融计算42010-9-17金融学院－－金融计算5算法的描述：日常语言和数学语言结合描述程序流程图程序语言例：求解二元一次联立方程组⎩⎨⎧=+=+22221211212111b x a x a b x a x a2010-9-17金融学院－－金融计算6用行列式解法：首先判别12212211a a a a D −=（1）如果，则令计算机计算0≠D () , 1222211D a b a b x −=()Da b a b x 2111122−=输出计算的结果x 1，x 2。

（2）如果D = 0，则或是无解，或有无穷多组解。

是否为零，存在两种可能：日常语言描述2010-9-17金融学院－－金融计算712212211D a a a a −=令通过求解过程，可以总结出算法步骤如下：S2 计算12212211D a a a a −=S3 如果0D =则输出原方程无解或有无穷多组解的信息;否则0D ≠ D 1212112b a b a x −= D 2121221b a b a x −=S1 输入2122211211,,,,,b b a a a a S4 输出计算的结果21,x x 算法语言2010-9-17金融学院－－金融计算8输入2122211211,,,,,b b a a a a D=a 11a 22-a 12a 21D=0开始Da b a b x Da b a b x /)(/)(21111221222211−=−=输出x 1, x 2结束No 输出无解信息Yes 程序流程图现代科学研究的三大支柱理论研究科学实验科学计算计算数学2010-9-17金融学院－－金融计算921世纪信息社会的两个主要特征：“计算机无处不在”“数学无处不在”21世纪信息社会对科技人才的要求：--会“用数学”解决实际问题--会用计算机进行科学计算2010-9-17金融学院－－金融计算102010-9-17金融学院－－金融计算11建立数学模型选取计算方法编写上机程序计算得出结果金融模型的量化过程分析金融问题分析结果解释问题数值计算过程在建立了数学模型之后，并不能立刻用计算机直接求解，由于计算机能够进行加、减、乘、除及逻辑运算，每个解数学问题的算法只能通过计算机能够执行的运算来表示，所以必须将数学模型中的连续变量离散化，编制出计算机可以识别的指令组合，称之为算法，再上机计算得出满意的数值结果。

2010-9-17金融学院－－金融计算121、定义数值计算的定义数值计算方法，是数学的一个分支，对象是研究建立各种数学问题数值计算算法的方法与理论，任务是提供在计算机上可行的、理论可靠的、计算复杂性好的各种常用算法。

2010-9-17金融学院－－金融计算13但并不是所有的问题都可以编制算法进行计算，那些可以编制算法进行计算的问题称为可计算问题，否则称为不可计算的问题，同时可以编制算法的问题也不是全部可以利用计算机实现，有些问题算法太复杂，计算量过大，以致找不到有效的算法，这种问题称为不可处理问题。

2010-9-17金融学院－－金融计算14第二章：数值计算简介数值计算的基本概念数值算法优劣的判断数值算法内容介绍2010-9-17金融学院－－金融计算15§2判断标准评价算法的两个主要标准：速度和精度一个面向计算机,计算复杂性好,存储量少，逻辑结构简单，精度高，又有可靠理论分析的算法就是一个好算法.2010-9-17金融学院－－金融计算161、计算的复杂度：计算复杂性包括时间复杂性和空间复杂性时间复杂性即计算量：一个算法所需基本运算总次数. （包括四则运算，逻辑运算）一个算法所需的乘除运算总次数。

空间复杂性即存储量，指计算过程中需要的存储数量。

2010-9-17金融学院－－金融计算17算法复杂度比较实例1255x例1计算254 A:x255=x.x (x)算法A: (SAS程序) data;x=2;y=x;do i=1 to 254; y=y*x;end;put y;run;计算结果：y=5.7896045E76计算量：N=256存储量：3开始X=2,y=x,i=1i>254Y=y*xi=i+1输出y结束YN2010-9-17金融学院－－金融计算182010-9-17金融学院－－金融计算19实例1（续）B:x 255=x ·x 2·x 4·x 8·x 16·x 32·x 64·x128计算结果：y=5.7896045E76计算量：N=17存储量：4算法B （SAS ）:Data;x=2; s=x;y=x;do i=1 to 7;s=s*s; y=y*s;end;put y;run;算法B复杂度更小，更好！2010-9-17金融学院－－金融计算2032()34262p x x x x =+−+计算多项式例：的值。

231,x x x 由计算法：算出后再算。

需乘法5次，加法3次，存储单元7个。

()[(34)22]6p x x x x =+−+算法：需乘法3次，加法3次，存储单元6个。

算法复杂度比较实例22010-9-17金融学院－－金融计算21算法2、秦九韶算法（1247）(Horner 算法1819)算法1、需乘法2n-1次，加法n次，存储单元n+4个。

0111)(a x a xa x a x P n n n n n ++++=−−L 一般地，计算n 次多项式的值需乘法n次，加法n次，存储单元n+3个。

计算如下例2（续）2010-9-17金融学院－－金融计算22有递推公式1210()(((())n n n n P x x x x x a x a a a a −−=+++++L L nn a s =k k k a xs s +=+10)(s x P n =()0,1,2,,1L −=n k 例2（续）复杂度的度量关键相比较来说，随着计算机的发展，时间复杂性是我们更关注的。

无论是时间复杂度的度量还是空间复杂度的度量，最重要的不是它的精确复杂度，而是复杂度的增长速度，这个速度可以用无穷大阶数来表示。

对于前面两个例子，虽然算法2相对算法1复杂度更小一些，但是就无穷大的阶数来讲是同阶的0(n)，因此，在计算机计算时他们所需要的时间差别并不大。

2010-9-17金融学院－－金融计算232010-9-17金融学院－－金融计算24一、误差的背景介绍1. 来源与分类¾从实际问题中抽象出数学模型——模型误差例3:请描述股票价格与时间之间的关系。

}21exp{2000t W ut s S s S dW S dt S dS t t t t t t σσσμ−+=⇒=+=其中μ为期望收益率,σ为收益波动率。

2.计算精度的度量－－误差2010-9-17金融学院－－金融计算25¾通过测量得到模型中参数的值——观测误差¾求近似解——截断误差¾机器字长有限——舍入误差π= 3.1415926…L 3333.031=x = 8.12345数值计算研究的误差！431()4!xe S x x −=+L2010-9-17金融学院－－金融计算26二、绝对误差、相对误差1．绝对误差与绝对误差限例4:若用以厘米为最小刻度的尺去量桌子的长，大约为1.45米，求1.45米的绝对误差。

1.45米的绝对误差=？不知道！定义1：设x 是准确值，x *为x 的一个近似值，称*)(x x x e −=是近似值x 的绝对误差绝对误差,简称为误差误差。

2010-9-17金融学院－－金融计算27但实际问题往往可以估计出不超过某个正数ε，即，则称ε为绝对误差限，有了绝对误差限就可以知道x 范围为)(x e ε≤−*x x ε±=*x x ],[**εε+−x x 即x 落在内。

在应用上，常常采用下列写法来刻划x *的精度。

εε+≤≤−**x x x2010-9-17金融学院－－金融计算282．相对误差和相对误差限xx x x e *−=定义2：设x 是准确值，x *是近似值，称rxxx ε≤−*满足为近似值x 的相对误差相对误差，相应地，若正数，r ε则称为x 的相对误差限相对误差限。

r ε2010-9-17金融学院－－金融计算293．有效数字则说x*近似表示x 精确到小数后第n 位，并从这第n 位起直到最左边的非零数字之间的一切数字都称为有效数字有效数字，并把有效数字的位数称为有效位数有效位数。

定义3：如果nx x −×≤−1021*410211416.3−×≤−π5102114159.3−×≤−π由上述定义0015926.014.3=−π有效数位为3位0000074.01416.3−=−π有效数位为5位0000926.01415.3=−π有效数位为4位例、误差的传播与积累例5：蝴蝶效应——纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！NY BJ以上是一个病态问题2010-9-17金融学院－－金融计算30度量误差的原则当某个量的准确值很小或很大时，相对误差比绝对误差更能反映准确数与近似数的差异。

在数值计算中，尽可能多地保留近似数的有效数字，有效数字越多，相对误差越小，计算结果越精确。

2010-9-17金融学院－－金融计算312010-9-17金融学院－－金融计算323、数值计算减小误差的方法1．要使用数值稳定的算法例6：求（n = 0, 1, 2, …, 8）的值。

∫+=10dx 5x x I nn 解：由于nx x x x I I n n n n n 1dx dx 5551011011==++=+∫∫−−−初值)2.1ln(5ln 6ln dx 51100=−=+=∫x I2010-9-17金融学院－－金融计算33递推公式⎪⎩⎪⎨⎧=−==−)8,,2,1(,51)2.1ln(10L n I n I I n n 按上式就可以逐步算出09.05101≈−=I I 05.052112≈−=I I Whathappened?!025.155145≈−=I I 952.456156−≈−=I I 不稳定的算法！……….2010-9-17金融学院－－金融计算34这就是误差传播所引起的危害!改变公式：n I I n n 151=+−将公式变为不妨设I 9 ≈I 10，于是由10951501I I −=可求得I 9 ≈0.017，按上式可逐次求得)1,,1,( 51511L −=−=−n n K I K I K k2010-9-17金融学院－－金融计算35I 8 ≈0.019I 7 ≈0.021I 6 ≈0.024I 5 ≈0.028I 4 ≈0.034I 3 ≈0.043I 2 ≈0.058I 1 ≈0.088I 0 ≈0.182稳定的算法！2．要避免两个相似数相减在数值计算中，两个相近的数作减法时有效数字会损失。