《数值分析》》PPT课件.ppt

数数 值值 分分 析析理 学 院刘 秀 娟第第 1 1 章章 绪绪 论论§1.11.1 数值分析的研究对象数值分析的研究对象l数值分析是近代数学的一个重要分支，它是研究数值分析是近代数学的一个重要分支，它是研究各种数学问题的各种数学问题的数值解法数值解法，包括方法的构造和求，包括方法的构造和求解过程的理论分析解过程的理论分析l在电子计算机成为数值计算的主要工具之后，则在电子计算机成为数值计算的主要工具之后，则要求研究适合于计算机使用的数值计算方法，为要求研究适合于计算机使用的数值计算方法，为了更好地说明数值分析的研究对象，我们考察用了更好地说明数值分析的研究对象，我们考察用计算机解决科学计算问题时经历的几个过程：计算机解决科学计算问题时经历的几个过程： 提问：数值分析是做什么用的？提问：数值分析是做什么用的？ 提问：数值分析是做什么用的？提问：数值分析是做什么用的？选择数值选择数值计算方法计算方法程序设计程序设计上机上机计算计算求出结果求出结果构造数构造数学模型学模型实实 际际 问问 题题l任务：数值分析的任务是提供在计算任务：数值分析的任务是提供在计算机上实际可行的，有可靠理论分析、机上实际可行的，有可靠理论分析、计算复杂性好的各种数值计算方法。

计算复杂性好的各种数值计算方法l特点：数值分析是与计算机及其它科特点：数值分析是与计算机及其它科学有密切关系的数学课程，因此它即学有密切关系的数学课程，因此它即具有纯数学的高度抽象性与严密科学具有纯数学的高度抽象性与严密科学性的特点，同时又具有应用广泛性与性的特点，同时又具有应用广泛性与数值试验的高度技术性，除此之外，数值试验的高度技术性，除此之外，它还有以下几个基本特点：它还有以下几个基本特点： 1、采用、采用“构造性构造性”方法；方法； 2、采用、采用“离散化离散化”方法；方法； 3、采用、采用“递推化递推化”方法；方法； 4、采用、采用“近似代替近似代替”方法等等方法等等• 研究内容研究内容l线性方程组的数值解线性方程组的数值解l矩阵特征值与特征向量计算矩阵特征值与特征向量计算l非线性方程的数值解非线性方程的数值解l数值逼近数值逼近l数值积分数值积分l常微、偏微的数值解常微、偏微的数值解• 研究方法研究方法l理论分析理论分析l算法分析算法分析l误差分析误差分析l收敛性分析收敛性分析l收敛速度收敛速度 §1.2 1.2 误差误差知识与算法知识知识与算法知识1.2.1 误差的来源与分类误差的来源与分类 在工程技术的计算中，估计计算结在工程技术的计算中，估计计算结果的精确度是十分重要的工作，而影响果的精确度是十分重要的工作，而影响精确度的是各种各样的误差。

误差的来精确度的是各种各样的误差误差的来源是复杂的，但主要有以下四种：源是复杂的，但主要有以下四种：Ø 从实际问题中抽象出数学模型从实际问题中抽象出数学模型 —— 模型误差模型误差 ( Modeling Error )Ø 通过测量得到模型中参数的值通过测量得到模型中参数的值 —— 观测误差观测误差 ( Measurement Error )Ø 求近似解求近似解 —— 方法误差方法误差 (截断误差截断误差 ( Truncation Error ) )Ø 机器字长有限机器字长有限 —— 舍入误差舍入误差 ( Roundoff Error )Ø模型误差模型误差l处理实际问题时，要建立数学模型，通常模型只处理实际问题时，要建立数学模型，通常模型只是近似的由此产生的是近似的由此产生的数学模型解数学模型解与与实际问题的实际问题的解解 之间的误差叫之间的误差叫模型误差模型误差l例如例如 是实际问题的解，而若数学模型的解是是实际问题的解，而若数学模型的解是由此产生的误差叫作模型误差由此产生的误差叫作模型误差Ø观测误差观测误差l数学模型中包含某些变量，如时间、长度、电压数学模型中包含某些变量，如时间、长度、电压等，它们一般是通过观测来获得。

