研究生课程《数值分析》-第六章线性方程组的迭代解法

数值分析--第6章解线性方程组的迭代法第6章 解线性方程组的迭代法直接方法比较适用于中小型方程组。

对高阶方程组，即使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。

迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。

故能有效地解一些高阶方程组。

1 迭代法概述迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。

由不同的计算规则得到不同的迭代法。

迭代法的一般格式(1)()(1)()(,,,),0,1,k k k k m kF k +--==x x x x式中(1)k +x 与()(1)(),,,k k k m --x x x 有关，称为多步迭代法。

若(1)k +x 只与()k x 有关，即(1)()(),0,1,k k kF k +==x x称为单步迭代法。

再设kF 是线性的，即(1)(),0,1,k kk kk +=+=x B x f式中n nk ⨯∈B R ，称为单步线性迭代法。

kB 称为迭代矩阵。

若k B 和kf 与k 无关，即(1)(),0,1,k k k +=+=x Bx f称为单步定常线性迭代法。

本章主要讨论具有这种形式的各种迭代方法。

1.1 向量序列和矩阵序列的极限由于nR 中的向量可与nR 的点建立——对应关系，由点列的收敛概念及向量范数的等价性，可得到向量序列的收敛概念。

定义6.1 设(){}k x 为n R 中的向量序列，nx R ∈，如果()lim 0k k x x →∞-=其中为向量范数，则称序列(){}k x 收敛于x ，记为()lim k k x x →∞=。

定理6.1 nR 中的向量序列(){}k x 收敛于nR 中的向量x 当且仅当()lim (1,2,,)k i i k x x i n →∞==其中()()()()1212(,,,),(,,,)k k k k T Tnnx x x x x x x x ==。

数值分析课程实验报告实验名称 线性方程组的迭代解法Ax b =的系数矩阵对角线元素容许误差。

