数值分析第五版章课件.ppt

《数值分析第五版章课件.ppt》由会员分享，可在线阅读，更多相关《数值分析第五版章课件.ppt（91页珍藏版）》请在三一办公上搜索。

1、2022/12/5,1,2022/12/5,第1章 数值分析与科学计算引论,2,第1章 数值分析与科学计算引论,数值分析研究对象、作用与特点数值计算的误差误差定性分析与避免误差危害数值计算中算法设计的技术数学软件,2022/12/5,第1章 数值分析与科学计算引论,3,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,1 研究对象 用计算机求解数学问题的数值计算方法、理论及软件实现,应用数学,计算数学即数值分析,数值分析（计算方法）的研究对象,(理论与计算结合),插值与函数逼近（2、3）数值微分与数值积分（4）非线性方程数值解（7）数值线性代数（5、6、8）常微与偏

2、微分方程的数值解（9）等,1.1 数值分析的对象、作用与特点,2022/12/5,第1章 数值分析与科学计算引论,4,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,例 考虑线性方程组数值解问题,相关理论与精确解法根据方程的特点研究算法及相关理论,纯数学,计算数学,3 数值分析特点 面向计算机提供有效算法； TSP问题 可靠的理论分析（精度、收敛、稳定）; 好的计算复杂性（时、空）;阿基米德、刘徽、祖冲之 数值实验 B.C. 3 A.D.3 A.D.5,2 数值分析作用 科学研究的手段：科学理论、科学实验与科学计算,2022/12/5,第1章 数值分析与科学计算引

3、论,5,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,1.2 数值计算的误差,1 误差分类,模型误差: 数学模型 实际问题观测误差: 由观测产生截断误差/方法误差: 近似解 精确解舍入误差:计算机字长的限制,(不讨论),2 误差与有效数字,记x为准确值，x* 为 x的一个近似值,定义1 称 为近似值 的绝对误差，简称误差。,强近似值: 当弱近似值: 当,2022/12/5,第1章 数值分析与科学计算引论,6,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,误差限: 误差绝对值的上界,(不能完全反映近似值的好坏),相对误差:,相对误差

4、限: (可反映出近似程度的好坏),定义2 有效数字 若近似值 的误差限是某一位的半个单位，该位到 的 第一位非零数 字共有n位，就说 有n位有效数字。,2022/12/5,第1章 数值分析与科学计算引论,7,注: 有效位数与小数点后有多少位无关； m相同情况下，有效位数越多，误差限越小； 相对误差及相对误差限是无量纲的，绝对误差及误差限是有量纲的。,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,2022/12/5,第1章 数值分析与科学计算引论,8,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,3 数值运算的误差估计,2022/1

5、2/5,第1章 数值分析与科学计算引论,9,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,1.3 误差定性分析及避免误差危害,概率分析法 向后误差分析法 区间分析法,1. 病态问题与条件数,病态问题,输入(微小的扰动) 输出(相对误差很大),条件数,2022/12/5,第1章 数值分析与科学计算引论,10,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,2. 算法的数值稳定性,定义3 一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定 的。例1.1：P.,2022/12/5,第1章

6、 数值分析与科学计算引论,11,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,2022/12/5,第1章 数值分析与科学计算引论,12,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软件,3. 误差危害的避免,（1）避免除数的绝对值远远小于被除数绝对值的除法；（2）避免两相近数相减，引起有效数字严重损失；（3） 防止大数吃小数；（4） 简化计算 步骤，减少运算次数；秦九韶、Horner（5） 数值稳定性。,2022/12/5,第1章 数值分析与科学计算引论,13,研究对象作用特点,数值计算误差,误差分析避免危害,数值计算算法设计,数学软

7、件,算法设计的三种基本技术,（1）化大为小的缩减技术 Zeno悖论 古希腊哲学家 结绳记数（13）10=（1101）2（2）化难为易的校正技术 用四则运算计算开方（3）化粗为精的松弛技术,1. 数值计算中算法设计的技术,周易.系辞下说：“上古结绳而治，后世圣人（伏羲）易之以书契“。,2022/12/5,第1章 数值分析与科学计算引论,14,2022/12/5,第2章 插值法,15,第2章 插值法,引言拉格朗日（Lagrange）插值均差与牛顿（Newton）插值埃尔米特（Hermite）插值分段低次插值三次样条插值,2022/12/5,第2章 插值法,16,引言,拉格朗日插值,牛顿插值,埃尔米

