数值分析ppt第一章

1、上页上页下页下页第一章第一章 绪绪 论论1.1 1.1 数值分析的研究对象与特点数值分析的研究对象与特点 数值分析是计算数学的一个主要部分，计算数值分析是计算数学的一个主要部分，计算数学是数学科学的一个分支，它是研究用计算机数学是数学科学的一个分支，它是研究用计算机求解各种数学问题的数值计算方法及其理论与软求解各种数学问题的数值计算方法及其理论与软件实现的一门科学。件实现的一门科学。 计算机解决实际问题的一般步骤如下计算机解决实际问题的一般步骤如下: : 实际问题实际问题数学模型数学模型数值计算方法数值计算方法程序设计程序设计上机求解上机求解 上页上页下页下页 由实际问题应用有关科学知识和数学

2、理论建由实际问题应用有关科学知识和数学理论建立数学模型之过程，通常作为应用数学的任务，立数学模型之过程，通常作为应用数学的任务，而根据数学模型提出求解的数值计算方法则为计而根据数学模型提出求解的数值计算方法则为计算数学的任务，也是数值分析的研究对象。算数学的任务，也是数值分析的研究对象。数值分析的内容包括：数值分析的内容包括： 插值、函数逼近与曲线拟合、数值微分与积分、插值、函数逼近与曲线拟合、数值微分与积分、数值代数（线性代数方程组得求解、非线性方程数值代数（线性代数方程组得求解、非线性方程得求根问题、矩阵的特征值与特征向量的求法）、得求根问题、矩阵的特征值与特征向量的求法）、常微分与偏微分

3、方程的数值计算。常微分与偏微分方程的数值计算。上页上页下页下页 数值分析是研究适合在计算机上使用的实际可数值分析是研究适合在计算机上使用的实际可行、理论可靠、计算复杂性好的数值计算方法行、理论可靠、计算复杂性好的数值计算方法. 即即第一第一 面向计算机面向计算机, 即算法只能由计算机可执行的即算法只能由计算机可执行的 加减乘除四则运算和各种逻辑运算组成加减乘除四则运算和各种逻辑运算组成. 第二第二 要有可靠的理论分析要有可靠的理论分析. 基本概念包括误差、稳基本概念包括误差、稳 定性、收敛性、计算量、存储量等定性、收敛性、计算量、存储量等.第三第三 要有良好的复杂性及数值实验要有良好的复杂性及

