第2章 解线性代数方程组的迭代法

第2章解线性代数方程组的迭代法求解线性代数方程组主要有直接法和迭代法两种常见方法。直接法一般适合小型的系数矩阵，为了求解现实当中常见的大型稀疏矩阵，下面我们将重点介绍迭代法。它是一种不断套用一个迭代公式，逐步逼近方程的解的方法。将讨论两类主要方法，一类是逐步逼近法，另一类是下降法，包括最速下降法和共轭梯度法。为了对线性方程组数值解的精确程度，以及方程组本身的性态进行分析，需要对向量和矩阵的“大小”引进某种度量，范数就是一种度量尺度，向量和矩阵的范数在线性方程组数值方法的研究中起着重要的作用。2.1向量、矩阵范数与谱半径（2）齐次性：对任何实数和向量x||kx||＝|k|||x||（3）三角不等式：对任何向量x和y，都有||x＋y||≤||x||＋||y||（1）非负性：对任何向量x，||x||≥0，且||x||＝0当且仅当x＝02.2.1向量的范数定义2.1设是x的实值函数，且满足条件xxNCxRxnn)()(，或则称为Rn(或Cn)上的一个向量范数(或向量模)，||x||的值为向量x的范数。xxN)(向量1-范数：niixx1121122niixx向量2-范数：向量无穷范数：inixmaxx1容易验证，以上三种范数都满足向量范数的三个条件。理论上存在多种多样的向量范数，但最常用的是如下三种。设向量x＝(x1，x2，…，xn)T，定义解:对于向量x＝(1，-3，2，0)T，根据定义可以计算出：||x||1＝|1|＋|-3|＋|2|＋|0|＝61402312122222x30,2,3,1maxx由此例可见，向量不同范数的值不一定相同，但这并不影响对向量大小做定性的描述，因为不同范数之间存在如下等价关系。例2.1设向量x＝(1，-3，2，0)T，求向量范数||x||p，P＝1，2，∞。定理2.1（范数的等价性）对于Rn上任何两种范数||·||α和||·||β，存在的正常数m，M，使得：nRxxMxxm,范数的等价性表明，一个向量若按某种范数是一个小量，则它按任何一种范数也将是一个小量。容易证明，常用的三种向量范数满足下述等价关系。||x||∞≤||x||1≤n||x||∞||x||∞≤||x||2≤||x||∞||x||∞≤||x||1≤||x||2定义2.2对于向量序列,,2,1,),,,()()(2)(1)(kxxxxTknkkk*)(limxxkk*)(xxkTnxxxx),,,(**2*1*及向量*)(limikxxik如果则称向量序列x(k)收敛于向量x*。记作或2.1.2矩阵的范数矩阵范数是反映矩阵“大小”的一种度量，具体定义如下。AxNCxRAnnnn)()(，或定义2.3设为A的实值函数，且满足条件：（1）||A||≥0，且||A||＝0时，当且仅当A＝0（2）||kA||＝|k|||A||，k∈R（3）||A＋B||≤||A||＋||B||则称上的一个矩阵范数，||A||的值为矩阵A的范数。)()(nnnnCxRAxN或为设n阶矩阵A＝（aij），常用的矩阵范数有：矩阵1-范数：niijnjaA111||max212的最大特征值AAAT矩阵2-范数：njijni1amaxA1||矩阵无穷范数：列和行和以上三种范数都满足矩阵范数的条件，通常将这三种矩阵范数统一表示为||A||p，P＝1，2，∞。例2.2设矩阵4321A求矩阵A的范数||A||p，P＝1，2，∞。解根据定义6|4||2||,3||1|max1A43214231AAT由于7|4||3||,2||1|maxA20141410此方程的根为矩阵ATA的特征值，解得221151221152因此46.522115212A则它的特征方程为:0430201414102AAIT在线性方程组的研究中，经常遇到矩阵与向量的乘积运算，若将矩阵范数与向量范数关联起来，将给问题的分析带来许多方便。设||·||是一种向量范数，由此范数派生的矩阵范数定义为pp0xpxAxmaxA注意，此式左端||A||表示矩阵范数，而右端是向量Ax和x的范数，利用向量范数所具有的性质不难验证，由上式定义的矩阵范数满足矩阵范数的条件。)1(,,nnnRARxxAAx通常将满足上式的矩阵范数称相容范数。由向量范数||x||p派生出的矩阵范数：pxppxpAxmaxxAxmaxAp10通过向量范数定义的矩阵范数，满足不等式关系：称之为矩阵A的算子范数，其中p＝1，2或∞。)2(,,nnRBABAAB定理2.2由上式所定义的矩阵范数为相容范数。ppppppyppxAAxAyAymaxxAx0证明：当x=0时，(1)式显然成立。,0x,,nnRBApPxpxpBxAmaxABxmaxABpp11PPpxPBABxmaxAp12.1.3矩阵的谱半径矩阵范数同矩阵特征值之间有密切的联系，设λ是矩阵A相应于特征向量x的特征值，即Ax＝λx,于是利用向量-矩阵范数的相容性，得到|λ|||x||=||λx||从而，对A的任何特征值λ均成立=||Ax||≤||A||||x|||λ|≤||A||（3）设n阶矩阵A的n个特征值为λ1,λ2，…λn，称inimaxA1)(为矩阵A的谱半径。从(3)式得知，对矩阵A的任何一种相容范数都有ρ(A)≤||A||。2.2迭代法的一般形式与收敛性定理2.2.1迭代法的一般形式已知线性代数方程组(2.2.1)Axb首先将方程组改写成等价的形式(2.2.2)xHxg从而建立迭代式：10,1,2(2.2.3)kkxHxgkkx称为迭代序列，并称H为迭代矩阵。**xHxg则是线性方程组Ax=b的解。*x当给定初始向量0x后可得到迭代向量序列，若kx*limkkxx在等式(2.2.3)两端取极限可得2.2.2迭代法的收敛性利用迭代公式(2.2.3)构造序列，以求得方程组(2.2.2)的近似解的算法称为解(2.2.2)式的简单迭代法。)(kx若迭代序列收敛，则称此迭代法是收敛的。)(kx**xHxg1,kkxHxg两式相减，知误差向量满足下列迭代关系：*xxk)(*)(*)1(xxHxxkk,2,1,0),(*)0(1*)1(kxxHxxkk由此递推：引理2.1：迭代法(2.2.3)式对任何初始近似均收敛的充分必要条件是0xkHk0引理2.2：的充要条件是0kHk()1H定理2.4：迭代法(2.2.3)式对任何初始近似均收敛的充分必要条件是迭代矩阵H的谱半径0x()1H推论：若(允许为任何一种相容的矩阵范数)，则迭代法(2.2.3)式收敛。1H例1设其中，0.10.50.80.1H1,kkxHxg讨论该迭代法的收敛性。例2设其中，0.900.30.8H1,kkxHxg讨论该迭代法的收敛性。2.2.3迭代法的收敛速度定理2.5当时，由迭代法（2.2.3）式所定义的序列满足如下估计式：1H(){}kx()*()(1)1kkkHxxxxH()*(1)(0)1kkHxxxxH*)0(*)(xxxxk*)0(*)(xxHxxkk现在讨论使误差减少初始误差的倍所需的最少迭代次数。若要求则kkHH)(两边取对数得:)(lnlnln)(lnHkHk)(lnH定义:为迭代法(2.2.3)的渐进收敛速度。2.3Jacabi方法与Gauss-Seidel方法2.3.1Jacabi方法设A=D-L-U,则DLUxbDxbLUx11xDLUxDb即迭代格式为11101kkxDLUxDbk＝，，(2.3.4)bDxADIx11也可改写为迭代矩阵为11()JHIDADLU分量形式为11111ijnijikjijkjijiikibxaxaax1,2,,0,1,2,ink2.3.2Gauss-Seidel方法1111111,2,inkkkjiijjijijjiiixaxaxbina(1)kix计算第i个新分量时，前i-1个均已求出，一般来说，后算出来的值有更好的近似，因此可用这些新值来计算利用最新值进行计算的方法称为Seidel迭代法。对Jacabi迭代法运用Seidel技巧得到1(1)()()1inkkkiijjijjijjixhxhxg1(1)(1)()1inkkkiijjijjijjixhxhxg在用简单迭代法其矩阵形式为11101kkkxDLxUxbk＝，，整理成一般迭代法的形式为111()()kkxDLUxDLb例2.3用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组,已知方程组得精确解为x*=(1，1，1)T。解：先改写方程如下再写出Jacobi迭代格式,2,1,0k141035310214310321321321xxxxxxxxx)314(101)325(101)314(101213312321xxxxxxxxx)314(101)325(101)314(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx取初值为:x(0)=(0，0，0)T,求得:x(1)=(1.4，0.5，1.4)Tx(6)=(1.00025，1.00580，1.00251)T误差为由x*=(1，1，1)T得到||x(6)-x*||∞=0.00580。初值也取为:x(0)=(0，0，0)T,求得近似解：Gauss-Seidel迭代格式为,2,1,0k)314(101)325(101)314(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx初值也取为:x(0)=(0，0，0)T,求得近似解：误差为由x*=(1，1，1)T得到||x(4)-x*||∞=0.00846。Jacobi迭代法迭代6次与Gauss-Seidel迭代法迭代4次的精度一致，说明Gauss-Seidel迭代法收敛的较快。x(1)=(1.4，0.78，1.026)Tx(4)=(0.99154，0.99578，1.00210)T2.3.3对角占优矩阵与不可约矩阵12.4(),1,,1,ijnijiijjiAaaainiAinA＝，定义若矩阵满足条件且至少有一个使不等式严格成立，则称为（按行）对角占优矩阵，若对严格不等式均成立，则称为（按行）严格对角占优矩阵2.5(2).,1nnTARnPBCPAPODBDOAA定义设若存在置换矩阵使得其中和是阶数的方阵，是零矩阵，则称为可约的，否则称为不可约的.(),0,1,2,,iiAainA定理26若为严格对角占优矩阵或对角占优且不可约矩阵则且是非奇异的.(1)()()(),A定理27若系数矩阵满足按行或列严格对角占优矩阵,或者2不可约按行或列对角占优则Jacabi迭代法和Gauss-Seidel迭代法均收敛.,2.AADA定理28若是对角元素大