《数值分析第1章数值分析与科学计算引论.ppt》由会员分享，可在线阅读，更多相关《数值分析第1章数值分析与科学计算引论.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2023/5/20数值分析与科学计算引论1第第1 1章章 数值分析与科学计算引论数值分析与科学计算引论&数值分析的对象、作用与特点数值分析的对象、作用与特点&数值计算的误差数值计算的误差&数值计算的数值计算的误差定性分析与避免误差危害误差定性分析与避免误差危害&数值计算中算法设计的技术数值计算中算法设计的技术2023/5/20数值分析与科学计算引论21.1 数值分析的对象、作用与特点数值分析的对象、作用与特点1.1.1 研究对象与作用研究对象与作用计算数学计算数学根据实际问题的数学模型提出问题求解的数值计算方法，根据实际问题的数学模型提出问题求解的数值计算方法，并对方法进行理论分析和软件实现并
2、对方法进行理论分析和软件实现.1.1.2 特点特点算法能在计算机上实现，并有好的计算复杂性；算法能在计算机上实现，并有好的计算复杂性；面向计算机，提供切实可行的有效算法；面向计算机，提供切实可行的有效算法；有可靠的理论分析，能达到精度要求，算法的收敛性与数有可靠的理论分析，能达到精度要求，算法的收敛性与数 值稳定性，值稳定性，算法的算法的误差分析；误差分析；通过数值实验通过数值实验 证明算法行之有效。证明算法行之有效。计算机上实现数值计算，解决实际问题计算机上实现数值计算，解决实际问题.1.1.3 实际应用实际应用2023/5/20数值分析与科学计算引论31.2 数值计算的误差数值计算的误差
3、误差的来源与分类误差的来源与分类模型误差模型误差在将实际问题归结为数学模型时，需要对问在将实际问题归结为数学模型时，需要对问题作一定的简化和假设。题作一定的简化和假设。观测误差观测误差 数学模型中需要用到的一些系数、初值等数学模型中需要用到的一些系数、初值等常数来自于测量仪器或统计资料，由于客观条件和仪器精常数来自于测量仪器或统计资料，由于客观条件和仪器精度的限制不可避免有误差。度的限制不可避免有误差。方法误差方法误差 (截断误差截断误差)模型的准确解模型的准确解与用与用数值方法求数值方法求得的近似解得的近似解之间的误差称为之间的误差称为“截断误差截断误差”。舍入误差舍入误差在上机实际计算时，
4、由于计算机对所运算的在上机实际计算时，由于计算机对所运算的对象按机器字长四舍五入而产生的最终计算解与模型的准对象按机器字长四舍五入而产生的最终计算解与模型的准确解之间的误差。确解之间的误差。实际算法实际算法:有限、有限、四则运算化四则运算化（理论计算误差）（理论计算误差）2023/5/20数值分析与科学计算引论4误差的产生误差的产生实际问题实际问题数学模型数学模型建建 模模模型模型误差误差观测观测误差误差数值方法数值方法数值解数值解离散离散截断截断误差误差计算计算舍入舍入误差误差实例实例2023/5/20数值分析与科学计算引论5大家一起猜大家一起猜？11/e将将 作作Taylor展开后再积分展
5、开后再积分S4R4取取则则称为称为截断误差截断误差|舍入误差舍入误差|=0.743 由截去部分由截去部分引起引起由留下部分由留下部分引起引起例例1 1近似计算近似计算解解：2023/5/20数值分析与科学计算引论61.2.2 误差与有效数字误差与有效数字 绝对误差绝对误差 /*absolute error*/其中，其中，x 准确值，准确值，x*x的近似值的近似值，例如：，例如：上常记为上常记为，称为，称为绝对误差限绝对误差限，一般地，一般地，的上限记为的上限记为误差绝对值不能超过某个正数误差绝对值不能超过某个正数工程工程注注注注：e*e*理论上讲是唯一确定的，可能取正理论上讲是唯一确定的，可能
6、取正理论上讲是唯一确定的，可能取正理论上讲是唯一确定的，可能取正，也可能取负。也可能取负。也可能取负。也可能取负。e*0 时，时，x*称为强近似值，称为强近似值，e*0 0 不唯一，当然不唯一，当然不唯一，当然不唯一，当然 越小越具有参考价值。越小越具有参考价值。越小越具有参考价值。越小越具有参考价值。通常是不知道的通常是不知道的根据具体情况根据具体情况，可，可事先事先估计估计出误差的范围出误差的范围误差绝对值的误差绝对值的“上界上界”，或称，或称“误差限误差限”，即有，即有 2023/5/20数值分析与科学计算引论7例例2 设设=3.1415926 近似值近似值 A=3.14,它的绝对误差是
7、它的绝对误差是 0.0015926，有，有 -A=0.0015926 0.002=0.2 10-2可见，可见，绝对误差限绝对误差限*不是唯一的，但不是唯一的，但*越小越好越小越好,例例3 又近似值又近似值 A =3.1416=3.1416，它的绝对误差是，它的绝对误差是0.00000740.0000074，有，有|-A|=0.0000074 0.000008=0.8 10-5例例4 又近似值又近似值 A=3.1415=3.1415，它的绝对误差是，它的绝对误差是0.00009260.0000926，有，有|-A A|=0.0000926|=0.0000926 0.0001=0.10.0001=
8、0.1 1010-3-3绝对误差限并不能很好地反映近似值的好坏，绝对误差限并不能很好地反映近似值的好坏，x*=10，x*=1，y*=10000，y*=5虽然虽然 y*是是 x*的的5倍，但在倍，但在10000内差内差5显然比显然比10内差内差1好。好。2023/5/20数值分析与科学计算引论8相对误差相对误差/*relative error*/x*的的相对误差限相对误差限注：注：注：注：从从从从 的定义可见，的定义可见，的定义可见，的定义可见，实际上被实际上被实际上被实际上被偷换偷换偷换偷换成了成了成了成了 ，而后才考，而后才考，而后才考，而后才考察其上限。那么这样的偷换是否察其上限。那么这样
9、的偷换是否察其上限。那么这样的偷换是否察其上限。那么这样的偷换是否合法合法合法合法？严格的说法是，严格的说法是，严格的说法是，严格的说法是，与与与与 是否反映了是否反映了是否反映了是否反映了同一数量级同一数量级同一数量级同一数量级的误差的误差的误差的误差？关于此问题的详细讨论可见教材关于此问题的详细讨论可见教材关于此问题的详细讨论可见教材关于此问题的详细讨论可见教材p5p5。实际计算中，相对误差通常取为：实际计算中，相对误差通常取为：2023/5/20数值分析与科学计算引论9例例5解解结论结论?俗称俗称“好坏好坏”、“多少多少”是相是相对的对的 近似数的相对误差是近似数精确度的基本度量近似数的
10、相对误差是近似数精确度的基本度量,一一个近似数个近似数 的相对误差越小，则近似数越精确。的相对误差越小，则近似数越精确。结论结论 设设 ，估计近似数估计近似数 的绝对误差与相对误差。的绝对误差与相对误差。但但 是是 的一个的一个好的近似好的近似，不是不是 的的好的近似好的近似。2023/5/20数值分析与科学计算引论10有效数字有效数字例例6问：问：有几位有效数字？请证明你的结论。有几位有效数字？请证明你的结论。43若近似值若近似值 x*的误差限是的误差限是某一位的半个单位某一位的半个单位,该位到该位到 x*的第一位的第一位非零数字共有非零数字共有 n 位位,就说就说 x*有有 n 位有效数字
11、位有效数字.证明证明注注注注：如果如果x*是由是由x四舍五入得到的近似值，则四舍五入得到的近似值，则x*的每一位的每一位都是有效数字。当都是有效数字。当x已知已知 时，可根据需要产生每位皆有效时，可根据需要产生每位皆有效的近似值。的近似值。有有 n 位有效数字位有效数字的的x*可表示为可表示为2023/5/20数值分析与科学计算引论11有效数字与相对误差的关系有效数字与相对误差的关系 有效数字有效数字 相对误差限相对误差限已知已知 x*有有 n 位位有效数字有效数字，则其，则其相对误差相对误差为为 相对误差限相对误差限 有效数字有效数字已知已知 x*的的相对误差相对误差满足满足可见可见 x*至
12、少至少有有 n 位位有效数字有效数字。2023/5/20数值分析与科学计算引论12假设假设 *取到取到 n 位有效数字，则其相对误差上限满足位有效数字，则其相对误差上限满足要保证其相对误差限小于要保证其相对误差限小于0.001%，只要保证其上限满，只要保证其上限满足足已知已知 a1=3，则从以上不等式可解得，则从以上不等式可解得 n 6 log6，即，即 n 6，应取，应取 *=3.14159。例例7 为使为使 的相对误差小于的相对误差小于0.001%,至少应取几位有效数字？至少应取几位有效数字？解解2023/5/20数值分析与科学计算引论13问题问题：这些这些公式的形式公式的形式有什么有什么
13、特点特点？使你想到什么？使你想到什么？代数运算的误差估计代数运算的误差估计1.2.3 数值运算的误差估计数值运算的误差估计2023/5/20数值分析与科学计算引论14 函数值的误差估计函数值的误差估计问题：问题：对于对于 y =f(x)，若用，若用 x*取代取代 x，将对，将对y 产生什么影响？产生什么影响？由函数的由函数的泰勒展开式泰勒展开式函数值的函数值的相对误差相对误差（限限），有：），有：2023/5/20数值分析与科学计算引论15相对误差条件数相对误差条件数 f 的条件数在某一点是的条件数在某一点是小小大大，则称，则称 f 在该点是在该点是好条件的好条件的 坏坏条件的条件的。问题：问
14、题：若若的近似值为的近似值为则则 的近似值的近似值 于是函数值于是函数值 的误差的误差2023/5/20数值分析与科学计算引论161.3 误差定性分析与避免误差危害误差定性分析与避免误差危害 F 一个工程或科学计算问题往往要运算千万次，由于每步运算一个工程或科学计算问题往往要运算千万次，由于每步运算都有误差，如果每步都做误差分析是不可能的，也不科学都有误差，如果每步都做误差分析是不可能的，也不科学.F 误差积累有正有负，绝对值有大有小，都按最坏情况估计误误差积累有正有负，绝对值有大有小，都按最坏情况估计误差限得到的结果比实际误差大得多，这种保守的误差估计不反差限得到的结果比实际误差大得多，这种
15、保守的误差估计不反映实际误差积累映实际误差积累.概率分析法概率分析法威尔金森威尔金森(Wilkinson)的的向后误差分析法向后误差分析法穆尔穆尔(Moore)的的区间分析法区间分析法.1.3.1 舍入误差的定量分析方法舍入误差的定量分析方法2023/5/20数值分析与科学计算引论17例例8 计算计算 公式一公式一:注意此公式注意此公式精确精确成成立立记为记为则初始误差则初始误差?!发生了发生了什麽什麽?!1.3.2 数值稳定性与误差的传播数值稳定性与误差的传播2023/5/20数值分析与科学计算引论18考察第考察第n步的误差步的误差我们有责任改变。我们有责任改变。造成这种情况的是造成这种情况
16、的是不稳定的算法不稳定的算法迅速积累迅速积累,误差呈递增走势误差呈递增走势.可见初始的小扰动可见初始的小扰动 公式二公式二:注意此公式与注意此公式与公式公式一一在理论上在理论上等价等价。方法：方法：先估计一个先估计一个IN,再反推要求的再反推要求的In(n N)。可取可取2023/5/20数值分析与科学计算引论19取取 我们很幸运！我们很幸运！2023/5/20数值分析与科学计算引论20考察反推一步的误差：考察反推一步的误差：以此类推，对以此类推，对 n N 有：有：误差逐步递减误差逐步递减,这样的算法称为这样的算法称为稳定的算法稳定的算法。舍入误差的定性分析舍入误差的定性分析 一个算法如果输
17、入数据有扰动（即误差），而计算过程中一个算法如果输入数据有扰动（即误差），而计算过程中舍入误差不增长舍入误差不增长,则称此算法是则称此算法是数值稳定数值稳定的，否则此算法就称为的，否则此算法就称为不稳定不稳定的。的。数值稳定性数值稳定性/*Numerical Stability*/2023/5/20数值分析与科学计算引论21病态问题病态问题 输入数据的微小扰动（即误差），引起输出数据（即问输入数据的微小扰动（即误差），引起输出数据（即问题解）的相对误差很大的数学问题。题解）的相对误差很大的数学问题。（3.3）称为称为计算函数值问题计算函数值问题的的条件数条件数.计算函数值计算函数值 时，时，若
18、若 有扰动有扰动 ，相对误差为相对误差为 ，函数值函数值 的相对误差为的相对误差为相对误差比值相对误差比值1.3.2 病态问题与条件数病态问题与条件数病态问题举例病态问题举例计算函数值问题的条件数计算函数值问题的条件数很大的问题很大的问题病态问题病态问题2023/5/20数值分析与科学计算引论22 函数函数它表示相对误差可能放大它表示相对误差可能放大 倍倍.如如 ，有有 ，自变量相对误差为自变量相对误差为 ，函数值相对误差为函数值相对误差为 ，一般情况下一般情况下,条件数条件数 就认为是病态，就认为是病态，越大，病态越大，病态越严重越严重.的条件数的条件数若取若取这时问题可以认为是病态的这时问
19、题可以认为是病态的.计算函数值问题举例计算函数值问题举例2023/5/20数值分析与科学计算引论23避免相近二数相减。避免相近二数相减。举例：举例：a1=0.12345，a2=0.12346，各有，各有5位有效数字。位有效数字。而而 a2 a1=0.00001，只剩下，只剩下1位有效数字。位有效数字。几种经验性避免方法：几种经验性避免方法：当当|x|1 时：时：避免小分母避免小分母:分母小会造成舍入误差增大。分母小会造成舍入误差增大。选用稳定的算法。选用稳定的算法。1.3.3 避免误差危害的若干原则避免误差危害的若干原则2023/5/20数值分析与科学计算引论24避免大数避免大数吃吃小数小数举
20、例：举例：用单精度计算用单精度计算 的根。的根。精确解为精确解为 算法算法1 1：利用求根公式利用求根公式在计算机内，在计算机内，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大数大数吃吃小数小数 x 3.81574 y 0.000
21、1=38157.4 x 3.81574 y+y 0.0001+0.00001=34688.52023/5/20数值分析与科学计算引论25?算法算法2：先取先取 再利用再利用求和时求和时从小到大从小到大相加，可使和的误差减小。相加，可使和的误差减小。举例：举例：按从小到大、以及从大到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算1+2+3+40+109先化简再计算，减少步骤，避免误差积累。先化简再计算，减少步骤，避免误差积累。一般来说，计算机处理下列运算的速度为一般来说，计算机处理下列运算的速度为?如计算多项式的值用秦九韶法如计算多项式的值用秦九韶法(P11).2023/5/20数值分析
22、与科学计算引论26算法设计的好坏算法设计的好坏影响计算结果的精度，好算法大量节省计算时间影响计算结果的精度，好算法大量节省计算时间.1.4 数值计算中算法设计的技术数值计算中算法设计的技术算法设计的一个重要原则算法设计的一个重要原则减少运算次数减少运算次数1.4.1 多项式求值的秦九韶算法多项式求值的秦九韶算法设给定设给定 次多项式次多项式求求 处的值处的值 .直接计算直接计算 再相加再相加加法次数加法次数减少计算量，减少误差减少计算量，减少误差?多项式求值多项式求值乘法次数乘法次数 计计算算量量2023/5/20数值分析与科学计算引论27记记（4.1）则则 .求求 在在 点的值点的值.其中其
23、中秦九韶算法秦九韶算法J计算量计算量加法次数加法次数乘法次数乘法次数 J优点优点由由（4.1）式式2023/5/20数值分析与科学计算引论28对对 求导得求导得故故 .则则（4.1）其中其中计算计算 的秦九韶算法的秦九韶算法2023/5/20数值分析与科学计算引论29此处此处 例例8 设设 ，用秦九韶算法求，用秦九韶算法求 和和 的值的值.用（用（4.1）和（）和（4.2）式构造出计算表格（）式构造出计算表格（1-2）解解2023/5/20数值分析与科学计算引论30迭代法举例迭代法举例开方运算开方运算迭代法迭代法数值计算普遍使用的重要方法数值计算普遍使用的重要方法 迭代法与开方求值迭代法与开方
24、求值?迭代法的构造迭代法的构造 假定假定 ，求，求 等价于解方程等价于解方程（4.3）先给定一个初始近似先给定一个初始近似 ，令，令 ，是一个是一个校正量，称为增量，校正量，称为增量，按同一公式重复计算逐次逼近真值的方法按同一公式重复计算逐次逼近真值的方法即即舍去高阶项舍去高阶项 ，则得，则得即即2023/5/20数值分析与科学计算引论31（4.4）这里这里 不是的真值，但它是真值不是的真值，但它是真值 的的进一步近似进一步近似，重复以，重复以上过程进行迭代上过程进行迭代它可逐次求得它可逐次求得 若若 则则 ，容易证明序列，容易证明序列 对任何对任何 均收敛均收敛1 1次加法次加法 1 1次除
25、法次除法 1 1次移位次移位 例例9 用迭代法（用迭代法（4.44.4）求）求 ，取，取 若计算精确到若计算精确到 ，由，由（4.4）式可求得式可求得迭代迭代3 3次误差即小于次误差即小于 解解 2023/5/20数值分析与科学计算引论321.4.3 以直代曲与化整为以直代曲与化整为“零零”数值计算：将非线性问题线性化。数值计算：将非线性问题线性化。圆周率圆周率 的计算是古代数学的一个光辉成就，充分体的计算是古代数学的一个光辉成就，充分体现了以直代曲化整为现了以直代曲化整为“零零”的思想的思想.图图1-11-1几何：在局部范围内用直线近似曲线。几何：在局部范围内用直线近似曲线。2023/5/2
26、0数值分析与科学计算引论33方程求根的牛顿迭代法方程求根的牛顿迭代法 求函数方程求函数方程 的根的根图1-2以直代曲相当于用切线方程以直代曲相当于用切线方程的根的根 近似近似 ，从而，从而（4.5）牛顿迭代法牛顿迭代法以直代曲举例以直代曲举例几何上表现为平面上的一条曲线几何上表现为平面上的一条曲线它与它与 轴交点的横坐标即为方程的根轴交点的横坐标即为方程的根 .2023/5/20数值分析与科学计算引论34（4.6）定积分计算的梯形公式与复合梯形公式定积分计算的梯形公式与复合梯形公式梯形公式梯形公式以直代曲以直代曲图图1-3复合梯形公式复合梯形公式化整为化整为“零零”将积分区间分割为小区间将积分
27、区间分割为小区间其中其中在每个小区间在每个小区间 上用梯形公式计算，再上用梯形公式计算，再求和，得到求和，得到（4.7）2023/5/20数值分析与科学计算引论35 加权平均的松弛技术加权平均的松弛技术 松弛技术是计算方法中提高收敛速度的有效方法，设松弛技术是计算方法中提高收敛速度的有效方法，设量量 为精确值，为精确值，与与 为为 的两个近似值，其加权的两个近似值，其加权平均为平均为其中其中 为为松弛因子松弛因子.通常通常 是比是比 更接近真值更接近真值 ，要求，要求 比比 更接近更接近 可选可选 .2023/5/20数值分析与科学计算引论36作业作业：P19:1,2,5,7,11,14 2023/5/20数值分析与科学计算引论37练习练习