大连理工大学矩阵与数值分析第1章 计算方法ppt课件.ppt

《大连理工大学矩阵与数值分析第1章 计算方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《大连理工大学矩阵与数值分析第1章 计算方法ppt课件.ppt（113页珍藏版）》请在三一办公上搜索。

1、大连理工大学研究生教育大楼,矩阵与数值分析,大连理工大学工科硕士研究生数学公共基础课程,授课教师基本信息,姓 名：孟兆良工作单位：数学科学学院办公地点：创新园大厦（大黑楼）A1035室联系电话：84708351-8035(o)EMAIL: ,创业园大厦,主 讲 教 材,课程的总成绩,考 核 要 求,期末考试,平时作业,数值实验,占20%；,占10%；,占70%；,知识，只有当它靠积极的思考得来而不是凭记忆得来的时候，才是真正的知识。,第1章 绪 论,1.1 计算机科学计算研究对象与特点,1.2 误差分析与数值方法的稳定性,1.3 向量与矩阵的范数,科学计算、理论计算和实验并列为三大科学方法。

2、我们所学习的内容属于一门新学科科学计算。 即现代意义下的计算数学。 主要研究在计算机上可计算的有效算法及其相关理论。,本课程主要研究现代、行之有效数值方法,1.1 计算机科学计算研究对象与特点,主要内容包括：,微分方程数值解法,本课程主要研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现,数值代数,数值逼近,（数值微分积分）,矩阵分析简介,三、有好的计算复杂性，既要时间复杂性好，是指节省时间，又要空间复杂性好，是指节省存储量，这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。,课程的特点：,一、构造计算机可行的有效算法,二、给出可靠的理论分析，即对任意逼近并达到精度要求，保

3、证数值算法的收敛性和数值稳定性，并可进行误差分析。,四、数值实验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验证明是行之有效的。,考察，线性方程组的解法,早在18世纪Cramer已给出了求解法则： Cramers Ruler,什么是有效算法？,（D0）,Cramers Ruler,这一结果理论上是非常漂亮的，它把线性方程组的求解问题,归结果为计算n+1个n阶行列式问题。,对于行列式的计算，理论上又有著名的Laplace展开定理。,这样理论上我们就有了一种非常漂亮的求解线性方程组的方法。,然而我们做一简单的计算就会发现,由于这一方法的运算量,大得惊人，以至于完全不能用于实际计算。

4、,其中Aij表示元素aij的代数余子式。,设计算k阶行列式所需要的乘法运算的次数为mk，则容易推出,于是，我们有,这样，利用Cramer法和Laplace展开定理来求解一个n阶线性方程组，所需的乘法运算次数就大于,在算法中运用行列展开计算，则总的的乘法运算次数将达：,若使用每秒百亿次的串行计算机计算, 一年可进行的运算应为：,26！=4.03291026（次）,13(亿年),365(天) 24(小时) 3600(秒) 1010 3.1536 1017 （次）,以求解25阶线性方程组为例，如果用Cramer法则求解，,共需要耗费时间为：,（n+1）n!=(n+1)!,它远远超出目前所了解的人类文

5、明历史！,这就是研究数值方法的必要性。,随着科学技术的发展，出现的数学问题也越来越多样化，有些问题用消去法求解达不到精度，甚至算不出结果，从而促使人们对消去法进行改进，又出现了主元消去法，大大提高了消去法的计算精度。,而著名的 Gauss消元法，它的计算过程已作根本改进，,成为有效算法，使得可在不到一秒钟之内即可完成上述计算,Cramer 算法是“实际计算不了”的。,任务。,1.2 误差分析与数值方法的稳定性,1.2.1 误差来源与分类,1.2.2 误差的基本概念和有效数字,1.2.3 函数计算的误差估计,1.2.4 数值方法的稳定性和避免误差危害的基本原则,1.2.1 误差来源与分类,用计算

