解线性方程组的直接方法

第5章解线性方程组的干脆方法15.1引言与预备学问

5.1.1引言线性方程组的数值解法一般有两类：1.干脆法经过有限步算术运算，可求得方程组精确解的方法(若计算过程中没有舍入误差).但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解.22.迭代法是用某种极限过程去逐步靠近线性方程组精确解的方法.35.1.2向量和矩阵用表示全部实矩阵的向量空间，表示全部复矩阵的向量空间.这种实数排成的矩形表，称为行列矩阵.称为维列向量.4其中为的第列.其中为的第行.也可写成行向量的形式写成列向量的形式5(5)单位矩阵矩阵的基本运算：(1)矩阵加法(2)矩阵与标量的乘法(3)矩阵与矩阵乘法(4)转置矩阵6(6)非奇异矩阵设则称是如果存在，则称为非奇异矩阵.如果均为非奇异矩阵，其中如果的逆矩阵，记为且则(7)矩阵的行列式设则的行列式可按任一行(或列)展开，7其中为的代数余子式，行列式性质：即的余子式.为元素85.1.3特殊矩阵设(1)对角矩阵(2)三对角矩阵(3)上三角矩阵(4)上海森伯格（Hessenberg）阵(5)对称矩阵9(6)埃尔米特矩阵(7)对称正定矩阵(8)正交矩阵(9)酉矩阵(10)初等置换阵由单位矩阵交换第行与第行(或交换第列与第列)，得到的矩阵记为,且10(11)置换阵

定理1设，(1)对任何方程组有唯一解.（为交换第行与第行得到的矩阵）；（为交换第列与第列得到的矩阵）；由初等置换阵的乘积得到的矩阵.则下述命题等价：(2)齐次方程组只有唯一解.(4)存在.(5)的秩(3)11

定理2设为对称正定阵，则(1)为非奇异矩阵，且亦是对称正定阵.(2)记为的顺序主子阵，则亦是对称正定矩阵，其中(3)的特征值(4)的顺序主子式都大于零，即12

定理3设为对称矩阵.或的特征值则为

定理4(Jordan标准型)设为阶矩阵，则存在一个非奇异矩阵使得如果对称正定阵.13其中为若当（Jordan）块.(1)当的若当标准型中所有若当块均为一阶时，此标准型变成对角矩阵.14(2)如果的特征值各不相同，则其若当标准型必为对角阵155.2高斯消去法16

5.2.1高斯消去法设有线性方程组（2.1）或写为矩阵形式17简记为

例1

