《【6A文】数值分析》由会员分享，可在线阅读，更多相关《【6A文】数值分析（554页珍藏版）》请在金锄头文库上搜索。
1、数 值 分 析 (科学与工程计算基础),主讲：雷 秀 仁 华南理工大学理学院数学系,教材,应用数值分析 郑咸义等 编著 （华南理工大学出版社） 参考书目 Numerical Analysis:Mathematics of Scientific Computing (Third Edition) David Kincaid & Ward Cheney（机械工业出版社) Numerical Analysis (Seventh Edition) Richard L. Burden & J. Douglas Faires （高等教育出版社）,数值分析的研究对象,数值分析属于计算数学的范畴，是数学的一
2、个分支，也称为数值计算方法、计算方法、数值方法等。 其研究对象是求解各种数学问题的数值方法的设计、分析及其有关的数学理论和具体实现的一门学科。 它是科学与工程计算（科学计算）的基础。,许多科学与工程实际问题（如：核武器的研制、导弹的发射、气象预报等）的解决都离不开科学计算。 目前，理论、试验、计算已成为人类进行科学活动的三大方法。,数值分析的研究对象,科学计算的过程，是从数学模型的提出到上机计算得出结果的完整过程。（下图表明了其中的主要步骤和相互关系 ）,数值分析研究的对象,数值分析研究的对象,数值分析是数学、计算机科学与其他学科交叉的产物。,本门课程将着重介绍进行科学计算所必须掌握的一些最基
3、本、最常用的数值方法（数值算法），并作相关分析。,数值分析的任务,对典型的数学问题给出数值求解方法(近似方法)，并对算法进行理论分析，使得其能够在计算机有效地得以实现。 数值算法的构造 算法的理论分析,数值分析的任务,针对数值问题研究可在计算机上执行且行之有效 的计算公式（数值算法）。 例：解线性方程组，已有Cramer法则，但不可行。, 数值算法的分析，主要包括误差分析（数值问题的性态，数值方法的截断误差、舍入误差和稳定性、收敛性等）和复杂性分析（计算量、存储量）。,课程目的, 学习一些常用的数值方法，掌握 数值方法的基本理论，为进一步 研究和使用更复杂的数值算法奠定 基础。,初步掌握一种科
4、学计算软件包 （如Matlab）的使用方法。,课程主要内容,插值方法； 曲线拟合与函数逼近； 数值逼近 数值积分与数值微分； 线性代数方程组数值求解的直接法； 线性代数方程组数值求解的迭代法； 数值代数 非线性方程与方程组数值求解； 常微分方程数值求解。 Matlab 简介,第一章 绪 论,主要内容： 一些常用概念； 数值算法的复杂度与稳定性。 数值计算中的误差； 数值算法设计的若干原则；,1.数值分析中常用的一些概念,数值问题 数值解 算法 计算量 病态问题 算法数值稳定性,数值问题、数值解 、算法,由一组已知数据（输入数据），求出一组结果数据（输出数据），使得这两组数据之间满足预先制定的某
5、种关系的问题，称为数值问题。 由数值计算公式算出的数值形式的解(通常由计算机计算得到)称为数值解。一般数值解是近似解。 由给定的已知量，经过有限次的四则运算及规定的运算顺序，求出所关心的未知量的数值解，这样所构成的整个计算步骤，称为数值算法（简称算法）。,计算量,一个算法所需要的乘法和除法总次数称为计算量。计算量的单位为flop，表示完成一次浮点数乘或除法所需要的时间。算法的计算量可以衡量算法的优劣，因为它体现着算法的计算效率，通常算法的计算量越小，则算法的计算效率越高，因而该算法也越好。 由于计算机做加减法要比乘除法快得多，故算法的计算量可以不考虑加减法的时间。 例: 设A，分别为1020，
6、2050，5010的矩阵，计算 D=ABC 就有如下不同的算法和计算量 算法1：D=(AB)C 计算量 N1=15000 flop; 算法2：D=A(BC) 计算量 N2=12000 flop.,病态问题,因初始数据的微小变化，导致解产生剧烈变化问题称为病态问题。病态问题也称为坏问题，这类问题通常是问题本身固有的。 求解病态问题应该特别注意，因为实际问题的数据都是近似的或经计算机计算要对输入数据做舍入处理，这都引起原始数据的扰动，若所求解的正好是个病态问题，则采用通常算法计算就会出现很隐蔽的错误，导致不良的后果。病态问题在函数计算、方程求根及方程组求解中都是存在的，它的计算或求解应用专门的方法
7、或将其转化为非病态问题来求解。,例：病态的方程组,考察方程组 和 上述方程组尽管只是右端项有微小扰动，但解大不相同： 一个是 ，一个是 。 这类方程组称为病态的。,算法的数值稳定性,在计算过程中产生的舍入误差能被控制在一定的范围内，且对最后的结果影响不大的算法称为数值稳定算法。不是数值稳定的算法称为数值不稳定算法。 数值不稳定算法会导致计算结果失真，对数值不稳定的算法常采用转化成相应的数值稳定的算法来处理 。,2.对算法所要考虑的问题,计算速度。 例如，求解一个20阶线性代数方程组，若用克莱姆法则要进行约 次乘法运算，如用每秒1亿次乘法运算的计算机要30万年。而用Gauss消去法只需约3000
8、次乘法运算，用普通微机1秒之内便可算出结果。,2. 存储量。 大型问题有必要考虑。,3. 收敛性。 不收敛的算法无使用价值。 4. 数值稳定性。 在大量计算中，舍入误差的积累能否控制住，这与算法有关。,3. 数值计算中的误差,来源及种类 - 模型误差、参数误差、 截断误差、舍入误差。,1. 模型误差（也称描述误差） 模型误差是在建立数学模型时，由于忽略了一些次要因素 而产生的误差，它是数学建模阶段要考虑的误差，不是计算 方法可以解决的。,2. 参数误差（也称观测误差） 测量已知参数时，数据带来的误差 ，它也不是计算方法 能解决的问题。,数值计算中的误差,3. 截断误差（也称方法误差） 截断误差
9、是对参与计算的数学公式做简化可行处理后所产 生的误差（用有限过程代替无限过程或用容易计算的方法代 替不容易计算的方法），即数学模型的数值解与精确解之间 的误差，是计算方法关注的内容。（举例：P6 sinx = ）,4. 舍入误差（也称计算误差） 舍入误差是由于计算机只能表示有限位数字，因而只能取 有限位数进行计算所得的误差，它也是计算方法关注的内容。 （举例： ）,数值计算中的误差,误差的基本概念 绝对误差 - 近似数 x * 关于准确数 x 的绝对误差： E(x) = x x *（或 E(x *) = x x * ） - 近似数 x * 关于准确数 x 的绝对误差限： E(x)= x x *
10、 - 工程上表示准确数 x 的范围： x * x x * + 或 x = x * - 函数值的绝对误差： Ef (x) f (x) E(x) （利用微分中值公式导出） 举例：f (x) = x3,数值计算中的误差,相对误差 - 近似数 x * 关于准确数 x 的相对误差：,- 函数值的相对误差限：,- 近似数 x * 关于准确数 x 的相对误差限：,数值计算中的误差,有效数字 - 用 x * 表示 x 时准确到小数点后第 k 位：,- 近似数 x * 具有 n 位有效数字：,举例,数值计算中的误差,有效数字与相对误差的关系 - n 位有效数字的近似数 x * 其相对误差：,- 相对误差为 的近
11、似数 x * 至少具有 n 位有效数字。,注：在未标明近似数的绝对误差时默认该近似数准确到末位数字， 从其最左边的非零数字起直到最右边的一位数字止均为有效数字。,4. 数值计算中应注意的几个问题,若干原则 - 注意简化计算步骤，减少运算次数； （例：秦九韶算法) 避免两个相近的数相减，减少有效 数字的损失；（例） 使用数值稳定的算法;（例:习题1.16） 小心处理病态的数学问题；,复习题,习题 1.1(3)(4)、1.2、1.3、1.4、 1.6、1.9 (1) 、1.15、1.16,数值分析,2.1 插值问题的提出,第二章 函数近似计算的插值法,插值问题的提出,求简单函数 P (x)，使得,
12、计算 f (x)可通过计算 P (x)来近似代替。如下图所示。,一、插值问题的数学提法,这就是插值问题, (*)式为插值条件,其插值函数的图象如图,（截断误差）,整体误差的大小反映了插值函数的好坏.,为了使插值函数更方便在计算机上运算,一般插值函数都使用代数多项式或有理函数.,本章讨论的就是(代数)多项式插值.,满足插值条件的多项式 P(x)是否存在且唯一？,2. 若满足插值条件的P(x)存在,又如何构造出P(x); 即插值多项式的常用构造方法有哪些？,3. 用P(x)代替f(x)的误差估计，即截断误差的估计；,对于多项式插值，我们主要讨论以下几个问题：,4. 当插值节点无限加密时，插值函数是
13、否收敛于 f(x)。,二、插值多项式的存在唯一性,且满足,-(1),上述方程组的系数行列式为n+1阶Vandermond行列式,定理1.,由Cramer法则,线性方程组(1)有唯一解,-(3),-(2),则满足插值条件,的次数 n 的插值多项式,存在且唯一.,虽然线性方程组(1)推出的插值多项式存在且唯一,但通过解线性方程组(1)求插值多项式却不是好方法.,数值分析, 2.2 Lagrange插值多项式,第二章 函数近似计算的插值法,若通过求解线性方程组(1)来求解插值多项式,系数 , 不但计算工作量较大, 且难于得到,的简单表达式.,一、 代数多项式的构造:,可通过找插值基函数的方法,得到插
14、值多项式!,十八世纪法国数学家Lagrange对以往的插值算法进 行研究与整理，提出了易于掌握和计算的统一公式， 称为Lagrange插值公式。 它的特例是线性插值公式和抛物线插值公式。,Lagrange插值多项式,1. 线性插值,已知两个插值点及其函数值：,插值节点,对应的函数值,求一次多项式,使得,由于方程组的系数行列式,所以，按Gramer法则，有唯一解,于是,容易验证，过点（x0，f0）与（x1，f1）直线方程就是式（B-1），如图2-3所示。,2. 抛物线插值,求一个二次多项式,使得,由于该方程组的系数行列式,所以，有唯一解。即满足这样条件的二次多项式是唯一确定的。,满足上述条件，所
15、以它就是所求的二次多项式。,容易验证，P2(x)是过点(x0, f0)、(x1, f1)与(x2, f2)三点的抛物线，如图2-4所示。,3. n 次Lagrange插值,求次数不超过 n 的多项式Pn(x) 。,使得,根据线性空间的理论,并且形式不是唯一的,且在不同的基下有不同的形式,且满足插值条件:,n+1次多项式,且,-(4),从而,令,即,由(4)式,可得,其中,-(6),-(5),这个改写了的Lagrange插值公式，在许多理论分析中是比较有用的。,Lagrange插值公式的标准型公式:,例1:,解:,且,在例1中,如果只给出两个节点169和225,也可以作插值 多项式,即1次Lagrange插值多项式,有两个插值基函数, 也就是Lagrange线性插值.,Lagrange线性插值基函数(一次插值)为,Lagrange线性插值多项式为,例2.,解:,Lagrange插值基函数为,Lagrange线性插值多项式为,所以,二、插值余项,满足,不会完全成立,因此, 插值多项式存在着截断误差, 那么我们怎样估 计这个截断误差呢？,则成立,根据Rolle定理,再由Rolle定理,依此类推,由于,所以,因此,即,定理1.,Lagrange型余项,n=1:,n=2:,设,则,插值基函数的性质,Lagrange插值算法特点