6、机解决科学计算问题时经常采用的处理方式是将连续的问题离散化、用有限代替无限等，并且用数值分析所处理的一些数据，不论是原始数据，还是最终结果，绝大多数都是近似的，因此在此过程中，误差无处不在。,误差的来源主要从以下几个方面：,实际问题,数学模型,计算机数值结果,编程实现算法,数值计算方法,计算机科学计算的流程图,模型误差,方法误差或称为截断误差,观测误差,舍入误差,型的解之间的误差,生的误差，如用有限代替无限的过程所产生的误差,1模型误差,2. 截断误差,由实际问题抽象出数学模型，要简化许多,条件，这就不可避免地要产生误差实际问题的解与数学模,从数学问题转化为数值问题的算法时所产,截断误差通常是

7、指用一个基本表达式替换一个相当复杂的算术表达式时所引起的误差。这一术语从用截断Taylor级数替换一个复杂的算术表达式的技术中衍生而来。,例如，,求,的值的运算，,我们可用无穷级数：,截断误差,则数值方法的误差是,给定,=,计算过程中也可能产生误差,测手段的限制，得到的数据必然有误差,3. 观测误差,4. 舍入误差,例如，,就是舍入误差。,初始数据大多数是由观测而得到的。由于观,以计算机为工具进行数值运算时，由于计算,机的字长有限，原始数据在计算机上的表示往往会有误差，在,模型和观测两种误差不在本课程的讨论范围,这里主要讨论算法的截断误差与舍入误差，而截,分析初始数据的误差通常也归结为舍入误差

8、,研究计算结果的误差是否满足精度要求就是：,断误差将结合具体算法讨论,误差估计问题,1.2.2 误差的基本概念和有效数字,设x为精确值，,因此误差 x-a 也未知。,称,通常准确值 x 是未知的，,a为x的一个近似值，,绝对误差界,误差 x-a 可正可负。,绝对误差（误差）,则 叫做近似值a的误差界（限）。,它总是正数。,定义,定义,ea 使得,（1-1）,设x为精确值，,若有常数,a为x的一个近似值，,例如，用毫米刻度的米尺测量一长度x，读出和该长度接近的刻度a，a是x的近似值，它的误差界是0.5mm，,于是有,如若读出的长度为765mm ，则有，,虽然从这个不等式不能知道准确的x是多少，但

9、可知,绝对误差界,结果说明x在区间764.5，765.5内。,对于一般情形 ，,即可以表示为,也可以表示为,但要注意的是，误差的大小并不能完全表示近似值的好坏。,实际计算中，,如果真值 未知时，,若 ，,称为近似值a 的相对误差。,作为a的相对误差，,条件是 较小。,通常取,相对误差（误差）,则将近似值的误差与准确值的比值,定义,相对误差也可正可负。,是 的平方项级，故可忽略不计。,这是由于两者之差,下面我们看看相对误差的作用,有两个量 x=3.000， a=3.100，,绝对误差,相对误差,绝对误差,相对误差,则其绝对误差：,例,其相对误差为：,则其绝对误差：,其相对误差为：,又有两个量,相

10、对误差的绝对值上界叫做相对误差界（限），,记为：,相对误差界（限）,其近似值 ,求a,已知,，因此其绝对误差界为：,相对误差界为：,不是唯一的。,的绝对误差界和相对误差界。,解：,0.0003,0.0002。,此例计算中不难发现，,绝对误差界和相对误差界并,例1,我们要注意它们的作用。,当准确值x位数比较多时，人们常常按四舍五入的原则得到x的前几位近似值a，,那么，它们的误差界的取法应为：,例如,误差界的取法,取3位：,取5位：,（1-2）,一个数字，,（1-3）,则称a为x的具有n位有效数字的近似值。,定义1.3,设 x 为精确值，,a为x 的一个近似值，表示为：,可以是有限或无限小数形式，

11、,其中 ai(i=1,2,n)是0到9中的,如果其绝对误差界,n为正整数，,k为整数，,在例1中，,而,的具有4位有效字的近似值。,因其绝对误差界为,故a1也只是e 的具有4位有效数字的近似值。,再取,即a 是,那么，可知,由于a的绝对误差界为,作为,也具有4位有效数字。,同样我们可以分析出,这是因为：,那么，有,这表明：有效数字位数与小数点的位置无关,的近似值，,下列近似值的绝对误差限均为0.005，问它们,解：首先将它们表示成标准形式,则由已知条件，,各有几位有效数字？,例 2,即a有5位有效数字；,即b有1位有效数字；,同理，由,由,即c无有效数字。,一般来说，绝对误差与小数位数有关，相

