2022年成都市中考满分作文第八章线性方程组的迭代解法.pdf
第八章 线性方程组的迭代解法7.1 引言解线性方程组的直接方法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为 n2量级，这在系数矩阵 A 的规模比较小的时候还比较合适（如：矩阵维数n400） 。但是，当 A 为大型稀疏矩阵 时，再利用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法： 迭代法 。从第六章方程求根的迭代方法可以推测：迭代法： 从线性方程组一个初始的近似解（向量）出发，反复套用同一个迭代公式，构造一个无穷序列，逐步逼近方程组精确解的方法（一般有限步内得不到精确解）。特点：该方法具有存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点，但是存在收敛性 及收敛速度 方面的问题。例 8.1（P201）如何设计方程组的迭代公式线性方程组：等价的迭代方程组：迭代过程：AxbxBxf1kkxBxf可以写成多种等价的迭代方程组，例如：AIAIxIA xbBxf11ADADxIDA xD bBxf，0iia（例 8.1）11ALDUxDLU xD bBxf，0iiaJacobi 迭代注：- -AL D U的形式如下精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 8 页 - - - - - - - - - - 121311112111212322122222313211212300000000nnnnnnnnnnnnnnnaaaaaaaaaaaaaaAaaaaaaaaaaL -D -U问题：1、是否任意一个等价的迭代方程组，按迭代法做出的向量序列都一定逐步逼近方程组的解呢？2、如何保证收敛性？定义 8.1 对于给定的方程组xBxf，用式子10211.kkxBxfxBxfxBxf逐步代入求近似解的方法称为 迭代法 （或称为 一阶定常迭代法 ，这里 B 与迭代次数 k 无关） 。如果limkkx存在（记作*x） ，称此迭代法 收敛，显然*x就是方程组的解；否则称此迭代法 发散。收敛性讨论从误差的角度分析，引入误差向量：*kkxx则：lim*kkxxl i m0kk，*kkxx将1021-1.kkxBxfxBxfxBxf的各个方程减去*xBxf得：1202.kkkkBBB，0为初始误差精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 8 页 - - - - - - - - - - 如果矩阵 B满足 lim0kkB（零矩阵）， 那么lim0kk就成立， 即lim*kkxx，迭代过程收敛。8.2 Jacobi迭代法与 Gauss-Seidel迭代法8.2.1 Jacobi （雅可比）迭代法迭代公式线性方程组：矩阵形式描述：11 11111nnnnnnna xa xba xa xbAxb等价的迭代方程组：11122111222112331221111111nnnnnnnn nnnnxba xa xaxba xa xa xaxba xaxa0iiaxB xfB=？ f=？即：11niiijjjiiijxba xa因此， Jacobi迭代法的迭代公式为00001211,.,1Tnnkkiiijjjiiijxxxxxba xa迭代矩阵令ADLU，其中：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 8 页 - - - - - - - - - - 1122D=nnaaa21313212300L=00nnnaaaaaa12131232100U00nnnnaaaaaa则，等价的迭代方程组为：1111DLUxbIDLUxD bxDLU xD bxBxfAxb111BDLUIDfD bA迭代公式的矩阵形式为：0000121,.,TnkkxxxxxBxf称 B 为 Jacobi方法迭代矩阵 。特点：Jacobi迭代法公式简单，每迭代一次只需要计算一次矩阵和向量乘法！在用计算机计算时，计算x(k+1)时需要 x(k)的所有分量，因此需开两组存储单元分别存放 x(k)和 x(k+1)。8.2.2 Gauss-Seidel （高斯 -赛德尔）迭代法由 Jacobi方法迭代公式可知，迭代的每一步计算过程，都是用x(k)的全部分量来计算 x(k+1)的所有分量。能否在计算 x(k+1)的第 i 个分量1kix时，利用 x(k+1)已经计算出的前i-1 个分量111121,.,kkkixxx的信息？这样做有两方面的优势：1、 从直观上看，最新计算出的分量可能比旧的分量要好些（更精确逼近线性方程组的真实解向量） 。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 8 页 - - - - - - - - - - 2、 计算1kix时只需要 x(k)的 i+1n 个分量，因此 x(k+1)的前 i 个分量可存储在 x(k)的前 i 个分量所占的存储单元，无需开两组存储单元。因此，对这些最新计算出来的第k+1 次近似 x(k+1)的分量1kjx加以利用，就得到解方程组的Gauss-Seidel迭代法（ G-S 方法） 。迭代公式Gauss-Seidel迭代法的迭代公式：00001211111,.,1Tninkkkiiijjijjjjiiixxxxxba xa xa注：对比 Jacobi迭代公式：00001211111,.,11Tnninkkkkiiijjiijjijjjjjiiiiiijxxxxxba xba xa xaaGauss-Seidel迭代公式也可以写为：(1)( )111=+0,1,2,.;1,2,.,1kkiiiinkkiiijjijjjj iiixxxkinxba xa xa（注意第二项求和， j=i）迭代矩阵由 Gauss-Seidel迭代公式：111111inkkkiiijjijjjjiiixba xa xa得：11111inkkkiiiiijjijjjjia xba xa x写成矩阵的形式：11kkkDxbLxUx1kkDL xbUx精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 8 页 - - - - - - - - - - 若设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就成立，即精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 8 页 - - - - - - - - - - lim*kkxx，迭代过程收敛。矩阵序列的极限定义 8.2 设有矩阵序列kkijn nAa（1,2,.k）及ijn nAa，如果limkijijkaa（,1,2,.,i jn）成立，则称kA收敛于 A，记作 limkkAA。例 8.4 矩阵序列的例子矩阵序列极限的概念可以用任何矩阵范数来描述。范数的定义如果矩阵ijn nAa的某个 非负实函数 N A ，记作 A ，满足条件：（1）0A当且仅当0A时，0A（非负性）（2）AAR（齐次性）（3）对任意两个阶数相同的矩阵A,B 有 ABAB （三角不等式性）（4）A,B 矩阵为同阶矩阵 , ABA B （相容性）则称 N AA 为矩阵范数 。矩阵范数的例子：A 的行范数：11maxniji njAaA 的列范数：111maxnijjniAaA 的 2 范数：12A（1是TA A最大特征值）定理 8.1 limkkAA 的充要条件 是0kAA（k）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 8 页 - - - - - - - - - - （证明略。 ）定理 8.2 设迭代矩阵ijn nBb，则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对于任意初始向量0 x及任意 f，解此方程组的迭代法（即1kkxBxf）收敛的充要条件是1B。（证明见 P207-208）验证迭代过程是否收敛的例子：例 8.5，例 8.6 收敛速度的讨论可以看出，当1B越小时，收敛速度越快。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 8 页 - - - - - - - - - -
