大连理工大学-矩阵与数值分析绪论ppt课件.ppt

计 算 机 科 学 计 算 （第（第 一一 版）版） 施吉林施吉林 张宏伟张宏伟 金光日金光日 编编 高等教育出版社高等教育出版社 本课件在张宏伟老师提供课件基础上略加改动而成，谨此致谢！第第1 1章章 绪绪 论论1.11.1 计算机科学计算研究对象与特点计算机科学计算研究对象与特点科学计算（计算方法、计算数学、数值分析）：科学计算（计算方法、计算数学、数值分析）：计算机上计算机上求解数学问题的求解数学问题的离散近似算法离散近似算法  主要内容包括：主要内容包括：微分方程数值解法微分方程数值解法 本课程研究用计算机求解各种数学问题本课程研究用计算机求解各种数学问题的数值计算方法、理论与软件实现的数值计算方法、理论与软件实现数值代数数值代数数值逼近数值逼近（数值微分积分）（数值微分积分） 课程特点课程特点： 一、构造计算机可行的一、构造计算机可行的有效算法：计算量与存储量有效算法：计算量与存储量。

二、给出实用的理论分析结果，如算法二、给出实用的理论分析结果，如算法收敛性收敛性和和稳定性稳定性 考察线性方程组考察线性方程组早在早在1818世纪世纪GramerGramer已给出了求解法则已给出了求解法则：： 什么是有效算法？什么是有效算法？…，（D≠0），GramerGramer’s s RulerRuler 从理论上讲从理论上讲 GramerGramer法则是一个求线性方程组的数值方法，法则是一个求线性方程组的数值方法，且对阶数不高的方程组行之有效但是在计算机上，它是否实且对阶数不高的方程组行之有效但是在计算机上，它是否实际可行？际可行？在算法中的乘、除运算次数将达在算法中的乘、除运算次数将达使用每秒一亿次的串行计算机计算使用每秒一亿次的串行计算机计算, , 一年可进行的运算应为：一年可进行的运算应为：2121！！=9.7×10=9.7×102020次次(9.7×1020) (3.5) (3.097 × 1015 ) 30(万年万年)365(天天) × 24(小时小时) × 3600(秒秒) × 109 3.5 × 1015（次）（次） »以求解以求解20阶线性方程组为例，如果用阶线性方程组为例，如果用Gramer法则求解，法则求解，共需要耗费时间为：共需要耗费时间为：1.2 1.2 误差分析与数值方法的稳定性误差分析与数值方法的稳定性 1.2.1 1.2.1 误差来源与分类误差来源与分类 误差的主要来源：误差的主要来源： 实际问题实际问题数学模型数学模型计算机数值结果计算机数值结果数值计算方法数值计算方法计计算算流流程程与与误误差差来来源源模型误差观测误差截断误差舍入误差1．模型误差：模型误差：实际问题的解与数学模型的解之间的误实际问题的解与数学模型的解之间的误 差，来源于数学模型对实际问题的的简化。

差，来源于数学模型对实际问题的的简化2.2. 观测误差：观测误差：初始数据大多数是由观测而得到的由于观初始数据大多数是由观测而得到的由于观测手段的限制，得到的数据常有误差测手段的限制，得到的数据常有误差 截断误差这一术语来源：截断误差这一术语来源： 截断截断TaylorTaylor级数，用级数，用TaylorTaylor级数的有限项近似替代级数的有限项近似替代 TaylorTaylor级数的无穷和级数的无穷和3. 3. 截断误差：截断误差：数学模型与数值计算模型的误差，数学模型与数值计算模型的误差， 如有限代替无限、离散代替连续的误差如有限代替无限、离散代替连续的误差 例如，例如，求求的值 利用无穷级数：利用无穷级数：前前项和项和截断误差则数值方法的误差是则数值方法的误差是，，近似代替函数近似代替函数给定给定=4. 舍入误差舍入误差例如，例如，产生的误差产生的误差就是就是舍入误差舍入误差 用用 近似代替近似代替 ，，由于计算机字长有限而造成的计算过程中由于计算机字长有限而造成的计算过程中误差。

