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

2020 3 25 1 2020 3 25 第1章数值分析与科学计算引论 2 第1章数值分析与科学计算引论 数值分析研究对象 作用与特点数值计算的误差误差定性分析与避免误差危害数值计算中算法设计的技术数学软件 2020 3 25 第1章数值分析与科学计算引论 3 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 1研究对象用计算机求解数学问题的数值计算方法 理论及软件实现 应用数学 计算数学即数值分析 数值分析 计算方法 的研究对象 理论与计算结合 插值与函数逼近 2 3 数值微分与数值积分 4 非线性方程数值解 7 数值线性代数 5 6 8 常微与偏微分方程的数值解 9 等 1 1数值分析的对象 作用与特点 2020 3 25 第1章数值分析与科学计算引论 4 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 例考虑线性方程组数值解问题 相关理论与精确解法根据方程的特点研究算法及相关理论 纯数学 计算数学 3数值分析特点面向计算机提供有效算法 TSP问题可靠的理论分析 精度 收敛 稳定 好的计算复杂性 时 空 阿基米德 刘徽 祖冲之数值实验B C 3A D 3A D 5 2数值分析作用科学研究的手段 科学理论 科学实验与科学计算 2020 3 25 第1章数值分析与科学计算引论 5 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 1 2数值计算的误差 1误差分类 模型误差 数学模型实际问题观测误差 由观测产生截断误差 方法误差 近似解精确解舍入误差 计算机字长的限制 不讨论 2误差与有效数字 记x为准确值 x 为x的一个近似值 定义1称为近似值的绝对误差 简称误差 强近似值 当弱近似值 当 2020 3 25 第1章数值分析与科学计算引论 6 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 误差限 误差绝对值的上界 不能完全反映近似值的好坏 相对误差 相对误差限 可反映出近似程度的好坏 定义2有效数字若近似值的误差限是某一位的半个单位 该位到的第一位非零数字共有n位 就说有n位有效数字 2020 3 25 第1章数值分析与科学计算引论 7 注 有效位数与小数点后有多少位无关 m相同情况下 有效位数越多 误差限越小 相对误差及相对误差限是无量纲的 绝对误差及误差限是有量纲的 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 2020 3 25 第1章数值分析与科学计算引论 8 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 3数值运算的误差估计 2020 3 25 第1章数值分析与科学计算引论 9 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 1 3误差定性分析及避免误差危害 概率分析法向后误差分析法区间分析法 1 病态问题与条件数 病态问题 输入 微小的扰动 输出 相对误差很大 条件数 2020 3 25 第1章数值分析与科学计算引论 10 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 2 算法的数值稳定性 定义3一个算法如果输入数据有误差 而在计算过程中舍入误差不增长 则称此算法是数值稳定的 否则称此算法为不稳定的 例1 1 P 2020 3 25 第1章数值分析与科学计算引论 11 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 2020 3 25 第1章数值分析与科学计算引论 12 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 3 误差危害的避免 1 避免除数的绝对值远远小于被除数绝对值的除法 2 避免两相近数相减 引起有效数字严重损失 3 防止大数吃小数 4 简化计算步骤 减少运算次数 秦九韶 Horner 5 数值稳定性 2020 3 25 第1章数值分析与科学计算引论 13 研究对象作用特点 数值计算误差 误差分析避免危害 数值计算算法设计 数学软件 算法设计的三种基本技术 1 化大为小的缩减技术Zeno悖论古希腊哲学家结绳记数 13 10 1101 2 2 化难为易的校正技术用四则运算计算开方 3 化粗为精的松弛技术 1 数值计算中算法设计的技术 周易 系辞下 说 上古结绳而治 后世圣人 伏羲 易之以书契 2020 3 25 第1章数值分析与科学计算引论 14 2020 3 25 第2章插值法 15 第2章插值法 引言拉格朗日 Lagrange 插值均差与牛顿 Newton 插值埃尔米特 Hermite 插值分段低次插值三次样条插值 2020 3 25 第2章插值法 16 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2 1引言 在科学计算中经常要用较简单的函数来逼近较复杂的函数 按函数逼近问题提法的不同 通常有插值 函数逼近及曲线拟合等三种问题 1 插值设函数 在点 上的函数值分别为 求一简单函数 使 2 1 0 2020 3 25 第2章插值法 17 称点 为插值节点 区间 为插值区间 为被插值函数 为 的插值函数 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 由于多项式具有结构简单 数值计算和理论分析都很方便的优点 因此通常取为多项式 相应的插值法称为多项式插值 2020 3 25 第2章插值法 18 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2 函数逼近设为定义在区间上的某类函数构成的线性空间 为的子集 对于 求 使与的差在某种度量意义下最小 这就是函数逼近问题 通常取为连续函数空间 而通常是多项式 有理函数或三角多项式函数等 2020 3 25 第2章插值法 19 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 20 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2 2拉格朗日插值 n次插值多顶式 1线性插值 一次 2020 3 25 第2章插值法 21 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 利用函数的零点及一次多项式性质 由待定系数法可求得 2020 3 25 第2章插值法 22 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2抛物插值 二次 由待定系数法可求得 2020 3 25 第2章插值法 23 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 24 3拉格朗日插值多项式 将线性与抛物型插值推广到一般的情形 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 25 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 26 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 证明设所求的插值多项式为则由插值条件得关于的线性方程组 从而线性方程组有唯一解 这就证明了的存在唯一性 2020 3 25 第2章插值法 27 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 4插值余项与误差估计 2020 3 25 第2章插值法 28 例2 1已知 1 用线性插值及抛物插值计算的近似值 2 并问它们各有几位有效数字 3 求抛物插值的误差 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 29 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 再用抛物插值计算 取 由抛物插值公式得 所以 因此用抛物插值所得的近似值具有4位有效数字 线性插值仅用两个节点上的信息 精度自然较低 而抛物插值用了三个节点上的信息 精度通常会有所提高 2020 3 25 第2章插值法 30 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 这又一次说明了用抛物插值所得的近似值具有4位有效数字 2020 3 25 第2章插值法 31 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2 3均差与牛顿插值 一阶均差 二阶均差 K阶均差 承袭性 1均差及其性质 2020 3 25 第2章插值法 32 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2牛顿插值公式 可克服Lagrange插值法无承袭性的缺点 2020 3 25 第2章插值法 33 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 差商表 2020 3 25 第2章插值法 34 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 例2 2 解 的表达式中前两项为线性插值 加上第三项后为二次插值 与前例比较结果是相同的 2020 3 25 第2章插值法 35 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 前面讨论插值问题只提函数值条件 没有导数条件 有些实际问题不但要求插值函数与被插值函数在节点上函数值相同 即 过点 而且要求导数值也相同 即 相切 有时甚至要求高阶导数也相同 满足这种既要求函数值相同也要求导数值相同的插值多项式称为Hermite插值多项式 函数值的个数与导数值的个数可以不等也可以相等 下面分别用基于承袭性方法及基函数方法来讨论 2 4埃尔米特插值 2020 3 25 第2章插值法 36 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 先考虑函数值的个数与导数值的个数不等的情形 以一个具体问题为例进行讨论 问题的提法为已知 求二次函数 使 这里给出了三个条件 可唯一地确定一个次数不超过二次的多项式 由于前两个条件可确定一个一次函数 正是Lagrange插值函数 因此可令 从而 由第三个条件得 2020 3 25 第2章插值法 37 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 再考虑函数值的个数与导数值的个数相等且具有个节点的一般情形 2020 3 25 第2章插值法 38 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 39 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 定理满足插值条件的多项式是存在唯一的 证明存在性的证明已由前面的构造而得 下面证明唯一性 设也是满足插值条件且次数不超过2n 1的多项式 令 2020 3 25 第2章插值法 40 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 与Lagrange插值余项定理类似地有下列Hermite插值余项定理 其证明方法也相似 定理 2020 3 25 第2章插值法 41 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 42 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 例2 3求满足条件且次数不超过三的Hermite插值多项式 解 例2 4 证 2020 3 25 第2章插值法 43 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2 5分段低次插值 插值多项式的次数是随着插值节点的增加而升高的 那么插值多项式的次数越高是否意味着逼近效果越好呢 2020 3 25 第2章插值法 44 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 1分段线性插值用折线来逼近曲线 2020 3 25 第2章插值法 45 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 46 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 定理 证明 2020 3 25 第2章插值法 47 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2分段三次Hermite插值 2020 3 25 第2章插值法 48 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 49 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2 6三次样条插值插值 2020 3 25 第2章插值法 50 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 由定义知在每个小区间上为次数不超过三次的多项式 有4个待定系数 共有n个小区间 故共有4n个待定系数 1 已知两端点的一阶导数值 即2 已知两端点的二阶导数值 即3 S x 为周期的周期函数时 求S x 的方法有多种 现以S x 的二阶导数表达S x 为例 2020 3 25 第2章插值法 51 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 2020 3 25 第2章插值法 52 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 对第一 第二种边界条件可得方程组 对第三种边界条件可得方程组 2020 3 25 第2章插值法 53 引言 拉格朗日插值 牛顿插值 埃尔米特插值 分段低次插值 三次样条插值 例2 4给定数据表如下 求满足边界条件的三次样条插值函数 2020 3 25 第3章函数逼近与曲线拟合 54 第3章函数逼近与曲线拟合 函数逼近基本概念正交多项式最佳一致逼近最佳平方逼近曲线拟合的最小二乘法 2020 3 25 第3章函数逼近与曲线拟合 55 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 3 1函数逼近基本概念 1函数逼近与函数空间函数逼近 对函数类A中给定的函数f x A 要求在另一类简单的便于计算的函数类B中求函数p x B 使p x 与f x 的误差在某种度量意义下最小 一般A C a b B通常为多项式 有理函数和分段低次多项式 基本概念 线性相关 线性无关 基 坐标 n维空间 无限维空间 2020 3 25 第3章函数逼近与曲线拟合 56 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2020 3 25 第3章函数逼近与曲线拟合 57 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2范数与赋范空间 2020 3 25 第3章函数逼近与曲线拟合 58 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 3内积与内积空间 2020 3 25 第3章函数逼近与曲线拟合 59 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 内积空间X上可引入范数满足范数的三条性质 2020 3 25 第3章函数逼近与曲线拟合 60 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 3 2正交多项式 1正交函数族与正交多项式 2020 3 25 第3章函数逼近与曲线拟合 61 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2020 3 25 第3章函数逼近与曲线拟合 62 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2020 3 25 第3章函数逼近与曲线拟合 63 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2勒让德 Legendre 多项式 2020 3 25 第3章函数逼近与曲线拟合 64 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 性质1 Legendre多项式在区间上带权正交 并且 2020 3 25 第3章函数逼近与曲线拟合 65 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 3切比雪夫 Chebyshev 多项式 2020 3 25 第3章函数逼近与曲线拟合 66 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 性质 2020 3 25 第3章函数逼近与曲线拟合 67 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 4其它常用正交多项式 1 第二类Chebyshev多项式 2 拉盖尔 Laguerre 多项式 3 Hermite多项式 2020 3 25 第3章函数逼近与曲线拟合 68 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 3 3最佳一致逼近 2020 3 25 第3章函数逼近与曲线拟合 69 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2020 3 25 第3章函数逼近与曲线拟合 70 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 3 4最佳平方逼近 问题可转化为求 法方程 1概念与计算 2020 3 25 第3章函数逼近与曲线拟合 71 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2020 3 25 第3章函数逼近与曲线拟合 72 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2020 3 25 第3章函数逼近与曲线拟合 73 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 当n较大时 法方程的系数矩阵H是严重病态的 所以通常采用正交函数特别是用正交多项式函数做基 以避免病态方程组的求解问题 2020 3 25 第3章函数逼近与曲线拟合 74 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2用正交函数作最佳平方逼近 2020 3 25 第3章函数逼近与曲线拟合 75 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2020 3 25 第3章函数逼近与曲线拟合 76 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2020 3 25 第3章函数逼近与曲线拟合 77 基本概念 正交多项式 最佳一致逼近 最佳平方逼近 曲线拟合最小二乘 2020 3 25 第3