计算方法第一章绪论.pptVIP

计算方法 参考资料 v数值分析李庆扬、王能超、易大义 华 中理工大学出版社1982年 v计算方法算法设计及其MATLAB实现 王能超 ，高等教育出版社 2005年 v计算机数值计算方法及程序设计 周煦 机械工业出版社 v数值方法金一庆 陈越 机械工业出版社 v计算方法引论徐萃薇 高等教育出版社 v计算方法精品课网站/zcr-1.htm v/mathews/numerical.html 考核方式 v一、平时占10分 1平时表现占10分，扣分标准如下（扣到0为止）： v (1)旷课1次扣2分; v (2) 迟到、早退1次扣1分; v (3)违反课堂纪律扣13分; v (4)替答到扣3分，被替扣2分; v (5)上机聊天、玩游戏、带耳机等发现一次扣1分。 v (6) 作业不及格或没交一次扣1分。 v二、实验一表占40（二表占20）分 以最后的实验上机考试分数为准，成绩以百分制给出 ，最后折合。上机考试使用机试系统。程序填空和程序 改错各1题。 v三、期末笔试一表占50分（二表占70分） 笔试试卷以百分制给出，最后折合。第8周课内时间考 。 上机要求 v按学号坐(见上机安排) v课前把程序写在纸上或者把空填好 v教材和实验讲义都带着 v保存自己调好的程序 v交2次实验报告 牛顿迭代、曲线拟合 科学计算的意义 v科学计算与科学实验、科学理论并列为科学方法论 的三大组成部分。 v关键时期和代表性的人物 1.Galileo(1564-1642)是实验物理的开创者，倡导科学的 数学化，为近代科学制订了具体而有效的程序，通过关 键实验，演绎基本原理，达到认识世界的目的，霍金称 他为近代科学奠基人。 Kepler（1571-1630）对行星数据的计算和分析，提出行 星运动三大定律，是按此程序研究的一个成功典范。 科学计算的意义 v2.Newton（1642-1725）开创了微积分，提出了力 学的三大定律，特别是万有引力定律，是科学发展 进入理论思维的标志。 vEinstein（1878-1955）提出的相对论是这种理论思 维的顶峰，在几个世纪中，实验方法和理论分析一 直强有力地推动着科技的发展，科学家们也没有停 止过使用科学计算来进行研究，但由于以前没有计 算机，计算只能是小规模的。 科学计算的意义 vV.Neumann(1903-1957)1945年研制的第一 台计算机带来了科学研究的新的革命，将科 学家从繁重的劳动中解放出来，目前，科学 计算已发展成为一种研究方法，“科学计算与 实验、理论三足鼎立，相辅相成，成为当今 科学活动的三大方法。 1、一个两千年前的例子 今有上禾三秉，中禾二秉，下禾一秉，实三 十九斗； 上禾二秉，中禾三秉，下禾一秉，实三 十四斗； 上禾一秉，中禾二秉，下禾三秉，实二十 六斗。 问上、中、下禾实一秉各几何？ 答曰：上禾一秉九斗四分斗之一。中禾一秉 四斗四分斗之一。下禾一秉二斗四分斗之三 。-九章算术 1、一个两千年前的例子 线性方程组的数值方法！ x是行星运动的轨道，它是时间t 的函数 非线性方程的数值解法 3、全球定位系统（Global Positioning System, GPS) 表示地球上 一个接收点R的当前位 置，卫星Si的位置为 ，则得 到下列非线性方程组 记为 其中 4、已经测得在某处海洋不同深度处的水温如下： 深度（M） 466 741 950 1422 1634 水温（oC）7.04 4.28 3.40 2.54 2.13 根据这些数据，希望合理地估计出其它深度（如 500米，600米，1000米）处的水温 插值法 下面给出的是中国1900年 到2000年的人口数，我 们的目标是预测未来的人 口数（数据量较大时） 195055196 196066207 197082992 198098705 1990114333 2000126743 曲线拟合 建筑上用的一种铝制波纹瓦是用一种机 器将一块平整的铝板压制而成的. 假若要求波纹瓦长4英尺,每个波纹的高度(从 中心线)为1英寸,且每个波纹以近似2英寸 为一个周期. 求制做一块波纹瓦所需铝板的 长度L. 这个问题就是要求由函数f f( (x x)=)=sin xsin x给定的给定的 曲线从曲线从x x=0=0到到x x=48=48英寸间的英寸间的弧长弧长L L. . 由微积分学我们知道由微积分学我们知道, ,所求的弧长可表示为所求的弧长可表示为: : 上述积分称为第二类椭圆积分,它不能用普 通方法来计算. 数值积分 A，B，C是三种蛋白质，其反应如下： 常微分方程的数值方法 A： B： C： 第1章 引论 v1.1 计算方法的研究内容与意义 v1.2 误差 v1.3 数值方法的稳定性与算法设计原则 1.1计算方法的研究内容与意义 v计算方法研究的内容 研究用计算机解决数学问题的数值方法和理论。 计算机解决实际问题的步骤 v实际问题 v建立数学模型 v选择数值算法 v编程计算结果 主要任务 v算法设计及其理论分析和编程实现 算法设计：计算速度、存贮量等 算法分析：收敛性、稳定性及误差分析等 讲授内容 v非线性方程求根、线性方程组求解、插值与拟合、数值积分、常 微分方程初值问题的数值解法 v算法研究的意义 算法研究的意义 引例1 计算n次多项式的值 1. 如果不设计算法需进行的运算次数为： 2. 若简单设计一下算法 这样的算法只需作n次乘法和n次加法运算， 这种方法称为秦九韶算法。 n(n+1)/2次乘法和n次加法。 秦九韶算法 v算法：从已知出发，经过有限次四则运算及规定的 运算顺序构成的完整的计算步骤。 输入多项式的次数n和系数（ an,an-1,a1 ,a0）及x s= an 做循环 i=n-1，0 v s=s*x+ai 输出s v此算法要求上机完成 秦九韶简介 秦九韶（公元12021261），字道古，安岳人。秦九 韶与李冶、杨辉、朱世杰并称宋元数学四大家。其父秦季 栖，进士出身，官至上部郎中、秘书少监。 秦九韶聪敏勤 学。宋绍定四年（1231），秦九韶考中进士，先后担任县 尉、通判、参议官、州守、同农、寺丞等职。先后在湖北 、安徽、江苏、浙江等地做官，1261年左右被贬至梅州（ 今广东梅县），不久死于任所。他在政务之余，对数学进 行虔心钻研，并广泛搜集历学、数学、星象、音律、营造 等资料，进行分析、研究。 宋淳祜四至七年（1244至1247），他在为母亲守孝时 ，把长期积累的数学知识和研究所得加以编辑，写成了闻 名的巨著数学九章，并创造了“大衍求一术”。这 不仅 在当时处于世界领先地位，在近代数学和现代电子计算设 计中，也起到了重要作用，被称为“中国剩余定理”。他所 论的“正负开方术”，被称为“秦九韶程序”。现在，世界各 国从小学、中学到大学的数学课程，几乎都接触到他的定 理、定律和解题原则。秦九韶在数学方面的研究成果，比 英国数学家取得的成果要早500多年。 秦九韶的数学成就及对世界数学的贡献主要表现在： 1、秦九韶的数书九章是一部划时代的巨著 秦九韶潜心研究数学多年，在湖州守孝三年，所写成的世界数学 名著数学九章，癸辛杂识续集称作数学大略，永乐大 典称作数学九章。全书九章十八卷，九章九类：“大衍类”、“ 天时类”、“田域类”、“测望类”、“赋役类”、“钱谷类”、“营建类”、“ 军旅类”、“市物类”，每类9题（9问）共计81题（81问），该书内容 丰富至极，上至天文、星象、历律、测候，下至河道、水利、建筑、 运输，各种几何图形和体积，钱谷、赋役、市场、牙厘的计算和互易 。许多计算方法和经验常数直到现在仍有很高的参考价值和实践意义 ，被誉为“算中宝典”。该书著述方式，大多由“问曰”、“答曰”、“术 曰”、“草曰”四部分组成：“问曰”，是从实际生活中提出问题；“答曰 ”，给出答案；“术曰”，阐述解题原理与步骤；“草曰”，给出详细的 解题过程。此书已为国内外科学史界公认的一部世界数学名著。此书 不仅代表着当时中国数学的先进水平，也标志着中世纪世界数学的最 高水平。我国数学史家梁宗巨评价道：“秦九韶的数书九章（ 1247年）是一部划时代的巨著，内容丰富，精湛绝伦。特别是大衍 求一术（不定方程的中国独特解法）及高次代数方程的数值解法，在 世界数学史上占有崇高的地位。那时欧洲漫长的黑夜犹未结束，中国 人的创造却像旭日一般在东方发出万丈光芒。” 2、秦九韶的“大衍求一术”，领先高斯554年，被康托尔称为“最幸运的天才” 秦九韶所发明的“大衍求一术”，即现代数论中一次同余式组解法，是中世纪世界数 学的最高成就，比西方1801年著名数学家高斯（Gauss，17771855年）建立的同余理 论早554年，被西方称为“中国剩余定理”。秦九韶不仅为中国赢得无尚荣誉，也为世界数 学作出了杰出贡献。 3、秦九韶的任意次方程的数值解领先霍纳572年 秦九韶在数书九章中除“大衍求一术”外，还创拟了正负开方术，即任意高次方 程的数值解法，也是中世纪世界数学的最高成就，秦九韶所发明的此项成果比1819年英 国人霍纳（WGHorner，17861837年）的同样解法早572年。秦九韶的正负方术，列 算式时，提出“商常为正，实常为负，从常为正，益常为负”的原则，纯用代数加法，给 出统一的运算规律，并且扩充到任何高次方程中去。 此外，秦九韶还改进了一次方程组的解法，用互乘对减法消元，与现今的加减消元法完 全一致；同时秦九韶又给出了筹算的草式，可使它扩充到一般线性方程中的解法。在欧 洲最早是1559年布丢（Buteo，约14901570年，法国）给出的，他开始用不很完整的 加减消元法解一次方程组，比秦九韶晚了312年，且理论上的不完整也逊于秦九韶。 秦九韶还创用了“三斜求积术”等，给出了已知三角形三边求三角形面积公式，与海伦（ Heron，公元50年前后）公式完全一致。秦九韶还给出一些经验常数，如筑土问题中的“ 坚三穿四壤五，粟率五十，墙法半之”等，即使对现在仍有现实意义。秦九韶还在十八卷 77问“推计互易”中给出了配分比例和连锁比例的混合命题的巧妙且一般的运算方法，至 今仍有意义。 算法研究的意义 1.克莱姆法则， n=20时计算量为(n+1)n!(n-1) = 9.71020， 理论上可行，用每秒3千亿次的计算机 要算100年。 2. 用高斯消元法，计算量为2670 v算法研究是非常必要的，算法研究包括算法设计和算 法分析。 。 v引例2 求n阶线性方程组的解 1.2 误差 （本章重点：P11-P17） v误差 近似值与准确值之差，称为误差。 v1. 误差的来源： 模型误差 测量误差 截断误差 舍入误差 v 我们只讨论截断误差和舍入误差。 2. 误差的基本概念 定义1.1 设x为准确值，x*为其近似值， 称E=x-x*为近似值x*的绝对误差，简称误差。 称为x*的绝对误差限，简称误差限，也叫精度。 由误差限可知准确值x的范围 x* - xx* + 在工程中常记为 x= x* 2. 误差的基本概念 定义1.2 近似值x*的误差与其准确值x之比 称为近似值x*的相对误差。 均称为相对误差限 实际中经常用代替相对误差限 相对误差绝对值的任一个上界 定义1.3 设x*是准确值x的一个近似值，把它 写成规格化形式 x*= (1.1) (i=1,2,m)为0到9中的某个数字，且 若x*的绝对误差E满足 则称x*有n位有效数字 其中 定理1.1 定理1.1 设x*是准确值x的某个近似值， 其规格化形式为(1.1)， (1) 若x*具有n位有效数字，则x*的相对误差 满足 (2) 若x*的相对误差满足 则x*至少具有n位有效数字。 x*= (1.1) 证明 证证 10k -1=0.110k 于是 (1) 若x*具有n位有效数字，则则 即 10k 证明 (2) 若 则则 于是x*至少具有n位有效数字。 思考 v定理的结论可以再精确一些 精确到什么程度？如何证明？ 提示：从证明的过程，考虑修正定理的结论 10k -1=0.110k 10k 10k -1=0.a110k 0.(a1+1)10k=(a1+1)*10k-1 1.3 数值方法的稳定性与算法设计原则 v算法设计的方法 v算法设计的原则 算法设计的技术 v化大为小的缩减技术 例如秦九韶算法 v化难为易的校正技术 例如牛顿迭代法求a的算术平方根 Xk+1= (xk+a/xk)/2 v化粗为精的松弛技术 龙贝格求积算法 千古绝技“割圆术” 算法设计的原则 1. 防止大数“吃掉”小数 2. 避免两个相近数相减 3. 避免大数作乘数和小数作除数 4. 减少运算次数，避免误差积累 例1 计算x255 5.采用稳定的算法 采用稳定的算法 例1.2 计计算积积分 解： 根据分步积积分公式，可得 即 有两种方法：1.先求I0，再求I1，I2，I9 2. 先求I9，再求I8，I7，I0 例1.2 计算积分 (1) 先计计算 ，然后使用递递推公式 设计设计 算值值的误误差为为 易证证，若 则则 由此可见见，若计计算 时产时产 生了误误差，则则用该该方法计计 算 时时将误误差放大了9!=362880倍，因此该该数值值方 法不可取。这这就是不稳稳定的算法。由于误误差 传传播引起的危害。 误差的传播与积累 例3：蝴蝶效应 一只蝴蝶在巴西扇动翅膀，有可能会在美 国的德克萨斯引起一场龙卷风？！ BXMG 以上是一个病态问题 蝴蝶效应 v先从美国麻省理工学院气象学家洛伦兹（Lorenz） 的发现谈起。为了预报天气，他用计算机求解仿真 地球大气的13个方程式。为了更细致地考察结果， 他把一个中间解取出，提高精度再送回。而当他喝 了杯咖啡以后回来再看时竟大吃一惊：本来很小的 差异，结果却偏离了十万八千里！计算机没有毛病 ，于是，洛伦兹（Lorenz）认定，他发现了新的现 象：“对初始值的极端不稳定性”，即：“混沌”，又 称“蝴蝶效应”，亚洲蝴蝶拍拍翅膀，将使美洲几个 月后出现比狂风还厉害的龙卷风！