陈研 chenyan@cau.edu.cn Tel:62732959 新学科综合楼 4-201 数 值 计 算 方 法 陈研 chenyan@cau.edu.cn Tel:62732959 新学科综合楼 4-201 中国农业大学资源和环境学院 2005年9月.

Presentation on theme: "陈研 chenyan@cau.edu.cn Tel:62732959 新学科综合楼 4-201 数 值 计 算 方 法 陈研 chenyan@cau.edu.cn Tel:62732959 新学科综合楼 4-201 中国农业大学资源和环境学院 2005年9月."— Presentation transcript:

1 陈研 chenyan@cau.edu.cn Tel:62732959 新学科综合楼 4-201
数 值 计 算 方 法 陈研 Tel: 新学科综合楼 4-201 中国农业大学资源和环境学院 2005年9月

2 §1 数值计算方法的意义、内容与方法 20 世纪最伟大的科学技术发明---计算机 计算机是对人脑的模拟，它强化了人的思维智能； 计算机的发展和应用，已不仅仅是一种科学技术 现象，而且成了一种政治、军事、经济和社会现象； 没有软件的支持，超级计算机只是一堆废铁而已； 软件的核心就是算法。 算法犹如乐谱， 软件犹如CD盘片， 而硬件如同CD唱机。

3 现代科学研究的三大支柱 算法的研究和应用正是本课程的主题 ！ 理论研究 科学实验 科学计算 计算数学

4 21世纪信息社会的两个主要特征： “计算机无处不在” “数学无处不在” 21世纪信息社会对科技人才的要求： --会“用数学”解决实际问题 --会用计算机进行科学计算

5 建立数学模型 选取计算方法 计算得出结果 编写上机程序 科学计算解题过程

6 一、计算数学的产生和早期发展 计算数学是数学的一个古老的分支，虽然数学不仅仅 是计算，但推动数学产生和发展的最直接原因还是 计算问题。 二、二十世纪计算数学的发展 数值代数 概率统计计算 最优化计算 蒙特卡罗方法 数值逼近 微分方程的数值解法 计算几何 微分方程的反演问题

7 数值计算的主要内容 数值代数：方程求根、线性方程组求解、 特征值和特征向量的计算、 非线性方程组的求解； 数值逼近：插值、数值微分和积分、
最小二乘法； 微分方程数值解： 常微分方程数值解； 偏微分方程数值解： 差分法 有限元法 有限体积法

8 教材 参考书目 数值计算方法 徐涛 编著 （吉林科学技术出版社）  应用数值方法 使用MATLAB和C语言
数值计算方法 徐涛 编著 （吉林科学技术出版社） 参考书目  应用数值方法 使用MATLAB和C语言 Robert J.Schilling & Sandra L.Harris （机械工业出版社）  Numerical Recipes in C++ The Art of Scientific Computing Second Edition William H.Press 等著 （电子工业出版社）  现代数值分析 李庆扬、易大义、王能超 编著 （高等教育出版社）

9 §2 算 法 一、算法的概念 定义：由基本运算及运算顺序的规定所构成的完整的 解题步骤，称为算法。
§2 算 法 一、算法的概念 定义：由基本运算及运算顺序的规定所构成的完整的 解题步骤，称为算法。 描述算法可以有不同的方式。例如，可以用日常语言 和数学语言加以叙述，也可以借助形式语言（算法语言） 给出精确的说明，也可以用框图直观地显示算法的全貌。

10 例1：一群小兔一群鸡，两群合到一群里，要数腿共48， 要数脑袋整17，多少小兔多少鸡？
算术方法 ： 代数方法 ： 若没有小兔，则鸡应是17只 设有x只小鸡，y只小兔 ， 总腿数 ：2＊17＝34 一只小兔增加 2条腿， 应该有 (-2)*(i) +(ii) , 得 高斯消去法 只小兔 只小兔 10只小鸡

11 例：求解二元一次联立方程组 用行列式解法：首先判别 是否为零，存在两种可能： （1）如果 ，则令计算机计算 输出计算的结果x1，x2。 （2）如果D= 0，则或是无解，或有无穷多组解。

12 令 通过求解过程，可以总结出算法步骤如下： S1 输入 S2 计算 S3 如果 则输出原方程无解或有无穷多组解的信息; 否则 S4 输出计算的结果

13 输入 D=a11a22-a12a21 D=0 开始 输出 x1, x2 结 束 No 输出无解信息 Yes

14 二、算法的优劣  计算量小 例：用行列式解法求解线性方程组: n阶方程组，要计算n + 1个n阶行列式的值，
 存贮量少  逻辑结构简单

