计算方法与软件应用5

1、三、逐次超松弛迭代法对于大规模的稀疏方程组，迭代和迭代是两种基本迭代方法，并且代表了两种典型的算法：平行算法和串行算法.不足之处是在很多情况下这两种算法的收敛速度较慢，需要进行改进，常见的做法是加入参数（松弛因子）使算法起到加速作用。常见的算法有算法（逐次超松弛法），及算法（同步迭代法）。这两种算法一个是在迭代法基础上发展得到的，一个是在迭代基础上发展得到的。1、算法（逐次超松弛法）由上面的讨论可知，迭代的格式是 现在在上式的每个方程中假如，得到 其一般式是： 上式可以将看成是由加上一个校正量得到。如果在这个校正量前乘上一个因子，则得到：(4.9)或等价于上式右端的括号内正是迭代格式，只是多了

2、个系数，注意到前的系数为，因此迭代法可以看成是迭代法与计算值的一种算术加权平均。如果因子选取的比较合适，它可以起到加速收敛的作用。当=1时，迭代法就是迭代。如果采用矩阵分裂记号(4.9)可以得到： 从而得到算法矩阵表示的紧凑形式 (4.10)其中迭代矩阵=称具有上述迭代格式的迭代法为逐次超松弛法,简称迭代,其中参数称为松弛因子.注: (1)可以证明, 迭代收敛的必要条件是,当时称为亚松弛迭代,而当时,称为超松弛迭代.证明:因迭代的迭代矩阵为 =设矩阵的个特征值为,则 = = = =注意到的定义,有 1 (2) 算法收敛的充分必要条件是.当方程组的系数阵是对称正定时,对的任意算法都收敛,但收敛的

3、速度并不一样,此时我们可以找到最佳的松弛因子 而对一般的线性方程组则要通过反复试验才能求得比较满意的，选得恰当的才能使方法起到加速作用，一般的取值在1与1.7之间. (3) 用简单的编制算法程序如下：建立文件名，内容为：%using SOR iterative to solve linear algebraic equations ax=bfunction y,r,n=sor(a,b,x0,w,e,N)D=diag(diag(a);U=-triu(a,1);L=-tril(a,-1);G=(D-w*L)(1-w)*D+w*U);f=w*(D-w*L)b);y=G*x0+f;n=1;while

4、(norm(y-x0,inf)>=e & n<N) x0=y;y=G*x0+f;n=n+1;endn;y;r=norm(y-x0,inf);为了找到最佳的松弛因子，可以用下面的循环语句：%Finding better relaxation factor wfor i=1:15 w=0.95+i/20;N=8; y,r,n=sor(a,b,x0,w,1e-15,N); h(i)=r;ends,j=min(h);w=0.95+j/20给定 a=78 -2 -12 -14;-2 86 -4 6;-12 -4 72 -8;-14 6 -8 74;b=76;8;112;68;x0=0

5、;0;0;0;e=1e-8试用求解线性方程组ax=b，并给出最佳的松弛因子.解a=78 -2 -12 -14;-2 86 -4 6;-12 -4 72 -8;-14 6 -8 74;b=76;8;112;68;x0=0;0;0;0;e=1e-8;for i=1:15 w=0.95+i/20;N=8; y,r,n=sor(a,b,x0,w,1e-15,N); h(i)=r;ends,j=min(h);w=0.95+j/20w = 1.0500x,r,n=sor(a,b,x0,w,e,20)x = 1.5350 0.1220 1.9752 1.4130r = 2.8979e-009n = 82、算

6、法简介在迭代中,新向量的分量计算次序是从第1个到第个逐个进行的,即 , 在迭代过程中也可以将这个过程倒过来,即从第个到第1个进行计算,其形式为 ,如果将这两种迭代过程交叉使用,即对 称这种迭代法为迭代法，因相应的迭代矩阵较繁，这里不再写出。 设有线性方程组 试写出迭代，迭代，迭代格式解：迭代格式 迭代格式 迭代格式 设有线性方程组试证明：在迭代求解时，用迭代发散，而用迭代收敛。解： 因 =，=，=，=所以，迭代矩阵为=迭代矩阵为=由，得到特征值为：，由，得到特征值为：，所以，迭代发散，迭代收敛。设有线性方程组证明：该方程组用迭代法求解时，对任意的初始向量收敛，而用迭代法时求解时不是关于任意的初