12、对误差与有效数字位数有关,其表达形式如,（1-4）,（2）如果其相对误差界满足,（1-5）,（1）如果a有位n有效数字，则其相对误差界满足,则a至少具有n位有效数字。,设实数x为某个精确值，a为它的一个近似值，,定理 1.1,由（1-2）可得到,（1-6）,结论（1）成立。,证,所以如果a有n位有效数字，那么,再由（1-5）和（1-6）,由定义1.3知，a具有n位有效数字。,近似值为a，,f(a)作为f(x)的近似，其误差应如何估计？,1.2.3 函数计算的误差估计,下面我们用Taylor展开的方法来估计其误差。,即有,设一元函数f(x)具有二阶连续导数，,进一步，有,取绝对值，由三角不等式，

13、得,注意不等式,相比不太大，,其中在x与a之间。,近似绝对误差估计式：,的二次项，,就得到f(a)的一个,则可忽略,如果,近似相对误差界为：,与,的值,的近似值分别为,则,（1-7）,其中,所以可以估计到函数值的误差界，,（1-8）,为n元函数，,如果,现将估计式（1-8）应用到数的四则运算的误差估计中，,即 n=2，分别取,自变量,这时有,从而得到四则运算的估计式：,(1-9),(1-10),(1-11),练习,已知,均为有效数字，,求 的相对误差界。,解：取,根据（1-8）式，得,由已知，,从而,这时由（1-24）可知，计算的相对误差会很大,（1-9）,当 时，,则,会导致计算值的有效数字

14、的损失。,在计算中应尽量避免出现两个相近的数相减,两个数相减的相对误差,结论,进而,必有,例,各自的相对误差为：,和,而,差的相对误差界扩大了,否则，出现与数值稳定相反的情况，,1.2.4 数值方法的稳定性和避免误差危害的基本原则,1.数值方法的稳定性,用某一种数值方法求一个问题的数值解，,如果在方法的计算,过程中舍入误差在一定条件下能够得到控制（或者说舍入误差,的增长不影响产生可靠的结果），,则称该方法是数值稳定的；,则称之为数值不稳定的。,蝴蝶效应 亚洲蝴蝶拍拍翅膀，将使风和日丽的美洲 几个月后出现狂风暴雨?！,Asia,America,什么是蝴蝶效应？ 美国麻省理工学院气象学家洛伦兹(L

15、orenz)为了预报天气，他用计算机求解仿真地球大气的13个方程式。为了更细致地考察结果，他把一个中间解取出，提高精度再送回。而当他喝了杯咖啡以后回来再看时竟大吃一惊：本来很小的差异，结果却偏离了十万八千里！计算机没有毛病，于是，洛伦兹（Lorenz）认定，他发现了新的现象：“对初始值的极端不稳定性”，即：“混沌 ”，又称“蝴蝶效应”,由于,则递归算法如下：,1.,2.,计算积分,例6,解：,计算出,由,计算出,由,What happened?!,! !,? !,?,?,，然后按方法1计算,的近似值,，如果最初计算时误差为：,递推过程的舍入误差不记，并记,，则有,，那么计算,时产生的舍入误差,

16、放大了 倍，因此，该方法是数值不稳定的。,按方法2计算时，,记初始误差为,，则有,生的舍入误差为,由此可知，使用公式2计算时不会放大舍入误差。,该方法是数值稳定的。,因此，,为了用数值方法求得数值问题满意的近似解，,2、避免误差危害的基本原则,(I)避免有效数字的损失,（3）避免小数做除数或大数做乘数。,在四则运算中为避免有效数值的损失，应注意以下事项：,（1）在做加法运算时，应防止“大数吃小数”；,（2）避免两个相近数相减；,中应注意下面两个基本原则。,在数值运算,在五位十进制的计算机上计算,解 计算机作加减法时，先将所相加数阶码对齐，根据,。这种现象被称为“大数吃小数”。,后一种方法的结果

