《计算方法》PPT课件

1 计算方法 1 1计算方法研究的对象和特点计算方法实际上就是计算机上使用的数值计算方法 所以这门课程又称为数值计算方法或数值分析 它是专门研究求解各种数学问题的数值计算方法 现在 由于大多数科学计算都比较复杂 人工计算无法完成 而计算机科学的迅速发展和广泛应用提供了解决这些复杂问题的新途径 用计算机解决科学计算问题的一般过程 可以概括为 实际问题 数学模型 计算方法 程序设计 上机计算 结果分析 3 2020 4 20 主讲韩光朋 由实际问题应用有关科学知识和数学理论建立数学模型这一过程 通常作为应用数学的任务 而根据数学模型提出求解的计算方法直到编出程序上机算出结果 进而对计算结果进行分析 这一过程则是计算数学的任务 也是数值计算方法的研究对象 因此 数值计算方法就是研究用计算机解决数学问题的数值方法及其理论的科学 它的内容包括 误差理论 线性与非线性方程 组 的数值解 矩阵的特征值与特征向量计算 曲线拟合与函数逼近 插值方法 数值积分与数值微分 常微分方程与偏微分方程数值解等 4 2020 4 20 主讲韩光朋 计算方法要解决的几个问题 或研究的对象 5 2020 4 20 主讲韩光朋 把实际问题归结为数值问题由于电子数字计算机的广泛使用 使越来越多的实际问题能归结为数值问题而得到解决 如 曲线拟合 数值逼近等 什么是数值问题呢 所谓数值问题 指的是由一组已知数据 又称输入数据 求出一组结果数据 又称输出数据 使得这两组数据之间满足预先指定的某种关系 函数关系 的问题 即由一组数求得另一组数 制定数值问题的算法 什么叫算法 用完全确定的运算规则 包括运算的逻辑顺序 对某一类数值问题的输入数据进行处理 判断此数值问题是否有解 在解存在的情况下 给出输出数据 此种过程称为算法 6 2020 4 20 主讲韩光朋 得不到准确解时 设法得到近似解例 求已知数 由数学中的极限理论可知 极限存在 于是又 n只能有限 x是近似值 7 2020 4 20 主讲韩光朋 在计算方法中 我们还将讨论 解的特性 近似程度 敛散性 各种方法的优缺点 速度 存储量 各种方法的实用范围 收敛范围 8 2020 4 20 主讲韩光朋 一个好的方法应具有如下特点 第一 面向计算机 要根据计算机特点提供实际可行的有效算法 即算法只能包括加 减 乘 除运算和逻辑运算 是计算机能直接处理的 第二 有可靠的理论分析 能任意逼近并达到精度要求 对近似算法要保证方法的收敛性和数值稳定性 还要对误差进行分析 这些都建立在相应数学理论基础上 第三 要有好的计算复杂性 即时间复杂性和空间复杂性 时间复杂性好是指节省时间 空间复杂性好是指节省存储量 这也是建立算法要研究的问题 它关系到算法能否在计算机上实现 第四 要有数值实验 即任何一个算法除了从理论上要满足上述三点外 还要通过数值试验证明是行之有效的 9 2020 4 20 主讲韩光朋 例 一个简单的算法问题 设要对给定的求多项式的值 一种计算过程是直接计算的每一项后逐项求和 这样要做次乘法和次加法 10 2020 4 20 主讲韩光朋 另一种算法就是先将变形为如下形式 再由内层向外层计算 如设 就可以得到一个递推公式 k 1 2 n 1 3 这样的计算过程只需要计算n次乘法和n次加法 这种算法和上一种算法相比 不仅逻辑结构简单 而且计算也明显地减少了 多项式求值的这种算法称为秦九韶算法 计算框图见图1 2 11 2020 4 20 主讲韩光朋 1 2误差的来源及其基本概念1 2 1误差来源 用数值计算方法解决科学技术中的具体问题 一般说都有误差 其来源有下列四种 注 由于人为的粗心大意造成的计算错误 不算误差 1 模型误差数学描述和实际问题之间的误差如 匀加速运动或自由落体运动公式略去了风力 空气阻力等 2 观察误差如 读表 读尺 读温度计 12 2020 4 20 主讲韩光朋 3 截断误差如 对x 0 求 利用泰勒公式有取其部分和作为 就产生了截断误差 4 舍入误差由于计算机的字长有限 对超过位数的数字要进行舍入 通常取与它们接近的数来表示 由此产生的误差称为舍入误差 例如 我们通常使用2 71828和3 1416来表示的近似值 由此所产生的误差就是舍入误差 13 2020 4 20 主讲韩光朋 本课程仅讨论后两种误差 截断误差和舍入误差 讨论它们在计算过程中的传播和对计算结果的影响 研制能够控制误差的影响且保证最终结果有足够精度的算法 14 2020 4 20 主讲韩光朋 1 2 2误差的概念和有效数字 1 绝对误差定义1 1设某数的精确值为 其近似值为 那么与之差称为近似值的绝对误差 简称误差 一般地 某数的精确值是不知道的 因而不能求出 但往往可以估计出它的大小范围 亦即可以确定一个正数 使得此时 称为的绝对误差限 有时也用表示近似值的精确值或精确值的所在范围 15 2020 4 20 主讲韩光朋 2 相对误差绝对误差反映不了一个近似数的准确程度 如 称一头大象误差十公斤 称一只蚂蚁误差一克 谁的近似程度好 显然大象的近似应好些 于是引进了相对误差 记称为近似值x的相对误差 由于精确值一般不知道 实际计算时通常取作为近似值x的相对误差 若能求出一个正数 使得 则称为近似值x的相对误差限 它是无量纲的数 通常用百分比表示 16 2020 4 20 主讲韩光朋 例 甲用米尺测量10M长的物体 所产生的绝对误差为2cm 乙用同一米尺测量1M长的物体 所产生的绝对误差为1cm 他们谁的测量精度好 解 根据上述定义可知 甲测量时的相对误差乙测量时的相对误差可见甲测量结果比乙精确 17 2020 4 20 主讲韩光朋 3 有效数字当准确数的位数很多时 我们常按 四舍五入 原则减少位数 得其近似数 并用 有效数字 来描述它 定义1 2如果近似值的误差限是某一位的半个单位 该位到的第一位非零数字共有位 则称有位有效数字 如果的每一位都是有效数字 则称为有效数 如 有5位有效数字 有6位有效数字 18 2020 4 20 主讲韩光朋 任何一个实数 经四舍五入后得到的近似值都可以表示为如下标准形式 其中m可为正负数 如果其绝对误差限满足 则称近似值具有n位有效数字 19 2020 4 20 主讲韩光朋 例1设 0 0270是某数经 四舍五入 所得 则误差不超过末位的半个单位 即 又 故该不等式又可写为由有效数字定义可知 有3位有效数字 分别是2 7 0 20 2020 4 20 主讲韩光朋 例2又 故该不等式又可写为故有3位有效数字 分别是3 2 8 由于中的数字9不是有效数字 故不是有效数 思考 有几位有效数字 有效数位为3位 有效数位为5位 有效数位为4位 22 2020 4 20 主讲韩光朋 4 有效数字与绝对误差 相对误差有如下关系 若某数的近似值有n位有效数字 那么这个近似值的绝对误差限为 注 由 1 4 式可知 m为整数位 n为小数位 由此看出 当m相同时 n越大 则m n越小 从而有效位数越多 其绝对误差限越小 数据也就越精确 23 2020 4 20 主讲韩光朋 用式 1 4 表示的近似数 若具有n位有效数字 则其相对误差限为则至少具有n位有效数字 反之 若的相对误差限为 24 2020 4 20 主讲韩光朋 证明由 知 若x具有n位有效数字 则从而 将上式代入 参见1 4式 25 2020 4 20 主讲韩光朋 反之 若x的相对误差限为所以x至少有n位有效数字 由 2 可以看出 有效位数越多 相对误差限就越小 精确度也就越高 26 2020 4 20 主讲韩光朋 1 2 3初值误差的传播近似数参加运算后所得到的值也是近似值 含有误差 将这一现象称为误差传播 数值运算中误差的传播情况比较复杂 主要表现在 算法本身可能有截断误差 初始数据在计算机内的浮点表示一般有舍入误差 每次运算一般又会产生新的误差 并且传播以前已经引入的误差 因此 对误差进行准确分析是困难的 但也是很重要的 它关系到一个方法是否稳定 计算结果是否可靠 误差的传播与积累 例3 蝴蝶效应 纽约的一只蝴蝶翅膀一拍 风和日丽的北京就刮起台风来了 NY BJ 以上是一个病态问题 28 2020 4 20 主讲韩光朋 1 3选用和设计算法应注意的问题一般衡量算法的标准有 算法是否稳定 算法的运算次数和算法的存储量是否尽量少 同时还要考虑误差的传播等 选用和设计算法应注意如下几个问题 选用数值稳定的计算公式 防止两个相近数相减 防止大数 吃掉 小数 简化计算步骤 减少运算次数 29 2020 4 20 主讲韩光朋 1 3 1选用数值稳定的计算公式如果数值算法的计算舍入误差积累是可以控制的 则称其为数值稳定的 反之 称为数值不稳定的 例 计算定积分 序列 利用分部积分法不难求得递推关系式为 公式推导 30 2020 4 20 主讲韩光朋 由式 1 16 可依次算出如下结果 p011 c 注意到 注 从积分中按x的最小和最大值提出ex 1 17 由上面的不等式可以看出 31 2020 4 20 主讲韩光朋 因此按递推关系式 1 16 所算出的计算值是错误的 严重偏离其准确值 发生这种现象的原因是因为本身有不超过的误差 设是具有精确初始值 并按式 1 16 计算而得的 则有由此可见 初始值微小的误差会随着计算步数的增加而迅速扩大 最终使计算结果失真 故算法式 1 16 不能控制误差的传播 是数值不稳定的 32 2020 4 20 主讲韩光朋 如果将式 1 16 改写为 1 18 又注意到 结合式 1 17 得 由上面的估计式取 开始按式 1 18 计算 有如下结果 p012 c 33 2020 4 20 主讲韩光朋 由此可以看出按递推关系式 1 18 算出的与结果相差无几 已精确到小数点后第四位 分析误差的传播 则有 这表明 随着计算步骤的增加 初始误差可以得到控制 于是可知算法 1 18 式是数值稳定的 公式推导 34 2020 4 20 主讲韩光朋 1 3 2防止两个相近数相减在数值计算中若有两个相近的数相减 则这两个数的前几位相同的有效数字会在它们之差中消失 从而使有效数字的位数减少 如果遇到两个相近的数相减运算 可考虑对公式进行处理 避免减法 例如 当很大时 下两式应作如下处理 35 2020 4 20 主讲韩光朋 1 3 3绝对值太小的数不宜作除数算法语言中已讲过 在机器上若用很小的数作除数会溢出停机 而且当很小的数稍有一点误差时 对计算结果影响很大 例如 36 2020 4 20 主讲韩光朋 1 3 4防止大数 吃掉 小数例 设a 63281312 b 0 1 c 0 9 求a b c之和 如果按 a b c次序来编制程序 此时按照加法浮点运算的对阶规则 应有 在八位的计算机上计算时 上式后面的两个数在计算机上变为了 机器零 被 吃掉 其结果为63281312 如果改变计算次序为 b c a 则有 0 1 0 9 63281312 1 63281312 63281313 这样就避免了小数被大数 吃掉 的现象 37 2020 4 20 主讲韩光朋 1 3 5简化计算步骤 减少运算次数对于同一个问题的计算 可以有不同的计算方法 如计算的值 如果逐个相乘 则要计算254次乘法 但如果写成只要做14次乘法运算就可以完成 由此可见 如果方法选择得当 则不仅能减少计算次数 提高计算速度 也可以简化逻辑结构 减少误差积累 从而达到提高计算精度的目的 38 2020 4 20 主讲韩光朋 误差问题是计算方法中既重要而又困难的课题 本章介绍了误差来源及相关基本概念 同时还给出设计算法时应注意的问题 这对今后学习是必须的 习题 4 要使的相对误差不超过至少需要保留多少位有效数字 所有至少要保留5位有效数字 2020年4月20日星期一 第40页 在许多科学技术和工程计算等实际问题中 常常会遇到求解非线性方程的问题 例如 求n次代数方程的根 或求由三角函数 指数函数和对数函数等组成的超越方程 例如 求超越方程的解 这些都可表示为求非线性方程的根 或称为求非线性方程的解 即求函数的零点 方程的根可以是实数 也可以是复数 2020年4月20日星期一 第41页 根的概念 给定方程f x 0 如果有 使得f 0 则称 为f x 0的根或f x 的零点 设有正整数m使得f x x mg x 且g 0 则当m 2时 称 为f x 0的m重根 当m 1时 称为f x 0的单根 本章只讨论实根的求法 2020年4月20日星期一 第42页 求根一般步骤 1 确定所给方程存在多少个根 2 进行根的隔离 找出每个有根区间 参考清华大学出版 靳天飞主编 计算方法 有根区间内的任一点都可看成是该根的一个近似值 3 逐步把近似根精确化 直到足够精确为止 本章主要讨论单根问题 求根的方法很多 如 二分法 又称对分法 牛顿法 又称切线法 双点弦截法 又称快速弦截法 迭代法等 2020年4月20日星期一 第43页 2 1二分法 2020年4月20日星期一 第44页 2020年4月20日星期一 第45页 2020年4月20日星期一 第46页 2020年4月20日星期一 第47页 三 二分法的定义 计算步骤与框图1 定义2 0象方法介绍那样 通过将区间 a b 对分 逐步缩小根的范围而求出方程f x 0的实根的方法称为二分法 也称为对分法 2 计算步骤 输入有根区间的端点a b及预先给定的容许精度e 计算 若f a f b 0 则b x 转向下一步 否则a x 转向下一步 若 b a e 则输出方程满足精度要求的值x 否则转向 2020年4月20日星期一 第48页 3 程序框图与程序实例 程序框图图2 2表示了用二分法求方程f x 0的根上机实习编制程序的框图 程序实例 我们用C语言编制了用二分法求方程根的程序 程序文本及计算结果可见第八章程序实例2 2020年4月20日星期一 第49页 2020年4月20日星期一 第50页 2020年4月20日星期一 第51页 2 2迭代法 本节分三步介绍 一 迭代法的基本思想二 迭代法需要解决的两个基本问题 如何选取初值 何时停机 三 迭代法的计算步骤和计算框图 2020年4月20日星期一 第52页 2020年4月20日星期一 第53页 思考 如何选取初值 2020年4月20日星期一 第54页 2020年4月20日星期一 第55页 二 迭代法需要解决的两个基本问题1 如何选取初始近似值 以及迭代函数g x 才能保证按迭代公式求出的迭代序列收敛 2 当迭代序列收敛时 用计算机如何决定迭代过程结束 2020年4月20日星期一 第56页 2 2 2迭代法的收敛条件 解决第一个问题 定理2 1设迭代函数g x 在区间 a b 上具有一阶导数 且满足 存在正数L 1 使对任意 有则方程在区间 a b 上存在惟一解 且对任意初始值 迭代过程收敛 即 证明见P22略 2020年4月20日星期一 第57页 定理2 1称为用迭代法求非线性方程解的全局收敛性定理 定理2 1中的条件对于较大范围的含根区间有时可能不成立 因此 实际使用迭代法时 常常考虑在根的某个邻域内的情形 这就是局部收敛性 定义2 1设是方程x g x 的解 如果在解的某个邻域内 迭代过程对于任意的均收敛 这种在解的邻域具有的收敛性 称为局部收敛性 2020年4月20日星期一 第58页 定理2 2如果在方程x g x 的解的某个邻域内 有则以为初值 由迭代格式xn 1 g xn n 0 1 2 产生的系列 xn 一定收敛于 反之 若在该邻域内有则以为初值 由迭代格式xn 1 g xn 产生的系列 xn 发散 证明见P23略 2020年4月20日星期一 第59页 例3分析例2中两种迭代格式的收敛性 解由例2知 第一种迭代格式和第二种迭代格式的迭代函数分别为故有当x属于有根区间 1 2 时 分别有由定理2 2知 第一种迭代格式 当取初值时收敛 第二种迭代格式发散 思考 如何确定有根区间 2020年4月20日星期一 第60页 2 2 3误差估计式 解决第二个问题 当迭代序列 xn 收敛时 如何决定迭代过程结束 这是采用迭代法在计算机上求解非线性方程的一个重要问题 通常是以迭代过程中相邻两项之差的绝对值是否小于给定的允许精度来确定 即以关系式 为允许精度 是否满足来决定迭代过程是否结束 定理2 3如果在方程x g x 的解的某一个邻域内 有 则有误差估计式 2 6 证明见P25略 2020年4月20日星期一 第61页 2020年4月20日星期一 第62页 下面说明 为什么可用迭代过程中相邻两项之差的绝对值来决定迭代过程结束 设是方程的准确解 为第n次迭代值 为保证精度而预先给定的控制常数 误差估计式 2 6 表明 要使 只要因此 当取时 由就能保证 2020年4月20日星期一 第63页 2020年4月20日星期一 第64页 1 2020年4月20日星期一 第65页 2 2020年4月20日星期一 第66页 2 2 5迭代法的收敛阶对非线性方程f x 0求解 我们可选取不同的迭代函数 即使由这些迭代函数产生的迭代序列都收敛 它们也会有快慢之分 如何反映迭代序列收敛的快慢呢 这就要引进迭代法收敛阶的概念 定义2 2设是收敛于f x 0的解的序列 记 如果存在实数和非零常数c 使得则称迭代序列 xn 为p阶收敛 或者称产生迭代序列 xn 的迭代方法xn 1 g xn 是p阶收敛的 特别地 当p 1时称为线性收敛 P 1时称为超线性收敛 p 2时称为平方收敛 显然 数p的大小反映了迭代法收敛的快慢 p越大则收敛越快 因此 迭代法的收敛阶是衡量迭代法优劣的重要标志之一 2020年4月20日星期一 第67页 2020年4月20日星期一 第68页 2020年4月20日星期一 第69页 2020年4月20日星期一 第70页 2020年4月20日星期一 第71页 2 3Newton迭代法 略 2020年4月20日星期一 第72页 2020年4月20日星期一 第73页 3 Newton迭代法收敛定理 定理2 5 略 则Newton迭代法 2 12 产生的数列 收敛到根 为例证明 其它情况类似 2020年4月20日星期一 第74页 略 2020年4月20日星期一 第75页 例6 略 解 设 用Newton迭代法求 2020年4月20日星期一 第76页 2020年4月20日星期一 第77页 x y xn Xn 1 Xn 2 tn x tn 1 x 0 2 3牛顿 Newton 法解非线性方程f x 0的牛顿 Newton 法 就是将非线性方程线性化的一种方法 牛顿法具有实用面广 收敛快等优点 2 3 1方法介绍所谓牛顿法 就是用f x 0的解的近似值xn n 0 1 2 的切线方程 图2 4 2 11 作为f x 的近似表达式 然后取tn x 0的解xn 1作为f x 0的解的进一步近似 如图2 4所示 由式 2 11 令tn x 0就得到了牛顿法的迭代公式 2 12 2020年4月20日星期一 第78页 由图2 4可以看出 牛顿法实际上是在每一步都使用不同的切线方程去逼近非线性方程 因此 牛顿法也称为切线法 它是一种将非线性方程线性化的方法 由迭代格式 2 12 可知 牛顿法是一种特殊的迭代法 其迭代函数在f x 及其导数满足一定条件的情况下 通过选择适当的初始值x0 迭代格式 2 12 所产生的迭代序列 xn 将收敛 2 13 2020年4月20日星期一 第79页 2 3 2牛顿法收敛的充分条件定理2 5设函数f x 在闭区间 a b 上存在二阶导数且满足条件 在区间 a b 上保号 设且则牛顿迭代格式 2 12 产生的迭代序列 收敛于方程f x 0的一个解 证明P32略 2020年4月20日星期一 第80页 2020年4月20日星期一 第81页 2020年4月20日星期一 第82页 2020年4月20日星期一 第83页 例6设c为正实数 导出用牛顿法求的公式 并证明迭代序列的误差满足关系式解设 则 所以由于所以f x 0在区间 0 1 内有一正根 又由于在区间内 若取 则在区间内满足定理2 5的条件 所以收敛的牛顿迭代式为 2020年4月20日星期一 第84页 记 则有 由例6中误差满足的关系式 2 14 可得对上式取极限可得由此可知 在用牛顿法求时是2阶收敛的 2 14 2020年4月20日星期一 第85页 2 3 3牛顿法的收敛阶定理2 6设函数f x 充分光滑 对于方程f x 0 若在区间 a b 内存在单根 则用牛顿法求的近似解时是2阶收敛的 若在区间 a b 内存在m 2 重根 则用牛顿法求的近似解时是线性收敛的 证明P35略 写出求 2020年4月20日星期一 第86页 2 3 4计算步骤和程序框图牛顿法的计算步骤为 选定初值 计算 按公式迭代 得新的近似值 并计算 对于给定的允许精度 如果 则终止迭代 取 否则 再转回步骤 计算 图2 6给出了用牛顿法求非线性方程f x 0解的程序框图 其中N为设定的最大迭代次数 2020年4月20日星期一 第87页 1 k 输出迭代失败标志 结束 开始 输出x1 输出奇异标志 图2 6 2020年4月20日星期一 第88页 例7求方程的解 解粗略地绘出函数的草图 如图2 7所示 图2 7 2020年4月20日星期一 第89页 对函数f x 求导可得 若取初值x0 3 用牛顿法求解例7的迭代格式为 经计算可得 x1 1 15999 x2 0 189438 x5 0 783595 x6 0 783599 若只需6位有效数字 则x6 0 783599 2020年4月20日星期一 第90页 在 2 18 式中 若取初值x0 8 经计算可得 x1 34 778107 x2 865 1519 继续迭代可知 xn随着n的增大将无限增大 此时迭代格式 2 18 发散 例7说明 使用牛顿法求解非线性方程 初值x0的选择非常重要 选择得不好会引起迭代序列发散 求不出方程的近似解 本例还说明 定理2 5的条件仅是一个充分条件 当条件不满足时 仍有可能收敛 如取x0 3时 迭代格式收敛 但f 3 1 472366 0 由式 2 17 知 故不满足定理2 5中的条件 2020年4月20日星期一 第91页 2 3 5双点弦截法 快速弦截法 在方程f x 0的根 附近任取两初始近似根x0 x1 由迭代公式 2 20 逐次逼近f x 0的根 这种求根算法称为弦截法 2020年4月20日星期一 第92页 2020年4月20日星期一 第93页 2020年4月20日星期一 第94页 2020年4月20日星期一 第95页 2020年4月20日星期一 第96页 2020年4月20日星期一 第97页 本章重点 对给定方程F X 0构造的两种迭代函数G1 x 和G2 x 判断其敛散性 习题 2020年4月20日星期一 主讲 韩光朋 98 2020年4月20日星期一 主讲 韩光朋 99 2020年4月20日星期一 主讲 韩光朋 100 3 1高斯 Gauss 消去法高斯消去法的基本思想 高斯消去法就是逐步消去变元的系数 将原方程组Ax b化为系数矩阵为三角形的等价方程组Ux d 然后求解系数矩阵为三角形的方程组而得到原方程组解的方法 我们把逐步消去变元的系数 将原方程组化为以系数矩阵为上三角形的等价方程组的过程称为消元过程 把求系数矩阵为上三角形方程组的过程称为回代过程 最初的求解线性代数方程组的高斯消去法也称为顺序消去法 它是由消元过程和回代过程组成 2020年4月20日星期一 主讲 韩光朋 101 2020年4月20日星期一 主讲 韩光朋 102 2020年4月20日星期一 主讲 韩光朋 103 2020年4月20日星期一 主讲 韩光朋 104 2020年4月20日星期一 主讲 韩光朋 105 2020年4月20日星期一 主讲 韩光朋 106 2020年4月20日星期一 主讲 韩光朋 107 2020年4月20日星期一 主讲 韩光朋 108 2020年4月20日星期一 主讲 韩光朋 109 2020年4月20日星期一 主讲 韩光朋 110 2020年4月20日星期一 主讲 韩光朋 111 2020年4月20日星期一 主讲 韩光朋 112 2020年4月20日星期一 主讲 韩光朋 113 2020年4月20日星期一 主讲 韩光朋 114 2020年4月20日星期一 主讲 韩光朋 115 2020年4月20日星期一 主讲 韩光朋 116 2020年4月20日星期一 主讲 韩光朋 117 注意 全主元消去法应增加一个解向量的伴随向量 记录每次交换的信息 2020年4月20日星期一 主讲 韩光朋 118 2020年4月20日星期一 主讲 韩光朋 119 2020年4月20日星期一 主讲 韩光朋 120 2020年4月20日星期一 主讲 韩光朋 121 3 2矩阵的三角分解 略 了解 转3 5节63屏 2020年4月20日星期一 主讲 韩光朋 122 2020年4月20日星期一 主讲 韩光朋 123 上标从1开始 2020年4月20日星期一 主讲 韩光朋 124 2020年4月20日星期一 主讲 韩光朋 125 2020年4月20日星期一 主讲 韩光朋 126 2020年4月20日星期一 主讲 韩光朋 127 2020年4月20日星期一 主讲 韩光朋 128 见例1 2020年4月20日星期一 主讲 韩光朋 129 2020年4月20日星期一 主讲 韩光朋 130 2020年4月20日星期一 主讲 韩光朋 131 2020年4月20日星期一 主讲 韩光朋 132 2020年4月20日星期一 主讲 韩光朋 133 上例 2020年4月20日星期一 主讲 韩光朋 134 2020年4月20日星期一 主讲 韩光朋 135 2020年4月20日星期一 主讲 韩光朋 136 2020年4月20日星期一 主讲 韩光朋 137 2020年4月20日星期一 主讲 韩光朋 138 2020年4月20日星期一 主讲 韩光朋 139 2020年4月20日星期一 主讲 韩光朋 140 2020年4月20日星期一 主讲 韩光朋 141 2020年4月20日星期一 主讲 韩光朋 142 2020年4月20日星期一 主讲 韩光朋 143 2020年4月20日星期一 主讲 韩光朋 144 2020年4月20日星期一 主讲 韩光朋 145 主讲 韩光朋 2020年4月20日星期一 主讲 韩光朋 146 2020年4月20日星期一 主讲 韩光朋 147 2020年4月20日星期一 主讲 韩光朋 148 2020年4月20日星期一 主讲 韩光朋 149 2020年4月20日星期一 主讲 韩光朋 150 2020年4月20日星期一 主讲 韩光朋 151 2020年4月20日星期一 主讲 韩光朋 152 2020年4月20日星期一 主讲 韩光朋 153 2020年4月20日星期一 主讲 韩光朋 154 2020年4月20日星期一 主讲 韩光朋 155 2020年4月20日星期一 主讲 韩光朋 156 2020年4月20日星期一 主讲 韩光朋 157 2020年4月20日星期一 主讲 韩光朋 158 2020年4月20日星期一 主讲 韩光朋 159 2020年4月20日星期一 主讲 韩光朋 160 3 5线性代数方程组的性态 2020年4月20日星期一 主讲 韩光朋 161 向量范数的计算方法 2020年4月20日星期一 主讲 韩光朋 162 略 2020年4月20日星期一 主讲 韩光朋 163 2020年4月20日星期一 主讲 韩光朋 164 说明三种范数等价 了解 2020年4月20日星期一 主讲 韩光朋 165 2020年4月20日星期一 主讲 韩光朋 166 3 5 2矩阵范数矩阵范数的定义 利用向量范数定义矩阵范数 2020年4月20日星期一 主讲 韩光朋 167 2020年4月20日星期一 主讲 韩光朋 168 2 N阶矩阵A的范数具有下列基本性质 2020年4月20日星期一 主讲 韩光朋 169 3 矩阵范数的计算 2020年4月20日星期一 主讲 韩光朋 170 此处将矩阵问题转换成向量问题进行讨论 略 2020年4月20日星期一 主讲 韩光朋 171 略 2020年4月20日星期一 主讲 韩光朋 172 求特征值 得到谱半径 重点 2020年4月20日星期一 主讲 韩光朋 173 3 5 3线性方程组的性态 2020年4月20日星期一 主讲 韩光朋 174 直接展开并移项 2020年4月20日星期一 主讲 韩光朋 175 2020年4月20日星期一 主讲 韩光朋 176 定理3 5说明误差与条件数有关 2020年4月20日星期一 主讲 韩光朋 177 2020年4月20日星期一 主讲 韩光朋 178 2020年4月20日星期一 主讲 韩光朋 179 定义条件数 2020年4月20日星期一 主讲 韩光朋 180 4 关于方程组性态的判断 定义什么叫 病态 和 良态 方程组 2020年4月20日星期一 主讲 韩光朋 181 2020年4月20日星期一 主讲 韩光朋 182 3 5 4方程组近似解可靠性判别法 能否用余向量或残量来判断 不能 2020年4月20日星期一 主讲 韩光朋 183 2020年4月20日星期一 主讲 韩光朋 184 2020年4月20日星期一 主讲韩光朋 185 4 1三种基本的迭代法4 1 1Jacobi迭代法 1 公式的推导 2 Jacobi迭代法的矩阵形式 3 Jacobi迭代法的缺陷 1 公式的推导 2020年4月20日星期一 主讲韩光朋 186 2020年4月20日星期一 主讲韩光朋 187 对于n阶方程组Ax b 假定系数矩阵A的对角元 i 1 2 n 时 类似于 4 3 式的推导 可得雅可比迭代格式为 2020年4月20日星期一 主讲韩光朋 188 在一定条件下 对任意初始向量 按迭代公式 4 4 求出的向量序列的极限存在且等于方程的解 这种用迭代格式 4 4 求线性代数方程组近似解的方法称为雅可比迭代法 也称简单迭代法 2020年4月20日星期一 主讲韩光朋 189 2 Jacobi迭代法的矩阵形式 2020年4月20日星期一 主讲韩光朋 190 2020年4月20日星期一 主讲韩光朋 191 3 Jacobi迭代法的缺陷 2020年4月20日星期一 主讲韩光朋 192 4 1 2高斯 赛德尔 GaussSeidel 迭代法 1 迭代公式 将4 3式作一点改进 得到下式 2020年4月20日星期一 主讲韩光朋 193 2 用矩阵形式表示 2020年4月20日星期一 主讲韩光朋 194 重点 2020年4月20日星期一 主讲韩光朋 195 2020年4月20日星期一 主讲韩光朋 196 2020年4月20日星期一 主讲韩光朋 197 3 程序框图 2020年4月20日星期一 主讲韩光朋 198 参看4 8式 4 1 3超松弛迭代法 SOR方法 要求了解 预算一次 2020年4月20日星期一 主讲韩光朋 199 重算一次 将两步并为一步 2020年4月20日星期一 主讲韩光朋 200 2 用矩阵形式表示 2020年4月20日星期一 主讲韩光朋 201 3 SOR方法的程序框图 2020年4月20日星期一 主讲韩光朋 202 略 2020年4月20日星期一 主讲韩光朋 203 2020年4月20日星期一 主讲韩光朋 204 4 2迭代法的收敛条件 2020年4月20日星期一 主讲韩光朋 205 4 2 1迭代法收敛的概念 2020年4月20日星期一 主讲韩光朋 206 3 用范数来讨论迭代法的收敛条件 2020年4月20日星期一 主讲韩光朋 207 4 2 2迭代法收敛性的判定定理 2020年4月20日星期一 主讲韩光朋 208 2020年4月20日星期一 主讲韩光朋 209 2020年4月20日星期一 主讲韩光朋 210 定理4 1只是用作理论研究 实际计算时仍用各自方法的迭代格式 2020年4月20日星期一 主讲韩光朋 211 2020年4月20日星期一 主讲韩光朋 212 2020年4月20日星期一 主讲韩光朋 213 2020年4月20日星期一 主讲韩光朋 214 证明略 有了定理4 2 对于某些方程组 可直接用系数矩阵来判定使用雅可比迭代法和G S迭代法求解是否收敛 重新考察例3 由于系数矩阵 可知矩阵A按行严格对角占优 因此 由定理4 2 采用雅可比迭代法和G S迭代法求解例3的方程组收敛 2020年4月20日星期一 主讲韩光朋 215 注 引理4 1的证明涉及到线性代数中的约当标准型和约当矩阵的有关知识 对引理4 1的证明感兴趣的读者可参看张徳荣 王新民 高安民编 计算方法与算法语言 第102面引理4 2020年4月20日星期一 主讲韩光朋 216 2020年4月20日星期一 主讲韩光朋 217 2020年4月20日星期一 主讲韩光朋 218 2020年4月20日星期一 主讲韩光朋 219 2020年4月20日星期一 主讲韩光朋 220 2020年4月20日星期一 主讲韩光朋 221 利用定理4 3可以证明松弛迭代法收敛的一个充分条件 定理4 4设方程组Ax b的系数矩阵A为实对称正定阵 且0 w 2 则松弛迭代法收敛 证明略 2020年4月20日星期一 主讲韩光朋 222 2020年4月20日星期一 主讲韩光朋 223 2020年4月20日星期一 主讲韩光朋 224 2020年4月20日星期一 主讲韩光朋 225 5 1插值与拟合的基本概念 2020年4月20日星期一 主讲韩光朋 226 2020年4月20日星期一 主讲韩光朋 227 2020年4月20日星期一 主讲韩光朋 228 2020年4月20日星期一 主讲韩光朋 229 且用此方法可得到插值多项式Pn 但这种方法不适用 只能用作理论研究 2020年4月20日星期一 主讲韩光朋 230 图5 1 插值余項 2020年4月20日星期一 主讲韩光朋 231 定理5 2设f x 在 a b 上n 1阶导数存在 则插值多项式 5 2 的余项为 2020年4月20日星期一 主讲韩光朋 232 2020年4月20日星期一 主讲韩光朋 233 5 2拉格朗日 Lagrange 插值 5 2 1拉格朗日插值基函数对于给定的n 1个互异的节点 为了构造求解n次多项式插值问题的可行算法 我们首先考虑一个简单的n次多项式插值问题 已知y f x 的如下函数值表 5 8 2020年4月20日星期一 主讲韩光朋 234 2020年4月20日星期一 主讲韩光朋 235 2020年4月20日星期一 主讲韩光朋 236 5 2 2拉格朗日插值多项式设用试验或观测方法得到函数的如下函数值表 5 11 2020年4月20日星期一 主讲韩光朋 237 这表明式 5 12 就是满足插值条件式 5 11 的多项式插值函数 它是插值基函数的线性组合 由插值多项式的存在唯一性知 将Ln x 化简成n次多项式标准形式 5 2 后 与用求解方程组 5 3 而得的插值多项式是相同的 称形如式 5 12 的插值多项式Ln x 为拉格朗日插值多项式 讨论 在 5 12 式中 当n 1时 是一次插值多项式 也称线性插值 2020年4月20日星期一 主讲韩光朋 238 2020年4月20日星期一 主讲韩光朋 239 例1已知的值如下 重点 求拉格朗日插值多项式L2 x 求L2 2 5 求插值余项R2 x 并估计R2 x 2020年4月20日星期一 主讲韩光朋 240 2020年4月20日星期一 主讲韩光朋 241 2020年4月20日星期一 主讲韩光朋 242 略 2020年4月20日星期一 主讲韩光朋 243 2020年4月20日星期一 主讲韩光朋 244 略 2020年4月20日星期一 主讲韩光朋 245 5 3牛顿插值 2020年4月20日星期一 主讲韩光朋 246 略 2020年4月20日星期一 主讲韩光朋 247 略 2020年4月20日星期一 主讲韩光朋 248 2020年4月20日星期一 主讲韩光朋 249 各阶差商可按差商表 见表5 1 计算 重点 2020年4月20日星期一 主讲韩光朋 250 5 3 2 Newton插值多项式 2020年4月20日星期一 主讲韩光朋 251 2020年4月20日星期一 主讲韩光朋 252 2020年4月20日星期一 主讲韩光朋 253 2020年4月20日星期一 主讲韩光朋