《数值分析 (7-3)第3章 线性代数计算方法》由会员分享，可在线阅读，更多相关《数值分析 (7-3)第3章 线性代数计算方法（124页珍藏版）》请在金锄头文库上搜索。
1、第3章 线性代数计算方法,1 高斯消去法 2 矩阵的三角分解3 迭代法 4 迭代法的收敛性,1 高斯消去法,1.1 顺序消去法 如果线性方程组(31)的系数矩阵A具备某特殊形式,例如其为上三角矩阵,且aii0,i=1,2,n,这时方程组(31)实际为,(34),由方程组(34)的最后一个方程直接可得,将其代入倒数第二个方程可求得,如此再解出xn-2,x2,x1,一般有,(35),其中规定,以上讨论告诉我们,对具有上三角形系数矩阵的方程组(34)求解极为方便。当然,若方程组(31)的系数矩阵为下三角形,则求解也很方便。于是对于一般形式的方程组(31),我们总设法把它化为系数矩阵呈上(或下)三角形
2、的方程组来求解。为了达到目的,可利用消去法进行。现举例如下: 解方程组,(36),作-消去中的x1,作-4消去中的x1,则方程组(36)化为,(36),对方程组(36)作- ,得到三角形方程组,(36),从方程组(36“)的方程解出x3,将所得的结果代入方程求出x2,再把x3、x2同时代入方程解出x1。这样可求出方程组的解为 上述求解方程组的方法就是高斯(Gauss)消去法。从式(36)到 (36)的过程称为消元过程而由(36)求出x3、x2、x1的过程称为回代过程。因此用高斯消去法求解性方程组要经过消元和回代两个过程。,在计算机上实现时,我们常把方程组右端的常数项排于系数矩阵的第n+1列,这
3、样顺序高斯消去法的计算步骤为: 1.消元过程 对于k=1,2,n-1,若按顺序有某一ark0,rk,则交换k与r行,然后计算 ,(311),2. 回代过程 对于k=n,n-1,2,1,计算,(312),1.2 主元素消去法 前述顺序消去法是按序通过用a11,a(1)22,a(n-2)n-1 (a(k-1)kk0)作为除数来达到消元目的的。在实际计算时,由于舍入误差的影响,计算结果会改变很大,甚至于完全失真。例如用高斯消去法求解下列方程组(用四位有效数字计算):,-105得 (1.000-1.000105)x2=1.000-6.000104化简可得 x2=0.6000回代求得 x1=105(0.
4、6-0.6000)=0而方程组的解应为 x1=0.4000 x2=0.6000,显然用上述方法求出的解x1与方程组的实际解相差很大。若改变两个方程的顺序,即 x1+x2=1 10-5 x1+x2=0.6 -10-5得 (1000-100010-5)x2=0.6-1.00010-5 化简得 x2=0.6000 回代求得 x1=(1-0.6000)=0.4000,高斯主元素消去法是顺序消去法的一种改进。它的基本思想是在逐次消元时总是选绝对值最大的元素(称之为主元)做除数,按顺序消去法的步骤消元。 这里主要介绍求解线性方程组最常用的列主元素消去法和全主元素消去法。 1.列主元素消去法 所谓列主元素消
5、去法就是在每一步消元过程中取系数子矩阵的第一列元素中绝对值最大者作主元。对线性方程组(31)进行n-1次消元后,可得到上三角形方程组,必须指出的是方程组(313)中的系数aij(ij)和右端的bi已经改变了,并非与原来相同。这样就可对方程组(313)回代求解。 例1 用列主元素消去法解方程组,(313),取四位有效数字计算。 解 中-18为主元,交换和得, , ,+12/18,+1/18得, ,第二列消元时,主元为1.167,交换方程和得, ,+1/1167得, ,回代求得 x1=1.000,x2=2.000,x3=3.001方程组的实际解 x1=1,x2=2,x3=3,在计算机上求解时,前面
6、已经讲过,常把右端常数项 b 作为系数矩阵A的第n+1列,从而得到增广矩阵(A, b), 仍记为A,于是, 列主元素消去法的计算过程为: (1)消元过程。对于k=1,2,n-1进行下述运算: 选主元,确定r,使得 若ark=0,说明系数矩阵为奇异,则停止计算否则进行下一步。 交换A的r、k两行 对i=k+1,k+2,n,j=k+1,k+2,n+1计算,(314),aij-aikakj/akk=aij (315) (2) 回代过程。对于k=n,n-1,1计算,(316),2. 全主元素消去法 所谓全主元素消去法,就是每步消元时选取系数子矩阵中绝对值最大的元素作主元。经过n-1次消元后,方程组(3
7、1)可化为上三角形方程组,(317),这里方程组(317)中的系数aij(ij)及bi一般改变了。特别是未知数的排列顺序,由于全主元素的消元过程中,其系数矩阵可能进行了列对调,那么未知数也相应地作了对调。例如,若矩阵第i列与第j列对调,则未知数xi与xj也相应地对调了,xi的结果实质上为xj的结果。,图 3.1,图 3.1,例2 用全主元素消去法求解方程组, ,解这里主元为-18,交换方程与方程得, ,再全选主元,主元为2.333,交换x2和x3所在的两列,同时改变两未知数的排列号得, ,-0.944/2.333得, ,已经化为三角方程组,回代求解 x1=1.000,x2=3.000,x3=2
8、.000 这里未知数x2与x3已对调,所以应恢复解的顺序,方程组的实际精确解为 x1=1.000,x2=2.000,x3=3.000 在计算机上求解时,我们仍把增广矩阵(A, b) 记为A,具体计算过程为 (1)消元过程。对k=1,2,n-1进行下列运算:,图 3.2,图 3.2, 选主元,确定r,t使得 若art=0,则系数矩阵为奇异的,停止计算否则进行下一步。 交换A中的r、t两行及t、k两列,并记下交换的足码t、k。 对i=k+1,k+2,n,j=k+1,k+2,n+1计算 (2) 回代过程。对k=n,n-1,1计算,(318),(319),(320),2 矩阵的三角分解,对于线性方程组
9、(31),若其系数矩阵A能够分解成两个三角形矩阵相乘,譬如, A=LU L为下三角矩阵,U为上三角矩阵,则求解方程组(31)就化为求解 LUx=b,令,Ux=y,(334),(335),则 Ly=b (335)、(336)都为三角形方程组,先求出(336)中的 y,然后代入(335)就可以求出原方程组(31)的解x。,(336),2.1 消去法与矩阵的初等变换 从矩阵的初等变换来看,前面所述的主元素消去法(假定主元素经过行列调换以后均在对角线上),就是通过一系列的初等变换将方程组(31)的系数矩阵A化为三角矩阵。其每一步的消元过程相当于对增广矩阵(A,b)作一次初等变换。 令 在消去第一列中的
10、ai1(i=2,3,n)时,左乘的矩阵为,这样就把A化为一个上三角矩阵U，即,在需要进行行交换时，还得左乘某些排列矩阵Pij,A=LU (337) 称式(337)为矩阵A的LU分解或三角分解。 由上述讨论,只要系数矩阵A非奇异,经过适当的行交换后总可以将A分解为一个下三角矩阵L和一个上三角矩阵U之积。下面首先讨论矩阵三角分解的唯一性。,2.2 矩阵三角分解的唯一性 设非奇异矩阵A存在一种三角分解LU,一般这种分解未必唯一,这是因为任意一个同阶的非奇异对角矩阵D总有 (LD)(D-1 U)=L1U1 它也是矩阵A的一种三角分解。为了确保三角分解的唯一性,需对分解加以规格化。 为使LU分解规格化,
11、可以把矩阵U换成DU,其中L为单位下三角矩阵,U为单位上三角矩阵,D为对角矩阵,即,我们称 A=LDU(338) 为矩阵A的一种LDU分解。关于矩阵A的LDU分解有如下定理: 定理1对于nn阶矩阵A存在唯一的LDU分解的必要充分条件是A的各阶主子矩阵A1,A2,An均非奇异。 证先证必要性。设A有唯一的LDU分解,即 A=LDU 由于 Ak=LkDkUk,其中Ak、Lk、Dk、Uk分别表示A、L、D、U的k阶主子矩阵。因为L、U是单位三角矩阵,D为非奇异对角矩阵,所以Lk、Uk、Dk均非奇异,从而知Ak必为非奇异矩阵。 再证充分性。用数学归纳法证明: 当k=1时,A1显然有这种三角分解且是唯一的,即 A1=L1D1U1=l11d1u11 其中 l11=1,d1=a11,u11=1,设对k=n-1时结论成立,将A按下面方式分块:,这里 s=(a1n,a2n,a n-1n)T rT=(an1,an2,a nn-1) a=ann再将A、D、U仿照A分块:,这里,设,若通过A的元素能唯一地定出L中的IT,U中的u及D中的d,就可确认A唯一地有LDU分解了。因为,其中r、s、a均为已知,于是有 L n-1 D n-1 u=s (D n-1 U n-1 )TI=r ITD n-1 u+d=a,
