北工大数值分析课件.ppt

1、数值分析 Numerical Analysis董君良董君良北京工业大学北京工业大学/理学院理学院计 算 方 法话说数学话说数学 数学是什么数学是什么？1 1.数学是关于数和形的学问数学是关于数和形的学问 l 数数 代数代数：数量关系的科学：数量关系的科学,有序思有序思 维占主导维占主导,培养逻辑推理能力；培养逻辑推理能力；l形形 几何几何：空间形式的科学：空间形式的科学,空间想空间想 象、形象思维占主导象、形象思维占主导,培养直觉培养直觉 能力和洞察力能力和洞察力.数学是一门研究现实世界中数量关系和空间数学是一门研究现实世界中数量关系和空间形式的科学形式的科学-恩格斯恩格斯数学的三大核心领域数

2、学的三大核心领域 分析分析(Mathematical Analysis)代数代数(Algebra)几何几何(Geometry)2.数学科学按内容可分成五大学科数学科学按内容可分成五大学科 应用数学应用数学(Applied mathematics)着限于说明自然现象，解决实际问题，是纯粹数学与科学技术之间的桥梁 纯粹数学纯粹数学 (Pure mathematics)专门研究数学本身的内部规律 撇开具体内容，以纯粹形式研究 计算数学计算数学(Computation mathematics)运筹与控制运筹与控制(Operation&control)概率论与数理统计概率论与数理统计(Probabili

3、ty&mathematical statistics)数值分析是计算数学的一个主要部分数值分析是计算数学的一个主要部分,它研究用它研究用计算机计算机求求解各种数学问题的数值计算解各种数学问题的数值计算方法方法及其及其理论理论与软件与软件实现实现.从单变量到多变量从单变量到多变量,从低维到高维从低维到高维;从线性到非线性从线性到非线性;从局部到整体从局部到整体,从简单到复杂从简单到复杂;从连续到间断从连续到间断,从稳定到分岔从稳定到分岔;从精确到随机、到模糊从精确到随机、到模糊;计算机的使用计算机的使用.首先是表现在现代数学的新领域和高层次中，首先是表现在现代数学的新领域和高层次中，其次是数学向