由于观测得到等，它们一般是通过观测来获得由于观测得到的数据与实际数据之间有误差，这种误差叫的数据与实际数据之间有误差，这种误差叫观测观测观测观测误差Ø截断误差截断误差l求解数学模型所用的数值计算方法，如果是一种求解数学模型所用的数值计算方法，如果是一种近似的方法，只能得到模型的近似解，由此产生近似的方法，只能得到模型的近似解，由此产生的误差称为的误差称为截断误差截断误差截断误差截断误差或或方法误差方法误差方法误差方法误差Ø舍入误差舍入误差l由于计算机的字长有限，参加运算的数据及其由于计算机的字长有限，参加运算的数据及其运算结果在计算机中存放会产生误差这种误运算结果在计算机中存放会产生误差这种误差叫差叫舍入误差舍入误差或或计算误差计算误差l例如例如 在在 16 位微机上计算，单精度实数存放仅有位微机上计算，单精度实数存放仅有 7 位有效数字在其上运算，会有位有效数字在其上运算，会有1   3   0.333 333 3, (1.000 002)2  1.000 004   0,后者的准确结果是后者的准确结果是 4  10 12大家一起猜大家一起猜？？11 / e解法之一解法之一：将将 作作Taylor展开后再积分展开后再积分S4R4 ( Remainder )取取则则称为称为截断误差截断误差 ( Truncation Error ).| 舍入舍入误差误差 ( Roundoff Error ) |= 0.747… …由截去部分由截去部分( excluded terms )引起引起由留下部分由留下部分( included terms )引起引起1.2.2 绝对误差、相对误差与有效数字绝对误差、相对误差与有效数字 (Error and Significant Digits ) 定义定义 绝对误差绝对误差 (absolute error)例如：例如：其中其中 x 为精确值，为精确值，x* 为为 x 的近似值。

的近似值e|的上的上界记为界记为  , 称为称为绝对误差限绝对误差限 (accuracy), ,工程上常工程上常记为记为 x = x* ±  . .注注注注: :理论上讲理论上讲理论上讲理论上讲, , , ,e e 是唯一确定的是唯一确定的是唯一确定的是唯一确定的, , 可能取正可能取正可能取正可能取正, , 也可能取负也可能取负也可能取负也可能取负. . . .     > 0 > 0 > 0 > 0 不唯一不唯一不唯一不唯一，，，，当然当然当然当然     越小越具有参考价值越小越具有参考价值越小越具有参考价值越小越具有参考价值提问：绝对误差限的大小能否完全地提问：绝对误差限的大小能否完全地表示近似值的好坏？表示近似值的好坏？l例如：例如：有两个量有两个量 问：问：谁的近似程度要好一些？谁的近似程度要好一些？ 思考定义定义 近似值近似值 x* 的的相对误差相对误差 (relative error)定义定义 近似值近似值 x* 的的相对误差上限相对误差上限( (界界) ) (relative accuracy)由于精确值由于精确值 x 未知未知, 实际上总把实际上总把 作为作为x*的的 相对误差，并且仍记为相对误差，并且仍记为er , 即即 注注注注: :相对误差一般用百分比表示相对误差一般用百分比表示相对误差一般用百分比表示相对误差一般用百分比表示. . . .例例1 用最小刻度为毫米的卡尺测量直杆甲和直杆用最小刻度为毫米的卡尺测量直杆甲和直杆乙，分别读出长度为乙，分别读出长度为 a=312mm 和和 b=24mm，，问：问： (a)，， (b)，，  r(a)，， r(b)各是多少？两直杆各是多少？两直杆的实际长度的实际长度 x 和和 y 在什么范围内？在什么范围内？ 解：解： 例例2 设设 a=-2.18 ，， b=2.1200 是分别由准确值是分别由准确值x和和y 经过四舍五入而得到的近似值，经过四舍五入而得到的近似值，问：问：  (a)，， (b)，，  r(a)，， r(b) 各是多少？各是多少？解：解：Ø有效数字有效数字 ( significant digits)四舍五入带来的绝对误差限四舍五入带来的绝对误差限 凡是由准确值凡是由准确值 x 经四舍五入而得到近似值经四舍五入而得到近似值 x*，，其绝对误其绝对误差限等于该近似值差限等于该近似值末位末位的半个单位。

