第5章 解线性方程组的直接方法.ppt

1、1 引言与预备知识,第5章 解线性代数方程组的直接法,一、引言,线性方程组的来源,线性方程组的分类：直接法，迭代法。,线性方程组的两类解法： 1、直接法：就是经过有限步算数运算，可求得线性方程组精确解的方法（若计算过程中没有舍入误差）。低阶稠密的线性方程组用直接法(如高斯消去法和三角分解法)。 2、迭代法：就是用某种极限过程去逐步逼近线性方程组精确解的方法。大型稀疏矩阵方程组(n很大,且零元素很多.如偏微方程数值解产生的线性方程组,n104)一般用迭代法。,二、向量和矩阵,三、特殊矩阵,设A=（aij） Rnn . 对角矩阵 如果当ij时，aij=0. 三对角矩阵 如果当|i-j|1时，aij

2、=0. 上三角矩阵 如果当i j时，aij=0. 上海森伯(Hessenberg)阵 如果当i j+1时，aij=0. 对称矩阵 如果AT = A 埃尔米特矩阵 设ACnn ,如果AH=A（AH=AT ，即为A的共轭转置） 对称正定矩阵 如果AT =A，对任意非零向量Rn, (A,)=T A 0. 正交矩阵 如果A-1=AT . 酉矩阵 设ACnn ,如果A-1=AH .,-,10) 初等置换阵 由单位矩阵I交换第i行与第j行（或交换第i列与第j列），得到的矩阵记为Iij,且 IijA=A（为交换A第i行与第j行得到的矩阵）； AIij=B（为交换A第i列与第j列得到的矩阵）。 11) 置换阵

3、 由初等置换阵的乘积得到的矩阵.,定理1 设ARnn, 则下述命题等价: 对任何b Rn ，方程组A=b有唯一解. 齐次方程组A=0只有唯一解=0. det(A) 0. A-1存在 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的顺序主子式都大于零，即det(Ak) 0(k=1,2,n),定理3 若ARnn 为对称矩阵.如果det(Ak) 0(k=1,2,n),或A得特征值i0（i=1,2