15 §3 数值计算中的误差 一、 误差的背景介绍 1. 来源与分类 从实际问题中抽象出数学模型 —— 模型误差
§3 数值计算中的误差 一、 误差的背景介绍 1. 来源与分类 从实际问题中抽象出数学模型 —— 模型误差 例1:质量为m的物体，在重力作用下，自由下落， 其下落距离s 与时间t 的关系是： （1.1） 其中 g 为重力加速度。

16 通过测量得到模型中参数的值 —— 观测误差 求近似解 —— 方法误差 (截断误差） 机器字长有限 —— 舍入误差 用计算机、计算器和笔算，都只能用有限位小数 来代替无穷小数或用位数较少的小数来代替位数较多 的有限小数，如：  = … x =

17 四舍五入后…… 在数值计算方法中，主要研究截断误差和舍入误差 （包括初始数据的误差）对计算结果的影响！

18 二、绝对误差、相对误差和有效数字 1．绝对误差与绝对误差限 定义1：设x是准确值，x*为x的一个近似值，称 是近似值x的绝对误差,简称为误差。 （1.5） 例 2:若用以厘米为最小刻度的尺去量桌子的长， 大约为1.45米，求1.45米的绝对误差。 1.45米的 绝对误差=？ 不知道！

19 但实际问题往往可以估计出 不超过某个正数，即，
，则称  为绝对误差限，有了绝对误差限 就可以知道x范围为 即x落在 内。在应用上，常常采用下列 写法来刻划x*的精度。

20 2．相对误差和相对误差限 定义2：设x是准确值，x*是近似值，称 （1.6） 为近似值x的相对误差，相应地，若正数 ， 满足 则称 为x的相对误差限。

21 3．有效数字 定义3：如果 （1.7） 则说x*近似表示x准确到小数后第n位，并从这第n位起 直到最左边的非零数字之间的一切数字都称为有效数字， 并把有效数字的位数称为有效位数。 由上述定义 有效数位为3位 有效数位为5位 有效数位为4位

22 误差的传播与积累 例3：蝴蝶效应 —— 纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！ NY BJ 以上是一个病态问题

23 §4 数值计算中应该注意的一些原则 1．要使用数值稳定的算法 例4：求 （n = 0, 1, 2, …, 8）的值。 解：由于 初值

24 递推公式 （1.8） 按 (1.8) 式就可以逐步算出 注意此公式精确成立 What happened?! 不稳定的算法 ！

25 这就是误差传播所引起的危害 ! 由递推公式（1.8）可看出，In-1的误差扩大了5倍后传给In， 因而初值I0的误差对以后各步计算结果的影响，随着n的增大 愈来愈严重。这就造成I4的计算结果严重失真。 改变公式： 将公式 变为 （1.9） 不妨设I9  I10，于是由 可求得I9  0.017，按公式（1.9）可逐次求得

26 I8  I7  0.021 I6  I8  0.028 I4  I3  0.043 I2  I1  0.088 I0  0.182 稳定的算法 ！ 在我们今后的讨论中，误差将不可回避， 算法的稳定性会是一个非常重要的话题。

27 2．要避免两个相似数相减 在数值计算中，两个相近的数作减法时有效数字会损失。 例5: 求 （1.10） 的值。当x = 1000，y 的准确值为 1、直接相减 2、将（1.10）改写为 则 y =

28 类似地 2. 绝对值太小的数不宜作除数 例6： 如分母变为0.0011，也即分母只有0.0001的变化时

29 3. 避免大数吃小数 例7：用单精度计算 的根。 精确解为  算法1：利用求根公式
例7：用单精度计算 的根。 精确解为  算法1：利用求根公式 在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为1010，则：1 =  1010，取单精度时就成为： 109+1=  1010= 1010

30 4. 先化简再计算，减少步骤，避免误差积累。 算法2：先解出 再利用 注：求和时从小到大相加，可使和的误差减小。
例8：按从小到大、以及从大到小的顺序分别计算 … 4. 先化简再计算，减少步骤，避免误差积累。 一般来说，计算机处理下列运算的速度为

31 5.算法的递推性 计算机上使用的算法常采用递推化的形式，递推 化的基本思想是把一个复杂的计算过程归结为简单过程
的多次重复。这种重复在程序上表现为循环。递推化的 优点是简化结构和节省计算量。 多项式求值：给定的x 求下列n 次多项多的值。 解：1. 用一般算法，即直接求和法； 2. 逐项求和法； 3. 秦九韶方法；

32 例9：用秦和韶方法求多项式 在x = - 0.2的值。 解： K a5-K vK 0.00833 v0 = a5 1 0.04167
v0 = a5 1 0.04 v1 = v0x+a4 2 v2 = v1x+a3 3 0.5 v3 = v2x+a2 4 1 v4 = v3x+a1 5 1 v5 = v4x+a0