第一节三角形方程组和三角分解-PPT.pptx

第一节三角形方程组和三角分解 如何利用电子计算机来快速、有效地求解线如何利用电子计算机来快速、有效地求解线性方程组得问题就是数值线性代数研究得核心问性方程组得问题就是数值线性代数研究得核心问题题,而且也就是目前仍在继续研究得重大课题之一。而且也就是目前仍在继续研究得重大课题之一。这就是因为各种各样得科学与工程问题往往最终这就是因为各种各样得科学与工程问题往往最终都要归结为一个线性方程组得求解问题。例如结都要归结为一个线性方程组得求解问题。例如结构分析、网络分析、大地测量、数据分析、最优构分析、网络分析、大地测量、数据分析、最优化及非线性方程组与微分方程组数值解等化及非线性方程组与微分方程组数值解等,都常遇都常遇到线性方程组得求解问题。到线性方程组得求解问题。线性方程组得求解问题就是一个古老得数学线性方程组得求解问题就是一个古老得数学问题。早在中国古代得问题。早在中国古代得九章算术九章算术中中,就已详细就已详细地描述了解线性方程组得消元法。到了地描述了解线性方程组得消元法。到了19世纪初世纪初,西方也有了西方也有了Gauss消去法消去法,然后求解未知数多得大然后求解未知数多得大型线性方程组则就是在型线性方程组则就是在20世纪中叶电子计算机问世纪中叶电子计算机问世后才成为可能。世后才成为可能。上页上页 下页下页 返回返回 结束结束 求解线性方程组得数值方法大体上可分为直求解线性方程组得数值方法大体上可分为直接法与迭代法两大类。接法与迭代法两大类。直接法就是指没有舍入误差得情况下经过有直接法就是指没有舍入误差得情况下经过有限次运算可求得方程组得精确解得方法。因此限次运算可求得方程组得精确解得方法。因此,直接法又称为精确法。直接法又称为精确法。迭代法则就是采取逐次逼近得方法迭代法则就是采取逐次逼近得方法,亦即从亦即从一个初始向量出发一个初始向量出发,按照一定得计算格式按照一定得计算格式,构造构造一个向量得无穷序列一个向量得无穷序列,其极限才就是方程组得精其极限才就是方程组得精确解确解,只经过有限次运算得不到精确解。只经过有限次运算得不到精确解。上页上页 下页下页 返回返回 结束结束 这一章这一章,我们将主要介绍解线性方程组得一类我们将主要介绍解线性方程组得一类最基本得直接法最基本得直接法GaussGauss消去法消去法,其特点就是其特点就是 (1 1)求解求解中小规模线性方程组中小规模线性方程组(即阶数不要太即阶数不要太高高,例如不超过例如不超过10001000)最常用得方法最常用得方法;(2 2)一般用于系数矩阵稠密一般用于系数矩阵稠密(即矩阵得绝大多即矩阵得绝大多数元素都就是非零得数元素都就是非零得)而又没有任何特殊结构而又没有任何特殊结构得线性方程组。得线性方程组。如若系数矩阵具有某种特殊形式如若系数矩阵具有某种特殊形式,则为了尽可则为了尽可能地减少计算量与存储量能地减少计算量与存储量,需采用其她专门得需采用其她专门得方法来求解。方法来求解。1、1、1 三角形方程组得解法三角形方程组得解法1、1、3 三角分解得计算三角分解得计算1、1、2 Gauss变换变换1、1 三角形方程组与三角分解三角形方程组与三角分解 由于三角形方程组简单易于求解,而且它又就是用分解方法解一般线性方程组得基础,所以我们首先考虑这种特殊类型得线性方程组得解法。上页上页 下页下页 返回返回 结束结束 1 1、1 1、1 1三角形方程组得解法三角形方程组得解法 (1.1.1)下三角形方程组形如这里 是已知的，是未知的，而 是已知的非奇异下三角阵，即,其中其中 上页上页 下页下页 返回返回 结束结束 我们容易得到方程组我们容易得到方程组(1 1、1 1、1 1)得解得解得分量表达式得分量表达式 这种解方程组（1.1.1）的方法称之为前代法前代法.如果在实际计算时将得到的 就存放在 所用的存储单元内，并适当调整一下运算顺序，可得如下算法：上页上页 下页下页 返回返回 结束结束 算法算法1.1.11.1.1（解下三角形方程组：前代法）（解下三角形方程组：前代法）该算法所需要的加、减、乘、除运算的次数为：即该算法的运算量为 。上页上页 下页下页 返回返回 结束结束 注意注意:针对方程针对方程(1 1、1 1、1 1)使用消元法使用消元法,我们能我们能够得到另外一种程序。算法分析如下够得到另外一种程序。算法分析如下:第一步:对增广矩阵实施行初等变换,使之成为其中：其中：显然地，上式右端是显然地，上式右端是与原方程组同解的一个方程组的增广矩阵。与原方程组同解的一个方程组的增广矩阵。上页上页 下页下页 返回返回 结束结束 第第k步步:消元工作如下消元工作如下上页上页 下页下页 返回返回 结束结束 经经n-1步变换之后步变换之后,我们将得到原方程组得如下同解我们将得到原方程组得如下同解方程方程:其中：其中：上页上页 下页下页 返回返回 结束结束 最后，对第最后，对第n个方程做行初等变换，令个方程做行初等变换，令 我们便得到原方程组的一个最简形式的同解方程组：我们便得到原方程组的一个最简形式的同解方程组：其中：其中：综合上述综合上述,我们得到如下算法程序我们得到如下算法程序:上页上页 下页下页 返回返回 结束结束 (1.1.2)再考虑如下上三角形方程组再考虑如下上三角形方程组:其中其中 是非奇异上三角阵。是非奇异上三角阵。这一方程组可以用所谓的回代法解之，即从方程组这一方程组可以用所谓的回代法解之，即从方程组的最后一个方程出发依次求出的最后一个方程出发依次求出 ，其计，其计算公式为算公式为上页上页 下页下页 返回返回 结束结束 显然该算法的运算量也为 。算法算法1.1.21.1.2（解上三角形方程组：回代法）（解上三角形方程组：回代法）上页上页 下页下页 返回返回 结束结束 对于一般的线性方程组对于一般的线性方程组 （1.1.3）其中其中 和和 是已知的，是已知的，是未知的，如果是未知的，如果我们能够将我们能够将A分解为：分解为：，即一个下三角阵，即一个下三角阵L与一与一个上三角阵个上三角阵U的乘积，那么原方程组的解的乘积，那么原方程组的解x便可由下面便可由下面两步得到：两步得到：(1)用前代法解用前代法解 得得y；(2)用回代法解用回代法解 得得x.所以对于求解一般得线性方程组来说所以对于求解一般得线性方程组来说,关键就是如关键就是如何将何将A分解为一个下三角阵分解为一个下三角阵L与一个上三角阵与一个上三角阵U得乘得乘积积,这正就是我们本节得中心任务。这正就是我们本节得中心任务。返回1、1、2 Gauss变换变换 引理引理1 设 是两个单位下三角矩阵，则 仍是单位下三角矩阵。引理引理2 设 是两个上三角矩阵，则 仍是上三角矩阵。定义定义1 设 ，那么以下的变换称为初等行（列）变换：第一种初等变换又称对换。互换的两行（列）；第二种初等变换又称倍乘。用中一个非零的数乘的某行（列）；第三种初等变换又称倍加。用中的一个数乘的某行（列）加到另外一行（列）。上页上页 下页下页 返回返回 结束结束 引理引理3 设设 是一个初等矩阵，则方程组是一个初等矩阵，则方程组与方程组与方程组 同解。同解。欲把一个给定的矩阵欲把一个给定的矩阵A分解为一个下三角阵分解为一个下三角阵L与一个上三角与一个上三角阵阵U的乘积，最自然的做法是通过一系列的初等变换，逐步将的乘积，最自然的做法是通过一系列的初等变换，逐步将A约化为一个上三角阵，而又能保证这些变换的乘积是一个下约化为一个上三角阵，而又能保证这些变换的乘积是一个下三角矩阵。这可归结为：对于一个任意给定的向量三角矩阵。这可归结为：对于一个任意给定的向量 找一找一个尽可能简单的下三角矩阵，使经这一矩阵作用之后的第个尽可能简单的下三角矩阵，使经这一矩阵作用之后的第k+1至第至第n分量均为零。能够完成这一任务的最简单的下三角矩阵分量均为零。能够完成这一任务的最简单的下三角矩阵便是便是Gauss变换阵。变换阵。上页上页 下页下页 返回返回 结束结束 定义定义3 如下形式的初等下三角阵如下形式的初等下三角阵其中其中 即即这种类型的初等单位下三角矩阵称作这种类型的初等单位下三角矩阵称作 Gauss 变换，变换，而称向量而称向量 为为 Gauss 向量。向量。上页上页 下页下页 返回返回 结束结束 命题命题1 对于一个给定的向量对于一个给定的向量 若若 ，取，取其中：其中：则则Gauss变换：变换：使使证明：由于证明：由于将将 代入，即得出结论。代入，即得出结论。上页上页 下页下页 返回返回 结束结束 命题命题2 Gauss变换变换 的逆变换为的逆变换为命题命题3 当当 时，则时，则上页上页 下页下页 返回返回 结束结束 命题命题4 设设 ，则对，则对A施以指标为施以指标为k的的Gauss变换，变换，A 的前的前k行保持不变。行保持不变。则则从而从而证明证明 将将A按行分块，记为按行分块，记为 返回1、1、3 三角分解得计三角分解得计算算1、1、3、1 算法得理论分析算法得理论分析假定 ，三角分解是指分解 ，其中 为下三角矩阵，为上三角矩阵。基于分解式的这种表达方式，有时亦称三角分解为LU分解。下面我们来讨论怎样利用下面我们来讨论怎样利用Gauss变换来实现变换来实现A得三得三角分解。先来考察一个简单得例子。设角分解。先来考察一个简单得例子。设上页上页 下页下页 返回返回 结束结束 我们首先计算一个Gauss变换 使得 的第1列的后两个元素为0。由命题1和4容易得出且然后再计算Gauss变换 使得 的第2列的最后一个元素为0，再由命题1和4得上页上页 下页下页 返回返回 结束结束 且且由命题由命题2令令上页上页 下页下页 返回返回 结束结束 则有则有对于一般的对于一般的n阶矩阵阶矩阵A，在一定条件下在一定条件下，我们也可以，我们也可以计算计算n-1个个Gauss变换变换 ，使得，使得 为为上三角矩阵上三角矩阵。事实上，记事实上，记 ，并假定已求出，并假定已求出k-1个个Gauss变变换换 使得使得其中其中 是是k-1阶上三角阵，阶上三角阵，为为 上页上页 下页下页 返回返回 结束结束 如果如果 ，则我们就又可以确定一个，则我们就又可以确定一个Gauss变换变换 ，使，使得得 中第中第k列的最后列的最后n-k个元素为个元素为0。由前面所介绍的。由前面所介绍的Gauss变换可知，这样的变换可知，这样的 应为应为其中其中因为因为 ，故，故 是唯一确定的。对于这样确定的是唯一确定的。对于这样确定的 ，我们有我们有上页上页 下页下页 返回返回 结束结束 其中其中 是是k阶上三角阵。从阶上三角阵。从k=1出发，如此进行出发，如此进行n-1步，最步，最终所得矩阵终所得矩阵 即为我们所要求的上三角矩阵，则我们就已即为我们所要求的上三角矩阵，则我们就已经实现了经实现了A的上三角形约化。的上三角形约化。若令若令则则注意到对注意到对 j i有有 ,从而从而上页上页 下页下页 返回返回 结束结束 由此可见由此可见,L不仅就是一个单位下三角矩阵不仅就是一个单位下三角矩阵,而且就是非常而且就是非常容易得到得。容易得到得。即即L具有形式具有形式 通常称通常称Gauss消去过程中的消去过程中的 为主元。显然，当且仅当为主元。显然，当且仅当 均不为零时，算法均不为零时，算法1.1.3才能进行到底。那才能进行到底。那么自然要问：给定的矩阵么自然要问：给定的矩阵A满足什么，才能保证所有主元均不满足什么，才能保证所有主元均不为零？这一问题可由下面定理回答。为零？这一问题可由下面定理回答。上页上页 下页下页 返回返回 结束结束 定理定理1.1.1 主元主元 均不为零的充分与必要均不为零的充分与必要条件是条件是A的的i阶顺序主子阵阶顺序主子阵 都是非奇异的。都是非奇异的。证明证明:对对k用归纳法用归纳法.当当k=1时，时，定理显然成立。，定理显然成立。假定定理直至假定定理直至k-1成立成立,下面只需证明下面只需证明“若若 非奇异非奇异,则则 非奇异的充要条件是非奇异的充要条件是 ”即可即可.由归纳法假定由归纳法假定知知 .因此，因此，Gauss消去过程至少可进行消去过程至少可进行k-1步，即可得到步，即可得到k-1个个Gauss变换变换 ，使得，使得（1.1.4）其中其中 是对角元为是对角元为 的上三角阵。的上三角阵。上页上页 下页下页 返回返回 结束结束 由此可知由此可知 的的k阶顺序主子阵有如下形式阶顺序主子阵有如下形式若将若将 的的k阶顺序主子阵分别记为阶顺序主子阵分别记为 ，则由（则由（1.1.4）及下三角阵的性质可知）及下三角阵的性质可知注意到注意到 是单位下三角阵，由此立即得到是单位下三角阵，由此立即得到从而有从而有 非奇异当且仅当非奇异当且仅当 。上页上页 下页下页 返回返回 结束结束 定理定理1.1.2 若若 的顺序主子阵的顺序主子阵 均非奇异，则存在唯一的单位下三角阵均非奇异，则存在唯一的单位下三角阵 和上三角和上三角阵阵 使得使得 。上页上页 下页下页 返回返回 结束结束 1、1、3、2 算法得编算法得编程程 这种计算三角分解的方法称作Gauss消去法消去法。实际编程计实际编程计算时，我们还需要弄清的是：当算时，我们还需要弄清的是：当 作用于作用于 后，后，的哪的哪些元素作了改变？以及作了怎样的改变？此外，些元素作了改变？以及作了怎样的改变？此外，及及 的的元素又是怎样存储起来的？元素又是怎样存储起来的？因为并注意到 是 的第k行以及 的前k个分量为0，我们即知 和 的前k行元素相同，而上页上页 下页下页 返回返回 结束结束 与与 的存储是这样考虑的：的存储是这样考虑的：中的第中的第k+1行至第行至第n行的元素在计算出行的元素在计算出 以后不再有用，故可以用新计算出以后不再有用，故可以用新计算出的的 元素冲掉元素冲掉 中相应位置上的元素。此外，由于中相应位置上的元素。此外，由于 的第的第k列对角元以下的元素列对角元以下的元素 为零，无需存储，为零，无需存储，故故 中非零元素即可存储在这些位置上。例如一个中非零元素即可存储在这些位置上。例如一个 的矩的矩阵阵A在经过二步消元后，其形式为在经过二步消元后，其形式为上页上页 下页下页 返回返回 结束结束