数值分析CH1_赖志柱.ppt

1,数值分析 Numerical Analysis,数值分析 Numerical Analysis,毕节学院数学与计算机科学学院 赖志柱 2012年08月,2,数值分析 Numerical Analysis,教材及主要参考书,李庆扬，王能超，易大义.数值分析（第五版）.清华大学出版社，2008，12. 同济大学计算数学教研室.数值分析基础.同济大学出版社，1998. 黄友谦、李岳生，数值逼近，第二版，北京：高等教育出版社，1987 . 关治、陆金甫，数值分析基础，北京：高等教育出版社，1998（2008重印）,3,数值分析 Numerical Analysis,徐利治、王仁宏、周蕴时，函数逼近的理论与方法，上海：上海科学技术出版社，1983 胡祖炽、林源渠，数值分析，北京：高等教育出版社，1988 曹志浩、张玉德、李瑞遐，矩阵计算与方程求根，第二版，北京：高等教育出版社，1984 冯康等编，数值计算方法，国防工业出版社，1978 张池平、施云慧，计算方法，北京：科学出版社，2002,4,数值分析 Numerical Analysis,李信真.计算方法.西北工业大学出版社，2000. 周品，何正风.MATLAB数值分析.机械工业出版社，2009,01. 张德丰等.MATLAB数值计算方法.机械工业出版社，2010,01. 魏毅强.数值计算方法.科学出版社，2004，8. 林成森.数值分析.科学出版社，2007，1.,5,数值分析 Numerical Analysis,杨刚、武燕、王宇翔，数值分析全析精解，西安：西北工业大学出版社，2007.6 李庆扬，数值分析复习考试指导，北京：高等教育出版社，2000 封建湖、车刚明，计算方法典型题分析解集，西安：西北工业大学出版社，1998 封建湖、聂玉峰、王振海，数值分析导教导学导考，西安：西北工业大学出版社，2003 杨蕤，数值分析全程导学及习题全解，北京：中国时代经济出版社，2007,6,数值分析 Numerical Analysis,同济大学计算数学教研室，数值计算解题方法与同步训练，上海：同济大学出版社，2001.4 马东升、熊春光，数值计算方法习题及习题解答，北京：机械工业出版社，2006.9 孙志忠，计算方法典型例题分析，第二版，北京：科学出版社，2005,7,数值分析 Numerical Analysis,成绩考核办法,1、平时成绩占20%：出勤、课堂提问、课堂讨论、平时作业、实验报告等 2、期中考试成绩占20% 3、期终考试成绩占60% 4、综合考核成绩平时成绩20%+期中考试成绩 20%+期终考试成绩60%,8,数值分析 Numerical Analysis,相关软件,C, C+ (Visual C+) MATLAB 相关软件包 Java, c#等,9,数值分析 Numerical Analysis,第一章 数值分析与计算科学引论,1.1 数值分析的对象、作用与特点 1.2 数值计算的误差 1.3 误差定性分析与避免误差危害,10,数值分析 Numerical Analysis,1.1 数值分析的对象、作用与特点,1.1.1 数学科学与数值分析 1.1.2 计算数学与科学计算 1.1.3 计算方法与计算机 1.1.4 数值问题与算法 1.1.5 数值分析课程的特点 1.1.6 其它,11,数值分析 Numerical Analysis,1.1.1 数学科学与数值分析,数学是科学之母，科学技术离不开数学，它通过建立数学模型与数学产生紧密联系，数学又以各种形式应用于科学技术各领域。 数值分析也称计算数学，是数学科学的一个分支，主要研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现。,12,数值分析 Numerical Analysis,用计算机求解科学技术问题通常的步骤,（1）根据实际问题建立数学模型；（应用数学的任务） （2）由数学模型给出数字计算方法；（可靠、高效的算法） （3）根据计算方法编制算法程序（数学软件）在计算机上计算出结果。 其中（2）和（3）是计算数学的任务。,13,数值分析 Numerical Analysis,数值分析的主要内容包括插值与数据逼近、数值微分与数值积分、线性方程组的数值求解、非线性方程与方程组求解、特征值计算、常微分方程数值解等。 数值分析也是以数学问题为研究对象，但它不像纯数学那样只研究数学本身的理论，而是把理论与计算紧密结合，着重研究数学问题的数值方法及其理论。 数值分析是一门内容丰富、研究方法深刻、有自身理论体系的课程。 数值分析既有纯数学高度抽象性与严密科学性的特点，又有应用数学的广泛性与实际试验的高度技术性的特点，是一门与计算机使用密切结合的实用性很强的数学课程。,14,数值分析 Numerical Analysis,1.1.2 计算数学与科学计算,计算数学是数学的一个分支，研究如何用计算机解决各种数学问题的科学，它的核心是提出和研究求解各种数学问题的高效而稳定的算法。 计算数学的主要内容包括代数方程、线性代数方程组、微分方程的数值解法，函数的数值逼近问题，矩阵特征值的求法，最优化计算问题，概率统计计算问题等等，还包括解的存在性、唯一性、收敛性和误差分析等理论问题。,15,数值分析 Numerical Analysis,计算科学(Scientific Computing)，又称科学计算(Computational Science)，是一个与数学模型构建、定量分析方法以及利用计算机来分析和解决科学问题相关的研究领域，它使用数学、统计与计算器的技术，借助计算机高速计算的能力，来解决现代科学、工程、经济或人文中的复杂问题。 狭义的科学计算是针对某些特定的数学问题，设计有效的计算方法来求解，因此即为数值分析、数值计算、计算方法。,16,数值分析 Numerical Analysis,科学计算是一门工具性、方法性、整合性（边缘性）的新学科，是各种科学与工程计算领域（如气象、地震、核能技术、石油探勘、航天工程、 密码解译等）中不可缺少的工具。 随着计算机的高速发展，数值计算方法已深入到各个科学研究领域，计算性交叉学科不断涌现，如计算力学、计算物理、计算化学、计算生物学、计算经济学等。,17,数值分析 Numerical Analysis,随着计算机技术的发展，科学计算与科学理论、科学实验一并被称为近代科学研究的三大基本手段。 使用计算机进行科学计算、数据处理及分析已成为人类科技活动的主要方法之一。熟练地使用计算机进行科学计算，已成为科技工作者的一项基本技能。 计算数学是科学计算的核心与基础。,18,数值分析 Numerical Analysis,1.1.3 计算方法与计算机,数值分析也称计算方法，它与计算工具的发展密切相关。 计算工具：算盘、算图、算表、算尺、手摇及电动计算机、电子计算机等。 只是在计算机出现以后，才使计算方法迅速发展并形成数学科学的一个独立分支计算数学。 当今计算能力的大幅度提高既来自计算机的进步，也来自计算方法的进步，两种发展相辅相成又相互促进。,19,数值分析 Numerical Analysis,1.1.4 数值问题与算法,能用计算机计算的“数值问题”是指输入数据（即问题中的自变量与原始数据）与输出数据（结果）之间函数关系的一个确定而无歧义的描述，输入输出数据可用有限维向量表示。 算法是指把对数学问题的解法归结为只有加、减、乘、除等基本运算，并确定运算次序的完整而准确的描述。,20,数值分析 Numerical Analysis,一般情况下，算法可以如下分类： 分类方法1：若算法只包含一个进程则称其为串行算法，否则为并行算法。 分类方法2：从算法执行所花费的时间角度来讲，若算术运算占绝大多数时间则称其为数值算法，否则为非数值算法。 分类方法3：按算法的内部特征分为确定型算法与非确定型算法。,21,数值分析 Numerical Analysis,通常的科学计算是实现确定型算法，“确定型”是指计算机在执行算法时，做完每一步都精确地知道下一步该怎么做。 智能计算是实现非确定型算法，这是一类基于选择的算法，计算机在执行这种算法时，存在不能精确地知道下一步该做什么而必须在几种可能方案中选择一种去执行的情况。,22,数值分析 Numerical Analysis,分类方法4：精确算法与近似算法 精确算法是指在没有运算舍入误差的假设下，能在确定的运算次数内获得数学问题的精确解。 近似算法本身有方法误差，从而在任何有限的运算次数内只能获得数学问题的近似解。 实际上，由于计算机的字长有限，每次运算都有舍入误差，从而无论精确解法还是近似算法都只能获得数学问题的近似解。,23,数值分析 Numerical Analysis,本课程介绍确定型数值串行算法。（其它类型算法参阅数据结构、并行算法等课程。） 算法的评价，即算法的可靠性，包括算法的收敛性、稳定性、误差估计等几个方面。 一个算法在保证可靠的大前提下再评价其优劣才是有价值的。 可靠算法的优劣，应该考虑其计算复杂性： 时间复杂度：计算机运行时间； 空间复杂度：占据计算机存储空间的多少； 逻辑复杂度：影响程序开发的周期以及维护。,24,数值分析 Numerical Analysis,1.1.5 数值分析课程的特点,数值分析是研究数值问题的算法，概括起来有以下四点： （1）面向计算机，能根据计算机特点提供切实可行的有效算法。 （2）有可靠的理论分析，能任意逼近并达到精度要求，对近似算法要保证收敛性和数值稳定性，还要对误差进行分析。 （3）设计的算法要有好的计算复杂性，它关系到算法能否在计算机上实现。 （4）要有数值实验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验证明是行之有效的。,25,数值分析 Numerical Analysis,1.1.6 其它,（1）本课程的基本要求： 掌握数值方法的基本原理（理论分析）； 掌握常用的科学与工程计算的基本方法（算法思想及计算）； 能用所学方法在计算机上算出正确结果（编程实现）。,26,数值分析 Numerical Analysis,（2）本课程的学习方法（建议）： 认识建立算法和对每个算法进行理论分析是基本任务，主动适应“公式多”和“讲理论”的特点；注重各章建立算法的问题的提法，搞清问题的基本提法，逐步深入；理解每个算法建立的数学背景，数学原理和基本线索，对最基本的算法要非常熟悉；认真进行数值计算的训练，学习各章算法完全是为用于实际计算，必须真会算。,27,数值分析 Numerical Analysis,（3）本课程学习结束后你应具备的能力： 对具体的数值计算问题，你会选择合适的算法，并通过计算机计算出正确结果；对给定的算法会从理论上分析其优劣性；会根据原理构造解决较简单数值计算问题的算法。 （4）本课程的现实关联性（强应用性）： 简单数学用表如平方表、开方表、三角函数表；现在计算机中的函数计算、所有程序中的基本函数的计算（包括计算器）；（插值方法）用于数码相机增加图像的分辨率。,28,数值分析 Numerical Analysis,1.2 数值计算的误差,1.2.1 误差来源与分类 1.2.2 误差与有效数字 1.2.3 数值运算的误差估计,29,数值分析 Numerical Analysis,1.2.1 误差来源与分类,误差是人们用来描述数值计算中近似解的精确程度，是科学计算中的一个十分重要的概念。 模型误差(Modeling Error)，也称描述误差，是数学模型与实际问题的差异。反映实际问题有关量之间的计算公式（数学模型）通常是近似的。 观测误差(Measurement Error)指物理数据的不可靠性。数学模型中包含的某些参数是通过观测或实验得到的。 注：通常可以根据测量工具的精度知道这类误差的上限。,30,数值分析 Numerical Analysis,截断误差(Truncation Error)，也称方法误差，一般指求某数学问题的数值解时，用有限的过程代替无限的过程所产生的误差，或用易于计算的问题代替不易计算的问题所产生的误差，亦即近似解与精确解之间的误差。,例1.1,例1.2 用差商近似导数产生的误差也是截断误差。,，,，,例1.3,31,数值分析 Numerical Analysis,舍入误差(Roundoff Error)，也称计算误差，是由于计算机的字长有限，原始数据在计算机上表示时产生的误差，或者计算过程中产生的误差。 在十进制运算中一般采用“四舍五入”法（四舍六入法）导致舍入误差，分析初始数据的误差通常归结为舍入误差。,例1.4 用3.14159近似代替 产生的误差,32,数值分析 Numerical Analysis,例1.5 近似计算 解：将 作Taylor展开后再积分 记 则 称为截断误差。,33,数值分析 Numerical Analysis,在数值分析中，总是假定数学模型正确合理地反映了客观实际问题，因而不考虑模型误差和观测误差，主要研究截断误差和舍入误差对计算结果的影响。,34,数值分析 Numerical Analysis,1.2.2 误差与有效数字,任何复杂计算问题的误差分析本质上都归结为数的误差估计。 绝对误差 相对误差 有效数字 度量间的关系,35,数值分析 Numerical Analysis, 绝对误差,定义1.1 设 是准确值 的一个近似值，称 为 近似 的绝对误差，简称为误差。 在不引起混淆时，符号 可简记作 或 。 如果存在正数 满足 ，则称 为 近似 的绝对误差界（限），简称为误差界（限）。常记为,36,数值分析 Numerical Analysis,注1：绝对误差是：近似值 - 准确值（有的教材指：准确值-近似值）； 注2：绝对误差是有量纲单位的量，并且可能取正值或负值。 注3：通常计算中所要求的误差，是指估计一个尽可能小的绝对误差限； 注4：绝对误差越小越具有参考价值。,37,数值分析 Numerical Analysis,38,数值分析 Numerical Analysis, 相对误差,绝对误差限虽然能够刻划对同一真值不同近似的好坏，但它不能刻划对不同真值近似程度的好坏。 例1.7 测量1公里的长度时有5米的误差，测量100米的长度时有1米的误差。就绝对误差而言，前者是后者的5倍，但这并不意味着后一种测量更精确，因为若考虑到被测量的数量本身的大小，前者的测量误差所占的比例为0.5%，而后者的误差所占的比例为1%，在这个层面上应该说前一种测量更精确些。,39,数值分析 Numerical Analysis,例1.8 在某种考试中，总分150分考139，总分100分考90，两者的绝对误差分别为11和10，优劣如何？ 因此，刻画近似值的精确程度，不仅要看绝对误差的大小，也要考虑近似数本身的大小。为此我们引入相对误差的概念。,40,数值分析 Numerical Analysis,定义1.2 设 是准确值 的一个近似，称 为 近似 的相对误差。在不引起混淆时，符号 可以简记为 或 。 在实际计算中，由于真值（准确值） 总是未知的，通常取 为 近似 的相对误差。,41,数值分析 Numerical Analysis,在前面的考试成绩分析例子中， 前者相对误差(150139)/150=0.073， 后者相对误差(100-90)/100=0.100， 显然前者的成绩更优。,42,数值分析 Numerical Analysis,注1：当准确值时，相对误差没有意义； 注2：相对误差可正可负，是一个无量纲量，通常用百分比表示； 相对误差及相对误差限是无量纲的，但绝对误差以及绝对误差限是有量纲的； 注3：通常要求计算的相对误差，是指估计一个尽可能小的相对误差限。 注4：近似值的精确程度取决于相对误差的大小。,43,数值分析 Numerical Analysis,44,数值分析 Numerical Analysis, 有效数字,定义1.3 若近似值 的误差界 是它某一数位的半个单位，该位到 的第一位非零数字一共有 位，则称近似值 有 位有效数字，或说 精确到该位。,45,数值分析 Numerical Analysis,定义1.3 设 的近似值 有如下标准形式 其中 ， 且 。 如果 为满足 的最大非负整数，则称 为 的具有 位（十进制）有效数字的近似值，或 有 位有效数字。 当 准确到最后一位（末位）时，则称 为有效数。,46,数值分析 Numerical Analysis,47,数值分析 Numerical Analysis,注1：有效数的误差限是末位数单位的一半，可见有效数本身就体现了误差界； 注2：对真值进行四舍五入得到有效数； 注3：准确数字有无穷多位有效数字； 注4：从实验仪器所读的近似数（最后一位是估计位）不是有效数，估计最后一位是为了确保对最后一位进行四舍五入得到有效数。 例如从最小刻度为厘米的标尺读得的数据123.4cm是为了得到有效数123.cm，读得数据156.7cm是为了得到有效数157.cm。,48,数值分析 Numerical Analysis,例1.12 写出下列各数的具有5位有效数字的近似值 187.9325，0.03785551，8.000033, 2.7182818 解：按定义（或四舍五入原则），上述各数的具有5位有效数字的近似值分别为 187.93, 0.037856, 8.0000, 2.7183 注5：数字末尾的0不可以随意添加或省略。,49,数值分析 Numerical Analysis, 度量间的关系,从前面的例子不难发现，近似值的有效数字位数越多，相对误差界就可以越小，反之亦然。,50,数值分析 Numerical Analysis,定理1.1实质上给出了一种求相对误差限的方法。,51,数值分析 Numerical Analysis,52,数值分析 Numerical Analysis,53,数值分析 Numerical Analysis,1.2.3 数值运算的误差估计, 四则运算的误差估计,54,数值分析 Numerical Analysis,55,数值分析 Numerical Analysis, 函数值的误差估计,当自变量有误差时，计算函数值也会产生误差，其误差可以利用函数的泰勒展开式进行估计。,56,数值分析 Numerical Analysis,57,数值分析 Numerical Analysis,1.3 误差定性分析与避免误差危害,1.3.1 误差的传播 1.3.2 算法的数值稳定性 1.3.3 病态问题与条件数 1.3.4 避免误差危害的若干原则,58,数值分析 Numerical Analysis,一个工程或科学计算问题往往要运算千万次，由于每步运算都有误差，如果每步都做误差分析是不可能的，也不科学。 因为误差积累有正有负，绝对值有大有小，都按最坏情况估计误差限得到的结果比实际误差大得多，这种保守的误差估计不反映实际误差积累。,59,数值分析 Numerical Analysis,1.3.1 误差的传播, 误差传播及其表现 与误差相关的两个术语 常用的误差分析方法,60,数值分析 Numerical Analysis, 误差传播及其表现,近似数参加运算后所得的值一般也是近似值，含有误差，将这一现象称为误差传播。 初始误差导致后续计算结果产生误差，我们称其为初值误差传播。,61,数值分析 Numerical Analysis,误差传播的表现,（1）算法本身可能有截断误差； （2）初始数据在计算机内的浮点表示一般有舍入误差； （3）每次运算一般又会产生新的舍入误差，并传播以前各步已经引入的误差； （4）误差有正有负，误差积累的过程一般包含有误差增长和误差相消的过程，并非简单的单调增长； （5）运算次数非常之多，不可能人为地跟踪每一步运算。,62,数值分析 Numerical Analysis, 与误差相关的两个术语,假设在某些条件下推导出一个理论上的误差界，如果这个界不依赖于计算结果，则称它为先验界或先验估计；如果这个界依赖于计算结果，即是说，仅在计算完成后利用计算的结果才能具体确定这个界，则称它为后验界或后验估计。,63,数值分析 Numerical Analysis, 常用的误差分析方法,向前误差分析方法与向后误差分析方法 区间分析法 概率分析法,64,数值分析 Numerical Analysis,向前误差分析方法与向后误差分析方法,向前误差分析是对每一步运算找出舍入误差界，随计算过程逐步向前分析，直至计算出最后结果的舍入误差的界。 向后误差分析法是一种先验估计，特别在矩阵计算的误差分析中有比较系统的研究，取得了较大的进展。而向前误差分析法只能应用于十分简单的情形。,65,数值分析 Numerical Analysis,区间分析法,穆尔,Moore，20世纪60年代 把参加运算的数都看成区间量，按照区间运算规则求得最后结果的近似值和误差界。,66,数值分析 Numerical Analysis,概率分析法,利用概率统计方法，将数据和运算中的舍入误差视为适合某种分布的随机变量，然后确定计算结果的误差分布。,67,数值分析 Numerical Analysis,1.3.2 算法的数值稳定性,一种算法，如果在执行它的过程中舍入误差在一定条件下能够得到控制（或者说舍入误差的增长不影响产生可靠的结果），则称它是数值稳定的，否则称为数值不稳定的。 定义1.4（教材P10，定义3） 一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定的。,68,数值分析 Numerical Analysis,算法数值稳定的一个必要条件是：原始数据的微小变化只会引起最后结果有微小的变化。具体地说，假定原始数据有误差 ，而且算法执行过程中的一切误差仅由 引起，设结果的误差为 ，那么稳定的算法必满足“当 相对于原始数据不太大时， 相对于结果也不太大”。 如果一种数值方法有初始误差 ，由它引起此后运算 步的误差是 ，常遇到下面两种情形，其中的 是与 无关的常数：,69,数值分析 Numerical Analysis,（1）如果 ,称误差的增长是线性型的； （2）如果 ,称误差的增长是指数型的。 例1.16 计算 并估计误差。,70,数值分析 Numerical Analysis,71,数值分析 Numerical Analysis,72,数值分析 Numerical Analysis,73,数值分析 Numerical Analysis,74,数值分析 Numerical Analysis,75,数值分析 Numerical Analysis,1.3.3 病态问题与条件数,对一个数值问题本身，如果输入数据有微小扰动（即误差），引起输出数据（即问题解）相对误差很大，这就是所谓病态问题。 计算函数值问题的条件数 :,76,数值分析 Numerical Analysis,77,数值分析 Numerical Analysis,1.3.4避免误差危害的若干原则,数值计算中首先要分清问题是否病态和算法是否数值稳定，计算时还应尽量避免误差危害，防止有效数字的损失，有下面若干原则。 避免相近数相减 避免除法中除数的数量级远小于被