数值分析课件1 jsff1

数值计算方法

与MATLAB应用电气工程学院

二、算法的优劣1.计算量或运算量：

一个算法所需的乘除运算总次数。计算量是衡量一个算法好坏的重要指标伴随着计算机速度的快速提升，需要求解问题的复杂程度也在迅速增加。

简单问题算法选择不当，导致无法计算。算法正确，显著简化计算量。例1已知a0,a1,a2,…,an,

x,计算多项式：

1）直接计算运算量（乘法）2）秦九韶算法（南宋1247年）运算量显然运算量为n。求解线性方程组时原则上可以用行列式解法的克莱姆法则。用这种方法解一个n阶方程组，要算n+1个n阶行列式的值，计算量为：n(n-1)(n+1)次乘法运算。当变量较少时，计算量增加并不明显，但是当变量较多时，例如n=20，显然这不是一个太大的方程组，然而即使每秒十亿次的计算机，也要工作千年才能完成。显然这种算法在实际中是完全没有意义的。例如：例2

解线性方程组其中，►克兰姆(Cramer)法则：

运算量(乘除)：►高斯消元法(Gauss)：

运算量(乘除)

Gauss:3060次；按每年3154万秒

Cramer:2）算法的存储量计算程序所占用的工作单元的数目——算法的存贮量。或称占用内存量。尽管计算机能贮存大量信息，目前内存和硬盘容量越来越大，但计算大型算题时也会出现内存紧张问题，因此，尽量节约存贮量也是设计算法时需要考虑的一个因素。3）算法的逻辑结构虽然计算机能够自动执行极其复杂的计算方案，但计算方案的每个细节都需要人来预先制定简单的逻辑结构能使程序结构简洁清晰会明显优化计算次数。对应用商业软件系统，结构简单的程序可使程序升级和修改非常便利。因此设计算法所要考虑的另一个因素是逻辑结构的复杂性问题。从计算人员的角度来看，总是希望算法的逻辑结构尽量简化，使得编制程序和使用程序时比较方便。由此可见，虽然计算机功能强大，如果想提高其使用效率，就不能忽视算法的研究。计算量大小、存贮量多少、逻辑结构是否简单，是评定算法优劣的标准。三、算法的递推性

递推化算法计算机适宜进行大量重复的简单计算。科学计算常用算法递推化的基本思想：复杂的计算过程归结为简单过程的多次重复循环递推化的优势：简化程序的逻辑结构，同时也可以加快计算速度，可以节省内存空间。例：对给定的X求下列n次多项式的值

按降幂的次序排列为设用表示第层（从里数起）的值，因此最里面一层为：令初值则第二层为：第K层为：这种递推算法不但逻辑结构简单，而且由于反复使用一个存储单元存放从而可以节省内存。

§1误差绝对的准确和精确数值分析或数值计算，不严格，不准确的错觉在工程领域中，既不存在也没有实际意义。总会存在误差工程实际的合理性研究的问题所容许，计算结果的近似性不可避免否则计算的结果就没有意义。因此研究算法的同时也要分析误差。一、误差的来源

1、模型误差指数学模型与实际问题之间出现的误差。

2、观测误差

由观测产生的误差。

3、截断误差

当数学模型不能得到精确解时，通常要用数值方法求它的近似解，其近似解与精确解之间的误差称为截断误差。如函数f(x)用Taylor展式的有限项来近似代替。

4、舍入误差

由于受计算机字长的限制，计算时只能取有限位数进行运算，由此产生的误差称舍入误差。在数值计算中考虑：截断误差

舍入误差

1）截断误差我们知道，许多数学运算（如微分，积分及无穷级数求和等）是通过极限过程来定义的，然而计算机只能完成有限次算术及逻辑运算，因此须将解题方案转化成算术运算与逻辑运算的有限序列。这种加工常表现为某种无穷过程的“截断”，由此产生的误差通常称为“截断误差”。下面以指数展开求和为例说明。指数函数可展开成下列幂级数形式许多数学计算如微分，积分，无穷级数的计算在理论上是无穷过程，而实际计算只能完成有限的运算，截断误差也是不可避免的。2）舍入误差计算机上只能用有限数位来表示一个数，对于计算过程中超出限定位数的尾数都要被舍去而造成误差，这种误差称为舍入误差。产生较大误差情形。两个相近的数相减，两个数值大小相差很大的数相除以后再乘一个很大的数因此计算时应该避免这种情况发生。（1）避免两个非常接近的数进行减法运算设数字a=44.407,b=44.396，各有五位有效数字,若取3位有效数字进行减法运算：V=a-b=44.4-44.4=0.0

有效数字的损失,说明上述算法准确度较低,因此,在计算时需要选择适当的计算公式,以免这种情况发生。

类似情况还有其他形式。这些在计算选择中均应注意。由于计算机只能用有限位数表示一个数，在计算过程中，当两个数很接近时，很有可能相减后所得结果为0，或者相减后有效数字位数大大减小。取四位有效数字计算时

