《绪论计算方法》PPT课件.ppt

第0章绪论 运用数学方法解决科学研究或工程技术问题 一般按如下途径进行 实际问题 模型设计 算法设计 程序设计 上机计算 问题的解 其中算法设计是计算方法课程的主要内容 结束 1 计算方法又称数值分析 数值计算方法 是研究并解决数学问题的数值近似解方法 是在计算机上使用的解数学问题的方法 它是计算数学的重要组成部分 0 1数值计算方法与算法 结束 2 0 1 1计算方法的任务计算方法课程研究常见的基本数学问题的数值解法 包含了数值代数 线性方程组的解法 非线性方程的解法 矩阵求逆 矩阵特征值计算等 数值逼近 数值微分与数值积分 常微分方程及偏微分方程的数值解法等 0 1 2算法进行科学计算 需要构造确定型数值算法 确定型算法可定义为 从给定的已知量出发 按指定的运算顺序 经过有限次的四则运算及逻辑运算 可求出给定问题的数值解的完整的计算步骤 结束 3 0 1 2算法的效率算法的计算量简化为该算法所需要的乘法和除法运算的总次数 计算量越小 计算效率就越高 0 1 3算法的表述形式算法的表述形式是多种多样的 1用数学公式和文字说明描述 这种方式符合人们的理解习惯 和算法的推证相衔接 易于学习接受 但离上机应用距离较大 2用框图描述 这种方式描述计算过程流向清楚 易于编制程序 详略难以掌握 3算法描述语言 它是表述算法的一种通用语言 有特定的表述程序和语句 可以很容易地转化为某种计算机语言 同时也具有一定的可读性 4算法程序 即用计算机语言描述的算法 它是面对计算机的算法 我们以后讨论的算法 都有现成的程序文本和软件可资利用 但从学习算法的角度看 这种描述方式并不有利 结束 4 0 1 4算法的基本特点1算法常表现为一个无穷过程的截断 例1计算sinx的值 根据sinx的无穷级数 0 1 这是一个无穷级数 我们只能在适当的地方 截断 使计算量不太大 而精度又能满足要求 如计算sin0 5 取n 3 结束 5 据泰勒余项公式 它的误差应为 0 2 可见结果是相当精确的 实际上结果的六位数字都是正确的 2算法常表现为一个连续过程的离散化 例2计算积分值 将 0 1 分为4等分 分别计算4个小曲边梯形的面积的近似值 然后加起来作为积分的近似值 如图1 1 记被积函数为f x 即 结束 6 计算有 I 0 697024 与精确值0 693147比较 可知结果不够精确 如进一步细分区间 精度可以提高 迭代是指某一简单算法的多次重复 后一次使用前一次的结果 这种形式易于在计算程序中实现 在程序中表现为 循环 过程 例3多项式求值 结束 7 3算法常表现为 迭代 形式 用tk表示xk uk表示 0 3 式前k 1项之和 作为初值令 0 4 0 3 对k 1 2 n 反复执行 0 5 显然Pn x un 而 0 5 式是一种简单算法的多次循环 令k 1 2 n 0 6 结束 对此问题还有一种更好的迭代算法 8 这两种算法都是将n次多项式化为n个一次多项式来计算 这种化繁为简的方法在数值分析中经常使用 下面估计一下以上两种算法的计算量 第一法 执行n次 0 5 式 每次2次乘法 一次加法 共计2n次乘法 n次加法 第二法 执行n次 0 6 式 每次1次乘法 一次加法 共计n次乘法 n次加法 显然第二种方法运算量小 它是我国宋代数学家秦九韶最先提出的 被称为 秦九韶算法 结束 9 显然Pn x vn 0 2 1误差的来源 1模型误差 原始误差 在建立数学模型时 往往要忽视很多次要因素 把模型 简单化 理想化 这时模型就与真实背景有了差距 即带入了误差 2测量误差数学模型中的已知参数 多数是通过测量得到 而测量过程受工具 方法 观察者的主观因素 不可预料的随机干扰等影响必然带入误差 结束 10 0 2误差与有效数字 在运用数学方法解决实际问题的过程中 每一步都可能带来误差 误差分析是一门比较艰深的专门学科 在数值分析中主要讨论截断误差及舍入误差 但一个训练有素的计算工作者 当发现计算结果与实际不符时 应当能诊断出误差的来源 并采取相应的措施加以改进 直至建议对模型进行修改 结束 11 4舍入误差计算机只能处理有限数位的小数运算 初始参数或中间结果都必须进行四舍五入运算 这必然产生舍入误差 3截断误差数学模型常难于直接求解 往往要近似替代 简化为易于求解的问题 这种简化带入误差称为方法误差或截断误差 定义0 1设x 是准确值 x是它的一个近似值 称e x x 为近似值x的绝对误差 简称误差 即 误差一般无法准确计算 只能根据测量或计算情况估计出它的绝对值的一个上限 这个上界称为近似值x的误差限 记为 e x x 其意义是 x x x 在工程中常记为 x x 如l 10 2 0 05mm R 1500 100 结束 12 0 2 2绝对误差与绝对误差限 误差是有量纲的量 量纲同x 它可正可负 绝对误差e 精确值x 近似值x 绝对误差不能完全刻画近似值的精度 如测量百米跑道产生10cm的误差与测量一个课桌长度产生1cm的误差 我们不能简单地认为后者更精确 还应考虑被测值的大小 下面给出定义 0 2 3相对误差与相对误差限 定义0 2误差与精确值的比值称为x的相对误差 记作er 相对误差是无量纲的量 常用百分比表示 它也可正可负 相对误差也常不能准确计算 而是用相对误差限来估计 相对误差限 实际上由于x 不知道 用上式无法确定 r 常用x代x 作分母 此时 结束 14 以后我们就用表示相对误差限 例4在刚才测量的例子中 若测得跑道长为100 0 1m 课桌长为120 1cm 则 定义0 3 结束 15 0 2 4有效数字 显然后者比前者相对误差大 定义0 4 结束 16 如 3 14159265 则3 14和3 1416分别有3位和5位有效数字 而3 143相对于 也只能有3位有效数字 如a 0 034537 则近似数0 0345有3位有效数字又如近似数c 30 4和d 30 40分别有3位和4位有效数字 如计算机上得到方程x3 x 1 0的一个正根为1 32472 保留4位有效数字的结果为1 325 保留5位有效数字的结果为1 3247 相对误差与有效数位的关系十分密切 定性地讲 相对误差越小 有效数位越多 反之亦正确 结束 17 0 3设计算法时应注意的原则 当参与运算的数值带有误差时 结果也必然带有误差 问题是结果的误差与原始误差相比是否扩大 1 对函数f x 的计算 设x是x 的近似值 则结果误差 用泰勒展式分析 忽略第二项高阶无穷小之后 可得函数f x 的误差限估计式 结束 18 0 3 1 数值运算时误差的传播 2 四则运算中误差的传播 其中 0 7 取等号 是因为作为多元函数 加减法的一次函数 泰勒展开没有二次余项 结束 例6 若电压V 220 5V 电阻R 300 10 求电流I并计算其误差限及相对误差限 解 19 所以 结束 1 避免相近数相减由公式 0 7 20 0 3 2算法中应避免的问题 当x1和x2十分相近时 x1 x2接近零 结束 将很大 所以 和 从直观上看 相近数相减会造成有效数位的减少 有时 通过改变算法可以避免相近数相减 大很多 即相对误差将显著扩大 将比 例7 解方程x2 18x 1 0 假定用4位浮点计算 解 用公式解法 可见第二个根只有两位有效数字 精度较差 若第二个根改为用韦达定理计算 可得较好结果 21 结束 如 等等 都可以得到比直接计算好的结果 可改为 如 可改为 若 则 这时 将比 扩大很多 3 防止小数被大数 吃掉 在大量数据的累加运算中 由于加法必须进行对位 有可能出现小数被大数 吃掉 22 2 避免除法中除数的数量级远小于被除数由公式 1 13 结束 如用六位浮点数计算某市的工业总产值 原始数据是各企业的工业产值 当加法进行到一定程度 部分和超过100亿元 0 1 1011 再加产值不足10万元的小企业产值 将再也加不进去 而这部分企业可能为数不少 合计产值相当大 这种情况应将小数先分别加成大数 然后相加 结果才比较正确 这个例子告诉我们 在计算机数系中 加法的交换律和结合律可能不成立 这是在大规模数据处理时应注意的问题 23 4 注意运算步骤的简化减少算术运算的次数以减少误差的积累效应 时参加运算的数字精度应尽量保持一致 否则那些较高精度的量的精度没有太大意义 24 结束 0 4范数 内积定义 设两个n维向量 令 称 x y 为向量x与y的内积 它是向量的一种运算 向量x与y都是列向量时 内积也可写成 x y xTy 范数是在广义长度意义下 对函数 向量 矩阵等元素 长度 的度量定义 结束 25 定义1x和y是Rn中的任意向量 向量范数 是定义在Rn上的实值函数 它满足 容易看出 实数的绝对值 复数的模 三维向量的模都满足以上三条 n维向量的范数概念是它们的自然推广 设向量x x1 x2 xn T 1 x 0 并且 当且仅当x 0时 x 0 非负性 2 kx k x k是一个实数 齐次性 0 4 1向量范数 3 x y x y 三角不等式 1 向量范数定义 其中 经常使用的三种范数为 称为向量X的Lp范数 容易验证 它们都满足三个条件 例8x 1 0 5 0 0 3 T 求解 结束 27 2 不同向量范数的关系 在Rn空间上的任意向量范数等价 即对任意给定的两种范数 有下列关系 m M 其中的m M是正的常数 表示向量或矩阵的 范数 或 3 向量的极限 定义如果称向量序列x k 收敛于向量x 定理向量序列x k 收敛于向量x的充要条件是 例9求向量序列x k 量的极限向量x 解 结束 29 从向量范数出发 可以定义矩阵的范数 定义设A是n n矩阵 定义 0 4 2矩阵范数 为矩阵A的范数 这样定义的范数有如下性质 1 A 0 当且仅当A是零矩阵时 A 0 非负性 2 kA k A 齐次性 1 矩阵范数定义 结束 30 3 两个同阶方阵A B 有 A B A B 三角不等式 4 A B都是n n矩阵 有 AB A B 5 A是n n矩阵 x是n维向量 有 Ax A x 相容性 1是ATA的最大特征值 列范数 2 范数 谱 行范数 2 常用矩阵范数 与向量范数的等价性质类似 矩阵范数之间也是等价的 结束 31 当向量或矩阵的任一种范数趋于零时 其它各种范数也趋于零 因此讨论向量和矩阵序列的收敛性时 可不指明使用的何种范数 证明时 也只要就某一种范数证明就行了 还有一种范数 F范数 它是向量2 范数的直接推广 结束 3