线性方程组的直接解法课件

第四章方程组的直接解法4.1 Gauss消去法消去法4.1.4 Gauss-Jordan消元法消元法4.1.3 主元素消去法主元素消去法4.1.2 矩阵的三角分解矩阵的三角分解4.1.1 Gauss消去法的计算过程消去法的计算过程4.1 Gauss消去法4.1.4 Gauss-J第四章方程组的直接解法第第4章章 线性方程组的直接解法线性方程组的直接解法教学目的教学目的 1.掌握解线性方程组的高斯消去法、高斯选主元素消去法；掌握解线性方程组的高斯消去法、高斯选主元素消去法；2.掌握用直接三角分解法解线性方程组的方法；掌握用直接三角分解法解线性方程组的方法；3.了解解对称正定矩阵线性方程组的平方根法与解三对角线方程了解解对称正定矩阵线性方程组的平方根法与解三对角线方程组的追赶法；组的追赶法；4.掌握向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分掌握向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析。析。教学重点及难点教学重点及难点 重点是重点是1.解线性方程组的高斯消去法、高斯选主元素消去法；解线性方程组的高斯消去法、高斯选主元素消去法；2.直接三角分解法解线性方程组的方法；直接三角分解法解线性方程组的方法；3.向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析；向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析；难点是难点是方程组的扰动分析。方程组的扰动分析。第4章 线性方程组的直接解法教学目的 第四章方程组的直接解法 实际中，存在大量的解线性方程组的问题。很多数值方实际中，存在大量的解线性方程组的问题。很多数值方法到最后也会涉及到线性方程组的求解问题：如样条插值的法到最后也会涉及到线性方程组的求解问题：如样条插值的M和和m关系式，曲线拟合的法方程，方程组的关系式，曲线拟合的法方程，方程组的Newton迭代等迭代等问题。问题。第第4章章 线性方程组的直接解法线性方程组的直接解法 实际中，存在大量的解线性方程组的问题。很第四章方程组的直接解法对线性方程组：对线性方程组：或者：或者：我们有我们有Gram法则：当且仅当法则：当且仅当时，有唯一的解，而且解为：时，有唯一的解，而且解为：对线性方程组：或者：我们有Gram法则：当且仅当时，有唯一的第四章方程组的直接解法但但Gram法则不能用于计算方程组的解，如法则不能用于计算方程组的解，如n100，1033次次/秒的计算机秒的计算机要算要算10120年年解线性方程组的方法可以分为解线性方程组的方法可以分为2类：类：直接法直接法：准确，可靠，理论上得到的解是精确的：准确，可靠，理论上得到的解是精确的迭代法迭代法：速度快，但有误差：速度快，但有误差本章讲解直接法本章讲解直接法对于中小型方程组，常用直接解法。从本质上来说，直接方法对于中小型方程组，常用直接解法。从本质上来说，直接方法的原理是找一个可逆矩阵的原理是找一个可逆矩阵M，使得，使得MA是一个上三角阵，这一过程一是一个上三角阵，这一过程一般称为般称为“消元消元”过程，消元之后再进行过程，消元之后再进行“回代回代”，即求解，即求解MAx=Mb。本章讨论本章讨论Gauss消去法及其变形，以及一些情况下的特殊方法，最后消去法及其变形，以及一些情况下的特殊方法，最后进行误差分析。进行误差分析。但Gram法则不能用于计算方程组的解，如n100，1033第四章方程组的直接解法4.1 Gauss消去法消去法我们知道，下面有我们知道，下面有3种方程的解我们可以直接求出：种方程的解我们可以直接求出：n次运算（n1）n/2次运算4.1 Gauss消去法我们知道，下面有3种方程的第四章方程组的直接解法（n1）n/2次运算（n1）n/2次运算第四章方程组的直接解法对方程组，作如下的变换，解不变对方程组，作如下的变换，解不变交换两个方程的次序交换两个方程的次序一个方程的两边同时乘以一个非一个方程的两边同时乘以一个非0 0的数的数一个方程的两边同时乘以一个非一个方程的两边同时乘以一个非0 0数，加到另一个方程数，加到另一个方程因此，对应的对增广矩阵因此，对应的对增广矩阵(A，b)，作如下的变换，解不变，作如下的变换，解不变交换矩阵的两行交换矩阵的两行某一行乘以一个非某一行乘以一个非0 0的数的数某一个乘以一个非某一个乘以一个非0 0数，加到另一行数，加到另一行消元法消元法就是对增广矩阵作上述行的变换，变为我们已知的就是对增广矩阵作上述行的变换，变为我们已知的3种类型之一，种类型之一，而后求根而后求根.对方程组，作如下的变换，解不变交换两个方程的次序一个方程第四章方程组的直接解法思思路路首先将首先将A化为上三角阵，再回代求解化为上三角阵，再回代求解 。=4.1.1 Gauss消去法的计算过程消去法的计算过程我们把方程组我们把方程组Ax=b写成写成设方程组设方程组(4,.1.1)的系数矩阵的系数矩阵A非奇异非奇异,记记(4.1.1)思路首先将A化为上三角阵，再回代求解。=4.1.1 Gau第四章方程组的直接解法 ,这样这样,方程组方程组(4.1.1)又可写成又可写成 。消元过程就是要按确定。消元过程就是要按确定的计算过程对方程组进行初等行变换的计算过程对方程组进行初等行变换,将方程组化为上三角方程组将方程组化为上三角方程组.线性方程组的直接解法课件第四章方程组的直接解法第一步消元第一步消元:假设假设 ,作初等行变换运算作初等行变换运算步骤如下：步骤如下：运算量：运算量：(n-1)*(1+n)第一步消元:假设 ,作初等行变换第四章方程组的直接解法运算量：运算量：(n-2)*(1+n-1)=(n-2)n第二步：第二步：运算量：(n-2)*(1+n-1)=(n-2)n第二步：第四章方程组的直接解法第第k步消元步消元:设消去法已进行设消去法已进行k-1步步,得到方程组得到方程组 ,此时此时对应的增广矩阵是对应的增广矩阵是第k步消元:设消去法已进行k-1步,得到方程组 第四章方程组的直接解法第第k步：步：类似的做下去，我们有：类似的做下去，我们有：运算量：运算量：(nk)*(1nk1)=(nk)(nk2)n1步以后，我们可以得到变换后的矩阵为：步以后，我们可以得到变换后的矩阵为：这就完成了消元过程。这就完成了消元过程。(4.1.4)第k步：类似的做下去，我们有：运算量：(nk)*(1n第四章方程组的直接解法因此，总的运算量为：因此，总的运算量为：加上加上 解上述上三角阵的运算量解上述上三角阵的运算量(n+1)n/2，总共为：，总共为：因此，总的运算量为：加上 解上述上三角阵的运算量(n+1)n第四章方程组的直接解法因为因为A非奇异，所以可求解上三角方程组（非奇异，所以可求解上三角方程组（4.1.4），通过逐次），通过逐次代入计算可得方程组的解，其计算公式为代入计算可得方程组的解，其计算公式为(4.1.5)求解上式的过程称为求解上式的过程称为回代过程回代过程。以上由消去过程和回代过程合起来求解（以上由消去过程和回代过程合起来求解（4.1.1）的过程就称）的过程就称为为Gauss消去法，或称为顺序消去法，或称为顺序Gauss消去法。消去法。因为A非奇异，所以可求解上三角方程组（4.1.4），通过第四章方程组的直接解法如果我们用如果我们用Cramer法则计算（法则计算（4.1.1）的解，要计算）的解，要计算n+1个阶行列式，个阶行列式，并作并作n次除法。如果用子式展开的方法计算行列式，则计算次除法。如果用子式展开的方法计算行列式，则计算每个行列式有每个行列式有n！次乘法。所以用！次乘法。所以用Cramer法则大约需要（法则大约需要（n+1）！）！次乘除法运算。例如，当次乘除法运算。例如，当n=10时，约需乘除法运算，而用时，约需乘除法运算，而用Gauss消消去法只需去法只需430次乘除法运算。次乘除法运算。例例4.1 用用Gauss消去法解方程组消去法解方程组解解 第一步消元，令第一步消元，令 得增广矩阵得增广矩阵如果我们用Cramer法则计算（4.1.1）的解，要计算n+第四章方程组的直接解法第二步消元，令第二步消元，令 得增广矩阵得增广矩阵利用回代公式（利用回代公式（4.1.5）依次得到）依次得到在这个例子中我们写出的是分数运算的结果。如果在计算机上在这个例子中我们写出的是分数运算的结果。如果在计算机上进行计算，系数矩阵和中间结果都用经过舍入的机器数表示，中间进行计算，系数矩阵和中间结果都用经过舍入的机器数表示，中间结果和方程组的解都会有误差。结果和方程组的解都会有误差。4.1.2 矩阵的三角分解矩阵的三角分解从上面的消元过程可以看出，消元过程能顺利进行的重要条件从上面的消元过程可以看出，消元过程能顺利进行的重要条件是主元素是主元素 。若用。若用 表示矩阵表示矩阵A的的k阶顺序阶顺序主子阵，则有下面的定理。主子阵，则有下面的定理。第二步消元，令 第四章方程组的直接解法定理定理4.1 全不为零的充要条件是全不为零的充要条件是A的顺序主子的顺序主子式式 其中其中 。证证 先证必要性设先证必要性设 ，则可进行，则可进行k-1步消元程。步消元程。显然显然 ，对，对 ，由于每步进行的初等变换不改变，由于每步进行的初等变换不改变顺序主子式的值，所以第顺序主子式的值，所以第i-1步消元后有步消元后有用归纳法证充分性。用归纳法证充分性。k=1时，命题显然成立。设命题对时，命题显然成立。设命题对m-1成立。成立。现设现设 由归纳假设有由归纳假设有 Gauss消去法可进行第消去法可进行第m-1步，矩阵步，矩阵A变换为变换为定理4.1 第四章方程组的直接解法其中其中 是对角元素为是对角元素为 的上三角阵。的上三角阵。因因 是通过消元过程由是通过消元过程由A逐步经初等变换得到的，逐步经初等变换得到的，A的的m 阶顺序主阶顺序主子式等于子式等于 的的m 阶顺序主子式，即阶顺序主子式，即由由 可推出可推出 ，定理得证。，定理得证。定理定理4.2 在方程组在方程组Ax=b中，中，A非奇异，则当非奇异，则当A的所有顺序主子式的所有顺序主子式均不为零时，可用均不为零时，可用Gauss消去法求解出方程组的解。消去法求解出方程组的解。特别地，若特别地，若A为对称正定矩阵，则由对称正定矩阵的性质可知，为对称正定矩阵，则由对称正定矩阵的性质可知，对原方程组不必作任何处理，可直接对原方程组不必作任何处理，可直接Gauss消去法求解方程组。消去法求解方程组。下面将消元过程用矩阵运算表示。对第下面将消元过程用矩阵运算表示。对第k步，利用（步，利用（4.1.3）给出）给出的乘数的乘数 ，记，记 ，又记，又记 为第为第k 个分量为个分量为1的单位向量，令的单位向量，令(4.1.6)其中 是对角元素为 第四章方程组的直接解法不难验证不难验证即即利用矩阵（利用矩阵（4.1.6），第），第k步消元过程相当于步消元过程相当于这样经过这样经过n-1步消元过程得到步消元过程得到这里，这里，是上三角阵。记是上三角阵。记 ，又记，又记不难验证利用矩阵（4.1.6），第k步消元过程相当于这里第四章方程组的直接解法这种矩阵称为单位下三角阵。这种矩阵称为单位下三角阵。L的对角线以下各元素就是各步消元过的对角线以下各元素就是各步消元过程的乘数。最后我们得到程的乘数。最后我们得到 A=LU （4.1.7）称该式为称该式为A的的LU分解。分解。定理定理4.3 矩阵矩阵 ，若其顺序主子式，若其顺序主子式 皆皆非零，则存在唯一的单位下三角阵非零，则存在唯一的单位下三角阵L和上三角阵和上三角阵U，使，使A=LU。其中，其中，都是单位下三角阵，都是单位下三角阵，都是上三角阵。因都是上三角阵。因A非奇异，非奇异，则则 都可逆。都可逆。A左乘左乘 ，右乘，右乘 即得即得因因 仍为上三角阵，仍为上三角阵，也是上三角阵，同理是单位下三角阵，所也是上三角阵，同理是单位下三角阵，所以只能有以只能有即即 。定理得证。定理得证证证 以上的分析已证明了以上的分析已证明了A可作可作LU分解，下面证明分解的唯一性。分解，下面证明分解的唯一性。设设A有两个分解式有两个分解式这种矩阵称为单位下三角阵。L的对角线以下各元素就是各步消元过第四章方程组的直接解法分解式（分解式（4.1.7）也称为）也称为Doolittle分解。由（分解。由（4.1.7）式可求出）式可求出A的的行列式，即行列式，即若将上三角若将上三角U写成写成 ，其中，其中D是对角阵，是对角阵，是单位上三角阵，是单位上三角阵，则有则有称该式为称该式为A的的LDU分解，显然，这种分解具有唯一性。分解，显然，这种分解具有唯一性。（4.1.8）4.1.3 主元素消去法主元素消去法在以上的在以上的Gauss消去法中，消元过程能进行的条件是主元素消去法中，消元过程能进行的条件是主元素 。例如，若。例如，若 ，消去过程的第，消去过程的第1步就步就不能进行。有时虽然不能进行。有时虽然 但是但是 很小，这时计算过程的很小，这时计算过程的舍入误差会导致消去法数值不稳定，以致结果不可靠。舍入误差会导致消去法数值不稳定，以致结果不可靠。例例4.2 用三位十进制浮点运算求解用三位十进制浮点运算求解分解式（4.1.7）也称为Doolittle分解。由（4第四章方程组的直接解法解解 这个方程组的准确解显然应接近这个方程组的准确解显然应接近 .但是系数但是系数 是是个小主元，如果用个小主元，如果用Gauss消去法求解，则有消去法求解，则有在三位十进制运算的限制下，得到在三位十进制运算的限制下，得到 ，代回第，代回第1个个方程得方程得 ，这个显然不是正确的解。因为用小主元，这个显然不是正确的解。因为用小主元 做除法，做除法，使乘数使乘数 是个大数，在是个大数，在 的计算中，的计算中，的值完全被掩盖了。的值完全被掩盖了。如果先把两个方程的次序交换，再用如果先把两个方程的次序交换，再用Gauss消去法，就不会出现消去法，就不会出现上述问题，解得上述问题，解得 ，这就是列主元素消去法的思想。，这就是列主元素消去法的思想。列主元素消去法列主元素消去法也称按列部分主元的消去法。一般地，在完成也称按列部分主元的消去法。一般地，在完成了第了第k-1步消元运算后，在步消元运算后，在 的第的第k 列元素列元素 之下的所有之下的所有元素中选一个绝对值最大的元素作为主元素，即若元素中选一个绝对值最大的元素作为主元素，即若解 这个方程组的准确解显然应接近 第四章方程组的直接解法则以则以 为主元素，这里为主元素，这里 ,且且 由于非奇异，由于非奇异，有有 .这样，这样，有达到控制舍入误差的作有达到控制舍入误差的作用。用。选出主元素后，若则进行顺序选出主元素后，若则进行顺序Gauss消去法的第消去法的第k步若步若 ，则将则将 的第的第 行与第行与第k行交换，然后进行消元运算。行交换，然后进行消元运算。完成了完成了n-1步主元，换行与消元运算后，得到步主元，换行与消元运算后，得到 ，这是，这是与原方程组等价的方程组与原方程组等价的方程组,是一个上三角阵是一个上三角阵,再代回求解再代回求解.这就是这就是列列主元素消去法的计算过程主元素消去法的计算过程.除了列主元素消去法外除了列主元素消去法外,还有一种还有一种完全主元素消去法完全主元素消去法.在其过程的第在其过程的第k 步步 ,不是按列来选主元不是按列来选主元,而是在右下角的而是在右下角的n-k+1阶子阵中阶子阵中选主元选主元 ,即即然后将然后将 的第的第 行与第行与第k行交换将第行交换将第 列与第列与第k列交换列交换,同时同时将自变量将自变量 与与 的位置交换并记录自变量的排列次序的位置交换并记录自变量的排列次序.直到消直到消去法完成后去法完成后,再按记录恢复自变量为自然次序再按记录恢复自变量为自然次序.完全主元法比列主元完全主元法比列主元法法则以 为主元素，这里 第四章方程组的直接解法运算量大得多运算量大得多,由于列主元法的舍如误差一般已较小由于列主元法的舍如误差一般已较小,所以在实际计所以在实际计算中多用列主元法算中多用列主元法.例例4.3 用列主元素消去法解方程组用列主元素消去法解方程组Ax=b,计算过程中五位有计算过程中五位有效数字进行运算效数字进行运算,其中其中解解 记记 .第一步选列主元为第一步选列主元为 ，交换，交换第第1行与第行与第3行，再消元计算得行，再消元计算得第二步选列主元为第二步选列主元为 ,交换第交换第2行与第行与第3行，再消元计行，再消元计算得算得运算量大得多,由于列主元法的舍如误差一般已较小,所以在实际计第四章方程组的直接解法消去过程至此结束。回代计算依次得到解消去过程至此结束。回代计算依次得到解这个例题的精确解是这个例题的精确解是 而用不选住主元的顺序而用不选住主元的顺序Gauss消去法，则解得消去法，则解得这个结果误差较大，这是因为消去法的第这个结果误差较大，这是因为消去法的第1步中，步中，按绝对值比按绝对值比其他元素小很多所引起的。从此例看到列主元素消去法是有效的其他元素小很多所引起的。从此例看到列主元素消去法是有效的方法。方法。消去过程至此结束。回代计算依次得到解这个结果误差较大，这是因第四章方程组的直接解法下面讨论矩阵的含换行的三角分解，即列主元法中消去过程下面讨论矩阵的含换行的三角分解，即列主元法中消去过程的矩阵表示。一般的，将矩阵的矩阵表示。一般的，将矩阵A的第的第i行与第行与第j行交换，其结果相行交换，其结果相当于矩阵当于矩阵A左乘一个初等排列矩阵左乘一个初等排列矩阵 ，即，即 ，这里，这里 是是单位阵单位阵I交换第交换第i行与第行与第j行后所得的矩阵，不难验证行后所得的矩阵，不难验证若矩阵若矩阵A右乘右乘 得得 ，其结果是将，其结果是将A的第的第i列与第列与第j列交换后所列交换后所得的矩阵。得的矩阵。我们把若干个初等排列矩阵的乘积称作我们把若干个初等排列矩阵的乘积称作排列矩阵排列矩阵，其结果是，其结果是将单位矩阵经过若干次交换所得的矩阵。将单位矩阵经过若干次交换所得的矩阵。列主元素消去法的每一步，一般是先按列选主元再交换行，然后列主元素消去法的每一步，一般是先按列选主元再交换行，然后进行消元计算，所以有进行消元计算，所以有其中其中 为为(4.1.6)所示，所示，是初等排列阵，是初等排列阵，是第是第k步列选主步列选主元所在的行号。如果第元所在的行号。如果第k步不需换行，则步不需换行，则下面讨论矩阵的含换行的三角分解，即列主元法中消去过程的矩第四章方程组的直接解法列主元素消去法的消元过程进行列主元素消去法的消元过程进行n-1步之后得到上三角阵步之后得到上三角阵 ,记记这就是列主元法消去过程的矩阵表示。由于列主元的选取，我们可这就是列主元法消去过程的矩阵表示。由于列主元的选取，我们可知知 及及 原始的绝对值不大于原始的绝对值不大于1。定理定理4.4 设设A为非奇异矩阵，则存在排列阵，单位小三角矩阵为非奇异矩阵，则存在排列阵，单位小三角矩阵L和上三角阵和上三角阵U，使，使PA=LU.证证 从从(4.1.9)可得可得其中其中U为上三角阵。令排列阵为上三角阵。令排列阵则利用则利用 有有列主元素消去法的消元过程进行n-1步之后得到上三角阵 第四章方程组的直接解法4.1.4 Gauss-Jordan消元法消元法考虑考虑Gauss消去法的一种修正：消去对角线下方和上方的元素。消去法的一种修正：消去对角线下方和上方的元素。称这种方法为称这种方法为Gauss-Jordan消去法。设用消去法。设用Gauss-Jordan消去法已完消去法已完成成k-1步，得到与方程步，得到与方程Ax=b等价的方程组等价的方程组 ，此时对应的，此时对应的增广矩阵是增广矩阵是由此，若记由此，若记则得则得PA=LU。由初等排列阵的性质。由初等排列阵的性质 是一个单位下三角阵，是一个单位下三角阵，L也是一个单元下三角阵。定理得证。也是一个单元下三角阵。定理得证。4.1.4 Gauss-Jordan消元法考虑Gauss第四章方程组的直接解法这里，略去了矩阵元素的上标。在第这里，略去了矩阵元素的上标。在第k步计算时，考虑对上述矩阵地步计算时，考虑对上述矩阵地k列中的第列中的第k行上，下都进行消元计算。若用列主元素消去法，仍然是行上，下都进行消元计算。若用列主元素消去法，仍然是第第k列元素列元素 之下的所以元素中选一个绝对值最大的元素做为主元素之下的所以元素中选一个绝对值最大的元素做为主元素,即即但是，将第但是，将第k行与第行交换后，要通过住行将第行与第行交换后，要通过住行将第k列的第列的第 个元素化为零，再将主行的对角线上元素化为个元素化为零，再将主行的对角线上元素化为1。最后。最后 得得 ，这里，这里，是单位矩阵，是单位矩阵，就是计算解。就是计算解。可见，可见，Gauss-Jordan消去法用不着回代求解，其计算量大约消去法用不着回代求解，其计算量大约需要需要 次乘除法运算，要比次乘除法运算，要比Gauss消去法的计算量大但用消去法的计算量大但用Gauss-Jordan消去法求一个矩阵的逆矩阵是很合适的。消去法求一个矩阵的逆矩阵是很合适的。这里，略去了矩阵元素的上标。在第k步计算时，考虑对上述矩阵地第四章方程组的直接解法定理定理4.5 设设A为为为为n阶非奇异矩阵，方程组阶非奇异矩阵，方程组Ax=I的增广矩阵为的增广矩阵为C=（A，I）。如果对）。如果对C用用Gauss-Jordan消去法化为（消去法化为（I，T），则），则 .证证 设设 ,则则 这里，这里，为单位矩阵为单位矩阵I的第的第j列，用列，用Gauss-Jordan消去法解方程组消去法解方程组 ,其解在其解在C中中I的第的第j列，即为列，即为T的第的第j列，即列，即 .因此因此 .定理得证定理得证.例例4.4 用用Gauss-Jordan消去法求矩阵消去法求矩阵的逆矩阵。的逆矩阵。定理4.5 设A为为n阶非奇异矩阵，方程组Ax=I的增第四章方程组的直接解法解解 用列主元素消去法有用列主元素消去法有解 用列主元素消去法有第四章方程组的直接解法在实际计算中，为了节省内存单元，单位矩阵不必存放。在上例中，在实际计算中，为了节省内存单元，单位矩阵不必存放。在上例中，可将可将 的最后一列放在的最后一列放在A第第I列，将列，将 的第的第5列存放在列存放在A的第的第2列，列，将将 的第的第4列存在列存在A的第的第3列。一般地，第列。一般地，第k步消元时，可将步消元时，可将A的第的第k列列用向量用向量取代。最后再调整一下列就可以在取代。最后再调整一下列就可以在A的位置得到的位置得到 。实际上，在。实际上，在A的位置最后得到的矩阵的位置最后得到的矩阵 是的逆矩阵是的逆矩阵 ，其中，其中P为行变换为行变换形成的排列阵，于是形成的排列阵，于是在实际计算中，为了节省内存单元，单位矩阵不必存放。在上例中，