误差 模型和观测两种误差不在本课程的讨论范围模型和观测两种误差不在本课程的讨论范围 这里主要讨论这里主要讨论截断误差截断误差与与舍入误差舍入误差，而截断，而截断误差将结合具体算法讨论误差将结合具体算法讨论. . 初始数据误差也常常归结为初始数据误差也常常归结为舍入误差舍入误差. . 下面讨论下面讨论误差估计误差估计几个基本问题几个基本问题 1.1.1.1.误差的基本概念误差的基本概念误差的基本概念误差的基本概念 设设 为精确值，为精确值，因此误差因此误差 也未知称称 通常准确值通常准确值 是未知的，是未知的，为近似值的为近似值的绝对误差，绝对误差， 简称简称误差误差为为 的一个近似值的一个近似值，绝对误差界（限）误差误差 可正可负可正可负绝对误差（误差） 则则 叫做近似值的叫做近似值的误差界（限）误差界（限）它总是正数它总是正数定义定义1.41.4定义定义1.51.5 设设 为精确值，为精确值， 为为 的一个近似值的一个近似值，若有常数若有常数使得使得（（1-131-13）） 例如，用毫米刻度的米尺测量一长度 ，读出和该长度接近的刻度 ，是 的近似值， 它的误差限是 ，于是 如读出的长度为 ， 则有 . 虽然从这个不等式不能知道准确的 是多少，但可知绝对误差界（限）结果说明 在区间 内. 对于一般情形 ，即也可以表示为 但要注意的是，误差的大小并不能完全表示近似值的好坏.  实际计算中，实际计算中， 如果真值如果真值 未知时，未知时， 若若 ，称为近似值称为近似值 的的相对误差相对误差。

作为作为 的相对误差，的相对误差，条件是条件是 较小通常取通常取相对误差（误差）则将近似值的误差与准确值的比值则将近似值的误差与准确值的比值定义定义 相对误差也可正可负，其绝对值上界叫做相对误差也可正可负，其绝对值上界叫做相对误差界（限）相对误差界（限） 是是 的平方项级，故可忽略不计的平方项级，故可忽略不计记为：记为：相对误差界（限）这是由于 例，有两个量例，有两个量 ， 则则 又例如，有两个量又例如，有两个量 绝对误差相对误差绝对误差相对误差则= -0.1 上例中，绝对误差有较大变化，而上例中，绝对误差有较大变化，而相对误差相同相对误差由于考虑到准相对误差相同相对误差由于考虑到准确值本身的大小常常更有意义确值本身的大小常常更有意义 其近似值 ,求 已知，因此其绝对误差界为：相对误差界为：的绝对误差界和相对误差界解：0.00030.0002注意：绝对误差界和相对误差界并非唯一例例1 1 当准确值 位数比较多时，常常按四舍五入的原则得到 的前几位近似值 ， 取3位 取5位 它们的误差界可以取为：例如误差界的确定误差界的确定（1-14）的一个数字，的一个数字， 为整数，为整数，（1-15）则称则称 为为 的具有的具有 位位有效数字有效数字的近似值。

的近似值定义定义1.61.6 设设 为精确值，为精确值， 为为 的一个近似值的一个近似值，表为表为可以是有限或无限小数形式，可以是有限或无限小数形式， 其中其中 是是0 0到到9 9中中为使下式成立的最大正为使下式成立的最大正整数，整数，  其中其中非零，非零，是四舍五入得到的，则是四舍五入得到的，则     如果一个近似值是由精确值经四舍五入如果一个近似值是由精确值经四舍五入得到的，那么，从这个近似值的末尾数（可得到的，那么，从这个近似值的末尾数（可以是零）向前数起直到再无非零数字止，所以是零）向前数起直到再无非零数字止，所数到的数字均为有效数字数到的数字均为有效数字有效数字位数与小数点的位置无关有效数字位数与小数点的位置无关 一般来说，绝对误差与小数位数有一般来说，绝对误差与小数位数有关，相对误差与有效数字位数有关关，相对误差与有效数字位数有关 下列近似值的绝对误差限均为0.005，问它们各有几位有效数字？解：则由已知条件， 练习1 即有5位有效数字； 有1位有效数字； 即无有效数字。