7、始向量收敛证明：因 =，=，=，=，：，即用迭代法求解时，对任意的初始向量收敛，而用迭代法时求解时发散，但这种发散的含义是指此时用迭代发求解时，对某些初始向量收敛，而对某些初始向量却发散。 对线性方程组 ，证明：在用迭代和迭代法求解时，这两种方法要么同时收敛，要么同时发散。证明：因迭代的特征方程即 ，当时，；当时，；当时，综上有迭代的特征方程为 ，即， ，显然，当时，即两种迭代法同时收敛；时，由迭代收敛的充要条件知，两种迭代法都发散。练习题1：设两点边值问题的精确解为现以h为步长划分区间为100等份，用差分近似代替微分，将微分方程离散化为线性方程组，代入初始条件后，得到如下的方程组问题其中，。

8、(1) 分别用J迭代法，G-S迭代法和SOR迭代法求解，并与精确解进行比较；(2) 如果，再求解该问题练习题2：设是一个对称正定矩阵，分别是其最大和最小特征值，对于线性方程组建立迭代法求出的范围使迭代法收敛，并求出最优使迭代法的渐进收敛速度最大。练习题3：对某电路的分析，可以归结为下面的线性方程组，其中R(1,1)=31；R(1,2)=-13；R(1,6)=-10；R(2,1)=-13；R(2,2)=35；R(2,3)=-9；R(2,5)=-11；R(3,2)=-9；R(3,3)=31；R(3,4)=-10；R(4,3)=-10；R(4,4)=79；R(4,5)=-30；R(4,9)=-9；R

9、(5,4)=-30；R(5,5)=57；R(5,6)=-7；R(5,8)=-5；R(6,5)=-7；R(6,6)=47；R(6,7)=-30；R(7,6)=-30；R(7,7)=41；R(8,5)=-5；R(8,8)=27；R(8,9)=-2；R(9,4)=-9；R(9,8)=-2；R(9,9)=29；V=(-15, 27, -23, 0, -20, 12, -7, 7, 10)T其余元素为零。要求：（1）用高斯列主元消去法求解该方程组；（2）用SOR方法迭代求解该方程组，误差，近似最佳松弛因子由试算法确定，设第四章 非线性方程组的数值解法在科学研究与工程计算中的许多问题，都可以归结为非线性方

10、程组的数值求解问题。本章主要介绍求解非线性方程和方程组的基本思想及其数值实现§1 非线性方程组的基本概念 定义4.1.1：含n个变量的n个方程构成的方程组 （4.1）称为非线性方程组，其中是定义在域上关于自变量的实值函数，且中至少有一个是非线性函数，当时，非线性函数构成的方程称为一元非线性方程；如果全是线性函数，则方程组为线性方程组。为了讨论方便，引入非线性方程组的向量形式，记,其中，是从域 到的映射，称为向量值函数。则非线性方程组(4.1)的向量形式可表述为 (4.2)求解非线性方程组问题，就是寻找一个向量,使得多元向量值函数满足，我们称向量为非线性方程组的解。因是非线性函数，所以

11、非线性方程组的求解问题无论在理论上或解法上，都远不如线性方程组成熟和有效。从解的存在唯一性来看，对于线性方程组，只要存在，则其解也是唯一存在的；而非线性方程组解的存在唯一性至今还没有完全解决。从求解的方法上来看，线性方程组可以采用直接法求解，也可以采用迭代法求解；而非线性方程组除了特殊的情况外，直接法几乎是不能使用的，一般只能采用迭代法进行求解。下面将围绕非线性方程组迭代求解的基本问题，即迭代收敛性、收敛速度和计算效率，先研究一元非线性方程的求解，然后再讨论多元非线性方程组的情形。§4.2 一元非线性方程的迭代法求解最简单的非线性方程组一元非线性方程，是求解非线性方程组的基础。本节我