4、, ,n ）.则A为对称正定矩阵。 有重特征值的矩阵不一定相似于对角矩阵，那么一般n阶矩阵A在相似变换下能简化到什么形状？,定理4(若尔当（Jordan）标准型） 设A为n阶矩阵，则存在一个非奇异矩阵P使得,为若尔当块. 1）当A的若尔当标准形中所有若尔当块Ji均为一阶时，此标准型变成对角矩阵； 2）如果A的特征值各不相同，则其若尔当标准型必为对角矩阵diag（1 2 n）.,2 高斯消去法,一、高斯消去法,设有线性方程组：AX=b （2.1）,首先举一个例子来说明消去法的基本思路 例2 用消去法解线性方程组,解 第1步.将方程（2.2）乘上-2加到方程（2.4）式中的未知数X1，得到 4X2

5、X3=11. (2.5) 第2步. 将方程（2.3）加到方程（2.5）上去，消去（2.5）中的未知数X2。得到与原方程组等价的三角形线性方程组,显然，线性方程组（2.6）是容易求解的，解为,这里（-2）r1+r3r3,r2+r3r3,其中用ri表示矩阵的第i行,由此看出，用消去法解线性方程组的基本思想是用逐次消去 未知数的方法把原线性方程组AX=b化为与其等价的三角形线性 方程组，从而求解三角形线性方程组可用回代的方法求解。 下面我们讨论求解一般线性方程组的高斯消去法。 将方程组AX=b 记为A（1）X=b（1） .其中 A（1） =（aij (1)）=(aij), b(1)=b.,（1）消元

6、过程,简记为 A（2）X=b（2） ， 其中A（2），b（2）的元素计算公式为,第1步：设,首先计算乘数,用mi1乘（2.1）的第1个方程组，加到第i个中，消去方程组（2.1）的从第2个方程到第n个方程中的未知数X1，得到与方程组（2.1）等价的线性方程组,第k步：若,用,乘第k行,加到第i行中，得到,简记为,A（k）X=b（k） ，,同理可得,继续上述过程，且设akk(k) 0(k=1,2,n-1),直到完成第n-1步消元计算，最后得到,由方程组（2.1）约化为方程组（2.10）的过程称为消元过程,若ARnn是非奇异矩阵，,则由（2.10）得到,这个过程称为回代过程.,（2）回代过程,说明:

7、 若线性方程组的系数矩阵非奇异，则它总可以通过带行交换的高斯消去法进行求解。,定理5 设A=b,其中ARnn . (1)如果,则可以通过高斯消去法将Ax=b约化为,(2)如果系数矩阵A非奇异，总可以通过带行交换的高斯消去法进行求解。,但是，高斯消去法对于某些简单的矩阵可能会失败,比如:,由此需要对前述的算法进行修改，首先研究原来矩阵A在什么条件下才能保证,等价的三角线性方程组（2.10）求解.,下面的定理给出了这个条件。,证明 首先利用归纳法证明定理6的充分性.显然,当k=1时,定理6成立,现设定理6充分性对k-1是成立的,求证定理6充分性对k亦成立.设Di0（i=1,2,k）,于是由归纳法假

8、设aii(i) 0(i=1,2,k-1),可用高斯消去法将A（1）约化到A（k）,即,(2.13),由设Di0 （i=1,2,k）,利用（2.13）式，则有akk(k) 0 ,由定理6充分性对k亦成立. 显然,由假设aii(i) 0 (i=1,2,k),利用(2.13)式亦可推出Di0(i=1,2,k).,二、矩阵的三角分解,下面建立高斯消去法与矩阵的因式分解的关系.设方程组Ax=b的系数矩阵A的各顺序主子式均不为0.由于对A施行行的初等变换相当于用初等矩阵左乘A.,从而我们可以知道，高斯消去法实质是将A分解为两个三角矩阵的相乘的因式分解，于是有如下重要定理。,3 高斯主元素消去法,例4 采用

9、3位十进制，用消元法求解,解法1：,解法2：,全主元消去法;列主元消去法.,一、列主元消去法,设有线性方程组：AX=b,第一步:先在A的第一列选取绝对值最大的元素作主元素,然后交换其增广矩阵的第1行和第i1行(当i11时),再进行第1次消元.得到,重复上述过程，设已完成第k-1步的选主元素，交换两行及消元计算， 约化为,其中A（k）的元素仍记为aij，b(k)的元素仍记为b.,第k步选主元素(在A（k）右下角方阵的第1列内选),即确定ik，使,然后交换第k行和第ik （k=1,2,n-1）行(当ikk时),再进行第k次消 元.,最后将原线性方程组化为,回代求解,算法(列主元消去法). 设AX=

10、b，本算法用A得具有行交换的列主元素消去法，消元结果冲掉A，乘数mij冲掉aij，计算解X冲掉常数项b，行列式存放在det中. 1.det1 2.对于k=1,2,n-1 (1) 按列选主元 (2)如果aik,k=0,则计算停止（det（A）=0） (3)如果ik=k则转（4） 换行：akjaik.j(j=k,k+1,n) , bk bik , det -det (4)消元计算 对于i=k+1,n aik mik=aik/akk 对于j=k+1,n aij aij-mik*akj bi bi-mik*bk,(5)detakk*det 3.如果ann=0，则计算停止（det（A）=0） 4.回代求

11、解 (1)bn bn/ann (2)对于i=n-1,2,1,5.detann*det,下面用矩阵描述列主元消去法,二、高斯若当消去法,算法(高斯若当消元法).,例4 采用高斯若当消去法求矩阵,的逆A-1 .,4 矩阵的三角分解法,设有线性方程组：AX=b,一、直接三角分解法,1、不选主元三角分解算法 当A非奇异时，由不需选主元的顺序高斯消去法知,就有,不选主元的三角分解算法：,于是，可以通过求解两个三角形方程组,得到原方程组的解,求解方程组计算公式:,说明: 上面方法称为杜利特尔（Doolittle）分解方法,练习,利用LU(Doolittle)分解法求解方程组,克劳特分解方法 设A为nn阶非

12、奇异矩阵,且各阶主子矩阵为非奇异,则矩 阵A的克劳特(Crout)分解为 A=LU 其中,这样,L、U中的元素都已求出。计算L的各列与U的各行的次序如图所示 。,图,对方程组Ax=b的系数矩阵A作出LU分解后,方程组便化为 LUx=b 则求解上列方程组就化为依次解方程组 Ly=b Ux=y 由于L为下三角矩阵,U为单位上三角矩阵,故上述方程组的求解极为方便。他们的计算公式分别为,用克劳特分解求解线性方程组Ax=b的计算过程为: LU分解过程:对于k=1,2,n依次计算,例4 用克劳特分解方法求解下列方程组,解 令,利用矩阵乘法可得到,这样原方程组就化为依次求下列两个三角形方程组,代入第二个方程

13、组可求得原方程组的解为,2、选主元直接三角分解法,从直接三角分解公式可看出当 时计算将中断，或者当 绝对值很小时，按分解公式计算可能引起舍入误差的累积。但如果当A非奇异，我们可以通过交换A的行实现矩阵PA的LU分解.因此可采用与列主元消去法类似的方法，将直接三角分解法修改为（部分）选主元的三角分解法。,5 向量和矩阵的范数,为了研究线性方程组的近似解的误差估计和迭代法的收敛性, 我 们需要对Rn中的向量(或Rnn中的矩阵)的“大小”引进某种度量向 量(或矩阵)的范数.,首先考虑Rn中向量的长度, 然后可定义向量(或矩阵)的范数.,定义1 设=( 1, 2, , n)T， =( 1, 2, ,

14、n)T Rn . 将实数(, )= T = 1 1+ 2 2+ + n n（或复 数(, )= H = ）,称为向量, 的数量积.并将非负实,数| |2 = (, )1/2 = 称 为向量的欧氏范数.,(1) 正定性：,等号当且仅当,时成立；,(2) 齐次性：,(3) 三角不等式：,则称,为向量,的范数或模.,由(3)得,(4),几种常用范数,(无穷范数),(1-范数),(2-范数),(p-范数),可以验证它们都是范数. 易见前三种范数是p-范数的特殊情况,例6 计算向量,的几种常用范数,证明 设,只需证明当xy时N（x） N（y）即成.事实上,证明 只要就s=证明上式成立即可，即证明存在常数

15、c1,c20,使,考虑函数 f(x)=xt0, xRn .,记S=x|x1,xRn,则S是一个有界闭集。由于f(x)为S上的连续函数，所以f(x)于S上达到最大最小值，即存在x,x” S使得,设x Rn 且x0,则,显然c1,c20,上式为,定义4(矩阵的范数),(1) 正定性：,等号当且仅当,时成立；,(2) 齐次性：,(3) 三角不等式：,则称,为 矩阵,的范数或模。,显然这种矩阵的范数Av依赖于向量范数xv的具体含义。也就是说，当给出一种具体的向量范数xv时，相应地就得到了一种矩阵范数Av,诱导出的常用范数有：,它们满足如下相容关系：,例7 计算矩阵,的几种常用范数,证明 用反证法。若d

16、et（IB）=0,则（IB）X=0有非零解， 即存在X00使BX0=X0,故B1，与假设矛盾，又由,(IB)（I B）-1 =I，有,（I B）-1=I+B （I B）-1 ，,从而,（I B）-1 I+B （I B）-1 （I B）-1 ,6 误差分析,一、矩阵的条件数,考虑线性方程组 AX=b 系数矩阵A和右端b的小扰动所产生的相对误差.,例8 方程组,准确解为,常数项微小变化后,准确解,定义7 如果矩阵A或常数项b的微小变化,引起线性方程组AX=b的解的巨大变化,则称此方程组为病态方程组矩阵A称为病态矩阵,否则称方程组为良态方程组,矩阵A为良态矩阵.,条件数刻画了线性方程组AX=b的解对数据误差的灵敏程度，它只与此方程组的系数有关，反映了方程组固有的本性。故可用条件数来描述方程组的性态.,例9 求Hilbert矩阵H3的条件数.,注：一般判断矩阵是否病态，并不计算A1，而由经验得出。 行列式很大或很小（如某些行、列近似相关）； 元素间相差大数量级，且