成都市中考满分作文-第八章线性方程组的迭代解法

第八章线性方程组的迭代解法7.1引言解线性方程组的直接方法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在系数矩阵A的规模比较小的时候还比较合适（如：矩阵维数n400）。但是，当A为大型稀疏矩阵时，再利用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法：迭代法。从第六章方程求根的迭代方法可以推测：迭代法：从线性方程组一个初始的近似解（向量）出发，反复套用同一个迭代公式，构造一个无穷序列，逐步逼近方程组精确解的方法（一般有限步内得不到精确解）。特点：该方法具有存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点，但是存在收敛性及收敛速度方面的问题。例8.1（P201）如何设计方程组的迭代公式线性方程组：等价的迭代方程组：迭代过程：AxbxBxf1kkxBxf可以写成多种等价的迭代方程组，例如：AIAIxIAxbBxf11ADADxIDAxDbBxf，0iia（例8.1）11ALDUxDLUxDbBxf，0iiaJacobi迭代注：--ALDU的形式如下121311112111212322122222313211212300000000nnnnnnnnnnnnnnnaaaaaaaaaaaaaaAaaaaaaaaaaL-D-U问题：1、是否任意一个等价的迭代方程组，按迭代法做出的向量序列都一定逐步逼近方程组的解呢？2、如何保证收敛性？定义8.1对于给定的方程组xBxf，用式子10211.......kkxBxfxBxfxBxf逐步代入求近似解的方法称为迭代法（或称为一阶定常迭代法，这里B与迭代次数k无关）。如果limkkx存在（记作*x），称此迭代法收敛，显然*x就是方程组的解；否则称此迭代法发散。收敛性讨论从误差的角度分析，引入误差向量：*kkxx则：lim*kkxxlim0kk，*kkxx将1021-1.......kkxBxfxBxfxBxf的各个方程减去**xBxf得：1202...kkkkBBB，0为初始误差如果矩阵B满足lim0kkB（零矩阵），那么lim0kk就成立，即lim*kkxx，迭代过程收敛。8.2Jacobi迭代法与Gauss-Seidel迭代法8.2.1Jacobi（雅可比）迭代法迭代公式线性方程组：矩阵形式描述：1111111nnnnnnnaxaxbaxaxbAxb等价的迭代方程组：11122111222112331221111111nnnnnnnnnnnnxbaxaxaxbaxaxaxaxbaxaxa0iiaxBxfB=？f=？即：11niiijjjiiijxbaxa因此，Jacobi迭代法的迭代公式为00001211,,...,1Tnnkkiiijjjiiijxxxxxbaxa迭代矩阵令ADLU，其中：1122D=nnaaa21313212300L=00nnnaaaaaa12131232100U00nnnnaaaaaa则，等价的迭代方程组为：1111DLUxbIDLUxDbxDLUxDbxBxfAxb111BDLUIDfDbA迭代公式的矩阵形式为：0000121,,...,TnkkxxxxxBxf称B为Jacobi方法迭代矩阵。特点：Jacobi迭代法公式简单，每迭代一次只需要计算一次矩阵和向量乘法！在用计算机计算时，计算x(k+1)时需要x(k)的所有分量，因此需开两组存储单元分别存放x(k)和x(k+1)。8.2.2Gauss-Seidel（高斯-赛德尔）迭代法由Jacobi方法迭代公式可知，迭代的每一步计算过程，都是用x(k)的全部分量来计算x(k+1)的所有分量。能否在计算x(k+1)的第i个分量1kix时，利用x(k+1)已经计算出的前i-1个分量111121,,...,kkkixxx的信息？这样做有两方面的优势：1、从直观上看，最新计算出的分量可能比旧的分量要好些（更精确逼近线性方程组的真实解向量）。2、计算1kix时只需要x(k)的i+1~n个分量，因此x(k+1)的前i个分量可存储在x(k)的前i个分量所占的存储单元，无需开两组存储单元。因此，对这些最新计算出来的第k+1次近似x(k+1)的分量1kjx加以利用，就得到解方程组的Gauss-Seidel迭代法（G-S方法）。迭代公式Gauss-Seidel迭代法的迭代公式：00001211111,,...,1Tninkkkiiijjijjjjiiixxxxxbaxaxa注：对比Jacobi迭代公式：00001211111,,...,11TnninkkkkiiijjiijjijjjjjiiiiiijxxxxxbaxbaxaxaaGauss-Seidel迭代公式也可以写为：(1)()111=+0,1,2,...;1,2,...,1kkiiiinkkiiijjijjjjiiixxxkinxbaxaxa（注意第二项求和，j=i）迭代矩阵由Gauss-Seidel迭代公式：111111inkkkiiijjijjjjiiixbaxaxa得：11111inkkkiiiiijjijjjjiaxbaxax写成矩阵的形式：11kkkDxbLxUx1kkDLxbUx若设1DL存在，则：111kkxDLUxDLb于是，Gauss-Seidel迭代公式的矩阵形式为：1kkxGxf其中：1GDLU，1fDLb称G为Gauss-Seidel迭代方法的迭代矩阵。特点：在用计算机计算时，只需一组存储单元，以便存放近似解。每迭代一步只需计算一次矩阵与向量的乘法。例8.2此例题中Gauss-Seidel迭代法比Jacobi迭代法收敛快，但这个结论在一定条件下才是对的。（当Jacobi迭代法和Gauss-Seidel迭代法都收敛时，Gauss-Seidel迭代法比Jacobi迭代法收敛快）例8.3此例题说明，存在某些线性方程组，用Jacobi迭代法收敛而Gauss-Seidel迭代法发散。注意：1)Gauss-Seidel迭代法的计算过程中只需用一个一维数组存放迭代向量。2)Gauss-Seidel迭代不一定比Jacobi迭代收敛快。8.3迭代法的收敛性前面已经从误差的角度分析了迭代过程收敛的条件：如果迭代矩阵B满足lim0kkB（零矩阵），那么lim0kk就成立，即lim*kkxx，迭代过程收敛。矩阵序列的极限定义8.2设有矩阵序列kkijnnAa（1,2,...k）及ijnnAa，如果limkijijkaa（,1,2,...,ijn）成立，则称kA收敛于A，记作limkkAA。例8.4矩阵序列的例子矩阵序列极限的概念可以用任何矩阵范数来描述。范数的定义如果矩阵ijnnAa的某个非负实函数NA，记作A，满足条件：（1）0A当且仅当0A时，0A（非负性）（2）AAR（齐次性）（3）对任意两个阶数相同的矩阵A,B有ABAB（三角不等式性）（4）A,B矩阵为同阶矩阵,ABAB（相容性）则称NAA为矩阵范数。矩阵范数的例子：A的行范数：11maxnijinjAaA的列范数：111maxnijjniAaA的2范数：12A（1是TAA最大特征值）定理8.1limkkAA的充要条件是0kAA（k）（证明略。）定理8.2设迭代矩阵ijnnBb，则0kB（k）的充要条件是1B。（证明见P206）注：B是矩阵B的普半径。设A是n×n矩阵，λi(i=1,2,…,n)是其特征值。称max,1,2,...,iAin为A的谱半径。即矩阵A的特征值中绝对值最大的那一个特征值的绝对值。矩阵A的特征值和特征向量：()det()0APIA的根，为矩阵A的特征值。满足ivAv的向量v为矩阵A的对于特征值i的特征向量。定理8.3迭代法的收敛性定理设有方程组xBxf对于任意初始向量0x及任意f，解此方程组的迭代法（即1kkxBxf）收敛的充要条件是1B。（证明见P207-208）验证迭代过程是否收敛的例子：例8.5，例8.6收敛速度的讨论可以看出，当1B越小时，收敛速度越快。