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