雅可比（Jacobi ）迭代法解方程组的算法描述如下：任取初始向量(0)(0)1(xx =1+，并且 1,2,...,n ，计算 11(ni j ii j ib a a =≠-∑()k x ，结束；否则执行④，则不收敛，终止程序；否则转② 迭代法的算法描述）迭代法中，如果当新的分量求出后，马上用它来代替旧的分量，则可能会更快地接近方程组的准确解。

基于这种设想构造的迭代公式,n ，k = （2）算法可相应地从雅可比（Jacobi ）迭代法改造得到(Gauss-Seidel)迭代得到的值进一()()()1((1k i ii k k i i x b a x x ωω==+-1,2,,n ，2,k =（3）为松弛因子（显然当1ω=塞德尔迭代公式） ()k ix 通常优于旧值(1)k ix -，在将两者加工成松弛值时，自然要求松弛因子1ω>，以尽量发挥新值的优势，这类迭代就称为逐次超松弛迭代法。

SOR 迭代的关键在于选取合适的松弛因子，松弛因子的取值对收敛速度影响很大，但如何选取最佳松弛因子的问题，至今仍未有效解决，在实际计算时，通常依据系数矩阵的特点，并结合以往的经验选取合适的松弛因子。

练习与思考题分析解答(0)(1,1,1,1)x =[ -0.999976, -0.999976, -0.999976, -0.999976]x =[ -0.99999, -0.999991, -0.999992, -0.999993]x =塞德尔迭代算法的收敛速度要比雅可比迭代算法的收敛速度快SOR 迭代实质上是高斯原理和基本方法相同。

如果选择合适的松弛因子，它能够加快收敛速度。

SOR 迭代算法更加普通，当选取一个合适的松弛因子后收敛速度明显加快。

迭代算法将前一步的结果[ -0.99999, -0.999991, -0.999992, -0.999993]x =[ -0.999992, -0.999993, -0.999994, -0.999995]x =[ -0.999993, -0.999994, -0.999995, -0.999995]x =[ -0.999992, -0.999993, -0.999994, -0.999995]x =[ -0.999999, -1.0, -1.0, -1.0]x =[ -0.999999, -1.0, -1.0, -1.0]x =因为为了保证迭代过程收敛，松弛因子1.3左右。

1 / 8数值分析实验六：解线性方程组的迭代法2016113 张威震1 病态线性方程组的求解1.1 问题描述理论的分析表明，求解病态的线性方程组是困难的。

实际情况是否如此，会出现怎样的现象呢？实验内容：考虑方程组Hx=b 的求解，其中系数矩阵H 为Hilbert 矩阵，,,1(),,,1,2,,1i j n n i j H h h i j n i j ⨯===+-这是一个著名的病态问题。

通过首先给定解（例如取为各个分量均为1）再计算出右端b 的办法给出确定的问题。

实验要求：（1）选择问题的维数为6，分别用Gauss 消去法、列主元Gauss 消去法、J 迭代法、GS 迭代法和SOR 迭代法求解方程组，其各自的结果如何？将计算结果与问题的解比较，结论如何？（2）逐步增大问题的维数（至少到100），仍然用上述的方法来解它们，计算的结果如何？计算的结果说明了什么？（3）讨论病态问题求解的算法1.2 算法设计首先编写各种求解方法的函数，Gauss 消去法和列主元高斯消去法使用实验5中编写的函数myGauss.m 即可，Jacobi 迭代法函数文件为myJacobi.m ，GS 迭代法函数文件为myGS.m ，SOR 方法的函数文件为mySOR.m 。

1.3 实验结果1.3.1 不同迭代法球求解方程组的结果比较选择H 为6*6方阵，方程组的精确解为x* = (1, 1, 1, 1, 1, 1)T ，然后用矩阵乘法计算得到b ，再使用Gauss 顺序消去法、Gauss 列主元消去法、Jacobi 迭代法、G-S 迭代法和SOR 方法分别计算得到数值解x1、x2、x3、x4，并计算出各数值解与精确解之间的无穷范数。

Matlab 脚本文件为Experiment6_1.m 。

迭代法的初始解x 0 = (0, 0, 0, 0, 0, 0)T ，收敛准则为||x(k+1)-x(k)||∞<eps=1e-6，SOR方法的松弛因子选择为w=1.3，计算结果如表1。

数值分析第六章线性方程组迭代解法线性方程组是数值分析中的重要内容之一，其求解方法有很多种。

其中一种常用的方法是迭代解法，即通过不断迭代逼近方程组的解。

本文将介绍线性方程组迭代解法的基本思想和常用方法。

线性方程组可以用矩阵形式表示为Ax=b，其中A是系数矩阵，b是常数向量，x是未知向量。

线性方程组的解可以是唯一解，也可以是无穷多个解。

迭代解法的基本思想是通过不断迭代，并利用迭代序列的极限，逼近线性方程组的解。

迭代解法适用于大型的线性方程组，而直接求解法则适用于小型的线性方程组。

常用的迭代解法有雅可比迭代法、高斯-赛德尔迭代法和逐次超松弛迭代法。

雅可比迭代法是最简单的线性方程组迭代解法之一、它的基本思想是将线性方程组的每个方程都单独表示为未知数x的显式函数，然后通过不断迭代求解。

雅可比迭代法的迭代公式为：x(k+1)=D^(-1)(b-(L+U)x(k))其中，D是A的对角元素构成的对角矩阵，L是A的下三角矩阵，U 是A的上三角矩阵，x(k)是第k次迭代的解。

高斯-赛德尔迭代法是雅可比迭代法的改进版。

它的基本思想是将每个方程的解带入到下一个方程中，而不是等到所有方程都迭代完毕后再计算下一组解。

高斯-赛德尔迭代法的迭代公式为：x(k+1)=(D-L)^(-1)(b-Ux(k))其中，D是A的对角矩阵，L是A的下三角矩阵（除去对角线），U是A的上三角矩阵（除去对角线），x(k)是第k次迭代的解。

逐次超松弛迭代法是对高斯-赛德尔迭代法的改进。

它引入了松弛因子w，通过调节松弛因子可以加快收敛速度。

逐次超松弛迭代法的迭代公式为：x(k+1)=(D-wL)^(-1)[(1-w)D+wU]x(k)+w(D-wL)^(-1)b其中，D是A的对角矩阵，L是A的下三角矩阵（除去对角线），U是A的上三角矩阵（除去对角线），w是松弛因子，x(k)是第k次迭代的解。

线性方程组迭代解法需要设置迭代停止准则，通常可以设置迭代次数上限或者设置一个精度要求。

第六章 线性方程组迭代解法要点：（1）线性方程组迭代格式：Jacobi 迭代，G-S 迭代 （2）矩阵范数计算，矩阵谱半径计算（3）线性方程组迭代格式(1)()k k x Bx f +=+的收敛性判断（4）Jacobi 迭代，G-S 迭代收敛的判断 （5）线性方程组的性态 复习题：1、已知线性方程组为123211*********x x x -⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦⎣⎦（1）写出Jacobi 迭代格式和Seidel 迭代格式； （2）写出Jacobi 迭代矩阵和Seidel 迭代矩阵； （3）判别这两种迭代法的收敛性。

解：(1) Jacobi 迭代格式： (1)()()123(1)()()213(1)()()312111222311122k k k k k k k k k x x x x x x x x x +++⎧=-+⎪⎪⎪=--+⎨⎪⎪=+-⎪⎩Gauss-Seidel 迭代格式：(1)()()123(1)(1)()213(1)(1)(1)312111222311122k k k k k k k k k x x x x x x x x x ++++++⎧=-+⎪⎪⎪=--+⎨⎪⎪=+-⎪⎩（2）Jacobi 迭代矩阵：111022()10111022J B D L U -⎛⎫- ⎪ ⎪=+=-- ⎪ ⎪⎪⎝⎭Gauss-Seidel 迭代矩阵：11102211()0221002GS B D L U -⎛⎫- ⎪ ⎪⎪=-=-- ⎪ ⎪⎪- ⎪⎝⎭ （3） 35||4J I B λλλ-=+，得J B的特征值为12,30, 2λλ==±()12J B ρ=>， 可见Jacobi 迭代格式不收敛另外， 21||()2GS I B λλλ-=+，得GS B 的特征值为12,310, 2λλ==-1()12GS B ρ=<， 可见Gauss-Seidel 迭代格式收敛2、设方程组1312123879897x x x x x x x -+=⎧⎪-+=⎨⎪--=⎩试问，是否可以适当调整方程的排列顺序，使得用Gauss-Seidel 迭代法求解时收敛？说明收敛原因解：可通过方程顺序交换，等价为以下方程组1231213979887x x x x x x x --=⎧⎪-+=⎨⎪-+=⎩这样，系数矩阵911190108--⎛⎫⎪- ⎪ ⎪-⎝⎭为严格对角占优矩阵，对该方程组使用Jacobi 迭代和Gauss-Seidel 迭代均收敛3、对方程组⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡43132121x x ，验证Jacobi 迭代法的收敛性，若发散，则说明理由， 并调整方程顺序使得Jacobi 迭代收敛。