的半个单位定义定义 有效数字有效数字 设设 x* 是数是数 x 的近似值，如果的近似值，如果 x* 的绝对误差限是它的的绝对误差限是它的某一位的半个单位，并且从该位到它的第一位非零数字共某一位的半个单位，并且从该位到它的第一位非零数字共有有 n 位，则称用位，则称用 x* 近似近似 x 时，具有时，具有 n 位有效数字位有效数字用科学计数法，记用科学计数法，记（其中（其中 ））,若若 ( (即即 an 的截取的截取按四舍五入规则按四舍五入规则) )，，则则 x* 至少有至少有n 位有效数字，且精确到位有效数字，且精确到10m  n.Ø有效数字的确定方法有效数字的确定方法有效数字的位数有效数字的位数 n = 近似数科学记数法的幂指近似数科学记数法的幂指 数数－－绝对误差限科学记数法的幂指数绝对误差限科学记数法的幂指数.当差为负整数时当差为负整数时，表示没有效数字，表示没有效数字! ! 把误差限把误差限表示为表示为0.5×100.5×10m n, , 当指数当指数 m   n 是最小的整数是最小的整数时时, , 有效数字的位数精确地是有效数字的位数精确地是 n. .例例3 下列近似值的绝对误差限都是下列近似值的绝对误差限都是0.005，， 问：各个近似值有几位有效数字？问：各个近似值有几位有效数字？ 注注注注: : 1 1、同一个准确值的不同近似值，有效数、同一个准确值的不同近似值，有效数、同一个准确值的不同近似值，有效数、同一个准确值的不同近似值，有效数字越多，其绝对误差和字越多，其绝对误差和字越多，其绝对误差和字越多，其绝对误差和相对误差都越小相对误差都越小相对误差都越小相对误差都越小. . . . 2 2 2 2、准确值的有效数字可看做有无限多位、准确值的有效数字可看做有无限多位、准确值的有效数字可看做有无限多位、准确值的有效数字可看做有无限多位. . . .3位：1，3，81位：30位例例问：问： 有几位有效数字？请证明你的结论。

有几位有效数字？请证明你的结论注：注：注：注：1 1、、、、由准确值经过四舍五入得到的近似值，从它的末位由准确值经过四舍五入得到的近似值，从它的末位由准确值经过四舍五入得到的近似值，从它的末位由准确值经过四舍五入得到的近似值，从它的末位数字到第一位非零数字都是有效数字数字到第一位非零数字都是有效数字数字到第一位非零数字都是有效数字数字到第一位非零数字都是有效数字 2 2、、、、0.23000.2300有有有有4 4位有效数字，而位有效数字，而位有效数字，而位有效数字，而0.230.23只有只有只有只有2 2位有效数字位有效数字位有效数字位有效数字1230012300有有有有5 5位有效数字，如果写成位有效数字，如果写成位有效数字，如果写成位有效数字，如果写成0.1230.123   10105 5，则表示只有，则表示只有，则表示只有，则表示只有3 3位有效数字位有效数字位有效数字位有效数字 数字末尾的数字末尾的数字末尾的数字末尾的0 0不可随意省去！不可随意省去！不可随意省去！不可随意省去！证明证明：1.2.3 函数求值的误差估计函数求值的误差估计问题一问题一：对于函数：对于函数 y = f (x)，，若用若用 x* 取代取代 x，， 将对将对 y 产生什么影响？产生什么影响？分析分析：：e(y) = f (x)   f (x*) e(x) = x   x *= f '(  )(x   x *)x* 与与 x 非常接近时，可认为非常接近时，可认为 f '(  )   f '(x*) ，，则则有：有：|e(y)|   | f '(x*)|·|e(x)| (1) (2)即：即：x*产生的误差经过产生的误差经过 f 作用后被放大作用后被放大/缩小了缩小了| f '(x*)|倍。

故称倍故称| f '(x*)|为为放大因子放大因子 ( amplification factor ) 或或 绝对条件数绝对条件数 ( absolute condition number ).相对误差条件数相对误差条件数 ( relative condition number) f 的条件数在某一点是的条件数在某一点是小小\大大，则称，则称 f 在该点是在该点是好条件的好条件的 ( well-conditioned ) \坏条件的坏条件的 ( ill-conditioned )问题二问题二：对于：对于n 元函数元函数 将对将对 u 产生什么影响？产生什么影响？问题三：四则运算结果的误差估计问题三：四则运算结果的误差估计 设设a,b 分别是准确值分别是准确值x,y 的近似值，则的近似值，则 设设a,b 分别是准确值分别是准确值x,y 的近似值，则的近似值，则例例4 设有三个近似数设有三个近似数 a=2.31,=2.31,b=1.93,=1.93,c=2.24=2.24它们都有三位有效数字，试计算它们都有三位有效数字，试计算p= =a+ +bc，，并问：并问：p的计算结果能有几位有效数字？的计算结果能有几位有效数字？ 例例5 ε(p) ≈0.025852位f(x,y) ≈0.49543≈0.39%ε(u) ≈0.0022<0.005p ≈ 6.63321.2.4 算法及其计算复杂性算法及其计算复杂性定义定义 算法算法 就是规定了怎样从输入数据计算出数就是规定了怎样从输入数据计算出数值问题解的一个有限的基本运算序列值问题解的一个有限的基本运算序列. . 定义定义算法的计算复杂性算法的计算复杂性 是指在达到给定精度时是指在达到给定精度时, ,该算法所需的计算量和所占的内存空间该算法所需的计算量和所占的内存空间. . 前者叫前者叫时间复杂性时间复杂性，后者叫，后者叫空间复杂性空间复杂性. .例子例子 计算下面多项式的值。