即减小舍入误差影响的几个原则：减小舍入误差影响的几个原则：1.1.避免两个相近的数做减法避免两个相近的数做减法两个具有两个具有个有效数字的相近数相减后，个有效数字的相近数相减后，常常损失有效数字例如在三位有效数字计算机常常损失有效数字例如在三位有效数字计算机上求解方程上求解方程一个根为一个根为有三位有效数字有三位有效数字而另一个根为而另一个根为只有一位有效数字只有一位有效数字方程方程的的改进求根公式改进求根公式：：当当很小时，用下面近似公式计算很小时，用下面近似公式计算例例 2.2.防止防止“大数吃小数大数吃小数” 计算计算在五位有效数字计算机上，由于加减法要对齐小数点，在五位有效数字计算机上，由于加减法要对齐小数点，导致导致“大数吃小数大数吃小数”因此，应该因此，应该小数相加后，小数相加后，再与大数相加再与大数相加：：3.3.避免小数做除数或大数做乘数避免小数做除数或大数做乘数例如，例如，若若则则绝对误差绝对误差比比增大增大倍当当时，时，有可能有可能溢出溢出！！即为所求次乘法和例如，直接逐项求和计算若令， 则有递推公式（秦九韶算法，霍纳算法）递推公式（秦九韶算法，霍纳算法）：需 次乘法，次加法。

4.4.巧用等价公式巧用等价公式 减少运算次数减少运算次数需要次加法由于则递归算法如下：1.2.计算积分计算积分解：解：算出算出由由计算出计算出由由5.5.选择稳定的算法（稳定性：舍入误差的积累影响不大选择稳定的算法（稳定性：舍入误差的积累影响不大) )  设的近似值为，然后按方法1计算的近似值 如果最初计算时误差为递推过程的舍入误差不记，并记，则有舍入误差 放大了 倍，因此是数值不稳定数值不稳定的按方法2计算时， 记初始误差为，则有 因此公式2是数数值稳定定的1.2 1.2 向量与矩阵的向量与矩阵的范数范数实数或复数的大小由非负实数 度量2）齐次性齐次性 （3）三角不等式三角不等式 注意到注意到 满足以下三个条件：满足以下三个条件：（1）非负性非负性 当且仅当当且仅当 时时 向量和矩阵的向量和矩阵的范数范数：向量和矩阵的：向量和矩阵的“长度长度”或或“大小大小”。

