第五讲： 解线性方程组的直接方法

1、第第5章章 解线性方程组的直接方法解线性方程组的直接方法 /*Chapter5 Direct Methods for Solving Linear Systems */ 5.1 引言与预备知识引言与预备知识 5.2 高斯消去法高斯消去法 5.3 矩阵三角分解法矩阵三角分解法 5.4 向量和矩阵的范数向量和矩阵的范数 5.5 误差分析误差分析 这一章讨论线性方程组这一章讨论线性方程组5.1 引言与预备知识引言与预备知识 .,22112222212111212111mnmnmmnnnnbxaxaxabxaxaxabxaxaxa的数值解法的数值解法. 在自然科学和工程技术中在自然科学和工程技术中,

2、,很多问题归结为很多问题归结为解解线性方程组线性方程组. .例如电学中的网络问题，船体数学放例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元方法解常微分方程、偏微分方程边分法或者有限元方法解常微分方程、偏微分方程边值问题等都导致求解线性方程组，而这些值问题等都导致求解线性方程组，而这些方程组的方程组的系数矩阵大致分为两种系数矩阵大致分为两种，一种是低阶稠密矩阵一种是低阶稠密矩阵( (例例如，阶数不如，阶数不超过超过150)

3、. 另另一种是大型稀疏矩阵一种是大型稀疏矩阵( (即矩即矩阵阶数高且零元素较多阵阶数高且零元素较多).).5.1.1 引引 言言 有的问题的数学模型中虽不直接表现为含线性有的问题的数学模型中虽不直接表现为含线性方程组方程组, ,但它的数值解法中将问题但它的数值解法中将问题“离散化离散化”或或“线性化线性化”为线性方程组为线性方程组. .因此因此线性方程组的求解是线性方程组的求解是数值分析课程中最基本的内容之一数值分析课程中最基本的内容之一. . 关于线性方程组的解法一般有两大类：关于线性方程组的解法一般有两大类：直接法、直接法、 迭代法迭代法 但实际计算中由于舍入误差的存在和影响，这但实际计算

4、中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解种方法也只能求得线性方程组的近似解. . 本章将阐本章将阐述这类算法中最基本的和具有代表性的算法就是述这类算法中最基本的和具有代表性的算法就是高高斯消去法斯消去法, ,以及它的某些变形和应用以及它的某些变形和应用. .这类方法是解这类方法是解低阶稠密矩阵方程组及某些大型稀疏矩阵方程组低阶稠密矩阵方程组及某些大型稀疏矩阵方程组( (例例如，大型带状方程组如，大型带状方程组) )的有效方法的有效方法. . 1. 直接法直接法 经过有限次的算术运算经过有限次的算术运算, ,可以求得方程组的精确可以求得方程组的精确解解( (假定计算过程没

5、有舍入误差假定计算过程没有舍入误差).).如线性代数课程中如线性代数课程中提到的克莱姆算法就是一种直接法提到的克莱姆算法就是一种直接法. .但该法对高阶方但该法对高阶方程组计算量太大程组计算量太大, ,不是一种实用的算法不是一种实用的算法. . 就是就是用某种极限过程去逐步逼近方程组精确解用某种极限过程去逐步逼近方程组精确解的方法的方法. . 迭代法具有计算机的存储单元较少、程序设迭代法具有计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优计简单、原始系数矩阵在计算过程中始终不变等优点，但存在点，但存在收敛条件收敛条件和和收敛速度收敛速度问题问题. .迭代法是解大迭代法是

6、解大型稀疏矩阵方程组型稀疏矩阵方程组( (尤其是由微分方程离散后得到的尤其是由微分方程离散后得到的大型方程组大型方程组) )的重要方法的重要方法( (见第见第6 6章章).). 为了讨论线性方程组数值解法，需复习一些基为了讨论线性方程组数值解法，需复习一些基本的矩阵代数知识本的矩阵代数知识. . 2. 迭代法迭代法5.1.2 向量和矩阵向量和矩阵 基本概念基本概念： 用用Rmn表示全部表示全部mn实矩阵的向量空间；实矩阵的向量空间； 用用Cmn表示全部表示全部mn复矩阵的向量空间复矩阵的向量空间. mnmmnnijnmaaaaaaaaaaARA212222111211)(由数排成的矩阵表，称为

7、由数排成的矩阵表，称为m行行n列矩阵列矩阵). mmxxxxRx21其中其中aj为为A的第的第j列的列的m维列向量维列向量. 同理同理(m维列向量维列向量). ,21naaaA ,21 TmTTbbbA其中其中biT为为A的第的第i行的行的n维行向量维行向量. 矩阵的基本运算矩阵的基本运算： (1) 矩阵加法矩阵加法).,(nmijijijRCBAbacBAC (2) 矩阵与标量的乘法矩阵与标量的乘法).,(是是一一个个数数 nmijijRCAacAC (3) 矩阵与矩阵的乘法矩阵与矩阵的乘法).,(1pmpnnmnkkjikijRCRBRAbacABC (4) 转置矩阵转置矩阵.,jiijm

8、nTnmacRACRA (5) 单位矩阵单位矩阵 ,21nnnReeeI 其中其中., 2 , 1,)0 , 0 , 1 , 0 , 0(nkeTk (6) 非奇异矩阵非奇异矩阵.,IBAABRBAnn 且且若若则称则称B是是A的逆矩阵，记为的逆矩阵，记为A- -1，且，且(A- -1)T=(AT)- -1. 如如果果A- -1存在，则存在，则A称为非奇异矩阵称为非奇异矩阵. 如果如果A、B均为非均为非奇异矩阵，则有奇异矩阵，则有(AB)- -1=B- -1A- -1. (7) 矩阵的行列式矩阵的行列式), 2 , 1()det(1niAaAnjijij 设设ARnn，则，则A的行列式可按任一

9、行的行列式可按任一行(列列)展开展开,其中其中Aij为为aij的代数余子式，的代数余子式，Aij=(- -1)i+jMij，为，为Mij元元素素aij的余子式的余子式. 行列式性质行列式性质：.,),det()det()det()(nnRBABAABa .),det()det()(nnTRAAAb .,),det()det()(nnnRARcAccAc .0)det()(是是非非奇奇异异矩矩阵阵AAd 5.1.3 矩阵的特征值与谱半径矩阵的特征值与谱半径定义定义1设设A=(aij) Rnn，若存在数，若存在数 (实数或复数实数或复数)和非零向量和非零向量x=(x1,x2,xn)T Rn，使，使

10、 Ax= x, (1.1)则称则称 为为A的的特征值特征值, x为为A对应对应 的的特征向量特征向量, A的全体的全体特征值称为特征值称为A的的谱谱,记作记作(A),即即(A)= 1, 2, n.记记称为称为A的的谱半径谱半径.)2 . 1(,max)(1iniA 由由(1.1)式式 可知可使齐次线性方程组可知可使齐次线性方程组( I- -A)x=0有非零解，故系数行列式有非零解，故系数行列式det( I- -A)=0，记，记p( )称为矩阵称为矩阵A的的特征多项式特征多项式，方程，方程(1.3)称为称为A的的特征特征方程方程. 因为因为n次代数方程次代数方程p( )在复数域中有在复数域中有n

11、个根个根 1, 2, , n，故，故)3 . 1(. 0)det()(111212222111211 nnnnnnnnnncccaaaaaaaaaAIp ).()()(21np 由由(1.3)式中的行列式展开可得式中的行列式展开可得,1211 niiinac .det)1()1(21Acnnnn 故故A=(aij) Rnn的的n个特征值个特征值 1, 2, n是它的特征方是它的特征方程程(1.3)的的n个根，并有个根，并有)4 . 1(.det21nA )5 . 1(.11 niiniiiatrA 称称trA为为A的的迹迹.及及A的特征值的特征值 和特征向量和特征向量x还有以下性质：还有以下性

12、质： AT与与A有相同的特征值有相同的特征值 及特征向量及特征向量x. 若若A非奇异非奇异, 则则A- -1的特征值为的特征值为 - -1,特征向量为特征向量为x. 相似矩阵相似矩阵B=S- -1AS有相同的特征多项式有相同的特征多项式.例例1 求矩阵的特征值及谱半径求矩阵的特征值及谱半径.242422221 A解解 矩阵矩阵A的特征方程为的特征方程为. 0)7()2(242422221)det(2 AI得得A的特征值为的特征值为 1= 2=2, 3=7，谱半径，谱半径 (A)=7.5.1.4 特殊矩阵特殊矩阵 设设A=(aij)Rnn. (1) 对角矩阵对角矩阵 如果当如果当ij 时，时，a

13、ij =0. (2) 三对角矩阵三对角矩阵 如果当如果当|i- -j|1时，时，aij =0. (3) 上三角矩阵上三角矩阵 如果当如果当ij时，时，aij =0. (4) 上海森伯格上海森伯格(Hessenberg)矩阵矩阵 如果当如果当ij+1时，时，aij =0. (5) 对称矩阵对称矩阵 如果如果AT=A. (6) 埃尔米特埃尔米特(Hermit)矩阵矩阵 设设ACnn ，如果当，如果当AH =A(AH是是A的共轭转置矩阵的共轭转置矩阵). (7) 对称正定矩阵对称正定矩阵 如果如果AT =A且对任意非零向量，且对任意非零向量， xRn，(Ax, x)=xTAx0. (8) 正交矩阵正

14、交矩阵 如果如果A- -1=AT. (9) 酉矩阵酉矩阵 设设ACnn，如果，如果A- -1=AH. (10) 初等置换阵初等置换阵 由单位矩阵由单位矩阵I交换第交换第i行与第行与第j行行(或第或第i列与第列与第j列列)，得到的矩阵记为，得到的矩阵记为Iij，且，且. IijA=B(为交换为交换A第第i行与第行与第j行得到的矩阵行得到的矩阵)； AIij=C(为交换为交换A第第i列与第列与第j列得到的矩阵列得到的矩阵). (11) 置换阵置换阵 由初等置换阵的乘积得到的矩阵由初等置换阵的乘积得到的矩阵. 定理定理1 设设ARnn，则下述命题等价：，则下述命题等价： (1) 对任何对任何bRn，

15、方程组，方程组Ax=b有唯一解有唯一解. (2) 齐次方程组齐次方程组Ax=0只有唯一解零解只有唯一解零解x=0. (3) det(A)0. (4) A- -1存在存在. (5) A的秩的秩rank(A)=n. 定理定理2 设设ARnn为对称正定矩阵，则为对称正定矩阵，则 (1) A为非奇异矩阵，且为非奇异矩阵，且A- -1亦是对称正定矩阵亦是对称正定矩阵. (2) 设设Ak为为A的顺序主子阵，则的顺序主子阵，则Ak(k=1,2,n)亦亦是对称正定矩阵，其中是对称正定矩阵，其中 (3) A的特征值的特征值 i0 (i=1,2,n). (4) A的顺序主子式都大于零，即的顺序主子式都大于零，即A

16、k的行列式的行列式det(Ak)0 (k=1,2,n).)., 2 , 1(1111nkaaaaAkkkkk 定理定理3 设设ARnn为对称矩阵，如果为对称矩阵，如果det(Ak)0 (k=1,2, ,n)，或，或A的特征值的特征值 i0 (i=1,2,n)，则，则A为为对称正定矩阵对称正定矩阵. 有重特征值的矩阵不一定相似于对角矩阵，那有重特征值的矩阵不一定相似于对角矩阵，那么一般么一般n阶矩阵阶矩阵A在相似变换下能简化到什么形状在相似变换下能简化到什么形状. 定理定理4(Jordan标准型标准型) 设设A为为n阶矩阵，则存在阶矩阵，则存在一个非奇异一个非奇异n阶矩阵阶矩阵P使得使得.)()

