解线性方程组的直接方法 (2)精选PPT.ppt

《解线性方程组的直接方法 (2)精选PPT.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的直接方法 (2)精选PPT.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、解线性方程组的直接解线性方程组的直接方法方法第1页，此课件共80页哦二、向量和矩阵二、向量和矩阵第2页，此课件共80页哦第3页，此课件共80页哦三、特殊矩阵三、特殊矩阵设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.酉矩阵 设

2、A ACnn,如果A-1=AH.-第4页，此课件共80页哦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第5页，此课件共80页哦定理定理2 若ARnn 为对称正定矩阵，则(1)

3、A A为非奇异矩阵，且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)第6页，此课件共80页哦定理定理3 若ARnn 为对称矩阵.如果det(Ak)0(k=1,2,n),或A得特征值i0（i=1,2,n）.则A为对称正定矩阵。有重特征值的矩阵不一定相似于对角矩阵，那么一般n阶矩阵A在相似变换下能简化到什么形状？定理定理4(若尔当（Jordan）标准型）设A为n阶矩阵，则存在一个非奇异矩阵P使得第7页，此课件共80页哦为若尔当块

4、.1）当A A的若尔当标准形中所有若尔当块Ji均为一阶时，此标准型变成对角矩阵；2）如果A A的特征值各不相同，则其若尔当标准型必为对角矩阵diag（1 2 n）.第8页，此课件共80页哦2 2 高斯消去法高斯消去法一、高斯消去法一、高斯消去法设有线性方程组：AXAX=b b （2.12.1）首先举一个例子来说明消去法的基本思路例例2 2 用消去法解线性方程组第9页，此课件共80页哦解 第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行第10页，此课件共80页哦 由此看出，用消去法解线性方程组的基本思想是用逐次消去未知数的方法把原线性方程组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.第11页，此课件共80页哦（1）消元过程 简记为 A A（2

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

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

8、充分性对k亦成立.设Di0（i=1,2,k）,于是由归纳法假设aii(i)0(i=1,2,k-1),可用高斯消去法将A（1）约化到A（k）,即第16页，此课件共80页哦(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).第17页，此课件共80页哦第18页，此课件共80页哦二、矩阵的三角分解二、矩阵的三角分解下面建立高斯消去法与矩阵的因式分解的关系.设方程组Ax=b的系数矩阵A的各顺序主子式均不为0.由于对A施行行的初等变换相当于用初等矩阵左乘

9、A.第19页，此课件共80页哦第20页，此课件共80页哦 从而我们可以知道，高斯消去法实质是将A分解为两个三角矩阵的相乘的因式分解，于是有如下重要定理。第21页，此课件共80页哦第22页，此课件共80页哦第23页，此课件共80页哦3 3 高斯主元素消去法高斯主元素消去法例例4 4 采用3位十进制，用消元法求解 解法解法1：第24页，此课件共80页哦解法解法2：全主元消去法;列主元消去法.第25页，此课件共80页哦一、列主元消去法一、列主元消去法设有线性方程组：AX=b第一步:先在A A的第一列选取绝对值最大的元素作主元素,然后交换其增广矩阵的第1行和第i1行(当i11时),再进行第1次消元.得

10、到第26页，此课件共80页哦重复上述过程，设已完成第k-1步的选主元素，交换两行及消元计算，约化为其中A（k）的元素仍记为aij，b(k)的元素仍记为b.第k步选主元素(在A（k）右下角方阵的第1列内选),即确定ik，使然后交换第k行和第ik（k=1,2,n-1）行(当ikk时),再进行第k次消元.第27页，此课件共80页哦最后将原线性方程组化为回代求解第28页，此课件共80页哦算法算法(列主元消去法).设AX=b，本算法用A得具有行交换的列主元素消去法，消元结果冲掉A，乘数mij冲掉aij，计算解X冲掉常数项b，行列式存放在det中.1.det12.对于k=1,2,n-1 (1)按列选主元

11、(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第29页，此课件共80页哦(5)detakk*det3.如果ann=0，则计算停止（det（A）=0）4.回代求解 (1)bn bn/ann(2)对于i=n-1,2,15.detann*det第30页，此课件共80页哦下面用矩阵描述列主元消去法第31页，此课件共80页哦第32页，此课件共80页哦

12、二、高斯二、高斯若当消去法若当消去法第33页，此课件共80页哦算法算法(高斯高斯若当消元法若当消元法).第34页，此课件共80页哦第35页，此课件共80页哦例例4 4 采用高斯若当消去法求矩阵的逆A-1.第36页，此课件共80页哦4 4 矩阵的三角分解法矩阵的三角分解法设有线性方程组：AX=bAX=b一、直接三角分解法一、直接三角分解法1 1、不选主元三角分解算法、不选主元三角分解算法当A A非奇异时，由不需选主元的顺序高斯消去法知第37页，此课件共80页哦就有,不选主元的三角分解算法不选主元的三角分解算法：第38页，此课件共80页哦于是，可以通过求解两个三角形方程组得到原方程组的解,求解方程

13、组计算公式求解方程组计算公式:说明说明:上面方法称为杜利特尔（Doolittle）分解方法第39页，此课件共80页哦练习练习利用LU(Doolittle)分解法求解方程组第40页，此课件共80页哦 克劳特分解方法 设A为nn阶非奇异矩阵,且各阶主子矩阵为非奇异,则矩阵A的克劳特(Crout)分解为 A=LU 其中第41页，此课件共80页哦第42页，此课件共80页哦 这样,L、U中的元素都已求出。计算L的各列与U的各行的次序如图所示。图 第43页，此课件共80页哦 对方程组Ax=b的系数矩阵A作出LU分解后,方程组便化为 LUx=b 则求解上列方程组就化为依次解方程组 Ly=b Ux=y 由于L

14、为下三角矩阵,U为单位上三角矩阵,故上述方程组的求解极为方便。他们的计算公式分别为第44页，此课件共80页哦 用克劳特分解求解线性方程组Ax=b的计算过程为:LU分解过程:对于k=1,2,n依次计算第45页，此课件共80页哦第46页，此课件共80页哦 例4 用克劳特分解方法求解下列方程组解 令 第47页，此课件共80页哦 利用矩阵乘法可得到 第48页，此课件共80页哦 这样原方程组就化为依次求下列两个三角形方程组代入第二个方程组可求得原方程组的解为 第49页，此课件共80页哦2、选主元选主元直接三角分解法直接三角分解法从直接三角分解公式可看出当 时计算将中断，或者当 绝对值很小时，按分解公式计

15、算可能引起舍入误差的累积。但如果当A非奇异，我们可以通过交换A的行实现矩阵PA的LU分解.因此可采用与列主元消去法类似的方法，将直接三角分解法修改为（部分）选主元的三角分解法。第50页，此课件共80页哦5 5 向量和矩阵的范数向量和矩阵的范数 为了研究线性方程组的近似解的误差估计和迭代法的收敛性,我们需要对Rn中的向量(或Rnn中的矩阵)的“大小”引进某种度量向量(或矩阵)的范数.首先考虑Rn中向量的长度,然后可定义向量(或矩阵)的范数.定义定义1 1 设设=(1,2,n)T，=(1,2,n)T Rn.将实数(,)=T =1 1+2 2+n n（或复数(,)=H =）称为向量,的数量积.并将非

16、负实数|2=(,)1/2=称 为向量的欧氏范数.第51页，此课件共80页哦第52页，此课件共80页哦(1)正定性：等号当且仅当时成立；(2)齐次性：(3)三角不等式：则称为向量的范数范数或模模.由(3)得(4)第53页，此课件共80页哦几种常用范数(无穷范数)(1-范数)(2-范数)(p-范数)可以验证它们都是范数.易见前三种范数是p-范数的特殊情况例例6 6 计算向量的几种常用范数第54页，此课件共80页哦证明证明 设只需证明当xy时N（x）N（y）即成.事实上第55页，此课件共80页哦第56页，此课件共80页哦证明证明 只要就s=证明上式成立即可，即证明存在常数c1,c20,使考虑函数 f

17、(x)=xt0,xRn.记S=x|x1,xRn,则S是一个有界闭集。由于f(x)为S上的连续函数，所以f(x)于S上达到最大最小值，即存在x,x”S使得设x Rn 且x0,则显然c1,c20,上式为第57页，此课件共80页哦第58页，此课件共80页哦第59页，此课件共80页哦定义定义4 4(矩阵的范数)(1)正定性：等号当且仅当时成立；(2)齐次性：(3)三角不等式：则称为 矩阵的范数范数或模模。第60页，此课件共80页哦第61页，此课件共80页哦显然这种矩阵的范数Av依赖于向量范数xv的具体含义。也就是说，当给出一种具体的向量范数xv时，相应地就得到了一种矩阵范数Av第62页，此课件共80页

18、哦诱导出的常用范数有：它们满足如下相容关系：例例7 7 计算矩阵的几种常用范数第63页，此课件共80页哦第64页，此课件共80页哦第65页，此课件共80页哦证明 用反证法。若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 第66页，此课件共80页哦6 6 误差分析误差分析一、矩阵的条件数一、矩阵的条件数考虑线性方程组 AX=b

19、系数矩阵A和右端b的小扰动所产生的相对误差.例例8 8 方程组准确解为常数项微小变化后准确解第67页，此课件共80页哦定义定义7 7 如果矩阵A或常数项b的微小变化,引起线性方程组AX=b的解的巨大变化,则称此方程组为病态方程组矩阵A称为病态矩阵,否则称方程组为良态方程组,矩阵A为良态矩阵.第68页，此课件共80页哦第69页，此课件共80页哦 条件数刻画了线性方程组AX=b的解对数据误差的灵敏程度，它只与此方程组的系数有关，反映了方程组固有的本性。故可用条件数来描述方程组的性态.第70页，此课件共80页哦第71页，此课件共80页哦第72页，此课件共80页哦例例9 9 求Hilbert矩阵H3的

20、条件数.第73页，此课件共80页哦注：注：一般判断矩阵是否病态，并不计算一般判断矩阵是否病态，并不计算A 1，而由经验得，而由经验得出。出。行列式很大或很小（如某些行、列近似相关）；行列式很大或很小（如某些行、列近似相关）；元素间相差大数量级，且无规则；元素间相差大数量级，且无规则；主元消去过程中出现小主元；主元消去过程中出现小主元；特征值相差大数量级。特征值相差大数量级。如何发现判断矩阵是病态的?第74页，此课件共80页哦如何解决和处理?预处理方法，即将AX=b转化为等价的方程组第75页，此课件共80页哦例例10 10 设则化为则第76页，此课件共80页哦 设 为线性方程组Ax=b的近似解，于是可计算 的剩余向量 ，当 很小时，是否为Ax=b一个较好的近似解呢？下面的定理给出了解答。由（5.12）以及（5.13）式即得到（5.11）（5.11）式说明，近似解 的精度不仅依赖于剩余r的“大小”，而且依赖于A的条件数，当A是病态的，即使有很小的剩余r，也不能保证 是高精度的近似解第77页，此课件共80页哦第78页，此课件共80页哦第79页，此课件共80页哦第80页，此课件共80页哦