工学计算方法.pptx

计算方法的内容计算方法的内容 1.第一章第一章 引论：引论：132.第二章第二章 线性方程组的直接法线性方程组的直接法14，5-63.第三章第三章 插值法与最小二乘法插值法与最小二乘法14，5-74.第四章第四章 数值积分与微分数值积分与微分1，2，5，35.第五章第五章 常微分方程数值解法：常微分方程数值解法：1，26.第六章第六章 逐次逼近法：逐次逼近法：132第一章第一章 计算方法引论计算方法引论 现代科学的三个重要组成部分现代科学的三个重要组成部分:科学理论科学理论,科学实验科学实验,科学计算科学计算。仅靠数学理论的演绎和推导不能解决实际中的数值问仅靠数学理论的演绎和推导不能解决实际中的数值问题，只有计算机科学相结合，才能研制出实用的好算题，只有计算机科学相结合，才能研制出实用的好算法。法。好的算法变成数值软件以后才可能为社会创造更大的好的算法变成数值软件以后才可能为社会创造更大的财富。财富。1.计算机数值方法概述计算机数值方法概述 计算方法是计算方法是数学与计算机科学数学与计算机科学的的交叉学科交叉学科。1 1）数学的发展极大地促进了计算机科学的发展：数学的发展极大地促进了计算机科学的发展：Leibniz发现二进制编码；发现二进制编码；Von Neumann提出现代计算机建构理论；提出现代计算机建构理论；Bohm和和Jacopini为结构化程序设计奠定了基础。为结构化程序设计奠定了基础。2）计算机科学为数学提供先进手段，并对数学计算机科学为数学提供先进手段，并对数学 发展产生了重大影响。发展产生了重大影响。为利用数学解决实际问题提供了工具；为利用数学解决实际问题提供了工具；解决了一些数学难题，并提出了新的研究课题；解决了一些数学难题，并提出了新的研究课题；促进了促进了“并行算法并行算法”的研究和新一代计算机的发展。的研究和新一代计算机的发展。2 计算方法的发展，产生了大量适合计算机求解的计算方法的发展，产生了大量适合计算机求解的现代数值方法，成为科学计算的主要方法。现代数值方法，成为科学计算的主要方法。现代计算方法的一个现代计算方法的一个显著特点显著特点：已产生大量实用的已产生大量实用的“综合数学软件库综合数学软件库”，并逐步，并逐步 形成了数值软件产业。形成了数值软件产业。例如：例如：Mathematica是综合数学软件包，集符合演算、数值是综合数学软件包，集符合演算、数值 计算和图形演示等；计算和图形演示等；STYR是一个集数学、统计、应用软件等大型综合是一个集数学、统计、应用软件等大型综合 数值软件库；数值软件库；Matlab是集数值计算、图形演示等一体的综合数值是集数值计算、图形演示等一体的综合数值 软件库。软件库。计算方法的研究问题：将常见的数学模型计算方法的研究问题：将常见的数学模型转变转变成数值成数值 问题，提出相应的问题，提出相应的数值方法数值方法，并设计，并设计数值算法数值算法，并利，并利 用用程序程序计算数值结果。计算数值结果。3 严格来讲，需要掌握一定的程序设计方法严格来讲，需要掌握一定的程序设计方法4以计算机求解数学模型包含三个过程：以计算机求解数学模型包含三个过程：总体设计总体设计：模型的细化；：模型的细化；详细设计详细设计：算法的设计；：算法的设计；程序设计程序设计：利用某种计算机语言实现编写程序。：利用某种计算机语言实现编写程序。学习本课程的学习本课程的基础知识基础知识：微积分、线性代数、微分方程等基本知识。微积分、线性代数、微分方程等基本知识。了解某种计算机高级语言。了解某种计算机高级语言。2 数值问题与数值算法数值问题与数值算法 利用利用数学和计算机知识数学和计算机知识解决实际问题解决实际问题可分为两步可分为两步：建立数学模型建立数学模型：需要：需要利用有关专业知识和数学理论利用有关专业知识和数学理论，这属于应用数学范围；这属于应用数学范围；提出提出数值问题与数值方法数值问题与数值方法：将数学模型将数学模型变成变成数值问题数值问题，进而，进而研究研究该数值该数值 问题的问题的数值方法数值方法，并设计有效的数值算法的过程，并设计有效的数值算法的过程，这属于计算方法的范围。这属于计算方法的范围。数值方法数值方法：将求解：将求解“数值问题数值问题”在在“计算机上可执行计算机上可执行”的一系列计算公式。数值问题的总体称为计算方法。的一系列计算公式。数值问题的总体称为计算方法。数值问题数值问题：指：指“输入数据与输出数据之间函数关系的输入数据与输出数据之间函数关系的 一个一个确定而无歧义确定而无歧义的描述的描述”。5“计算机上可执行计算机上可执行”的系列计算公式：这一系列公式中的的系列计算公式：这一系列公式中的 运算只能是运算只能是四则运算四则运算和和逻辑运算逻辑运算（与、或、非等）。（与、或、非等）。什么什么“数学模型数学模型”是是“数值问题数值问题”？1)1)求方程求方程 的根。的根。输入输入a,b,c，则输出数据是根，则输出数据是根x1和和x2，故是，故是“数值问题数值问题”2)求常微分方程的解求常微分方程的解 因输入数据为因输入数据为2和和3，x=0和和y=0等，输出是函数等，输出是函数，故不是，故不是“数值问题数值问题”。如何如何将数学模型变成将数学模型变成“数值问题数值问题”将不是将不是“数值问题数值问题”转化为转化为“数值问题数值问题”的方法：的方法：“离散化离散化”。3例如，例如，将求解将求解 的问题变成求的问题变成求，如可如可 x1，x2，x100 取为取为 0.1,0.2,0.3,10=a 2-1 2-1 数值方法数值方法 计算公式不一定都是数值方法。如求计算公式不一定都是数值方法。如求 。7类似地，类似地，求根公式求根公式不能在计算机不能在计算机上直接运行上直接运行 研究数值方法的任务有三条：研究数值方法的任务有三条：1 1）将计算机不能直接计算的运算化成计算机上）将计算机不能直接计算的运算化成计算机上可执行可执行的的 运算；利用运算；利用等价等价或或近似等价近似等价的方法转化；的方法转化；2）研究在计算机上研究在计算机上可执行可执行且且有效的有效的一系列计算公式；一系列计算公式；3 3）误差分析：研究数值问题的性态和数值方法的稳定性。）误差分析：研究数值问题的性态和数值方法的稳定性。计算机上能直接进行的运算：计算机上能直接进行的运算：四则运算四则运算 和和 逻辑运算逻辑运算 计算机上不能直接执行的运算包括：计算机上不能直接执行的运算包括：开方、超越函数、极限、微分、积分等开方、超越函数、极限、微分、积分等 几个转化例子几个转化例子 8 本课程本课程重点重点是介绍常见的行之有效的新的数值方法。是介绍常见的行之有效的新的数值方法。2-2 数值算法数值算法 数值算法数值算法：有步骤地完成求解数值问题的过程。：有步骤地完成求解数值问题的过程。数值算法的解题过程必须具备以下四个特性：数值算法的解题过程必须具备以下四个特性：1）目的性目的性：算法目的明确，条件和结论均应明确；：算法目的明确，条件和结论均应明确；2）确定性确定性：算法必须精确地给出每一步的操作；：算法必须精确地给出每一步的操作；3）可执行性可执行性：算法中的每个操作都是可执行的；：算法中的每个操作都是可执行的；4）有穷性有穷性：算法必须在有限步内结束解题过程。：算法必须在有限步内结束解题过程。计算机上的算法分类计算机上的算法分类 按求解问题的不同可分为两类：按求解问题的不同可分为两类：数值算法数值算法和和非数值算法非数值算法（符号推理、公式推导）。（符号推理、公式推导）。9 按面向计算机的不同，可分为：按面向计算机的不同，可分为：面向串行计算机的面向串行计算机的串行算法串行算法，只有一个进程；，只有一个进程；面向并行计算机的面向并行计算机的并行算法并行算法，含两个以上的进程，含两个以上的进程 根据算法内部的特点可分为：根据算法内部的特点可分为：确定性算法确定性算法，每完成一步确切知道下一步该做什么，每完成一步确切知道下一步该做什么 非确定性算法非确定性算法（智能算法）。（智能算法）。注：注：计算机数值方法计算机数值方法只研究只研究计算机上计算机上串行确定型串行确定型数值算法。数值算法。例例1 1 给出等差数列给出等差数列1,2,3,10000的求和算法的求和算法 1）取取N=0,S=0；2）N+1N,S+NS；3）若若N0不成立，不成立，转，转76.，7.输出输出x1和和x214二图示法：二图示法：又又分分为为“流流程程图图”法法和和“结结构构化化框框图图”法。法。流程图示法流程图示法 15 结构化框图法：结构化框图法：N-S图示法图示法 1顶层设计：顶层设计：2第第1层设计：细化层设计：细化(II)3第第2层设计：层设计：a)细化细化(I)16b)细化细化(II)4.第第3层设计：细化层设计：细化 173 3 误差误差 3-1 误差的基本概念误差的基本概念 数值计算中的数值计算中的误差来源误差来源有两种：有两种：1)1)舍入误差舍入误差：由于计算机的字长有限，原始数据：由于计算机的字长有限，原始数据 在计算机中的表示、运算产生的误差；在计算机中的表示、运算产生的误差；2)截断误差截断误差：由数学问题化成数值问题产生的误差：由数学问题化成数值问题产生的误差例如：例如：若计算机仅能表示若计算机仅能表示6位十进制数，则将表示为位十进制数，则将表示为,误差误差 若将与数若将与数9.210 00进行加法运算，得进行加法运算，得 R1 1和和R2 2都是舍入误差。都是舍入误差。18 计算计算 的数值。因的数值。因 由算法的有限性，故利用由算法的有限性，故利用截断部分和截断部分和 来近似代替，由此产生的误差即为来近似代替，由此产生的误差即为截断误差截断误差，估计为，估计为 绝对误差绝对误差与与相对误差相对误差 19定义定义3.1 设设x为准确值，为准确值，为为x的一个近似值，称的一个近似值，称 为近似值为近似值 的的（绝对）误差（绝对）误差，简记为简记为E。圆周率的近似值圆周率的近似值a=3.14,绝对误差绝对误差E=0.00159 一般来说，一般来说，E的的准确值很难求准确值很难求出，只能估计出出，只能估计出|E|的的 某个某个上界上界 ，即，即 称为近似值称为近似值 的的(绝对绝对)误差限误差限，简记为，简记为 。于是。于是，：可表示成可表示成定义定义3.2 近似值近似值 的误差与准确值的误差与准确值x之比之比称为近似值称为近似值 的的相对误差相对误差，简记为，简记为 20绝对值的任一上界绝对值的任一上界 ，称为，称为相对误差限相对误差限，简记为，简记为 由于由于x的准确值难以确定，通常利用的准确值难以确定，通常利用 代替代替 注：注：绝对误差限与相对误差限绝对误差限与相对误差限不唯一；它们越小越好不唯一；它们越小越好。对于准确值对于准确值x取近似值最常用的方法是采用取近似值最常用的方法是采用“四舍五入四舍五入”的原则。由此产生了一个专有名词的原则。由此产生了一个专有名词有效数字有效数字。21 定义定义3.3 如果近似值如果近似值 的误差的绝对值不超过的误差的绝对值不超过某一位数字的半个单位，且该位数字到某一位数字的半个单位，且该位数字到 的第一位的第一位非零数字共有非零数字共有n位，则称用位，则称用 （近似（近似x时）具有时）具有n位位有效数字有效数字。例如：例如：有有5位有效数字，位有效数字，而而 有有4位有效数字。位有效数字。确定有效数字的等价方法确定有效数字的等价方法：数的规格化表示：数的规格化表示：1)(3.2)2)(3.3)其中，其中，k 是某个范围内的整数，是某个范围内的整数，为为0,1,0,1,9,9中的数字。中的数字。若将近似值若将近似值 表示成表示成(3.2)(3.2)式作为式作为x的在第的在第n+1位位 数字进行四舍五入，则数字进行四舍五入，则 具有具有n位有效数字，即位有效数字，即(3.5)如：如：，有，有，五位有效数字。，五位有效数字。22 有效数字的等价定义有效数字的等价定义 定义定义3.4 如果如果x的近似值的近似值 满足不等式（满足不等式（3.53.5），即），即 一种特殊情况一种特殊情况：有效数字不唯一。如：有效数字不唯一。如 则称则称 具有具有n位有效数字。位有效数字。和和都是都是 的两位有效数字。的两位有效数字。一般情况：近似值的有效位数越多，误差的绝对值越小。一般情况：近似值的有效位数越多，误差的绝对值越小。但也有但也有个别例外个别例外，如，如 分别有分别有3和和4位有效数字。位有效数字。，23（最大的（最大的n值）值）近似值的近似值的有效数字有效数字与与相对误差相对误差之间的关系：之间的关系：定理定理3.1 设设 是是x的近似值，它的表达式为的近似值，它的表达式为:则则 的的有效位数有效位数与与 的的相对误差相对误差之间有如下关系：之间有如下关系：1）若若 具有具有n位有效数字，则位有效数字，则 的相对误差的相对误差 满足满足 2）若若 的相对误差的相对误差 满足满足 则则 至少具有至少具有n位有效数字。位有效数字。(证明略：证明略：P16-17)24(3.6)(3.7)例例6 设设x=1.986,x*=1.98,则则 故由故由(3.7)(3.7)知，知，x*至少具有至少具有2位有效数字。位有效数字。由由（3.5），k-n=-1，k+1=2，所以，所以x*具有具有2位有效数字。位有效数字。25另一方面：另一方面：x*具有具有2位有效数字，故由位有效数字，故由(3.6)，得，得因因注：上界注：上界 并不是最小的。并不是最小的。3-2 3-2 浮点基本运算的误差浮点基本运算的误差 在计算机中，每个数在计算机中，每个数x都用都用有限位有限位二进制数表示，二进制数表示，其规格化浮点数形式由其规格化浮点数形式由三部分组成三部分组成：1)阶码：确定小数点的位置；阶码：确定小数点的位置；(决定了数的取值范围决定了数的取值范围)2)数符：表示正、负号；数符：表示正、负号；3)尾数：表示机器数字长；尾数：表示机器数字长；（长度与精度有关）（长度与精度有关）形式为：形式为：其中，其中，2称为浮点数的称为浮点数的基基,是是0或或1；称；称x*为为x的的浮点数浮点数,记为记为 26(0表示正，表示正，1表示负表示负)其中，数符其中，数符0表示正表示正，1表示负表示负。浮点数也称。浮点数也称机器数机器数。设原始数据设原始数据 ，其尾数，其尾数若机器数若机器数fl(x)的尾数的尾数 是是 t 位：位：则则 于是于是 fl(x)的绝对误差的绝对误差E和相对误差和相对误差（绝对误差绝对误差E），故，故因因27一浮点数的四则运算的误差一浮点数的四则运算的误差 浮点数浮点数x和和y的四则运算结果的浮点表示：的四则运算结果的浮点表示：(3.9)(3.10)(3.11)其中，其中，,。二二 连加和连乘的误差连加和连乘的误差 设设 为规格化浮点数，求为规格化浮点数，求 和和 计算从左向右进行，计算从左向右进行，每次运算都进行截取每次运算都进行截取，再作下一次运算，再作下一次运算281.连加连加:设设 (3.12)则则(3.13)29因为因为 其中，其中，(3.14)各相对误差限的大小与运算先后有关各相对误差限的大小与运算先后有关；先运算的数，误差也较大先运算的数，误差也较大 运算应先安排小数参加运算，可防止运算应先安排小数参加运算，可防止“大数吃小数大数吃小数”302.2.连乘连乘:各相对误差限的大小与运算先后各相对误差限的大小与运算先后无关。无关。3-3 数值方法的稳定性与算法设计原则数值方法的稳定性与算法设计原则 设计和选择算法设计和选择算法首要关心首要关心的问题是的问题是精度精度要求，要要求，要建立一些定性分析准则用于判断结果的可靠性，建立一些定性分析准则用于判断结果的可靠性，这是这是数值稳定性问题数值稳定性问题。对于一个数值方法，若对原始数据或某一步有舍入误差，对于一个数值方法，若对原始数据或某一步有舍入误差，在执行过程中，这些误差能得到控制，则称在执行过程中，这些误差能得到控制，则称该数值方法该数值方法稳定稳定。否则，称为。否则，称为不稳定的不稳定的。利用两种数值方法利用两种数值方法A和和B解输入和舍入误差规则相同的解输入和舍入误差规则相同的同一问题，若用同一问题，若用A发比发比B法得到的计算解精度更高，则法得到的计算解精度更高，则称称A法比法比B法具有较大的稳定性法具有较大的稳定性。例例8 计算积分计算积分,解：由于解：由于 故故(3.16)方法一方法一：利用公式：利用公式(3.6)(3.6)式，先计算式，先计算I0，然后计算，然后计算I1,I2,I7 设计算值设计算值 的误差为的误差为 ，若，若I0时误差为时误差为 ，则，则 方法二方法二：利用公式：利用公式，先计算先计算I7，再计算，再计算I6,I5,I0 计算计算 I7 时产生误差时产生误差 ，那么计算，那么计算 I0 时的误差为时的误差为 例例9 9 求线性方程组求线性方程组(3.17)其准确解为其准确解为x1=x2=x3=1。但是，若对数据取。但是，若对数据取3位有效数字，位有效数字，利用利用Guass消去法求解，则计算解：消去法求解，则计算解：33同样对方程同样对方程 利用利用Guass消去法，取消去法，取3位有效数字，则得到准确解：位有效数字，则得到准确解：“数值问题数值问题”计算解的精度，计算解的精度，不但不但与数值方法的稳定有关，与数值方法的稳定有关，而且而且还与数值问题的性态好坏有关。还与数值问题的性态好坏有关。在数值问题中，若输出数据对输入数据的扰动（误差）在数值问题中，若输出数据对输入数据的扰动（误差）很敏感（小的变化会引起较大的变化），称这类数值很敏感（小的变化会引起较大的变化），称这类数值问题为问题为病态问题病态问题；否则称为；否则称为良态问题良态问题。34 选用计算公式和设计算法时的选用计算公式和设计算法时的普遍原则普遍原则：一四则运算中的稳定性问题一四则运算中的稳定性问题 1）防止大数吃小数防止大数吃小数 预防方法：预防方法：先加小数先加小数，由小到大逐次相加。如，由小到大逐次相加。如 2）要避免两个相近数相减要避免两个相近数相减 相近数相减会严重损失有效数值的位数相近数相减会严重损失有效数值的位数 可改为可改为 再如仿照前面求二次方程的根的方法处理。再如仿照前面求二次方程的根的方法处理。353）避免小数作除数和大数作乘法避免小数作除数和大数作乘法 这样可避免误差放大，因这样可避免误差放大，因(3.18)(3.19)二二 提高算法效率提高算法效率问题问题 1）尽量减少运算次数：尽量减少运算次数：以两例说明：以两例说明：例例10 计算计算 的值。的值。直接计算需要直接计算需要n(n+1)/2次乘法和次乘法和n次加法。次加法。若将公式变成若将公式变成递推公式递推公式：后，再计算后，再计算Pn(x)，只需做，只需做n次乘法和次乘法和n次加法。次加法。充分利用递推公式充分利用递推公式，可提高算法效率。，可提高算法效率。2）充分利用耗时少的运算充分利用耗时少的运算 例如：例如：k+k比比2k，a*a比比a2，b*0.25比比b/4等节省时间。等节省时间。3）充分利用存贮空间充分利用存贮空间 1）节省原始数据的存贮单元；节省原始数据的存贮单元；2）节省工作单元。节省工作单元。37三三 着眼于高质量的软件着眼于高质量的软件