数值计算方法课件.ppt

1,数值计算方法,2,主要内容,算法和误差 非线性方程 线性方程组 特征值 插值和拟合 微分和积分 微分方程,3,第一章 算法与误差,数值计算是求解数学问题的常用方法，随着计算机技术的飞速发展，数值计算方法在现代科学研究中的作用越来越广泛。数值计算的算法的研究越来越受到人们的重视。 1) 数值计算是应用数学一个重要分支,比如:微分方程,现代物理. 2) 新的数学,混沌理论(迭代法求非线性方程的根). 与过去相比，现代数值计算方法有两个显著特点： 1） 数值计算的方法和理论都结合数字计算机的特点来研究。在进行算法研究时，注意算法与计算速度，计算内存消耗的关系 2）在研究算法时，注重算法误差分析，注意数值解的收敛性和数值计算的稳定性问题。,4,模型：人们为了一定的目的，对客观事物的某一部分进行简化、抽象和提炼出来的替代物，它集中反映了客观事物中人们需要研究的那部分特征。 数学模型：将模型的特征、内存规律用数学的语言和符号来描述的数学表述或数学结构。例如：人口增长模型 求解问题的方法和步骤： 形成问题明确待研究问题的特征、背景、用途 提出假设抓住主要矛盾、忽略次要因素 建立模型量化关键因素、建立数学结构和模型 算法求解选择合适的算法对模型问题进行求解 算法分析对算法的误差和灵敏度、稳定性进行分析 修正模型对模型进行检验和修正 算法应用应用成果解决实际问题,5,1.1 算法 一、算法的概念 当我们用数值计算方法求解一个比较复杂的数学问题时，常常要事先拟定一个计算方案，规划一下计算的步骤。所谓算法，就是指在求解数学问题时，对求解方案和计算步骤的完整而明确的描述。 描述一个算法可以采用许多方法，最常用的一个方法是程序流程图。算法也可以用人的自然语言来描述。如果用计算机能接受的语言来描述算法，就称为程序设计。,6,二、算法的质量标准 求解一个数学问题，可以采用不同的算法，比如：线性方程组，可用克莱姆法则，高斯消元法等多种方法求解。但是每一种方法的优劣不同，评价一个算法的好坏有以下几个标准： 1） 算法的计算量（时间复杂性） 例1：用克莱姆法则求解一个n阶线性方程组时，需要计算（n+1）个n阶行列式的值。需要做 次乘法。设n=20,若采用10亿/秒的计算机，要花费三十万年的时间进行计算。若用高斯消元法来求解，采用一个普通的586微机，在几分钟之内就可得结果。 计算量的大小事衡量一个算法优劣的重要标准。,7,例2：天竺国，梵塔 据说在东方的古国印度土地上，有一座印度教的神庙，这庙有一块黄铜板，板上插著三根细细的、镶上宝石的细针，细针像菜叶般粗，而高就像成人由手腕到肘关节的长。 当印度教的主神梵天在创造地球这个世界时，就在其中的一根针上从下到上放了半径由大到小的六十四片圆金片环，这就是有名的梵塔或称汉内塔（Towers of Hanoi）。 天神梵天要这庙的僧侣，把这些金片全部由一根针移到另外一根指定的针上，一次只能移一片，不管在什么情况下，金片环的大小次序不能变更，小金片环永远只能放在大金片环上面。 只要有一天这六十四片的金环能从指定的针上完全转移到另外指定的针上，世界末日就来到。 经过计算机的运算，移动的次数需18,446,744,073, 709,551,615，一秒移动一次，大约需要5849亿年。,8,2） 算法的空间复杂性 当使用计算机求解一个数学问题时，计算程序要占用许多工作单元（内存）。当计算一个大型的数学问题时，内存的消耗量是很大的。因此，算法占用内存数量的多少，是衡量算法优劣的另一个标准。 3） 算法逻辑结构的复杂性 设计算法时应该考虑的另一个因素是逻辑结构问题，虽然计算机能自动执行极其复杂的计算程序，但是计算程序的每个细节都需要编程人员制定，因此算法的逻辑结构应尽量简单，才能使程序的编制、维修和使用比较方便。 以上我们介绍了算法的一些基本概念。下面讨论数值计算中的另一个重要问题误差。,9,1.2 误差 在研究算法时，要进行误差分析，能估计误差的算法才是有实用价值的算法。 一、 误差的来源： 引起计算误差的原因是多方面的。 1）模型误差 当解决一个工程实际问题时，常常需要用一定的数学表达式来描述，即建立一个数学模型。建立数学模型时，通常要根据实际需要做一些简化，忽略一些次要因素，是模型不致过分复杂，又能满足精度要求。这样建立起来的数学模型是客观现象的近似描述。这种近似必然产生误差。,10,2） 方法误差 在计算过程中，由数学方法产生的误差，称为方法误差。,例如，在计算指数函数的值时，常用到如下幂级数展开式：,这是一个无穷级数。计算时，只能取有限项。,用有限项逼近无穷级数，会产生一个误差，这个误差是由数学方法产生的，所以是一种方法误差。,11,3) 舍入误差 在计算过程中，当我们表示一个数时，常常只能取有限位。超出的尾数将会舍去，从而造成误差，这种误差称为舍入误差。 舍入误差时我们数值计算中重点研究的对象，将贯穿整个课程之中。,12,二、 误差的概念 1） 误差： 某个量的真值与近似值的差的绝对值，称为近似值的误差，又称绝对误差，用e表示。,真值，,近似值，,2） 误差限 在许多情况下，我们不知道某个量的真实值是多少，因此也不知道它的近似值的误差。但是我们能估计出误差不会超过某个确定的数值。这个数值就称为近似值的误差限。 我们能用误差限定量的衡量一个近似值的误差。,如果某近似值的误差限是，我们就说，在允许误差的条件下，近似值是准确的。,13,3）有效数字 我们还可以用有效数字的概念来说明一个近似值的准确程度。 我们先介绍“四舍五入”的概念，四舍五入是数值计算时，取近似值的一种方法。若被舍去部分的头一位大于等于5时，就在所取数的末位加1；小于5时，就舍去。 用四舍五入方法得到的近似值，称为有效数字。 有效数字的末位到第一位非零数字的个数，称为该有效数字的位数。 有效数字可用来表示一个近似值的准确程度，一个近似值的有效位数越多，这个近似值就越逼近真值。,14,由上面的有效数字的定义，我们能给出另外一种等价的定义。 若近似值的误差小于某一位的半个单位，便称近似值准确到这一位。从这一位到第一个非零数字的个数就是近似值的有效位数。 上述定义常用在数值计算的过程中，用来控制迭代的精度。,15,例：圆周率是一个无理数， =3.14159265358979323，考察下列近似值的有效位数。,16,3）,的万分位不是按四舍五入规则得到的，因此,有四位有效数字，而不是五位有效数字。,小于千分位上的半个单位，从千分位到个位有四位。,精确到千分位。3.1416有五位有效数字，准,确到万分位。3.1415有四位有效数字，准确到千分,位。这就是,的近似值采用3.1416,而不采用3.1415,的原因。,17,18,19,20,21,22,23,24,25,26,27,x=1.364746094,28,29,若 是方程的根，则 称为方程的不动点。,30,31,32,33,34,x=1.36523002,35,36,37,38,39,40,41,x=1.3652300,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,例：线性插值：,线性拟合：,函数,与各结点的误差的平方和最小。,98,5.2线性插值,99,100,101,102,103,104,105,106,107,108,5.4插值余项,n次插值多项式,在结点处，,恒等于,在其它点有误差：,109,110,111,112,以三阶插值公式为例：,取等距节点：,设：,插值点：,则：,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,