北工大数值分析课件

数值分析

NumericalAnalysis董君良北京工业大学/理学院dongjl@计算方法数值分析NumericalAnalysis董君良计算1话说数学

——数学是什么？1.

数学是关于数和形的学问数——代数：数量关系的科学,有序思维占主导,培养逻辑推理能力；形——几何：空间形式的科学,空间想象、形象思维占主导,培养直觉能力和洞察力.数学是一门研究现实世界中数量关系和空间形式的科学

恩格斯话说数学——数学是什么？1.数学是关于数和形的学问2数学的三大核心领域分析

(MathematicalAnalysis)代数

(Algebra)几何

(Geometry)2.

数学科学按内容可分成五大学科

应用数学

(Appliedmathematics)着限于说明自然现象，解决实际问题，是纯粹数学与科学技术之间的桥梁纯粹数学

(Puremathematics)专门研究数学本身的内部规律撇开具体内容，以纯粹形式研究数学的三大核心领域分析(MathematicalAn3计算数学

(Computationmathematics)运筹与控制(Operation&control)概率论与数理统计(Probability

&mathematicalstatistics)数值分析是计算数学的一个主要部分,

它研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现.计算数学(Computationmathematics4从单变量到多变量,从低维到高维;从线性到非线性;从局部到整体,从简单到复杂;从连续到间断,从稳定到分岔;从精确到随机、到模糊;计算机的使用.首先是表现在现代数学的新领域和高层次中，其次是数学向一切学科与社会部门的渗透和应用。现代数学发展的新趋向从单变量到多变量,从低维到高维;从线性到非线5计算机的应用例子求functionmysum=mysum(n)mysum=0Fori=1:1:nmysum=mysum+i;endmysum计算机的应用例子求functionmysum=my6如果线性方程组的系数行列式不等于零，即Crammer法则那么线性方程组有解，并且解是唯一的，可以表示为：如果线性方程组的系数行列式不等于零，即Crammer法则那7

例：求解一个

n

阶线性方程组，如果使用克莱姆法则，需要计算

n+1

个

n

阶行列式，在不计加减运算情况下，至少需要

n!(n2-1)

次乘除运算。当

n=20

时，用每秒运算30亿次（P43.0G）的计算机求解时，大约需要10000年的时间。而如果使用高斯（Gauss）消元法，高斯消去法总的乘除运算量为：大约需要3060次乘除运算，不到一秒钟就能完成。例：求解一个n阶线性方程组，如果使用克莱姆法则，需要计8科学计算科学计算ScientificComputing

(计算科学ComputationalScience)使用数学、统计与计算器的技术，借助计算机高速计算的能力，来解决现代科学、工程、经济或人文中的复杂问题狭义的科学计算是针对某些特定的数学问题，设计有效的计算方法来求解，即为数值计算/数值分析/计算方法/计算数学科学计算是一门工具性、方法性、整合性的新学科，是各种科学与工程计算领域（如：气象、地震、核能技术、石油探勘、航天工程、密码解译等）中不可缺少的工具计算数学是科学计算的核心与基础科学计算科学计算ScientificComputing9科学计算已成为当今科学研究的三种基本手段之一，是数学将触角伸向其他学科的桥梁。科学计算随着计算机的高速发展，数值计算方法已深入到各个科学研究领域，计算性交叉学科不断涌现，如计算力学、计算物理、计算化学、计算生物学、计算经济学等科学计算使用计算机进行科学计算、数据处理及分析已成为人类科技活动的主要方法之一。熟练地使用计算机进行科学计算，已成为科技工作者的一项基本技能

科学计算已成为当今科学研究的三种基本手段之一，是数学将触角10科学计算利用计算机解决实际问题通常分下面几个过程：实际问题数学模型数值方法程序设计上机实现科学计算利用计算机解决实际问题通常分下面几个过程：实际数学11应用举例问：今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？

——《九章算术》例：一个古老的数学问题应用举例问：今有例：一个古老的数学问题12应用举例线性方程组数值求解——教材第五、六章应用举例线性方程组数值求解13应用举例例：人口预测表格中是我国1950年到2005年的人口数（见中国统计年鉴），试预测未来的人口数插值与曲线拟合——教材第二、三章年份人口(万)1950551961955614651960662071965725381970829921975924201980987051985105851199011433199512112120001267432005130756应用举例例：人口预测表格中是我国1950年到2005年的人口14应用举例例：铝制波纹瓦的长度问题建筑上用的一种铝制波纹瓦是由机器将一块平整的铝板压制而成。假若要求波纹瓦长4英尺，每个波纹的高度(从中心线)为1英寸，且每个波纹以近似2

英寸为一个周期。求制做一块波纹瓦所需铝板的长度L。应用举例例：铝制波纹瓦的长度问题建筑上用的一种铝制波纹瓦是由15应用举例这个问题就是要求由函数

f(x)=sinx给定的曲线从x=0

到x=48

英寸间的弧长L，即:数值积分与数值微分——教材第四章上述积分为第二类椭圆积分，无法用普通方法来计算应用举例这个问题就是要求由函数数值积分与数值微分上述积分为第16应用举例矩阵特征值计算——教材第八章例：Google搜索引擎1998年创立，目前市值近2000亿G:GoogleMatrix,“theworld’slargestmatrixcomputation”x:PageRankvector“The$25,000,000,000Eigenvector”——SIAMReview，2006Gx=x,eTx=1应用举例矩阵特征值计算例：Google搜索引擎1998年17

搜索引擎：给定关键词，如何从几十万、几百万的海量网页中找出最有用的信息解决思路网页索引确定网页和查询的关系分类线性代数在Google中的应用搜索引擎：给定关键词，如何从几十万、几百万的海量网页中找出18Http网页链接示意图Http网页链接示意图19

基本原理“从优质的网页链接过来的网页必定还是优质网页”超链接A→B≡A对B投一票若A的质量高（如QQ），则该投票分数高PageRank（衡量网页质量）基本原理“从优质的网页链接过来的网页必定还是优质网页”Pa20

PageRank示意图PageRank示意图21网

页

链

接

矩

阵by

“网络爬虫”网

页

链

接

矩

阵by“网络爬虫”22Google矩阵问题：已知Google矩阵（网页邻接矩阵），如何求出PageRank?首先，PageRank可以表示为向量R=[R1,R2,…,Rn]PageRank（衡量网页质量）Google矩阵问题：已知Google矩阵（网页邻接矩阵），23

PageRank是Google矩阵的主特征向量Google矩阵A记A=AT（关注被链接）A（注意每列为和1向量）PageRank是主特征向量由于网页矩阵规模巨大（数量级约为240×240

），无法采用常规矩阵运算，因此通常采用迭代的方法求解令x=PageRank，则求解x=AxA的最大特征值为1(主特征值)x是主特征值1对应的特征向量PageRank是Google矩阵的主特征向量PageRa24计算方法的任务计算方法/数值分析的任务设计求解各种实际问题的高效可靠的数值方法有效：易于在计算机上实现运算只包括加、减、乘、除以及逻辑运算

可靠：收敛性稳定性等有理论保证高效：尽可能地节省计算时间和存储空间即计算复杂性好对于同一问题，不同的算法在计算性能上可能相差百万倍或者更多！

对求得的数值解的精度进行评估研究数值算法在计算机上的实现计算方法的任务计算方法/数值分析的任务设计求解各种实际问25计算方法例：求解一个n

阶线性方程组，如果使用克莱姆法则，需要计算n+1个n

阶行列式，在不计加减运算情况下，至少需要n!(n2-1)

次乘除运算。而使用高斯消去法，只需约2n3/3

次乘除运算用每秒运算30亿次（主频3.0G）的计算机求解时，大约需要10000年的时间当n=20时，如果使用高斯消去法，不到一秒钟就能完成计算方法例：求解一个n阶线性方程组，如果使用克莱姆法则，26数值方法特点数值分析就是研究数值问题的算法，其特点

方法是近似的，所以求出的解是有误差的与计算机紧密结合：上机实现掌握一门语言：C语言或Fortran语言熟悉一种数学软件：Matlab，Maple或Mathematica有可靠的理论分析，有好的计算复杂性数值试验数值方法特点数值分析就是研究数值问题的算法，其特点方法是27基本概念解析解、精确解、真解、真值：是一种包含分式、三角函数、指数、对数甚至无限级数等基本函数的解的形式

数值解、近似解：利用数值分析的方式来求得

数值算法：求问题的数值解的方法算法的可靠性包括：收敛性，稳定性，误差估计等算法的评价（优劣）时间复杂度（计算机运行时间）空间复杂度（所占用的计算机存储空间）逻辑复杂度（影响程序开发的周期以及维护的难易程度）好的算法－－有可靠的理论分析以及计算复杂性的算法基本概念解析解、精确解、真解、真值：是一种包含分式、三角函28课程信息数值分析（第五版）

教材：李庆扬等编著，清华大学出版社，2008数值分析全程导学及习题全解（第5版）

教材配套辅导书

：清华大学出版社，2010课程信息数值分析（第五版）教材：李庆扬等编著，清华大学出29参考资料

第三种科学方法：计算机时代的科学计算

石钟慈著，清华大学出版社，院士科普书系，2000

科学计算导论（第2版）（英文影印版）

M.T.Heath著，清华大学出版社：McGraw-Hill，2001

现代科学计算

蔡大用，白峰杉，科学出版社，2000

数值线性代数

徐树方等，北京大学出版社，2000

参考资料参考资料第三种科学方法：计算机时代的科学计算

石钟慈著30主要内容插值法函数逼近数值积分和数值微分线性方程组的直接解法和迭代解法非线性方程（组）的数值求解矩阵特征值与特征向量的计算

常微分方程的数值解法主要内容插值法31所需知识微积分高等代数、线性代数常微分方程

Matlab编程所需知识考试方式期末80%平时20%（考勤，课堂表现，平时作业）无期中考试所需知识微积分所需知识考试方式期末80%32数学软件由于各种科学计算问题最后通常都归结为求解一些基本的问题，针对这些基本问题，已有一些相对固定的高效的算法，并设计成软件包。最有名的软件包之一LAPACK——LinearAlgebraPACKage较流行的软件：Matlab，Maple，Mathematica等网络资源：NetLib、GAMS数学软件由于各种科学计算问题最后通常都归结为求解一些基本的问33数值分析

NumericalAnalysis董君良北京工业大学/理学院dongjl@计算方法数值分析NumericalAnalysis董君良计算34话说数学

——数学是什么？1.

数学是关于数和形的学问数——代数：数量关系的科学,有序思维占主导,培养逻辑推理能力；形——几何：空间形式的科学,空间想象、形象思维占主导,培养直觉能力和洞察力.数学是一门研究现实世界中数量关系和空间形式的科学

恩格斯话说数学——数学是什么？1.数学是关于数和形的学问35数学的三大核心领域分析

(MathematicalAnalysis)代数

(Algebra)几何

(Geometry)2.

数学科学按内容可分成五大学科

应用数学

(Appliedmathematics)着限于说明自然现象，解决实际问题，是纯粹数学与科学技术之间的桥梁纯粹数学

(Puremathematics)专门研究数学本身的内部规律撇开具体内容，以纯粹形式研究数学的三大核心领域分析(MathematicalAn36计算数学

(Computationmathematics)运筹与控制(Operation&control)概率论与数理统计(Probability

&mathematicalstatistics)数值分析是计算数学的一个主要部分,

它研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现.计算数学(Computationmathematics37从单变量到多变量,从低维到高维;从线性到非线性;从局部到整体,从简单到复杂;从连续到间断,从稳定到分岔;从精确到随机、到模糊;计算机的使用.首先是表现在现代数学的新领域和高层次中，其次是数学向一切学科与社会部门的渗透和应用。现代数学发展的新趋向从单变量到多变量,从低维到高维;从线性到非线38计算机的应用例子求functionmysum=mysum(n)mysum=0Fori=1:1:nmysum=mysum+i;endmysum计算机的应用例子求functionmysum=my39如果线性方程组的系数行列式不等于零，即Crammer法则那么线性方程组有解，并且解是唯一的，可以表示为：如果线性方程组的系数行列式不等于零，即Crammer法则那40

例：求解一个

n

阶线性方程组，如果使用克莱姆法则，需要计算

n+1

个

n

阶行列式，在不计加减运算情况下，至少需要

n!(n2-1)

次乘除运算。当

n=20

时，用每秒运算30亿次（P43.0G）的计算机求解时，大约需要10000年的时间。而如果使用高斯（Gauss）消元法，高斯消去法总的乘除运算量为：大约需要3060次乘除运算，不到一秒钟就能完成。例：求解一个n阶线性方程组，如果使用克莱姆法则，需要计41科学计算科学计算ScientificComputing

(计算科学ComputationalScience)使用数学、统计与计算器的技术，借助计算机高速计算的能力，来解决现代科学、工程、经济或人文中的复杂问题狭义的科学计算是针对某些特定的数学问题，设计有效的计算方法来求解，即为数值计算/数值分析/计算方法/计算数学科学计算是一门工具性、方法性、整合性的新学科，是各种科学与工程计算领域（如：气象、地震、核能技术、石油探勘、航天工程、密码解译等）中不可缺少的工具计算数学是科学计算的核心与基础科学计算科学计算ScientificComputing42科学计算已成为当今科学研究的三种基本手段之一，是数学将触角伸向其他学科的桥梁。科学计算随着计算机的高速发展，数值计算方法已深入到各个科学研究领域，计算性交叉学科不断涌现，如计算力学、计算物理、计算化学、计算生物学、计算经济学等科学计算使用计算机进行科学计算、数据处理及分析已成为人类科技活动的主要方法之一。熟练地使用计算机进行科学计算，已成为科技工作者的一项基本技能

科学计算已成为当今科学研究的三种基本手段之一，是数学将触角43科学计算利用计算机解决实际问题通常分下面几个过程：实际问题数学模型数值方法程序设计上机实现科学计算利用计算机解决实际问题通常分下面几个过程：实际数学44应用举例问：今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？

——《九章算术》例：一个古老的数学问题应用举例问：今有例：一个古老的数学问题45应用举例线性方程组数值求解——教材第五、六章应用举例线性方程组数值求解46应用举例例：人口预测表格中是我国1950年到2005年的人口数（见中国统计年鉴），试预测未来的人口数插值与曲线拟合——教材第二、三章年份人口(万)1950551961955614651960662071965725381970829921975924201980987051985105851199011433199512112120001267432005130756应用举例例：人口预测表格中是我国1950年到2005年的人口47应用举例例：铝制波纹瓦的长度问题建筑上用的一种铝制波纹瓦是由机器将一块平整的铝板压制而成。假若要求波纹瓦长4英尺，每个波纹的高度(从中心线)为1英寸，且每个波纹以近似2

英寸为一个周期。求制做一块波纹瓦所需铝板的长度L。应用举例例：铝制波纹瓦的长度问题建筑上用的一种铝制波纹瓦是由48应用举例这个问题就是要求由函数

f(x)=sinx给定的曲线从x=0

到x=48

英寸间的弧长L，即:数值积分与数值微分——教材第四章上述积分为第二类椭圆积分，无法用普通方法来计算应用举例这个问题就是要求由函数数值积分与数值微分上述积分为第49应用举例矩阵特征值计算——教材第八章例：Google搜索引擎1998年创立，目前市值近2000亿G:GoogleMatrix,“theworld’slargestmatrixcomputation”x:PageRankvector“The$25,000,000,000Eigenvector”——SIAMReview，2006Gx=x,eTx=1应用举例矩阵特征值计算例：Google搜索引擎1998年50

搜索引擎：给定关键词，如何从几十万、几百万的海量网页中找出最有用的信息解决思路网页索引确定网页和查询的关系分类线性代数在Google中的应用搜索引擎：给定关键词，如何从几十万、几百万的海量网页中找出51Http网页链接示意图Http网页链接示意图52

基本原理“从优质的网页链接过来的网页必定还是优质网页”超链接A→B≡A对B投一票若A的质量高（如QQ），则该投票分数高PageRank（衡量网页质量）基本原理“从优质的网页链接过来的网页必定还是优质网页”Pa53

PageRank示意图PageRank示意图54网

页

链

接

矩

阵by

“网络爬虫”网

页

链

接

矩

阵by“网络爬虫”55Google矩阵问题：已知Google矩阵（网页邻接矩阵），如何求出PageRank?首先，PageRank可以表示为向量R=[R1,R2,…,Rn]PageRank（衡量网页质量）Google矩阵问题：已知Google矩阵（网页邻接矩阵），56

PageRank是Google矩阵的主特征向量Google矩阵A记A=AT（关注被链接）A（注意每列为和1向量）PageRank是主特征向量由于网页矩阵规模巨大（数量级约为240×240

），无法采用常规矩阵运算，因此通常采用迭代的方法求解令x=PageRank，则求解x=AxA的最大特征值为1(主特征值)x是主特征值1对应的特征向量PageRank是Google矩阵的主特征向量PageRa57计算方法的任务计算方法/数值分析的任务设计求解各种实际问题的高效可靠的数值方法有效：易于在计算机上实现运算只包括加、减、乘、除以及逻辑运算

可靠：收敛性稳定性等有理论保证高效：尽可能地节省计算时间和存储空间即计算复杂性好对于同一问题，不同的算法在计算性能上可能相差百万倍或者更多！

对求得的数值解的精度进行评估研究数值算法在计算机上的实现计算方法的任务计算方法/数值分析的任务设计求解各种实际问58计算方法例：求解一个n

阶线性方程组，如果使用克莱姆法则，需要计算n+1个n

阶行列式，在不计加减运算情况下，至少需要n!(n2-1)

次乘除运算。而使用高斯消去法，只需约2n3/3

次乘除运算用每秒运算30亿次（主频3.0G）的计算机求解时，大约需要10000年的时间当n=20时，如果使用高斯消去法，不到一秒钟就能完成计算方法例：求解一个n阶线性方程组，如果使用克莱姆法则，59数值方法特点数值分析就是研究数值问题的算法，其特点

方法是近似的，所以求出的解是有误差的与计算机紧密结合：上机实现掌握一门语言：C语言或Fortran语言熟悉一种数