4、一切学科与社会部门的渗透和应用。其次是数学向一切学科与社会部门的渗透和应用。现代数学发展的新趋向现代数学发展的新趋向计算机的应用计算机的应用例子例子 求求1 2 35000?function mysum=mysum(n)mysum=0For i=1:1:n mysum=mysum+i;endmysum如果线性方程组如果线性方程组)1(22112222212111212111 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa的系数行列式不等于零，即的系数行列式不等于零，即nnnnnnaaaaaaaaaD212222111211 0，123123,nnDDDDxxxxDDDD，(2)

5、那么线性方程组那么线性方程组 有解，并且解是唯一的，可有解，并且解是唯一的，可以表示为：以表示为：1111,11,111,11,1njjnjnn jn jnnaaaaDaaaabb又令q 例：求解一个例：求解一个 n 阶线性方程组，如果使用克莱姆法则，阶线性方程组，如果使用克莱姆法则，需要计算需要计算 n+1 个个 n 阶行列式，在不计加减运算情况下，至阶行列式，在不计加减运算情况下，至少需要少需要 n!(n2-1)次乘除运算。当次乘除运算。当 n=20 时，时，用每秒运算用每秒运算30亿次（亿次（P4 3.0G）的计算机求解时，大约需的计算机求解时，大约需要要10000年的时间。年的时间。2

6、02109.7 1)-(2020!而如果使用高斯（而如果使用高斯（Gauss）消元法，消元法，高斯消去法总的乘除运算量为高斯消去法总的乘除运算量为：3233nnn 大约需要大约需要3060次乘除运算，不到一秒钟就能完成。次乘除运算，不到一秒钟就能完成。科学计算科学计算q 科学计算科学计算 Scientific Computing (计算科学计算科学 Computational Science)l 使用数学、统计与计算器的技术，借助计算机高速计算的使用数学、统计与计算器的技术，借助计算机高速计算的能力，来解决现代科学、工程、经济或人文中的复杂问题能力，来解决现代科学、工程、经济或人文中的复杂问题

7、 狭义的科学计算是针对某些特定的数学问题，设计有效的计算狭义的科学计算是针对某些特定的数学问题，设计有效的计算方法来求解，即为方法来求解，即为数值计算数值计算/数值分析数值分析/计算方法计算方法/计算数学计算数学u 科学计算是一门工具性、方法性、整合性的新学科，是各科学计算是一门工具性、方法性、整合性的新学科，是各种科学与工程计算领域（如：气象、地震、核能技术、石油种科学与工程计算领域（如：气象、地震、核能技术、石油探勘、航天工程、探勘、航天工程、密码解译等）中不可缺少的工具密码解译等）中不可缺少的工具计算数学计算数学是科学计算的是科学计算的核心核心与与基础基础u 科学计算已成为当今科学研究的

8、三种基本手段之一，是数科学计算已成为当今科学研究的三种基本手段之一，是数学将触角伸向其他学科的桥梁。学将触角伸向其他学科的桥梁。科学计算科学计算u 随着计算机的高速发展，数值计算方法已深入到各个科学随着计算机的高速发展，数值计算方法已深入到各个科学研究领域，计算性交叉学科不断涌现，如计算力学、计算物研究领域，计算性交叉学科不断涌现，如计算力学、计算物理、计算化学、计算生物学、计算经济学等理、计算化学、计算生物学、计算经济学等 q 科学计算科学计算u 使用计算机进行科学计算、数据处理及分析已成为人类科使用计算机进行科学计算、数据处理及分析已成为人类科技活动的主要方法之一。技活动的主要方法之一。熟

9、练地使用计算机进行科学计算，熟练地使用计算机进行科学计算，已成为科技工作者的一项基本技能已成为科技工作者的一项基本技能 科学计算科学计算q 利用计算机解决实际问题通常分下面几个过程：利用计算机解决实际问题通常分下面几个过程：实际实际问题问题数学数学模型模型数值数值方法方法程序程序设计设计上机上机实现实现应用举例应用举例问：今有问：今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下

10、禾实一秉各几何？问上、中、下禾实一秉各几何？九章算术九章算术3239xyz 2334xyz 2326xyz例：一个古老的数学问题例：一个古老的数学问题应用举例应用举例1112111212222211nnnnnnnnaaaxbaaaxbaaaxb 线性方程组数值求解线性方程组数值求解 教材第五、六章教材第五、六章Axb 应用举例应用举例例：人口预测例：人口预测表格中是我国表格中是我国1950年到年到2005年的人口数（见年的人口数（见中国统计年鉴），试预测未来的人口数中国统计年鉴），试预测未来的人口数插值与曲线拟合插值与曲线拟合 教材第二、三章教材第二、三章年份年份人口人口(万万)1950551

11、961955614651960662071965725381970829921975924201980987051985105851199011433199512112120001267432005130756应用举例应用举例例：例：铝制波纹瓦的长度问题铝制波纹瓦的长度问题建筑上用的一种铝制波纹瓦是由机器将一块平整的铝板压建筑上用的一种铝制波纹瓦是由机器将一块平整的铝板压制而成。假若要求波纹瓦长制而成。假若要求波纹瓦长 4 英尺，每个波纹的高度英尺，每个波纹的高度(从中从中心线心线)为为 1 英寸，且每个波纹以近似英寸，且每个波纹以近似 2 英寸为一个周期。英寸为一个周期。求制做一块波纹瓦所需

12、铝板的长度求制做一块波纹瓦所需铝板的长度 L。应用举例应用举例这个问题就是要求由函数这个问题就是要求由函数 f(x)=sin x给定的曲线从给定的曲线从 x=0 到到 x=48 英寸间的弧长英寸间的弧长 L，即，即:数值积分与数值微分数值积分与数值微分 教材第四章教材第四章484822001()d1(cos)dLfxxxx上述积分为第二类椭圆积分，无法用普通方法来计算上述积分为第二类椭圆积分，无法用普通方法来计算应用举例应用举例矩阵特征值计算矩阵特征值计算 教材第八章教材第八章例：例：Google 搜索引擎搜索引擎1998 年创立，目前市值近年创立，目前市值近2000亿亿G:Google Ma

13、trix,“the worlds largest matrix computation”x:PageRank vector “The$25,000,000,000 Eigenvector”SIAM Review，2006Gx=x,eTx=1 n搜索引擎：给定关键词，如何从几十万、几百搜索引擎：给定关键词，如何从几十万、几百万的海量网页中找出最有用的信息万的海量网页中找出最有用的信息n解决思路解决思路n网页索引网页索引n确定网页和查询的关系确定网页和查询的关系n分类分类线性代数在线性代数在Google中的应用中的应用Http网页链接示意图 n基本原理基本原理“从优质的网页链接过来的网页必定从优质

14、的网页链接过来的网页必定还是优质网页还是优质网页”n超链接超链接AB A 对对B 投一票投一票n若若A的质量高（如的质量高（如QQ），则该投票分数高），则该投票分数高PageRank（衡量网页质量）PageRank示意图网网页页链链接接矩矩阵阵by“网络爬虫”向外的链接数目表示从网页的超链接不存在指向网页网页的超链接指向网页存在从网页iiNjijiiNaaAjijinm)(0 )(/1)(,Google矩阵矩阵n问题：已知问题：已知Google矩阵（网页邻接矩阵），如矩阵（网页邻接矩阵），如何求出何求出PageRank?n首先，首先，PageRank可以表示为向量可以表示为向量nR=R1,R2

15、,RnPageRank（衡量网页质量）nPageRank是是Google矩阵的主特征向量矩阵的主特征向量nGoogle矩阵矩阵An记记A=AT（关注被链接）（关注被链接）nA（注意每列为和（注意每列为和1向量）向量）PageRank是主特征向量n由于网页矩阵规模巨大（数量级约为由于网页矩阵规模巨大（数量级约为240 240），无），无法采用常规矩阵运算，因此通常采用迭代的方法求解法采用常规矩阵运算，因此通常采用迭代的方法求解n令令 x=PageRank，则，则n求解求解 x=Ax nA的最大特征值为的最大特征值为1(主特征值主特征值)nx是主特征值是主特征值1对应的特征向量对应的特征向量计算方

16、法的任务计算方法的任务q 计算方法计算方法/数值分析的任务数值分析的任务u 设计求解各种实际问题的设计求解各种实际问题的高效可靠高效可靠的的数值方法数值方法l 有效：易于在计算机上实现有效：易于在计算机上实现 运算只包括加、减、乘、除以及逻辑运算运算只包括加、减、乘、除以及逻辑运算l 可靠：收敛性稳定性等有理论保证可靠：收敛性稳定性等有理论保证l 高效：尽可能地节省计算时间和存储空间高效：尽可能地节省计算时间和存储空间 即计算复杂性好即计算复杂性好对于同一问题，不同的算法在计算性能上可对于同一问题，不同的算法在计算性能上可能相差百万倍或者更多！能相差百万倍或者更多！u 对求得的对求得的数值数值

17、解的精度进行评估解的精度进行评估u 研究数值算法研究数值算法在计算机上在计算机上的的实现实现计算方法计算方法例：例：求解一个求解一个 n 阶线性方程组，如果使用阶线性方程组，如果使用克莱姆法则克莱姆法则，需，需要计算要计算 n+1 个个 n 阶行列式，在不计加减运算情况下，至少阶行列式，在不计加减运算情况下，至少需要需要 n!(n2-1)次乘除运算。而使用高斯消去法，只需约次乘除运算。而使用高斯消去法，只需约2n3/3 次乘除运算次乘除运算用每秒运算用每秒运算 30 亿次（主频亿次（主频3.0G）的计算机求解时，大的计算机求解时，大约需要约需要10000年的时间年的时间 22020!(201)

18、9.710 l 当当 n=20 时，时，如果使用高斯消去法，不到一秒钟就能完成如果使用高斯消去法，不到一秒钟就能完成 数值方法特点数值方法特点q 数值分析就是研究数值问题的算法，其特点数值分析就是研究数值问题的算法，其特点u 方法是近似的方法是近似的，所以求出的解是有误差的，所以求出的解是有误差的u 与计算机紧密结合：上机实现与计算机紧密结合：上机实现l 掌握一门语言：掌握一门语言：C 语言或语言或 Fortran 语言语言l 熟悉一种数学软件：熟悉一种数学软件：Matlab，Maple 或或 Mathematicau 有可靠的理论分析，有可靠的理论分析，u 有好的计算复杂性有好的计算复杂性u

19、 数值试验数值试验基本概念基本概念l 解析解、精确解、真解、真值：解析解、精确解、真解、真值：是一种包含分式、三角函是一种包含分式、三角函数、指数、对数甚至无限级数等数、指数、对数甚至无限级数等 基本函数的解的形式基本函数的解的形式 l 数值解、近似解：数值解、近似解：利用数值分析的方式来求得利用数值分析的方式来求得 l 数值算法：求问题的数值算法：求问题的数值解数值解的方法的方法u 算法的可靠性包括：算法的可靠性包括：收敛性收敛性，稳定性稳定性，误差估计误差估计等等u 算法的评价（优劣）算法的评价（优劣）l 时间时间复杂度（计算机运行时间）复杂度（计算机运行时间）l 空间空间复杂度（所占用的

20、计算机存储空间）复杂度（所占用的计算机存储空间）l 逻辑逻辑复杂度（影响程序开发的周期以及维护的难易程度）复杂度（影响程序开发的周期以及维护的难易程度）好的算法有可靠的理论分析以及计算复杂性的算法好的算法有可靠的理论分析以及计算复杂性的算法课程信息课程信息数值分析数值分析（第五版）（第五版）q 教材教材：李庆扬等编著，清华大学出版社，李庆扬等编著，清华大学出版社，2002008 8数值分析数值分析全程导学及习题全解（第全程导学及习题全解（第5 5版）版）q 教材配套辅导书教材配套辅导书：清华大学出版社，清华大学出版社，20201010参考资料参考资料l 第三种科学方法：计算机时代的科学计算第三

21、种科学方法：计算机时代的科学计算 石钟慈著，石钟慈著，清华大学出版社，院士科普书系清华大学出版社，院士科普书系，2000l 科学计算导论科学计算导论（第（第 2 版）（英文影印版）版）（英文影印版）M.T.Heath 著，清华大学出版社：著，清华大学出版社：McGraw-Hill，2001l 现代科学计算现代科学计算 蔡大用，白峰杉，科学出版社，蔡大用，白峰杉，科学出版社，2000l 数值线性代数数值线性代数 徐树方徐树方等，北京大学出版社，等，北京大学出版社，2000&参考资料参考资料主要内容主要内容q 插值法插值法q 函数逼近函数逼近q 数值积分和数值微分数值积分和数值微分q 线性方程组的

22、直接解法和迭代解法线性方程组的直接解法和迭代解法q 非线性方程（组）的数值求解非线性方程（组）的数值求解q 矩阵特征值与特征向量的计算矩阵特征值与特征向量的计算q 常微分方程的数值解法常微分方程的数值解法所需知识所需知识l 微积分微积分l 高等代数、线性代数高等代数、线性代数l 常微分方程常微分方程l Matlab 编程编程q 所需知识所需知识q 考试方式考试方式l 期末期末 80%l 平时平时 20%（考勤，课堂表现，平时作业）（考勤，课堂表现，平时作业）l无期中考试无期中考试数学软件数学软件由于各种科学计算问题最后通常都归结为求解一些由于各种科学计算问题最后通常都归结为求解一些基本的问基本的问题题，针对这些基本问题，已有一些相对固定的高效的算法，针对这些基本问题，已有一些相对固定的高效的算法，并设计成软件包。并设计成软件包。l 最有名的软件包之一最有名的软件包之一 LAPACK Linear Algebra PACKagel 较流行的软件：较流行的软件：Matlab，Maple，Mathematica 等等l 网络资源：网络资源：NetLib、GAMS