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

解线性方程组的直解线性方程组的直接方法接方法现在学习的是第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.酉矩阵 设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)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页为若尔当块.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。得到与原方程组等价的三角形线性方程组显然，线性方程组（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 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）回代过程现在学习的是第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充分性对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施行行的初等变换相当于用初等矩阵左乘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次消元.得到现在学习的是第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)按列选主元 (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页二、高斯二、高斯若当消去法若当消去法现在学习的是第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页于是，可以通过求解两个三角形方程组得到原方程组的解,求解方程组计算公式求解方程组计算公式:说明说明:上面方法称为杜利特尔（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为下三角矩阵,U为单位上三角矩阵,故上述方程组的求解极为方便。他们的计算公式分别为现在学习的是第44页，共80页 用克劳特分解求解线性方程组Ax=b的计算过程为:LU分解过程:对于k=1,2,n依次计算现在学习的是第45页，共80页现在学习的是第46页，共80页 例4 用克劳特分解方法求解下列方程组解 令 现在学习的是第47页，共80页 利用矩阵乘法可得到 现在学习的是第48页，共80页 这样原方程组就化为依次求下列两个三角形方程组代入第二个方程组可求得原方程组的解为 现在学习的是第49页，共80页2、选主元选主元直接三角分解法直接三角分解法从直接三角分解公式可看出当 时计算将中断，或者当 绝对值很小时，按分解公式计算可能引起舍入误差的累积。但如果当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 =）称为向量,的数量积.并将非负实数|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(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页诱导出的常用范数有：它们满足如下相容关系：例例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 系数矩阵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的条件数.现在学习的是第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页