数值分析-计算方法

数值分析 上海大学机自学院 第一章绪论 1 1课程主要内容1 非线性方程数值解法2 线性方程组的数值解法3 插值方法4 数值积分5 常微分方程初值问题的数值解法 1 2数值算法概论数值算法是利用计算机求解数学问题近似解的方法 所获近似解也称为原问题的数值解或逼近解 重点研究数值算法构造及其相关理论 包括误差分析 算法收敛性和稳定等 实际问题 数学模型 构造数值算法 程序设计 获取近似解 数值算法 不仅仅是单纯的数学公式 而是指解题方案准确而完整的描述 算法优劣主要取决于 1 计算开销2 误差控制 数值方法是一门与计算机应用密切结合的实用性很强的学科 思维方法是归纳法 核心问题是 误差 或误差分析 数值方法这门课程讨论连续变量问题又要讨论离散变量问题 关心的是数值结果 数值分析 计算数学 计算方法或数值方法这门课程已成为近代数学的一个重要分支 例1 1多项式求值的秦九韶算法P x a0 a1x a2x2 anxn 算法 令tk xkuk a0 a1x akxk则得递推公式tk xtk 1uk uk 1 aktk初值t0 1 u0 a0 k 1 2 n 显然 由算法 计算n次多项式P x 值所需的乘法次数为2n 算法 秦九韶算法 我国宋代数学家 P x a0 a1x a2x2 anxnP x a0 x a1 a2x anxn 1 P x a0 x a1 x a2 anxn 2 P x a0 x a1 x an 1 anx 显然 由里层往外一层一层的计算 仅需n次乘法运算 比算法 节省一半的计算量 秦九韶算法令 p 0 v0 an p 1 v1 anx an 1 v0 x an 1 p 2 v2 anx an 1 x an 2 v1x an 2 p k vk vk 1x an k p n vn vn 1x a0 v0 anvk vk 1x an k k 1 2 n P x vn 例1 2计算积分解 通过直接计算可产生如下递推公式 1 1 由经典微积分知识可推得In具有如下性质 1 2 单调递减 3 4 直接根据公式 1 1 从n 1计算到n 30 结果为 表1 1从n 18开始 计算值出现异常 原因是从第n 1步计算到第n步时 第n 1步的误差被放大了5倍 算法改造 由性质 4 取递推公式改写为 1 2 从n 30计算到n 1 由于该算法每向后推进一步 其误差便减少5倍 可期望获得符合原积分性态的数值结果 计算结果见表1 2 表1 2由此列可知 算法的设计十分重要 关系到计算结果是否真实可信 1 3误差实际问题的求解过程中 一般会产生误差 误差的产生是正常的 不可避免的 实际问题 数学模型 问题的解 模型误差 观测误差 截断误差 舍入误差 本课程中 仅考虑数值计算过程所带来的误差 即截断误差和舍入误差 截断误差计算过程中 往往将解题方案加工成算术运算与逻辑运算的有限序列 这种加工过程常表现为无穷过程的截断 由此产生的误差称为截断误差 用计算机计算 时 只能取有限项 截断误差为 舍入误差计算过程中数据的位数可能很多 甚至为无穷小数 受计算机字长限制 用机器代码表示的数据必须舍入成一定的位数 由此产生的误差称为舍入误差 定义1 1设 是某量的精确值 是其近似值 则称差 为 的绝对误差 一般而言 未知 直接确定e是困难的 常用 e 表征绝对误差 称为绝对误差限 定义1 2在定义1 1的假设条件下 称比值 为近似值得相对误差 通常用 er r表征相对误差 r称为相对误差限 因 未知 常用 表示相对误差 通常近似值的精度用所谓有效数字位数来表征 即近似值 的绝对误差限是它某一位的半个单位 则称该近似值 准确 到这一位 且这一位直到前面第一个非零数字为止的所有数字均为有效数字 如圆周率 的近似值为 3 142 其绝对误差限为 0 000407 0 0005 0 5 101 4则近似值 有4位有效数字 近似值 准确到小数点后第3位 小数点后第3位半个单位 定义1 3若 的近似值 0 1 2 10m 其中 1 0 诸 0 1 2 9 为整数 且 0 5 10 1 则称近似值 有 位有效数字或称 准确到10 位 定理1 1设近似值 0 1 2 10m有 位有效数字 则其相对误差限为 1 2 1 10 1 定理1 2设近似值 0 1 2 10m的相对误差限为 1 2 1 1 10 1 则近似值 有 位有效数字 证明 定理1 1因为 0 1 2 10 故有 1 10 1 1 1 10 1当 有 位有效数字时 0 5 10 1 10 1 12 1 10 1定理1 2 1 1 10 1 12 1 1 10 1 12 10 所以 有 位有效数字 例1 3下列近似值有几位有效数字 其相对误差是多少 1 2 71828 2 0 030021 0 0300解 1 2 7182818284 0 0000018 12 101 6近似值 2 71828有6位有效数字 2 0 000021 12 10 1 3近似值 0 0300有3位有效数字 例1 4为使 的近似值的相对误差小于0 001 至少应取几位有效数字 解 假定 的近似值有 位有效数字 则其相对误差上限为 12 1 10 1这里 1 3 依题意 应有 12 1 10 16 lg6即 6 应取近似值3 14159 函数值和算术运算的误差估计设一元函数 具有二阶连续导数 自变量的准确值为 近似值为 将函数 在 处做级数展开 12 2 2于是 12 2 2当 较小时 可以忽略其平方项12 2 2计为0 于是 例1 5设 0 的相对误差为 求ln 的绝对误差 例1 6设 的相对误差为2 求 的相对误差 对多元函数 1 2 若自变量的准确值 1 2 近似值为 1 2 取多元函数 1 2 的Taylor展式的一阶项 得多元函数绝对误差及相对误差的估计式 1 1 2 1 1 2 1 2 四则运算的绝对误差估计式 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 22 2 0 误差对计算结果的影响 例1 7用中心差商公式求f x 在x 2的导数 理论上 步长h愈小 计算结果愈准确 假定受计算机字长限制 只能取5位有效数字 于是h 0 1h 0 0001 4位有效数字 例1 8考察如下病态方程组准确解为 x1 x2 x3 1若将系数舍入成3位有效数字 则有其解为x1 1 09 x2 0 488 x3 1 49系数改变不大 但近似解与精确解出入太大 1 4避免误差扩大的几个常用原则1 简化计算步骤 减少运算次数2 避免两个相近数相减 导致有效数字损失a1 0 12345 a2 0 12346a2 a1 0 00001仅剩一位有效数字解决方法 1 2 3 3 避免小数做除数 放大误差4 注意运算次序 防止大数 吃掉 小数a 1234578 0 bi 1 i 1 2 100在具有8位浮点数的计算机上 计算a b1 b2 b100如果从左依次做加法运算 则有a b1 a a b1 b2 a b2 a a b1 b2 b100 a这里bi 1被当作数值0正确方法先计算 1100 再与 求和 1 5化粗为精的松弛方法1 松弛法设F0与F1为准确值F 的两个近似值取F0与F1的加权平均作为新的近似值 1 F0 F1权系数0 1称为松弛因子2 超松弛法如果F0与F1有优劣之分 譬如F0为劣F1为优 1 F1 F0 F1 F1 F0 割圆术阿基米德 3 14祖冲之3 1415926 3 1415927祖冲之之前的刘徽从计算圆内正6边形面积S6开始一直计算到圆内正192边形面积S192 圆半径r 10 其中S96 313584625 S192 31464625换算成圆周率后分别约为 3 14利用超松弛法 取 36105 S192 36105 S192 S96 314425该结果相当于圆内正3072边形的面积 换算成圆周率 得 3 1416比阿基米德的圆周率精度提高了两个数量级如果取 13 则可得圆周率 3 14159265相当于计算到圆内正24576边形面积 1 6向量范数与矩阵范数定义1 4称n维实空间上的一个非负函数为范数 若其满足 1 当且仅当 2 及 3 对于一维实空间R而言 即为绝对值 对于n维向量 将主要涉及lp p 1 2 范数 特别 l 范数为 定理1 3若与为Rn上的任意两种范数 则存在正常数C2 C1使得 定义1 5设有向量序列 X k Rn X k T 若 i 1 2 n则称序列 X k 收敛域向量X x1 x2 xn T 定理1 4在空间Rn中 序列 X k 收敛于向量X的充要条件是存在范数 使得定义1 6设A为n阶方阵 为Rn中的某范数 则称为矩阵A的从属于向量范数的范数 记作