第0章 绪 论
0.1 计算方法研究的基本问题利用数学方法解决实际问题通常包括:分析实际问题,建立数学模型,开发求解的算法,编写求解程序,以及运行程序并得到近似结果这五个步骤。其中前面两步为建模,后面三步为模型求解。
计算方法所面对的正是"模型求解",或者说求模型的数值解。因此我们不能把"计算方法"理解为"计算"的"方法",而应理解为利用计算工具求解复杂数学问题的方法论和基本方法。
1.关于模型的解释模型是使用频率极高的一个科技词汇,在不同的领域内,模型有不同的含义。对于控制专业的学生来说,模型可以理解为系统或者所对系统的描述。对于学习计算方法来说,数学模型就是表示实际问题的数学形式,它可以很简单,也可以很复杂。
在中学里的我们经常列线性方程组解应用题,列方程可看成是建模,解方程就是模型求解。在中学里,我们是列方程难而解方程容易。
在大学里的我们通常要列微分方程(组)解应用题,显然,教科书中介绍的求解析解的方法不仅难,而且不太实用。
2.数值计算问题的提出在实际工作中,我们经常要借助数学模型来描述实际的系统,借助数学方法完成比如系统建模,系统仿真,系统评估,系统优化,系统控制等一系列任务,这其中通常有大量的,非常复杂的数值计算问题。例如:
求解1000个变量,1000个线性方程组成的方程组;
用汇编语言编写求正数的算术平方根或立方根的程序;
通过实验确定弹簧的长度y与所受的拉力x的线性函数y=ax+b中的常数a和b;
3.计算工具的局限性数值计算依赖于一定的计算工具。现在我们已经有了高性能的电子计算机和丰富的软件,这为我们进行数值计算提供了难得的物质基础,但这还远远不够。
今天的电子计算机如果仅考虑它能进行那些基本运算,那么它们的真正的计算能力也只是对有限位的数进行加、减、乘、除这四则算术运算,和早期的计算工具相比,并不具有特别的优势。
今天,作为科技计算和工程控制的主要工具有计算器,各类大,中,小,微型计算机以及单片机。从数值计算的角度看,它们都只能对具有一定数位的数进行加减乘除四则运算。
4.计算方法研究的基本问题现在摆在我们面前的基本矛盾是:一方面随着科学技术的不断进步,我们需要求数值解的问题愈来愈复杂;另一方面,我们使用的计算工具都只能进行有限数位的数的加、减、乘、除四则运算。
计算方法研究的基本问题是如何把(实际中提出来的)复杂的数学问题的求解都尽可能有效地转化为对有限数位的数进行有限次数的四则运算。
5.努力跟上时代的步伐(现代问题)
现在我们使用的计算工具是电子数字计算机,虽然也只能进行有限位的四则运算,但和早期的计算工具相比,却具有存贮程序的能力,这可以免去我们大量的重复劳动利用计算机进行数值计算,从本质上将是求函数值,也就是由程序的输入产生输出。除汇编语言以外,几乎所有的程序设计语言都提供了求基本初等函数值的功能,所以初等函数值的计算问题已基本解决。
计算方法现在要解决的主要问题已上升为非初等函数求值计算,比如ln(x)的原函数不是初等函数,求ln(x)在区间[1,2]上的定积分就是一个问题。
6.对控制专业大学生的现实意义学习计算方法对于我们控制系的大学生来说,更有着特殊的现实意义:
当我们用单片机进行工程控制时,我们将直接利用单片机的指令系统编程,这就要求我们能够把复杂的计算问题转化为有限数位的数的四则运算问题。
求微分方程的数值解既是计算方法研究的典型问题,也是控制专业的学生将来会遇到的实际问题。
0.2计算方法课程的基本内容
1.误差分析
2.求函数的零点问题
3.解线性方程组的直接方法
4.曲线拟合
5.多项式插值
6.数值积分和数值微分
7.求常微分方程的数值解
8.与矩阵有关的各种计算问题
0.3 利用机器计算的基本方法
1离散化方法设f(x)是定义在[a,b]上的连续函数,当它们的表达式很复杂,甚至写不出来时,我们可以选择若干个离散点x0,x1,…,xn∈[a,b],求出f(x)在这些点处的函数值或函数值的近似值fi= f(xi) i=0,1,…,n,从而得到一个如下的函数值列表:
表1:离散的函数值列表
x
x0
x1
…
xn
f(x)
f0
f1
…
fn
提示:对于一个实际的控制系统来说,我们可以直接由数据采集系统获得上面的函数值列表,比如在一些离散的时刻点的温度、压力等等。
2插值方法对于任意给出的函数值列表,我们可以构造一个简单函数,比如n次多项式pn(x),满足条件
pn(xi)= fi i=0,1,…,n
并利用pn(x)近似表示f(x)。
提示:由于pn(x)是一个多项式函数,所以求它在某一点处的函数值、在某一点处的导数值、在某个区间上的定积分所涉及的计算都是四则运算,从而我们的问题得到了解决。
3逼近的方法设f(x)是满足某种特定条件的函数(比如在某个区间上连续可微、在某个区间上平方可积等),表达式比较复杂甚至写不出来,但是我们可以把它表示为一个简单函数系列{fn(x),n=1,2,…}的极限,即
Lim fn(x)=f(x) (n(∞)
这样我们就可以根据不同的精度要求选取适当大的正数N,利用fN(x)近似替代f(x)。
提示:如果f(x)可以展为泰勒级数,那么我们可以取fn(x)为f(x)的泰勒展式前n+1项。
4迭代的方法假如我们要计算出某个实际值x*,我们可以构造一个序列{xn,n=0,1,2,…},满足条件:
x0为已知值;
有一个简单函数φ(t),且xn+1=φ(xn),n=0,1,2,…
lim xn=x* (n→∞)
那么,我们可以反复利用xn+1=φ(xn),经过N次迭代后,用xN作为x*的近似值。
0.4 学好计算方法的几个的层次计算方法内容广泛,方法众多,即使同一个问题也可以有多种方法,要学好计算方法这门课,我们需要从几个不同的层面上来理解计算方法,从而理顺我们的思路。
1.把计算方法理解为一门学科计算方法作为一门学科,要解决的基本问题还是如何把复杂的科技数值计算问题有效地转化为只有一定数位的数的四则运算问题。
计算方法的内容是大学数学教科书中的遗留问题。但我们决不能把计算方法简单地理解为一门数学课。在电子计算机问世以前可以说是的,现在不能。
学习计算方法的目的是为了用数学方法解决实际问题,侧重点是求模型的数值解。我们可以通过对一些些典型的数学问题的研究形成一般性的方法体系,这样可以保事半功倍的效果。
2.把计算方法理解为数学方法的伸延我们现在毕竟是"学习"计算方法,期望值暂不要求太高,能顺利通过各种考试也行。既然我们的计算方法是结合大学数学教科书中的典型问题求数值解展开的,那么数学中相应的概念、定理、法则、公式对于我们求数值解肯定是有帮助的。
当我们研究典型的数学问题的数值解方法时,比如求数值积分和数值微分、求微分方程的数值解,我们完全可以把它们看作是数学教科书中的遗留问题。把它们留在这里集中解决,可以收到事半功倍的效果。
3.把计算方法理解为求解数学问题的计算机方法对于一个典型问题来说,无论用什么工具求数值解都需要算法。算法是为了解决特定问题或完成特定的任务而设计的一系列操作步骤。算法可以用自然语言来描述,也可以用流程图来描述。
在计算机非常普及的今天,对一些典型的数学问题求数值解得到的计算方法实际也就是计算机方法,也就是能够由计算机来执行的算法。
4,算法举例·多项式求值的秦九韶算法设有多项式 pn(x)=a0+a1x+…+anxn
它可以表为 pn(x)=(…((an)*x+an-1)*x+…a1)*x+a0
如果我们用一个共同的中间变量来表示每一层括号内的结果,即可形成一个算法。 算法说明如下:
1输入 n,a[0],a[1],…,a[n],x0
2设置 k=n,s=a[n]
3 for( k=n;k>0;k-- ){s*=x; s+=a[k-1];}
3输出 s
注意:这个算法特别适合用计算器来计算。
4,小结不管是过去还是今天,计算方法研究的基本问题没有发生是值的改变。但是过去的计算方法是面向手工和原始计算工具的,而今天的计算方法应当是面向是电子数字计算机的。
计算方法是连接工程数学、实际问题求解、计算机程序设计的中间环节。学会了利用计算机求解工程数学中的一些典型问题后,我们不难进一步利用计算机求解实际问题!
0.5关于算法的评价(简单介绍)
既然研究典型的数学问题的计算方法、或者说数值解方法最后都要用"算法"来描述,所以对具体的计算方法的评价也就转化为对算法的评价。一个算法的好或不太理想可用数值稳定性,计算量,存贮量这几个指标来刻画,近年来又增加了一条就是程序的可读性好。
1数值稳定性当我们用计算机进行数值计算时,计算机的输入和输出都是数值,而且在大多数情况下都是近似值。当输入的数据的误差被限制在某个允许范围内时,我们自然希望结果的误差也被限制在某个范围之内,至少我们不希望看到在计算过程中由于出现数字溢出而停机。
一个好的算法应当具有数值稳定性,也就是说,最后输出的结果是有效的。
2.节省计算时间我们有两种方式来评估计算时间,如果是有限步完成的计算问题,我们可以估算计算量;对于一个迭代过程来说,我们用收敛速率来描述计算时间。
(1)计算量的定义我们把作一次浮点数的乘法运算连同一次加法运算的计算量作为计算量的计量单位。
例如:假设A=(ai j)l×m,B=(bi j)m×n分别为 l×m 和m×n矩阵,记C=A·B,则C为l×n矩阵,由于
ci j=ai 1·b1 j+ ai 2·b2 j +...+ai m·bm j
所以求ci j的计算量为m,所以求C的计算量就是m·n·l,我们习惯上把它记为O(m·n·l),其含义是大体上与m·n·l成正比。
(2)收敛速率的定义:
在一个迭代过程中,如果我们有
其中c为常数,则称{xn}p阶收敛于x*,当p=1时,称算法具有线性速率收敛;当1<p<2时,称算法具有超线性收敛速率;当p=2时,称算法具有二次终结性质或二次收敛速率。
3.节省存贮空间节省存贮空间有两层含义:
第一层含义是指算法简单,因而程序就短,程序本身所占用的存贮空间便少;
第二层含义是指所需要保留的中间结果比较少,这样就可以省下为了保留中间结果所需要的额外的存贮空间。
这个问题的重要性现在已经大大降低了。
4.程序的可读性好在计算机发展的早期,人们使用计算机要支付高昂的机时费,所以程序员为了节省机时,往往会采用一些编程技巧,这样一来便增加了阅读程序的困难,也不便于软件的维护。现在由于技术的进步,计算机的机时费用已大大降低;另一方面,开发软件的费用又在大幅度上升,所以我们不鼓励为了过分节省计算机时间而牺牲程序的可读性。
0.1 计算方法研究的基本问题利用数学方法解决实际问题通常包括:分析实际问题,建立数学模型,开发求解的算法,编写求解程序,以及运行程序并得到近似结果这五个步骤。其中前面两步为建模,后面三步为模型求解。
计算方法所面对的正是"模型求解",或者说求模型的数值解。因此我们不能把"计算方法"理解为"计算"的"方法",而应理解为利用计算工具求解复杂数学问题的方法论和基本方法。
1.关于模型的解释模型是使用频率极高的一个科技词汇,在不同的领域内,模型有不同的含义。对于控制专业的学生来说,模型可以理解为系统或者所对系统的描述。对于学习计算方法来说,数学模型就是表示实际问题的数学形式,它可以很简单,也可以很复杂。
在中学里的我们经常列线性方程组解应用题,列方程可看成是建模,解方程就是模型求解。在中学里,我们是列方程难而解方程容易。
在大学里的我们通常要列微分方程(组)解应用题,显然,教科书中介绍的求解析解的方法不仅难,而且不太实用。
2.数值计算问题的提出在实际工作中,我们经常要借助数学模型来描述实际的系统,借助数学方法完成比如系统建模,系统仿真,系统评估,系统优化,系统控制等一系列任务,这其中通常有大量的,非常复杂的数值计算问题。例如:
求解1000个变量,1000个线性方程组成的方程组;
用汇编语言编写求正数的算术平方根或立方根的程序;
通过实验确定弹簧的长度y与所受的拉力x的线性函数y=ax+b中的常数a和b;
3.计算工具的局限性数值计算依赖于一定的计算工具。现在我们已经有了高性能的电子计算机和丰富的软件,这为我们进行数值计算提供了难得的物质基础,但这还远远不够。
今天的电子计算机如果仅考虑它能进行那些基本运算,那么它们的真正的计算能力也只是对有限位的数进行加、减、乘、除这四则算术运算,和早期的计算工具相比,并不具有特别的优势。
今天,作为科技计算和工程控制的主要工具有计算器,各类大,中,小,微型计算机以及单片机。从数值计算的角度看,它们都只能对具有一定数位的数进行加减乘除四则运算。
4.计算方法研究的基本问题现在摆在我们面前的基本矛盾是:一方面随着科学技术的不断进步,我们需要求数值解的问题愈来愈复杂;另一方面,我们使用的计算工具都只能进行有限数位的数的加、减、乘、除四则运算。
计算方法研究的基本问题是如何把(实际中提出来的)复杂的数学问题的求解都尽可能有效地转化为对有限数位的数进行有限次数的四则运算。
5.努力跟上时代的步伐(现代问题)
现在我们使用的计算工具是电子数字计算机,虽然也只能进行有限位的四则运算,但和早期的计算工具相比,却具有存贮程序的能力,这可以免去我们大量的重复劳动利用计算机进行数值计算,从本质上将是求函数值,也就是由程序的输入产生输出。除汇编语言以外,几乎所有的程序设计语言都提供了求基本初等函数值的功能,所以初等函数值的计算问题已基本解决。
计算方法现在要解决的主要问题已上升为非初等函数求值计算,比如ln(x)的原函数不是初等函数,求ln(x)在区间[1,2]上的定积分就是一个问题。
6.对控制专业大学生的现实意义学习计算方法对于我们控制系的大学生来说,更有着特殊的现实意义:
当我们用单片机进行工程控制时,我们将直接利用单片机的指令系统编程,这就要求我们能够把复杂的计算问题转化为有限数位的数的四则运算问题。
求微分方程的数值解既是计算方法研究的典型问题,也是控制专业的学生将来会遇到的实际问题。
0.2计算方法课程的基本内容
1.误差分析
2.求函数的零点问题
3.解线性方程组的直接方法
4.曲线拟合
5.多项式插值
6.数值积分和数值微分
7.求常微分方程的数值解
8.与矩阵有关的各种计算问题
0.3 利用机器计算的基本方法
1离散化方法设f(x)是定义在[a,b]上的连续函数,当它们的表达式很复杂,甚至写不出来时,我们可以选择若干个离散点x0,x1,…,xn∈[a,b],求出f(x)在这些点处的函数值或函数值的近似值fi= f(xi) i=0,1,…,n,从而得到一个如下的函数值列表:
表1:离散的函数值列表
x
x0
x1
…
xn
f(x)
f0
f1
…
fn
提示:对于一个实际的控制系统来说,我们可以直接由数据采集系统获得上面的函数值列表,比如在一些离散的时刻点的温度、压力等等。
2插值方法对于任意给出的函数值列表,我们可以构造一个简单函数,比如n次多项式pn(x),满足条件
pn(xi)= fi i=0,1,…,n
并利用pn(x)近似表示f(x)。
提示:由于pn(x)是一个多项式函数,所以求它在某一点处的函数值、在某一点处的导数值、在某个区间上的定积分所涉及的计算都是四则运算,从而我们的问题得到了解决。
3逼近的方法设f(x)是满足某种特定条件的函数(比如在某个区间上连续可微、在某个区间上平方可积等),表达式比较复杂甚至写不出来,但是我们可以把它表示为一个简单函数系列{fn(x),n=1,2,…}的极限,即
Lim fn(x)=f(x) (n(∞)
这样我们就可以根据不同的精度要求选取适当大的正数N,利用fN(x)近似替代f(x)。
提示:如果f(x)可以展为泰勒级数,那么我们可以取fn(x)为f(x)的泰勒展式前n+1项。
4迭代的方法假如我们要计算出某个实际值x*,我们可以构造一个序列{xn,n=0,1,2,…},满足条件:
x0为已知值;
有一个简单函数φ(t),且xn+1=φ(xn),n=0,1,2,…
lim xn=x* (n→∞)
那么,我们可以反复利用xn+1=φ(xn),经过N次迭代后,用xN作为x*的近似值。
0.4 学好计算方法的几个的层次计算方法内容广泛,方法众多,即使同一个问题也可以有多种方法,要学好计算方法这门课,我们需要从几个不同的层面上来理解计算方法,从而理顺我们的思路。
1.把计算方法理解为一门学科计算方法作为一门学科,要解决的基本问题还是如何把复杂的科技数值计算问题有效地转化为只有一定数位的数的四则运算问题。
计算方法的内容是大学数学教科书中的遗留问题。但我们决不能把计算方法简单地理解为一门数学课。在电子计算机问世以前可以说是的,现在不能。
学习计算方法的目的是为了用数学方法解决实际问题,侧重点是求模型的数值解。我们可以通过对一些些典型的数学问题的研究形成一般性的方法体系,这样可以保事半功倍的效果。
2.把计算方法理解为数学方法的伸延我们现在毕竟是"学习"计算方法,期望值暂不要求太高,能顺利通过各种考试也行。既然我们的计算方法是结合大学数学教科书中的典型问题求数值解展开的,那么数学中相应的概念、定理、法则、公式对于我们求数值解肯定是有帮助的。
当我们研究典型的数学问题的数值解方法时,比如求数值积分和数值微分、求微分方程的数值解,我们完全可以把它们看作是数学教科书中的遗留问题。把它们留在这里集中解决,可以收到事半功倍的效果。
3.把计算方法理解为求解数学问题的计算机方法对于一个典型问题来说,无论用什么工具求数值解都需要算法。算法是为了解决特定问题或完成特定的任务而设计的一系列操作步骤。算法可以用自然语言来描述,也可以用流程图来描述。
在计算机非常普及的今天,对一些典型的数学问题求数值解得到的计算方法实际也就是计算机方法,也就是能够由计算机来执行的算法。
4,算法举例·多项式求值的秦九韶算法设有多项式 pn(x)=a0+a1x+…+anxn
它可以表为 pn(x)=(…((an)*x+an-1)*x+…a1)*x+a0
如果我们用一个共同的中间变量来表示每一层括号内的结果,即可形成一个算法。 算法说明如下:
1输入 n,a[0],a[1],…,a[n],x0
2设置 k=n,s=a[n]
3 for( k=n;k>0;k-- ){s*=x; s+=a[k-1];}
3输出 s
注意:这个算法特别适合用计算器来计算。
4,小结不管是过去还是今天,计算方法研究的基本问题没有发生是值的改变。但是过去的计算方法是面向手工和原始计算工具的,而今天的计算方法应当是面向是电子数字计算机的。
计算方法是连接工程数学、实际问题求解、计算机程序设计的中间环节。学会了利用计算机求解工程数学中的一些典型问题后,我们不难进一步利用计算机求解实际问题!
0.5关于算法的评价(简单介绍)
既然研究典型的数学问题的计算方法、或者说数值解方法最后都要用"算法"来描述,所以对具体的计算方法的评价也就转化为对算法的评价。一个算法的好或不太理想可用数值稳定性,计算量,存贮量这几个指标来刻画,近年来又增加了一条就是程序的可读性好。
1数值稳定性当我们用计算机进行数值计算时,计算机的输入和输出都是数值,而且在大多数情况下都是近似值。当输入的数据的误差被限制在某个允许范围内时,我们自然希望结果的误差也被限制在某个范围之内,至少我们不希望看到在计算过程中由于出现数字溢出而停机。
一个好的算法应当具有数值稳定性,也就是说,最后输出的结果是有效的。
2.节省计算时间我们有两种方式来评估计算时间,如果是有限步完成的计算问题,我们可以估算计算量;对于一个迭代过程来说,我们用收敛速率来描述计算时间。
(1)计算量的定义我们把作一次浮点数的乘法运算连同一次加法运算的计算量作为计算量的计量单位。
例如:假设A=(ai j)l×m,B=(bi j)m×n分别为 l×m 和m×n矩阵,记C=A·B,则C为l×n矩阵,由于
ci j=ai 1·b1 j+ ai 2·b2 j +...+ai m·bm j
所以求ci j的计算量为m,所以求C的计算量就是m·n·l,我们习惯上把它记为O(m·n·l),其含义是大体上与m·n·l成正比。
(2)收敛速率的定义:
在一个迭代过程中,如果我们有
其中c为常数,则称{xn}p阶收敛于x*,当p=1时,称算法具有线性速率收敛;当1<p<2时,称算法具有超线性收敛速率;当p=2时,称算法具有二次终结性质或二次收敛速率。
3.节省存贮空间节省存贮空间有两层含义:
第一层含义是指算法简单,因而程序就短,程序本身所占用的存贮空间便少;
第二层含义是指所需要保留的中间结果比较少,这样就可以省下为了保留中间结果所需要的额外的存贮空间。
这个问题的重要性现在已经大大降低了。
4.程序的可读性好在计算机发展的早期,人们使用计算机要支付高昂的机时费,所以程序员为了节省机时,往往会采用一些编程技巧,这样一来便增加了阅读程序的困难,也不便于软件的维护。现在由于技术的进步,计算机的机时费用已大大降低;另一方面,开发软件的费用又在大幅度上升,所以我们不鼓励为了过分节省计算机时间而牺牲程序的可读性。