科学计算中离不开矩阵和向量的运算运算过程的科学计算中离不开矩阵和向量的运算运算过程的收敛、稳定、误差等问题都基于收敛、稳定、误差等问题都基于“距离距离”、、“长度长度”、、“大小大小”的概念，都用范数来描述的概念，都用范数来描述1.2.1 1.2.1 向量范向量范数数 （1）非负性非负性 并并且当且仅当 时 （2）齐次性齐次性 （3）三角不等式三角不等式则称函数 为上的一个向量范数．以及任意复（实）常数该函数满足（或 ）上的一个非负，若对任意向量 和 定义在实值函数，记为定义定义1.11.1（或记任意ｎ维向量 ( 为向量 的转置），常用的向量范数有 (1-1) (1-2) ( 为向量 的共轭转置） (1-3) (1-4)表示 的模．上述四种范数分别称为１，2，∞范数和p-范数 前面三种范数为p-范数当ｐ＝１，2，∞时的特例 例如，当 时， 。

事实上，两边开 次方得 由于 故容易验证以上三种范数均满足范数定义中的三个条件容易验证以上三种范数均满足范数定义中的三个条件 下面我们分析一下向量的１，下面我们分析一下向量的１，2 2和和∞∞- -范数的几何意义，范数的几何意义，以以为例给定任意一种向量范数都可以定义一种加权范数加权的加权的1-1-范数为：范数为： 加权的加权的2-2-范数为：范数为：和任意非奇异矩阵和任意非奇异矩阵例如对于和例例 对任给,试问如下实值函数是否构成向量范数？ 答：答：1.1. 不满足非负性条件，3.不满足齐次性条件；4. 满足加权向量范数的定义，故构成向量范数2.不满足非负性条件，例如取例如取都不是向量范数！例：求向量例：求向量的１，2和∞-范数解：解：  （向量范数的等价性定理范数的等价性定理）设）设和为上的任意两种向量范数，则存在两个与向量无关的正常数 c1和c2，使得下面的不等式成立 （1-6） 并称 和 为 上的等价范数等价范数 定理定理1.11.11. 1. 矩矩阵阵范范数数（2）齐次性齐次性 （3）三角不等式三角不等式则称函数 为上的一个矩阵范数。

以及任意复常数对任意矩阵矩阵 和 上的一个非负实值函数，记为，若该函数满足以下条件： 定义在（1）非负性非负性 当且仅当当且仅当 时时 0³A（4）相容性相容性定义定义1.21.2 （1-7） (1-8) 显然上述两个函数均满足矩阵范数定义中的（1）—（4） 我们分别称由（1-7）和（1-8）所定义的范数为矩阵的 - -范数和Frobenius范数（简称F-F-范数范数）．2 2．算子范数．算子范数 (1-9)则 是一种矩阵范数,称为算子范数定理定理1.21.2设设由算子范数定义，有由算子范数定义，有是向量范数定义是向量范数定义定义定义称如下集合为矩阵称如下集合为矩阵 的的谱谱定义矩阵定义矩阵 的的谱半径谱半径为为注：若矩阵为：若矩阵为：则其复共轭矩阵为：则其复共轭矩阵为： 我们称由关系式（1-9）定义的矩阵范数为从属于向量范数的矩阵范数，简称从属范数或算子范数算子范数．在向量范数中，最常用的范数为向量的1-1-范数、范数、2-范数范数和和∞-∞-范数，范数，下面分别导出从属这三种向量范数的矩阵范数． (列范数)(行范数) （1）（2）（3）（谱范数）其中 表示矩阵 的最大特征值； 定理定理1.31.3对任何算子范数，单位矩阵 的范数值为1，即推论推论事实上，特别地， 不是算子范数。

事实上，设求例例2 2解：解： 令 得， 满足1.2.4 1.2.4 矩阵范数的性质矩阵范数的性质为矩阵空间的任一算子范数，均有 设设则对任意的n 阶方阵 　 （1-10） 的谱半径 为方阵 其中定理定理1.1.４４证证，则有从而得到．设一般地，实值函数 可以作为一种矩阵范数吗？注意：当注意：当时，取，则有，从而 ；从而另一方面故实值函数 不可以作为一种范数！对于任给的对于任给的ε>0, 则存在定理定理1.51.5 上的一种算子范数 （依赖矩阵 和常数ε），使得 （1-11）注：注：定理1.５中的矩阵范数与给定的矩阵有关针对矩阵构造的矩阵范数对于另一个矩阵，不等式不一定成立  ， 如果 上的一种算子矩阵范数上的一种算子矩阵范数 且 则可逆且 (1-12)定理定理1.61.6 整理后便可得到(1-12)式证证 由定理由定理1.41.4可得，可得，设设 为矩阵为矩阵 的任意非零特征值的任意非零特征值则矩阵则矩阵 的特征值为：的特征值为：从而可知从而可知即即可逆。

进一步可逆进一步 秦九韶是一位既重视理论又重视实践，既善于继承又勇于创新的数学家．他所秦九韶是一位既重视理论又重视实践，既善于继承又勇于创新的数学家．他所提出的大衍求一术和正负开方术及其名著提出的大衍求一术和正负开方术及其名著《《数书九章数书九章》》，是中国数学史上光彩夺目，是中国数学史上光彩夺目的一页，对后世数学发展产生了广泛的影响．美国著名科学史家的一页，对后世数学发展产生了广泛的影响．美国著名科学史家G G．萨顿．萨顿( (Sarton，，1884－－1956) )说过，秦九韶是说过，秦九韶是“他那个民族，他那个时代，并且确实也是所有时代最他那个民族，他那个时代，并且确实也是所有时代最伟大的数学家之一伟大的数学家之一”．． 秦九韶的数学成就及对世界数学的贡献主要表现在以下方面：秦九韶的数学成就及对世界数学的贡献主要表现在以下方面： 1 1、秦九韶的、秦九韶的《《数书九章数书九章》》是一部划时代的巨著是一部划时代的巨著 2 2、秦九韶的、秦九韶的“大衍求一术大衍求一术”，领先高斯，领先高斯554年，被康托尔称为年，被康托尔称为“最幸运的天才最幸运的天才” 3 3、秦九韶的任意次方程的数值解领先英国人霍纳（、秦九韶的任意次方程的数值解领先英国人霍纳（W·G·Horner，，1786—1837年）年）572572年年 秦九韶秦九韶（公元（公元1202－－1261），字道古，安岳人。

南宋大数），字道古，安岳人南宋大数学家秦九韶与李冶、杨辉、朱世杰并称宋元数学四大家学家秦九韶与李冶、杨辉、朱世杰并称宋元数学四大家 秦九韶聪敏勤学宋绍定四年（秦九韶聪敏勤学宋绍定四年（1231），秦九韶考中进士，），秦九韶考中进士，先后担任县尉、通判、参议官、州守、同农、寺丞等职先先后担任县尉、通判、参议官、州守、同农、寺丞等职先后在湖北、安徽、江苏、浙江等地做官，后在湖北、安徽、江苏、浙江等地做官，1261年左右被贬至梅年左右被贬至梅州（今广东梅县），不久死于任所州（今广东梅县），不久死于任所  克萊姆克萊姆（（Gabriel Gramer）） 生于：生于： 公元公元17041704年年 瑞士瑞士 日内瓦日内瓦 卒于：卒于： 公元公元17521752年年 法国法国 巴尼奥勒巴尼奥勒 十八世纪瑞士数学家，精于数学和几何学。

早年十八世纪瑞士数学家，精于数学和几何学早年 在日内瓦读书，在日内瓦读书，17241724年起在日内瓦加尔文学院任教，年起在日内瓦加尔文学院任教， 17341734年成为几何学教授，年成为几何学教授，1750 1750 年任哲学教授年任哲学教授 他一生未婚，专心治学，平易近人且德高望重，他一生未婚，专心治学，平易近人且德高望重， 先后当选为伦敦皇家学会、柏林研究院和法国、意大先后当选为伦敦皇家学会、柏林研究院和法国、意大 利等学会的成员利等学会的成员 主要著作是主要著作是17501750年出版年出版《《代数曲线的分析引论代数曲线的分析引论》》，， 定义了正则、非正则、超越曲线和无理曲线等概念，第一次定义了正则、非正则、超越曲线和无理曲线等概念，第一次正式引入坐标系的纵轴（正式引入坐标系的纵轴（y y轴）。

轴） 为了确定经过为了确定经过5 5个点的一般二次曲线个点的一般二次曲线的系数，应用了著名的的系数，应用了著名的““克莱姆法则克莱姆法则””（（GramerGramer‘‘s Rules Rule），即由线性方程组的系数），即由线性方程组的系数确定方程组解的表达式该法则于确定方程组解的表达式该法则于17291729年由英国数学家马克劳林（年由英国数学家马克劳林（MaclaurinMaclaurin）得到，）得到，17481748年发表，但克莱姆的优越符号使之流传年发表，但克莱姆的优越符号使之流传。