《解线性方程组的直接方法 (2)精选文档.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的直接方法 (2)精选文档.ppt（80页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、解线性方程组的直接解线性方程组的直接方法方法本讲稿第一页，共八十页二、向量和矩阵二、向量和矩阵本讲稿第二页，共八十页本讲稿第三页，共八十页三、特殊矩阵三、特殊矩阵设A A=（aij）Rnn .对角矩阵 如果当ij时，aij=0.三对角矩阵 如果当|i-j|1时，aij=0.上三角矩阵 如果当i j时，aij=0.上海森伯(Hessenberg)阵 如果当i j+1时，aij=0.对称矩阵 如果A AT=A A埃尔米特矩阵 设A ACnn,如果AH=A（AH=AT，即为A的共轭转置）对称正定矩阵 如果AT=A，对任意非零向量Rn,(A,)=T A 0.正交矩阵 如果A-1=AT.酉矩阵 设A A
2、Cnn,如果A-1=AH.-本讲稿第四页，共八十页10)初等置换阵 由单位矩阵I I交换第i行与第j行（或交换第i列与第j列），得到的矩阵记为I Iij,且 I IijA A=A A（为交换A A第i行与第j行得到的矩阵）；AIAIij=B=B（为交换A A第i列与第j列得到的矩阵）。11)置换阵 由初等置换阵的乘积得到的矩阵.定理定理1 设ARnn,则下述命题等价:(1)对任何b Rn，方程组A=b有唯一解.(2)齐次方程组A=0只有唯一解=0.(3)det(A)0.(4)A-1存在(5)A的秩rank(A)=n本讲稿第五页，共八十页定理定理2 若ARnn 为对称正定矩阵，则(1)A A为非
3、奇异矩阵，且A-1亦是对称正定矩阵.(2)记A Ak为A A的顺序主子阵，则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,n）.则A为对称正定矩阵。有重特征值的矩阵不一定相似于对角矩阵，那么一般n阶矩阵A在相似变换下能简化到什么形状？定理定理4(若尔当（Jordan）标准型）设A为n阶矩阵，则存在一个非奇异矩阵P使得本讲稿第七页，共八十页为若尔当块.1）当A A
4、的若尔当标准形中所有若尔当块Ji均为一阶时，此标准型变成对角矩阵；2）如果A A的特征值各不相同，则其若尔当标准型必为对角矩阵diag（1 2 n）.本讲稿第八页，共八十页2 2 高斯消去法高斯消去法一、高斯消去法一、高斯消去法设有线性方程组：AXAX=b b （2.12.1）首先举一个例子来说明消去法的基本思路例例2 2 用消去法解线性方程组本讲稿第九页，共八十页解 第1步.将方程（2.2）乘上-2加到方程（2.4）式中的未知数X1，得到 4X2X3=11.(2.5)第2步.将方程（2.3）加到方程（2.5）上去，消去（2.5）中的未知数X2。得到与原方程组等价的三角形线性方程组显然，线性方
5、程组（2.6）是容易求解的，解为这里（-2）r1+r3r3,r2+r3r3,其中用ri表示矩阵的第i行本讲稿第十页，共八十页 由此看出，用消去法解线性方程组的基本思想是用逐次消去未知数的方法把原线性方程组AX=b化为与其等价的三角形线性方程组，从而求解三角形线性方程组可用回代的方法求解。下面我们讨论求解一般线性方程组的高斯消去法。将方程组AXAX=b b 记为A A（1 1）X X=b b（1 1）.其中 A A（1 1）=（a aij ij(1)(1)）=(a=(aijij),b),b(1)(1)=b.=b.本讲稿第十一页，共八十页（1）消元过程 简记为 A A（2 2）X X=b b（2
6、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 5 设A=b,其中ARnn.(1)如果则可以通过高斯消去法将Ax=b约化为(2)如果系数矩阵A A非奇异，总可以通过带行交换的高斯消去法进行求解。但是，高斯消去法对于某些简单的矩阵可能会失败,比如:由此需要对前述的算法进行修改，首先研究原来矩阵A A在什么条件下才能保证等价的三角线性方程组（2.10）求解.下面的定理给出了这个条件。本讲稿第十五页，共八十页证明 首先利用归纳法证明定理6的充分性.显然,当k=1时,定理6成立,现设定理6充分性对k-1是成立的,求证定理6充分性对k亦成立.设Di0（i=
8、1,2,k）,于是由归纳法假设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.本讲稿第十九页，共八十页本讲稿第二
9、十页，共八十页 从而我们可以知道，高斯消去法实质是将A分解为两个三角矩阵的相乘的因式分解，于是有如下重要定理。本讲稿第二十一页，共八十页本讲稿第二十二页，共八十页本讲稿第二十三页，共八十页3 3 高斯主元素消去法高斯主元素消去法例例4 4 采用3位十进制，用消元法求解 解法解法1：本讲稿第二十四页，共八十页解法解法2：全主元消去法;列主元消去法.本讲稿第二十五页，共八十页一、列主元消去法一、列主元消去法设有线性方程组：AX=b第一步:先在A A的第一列选取绝对值最大的元素作主元素,然后交换其增广矩阵的第1行和第i1行(当i11时),再进行第1次消元.得到本讲稿第二十六页，共八十页重复上述过程，
10、设已完成第k-1步的选主元素，交换两行及消元计算，约化为其中A（k）的元素仍记为aij，b(k)的元素仍记为b.第k步选主元素(在A（k）右下角方阵的第1列内选),即确定ik，使然后交换第k行和第ik（k=1,2,n-1）行(当ikk时),再进行第k次消元.本讲稿第二十七页，共八十页最后将原线性方程组化为回代求解本讲稿第二十八页，共八十页算法算法(列主元消去法).设AX=b，本算法用A得具有行交换的列主元素消去法，消元结果冲掉A，乘数mij冲掉aij，计算解X冲掉常数项b，行列式存放在det中.1.det12.对于k=1,2,n-1 (1)按列选主元 (2)如果aik,k=0,则计算停止（de
11、t（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*det3.如果ann=0，则计算停止（det（A）=0）4.回代求解 (1)bn bn/ann(2)对于i=n-1,2,15.detann*det本讲稿第三十页，共八十页下面用矩阵描述列主元消去法本讲稿第三十一页，共八十页本讲稿第三十二页，共八十页二、高斯二、高斯若当消去法若当消去法本讲稿第
12、三十三页，共八十页算法算法(高斯高斯若当消元法若当消元法).本讲稿第三十四页，共八十页本讲稿第三十五页，共八十页例例4 4 采用高斯若当消去法求矩阵的逆A-1.本讲稿第三十六页，共八十页4 4 矩阵的三角分解法矩阵的三角分解法设有线性方程组：AX=bAX=b一、直接三角分解法一、直接三角分解法1 1、不选主元三角分解算法、不选主元三角分解算法当A A非奇异时，由不需选主元的顺序高斯消去法知本讲稿第三十七页，共八十页就有,不选主元的三角分解算法不选主元的三角分解算法：本讲稿第三十八页，共八十页于是，可以通过求解两个三角形方程组得到原方程组的解,求解方程组计算公式求解方程组计算公式:说明说明:上面
13、方法称为杜利特尔（Doolittle）分解方法本讲稿第三十九页，共八十页练习练习利用LU(Doolittle)分解法求解方程组本讲稿第四十页，共八十页 克劳特分解方法 设A为nn阶非奇异矩阵,且各阶主子矩阵为非奇异,则矩阵A的克劳特(Crout)分解为 A=LU 其中本讲稿第四十一页，共八十页本讲稿第四十二页，共八十页 这样,L、U中的元素都已求出。计算L的各列与U的各行的次序如图所示。图 本讲稿第四十三页，共八十页 对方程组Ax=b的系数矩阵A作出LU分解后,方程组便化为 LUx=b 则求解上列方程组就化为依次解方程组 Ly=b Ux=y 由于L为下三角矩阵,U为单位上三角矩阵,故上述方程组
14、的求解极为方便。他们的计算公式分别为本讲稿第四十四页，共八十页 用克劳特分解求解线性方程组Ax=b的计算过程为:LU分解过程:对于k=1,2,n依次计算本讲稿第四十五页，共八十页本讲稿第四十六页，共八十页 例4 用克劳特分解方法求解下列方程组解 令 本讲稿第四十七页，共八十页 利用矩阵乘法可得到 本讲稿第四十八页，共八十页 这样原方程组就化为依次求下列两个三角形方程组代入第二个方程组可求得原方程组的解为 本讲稿第四十九页，共八十页2、选主元选主元直接三角分解法直接三角分解法从直接三角分解公式可看出当 时计算将中断，或者当 绝对值很小时，按分解公式计算可能引起舍入误差的累积。但如果当A非奇异，我
15、们可以通过交换A的行实现矩阵PA的LU分解.因此可采用与列主元消去法类似的方法，将直接三角分解法修改为（部分）选主元的三角分解法。本讲稿第五十页，共八十页5 5 向量和矩阵的范数向量和矩阵的范数 为了研究线性方程组的近似解的误差估计和迭代法的收敛性,我们需要对Rn中的向量(或Rnn中的矩阵)的“大小”引进某种度量向量(或矩阵)的范数.首先考虑Rn中向量的长度,然后可定义向量(或矩阵)的范数.定义定义1 1 设设=(1,2,n)T，=(1,2,n)T Rn.将实数(,)=T =1 1+2 2+n n（或复数(,)=H =）称为向量,的数量积.并将非负实数|2=(,)1/2=称 为向量的欧氏范数.
16、本讲稿第五十一页，共八十页本讲稿第五十二页，共八十页(1)正定性：等号当且仅当时成立；(2)齐次性：(3)三角不等式：则称为向量的范数范数或模模.由(3)得(4)本讲稿第五十三页，共八十页几种常用范数(无穷范数)(1-范数)(2-范数)(p-范数)可以验证它们都是范数.易见前三种范数是p-范数的特殊情况例例6 6 计算向量的几种常用范数本讲稿第五十四页，共八十页证明证明 设只需证明当xy时N（x）N（y）即成.事实上本讲稿第五十五页，共八十页本讲稿第五十六页，共八十页证明证明 只要就s=证明上式成立即可，即证明存在常数c1,c20,使考虑函数 f(x)=xt0,xRn.记S=x|x1,xRn,
17、则S是一个有界闭集。由于f(x)为S上的连续函数，所以f(x)于S上达到最大最小值，即存在x,x”S使得设x Rn 且x0,则显然c1,c20,上式为本讲稿第五十七页，共八十页本讲稿第五十八页，共八十页本讲稿第五十九页，共八十页定义定义4 4(矩阵的范数)(1)正定性：等号当且仅当时成立；(2)齐次性：(3)三角不等式：则称为 矩阵的范数范数或模模。本讲稿第六十页，共八十页本讲稿第六十一页，共八十页显然这种矩阵的范数Av依赖于向量范数xv的具体含义。也就是说，当给出一种具体的向量范数xv时，相应地就得到了一种矩阵范数Av本讲稿第六十二页，共八十页诱导出的常用范数有：它们满足如下相容关系：例例7
18、 7 计算矩阵的几种常用范数本讲稿第六十三页，共八十页本讲稿第六十四页，共八十页本讲稿第六十五页，共八十页证明 用反证法。若det（I IB B）=0,则（I IB B）X=0有非零解，即存在X00使B BX0=X0,故B1，与假设矛盾，又由(I IB B)（I I B B）-1=I I，有（I I B B）-1=I I+B B（I I B B）-1，从而（I I B B）-1 I I+B B（I I B B）-1（I I B B）-1 本讲稿第六十六页，共八十页6 6 误差分析误差分析一、矩阵的条件数一、矩阵的条件数考虑线性方程组 AX=b 系数矩阵A和右端b的小扰动所产生的相对误差.例例8
19、 8 方程组准确解为常数项微小变化后准确解本讲稿第六十七页，共八十页定义定义7 7 如果矩阵A或常数项b的微小变化,引起线性方程组AX=b的解的巨大变化,则称此方程组为病态方程组矩阵A称为病态矩阵,否则称方程组为良态方程组,矩阵A为良态矩阵.本讲稿第六十八页，共八十页本讲稿第六十九页，共八十页 条件数刻画了线性方程组AX=b的解对数据误差的灵敏程度，它只与此方程组的系数有关，反映了方程组固有的本性。故可用条件数来描述方程组的性态.本讲稿第七十页，共八十页本讲稿第七十一页，共八十页本讲稿第七十二页，共八十页例例9 9 求Hilbert矩阵H3的条件数.本讲稿第七十三页，共八十页注：注：一般判断矩
20、阵是否病态，并不计算一般判断矩阵是否病态，并不计算A 1，而由经验，而由经验得出。得出。行列式很大或很小（如某些行、列近似相关）；行列式很大或很小（如某些行、列近似相关）；元素间相差大数量级，且无规则；元素间相差大数量级，且无规则；主元消去过程中出现小主元；主元消去过程中出现小主元；特征值相差大数量级。特征值相差大数量级。如何发现判断矩阵是病态的?本讲稿第七十四页，共八十页如何解决和处理?预处理方法，即将AX=b转化为等价的方程组本讲稿第七十五页，共八十页例例10 10 设则化为则本讲稿第七十六页，共八十页 设 为线性方程组Ax=b的近似解，于是可计算 的剩余向量 ，当 很小时，是否为Ax=b一个较好的近似解呢？下面的定理给出了解答。由（5.12）以及（5.13）式即得到（5.11）（5.11）式说明，近似解 的精度不仅依赖于剩余r的“大小”，而且依赖于A的条件数，当A是病态的，即使有很小的剩余r，也不能保证 是高精度的近似解本讲稿第七十七页，共八十页本讲稿第七十八页，共八十页本讲稿第七十九页，共八十页本讲稿第八十页，共八十页