17、()(22111 rrJJJAPP 为为若当若当(Jordan) 块块.), 2 , 1( 1.111)(1nnrinJriiinniiiiiiii 且且 其中其中 (1) 当当A的若当标准型中所有若当块的若当标准型中所有若当块Ji均为一阶均为一阶时，此标准型变为对角矩阵时，此标准型变为对角矩阵. (2) 如果如果A的特征值各不相同，则其若当标准型的特征值各不相同，则其若当标准型必为对角矩阵必为对角矩阵diag( 1, 2, n).5.2 高斯消去法高斯消去法 本节介绍高斯消去法本节介绍高斯消去法( (逐次消去法逐次消去法) )及消去法及消去法和矩阵三角分解之间的关系和矩阵三角分解之间的关系.

18、 . 虽然高斯消去法是一虽然高斯消去法是一种古老的求解线性方程组的方法种古老的求解线性方程组的方法( (早在公元前早在公元前250250年年我国就掌握了解方程组的消去法我国就掌握了解方程组的消去法) )，但由它改进、，但由它改进、变形得到的选主元素消去法、三角分解法仍然是目变形得到的选主元素消去法、三角分解法仍然是目前计算机上常用的有效方法前计算机上常用的有效方法. .我们在中学学过消去我们在中学学过消去法法, ,高斯消去法就是它的标准化的、适合在计算机高斯消去法就是它的标准化的、适合在计算机上自动计算的一种方法上自动计算的一种方法. .5.2.1 高斯消去法高斯消去法 设有线性方程组设有线性

19、方程组)1 . 2(.,22112222212111212111 mnmnmmnnnnbxaxaxabxaxaxabxaxaxa或写成矩阵形式或写成矩阵形式.2121212222111211 mnmnmmnnbbbxxxaaaaaaaaa简记为简记为Ax=b. nnnnnnnnbxubxuxubxuxuxu2222211212111,nnnnubx .,112111uxubxnjjj ,)1)(1()1(11 nnnnnnnuxubx解为解为 当当m=n时，对时，对三角形方程组三角形方程组的解非常容易的的解非常容易的.如如: 上三角矩阵上三角矩阵所对应的线性所对应的线性方程组方程组 nnnnn

20、nbylylylbylylbyl221122221211111,1111lby 下三角矩阵下三角矩阵所对所对应的线性方程组应的线性方程组,2212122lylby ,计算量（乘除法的主要部分）都为计算量（乘除法的主要部分）都为 n2/2.解为解为nnnjjjnnlylby 111 因此，我们将一般的线性方程组化成等价的三因此，我们将一般的线性方程组化成等价的三角形方程组来求解角形方程组来求解. 首先举一个简单的例子来说明消去法的基本思想首先举一个简单的例子来说明消去法的基本思想. 例例2 用消去法解线性方程组用消去法解线性方程组 )4 . 2(. 122)3 . 2(, 54)2 . 2(,

21、632132321xxxxxxxx 解解 第第1步，将方程步，将方程(2.2)乘上乘上- -2加到方程加到方程(2.4)上上去，消去去，消去(2.4)中的未知数中的未知数x1，得到，得到)5 . 2(.11432 xx 第第2步，将方程步，将方程(2.3) 加到方程加到方程(2.5)上去，消去上去，消去(2.5)中的未知数中的未知数x2，得到与原方程组等价的三角形，得到与原方程组等价的三角形方程组方程组 . 62)6 . 2(, 54, 6332321xxxxxx显然，方程组是显然，方程组是(2.6)是容易求解的，解为是容易求解的，解为.)3 , 2 , 1(Tx 上述过程相当于对方程的上述过

22、程相当于对方程的增广阵做初等行变换增广阵做初等行变换 6200514061111114051406111112251406111)(bA132rr 23rr 其中其中ri用表示矩阵的第用表示矩阵的第i行行. 由此看出，用消去法解方程组的由此看出，用消去法解方程组的基本思想基本思想是用是用逐次消去未知数的方法把原方程组逐次消去未知数的方法把原方程组Ax=b化为与其等化为与其等价的三角形方程组，而求解三角形方程组可用回代价的三角形方程组，而求解三角形方程组可用回代的方法求解的方法求解. 换句话说，上述过程就是换句话说，上述过程就是用初等行变用初等行变换将原方程组系数矩阵化为简单形式换将原方程组系数

23、矩阵化为简单形式(上三角矩阵上三角矩阵)，从而求解原方程组从而求解原方程组(2.1)的问题转化为求解简单方程的问题转化为求解简单方程组的问题组的问题. 或者说，对系数矩阵或者说，对系数矩阵A施行一些行变换施行一些行变换(用一些简单矩阵左乘用一些简单矩阵左乘A)将其约化为上三角矩阵将其约化为上三角矩阵. 这这就是就是高斯消去法高斯消去法. 下面讨论求解一般线性方程组的高斯消去法下面讨论求解一般线性方程组的高斯消去法.由由 mnmnmmnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 )1()1(2)1(21)1(1)1(2)1(22)1(221)1(21

24、)1(1)1(12)1(121)1(11mnmnmmnnnnbxaxaxabxaxaxabxaxaxa .2121212222111211 mnmnmmnnbbbxxxaaaaaaaaa .)1()1(2)1(121)1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11 mnmnmmnnbbbxxxaaaaaaaaa 将将(2.1)记为记为A(1)x=b(1)，其中，其中 )1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11)1(mnmmnnaaaaaaaaaA )1()1(2)1(1)1(mbbbb.212222111211 mnmmnnaa

25、aaaaaaa.21 mbbb (1) 第第1步步(k=1). .,)2()2(2)2(2)2(2)2(22)2(22)1(1)1(12)1(121)1(11mnmnmnnnnbxaxabxaxabxaxaxa 设设a11(1) 0，首先计算，首先计算乘数乘数 mi1= ai1(1) /a11(1) (i=2,3,m).用用- -mi1乘乘(2.1)的第一个方程，加到第的第一个方程，加到第i个个(i=2,3, ,m)方程上，消去方程上，消去(2.1)的从第二个方程到第的从第二个方程到第m个方程中的个方程中的未知数未知数x1，得到与，得到与(2.1)等价的方程组等价的方程组.00)2()2(2)