17、是正确的，前一种方法的舍入误差影响太大。,例5,字长舍入，再加减。,规范化和阶码对齐后的数表示为:,1000个,，那么上式用,如果用63015依次加各个,如果改变运算,如果,，则,，用上述公式计算时,总之，两者其中之一必将会损失有效数字。,一元二次方程,例7,有两个根，其求根公式为,如果,，则有,如果,，则有,解一般二次方程 ax2+2bx+c=0,(a,b,c均不为零)，,其中,是b 的符号函数。,应取,如果,，则,，用上述公式计算时,如果,，则有,如果,，则有,如果改用公式:,计算得x2 0.062746，具有三位有效数字。,而 x2的精确值是 0.062746。,其原因为在计算x2时发生

18、了两个相近数相减，造成有效数字损失。,求方程 x2-16x+1=0 的根,若取三位有效数字计算，有,由习惯的公式：,，有三位有效数字。,，只有一位有效数字。,例,而,又例如, 在八位十进制计算机上，计算,为9位尾数左移变成机器零，,3.712 与,在计算机上做和时，,大数做乘数时，容易产生大的舍入误差，应尽量避免。,3.712由于阶码升,这便说明用小数做除数或用,就是所求的值。,如果直接逐项求和计算，需要大约 次乘法运算 即,例如，多项式求值运算，设,若取,，,(II)减少运算次数,次,n次,则有递推公式：,总的计算量需进行 次乘法。,若将公式变成如下递推公式，即令,若令,则有递推公式：,总的

19、计算量为n次乘法。,就是所求的的值。,39,10,5,0,1,-3,1,-1,令X=2,2,78,10,2,20,2,42,21,2,2,79,158,157,以上计算过程称之为 秦九韶算法,要计算十万项的和，计算量很大，另一方面舍入误差的积累也十分严重。,若要精确到10-5,取,只须计算前9项的和，截断误差便小于,如果改用级数,1.3 向量与矩阵范数,1.3.1 向量范数,1.3.2 范数的等价性,1.3.3 矩阵范数,1.3.4 矩阵范数的性质,供了实数变量或复数变量大小的度量。,即在 f(x)=x(绝对值或模)意义下，,（2）齐次性 ax=ax,（3）三角不等式 x+yx+y,注意到实函

20、数 f(x)=x满足以下三个条件：,（1）非负性 x0当且仅当x=0 时,x=0,我们在讨论实数、复数的大小、误差时，,把任何,一个实数变量或复数变量与一个非负实函数联系起来,这个实函数提,二、研究矩阵和向量的序列以及级数的收敛准则,范数的主要的应用：,一、研究这些矩阵和向量的误差估计,把任何一个向量或矩阵与一个非负实数联系起来，,在某种意义下，这个实数提供了向量和矩阵的大小的,度量。,取不同的向量或矩阵，就对应有一类向量或矩阵,矩阵大小的一种度量，称之为范数。,变量的实值函数，,其中每一个函数都可以看作向量或,1.3.1 向量范数,（1）非负性,（2）齐次性,（3）三角不等式,即对任意向量x