V=a-b=44.41-44.40=0.01例3:设x为正数,当x较大时,计算算式改为：上述两数a、b分别为1972和1971的开平方，取三位有效数字代入右端计算：取四位有效数字代入右端计算：差别不大此外还有x较大时：其他的有：x接近于0时：，（2）防止大数吃掉小数在上机计算时，有时计算中用到的数其数量级可能相差很大，由于计算机字长有限，或在实际应用中，定义的数字长度一定，如不注意运算次序，就可能出现当两个绝对值相差很大的数进行加法或减法运算时,绝对值小的数被绝对值大的数“吃掉”，从而使得计算结果不可靠。例4:解一元二次方程采用因式分解法,得到两个根为：x1=108,x2=1。

而采用计算机解题时，方法不当可得：x1=108,x2=0。

在8位十进制计算机上计算

计算机内部计算时，要先写成浮点形式，且要先对阶，对阶时，后者在8位机上表示时为0，则则计算结果就是大数的值。

(3)防止接近于零的数做除数(4)

防止两个相差很大的数相除然后再乘一个很大的数二、误差限1）绝对误差设x*为精确值（或准确值），x为x*的近似，称e=x*-x为近似值x的绝对误差。绝对误差限：如果精确值

x*

与近似值

x的误差的绝对值不超过某个正数ε，即

|e|=|x*－

x|≤ε。则精确值也可表示为

x*=x±ε，或

。

在给定的允许误差下近似值x和真值x*可以看成是“重合”的，或者说在满足允许误差的情况下，结果x是“准确”的。这就是工程中的准确的概念。例如：近似值x1=123.456和x2=0.0123456。它们的绝对误差限分别为：2）相对误差绝对误差有时不能说明误差的程度，这时需要用到相对误差的概念。例如：某厂生产某种产品1000件，不合格产品10件；另一种产品2000件，不合格产品10件，虽然绝对误差相同，但相对误差是不同的：10/1000=1%；10/2000=0.5%

三、有效数字误差限和有效数字均能表示一个数字的精确程度，但其意义是有所区别的。在数值计算中,求出一个近似值后，我们希望明确其准确程度。对于（1）若取误差为则该近似值有三位数是准确的，有3位有效数字。（2）近似值取误差为其误差绝对值小于

（3）若取近似值为其误差为虽然给出的是5个数字，但其误差绝对值超过了小数点后第四位的半个单位，因此其最后一位是不准确的，仅有四位有效数字。四舍五入的概念。第二章方程求解§1引言问题求解：多项式——代数方程无解析解经常对简单的二次方程

有解析解而对无解析解非数值解数值计算方法特点：概念十分简单，不需要引入许多复杂的数学知识。适合于在数字计算机上进行计算。(递推化)有时不能得出结果，这个问题将在后面多种计算问题中进行具体的讨论。(方法不当)数值计算一般来说只能得到近似解——但可以改善——选择计算方法——精确的结果。例如：对方程f(x)求解。称为它的根或函数的零点。数值解法两步：先确定根的某个粗糙的近似值即初始近似值，然后再将初始近似值采取某种方法逐步加工成满足所需精度的结果。“扫描”法求根的初始近似值。根的分布可能是很复杂的，假设方程在某个区间(a,b)内有且仅有一个实单根，从左端点a出发，按预选的步长h一步一步地向右求取函数值，进行一次根的“扫描”，至到所求的根必在点与之间或作为根的初始近似值

,由于：方程至少有一个正实根。

00.51.01.5的符号

负负负正在区间（1.0,1.5）内必有一个实根。取初始根。例2.1考察方程扫描中，步长的选择是关键。只要步长选得足够小，——可以得到具有任意精度的近似根。

例如将步长选为计算问题的允许误差，则最终得到的两个边界值均可满足误差要求。但步长小时计算量增大。因此如果精度要求比较高就不宜采用这种方法。

数值计算中有很多对粗糙近似值逐步精确化的方法。

§2二分法假定方程在区间（a,b）内有且仅有一个根

取其中点将区间（a,b）分为两半

是否同号

判断(1)同号说明根在右侧，取新的求根区间（x0,b)

记为（a1,b1)(2)异号说明根在左侧，新的求根区间（a,x0)

记为（a1,b1)如此反复下去，便可以得到一系列有根区间。每次二分求根区间缩小一半近似解序列误差只要求根区间的长度小于关于允许误差将能“准确”满足则近似解注：《庄子天下篇》有这样一个命题：“一尺之棰，日取其半，万世不竭。”实际上也说明二分法可以得到任意精度的近似解，其极限即为根的真值。例2.2用二分法求方程在区间内的实根。要求准确到小数点后第2位。即允许误差为0.005，书上给出了计算结果。显然只要便能达到所要的精度

特点：求根区间缩小的速度很快，较少计算次数可得达精度要求，与直接扫描相比优势明显。§3迭代法迭代法是一种逐次逼近法,求解非线性代数方程常用方法。原理：原方程变形作为固定的校正公式,反复校正根的近似值,使之逐步接近精确值,最后得到满足精度要求的结果。同样方程在设将方程变形为以下形式：附近的一个根。

KXKKXK012341.51.357211.330861.325881.3249456781.324761.324731.324721.32472对于方程一般形式设法将它化为下列形式如果给出根的某个近似值代入上式右端有：解序列