26、1(121)2()2(2)2(2)2(22)1(1)1(12)1(11 mnmnmnnbbbxxxaaaaaaa (2.7)简记为简记为 A(2)x=b(2)，其中其中A(2), b(2)的元素计算公式为的元素计算公式为 )., 2(), 2;, 2()1(11)1()2()1(11)1()2(mibmbbnjmiamaaiiijiijij (2) 第第k次消元次消元(k=1,2,s, s=min(m- -1,n). 设上述第设上述第1步，步， ，第，第k- -1步消元过程计算已经步消元过程计算已经完成，即已计算好与完成，即已计算好与(2.1)等价的方程组，简记为等价的方程组，简记为A(k)x

27、=b(k)，其中，其中)8 .2(.)()()2(2)1(121)()()2(2)1(1)()()2(2)2(22)1(1)1(12)1(11 kmkkmkkmnkknnnkmkkkkkkbbbbxxxxaaaaaaaaaaa 设设akk(k) 0，计算，计算乘数乘数 mik= aik(k) /akk(k) (i=k+1, ,m).用用- -mik乘乘(2.8)的第的第k个方程加到第个方程加到第 i个个(i= k+1, , m)方方程上，消去从第程上，消去从第k+1个方程到第个方程到第m个方程中的未知数个方程中的未知数xk，得到与，得到与(2.1)等价的方程组等价的方程组A(k+1)x=b(k

28、+1)，其中其中A(k+1), b(k+1)的元素计算公式为，的元素计算公式为， )9 . 2()., 1(), 1;, 1()()()1()()()1(mkibmbbnkjmkiamaakkikkikikkjikkijkij显然显然A(k+1)中从第中从第1行到第行到第k行与行与A(k)相同相同. (3) 继续上述过程，且设继续上述过程，且设aii(i) 0 (i=1,2, ,s)，直，直到完成第到完成第s步消元计算步消元计算. 最后得到与原方程组等价的最后得到与原方程组等价的简单方程组简单方程组A(s+1)x=b(s+1) ，其中，其中A(s+1)为上阶梯为上阶梯. 特别当特别当m=n时，

29、时，与原方程组等价的简单方程组为与原方程组等价的简单方程组为A(n)x=b(n)，即，即)10.2(.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11 nnnnnnnnbbbxxxaaaaaa由由(2.1)约化为约化为(2.10)的过程称为的过程称为消元过程消元过程. 如果如果A是非奇异矩阵，且是非奇异矩阵，且akk(k) 0 (k=1,2,n- -1)，求解三角形方程组求解三角形方程组(2.10)，得到求解公式，得到求解公式)11. 2().1 , 2, 1(/ )(,/)(1)()()()( nnkaxabxabxkkknkjjkkjkkknnnnnn(2.10)

30、的求解过程的求解过程(2.11) 称为称为回代过程回代过程. 注意：设注意：设Ax=b，其中，其中ARnn为非奇异矩阵，如为非奇异矩阵，如果果a11(1)=0，由于，由于A为非奇异矩阵，所以为非奇异矩阵，所以A的第的第1列一定列一定有元素不等于零，例如有元素不等于零，例如al1 0，于是可交换两行元素，于是可交换两行元素(即即r1rl)，将，将al1 调到调到(1,1)位置，然后进行消元计算，位置，然后进行消元计算，这时这时A(2)右下角矩阵为右下角矩阵为n- -1阶非奇异矩阵，继续这过阶非奇异矩阵，继续这过程，高斯消去法照样可进行计算程，高斯消去法照样可进行计算. 总结上述讨论即有总结上述讨

31、论即有 定理定理5 设设Ax=b，其中，其中ARnn. (1) 如果如果akk(k) 0 (k=1,2,n)，则可通过高斯消去，则可通过高斯消去法将法将Ax=b约化为等价的三角形方程组约化为等价的三角形方程组(2.10)，且计算，且计算公式为公式为 消元计算消元计算(k=1,2, ,n- -1) )., 1(), 1,(), 1(/)()()1()()()1()()(nkibmbbnkjiamaankiaamkkikkikikkjikkijkijkkkkikik 回代计算回代计算 ).1 , 2 , 1(/ )(,/)(1)()()()(nkaxabxabxnnnnkjjkkjkkknnnnn

32、n (2) 如果如果A为非奇异矩阵，则可通过高斯消去法为非奇异矩阵，则可通过高斯消去法(及交换两行的初等变换及交换两行的初等变换)将方程组将方程组Ax=b约化为等价的约化为等价的三角形方程组三角形方程组(2.10). 算法算法1(高斯算法高斯算法) 设设ARmn (m1), s=min(m- -1,n)，如果如果akk(k) 0 (k=1,2,s)，本算法用高斯方法将，本算法用高斯方法将A约化约化为上三角形矩阵，且为上三角形矩阵，且A(k)覆盖覆盖A，乘数，乘数mik覆盖覆盖aik. 对于对于 k=1,2, ,s (1) 如果如果akk=0，则计算停止；，则计算停止； (2) 对于对于i=k+

33、1, ,m (a) aikmik= aik/akk (b) 对于对于j=k+1, ,n aijaij- -mikakj . 显然，算法显然，算法1第第k步需要步需要m- -k次除法，次除法，(m- -k)(n- -k)次乘法，因此，本算法次乘法，因此，本算法(从第从第1步到第步到第s步消元计算总步消元计算总的计算量的计算量)大约需要大约需要s3/3- -(m- -k)s2/2+mns次乘法运算次乘法运算(对对相当大的相当大的s). 当当m=n时时, 总共大约需要总共大约需要n3/3次乘法运算次乘法运算. 数数akk(k)在高斯消去法中有着突出的作用，称为约在高斯消去法中有着突出的作用，称为约化

34、的化的主元素主元素(简称简称主元主元). 算法算法2(回代算法回代算法) 设设Ux=b，其中，其中U=(uij)Rnn为为非奇异上三角矩阵非奇异上三角矩阵，本算法计算，本算法计算Ux=b的解的解. 对于对于 i=n,n- -1, ,1 (1) xibi (2) 对于对于j=i+1, ,n xixi- -uijxj (in不算不算) (3) xi xi/uii 这个算法需要这个算法需要n(n-1-1)/2次乘除法运算次乘除法运算.例子例子 解方程组解方程组 02115472321321321xxxxxxxxx解解：消元：消元 0121111547112回代得回代得, 3263 x 3235 .

35、2rr 620033307112 5 . 35 . 05 . 203330711231212124rrrr , 233332 xx. 127321 xxx 高斯消去法对于某些简单的矩阵可能会失败，例如高斯消去法对于某些简单的矩阵可能会失败，例如.0110 A 由此，需要对算法由此，需要对算法1进行修改，首先研究原来矩阵进行修改，首先研究原来矩阵A在什么条件下才能保证在什么条件下才能保证akk(k) 0 (k=1,2, ,s). 下面的下面的定理给出了这个条件定理给出了这个条件. 定理定理6 约化的主元素约化的主元素aii(i) 0 (i=1,2,k)的充要条的充要条件是方阵件是方阵A的顺序主子

36、式的顺序主子式Di 0 (i=1,2,k)，即，即)12. 2()., 2 , 1(0, 01111111kiaaaaDaDiiiii 证明证明 首先利用归纳法证明首先利用归纳法证明充分性充分性. 显然显然, 当当k=1时，结论成立，假设结论对时，结论成立，假设结论对k- -1是成立的，对是成立的，对k由条件由条件设设Di 0 (i=1,2,k)，于是由归纳法假设我们有，于是由归纳法假设我们有aii(i) 0 (i=1,2,k- -1)，可用高斯消去法将，可用高斯消去法将A(1)约化到约化到A(k)，即，即.)()()2(2)1(1)()()2(2)2(22)1(1)1(12)1(11)()1

37、( knnkknnnknkkkkkkkaaaaaaaaaaaAA利用行列式的性质，我们有利用行列式的性质，我们有,0)2(22)1(11)2(22)1(12)1(112aaaaaD )13.2(.)()2(22)1(11)()1(1)1(11kkkkkkkkaaaaaaD 由条件有由条件有Di 0 (i=1,2,k)，利用，利用(2.13)式，则有式，则有aii(i) 0 (i=1,2,k)，定理，定理6的对的对k成立成立. 必要性必要性，由条件，由条件aii(i) 0 (i=1,2,k)，利用，利用(2.13)式式亦可推出亦可推出Di 0 (i=1,2,k). 定理定理6得证得证. ).,

38、3 , 2(/,1)(1)1(11nkDDaDakkkkk 推论推论 如果如果A的顺序主子式的顺序主子式Di 0 (i=1,2,n- -1), 则则5.2.2 矩阵的三角分解矩阵的三角分解 下面我们借助矩阵理论进一步对消去法做些分下面我们借助矩阵理论进一步对消去法做些分析，从而建立高斯消去法与矩阵因式分解的关系析，从而建立高斯消去法与矩阵因式分解的关系. 设设(2.1)的系数矩阵的系数矩阵ARnn的各顺序主子式均不的各顺序主子式均不为零，对于为零，对于A施行初等行变换相当于用初等矩阵左乘施行初等行变换相当于用初等矩阵左乘A，于是对，于是对(2.1)施行第施行第1次消元后化为次消元后化为(2.7

39、)，这时，这时A(1)化为化为A(2)，b(1)化为化为b(2)，即，即L1A(1) =A(2) , L1b(1)=b(2)，,10111211 nmmL其中其中.)2()2(2)1(1)2( nbbbb 一般第一般第k步消元，步消元，A(k)化为化为A(k+1)，b(k)化为化为b(k+1)，相当于相当于LkA(k) =A(k+1), Lkb(k)=b(k+1)，.1111, 1 knkkkmmL其中其中 重复以上过程，最后得到重复以上过程，最后得到;)()1(1221nnnAALLLL .)()1(1221nnnbbLLLL (2.14) 将上三角矩阵将上三角矩阵A(n)记为记为U，由，由

40、(2.14)得到得到.)(111211LUALLLAnn 其中其中,11111,21323121111211 nnnnnmmmmmmLLLL为单位下三角矩阵为单位下三角矩阵.,)() 1(, 1) 1(1, 1)2(2)2(1,2)2(22) 1(1) 1(1, 1) 1(12) 1(11)( nnnnnnnnnnnnnnaaaaaaaaaaAU 这就是说，这就是说，高斯消去法实质上产生了一个将高斯消去法实质上产生了一个将A分分解为解为两个三角形矩阵相乘的因式分解两个三角形矩阵相乘的因式分解，于是我们得到，于是我们得到如下重要定理，它在解方程组的直接法中起着重要作如下重要定理，它在解方程组的直

41、接法中起着重要作用用. 定理定理7(矩阵的矩阵的LU分解分解) 设设A为为n阶矩阵，如果阶矩阵，如果A的的顺序主子式顺序主子式Di 0 (i=1,2,n- -1)，则，则A可分解为一个单可分解为一个单位下三角矩阵位下三角矩阵L和一个上三角矩阵和一个上三角矩阵U的乘积，即的乘积，即A=LU,且且这种分解是唯一这种分解是唯一的的. 证明证明 根据以上根据以上高斯消去法的矩阵分析高斯消去法的矩阵分析，A=LU的存在性的存在性已经得到证明已经得到证明，现仅在，现仅在A为非奇异矩阵的假为非奇异矩阵的假定下来证明唯一性，当定下来证明唯一性，当A为奇异矩阵的情况留作练习，为奇异矩阵的情况留作练习，设设A有两

42、种分解为有两种分解为A=LU=L1U1，其中其中L, L1为单位下三角矩阵，为单位下三角矩阵，U, U1为上三角矩阵为上三角矩阵. 由于由于L- -1,U1- -1存在，故有存在，故有 L- -1L1=UU1- -1.上式右边为上三角矩阵，左边为单位下三角矩阵，从上式右边为上三角矩阵，左边为单位下三角矩阵，从而上式两边都必须等于单位矩阵而上式两边都必须等于单位矩阵I，故有，故有 L=L1，U=U1. 证毕证毕. 例例3 对于例对于例2，系数矩阵，系数矩阵,122140111 A由高斯消去法由高斯消去法 m21=0，m31=2，m32=- -1，故，故.200140111112010001LUA

43、 从而得到从而得到求矩阵行列式的计算公式求矩阵行列式的计算公式为为.)det()det(1)()()1(11)2(22)1(11 niiiinnnnnnaaaaaUA5.2.3 列主元消去法列主元消去法 由高斯消去法知道由高斯消去法知道, 在消元过程中可能有在消元过程中可能有akk(k)0的情况，这时消去法将无法进行；即使主元素的情况，这时消去法将无法进行；即使主元素akk(k) 0但很小时，用其作除数，会导致其它元素数量级的严但很小时，用其作除数，会导致其它元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠重增长和舍入误差的扩散，最后也使得计算解不可靠. 先看一个例子先看一个例子(

44、同时参看书上同时参看书上p148- -例例4). 高斯消去法也称高斯消去法也称主元素消去法主元素消去法 (条件条件det A 0) 即即当当akk(k)=0 时，高斯消元法时，高斯消元法无法进行无法进行；或；或 | akk(k) |0(i=1,2,n). 由矩阵乘法及由矩阵乘法及ljk=0(当当jk时时),得得,111jjijjkjkiknkjkikijlllllla 于是得到解对称正定方程组于是得到解对称正定方程组Ax=b的平方根法计算公式的平方根法计算公式 对于对于 j=1,2,n11221(1).(1,2, )(3.7)jjjjjjkklaljn 11(2).(1, );jijijikj

45、kjjklal llijn 求解求解Ax=b，即求解两个三角形方程组，即求解两个三角形方程组 Ly=b，求，求y ； LTx=y，求，求x.11(3).(1,2, ).(3.8)iiiikkiikybl ylin 1(4).(,1,1).niikikiik ixyl xlin n 由计算公式由计算公式(3.7)知知), 2 , 1(12njlajkjkjj 所以有所以有 ,max12jjnjjjjkaal 于是于是 .maxmax12,jjnjjkkjal 上面分析说明，分析过程中元素上面分析说明，分析过程中元素ljk的数量级不的数量级不会增长且对角元素会增长且对角元素ljj恒为正数恒为正数.

46、 于是有于是有 结论结论 不选主元素的平方根法是一个数值稳定的不选主元素的平方根法是一个数值稳定的方法方法. 当求出当求出L的第的第j列元素时，列元素时，LT的第的第j行元素亦算出行元素亦算出.所以平方根约需所以平方根约需n3/6次乘除法，大约为一般直接次乘除法，大约为一般直接LU分解法计算量的一半分解法计算量的一半. 例题例题 用平方根法求解对称正定方程组用平方根法求解对称正定方程组.25. 7645 . 375. 2175. 225. 41114321 xxx 解解 首先对首先对A进行进行Cholesky分解分解.1005 . 1205 . 05 . 0215 . 15 . 0025 .

47、0002 TLLA求解求解Ly=b，得，得 y1=2, y2=3.5, y3=1. 求解求解LTx=y，得，得 x1=1, x2=1, x3=1. 由公式由公式(3.7)看出，用平方根法解对称正定方程看出，用平方根法解对称正定方程组时，计算组时，计算L的元素的元素ljj需要用需要用到开方运算到开方运算. 为了避免为了避免开方开方，我们下面用，我们下面用定理定理10的分解式的分解式A=LDLT.1111112121212121 nnnnnTllldddlllLDLA即即 由矩阵乘法，并注意由矩阵乘法，并注意ljj=1,ljk=0(j1时时, aij=0, 且且 |b1|c1|0; |bi|ai|

48、+|ci|, ai,ci0, (i=2,3,n- -1). |bn|an|0. 我们利用矩阵的直接三角分解法来推导解三对我们利用矩阵的直接三角分解法来推导解三对角线方程组角线方程组(3.12)的计算公式的计算公式. 由系数阵由系数阵A的特点，的特点，可以将可以将A分解为两个三角矩阵的乘积，即分解为两个三角矩阵的乘积，即A=LU,其中取其中取L下三角阵下三角阵, 取取U为单位上三角阵为单位上三角阵, 这样求解这样求解方程组方程组Ax=f的方法称为的方法称为追赶法追赶法. 设设1122211111. (3.13)11nnnnn nnnnnbacbacbacbA11122211其中其中 为待定系数，

49、比较为待定系数，比较(3.13)两边即得两边即得 iii ,111,(2,3, ),(3.14)(1,2,1).iiiiiiiiibabincin 111111110c0,c /,01.bbb 由由 ，得得c0(1,2,1),(3.15)01,(3.14).iiiiin 即即而而由由可可求求出出下面我们用归纳法证明下面我们用归纳法证明(3.15)对对i=1是成立的是成立的. 现设现设(3.15)对对i- -1成立，求成立，求证对证对i亦成立亦成立.110.01.(3.14)iiiiiiiiiiibababac 也也就就是是由由得得到到);, 2(1niabiiii ).1, 2()/(1 ni

50、abciiiii .,分分解解的的实实现现了了我我们们完完全全确确定定了了的的假假设设条条件件由由这这就就是是说说LUAAiii 由归纳法假设由归纳法假设0| i- -1|1，又由，又由(3.15)及及A的假设的假设条件有条件有 求解求解Ax=f等价于求解两个三角形方程组等价于求解两个三角形方程组. Ly=f, 求求y; Ux=y, 求求x.从而得到解三对角线方程组的从而得到解三对角线方程组的追赶法公式追赶法公式.,/111bc ,/111bfy ).1, 3 , 2()/(1 niabciiiii (2).Lyf 解解)., 3 , 2()/()(11niabyafyiiiiiii (1).

51、 计算计算 i, i的递推公式的递推公式);, 2(1niabiiii ,nnyx (3).Uxy 解解).1 , 2 , 1(1 nixyxiiii 我们将计算系数我们将计算系数 及及 的的过程称为过程称为追的过程追的过程, 将计算方程组的解将计算方程组的解 的过程称为的过程称为赶的过程赶的过程. 合起来就是合起来就是追赶法追赶法.121 n nyyy2111xxxnn 追赶法公式实际上就是把高斯消去法用到求解追赶法公式实际上就是把高斯消去法用到求解三对角线方程组上去的结果三对角线方程组上去的结果. 这时由于这时由于A特别简单特别简单, 因此使得求解的计算公式非常简单因此使得求解的计算公式非

52、常简单,而且计算量仅为而且计算量仅为5n- -4次乘除法次乘除法,而另外增加一个方程组而另外增加一个方程组Ax=f2仅增加仅增加3n- -2次乘除法运算次乘除法运算,易见追赶法的计算量是比较小的易见追赶法的计算量是比较小的. 总结上述讨论有下面定理总结上述讨论有下面定理 定理定理11 设有三对角线方程组设有三对角线方程组Ax=f, 其中其中A满足条满足条件件(1), (2), (3), 则则A为非奇异矩阵且追赶法计算公式中为非奇异矩阵且追赶法计算公式中的的 i, i满足满足(1) 01 (1,2,1);iin (2) 0(2,3,1);0.iiiiiinnnnncbabainbaba 由定理由

53、定理11的的(1), (2)说明追赶法计算公式中不会说明追赶法计算公式中不会出现中间结果数量级的巨大增长和舍入误差的严重出现中间结果数量级的巨大增长和舍入误差的严重累积累积.5.4 向量和矩阵的范数向量和矩阵的范数5.4.1 向量范数向量范数 为了研究线性方程组近似解的误差估计和迭代为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对向量法的收敛性，我们需要对向量 x 的的“大小大小”及矩阵及矩阵A的的“大小大小”引进某种度量引进某种度量范数范数. 本节介绍本节介绍n维向维向量范数和量范数和nn矩阵的范数矩阵的范数. 向量范数是三维欧氏空向量范数是三维欧氏空间中向量长度概念的推广，在

54、数值分析中起着重要间中向量长度概念的推广，在数值分析中起着重要作用作用. 首先将向量长度概念推广到首先将向量长度概念推广到Rn(或或Cn)中中.),(),(11 niiiHniiiTyxxyyxyxxyyx或或复复数数称为向量称为向量x, y的的数量积数量积(内积内积). 将非负实数将非负实数,),(122 niixxxx221( , ),niixx xx 或或复复向向量量称为向量称为向量x的的欧氏范数欧氏范数. 定义定义2 设设x=(x1,x2,xn)T, y= (y1,y2,yn)T Rn , 将实数将实数 下面定理可在线性代数书中找到下面定理可在线性代数书中找到. 定理定理12 设设x,

55、 y Rn (或或Cn), 则则 (1). (x, x)=0, 当且仅当当且仅当x=0时成立时成立;_(3).( , )( , )( , )( , );x yy xx yy x 或或1212(4).(, )(, )(, );xxyxyxy 222(6).xyxy 三三角角不不等等式式( ,)( , ),xyx y 或或 (2). ( x, y)= (x, y), 为实数为实数 为复数为复数)22(5). ()|( , )|,x yxy高高斯斯施施瓦瓦茨茨不不等等式式等式当且仅当等式当且仅当x与与y线性相关时成立；线性相关时成立； 我们还可以用其他办法来度量我们还可以用其他办法来度量Rn中向量的

56、中向量的“大大小小”. 例如例如, 对于对于x=(x1,x2, xn)T Rn, 可以用一个可以用一个x的函数的函数N(x)=max|xi|来度量来度量 x 的的“大小大小”, 而且这种而且这种度量度量 x 的的“大小大小”的方法计算起来比欧氏范数方便的方法计算起来比欧氏范数方便. 在许多应用中在许多应用中, 对度量对度量x的的“大小大小”的函数的函数N(x)都要都要求是求是正定的正定的、齐次的、齐次的且且满足三角不等式满足三角不等式. . 下面我们下面我们给出向量范数的一般定义给出向量范数的一般定义. . (1) |x| 0(|x|=0当且仅当当且仅当x=0) (正定性正定性), (2) |

57、 x|=| | |x|, 对任何对任何 R(或或 C)(齐次性齐次性), (3) |x+y| |x|+|y| (三角不等式三角不等式). (4.1)则称则称N(x)=|x|是是Rn(或或Cn)上的一个上的一个向量范数向量范数(或或模模). 定义定义3(向量的范数向量的范数) 如果向量如果向量x Rn(或或Cn)的某个的某个实值函数实值函数N(x)=|x|，满足条件，满足条件: 由由(3)可推出不等式可推出不等式. (4) | |x|- -|y| | |x- -y|. (4.2) 下面给出几种下面给出几种常用的向量范数常用的向量范数, 设设x=(x1,x2,xn)T.1(1).max.ii nx

58、x 11(2).niixx 1122221(3).( , ).niixx xx 容易证明前三种范数是的容易证明前三种范数是的p- -范数范数特殊情况特殊情况, 其中其中向量的向量的 - -范数范数(最大范数最大范数)向量的向量的1- -范数范数11(4).nppipixx 向量的向量的p- -范数范数(1 p0, 使得对一切使得对一切x Rn有有.21stsxcxxc 证明证明 只要就只要就|x|s=|x|证明上式成立即可证明上式成立即可, 即证即证明存在常数明存在常数c1,c20, 使得使得. 0,21 xRxcxxcnt且且对一切对一切 考虑考虑n元函数元函数., 0)(ntRxxxf 记

59、记S=x|x|=1, x Rn, 则则S是一个有界闭集是一个有界闭集. 由于由于f(x)为为S上的连续函数上的连续函数, 所以所以f(x)于于S上达到最大值和最小上达到最大值和最小值值, 即存在即存在x , x S使得使得.)(max)(,)(min)(21cxfxfcxfxfSxSx 设设x Rn且且x0, 则则x/|x| S, 从而有从而有.,2121cxxccxxfct 即为即为即即.,21ntRxxcxxc 对一切对一切 可以证明常用范数满足下述关系可以证明常用范数满足下述关系.,21 xnxxxnxx以及以及.1,12211xxxnxxxn 注意注意 定理定理14不能推广到无穷维空间

60、不能推广到无穷维空间. 由定理由定理14可可得得结论结论: 如果在一种范数意义下向量序列收敛时如果在一种范数意义下向量序列收敛时, 则则在任何一种范数意义下该向量序列均收敛在任何一种范数意义下该向量序列均收敛. 定理定理15 , 其中其中|为向为向量的任一种范数量的任一种范数.0limlim)()( xxxxkkkk, 0limlim)()( xxxxkkkk 证明证明 显然显然, 而对于而对于Rn上任一种范数上任一种范数|, 由定理由定理14, 存在常数存在常数c1,c20, 使使. 0lim0lim)()( xxxxkkkk,)(2)()(1 xxcxxxxckkk于是又有于是又有5.4.