21、和y以及任意复常数,若该函数满足以下三个条件：,函数，记为 f(x)=x，,定义1.4,定义Cn在(n维复向量空间）上的一个非负实值,向量范数的概念是复数模的概念的自然推广，其定义如下：,x0当且仅当x=0n1时x=0,常用的向量范数有：,(1-18),( xH 为向量x的共轭转置）,上述四种范数分别称为,2,范数和p-范数。,xi表示xi的模。,(1-17),(1-19),(1-20),前面三种范数都为p-范数，当，2，时的范数。,注意，当时 ，,两边开p次方得,由于,故,容易验证以上三种范数均满足范数定义中的三个条件。,下面我们分析向量的，2和-范数的几何意义，,为此，不妨设,和 。,事实

22、上，,加权的范数：,是它的每一个分量的权系数。,其中W 为对角矩阵，,加权的1-范数为：,例如,对任,加权的2-范数为：,可定义出,其对角元素,例 对任给,试问如下实值函数是否构成,向量范数？,故，1.和2.不满足非负性条件。,3.不满足齐次性条件；,4. 满足加权向量范数的定义，故构成向量范数。,2.中取,1.中取,？,？,？,？,答：,解：,2）,3）,以3）为例证明之，事实上，,又,，故3）得证。,1）,但是在各种向量范数之间存在下述重要的关系。,1.3.2 向量范数的等价性,范数的定义可以验证：,根据向量,（向量范数的等价性定理）,上的任意两种向量范数，则存在两个与向量无关的正常数,c

23、10和c20，使得下面的不等式成立,（1-6）,并称 和 为 上的等价范数。,定理1.2,更一般地有，,利用定理1.1可证如下的重要的结果,（向量序列收敛性定理）,其中,定理,则,设,1.3.3 矩阵范数,若我们取,第i行,第j列,则Eij线性无关，而且任意一个mn 矩阵 A=(aij)都可表为：,这也就是说，全体mn 矩阵构成的空间的维数是mn。,Rmn亦可看作一个mn维的向量空间。,因此，,这样，我们自然想到将,向量范数的概念直接推广到矩阵上。,然而这种推广应考虑到,矩阵的乘法运算。,因而使用的矩阵范数的定义是按如下方式。,（2）齐次性,（3）三角不等式,即对任意矩阵A、B以及任意复常数,

24、，若该函数满足以下条件：,A0 当且仅当A=0mn时A=0,（4）相容性,定义1.5,定义在Cmn上的一个非负实值函数，记为,（1）非负性,（1-23）,(1-24),显然上述两个函数均满足矩阵范数定义中的（1）（3）,我们分别称由（1-23）和（1-24）所定义的范数为矩阵的,-范数和Frobenius范数（简称F-范数）。,性质：,下面证明(1-23)满足相容条件，,证： 由定义,其中,下面证明(1-24)满足相容条件，,证：记,例 设,，问是否构成A的,一种范数？,则可得出,，,，从而有,，故不构成A的一种范数。,若定义实值函数：,，则可验证其构成,A的一种范数。,解：取,那么，,（矩阵

25、范数的等价性定理）,上的任意两种矩阵范数，,C10和C20，使得下面的不等式成立,并称 和 为 上的等价范数。,定理,矩阵范数具有向量范数的一切性质,（矩阵序列收敛性定理）,其中,定理,则存在两个与矩阵无关的正常数,对于一种矩阵范数M 和一种向量范数V,如果对任意mn矩阵A和任意n维向量x, 满足,则称矩阵范数M 与向量范数V 是相容的。,定义1.6,矩阵m1范数与向量的p-范数是相容的，即,而矩阵的F-范数与向量的2-范数是相容的，即,作矩阵的特殊情形，那么由矩阵范数的相容性，我们便得到了,希望矩阵范数与向量范数之间最好有某种协调性。,矩阵与向量的乘积在矩阵计算中经常出现，所以我们自然,若将

26、向量看,这种协调性，即矩阵范数与向量范数的相容性。,矩阵 -范数与向量的 范数是相容的，,即,则，,矩阵 -范数与向量的 范数是相容的，,即,则,C-S不等式,证法二,其特征值全部为实数且非负，,则,可以证明任意一种矩阵范数必然存在与之相容的向量范数,2算子范数,定理1.3,证,其中,定理1.4,已知 和 上的同类向量范数 ,(1-25),则 是一种矩阵范数,且与已知的向量范数相容,若定义,其次注意到，,由(1-25)立刻可得到,即,即相容性成立。,故对每一个矩阵A而言，都能够找到向量 ，,使得,而且,其中,证,上的连续函数，,而当A0时，,存在x0Cn，,使Ax00，从而,（）齐次性，,（1

27、）非负性，当A=0 时，,（3）三角不等式，,假设A和B分别为mn阶矩阵，则,（4）相容性，AB=0 时显然。,，因此,相容的矩阵范数。,A和B分别为ml和ln阶矩阵，令,且又假设,（列和范数）,（行和范数）,（1）,（2）,（3）,（谱范数）,定理1.5,几种常用的算子范数,在向量范数中，最常用的范数为向量的1-范数、2-范数和,-范数，下面分别给出从属这三种向量范数的矩阵范数。,其中 max(AHA)表示矩阵AHA的最大特征值；,在此只给出（1）的证明。,，则,因此，有,证,设,则可取,如果存在某个 使得,第个分量,那么，即有,推论,事实上，,特别地，,不是算子范数。,事实上，,设,求,例

28、2,解：,令,得，,可以证明： 1.任意给定的矩阵范数必然存在与之相容的向量范数；任意给定的向量范数必然存在与之相容的矩阵范数（如从属范数）。 2. 一个矩阵范数可以与多种向量范数相容（矩阵的m1-范数与向量的p-范数相容）；多种矩阵范数可以与一个向量范数相容（矩阵的F-范数、2-范数与向量的2-范数相容）。 3. 从属范数一定与所定义的向量范数相容，但是矩阵范数与向量范数相容却未必有从属关系。（矩阵的F-范数与向量的2-相容，但无从属关系）。 4. 并非任意的矩阵范数与任意的向量范数相容。,故矩阵的 与向量的 不相容。,取,则有,矩阵范数与向量范数不相容的例子：,而,对任给,向量的內积的定义

29、为：,那么，,特别地，,对于酉矩阵 ，我们可有如下的结论：,事实上，,（酉矩阵的范数不变性）,注意，这里取,是一一对应关系。,1.3.3 矩阵范数的性质,设M为矩阵Cnn空间的任一矩阵范数，,任意的n阶方阵A均有,定理1.6,证,从而,故得到,设,则对,（1-26）,其中 (A)为方阵A的谱半径。,则存在向量x0，满足Ax= x，,特别地，当A时对称矩阵时，有,由矩阵2-范数的定义，得,问实值函数 可不可以作为的一种范数？,取,，则有,，而,；从而,，即有,故不可以作为的一种范数。,对于任给的 0, 则存在Cnn上的一种算子范数,定理1.7,（依赖矩阵A 和常数 ），使得,（1-27）,注：定

30、理1.7中的矩阵范数M 与给定的矩阵A有关。,针对矩阵A构造的矩阵范数M , 对于另一个矩阵B ,不等式,不一定成立。,？,Cnn上的一种矩阵范数,如果ACnn,定理1.8,证,则 IA可逆，且,且,(1),(2),若IA奇异,则,是A的一个特征值。,从而必有 。,这与,矛盾，,即 ，,故IA是可逆的,由 ，,两端右乘 ，可得,两端左乘A,整理可得,两端取范数,即,注 当A=I时便得到(1)的结论；,当矩阵范数为算子范数时，,秦九韶是一位既重视理论又重视实践，既善于继承又勇于创新的数学家他所提出的大衍求一术和正负开方术及其名著数书九章，是中国数学史上光彩夺目的一页，对后世数学发展产生了广泛的影

31、响美国著名科学史家G萨顿(Sarton，18841956)说过，秦九韶是“他那个民族，他那个时代，并且确实也是所有时代最伟大的数学家之一” 秦九韶的数学成就及对世界数学的贡献主要表现在以下方面： 1、秦九韶的数书九章是一部划时代的巨著 2、秦九韶的“大衍求一术”，领先高斯554年，被康托尔称为“最幸运的天才” 3、秦九韶的任意次方程的数值解领先英国人霍纳（WGHorner，17861837年）572年,秦九韶（公元12021261），字道古，安岳人。,湖北、安徽、江苏、浙江等地做官，1261年左右被贬至梅州,学家秦九韶与李冶、杨辉、朱世杰并称宋元数学四大家。,秦九韶聪敏勤学。宋绍定四年（123

32、1），秦九韶考中进士，,先后担任县尉、通判、参议官、州守、同农、寺丞等职。,后在,（今广东梅县），不久死于任所。,南宋大数,克萊姆（Gabriel Cramer） 生于： 公元1704年 瑞士 日内瓦 卒于： 公元1752年 法国 巴尼奥勒 十八世纪瑞士数学家，精于数学和几何学。早年 在日内瓦读书，1724年起在日内瓦加尔文学院任教， 1734年成为几何学教授，1750 年任哲学教授。 他一生未婚，专心治学，平易近人且德高望重， 先后当选为伦敦皇家学会、柏林研究院和法国、意大 利等学会的成员。 主要著作是1750年出版代数曲线的分析引论， 定义了正则、非正则、超越曲线和无理曲线等概念，第一次正式引入坐标系的纵轴（y轴）。为了确定经过5个点的一般二次曲线的系数，应用了著名的“克莱姆法则”（Cramers Rule），即由线性方程组的系数确定方程组解的表达式。该法则于1729年由英国数学家马克劳林（Maclaurin）得到，1748年发表，但克莱姆的优越符号使之流传。,max,j,i,max,