4、数值实验, 计算复杂性包计算复杂性包 括时间复杂和空间复杂性括时间复杂和空间复杂性, 并通过数值试验检并通过数值试验检 验其计算复杂性验其计算复杂性.上页上页下页下页 例如例如, 求解一个求解一个n阶线性方程组阶线性方程组, 用行列式解法的用行列式解法的克莱姆法则要进行克莱姆法则要进行(n+1)n！(n-1)次乘除运算次乘除运算. n=20时时, 大约进行大约进行1021 次运算次运算, 如用每秒如用每秒3亿次乘法运算的巨亿次乘法运算的巨型计算机要连续工作型计算机要连续工作) (100365246060103101121年年 完全没有实际意义完全没有实际意义. 而用加减消元法只需而用加减消元法

5、只需3000 次乘法次乘法运算运算.上页上页下页下页一一 误差的来源误差的来源1. 模型误差模型误差:在建立数学模型过程中在建立数学模型过程中, 不可能将所有因素均考不可能将所有因素均考虑虑, 必然要进行必要的简化必然要进行必要的简化, 这就带来了与实际这就带来了与实际问题的误差。问题的误差。2. 观测误差观测误差: 测量已知参数时测量已知参数时,数据带来的误差。数据带来的误差。3. 截断误差截断误差: 在设计算法时在设计算法时,近似处理带来的误差。近似处理带来的误差。4. 舍入误差舍入误差: 计算机的字长是有限的计算机的字长是有限的, 每一步运算每一步运算 均需四舍五入均需四舍五入, 由此产

6、出的误差。由此产出的误差。1.2 1.2 误误 差差上页上页下页下页二、误差的基本概念二、误差的基本概念 1. 误差和误差限误差和误差限,*)(*xxx 设设 x* 是准确值是准确值x的一个近似值的一个近似值, 称称 e(x*) = x* - x为近似值为近似值x*的绝对误差的绝对误差, 简称误差简称误差. e(x*)又简记又简记e*. 误差是有量纲的，可正可负。误差是有量纲的，可正可负。误差是无法计算的误差是无法计算的 (因为准确值因为准确值 x 不知道不知道), 但可以估但可以估计出它的一个较小上界计出它的一个较小上界, 即即 |x* - x| (x*) , 称称 (x*)是近似值是近似值

7、 x* 的绝对误差限的绝对误差限, 简称误差限简称误差限.上页上页下页下页2. 相对误差和相对误差限相对误差和相对误差限为近似值为近似值 x* 的相对误差。简记为的相对误差。简记为er*。实际计算中实际计算中, 由于准确值由于准确值 x 总是未知的总是未知的, 且由于且由于()()e xe xxx ()()e xxxxx 2( ()()e xx xe x 称称()()re xxxexxx 2()1()rrexex 是是er(x*)的平方项级的平方项级.上页上页下页下页当当er(x*)较小时较小时, 常取常取相对误差是无量纲的相对误差是无量纲的, 也可正可负也可正可负, 它的绝对值的较小它的绝对

8、值的较小上界称为该近似值的相对误差限上界称为该近似值的相对误差限, 记作记作*)(xr 简记为简记为( *)( *)( *)*rrxexxx *r , 即即*)()(xxxxxexer 上页上页下页下页 三、有效数字三、有效数字定义：如果近似值定义：如果近似值x*的误差限不超过某一位的半个的误差限不超过某一位的半个单位，该位到单位，该位到 x* 的第一位非零数字共有的第一位非零数字共有n 位位,我们我们称称 x* 有有n 位有效数字。它可表为位有效数字。它可表为)(*)(1121101010nnmaaax为整数，为整数，其中其中为为0-9 0-9 中的一个数字中的一个数字, ,naaa,21m

9、a, 01且且11021nmxx*上页上页下页下页*0.0020.005xx 所以所以 x* = 3.14 作为作为的近似值的近似值,有有3位有效数字；又位有效数字；又取取x*=3.1416 时时,*0.0000080.00005xx 所以所以 x* = 3.1416 作为作为 的近似值的近似值,有有5位有效数字。位有效数字。例例 = 3.1415926535, 取取 x* = 3.14 时，时，即即 m- n +1= - 2, m=0, n = 3, 所以所以 x* = 3.14 作为作为 近近似值时似值时, 就有就有3位有效数字。位有效数字。210210050.上页上页下页下页定义：称近似

10、值定义：称近似值x*的末位也是有效数字的近似数为的末位也是有效数字的近似数为有效数有效数, 误差限不超过末位的半个单位。误差限不超过末位的半个单位。Note: 1. 对精确值进行四舍五入得到的近似数均为对精确值进行四舍五入得到的近似数均为 有效数有效数; 上页上页下页下页有有n位有效数字，位有效数字，。则其相对误差限为。则其相对误差限为)(*)(1121101010nnmaaax01 a111021*)( nraxe证明证明故故mmaxa1011011)(|此定理说明，相对误差是由有效数字决定的。此定理说明，相对误差是由有效数字决定的。定理定理1设近似值设近似值11111021101050nm

11、nmraaxxxxe.|*|*)()(*)(1121101010nnmaaax，从而，从而上页上页下页下页设近似值设近似值mnaaax1021.*的相对误差的相对误差,10)1(2111 na则它至少有则它至少有n位有效数字。位有效数字。证明证明 已知已知*)(xer*)(*xexxxr 故故x* *至少有至少有n位有效数字。位有效数字。111102(1)na 不大于不大于定理定理 21111102110121101nmnmaa)()(上页上页下页下页 ()( )( )( *) ( *)e f xdf xfx dxfxe x 取绝对值得取绝对值得| ( *)| |() | | ( *) |()

12、 |( *)|( *) |( *)e fxfxe xfxxfxx 其中其中 为近似数为近似数 x* 的误差限。的误差限。函数运算误差函数运算误差1. 设设 f (x)在在(a,b)内连续可微内连续可微, x 的近似值为的近似值为 x*, f (x)的的近似值为近似值为 f (x*), 其误差为其误差为e f(x*),误差限为误差限为 ()f x ()x 第二节第二节 数值运算中误差的传播数值运算中误差的传播上页上页下页下页*)(*)(*)(| )(|*)(xxfxxfxf *)(*)(*)(*)()()(*)(xxfxfxxfxfxfr 2. 多元函数多元函数),(21nxxxfy 自变量的近

13、似值为自变量的近似值为yxxxn*,*,*,21的近似值为的近似值为12*(*,*,*),nyf xxx 函数值函数值 y*的运算误差为的运算误差为可得出一元函数运算的误差限和相对误差限分别为：可得出一元函数运算的误差限和相对误差限分别为：1212121211( *) (*,*,*)(,)(,)(*,*,*)(*)(*)nnnnnniiiiiie ye f xxxdf x xxf x xxf xxxe xe xxx 上页上页下页下页1212121211( *) ( *,*,*)(,)(,)( *,*,*)( *)( *)nnnnnniiiiiie ye f xxxdf x xxf x xxf

14、xxxe xe xxx ,*),*,*,(21 iinxfxxxxf记记则上式简记为则上式简记为*)(*)(*)(11iniiiniixexfxexfye 上页上页下页下页相对误差限相对误差限11*( *)*nniiiiffyxx|*|*)(*|*)(*)(11yxxfyxxfyniiniir 于是误差限于是误差限*)(*)(*)(11iniiiniixexfxexfye 上页上页下页下页由此可得四则运算的误差由此可得四则运算的误差, 以两数为例写出以两数为例写出121221()()()e x xxe xxe x 112212222| | () | | () |,0()xxe xxe xexx

15、x 121221()()()x xxxxx 112212222|()|(),0()xxxxxxxx )()()(*2*1*2*1xxxx 上页上页下页下页例例1 计算多项式的值计算多项式的值: 每项每项 ak xk 有有k 次乘法运算次乘法运算, 因此计算因此计算 Pn (x) 共需共需 11 22n nn 次乘法和次乘法和n次加法运算。次加法运算。 1210nnnnPxa xaxaxaxa 如将如将 Pn (x) 写成写成: 一、简化计算步骤一、简化计算步骤, 减少运算次数减少运算次数第三节第三节 设计算法时应注意的原则设计算法时应注意的原则0( )nknkkPxa x 上页上页下页下页用递

16、推算法用递推算法: 01, , 1,2, .nkkn kuauuxakn 最终最终 Pn (x)=un 共需共需n 次乘法和次乘法和n次加法运算。次加法运算。 一般地要注意一般地要注意:能在循环外计算能在循环外计算, 就不要放在循环就不要放在循环内计算。内计算。 1210nnnnPxa xaxaxaxa 上页上页下页下页如用四位有效数字计算如用四位有效数字计算: 例例217013 13.04 13 0.04 结果只有一位有效数字；结果只有一位有效数字；两个相近的数相减两个相近的数相减,有效数字会大大损失。有效数字会大大损失。二、二、 注意避免两个相近数的相减注意避免两个相近数的相减170130

17、.0384048 如改为：如改为：11170130.0384013.041317013 有四位有效数字有四位有效数字, 新算法避免了两个相近数的相减。新算法避免了两个相近数的相减。上页上页下页下页例例3 计算计算 解解 用五位十进制计算机进行计算用五位十进制计算机进行计算:0.1被大数被大数“吃掉吃掉”了了,从而从而有有三、防止大数三、防止大数 “吃掉吃掉” 小数小数 10001524920.152492i 555524920.10.52492 100.000001 100.52492 10 10001524920.1i 上页上页下页下页如改为如改为 0.1 就没有被吃掉。就没有被吃掉。 这也

18、是构造算法时要注意的问题这也是构造算法时要注意的问题, 避免重要的参数避免重要的参数被吃掉。被吃掉。100010.15249210052492i 5550.01 100.52492 100.52502 105250510001524920.1i 上页上页下页下页当当| x | y | 时时, 舍入误差会扩大舍入误差会扩大2( *)( *)*()*xyyxxyy 四、避免除数的绝对值远小于被除数的绝对值。四、避免除数的绝对值远小于被除数的绝对值。 例例430.510 的舍入误差均为的舍入误差均为, 而而的舍入误差为的舍入误差为:,则则 7311214100.510151010 xxxx 很小的数

19、作除数有时还会造成计算机的溢出而停机。很小的数作除数有时还会造成计算机的溢出而停机。710 xy*, yx*yx|,yx 上页上页下页下页五、使用数值稳定的算法五、使用数值稳定的算法用分部积分公式得递推用分部积分公式得递推公式公式:近似值近似值 In* 的递推公式的递推公式: In* =1-nIn-1* 例例5110,0,1,2,nxnIx edxn 1110001*0.6321xIedxeI In=1-nIn-1 在运算过程中在运算过程中,舍入误差能控制在某个范围内的算法舍入误差能控制在某个范围内的算法称为数值稳定的算法称为数值稳定的算法,否则就称为不稳定的算法否则就称为不稳定的算法. e(

20、In* ) = - n e( In-1* ), 用四位有效数字计算用四位有效数字计算:误差误差e( In* )的递推公式的递推公式:上页上页下页下页于是于是I7* , I8* 与精确值已经面目全非。与精确值已经面目全非。n精确值精确值 In 近似值近似值In*n精确值精确值 In 近似值近似值In*012340.632120.367870.264240.207270.170890.63210.36780.26420.20740.1704567890.145530.126800.112380.100930.091610.14080.11200.2180-0.72807.5520算法一算法一 In =1-nIn-1 ,100*10.6321IeI 代入得下表代入得下表 110,0,1,2,nxnIx edxn 上页上页下页下页由于计算由于计算I0有误差有误差 不计中间再产生的舍入误差不计中间再产生的舍入误差 |e(In*