8、特插值,分段低次插值,三次样条插值,2.1 引言,在科学计算中经常要用较简单的函数来逼近较复杂的函数。按函数逼近问题提法的不同，通常有插值、函数逼近及曲线拟合等三种问题。,（1）插值 设函数,在点,上的函数值分别为,，求一简单函数 ，使,（2.1）,0,2022/12/5,第2章 插值法,17,称点,为插值节点，区间,为插值区间，,为被插值函数，,为,的插值函数。,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,由于多项式具有结构简单，数值计算和理论分析都很方便的优点，因此通常取 为多项式。相应的插值法称为多项式插值。,2022/12/5,第2章 插值法,18,引言,拉

9、格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,（2）函数逼近 设 为定义在区间 上的某类函数构成的线性空间， 为 的子集，对于 ，求 ，使 与 的差在某种度量意义下最小，这就是函数逼近问题。,通常取为连续函数空间，而 通常是多项式、有理函数或三角多项式函数等。,2022/12/5,第2章 插值法,19,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2022/12/5,第2章 插值法,20,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2.2 拉格朗日插值,n次插值多顶式：,1 线性插值（一次）,2022/12/5,第2章 插

10、值法,21,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,利用函数的零点及一次多项式性质，由待定系数法可求得,2022/12/5,第2章 插值法,22,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2 抛物插值（二次）,由待定系数法可求得：,2022/12/5,第2章 插值法,23,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2022/12/5,第2章 插值法,24,3 拉格朗日插值多项式,将线性与抛物型插值推广到一般的情形,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2022/12/5

11、,第2章 插值法,25,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2022/12/5,第2章 插值法,26,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,证明 设所求的插值多项式为 则由插值条件得关于 的线性方程组,从而线性方程组有唯一解。这就证明了 的存在唯一性。,2022/12/5,第2章 插值法,27,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,4 插值余项与误差估计,2022/12/5,第2章 插值法,28,例2.1 已知 （1）用线性插值及抛物插值计算 的近似值；（2）并问它们各有几位有效数字；（3）

12、求抛物插值的误差。,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2022/12/5,第2章 插值法,29,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,再用抛物插值计算，取,由抛物插值公式得：,所以,因此用抛物插值所得 的近似值具有4位有效数字。,线性插值仅用两个节点上的信息，精度自然较低，而抛物插值用了三个节点上的信息，精度通常会有所提高。,2022/12/5,第2章 插值法,30,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,这又一次说明了用抛物插值所得的近似值具有4位有效数字。,2022/12/5,第2章 插

13、值法,31,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2.3 均差与牛顿插值,一阶均差:二阶均差:K阶均差:,承袭性,1 均差及其性质,2022/12/5,第2章 插值法,32,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2 牛顿插值公式,可克服Lagrange插值法无承袭性的缺点。,2022/12/5,第2章 插值法,33,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,差商表,2022/12/5,第2章 插值法,34,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,例2.2,解,的表达

14、式中前两项为线性插值，加上第三项后为二次插值，与前例比较结果是相同的。,2022/12/5,第2章 插值法,35,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,前面讨论插值问题只提函数值条件，没有导数条件。有些实际问题不但要求插值函数与被插值函数在节点上函数值相同，即“过点”，而且要求导数值也相同，即“相切”，有时甚至要求高阶导数也相同。满足这种既要求函数值相同也要求导数值相同的插值多项式称为Hermite插值多项式。函数值的个数与导数值的个数可以不等也可以相等，下面分别用基于承袭性方法及基函数方法来讨论。,2.4 埃尔米特插值,2022/12/5,第2章 插值法,3

15、6,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,先考虑函数值的个数与导数值的个数不等的情形，以一个具体问题为例进行讨论。 问题的提法为已知 ，求二次函数 ，使,这里给出了三个条件，可唯一地确定一个次数不超过二次的多项式。由于前两个条件可确定一个一次函数，正是Lagrange插值函数 ，因此可令,从而,由第三个条件得,2022/12/5,第2章 插值法,37,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,再考虑函数值的个数与导数值的个数相等且具有 个节点的一般情形。,2022/12/5,第2章 插值法,38,引言,拉格朗日插值,牛顿插值,埃尔

16、米特插值,分段低次插值,三次样条插值,2022/12/5,第2章 插值法,39,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,定理 满足插值条件 的多项式 是存在唯一的。,证明 存在性的证明已由前面的构造而得，下面证明唯一性。 设 也是满足插值条件且次数不超过2n1的多项式，令,。,2022/12/5,第2章 插值法,40,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,与Lagrange插值余项定理类似地有下列Hermite插值余项定理，其证明方法也相似。,定理,2022/12/5,第2章 插值法,41,引言,拉格朗日插值,牛顿插值,埃尔米特

17、插值,分段低次插值,三次样条插值,2022/12/5,第2章 插值法,42,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,例2.3 求满足条件 且次数不超过三的Hermite插值多项式,解,例2.4,证：,2022/12/5,第2章 插值法,43,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2.5 分段低次插值,插值多项式的次数是随着插值节点的增加而升高的，那么插值多项式的次数越高是否意味着逼近效果越好呢？,2022/12/5,第2章 插值法,44,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,1 分段线性插值 用