输入数据为计算下面多项式的值输入数据为ai和和x，，输出数据为输出数据为 p(x) 的值算法一算法一算法二算法二（秦九韶法）（秦九韶法）秦九韶法原理秦九韶法原理Tn=anTn-1= xTn+an-1T0= xT1+a0T1= xT2+a1算法比较算法比较Ø算法一算法一 所需乘法次数为所需乘法次数为 n(n+1)/2, ,加法次数为加法次数为n Ø算法二算法二 所需乘法次数为所需乘法次数为n，，加法次数也为加法次数也为n 两种算法所占内存空间基本相同算法二是1247年我国数学家秦九韶首次提出的 注意：简化计算步骤，减小运算次数注意：简化计算步骤，减小运算次数注意：简化计算步骤，减小运算次数注意：简化计算步骤，减小运算次数. . . .算法一算法一 逐个相乘要用逐个相乘要用254254次乘法算法二算法二 1414次乘法例子 计算 的值思考算法比较1. 避免相近二数相减避免相近二数相减例：例：a1 = 0.12345，，a2 = 0.12346，，各有各有5位有效数字位有效数字 而而 a2   a1 = 0.00001，，只剩下只剩下1位有效数字。

位有效数字 几种经验性避免方法：几种经验性避免方法：当当 | x | << 1 时：时： 设计算法时应遵循的一些原则设计算法时应遵循的一些原则2. 避免小分母避免小分母 : 分母小会造成浮点溢出分母小会造成浮点溢出 ( over flow )3. 避免大数避免大数吃吃小数小数例：例：用单精度计算用单精度计算 的根精确解为精确解为 算法算法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大数大数吃吃小数小数?算法算法2: :先解出先解出 再利用再利用注：注：注：注：求和时求和时从小到大从小到大相加，可使和的误差减小。

相加，可使和的误差减小例：例：按从小到大、以及从大到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算1 + 2 + 3 + … + 40 + 1094. 先化简再计算，减少步骤，避免误差积累先化简再计算，减少步骤，避免误差积累一般来说，计算机处理下列运算的速度为一般来说，计算机处理下列运算的速度为5. 选用稳定的算法选用稳定的算法,控制舍入误差的传播控制舍入误差的传播误差传播与积累误差传播与积累例：例：计算计算公式一：公式一：注意此公式注意此公式精确精确成立成立, 因为因为 记为记为则初始误差则初始误差 ???? !! !What happened?!考察第考察第n步的误差步的误差  公式公式方法：先估计一个方法：先估计一个IN , ,再反推要求的再反推要求的 In ( n << N )unstable algorithm), 我们有责任改变我们有责任改变 造成这种情况的是造成这种情况的是不稳定的算法不稳定的算法 迅速积累迅速积累, ,可见初始的小扰动可见初始的小扰动误差呈递增误差呈递增. .考察反推一步的误差：考察反推一步的误差：以此类推，对以此类推，对 n < N 有：有：误差逐步递减误差逐步递减, 这样的算法称为这样的算法称为稳定的算法稳定的算法 (stable algorithm). 在我们今后的讨论中在我们今后的讨论中, 误差误差将不可回避将不可回避, 算法的算法的稳定性稳定性会是一个非常重要的话题。

会是一个非常重要的话题可取可取当 N  时，取取 We just got lucky?作 业 题书：书：P12 习题一习题一1、、2、、3、、4、、5、、6、、7、、8、、12练 习 题1 1、、下列各近似值均有四位有效数字，试指出它们下列各近似值均有四位有效数字，试指出它们的绝对误差限和相对误差限的绝对误差限和相对误差限2 2、、下列近似值的绝对误差限都是下列近似值的绝对误差限都是0.00050.0005，试指出，试指出它们有几位有效数字它们有几位有效数字 3 3、、在四位十进制的限制下，试选择精确度最高的在四位十进制的限制下，试选择精确度最高的算法，计算下式的值算法，计算下式的值4 4、、设设 ，，在四位十进制的限制下，试在四位十进制的限制下，试使用一个具有数值稳定性的算法，计算使用一个具有数值稳定性的算法，计算 的近似值的近似值答案：答案：1、0.000005,0.03712%;0.005,0.04052%;0.0005,0.04167%.2、4、2、03、1342004、l数学符号 x0, , x1, , xn, y0, , y1, , ym, xi  1 ilk=0,1, , n 1. 0x,1x, , nx l(x, y)  pnm(x, y) l              lΓΔΘΛΞΦΨΩl                                  l   l    l                       l①②③④⑤⑥⑦⑧⑨。