解消去(2.4)中的未知数得到将方程(2.2)乘上加到方程(2.4)上去，第2步.用消去法解方程组第1步.将方程(2.3)加到方程(2.5)上去，消去方程18(2.5)中的未知数得到与原方程组等价的三角形方程组明显，方程组(2.6)是简洁求解的，解为上述过程相当于19其中用表示矩阵的第行.由此看出，用消去法解方程组的基本思想是用逐次消去未知数的方法把原方程组化为与其等价的三角形方程组，而求解三角形方程组可用回代的方法.上述过程就是用行的初等变换将原方程组系数矩阵化为简洁形式(上三角矩阵)，从而将求解原方程组(2.1)的问题转化为求解简洁方程组的问题.20或者说，对系数矩阵施行一些左变换(用一些简单矩阵)将其约化为上三角矩阵.下面探讨求解一般线性方程组的高斯消去法.将(2.1)记为其中(1)第1步设首先计算乘数用乘(2.1)的第一个方程，加到第个方程上，消去(2.1)的从第二个方程到第个方程中21的未知数得到与(2.1)等价的方程组（2.7）简记为其中的元素计算公式为22(2)第次消元设上述第1步，…，第步消元过程计算已经完成，（2.8）即已计算好与(2.1)等价的方程组简记为23设计算乘数加到第个方程用乘(2.8)的第个方程，消去从第个方程到第个方程中的未知数得到与元素的计算公式为显然中从第1行到第行与相同.(2.1)等价的方程组24(3)继续上述过程，且设直到完成第步消元计算.最后得到与原方程组等价的简单方程组其中为上梯形.特别当时，与原方程组等价的方程组为即（2.10）25如果是非奇异矩阵，且由(2.1)约化为(2.10)的过程称为消元过程.求解三角形方程组(2.10)，得到求解公式（2.11）(2.10)的求解过程(2.11)称为回代.如果由于为非奇异矩阵，所以的第一列一定有元素不等于零.26例如于是交换两行元素(即），将调到(1,1)位置，然后进行消元计算，这时右下角矩阵为阶非奇异矩阵.接着这过程，高斯消去法照样可进行计算.27

定理5设其中(1)如果将约化为等价的三角形方程组(2.10)，且计算公式为：则可通过高斯消去法(a)消元计算28(b)回代计算(2)如果为非奇异矩阵，则可通过高斯消去法(及交换两行的初等变换)将方程组约化为(2.10).29

算法1(高斯算法)本算法用高斯方法将约化为上梯形，且覆盖，乘数覆盖.对于(1)如果则计算停止(2)对于(a)(b)对于设假如30上三角阵，算法1第步需要作次除法，次乘法，因此，本算法(从第1步到第步消元计算总的计算量)当时，总共大约需要次乘法运算.数称为约化的主元素.

算法2(回代算法)设其中为非奇异本算法计算的解.对于(1)大约需要次乘法(对相当大的).31(2)对于(3)这个算法需要乘除法运算.高斯消去法对于某些简洁的矩阵可能会失败，由此，须要对算法1进行修改，例如在什么条件下才能保证首先需要研究原来的矩阵32

定理6约化的主元素的充要条件是矩阵的顺序主子式即（2.12）

证明显然，当时，定理6成立.现设定理6充分性对是成立的，求证定理6充分性对亦成立.首先利用归纳法证明定理6的充分性.33设可用高斯消去法将约化到，且有于是由归纳法假设有即34（2.13）由设定理6充分性对亦成立.显然，由假设利用(2.13)式，则有利用(2.13)式亦可推出35

推论如果的顺序主子式则36于是对(2.1)施行第一次消元后化为(2.7)，5.2.2矩阵的三角分解下面借助矩阵理论进一步对消去法作些分析，从而建立高斯消去法与矩阵因式分解的关系.设(2.1)的系数矩阵的各顺序主子式均不为零.由于对施行行的初等变换相当于用初等矩阵左乘，这时化为化为，即37其中一般第步消元，化为,化为，相当于其中38重复这过程，最终得到（2.14）记上三角矩阵为，由(2.14)得到39其中为单位下三角矩阵.这就是说，高斯消去法实质上产生了一个将分解为两个三角形矩阵相乘的因式分解，于是得到如下重要定理，它在解方程组的直接法中起着重要作用.40

定理7设为阶矩阵，如果的顺序主子式则可分解为一个单位下三角矩阵和一个上三角矩阵的乘积，

证明现在在为非奇异矩阵的假定下证明唯一性，设其中为单位下三角矩阵，为上三角矩阵.(矩阵的LU分解)且这种分解是唯一的.依据以上高斯消去法的矩阵分析，存在性已得证，41上式右边为上三角矩阵，左边为单位下三角矩阵，

例2由高斯消去法，由于存在，故从而上式两边都必需等于单位矩阵，唯一性得证.故对于例1，系数矩阵故4243

例35.3高斯主元素消去法由高斯消去法知道，在消元过程中可能出现即使主元素但很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠.这时消去法将无法进行；求解方程组44用4位浮点数进行计算.精确解舍入到4位有效数字为解法1用高斯消去法45计算解为明显计算解是一个很坏的结果，不能作为方程组的近似解.其缘由是我们在消元计算时用了小主元0.001，使得约化后的方程组元素数量级大大增长，经再舍入使得在计算(3,3)元素时发生了严峻的相消状况，因此经消元后得到的三角形方程组就不精确了.46

解法2交换行，避开确定值小的主元作除数.47得计算解为这个例子告诉我们，在采用高斯消去法解方程组时，小主元可能产生麻烦，故应避免采用绝对值小的主元素对一般矩阵来说，最好每一步选取系数矩阵(或消元后的低阶矩阵)中确定值最大的元素作为主元素，以使高斯消去法具有较好的数值稳定性.这就是全主元素消去法.在选主元时要花费较多机器时间，目前主要运用的是列主元消去法.48本节主要介绍列主元消去法，并假定(2.1)的为非奇异的.495.3.1列主元素消去法设方程组(2.1)的增广矩阵为首先在的第一列中选取绝对值最大的元素作为主元素，例如50重复上述过程，设已完成第步的选主元素，交换两行然后交换的第1行与第行，经第1次消元计算得约化为及消元计算，51其中的元素仍记为,的元素仍记为.第步选主元素(在右下角方阵的第1列内选)，即确定，使交换第行与行的元素，再进行消元计算，最终将原方程组化为52回代求解

算法3(列主元素消去法)设.本算法用具有行交换的列主元素消去法，消元结果冲掉，乘数冲掉，计算解冲掉常数项行列式存放在中.1.