18、折线来逼近曲线。,2022/12/5,第2章 插值法,45,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2022/12/5,第2章 插值法,46,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,定理,证明,2022/12/5,第2章 插值法,47,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2 分段三次Hermite插值,2022/12/5,第2章 插值法,48,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2022/12/5,第2章 插值法,49,引言,拉格朗日插值,牛顿插值,埃尔米特插

19、值,分段低次插值,三次样条插值,2.6 三次样条插值插值,2022/12/5,第2章 插值法,50,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,由定义知在每个小区间上为次数不超过三次的多项式，有4个待定系数，共有n个小区间，故共有4n个待定系数。,1）已知两端点的一阶导数值，即2）已知两端点的二阶导数值，即3）S(x)为周期的周期函数时,求S(x)的方法有多种，现以S(x)的二阶导数表达S(x)为例。,2022/12/5,第2章 插值法,51,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,2022/12/5,第2章 插值法,52,引言,拉格

20、朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,对第一、第二种边界条件可得方程组,对第三种边界条件可得方程组,2022/12/5,第2章 插值法,53,引言,拉格朗日插值,牛顿插值,埃尔米特插值,分段低次插值,三次样条插值,例2.4 给定数据表如下：,求满足边界条件 的三次样条插值函数,2022/12/5,第3章 函数逼近与曲线拟合,54,第3章 函数逼近与曲线拟合,函数逼近基本概念正交多项式最佳一致逼近最佳平方逼近曲线拟合的最小二乘法,2022/12/5,第3章 函数逼近与曲线拟合,55,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,3.1 函数逼近基本概

21、念,1 函数逼近与函数空间 函数逼近: 对函数类A中给定的函数f(x)A, 要求在另一类简单的便于计算的函数类B中求函数p(x) B, 使p(x)与f(x)的误差在某种度量意义下最小。 一般A Ca,b ,B通常为多项式、有理函数和分段低次多项式。,基本概念: 线性相关、 线性无关、 基、坐标、n维空间、无限维空间。,2022/12/5,第3章 函数逼近与曲线拟合,56,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,57,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2 范数与赋范空间,2022/12/

22、5,第3章 函数逼近与曲线拟合,58,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,3 内积与内积空间,2022/12/5,第3章 函数逼近与曲线拟合,59,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,内积空间X上可引入范数 满足范数的三 条性质,2022/12/5,第3章 函数逼近与曲线拟合,60,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,3.2 正交多项式,1 正交函数族与正交多项式,2022/12/5,第3章 函数逼近与曲线拟合,61,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12

23、/5,第3章 函数逼近与曲线拟合,62,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,63,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2 勒让德（Legendre）多项式,2022/12/5,第3章 函数逼近与曲线拟合,64,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,性质1. Legendre多项式 在区间 上带权 正交，并且,2022/12/5,第3章 函数逼近与曲线拟合,65,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,3 切比雪夫（ Cheby

24、shev ）多项式,2022/12/5,第3章 函数逼近与曲线拟合,66,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,性质,2022/12/5,第3章 函数逼近与曲线拟合,67,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,4 其它常用正交多项式,1.第二类Chebyshev多项式,2. 拉盖尔（Laguerre）多项式,3. Hermite多项式,2022/12/5,第3章 函数逼近与曲线拟合,68,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,3.3 最佳一致逼近,2022/12/5,第3章 函数逼近与曲线拟合,69,基本

25、概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,70,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,3.4 最佳平方逼近,问题可转化为求,法方程,1 概念与计算,2022/12/5,第3章 函数逼近与曲线拟合,71,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,72,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,73,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线

26、拟合最小二乘,当n较大时，法方程的系数矩阵H是严重病态的，所以通常采用正交函数特别是用正交多项式函数做基，以避免病态方程组的求解问题。,2022/12/5,第3章 函数逼近与曲线拟合,74,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2 用正交函数作最佳平方逼近,2022/12/5,第3章 函数逼近与曲线拟合,75,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,76,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,77,基本概念,正交

27、多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,78,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,79,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,3.5 曲线拟合的最小二乘法,1 最小二乘及其计算,2022/12/5,第3章 函数逼近与曲线拟合,80,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,81,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,202

28、2/12/5,第3章 函数逼近与曲线拟合,82,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,83,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,84,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,85,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,86,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,87,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2 用正交函数作最小二乘拟合,2022/12/5,第3章 函数逼近与曲线拟合,88,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,89,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,2022/12/5,第3章 函数逼近与曲线拟合,90,基本概念,正交多项式,最佳一致逼近,最佳平方逼近,曲线拟合最小二乘,此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！,