线性方程组的迭代法应用及牛顿迭代法的改进.doc

线性方程组的迭代法应用及牛顿迭代法的改进摘要: 迭代解法就是通过逐次迭代逼近来得到近似解的方法。由于从不同的问题而导出的线性代数方程组的系数矩阵不同，因此对于大型稀疏矩阵所对应线性代数方程组，用迭代法求解。本文论述了Jacobi法，Gauss-Seidel法，逐次超松弛法这三种迭代法，并在此基础上对牛顿型的方法进行了改进，从而使算法更为精确方便。关键词:线性方程组，牛顿迭代法，Jacobi法，Gauss-Seidel法，逐次超松弛法1.线性方程组迭代法1.1线性方程组的迭代解法的基本思想迭代法求解基本思想:从某一初始向量X（0）=x1(0) ,x2(0) ,xn(0) 出发，按某种迭代规则，不断地对前一次近似值进行修改，形成近似解的向量X(k)。当近似解X(k) =x1(k) ,x2(k) ,xn(k) 收敛于方程组的精确解向量X* =x1*,x2*,xn*时，满足给定精度要求的近似解向量X(k)可作为X*的数值解。 1.2 线性方程组的迭代法主要研究的三个问题(1) 如何构造迭代公式 (2) 向量数列X(k)的收敛条件 (3) 迭代的结束和误差估计解线性方程组的迭代解法主要有简单迭代法、 Gauss-Seidel法和SOR法。简单迭代法又称同时代换法或Jacobi法，是最简单的解线性方程组的迭代解法也是其他解法的基础。1.3Jacobi 迭代法设方程组点系数矩阵满足条件，i=0,1,2, n。把A分解为A=D+L+U 在迭代法一般形式中，取N=D, P=-(L+U)形成以下迭代公式 k=0，1， （2-1）其中任取。故上述迭代公式（2-1）称为Jacobi迭代法，又称简单迭代法，它的迭代矩阵是因，故Jacobi迭代法（2-1）的分量形式是，i=0,1,2, n k=0，1，1.4 Gauss-Seidel法解线性方程组的Gauss-Seidel法简称Seidel法，是对简单迭代法（Jacobi迭代法）点改进迭代公式在Jacobi迭代法点基础上可提出如下迭代公式 （3-1）其中 第i个式子为 i=1,2, n称为（3-1）Gauss-Seidel迭代公式由Seidel迭代公式（3-1）可以看出，在第k+1次迭代进行点过程中，因X点各个分量xi,i=1,2, ,n是逐个由迭代公式算出的，在计算分量xi(k+1) 时，序号在i之前点新分量x1(k+1), x2(k+1) , xi-1(k+1) 也已求出。Jacobi迭代公式等号的右边未采用这些新分量点值，而是全部使用老分量xj(k)的值计算xi(k+1) 。当迭代过程收敛时，这些新分量一般较老分量更接近于真值x1* ,x2*,xi-1*,若使用新分量代替老分量进行迭代，则可能使迭代过程加速，Seidel迭代法正是这样做的。由等价方程组构造迭代公式 i=1，2，n1.5逐次超松弛法逐次超松弛法（successive over relaxation method）简称SOR法，是对Gauss-Seidel迭代法点进一步改进而得到点一种加速迭代法。对于判定可收敛点迭代过程，使用SOR法可进一步加速收敛过程。设方程组点系数矩阵A满足aii0，i=1，2，n。把A分解为其中0称为松弛因子。在迭代法一般形式中，取 形成以下的迭代公式 k=0,1其中任选经化简得SOR方法实际计算公式为i=1，2，n；k=0，1，2.牛顿方法的改进对于函数f(x),假定已给出极小点的一个较好的近似点，则在处将f(x)泰勒展开到二次项，得二次函数。按极值条件得的极小点，用它作为的第一个近似点。然后再在处进行泰勒展开，并求得第二个近似点。如此迭代下去，得到一维情况下的牛顿迭代公式 (k=0,1,2,)对多元函数f(x),设为f(x)极小点的一个近似值，在处将f(x)进行泰勒展开，保留到二次项得，式中 f(x)在处的海赛矩阵。设为的极小点，它作为f(x)极小点的下一个近似点，根据极值必要条件即得 （k=0,1,2，）上式为多元函数求极值的牛顿法迭代公式。 对于二次函数，f(x)的上述泰勒展开式不是近似的，而是精确地。海赛矩阵是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可以找到极小点。因为若某一迭代法能使二次型函数在有限次迭代内达到极小点，则称此迭代方法是二次收敛的，因此牛顿方法是二次收敛的。从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿法公式，有时会使函数值上升，即出现现象。为此对上述牛顿方法进行改进，引入数学规划法的概念。如果把看作是一个搜索方向，则采取如下的迭代公式 （k=0,1,2,）式中 沿牛顿方向进行以为搜索的最佳步长可通过如下极小化过程求得。由于此种方法每次迭代都在牛顿方向上进行一维搜索，这就避免了迭代后函数值上升的现象，从而保持了牛顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求。其计算步骤如下：（1） 给定初始点，收敛精度，置。（2）计算。（3） 求，其中为沿进行一维搜索的最佳步长。（4） 检查收敛精度。若则，停机；否则，置，返回到2进行搜索。3 总结通过上述的分析，推导，论证，我们更好