12、们首先介绍用于确定解的范围的直接搜索法；然后再介绍两种迭代方法基本迭代法和牛顿迭代法。一、 非线性方程的直接搜索法 非线性方程的解或根，也称为函数的零点。它在几何上表示函数的图形与横坐标的交点，见下图xyo如果方程在区间内有实根，则称为有根区间；若在上只有一个根，则称为根的隔离区间。对于连续函数，如果它在根的两侧变号，那么可以用搜索法寻找足够小的隔离区间，然后取其中的任意一点（如中点）作为根的近似值。其基本步骤是：（1） 判断的符号，若，则；若，则不妨设（2） 选择合适的步长。如：，向前搜索一步，判断的符号。若，则；若，则可知，这时可取或为的近似值；若，则继续向前搜索一步，判断的符号。重复上述

13、过程，直到与异号，则可知，此时可取该区间内的任意一点作为的近似值。设有方程 试用搜索法寻找长度为0.2的根的隔离区间.解:作函数的图形如下: 从图中可以看出, 函数在左边的一个根的两侧变号.零步长,以为起点,取点列,依次计算它们的函数值,直到相邻的两个值变号,即可得到长度为0.2的隔离区间.具体计算见下表: -1.5 -1.3 -1.1-0.9 -3.125 -1.587 -0.441+0.361从计算可以看出程度为0.2的隔离区间为-1.1,-0.9逐步搜索法的优点是计算简单，缺点是步长很难选择。若过大，近似值的精度较差，若步长足够小，精度是提高了，但计算量却大大增加。因此搜索法是一种效率很

14、低的方法,通常用来求根的粗略估计,把它作为后面要讨论的迭代法的初始值.同时搜索法只适用于一元方程的奇重实根,不能推广到多元情形.如上例中的右边根因两侧不变号,因此不能用搜索法求根.事实上,设是的重根,则在的一个邻域中可表示为 =其中是不小于1的正整数。由此可见，仅当是奇数时才在的两侧变号，因而可以用逐步搜索法求根。搜索法的一种改进的方法是二分法，其基本思想是逐步将有根区间对分，通过判断在小区间端点处的函数值符号进一步搜索有根区间，将有根区间缩到充分小，从而给出满足精度的根的近似值。因时间关系我们不再介绍。 二、非线性方程的不动点迭代法迭代法是一种逐步逼近的方法，它使用一定的公式，反复校正根的近

15、似值，使其达到事先要求的精度。这种方法是解代数方程、超越方程以及方程组等行之有效的数值方法。1、 基本迭代法及其收敛性为了求一元非线性方程 （4.3）的实根,首先将它转化为等价形式 (4.4)如果满足方程,则也满足,反之亦然.称是方程(4.3)的根,是方程(4.4)的不动点.从而求的根的问题转化为求的不动点.一般来说,不可能从中直接得到不动点,需要先给出根的一个猜测值(称为初始值),然后代入方程(4.4)式构造迭代格式 (4.5)由此得到序列.若此序列有极限,即,则就是的不动点,也是方程的根。（4.5）式称为基本迭代法，也称为不动点迭代法，称为迭代函数。由于迭代过程中仅有决定，因此称这种迭代格

16、式为单步法。将方程（4.3）转化为(4.4)的方法有很多，如令等等。迭代函数的不同选择对应不同的迭代法，它们的收敛性可能有很大的差异。当方程有多个解时，同一迭代法的不同初始值也可能收敛到不同的根。现举例如下： 求的一个实根解：将它转化为两种不同的等价形式，及对应的迭代法分别为 （1） （2），由于，即连续函数在区间1，2上变号，从而1，2为有根区间。现取它的中点为初始值，迭代结果列于下表，可以算得此方程有唯一实根=1.32471795724475 0 1 2 11方法（1） 15135720881133086096132471796方法（2）15237500000123964844从计算结果中

17、可以看出，方法（1）收敛，方法（2）发散。 求的根解：将它转化为等价形式 ，得到迭代法 ，取初值迭代结果如下 0 1 2 3 4 5 10151416667141421614142141414214-10-15-1416667-1414216-1414214-1414214这说明，基本迭代法的收敛性取决于迭代函数的构造及初值的选取。下面给出基本迭代法的收敛性基本定理。定理1：设函数在闭区间上连续，并且满足（1） 映内性 ，（2） 压缩性 即存在常数（称为压缩系数），使得 ，则（1） 函数在闭区间上存在唯一的不动点（2） 对于任意的初值，由迭代法生成的点列都在区间中，并且收敛到，即（3） 有误差的估计式 （4。6）证明：（1）设，由的映内性 可以得到 ，由连续函