数值分析总复习.ppt
《数值分析总复习.ppt》由会员分享,可在线阅读,更多相关《数值分析总复习.ppt(88页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、序 言数值计算方法数值计算方法v能够做什么?能够做什么?v课程的特点、方法及意义?课程的特点、方法及意义?计算机解决实际问题的步骤计算机解决实际问题的步骤建立数学模型建立数学模型选择数值方法选择数值方法编写程序编写程序上机计算上机计算5在计算机上是否根据数学公式编在计算机上是否根据数学公式编程就能得到正确结果程就能得到正确结果?研究例子:求解线性方程组研究例子:求解线性方程组其准确解为其准确解为x1=x2=x3=1如把方程组的系数舍入如把方程组的系数舍入成两位有效数字成两位有效数字解为解为 x1 6.222.x238.25 x333.65.5计算机运算速度极快是否就可以计算机运算速度极快是否就
2、可以不考虑算法的效率不考虑算法的效率?用Grammer法则求解n元线性方程组需计算需计算 n+1个个 n 阶行列式阶行列式用定义计算,需用定义计算,需n!(n-1)(n+1)次次乘法乘法当当 n20时,总次数为时,总次数为9.710 2010亿次秒速度,需亿次秒速度,需300多年。多年。数值分析研究的对象数值分析研究的对象 计算计算方法方法又称又称:计算计算数学、数值方数学、数值方法、数值分析等。法、数值分析等。计算计算方法方法的分支有:的分支有:最优化方法、最优化方法、计算几何、计算概率统计等。计算几何、计算概率统计等。研究数值方法的研究数值方法的设计设计、分析分析和和有有关理论关理论基础与
3、基础与软件实现软件实现。包括包括:方法方法的收敛性、稳定性及误差分析,及效的收敛性、稳定性及误差分析,及效率问题。率问题。计算方法的内容计算方法的内容F连续系统的离散化连续系统的离散化F离散性方程的数值求解离散性方程的数值求解计算机能做什么?计算机能做什么?一般编程方法只能对具一般编程方法只能对具有一定数位的数进行四则运算有一定数位的数进行四则运算计计算算方法:方法:怎样把数学问题的求解运算,怎样把数学问题的求解运算,归结为对有限数位的数的四则运算归结为对有限数位的数的四则运算课课 程程 特特 点点1.面向计算机,根据计算机特点提供实际面向计算机,根据计算机特点提供实际可行的有效算法。可行的有
4、效算法。2.有可靠的理论分析,能任意逼近并达到有可靠的理论分析,能任意逼近并达到精度要求,对近似算法要保证收敛性和数精度要求,对近似算法要保证收敛性和数值稳定性,还要进行误差分析值稳定性,还要进行误差分析3.要有好的计算复杂性要有好的计算复杂性(节省时间与存储节省时间与存储空间空间)。4.要有数据实验,证明方法行之有效。要有数据实验,证明方法行之有效。主要方法简介主要方法简介1.离散变量与离散化离散变量与离散化 有些函数本来就是对自变量的离散值给出有些函数本来就是对自变量的离散值给出的,如实验数据表;但象的,如实验数据表;但象y=sinx 或或 y=ln x 等等函数,本身是连续的,人们却把它
5、们列成表,函数,本身是连续的,人们却把它们列成表,其中的其中的x已经不再看成连续变量,而是每隔一已经不再看成连续变量,而是每隔一定步长就跳跃取一个值的离散变量了。定步长就跳跃取一个值的离散变量了。典型方法:典型方法:微分方程数值解、数值积分微分方程数值解、数值积分 反过来,也可以把离散的变量反过来,也可以把离散的变量“联成联成”连连续变量的函数,如续变量的函数,如“插值、最小二乘法插值、最小二乘法”。2.函数逼近函数逼近 用简单函数用简单函数 y(x)近似代替函数近似代替函数 f(x),称为函称为函数逼近。两者的差数逼近。两者的差E(x)=f(x)-y(x)叫做逼近的叫做逼近的误差或余项。在数
6、值分析中误差或余项。在数值分析中,所谓的简单函数所谓的简单函数,主要是指可用主要是指可用“四则运算四则运算”进行计算的函数,进行计算的函数,一般是有理函数式;最简单的是多项式。一般是有理函数式;最简单的是多项式。除了选择逼近函数类外,逼近方法的选择除了选择逼近函数类外,逼近方法的选择同样重要。同样重要。常用的典型方法常用的典型方法:插值法插值法 一致逼近一致逼近 均方逼近均方逼近3.迭代法迭代法 重要方法之一。重要方法之一。除了用于求方程的根及方程组的解之外,除了用于求方程的根及方程组的解之外,也是求解微分方程的主要方法。也是求解微分方程的主要方法。收敛速度是衡量迭代法的一个重要准则,收敛速度
7、是衡量迭代法的一个重要准则,而迭代一步所用的计算量也常作为一个衡量标而迭代一步所用的计算量也常作为一个衡量标准,但二者得到的结果往往是矛盾的。准,但二者得到的结果往往是矛盾的。计算机中数的计算特点计算机中数的计算特点:1.加法先对阶加法先对阶,后运算后运算,再舍入再舍入2.乘法先运算乘法先运算,再舍入再舍入3.不在计算机数系中的数做四舍五入处理不在计算机数系中的数做四舍五入处理例如例如:在四位浮点十进制数的计算机上计算在四位浮点十进制数的计算机上计算1+104 解解:1+104=0.1000 101+0.1000 105 =0.00001 105+0.1000 105 (对阶对阶)=0.100
8、01 105 =0.1000 105=1041、模型误差、模型误差2、观测误差、观测误差3、截断误差截断误差4、舍入误差舍入误差5误误 差差 的的 来来 源源绝对误差:绝对误差:e=x*x ,x*是准确数是准确数 x是近似数是近似数绝对误差限绝对误差限 :|e|=|x*x|常表示为常表示为x=x*或或 x*x x*+相对误差:相对误差:er=(x*x)/x*,x*是准确数是准确数,x是近似数是近似数相对误差限相对误差限 r:|er/x*|=|x*x|/|x*|r相对误差比绝对误差更能反映准确数与近似数的差异相对误差比绝对误差更能反映准确数与近似数的差异例例:考虑考虑 1.x*=10,x=11
9、e=1 er=0.1 2.x*=1000,x=1001 e=1 er=0.001误误 差差 定定 义义有有 效效 数数 字字 用四舍五入得到的数都是有效数字。用四舍五入得到的数都是有效数字。有效数字越多有效数字越多,误差越小误差越小,计算结果计算结果越精确。越精确。如果|e|=|x*x|0.5 10-k 称近似数称近似数 x 准确到小数点后第准确到小数点后第k位位,从这小数点后第从这小数点后第k位数字直到最左边非位数字直到最左边非零数字之间的所有数字都称为有效数零数字之间的所有数字都称为有效数字字.12/30/202215四则运算的误差四则运算的误差绝对误差:绝对误差:e=x*x=x dx 相
10、对误差:相对误差:er=(x*x)/x*dx/x*=lnx利用这个关系可以讨论四则运算的误差和函数的误差利用这个关系可以讨论四则运算的误差和函数的误差定理定理:(有效数字与相对误差限的关系有效数字与相对误差限的关系)若近似数若近似数 x=0.a1 a2a t10m()有有n位位有有效数字,则其相对误差限为:效数字,则其相对误差限为:r(12a 1)10(n-1)反之,若反之,若 x 的相对误差限的相对误差限 r 1(2a 1+1)10(n-1)则则 x 至少有至少有n位有效数字。位有效数字。问题的敏感性问题的敏感性 对于一个问题,所使用的数据集记作对于一个问题,所使用的数据集记作D,所得的所得
11、的解集为解集为S,于是问题简记为于是问题简记为Sf(D)。然而在实际中,使用的数据为然而在实际中,使用的数据为D*且有一定误差,且有一定误差,从而所得解集从而所得解集S*f(D*)也将不会精确地为也将不会精确地为S(不考虑不考虑输入误差及公式误差输入误差及公式误差)。一个重要的。一个重要的问题问题问题问题是:当数据是:当数据集集D*很接近精确值很接近精确值D时,其解集是否也一定很接近精时,其解集是否也一定很接近精确解确解S呢?这就是呢?这就是“解对数据的敏感性解对数据的敏感性”问题。问题。定义定义定义定义:对问题:对问题 f(*),如,如数据集非常接近精确值数据集非常接近精确值D时,相应解集时
12、,相应解集S*f(D*)也非常接近精确解也非常接近精确解S f(D),则称问题则称问题 f(*)是是良态良态良态良态的,或的,或解对数据不敏感解对数据不敏感解对数据不敏感解对数据不敏感;否则,;否则,称称f(*)是是病态病态病态病态的,或的,或解对数据敏感解对数据敏感解对数据敏感解对数据敏感。描述问题的敏感性,常采用描述问题的敏感性,常采用“条件数条件数条件数条件数”这一概念。这一概念。对不同的问题,条件数的具体定义及计算也不尽一样。对不同的问题,条件数的具体定义及计算也不尽一样。作为实例,后面将讨论求解线性方程组问题。作为实例,后面将讨论求解线性方程组问题。例例例例:多项式:多项式p(x)=
13、(x-1)(x-2)(x-20)=x 20-210 x 19+显然,它有显然,它有20个精确零点个精确零点1、2、3、20。但若其系。但若其系数有一微小变化,其零点变化如何呢?数有一微小变化,其零点变化如何呢?仅考虑仅考虑 x 19 的系数变化的系数变化 2-23 10-7,即考察多项式即考察多项式p(x)+2-23x 19。现用现用2,t90的浮点系统的浮点系统(双精度双精度)求求其零点,其零点,(结果略结果略)将产生将产生10个复数零点,其中有两个离个复数零点,其中有两个离开实轴的距离超过开实轴的距离超过2.8。需要指出,这种变化并不是由舍入误差引起,也不需要指出,这种变化并不是由舍入误差
14、引起,也不是计算公式造成,而是由问题本身对系数的敏感性决定是计算公式造成,而是由问题本身对系数的敏感性决定的。的。求高阶多项式的零点问题往往是病态的求高阶多项式的零点问题往往是病态的。对于良态问题,原则上讲可以求得满足精度要求对于良态问题,原则上讲可以求得满足精度要求的解。但输入误差不可避免,因而还应保证所使用的的解。但输入误差不可避免,因而还应保证所使用的算法不会扩展误差在计算结果中的影响,否则计算结算法不会扩展误差在计算结果中的影响,否则计算结果仍不可信。果仍不可信。定义定义定义定义:对于一个由多阶段运算组成的算法,若每:对于一个由多阶段运算组成的算法,若每经过一个阶段的运算,原有的初值误
15、差或舍入误差的经过一个阶段的运算,原有的初值误差或舍入误差的影响不增长,则称这个算法是影响不增长,则称这个算法是数值稳定的数值稳定的数值稳定的数值稳定的。算法的数值稳定性算法的数值稳定性例例例例1 1:用:用5位有效数计算位有效数计算e 5.5 利用利用Taylor展式,第展式,第26项后,每项的绝对值项后,每项的绝对值0且且。计算结果不正。计算结果不正确。算法不是数值稳定的。确。算法不是数值稳定的。可以改变算法:可以改变算法:显然不会造成误差增长。显然不会造成误差增长。由于由于 ,可见,当,可见,当n增大增大时,时,y n 趋于趋于 ,可取,可取算出算出y 80.0185,y 70.0213
16、,y 60.0243,y 50.0284,y 40.0343,y 30.0431,y 20.0581,y 10.0884,y 00.182 一、防止相近的两数相减一、防止相近的两数相减 (会耗失许多有效数字会耗失许多有效数字,可以用数学公式化简后再做可以用数学公式化简后再做)。例例例例1 1:各有五位有效数字的各有五位有效数字的23.034与与22.993相减。相减。23.034 22.993=0.041 0.041只只有有两两位位有有效效数数字字,有有效效数数字字的的耗耗失失,说说明明准准确确度度减减小小。因因此此,在在计计算算时时需需要要加加工工计计算算公公式式,以以免免这这种种情情况发生
17、。况发生。数值计算中值得注意的问题数值计算中值得注意的问题例例例例2 2:当当x较大时较大时,计算计算二、防止大数吃小数二、防止大数吃小数.当当两两个个绝绝对对值值相相差差很很大大的的数数进进行行加加法法或或减减法法运运算算时时,绝绝对对值值小小的的数数有有可可能能被被绝绝对对值值大大的的数数“吃吃掉掉”从从而而引引起起计算结果很不可靠。计算结果很不可靠。例例例例:求一元二次方程求一元二次方程x2(108+1)x+108=0 的实数根的实数根.采采用用因因式式分分解解法法,很很容容易易得得到到两两个个根根为为x1=108,x2=1.如如采采用用字字长长为为16位位的的单单精精度度计计算算机机来
18、来计计算算,求求得得根根为为x1108 ,x20。(怎样计算可得较好的结果怎样计算可得较好的结果?)两两者者结结果果不不同同,因因为为计计算算机机计计算算时时做做加加减减法法要要“对对阶阶”,“对对阶阶”的的结结果果使使大大数数吃吃掉掉了了小小数数,产产生生了了误误差差。为为了了避避免免由由于于上上述述原原因因引引起起的的计计算算结结果果严严重重失失真真,可可以以根根据据一一些些具具体体情情况况,存存在在需需要要把把某某些些算算式式改改写写成成另另一一种种等价的形式。等价的形式。四、注意计算步骤的简化四、注意计算步骤的简化,减小运算次数减小运算次数.简简化化计计算算步步骤骤是是提提高高程程序序
19、执执行行速速度度的的关关键键,它它不不仅可以节省时间,还能减少舍入误差。仅可以节省时间,还能减少舍入误差。例例例例1 1:计算:计算9255 的值,若逐个相乘要用的值,若逐个相乘要用254次乘法,次乘法,但若写成但若写成 9255=9 92 94 98 916 932 964 9128只需做只需做14次乘法运算即可。次乘法运算即可。三、防止接近零的数做除数三、防止接近零的数做除数 分母接近零的数会产生溢出错误,因而产生大分母接近零的数会产生溢出错误,因而产生大的误差,此时可以用数学公式化简后再做。的误差,此时可以用数学公式化简后再做。此外,如果分子分母数量级悬殊太大此外,如果分子分母数量级悬殊
20、太大(分母很分母很小小),同样会造成误差增大。,同样会造成误差增大。方程(组)求解方程(组)求解问题总结问题总结一、主要内容小结一、主要内容小结(一一)方程求根方程求根1.有根判定:介值定理有根判定:介值定理2.初始近似值确定:搜索法初始近似值确定:搜索法(二分法二分法)3.不动点迭代法:不动点迭代法:考察考察f(x)=0,变形构造等价方变形构造等价方程确定迭代函数:程确定迭代函数:x=(x),并由此构造迭代格并由此构造迭代格式:式:xk+1=(xk)4.所产生的序列所产生的序列xk,若收敛则为方程的根。若收敛则为方程的根。5.所构造的迭代函数不同,对应不同的迭代所构造的迭代函数不同,对应不同
21、的迭代法,其收敛性也有很大差异。法,其收敛性也有很大差异。定理一定理一:假定函数假定函数 满足下列条件:满足下列条件:1.对任意对任意 有有 ;(1.1)2.存在正数存在正数 L1,使对任意使对任意 有有 (1.2)则迭代过程则迭代过程 对于任意初值对于任意初值 均收敛于方程均收敛于方程 的根的根 ,且有如下的误差估计式:,且有如下的误差估计式:(1.3)实用中实用中(1.2)式常用式常用 8定义定义定义定义1 1:如果存在:如果存在 的某个邻域的某个邻域 ,使迭代,使迭代格式格式 对于任意初值对于任意初值 均收敛,均收敛,则称迭则称迭代格式代格式 在根在根 邻近具有邻近具有局部收敛性局部收敛
22、性局部收敛性局部收敛性。定理二定理二定理二定理二:设:设 为方程为方程 的根,的根,在在 的邻近连的邻近连续,且续,且 ,则上述迭代格式在则上述迭代格式在 邻近具有局部邻近具有局部收敛性。收敛性。当迭代收敛时,收敛的快慢用当迭代收敛时,收敛的快慢用收敛阶收敛阶收敛阶收敛阶来衡量。来衡量。定义定义定义定义2 2:设迭代格式收敛于:设迭代格式收敛于x*,并记误差为并记误差为若有常数若有常数p0和和c0使得使得 ,则称迭代,则称迭代格式是格式是 p 阶收敛的。阶收敛的。13定理定理定理定理 三三三三:对于迭代过程:对于迭代过程 ,如果如果 在所求根在所求根 的邻近连续,并且的邻近连续,并且 (*)则
23、该迭代过程在点则该迭代过程在点 邻近是邻近是p 阶收敛的。阶收敛的。迭代终止准则:迭代终止准则:114.Newton迭代法迭代法1.若若 ,则至少二次收敛,则至少二次收敛 在一元方程解法中,最有效的是在一元方程解法中,最有效的是Steffensen迭代法和迭代法和Newton法。前者不需要求导数,但法。前者不需要求导数,但不易推广到多元的情形,后者需要计算导数,不易推广到多元的情形,后者需要计算导数,但可直接推广到多元方程组。但可直接推广到多元方程组。(二二)方程组直接解法方程组直接解法1.Gauss消元法消元法2.列列(全全)主元消元法主元消元法3.直接直接LU三角分解三角分解4.直接直接L
24、U三角分解三角分解消元法及三角分解的可行性定理消元法及三角分解的可行性定理(条件条件)定理定理定理定理1 1.矩阵矩阵A的各项顺序主子式均不为的各项顺序主子式均不为0。定理定理定理定理2 2.A对称正定。对称正定。定理定理定理定理3.3.A 为严格对角占优。为严格对角占优。(三三)方程组求解的迭代法方程组求解的迭代法1.Jacobi迭代公式迭代公式2.Gauss-Seidel迭代法迭代法Jacobi迭代和迭代和GS迭代格式可表述为统一形式迭代格式可表述为统一形式:对于其收敛性,我们有如下定理:对于其收敛性,我们有如下定理:定理定理:对任意初始向量对任意初始向量x(0)及任意右端向量及任意右端向
25、量 g,由此产生的迭代向量序列由此产生的迭代向量序列x(k)收敛的充要条件是收敛的充要条件是定理:定理:定理:定理:若若|B|1,则迭代法收敛则迭代法收敛.推论推论推论推论1 1:若若 满足下列条件之一:满足下列条件之一:(1)(2)(3)则迭代法收敛。则迭代法收敛。推论推论推论推论2 2:如果:如果A为严格为严格对角占优阵,或弱对角占优且不对角占优阵,或弱对角占优且不可约,则其可约,则其 Jacobi迭代和迭代和Seidel迭代对任意迭代对任意x(0)都收敛。都收敛。推论推论推论推论3 3:如果:如果A为为对称正定对称正定阵,则其阵,则其 Seidel迭代对任何迭代对任何初始向量初始向量x(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数值 分析 复习
限制150内