共轭梯度法

共轭梯度法 最速下降法 1.最速下降方向 函数f(x)在点x处沿方向d的变化率可用方向导数来 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示。对于可微函数，方向导数等 于梯度与方向的内积，即: TDf(x;d) = ?f(x)d, 因此，求函数f(x)在点x处的下降最快的方向，可归结为求解下列非线性规划: Tmin ?f(x)d s.t. ||d|| ? 1 当 d = -?f(x) / ||?f(x)|| 时等号成立。因此，在点x处沿上式所定义的方向变化率最小，即负梯度方向为最速下降方 向。 2.最速下降算法 最速下降法的迭代公式是 (k+1)(k)(k)x = x + λd , k(k)(k)(k)其中d是从x出发的搜索方向，这里取在x处的最速下降方向，即 (k)d = -?f(x). (k)(k)λ是从x出发沿方向d进行一维搜索的步长，即λ满足 kk(k)(k)(k)(k)f(x + λd) = min f(x+λd) (λ?0). k 计算步骤如下: n(1) (1)给定初点x? R，允许误差ε> 0， 置k = 1。 (k)(2)计算搜索方向d = -?f(x)。 (k)(k)(k)(3)若||d|| ? ε，则停止计算;否则，从x出发，沿d进行一维搜索，求λ，使 k(k)(k)(k)(k)f(x + λd) = min f(x+λd) (λ?0). k(k+1)(k)(k)(4)令x = x + λd ，置k = k + 1，转步骤(2)。 k 共轭梯度法 1.共轭方向 无约束问题最优化方法的核心问题是选择搜索方向。 以正定二次函数为例，来观察两个方向关于矩阵,共轭的几何意义。 设有二次函数: Tf(x) = 1/2 (x - x*)A(x - x*) , 其中A是n×n对称正定矩阵，x*是一个定点，函数f(x)的等值面 T1/2 (x - x*)A(x - x*) = c 是以x*为中心的椭球面，由于 ?f(x*) = A(x - x*) = 0， A正定，因此x*是f(x)的极小点。 (1)(1)设x是在某个等值面上的一点，该等值面在点x处的法向量 (1)(1)?f(x) = A(x - x*)。 (1)(1)又设d是这个等值面在d处的一个切向量。记作 (1)(2)d = x* - x。 (1)(1)(1)T(1)自然，d与?f(x)正交，即d?f(x) = 0，因此有 (1)T(2)dAd = 0， 即等值面上一点处的切向量与由这一点指向极小点的向量关于A共轭。 (1)(2)由此可知，极小化式所定义的二次函数，若依次沿着d和d进行一维搜索，则经两次迭代必达到极小点。 1.共轭梯度法 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出的。后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优化方法。 Fletcher-Reeves共轭梯度法，简称FR法。 共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜素，求出目标函数的极小点。根据共轭方向基本性质，这种方法具有二次终止性。 对于二次凸函数的共轭梯度法: TTmin f(x) = 1/2 xAx + bx + c, n其中x? R，A是对称正定矩阵，c是常数。 具体求解方法如下: (1)首先，任意给定一个初始点x，计算出目标函数f(x)在这点的梯度，若||g|| = 0，则停1止计算;否则，令 (1)(1)d = -?f(x) = -g。 1(1)(2)(2)(1)沿方向d搜索，得到点x。计算在x处的梯度，若||g|| ? 0，则利用-g和d构造22(2)(2)第2个搜索方向d，在沿d搜索。 (k)(k)(k)(k)一般地，若已知点x和搜索方向d，则从x出发，沿d进行搜索，得到 (k+1)(k)(k)x = x + λd , k 其中步长λ满足 k(k)(k)(k)(k)f(x + λd) = min f(x+λd)。 k 此时可求出λ的显示表达 k (k+1)(k)计算f(x)在x处的梯度。若||g|| = 0，则停止计算;否则，用-g和d构造下一个k+1k+1(k+1)(k+1)(k)搜索方向d，并使d和d关于A共轭。按此设想，令 (k+1)(k)d = -g + βd， k+1k(k)T上式两端左乘dA，并令 (k)T(k+1)(k)T(k)T(k)dAd = -dAg + βdAd = 0， k+1k 由此得到 (k)T(k)T(k)β = dAg / dAd。 kk+1(k+1)(k+1)再从x出发，沿方向d搜索。 在FR法中，初始搜索方向必须取最速下降方向，这一点决不可忽视。因子β可以简k22化为:β = ||g|| / ||g||。 kk+1k 3.非线性共轭梯度 当目标函数是高于二次的连续函数(即目标函数的梯度存在)时，其对应的解方程是非线性方程，非线性问题的目标函数可能存在局部极值，并且破坏了二次截止性，共轭梯度法需要在两个方面加以改进后，仍然可以用于实际的反演计算，但共轭梯度法不能确保收敛到全局极值。 (1)首先是共轭梯度法不能在n维空间内依靠n步搜索到达极值点，需要重启共轭梯度法，继续迭代，以完成搜索极值点的工作。 (2)在目标函数复杂，在计算时，由于需要局部线性化，需计算Hessian矩阵A，且计算工作量比较大，矩阵A也有可能是病态的。Fletcher和Reeves的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 最为常用，抛弃了矩阵A的计算，具体形式如下: 式中g和g分别为第k-1和第k次搜索是计算出来的目标函数的梯度。 k-1k 第五章 共轭梯度法 大家已经看到，在使用SOR方法求解线性方程组时，需要确定松驰因子，只有系数矩阵具有较好的性质时，才有可能找到最佳松驰因子，而且计算 时还需要求得对应的Jacobi矩阵B的谱半径，这常常是非常困难的。 这一章，我们介绍一种不需要确定任何参数的求解对称正定线性方程组的方法——共轭梯度法(或简称CG法)。它是50年代初期由Hestenes和Stiefel首先提出的，近20年来有关的研究得到了前所未有的发展，目前有关的方法和 理论已经相当成熟，并且已经成为求解大型稀疏线性方程组最受欢迎的一类方法。 共轭梯度法可由多种途径引入，这里我们将采用较为直观的最优化问题来引入。为此，我们先来介绍最速下降法。 5.1 最速下降法 考虑线性方程组 (5.1.1) 的求解问题。其中是给定的阶对称正定矩阵，是给定的维向量，是待求的维向量。为此，我们定义二次泛函 (5.1.2) 定理5.1.1 设对称正定，求解方程组等价于求二次泛函的极小点。 证明 直接计算可得 令，则有 若在某点处达到极小，则必有，从而有，即是方程组的解。 反之，若是方程组的解，即 于是对任一向量有 注意到A的正定性，则，因此，即是泛函的极小点。 定理证毕 这样，求解线性方程组的问题就转化为求二次泛函的极小点的问题。求二次函数的极小值问题，通常的做法就好象盲人下山那样，先任意给定一个初始向量，确定一个下山的方向，沿着经过点而方向为的直线找一个点 使得对所有实数有 也就是说，在这条直线上，使达到极小。然后从出发，再确定一个下山的方向，沿直线再找一个使得在点达到极小，即 如此等等。于是得到一串 和 ， 我们称为搜索方向，为步长。一般情况下是，先在点找下山方向，再在直线上确定步长使 ， 最后求出. 对不同的确定搜索方向和步长的方法，就给出各种不同的算法。 我们先考虑如何确定步长。设从出发，已经选定了下山方向为。我们现在的任务是，在直线上确定使得在上达到极小。为此，令 其中 由初等微分学的理论知，由方程 所确定的即为所求的步长，即 . (5.1.3) 步长确定以后，即可算法 . 那么是否小于呢,因为 因此，只要，就有 再考虑如何确定下山方向，我们知道增加最快的方向是梯度方向，因此，负梯度方向应该是减小最快的方向，于是最简单而直观的做法是选取为负梯度方向，即这样便得到了如下算法: 算法5.1.1 (解对称正定方程组:最速下降法) 对于最速下降法有如下的收敛性定理。 定理5.1.2 设的特征值为，则由上述算产生的序列满足 ， 其中 为了证明这一定理，我们先证一个引理。 引理5.1.1设的特征值为，是的一个实系数多项式，则 证明 设是的对应于的特征向量所构成的的一 组标准正交基，则对应任意的的有，从而有 于是 引理证毕 定理5.1.2的证明 由满足 ， 并注意到 (5.1.4) 由(5.1.4)得 于是有 (5.1.5) 对任意的成立。记，应用引理5.1.1，从(5.1.5)可得 (5.1.6) 对一切成立，再利用Chebyshev极小极大特征定理知，使取极小的充分必要条件是在区间上至少含有2个轮流为正负的偏差点。由于的线性性知，的交错点组恰好含有两个点，而且为和. 即 ，于是得到，从而 . (5.1.7) 将(5.1.7)代入(5.1.6)即得 . 定理证明 定理5.1.2表明，从任一初始向量出发，由最速下降法产生的点列总是收敛到方程组(5.1.1)的解，其收敛的快慢由的大小来决定。 虽然最速下降法简单易用，又可以充分利用的稀疏性，但由于当时收敛速度变得非常之慢，因此很少用于实际计算。然而它提示了一种重要的思想，开辟了一条全新的求解线性方程组的途径。例如把上述方法稍加改进，就可得到著名的共轭梯度法。 5.2 共轭梯度法及其基本性质 5.2.1 预备知识 定义1 设是对称正定矩阵。称是A-共轭的，是指 性质1 设有是彼此共轭的维向量，即 则一定是线性无关的。 ,证明,若有一组数满足 则对一切一定有 注意到，由此得出:即所有的,,(因此，是线性无关的( 性质, 设向量是线性无关的向量组，则可通过它们的线性组合得出一组向量，而是两两共轭的( ,证明,我们用构造法来证实上面的结论( ,,:取; ,,:令，取( „„ ,m:令 取 容易验证:符合性质,的要求( 性质,设是两两,,共轭的，是任意指定的向量，那么从出发，逐次沿方向搜索求的极小值，所得序列，满足: ( ,证明,由下山算法可知，从出发，沿方向搜索，获得 从而 性质,设是两两,共轭的，则从任意指定的出发，依次沿搜索，所得序列满足: (,) (,)，其中是方程组(5.1.1)的解( ,证明,(,)是性质,的直接推论，显然成立( (,)由于是两两,共轭的，故是线性无关的(所以对于向量可用线性表出，即存在一组数使 由于及，得出 ， 于是，再由得出 于是，与得出一样地，我们可以陆续得出: 对比和的表达式可知， 证明完毕 性质,是性质,的直接推论(但它给出了一种求(,.,.,)的算法，这种算法称之为共轭方向法(结合性质,，我们可以得到如下的性质,( 性质,设是上的一组线性无关的向量，则从任意指定的 出发，按以下迭代产生的序列: ,,:取，，; ,,:计算，取; 计算，得出; 如此进行下去，直到第n步: ,n:计算取 计算，得出( 显然: 根据性质,可知，不论采用什么方法，只要能够构造个两两,共轭的向量作为搜索方向，从任一初始向量出发，依次沿两两,共轭的方向进行搜索，经步迭代后，便可得到正定方程组的解( 5.2.2 共轭梯度法 算法步骤如下: ,预置步,任意，计算，并令取:指定算法终止 常数，置，进入主步; ,主步, (,)如果，终止算法，输出;否则下行; (,)计算: (,)计算: (,)置，转入(,)( 定理,.2.1 由共轭梯度法得到的向量组和具有如下性质: (,) (,) (,) (,)，其中 (5.2.1) 通常称之为Krylov子空间( ,证明,用归纳法(当时，因为 ， 因此定理的结论成立(现在假设定理的结论对成立，我们来证明其对也成立( 利用等式及归纳假设，有 又由于 ， 故定理的结论(,)对成立( 利用归纳假定有 而由(,)所证知，与上述子空间正交，从而有定理的结论(,)对也成立( 利用等式 和 ， 并利用归纳法假定和(,)所证之结论，就有 ( 成立;而由的定义得 这样，定理的结论(,)对也成立( 由归纳法假定知 进而 于是 再注意到(,)和(,)所证的结论表明，向量组和都是线性无关的，因此定理的结论(,)对同样成立( 定理证毕 定理5.2.1表明，向量和分别是Krylov子空间 的正交基和共轭正交基(由此可见，共轭梯度法最多步便可得到方程组的解(因此，理论上来讲，共轭梯度法是直接法( 定理5.2.2 用共轭梯度法计算得到的近似解满足 (5.2.,) 或 (5.2.,) 其中，是方程组的解，是由(5.2.1)所定义的Krylov子空间( 证明 注意到:，则(5.2.2)和(5.2.3)是等价的，因此我们下面只证明(5.2.3)成立( 假定共轭梯度法计算到步出现，那么有 此外，对计算过程中的任一步，有 设是属于的任一向量，则由定理5.2.1的(,)知，可以表示为 ， 于是 而 ， 再利用定理5.2.1的(,)就可以推出 于是定理得证( 定理证毕 由定理5.2.1，我们容易得出 由此可得 (5.2.4) 另外，从理论上讲，该迭代法经次迭代，便能得到精确解(但考虑到计算误差，可以作为无限迭代算法进行计算，直到为止( 从而，我们得到如下实用的共轭梯度算法: ,预置步,任意，计算，并令取:指定算法终止常数，置，进入主步; ,主步,(,)计算:， (,)如果，转入(3)(否则，终止算法，输出计算结果 (,)计算: (,)置，转入(1) 注:在算法,主步,中，引入变量，及，可以简 化计算。 结合程序设计的特点，共轭梯度法可改为如下实用形式: 算法,?,?,(解对称正定方程组:实用共轭梯度法) ; while and if else end end 共轭梯度法作为一种实用的迭代法，它主要有下面的优点: 算法中，系数矩阵,的作用仅仅是用来由已知向量产生向量 ，这不仅可充分利用,的稀疏性，而且对某些提供矩阵, 较为困难而由已知向量产生向量又十分方便的应用问题 是很有益的; 不需要预先估计任何参数就可以计算，这一点不像,,,等; 每次迭代所需的计算，主要是向量之间的运算，便于并行化。 5.2.3 收敛性分析 将共轭梯度法作为一种迭代法，它的收敛性怎样呢,这是本节下面主要讨论的问题: 而且，则共轭梯度法至多迭代步定理,.2.3 如果 即可得到方程组的精确解。 证明 注意到蕴含着子空间 的维数不会超过，由定理,.2.1即知定理的结论成立。 定理证毕 定理5?2?3表明，若线性方程组(5?1?1)的系数矩阵与单位相关一个秩的矩阵，而且很小时，则共轭梯度法将会收敛得很快。 定理5?2?4 用共轭梯度法求得的有如下的误差估计 (5?2?5) 其中 证明 由定理5?2?1可知，对任意的，有 记，则是常数项为1的次实系数多项式。令为所有常数项为1的次数不超过的实系数多项式的全体，则由定理5?2?2和引理5?1?1得 其中是的特征值。由Chebyshev多项式逼近定理及Chebyshev多项式的性质，定义在[-1，1]区间上的次Chebyshev多项式: 是所有常数项为1的次数不超过的实系数多项式中，在[-1，1]上与“0”的偏差值最小的多项式。且偏差值为1，对应的交错点组为: 。因此，多项式 是中在上与“0”的偏差值最小的多项式。即 于是，我们有 因此，定理得证。 定理证毕 ?2?5所给出的估计是十分粗糙的，而且实际计算时其收敛速度虽然定理5 往往要比这个估计快得多，但是它却提示了共轭梯度法的一个重要的性质:只要线性方程组(5?1?1)的系数矩阵是十分良态的(即)，则共轭梯度法就会收敛的很快。 5?4 预先共轭梯度法 上节已经证明，当线性方程组(5?1?1)的系数矩阵仅有少数几个互不相同的特征值或者非常良态时，共轭梯度法就会收敛的非常之快，这就促使我们在应用共轭梯度法时，首先应设法将(5?1?1)转化为一个系数矩阵仅有少数几个互不相等的特征值或者非常良态的等价方程组，然后再应用共轭梯度法于转化后的方程组。预先共轭梯度法正是基于这一基本思想的一种算法。它是先将(5?1?1)转化为 (5?4?1) 其中，这里要求是对称正定的，我们的目的是通过的选择，使具有我们所希望的良好性质。然后应用算法5?2?1于(5?4?1)，可得 (5?4?2) 其中是任意给定的初始向量， 按照上述公式直接迭代，需要事先教育处和，而且还需将迭代得到的近似解通过变换变成方程组(5?1?1)的近似解。实际上这些都是不必要的，令 并记，代入(5?4?2)的各式，整理后即得 其中是任意给定的初始向量， 这样，就得到了如下算法。 算法5?4?1(解对称正定方程组:预先共轭梯度法) 这一算法称作预先共轭梯度法，也叫做预条件共轭梯度法，简称PCG法，其中的矩阵M称作预先矩阵。 利用共轭梯度法的性质容易导出预先共轭梯度法具有如下性质: 残向量是相互正交的，即; 方向向量是相互正交的，即; 近似解向量满足 其中分别是的最大和最小特征值。 预先共轭梯度法成功与否，关键在于预优矩阵M是否选择合适。一个好的预优矩阵自然应该具有如下的特征: (1)是对称正定的; (2)是稀疏的; (3)仅有少数几个互不相同特征值或者其特征值集中在 某点附近; 形如方程组易于求解。 当然，对于一般的线性方程组要选择一个同时满足上述四个条件的预优矩阵 往往是十分困难的，然而对于具体的实际应用问题经常可以获得巨大的成功。下面我们简要地介绍几种常用的预优矩阵的选取技巧。 (1)对角预优矩阵。如果线性方程组的系数矩阵A的对角元素相差较大，则可取 作为预优矩阵，常常会使收敛速度大大提高。推而广之，若 ， 其中是易于求逆的方阵，则可取 (2)不完全Cholesky因子预优矩阵。这是一种非常重要的预优技巧，它是先求系数矩阵的不完全Cholesky分解: ， 其中是单位下三角矩阵，然后作为预优矩阵。由于分解中有一个剩余矩阵可供选择，所以我们就可要求具有某种需要的稀疏性，例如，与 具有相同的稀疏性。当然，要使得到的预优矩阵有效，还需使尽可能地接近。这样得到的预优矩阵的缺点是:在求解时需要解两个三角方程组，不利于并行化(因解三角形方程组的并行效率是很低的)。 (3)多项式预优矩阵。由于预优矩阵实质上是系数矩阵的某种近似，因此我们可将方程组的解看作是的近似。求近似解的一种最自然的方法就是利用上一章所介绍的古典迭代法: (5?4?3) 其中假定是一种较好的分裂。记，那么我们就可取 作为其近似解，从而就可取 作为预优矩阵。因为它是矩阵的多项式，因此称之为多项式预优矩阵。实际计算时，并不需要将真的计算出来，只需由迭代格式(5?4?3)产生即可。因此，这一方法特别有利于并行化。 5?5 Krylov子空间法 这一节，我们简要地介绍一下如何利用共轭梯度法的基本思想去求解一般的线性方程组 (5?5?1) 这里仅假定是非奇异的。由于篇幅所限，我们仅介绍其基本思想，详细细节读者可参阅有关文献。 5?5?1 正则化方法 类似于利用平方根法求解最小二乘问题，我们可以应用共轭梯度法于对称正定方程组 来求解方程组(5?5?1)。当然要想加速收敛，还需与预优化技术结合使用才行。虽然这一方法简单易行，而且对于一些没有什么特殊结构的线性方程组来说常常是有效的，然而当A病态时其收敛速度变得非常之慢，这是因为此时的正则化方程组通常是十分病态的(因会很大)。 5?5?2 残量极小化方法 为了避免正则化方法的缺点，近年来人们一直致力于寻找其收敛速度依赖于A的条件数而不是其平方的有效方法，并得到了不少各具千秋的方法。粗略地讲，这些方法大致可分为两类:残量极小化方法和残量正交化方法。 大家已经知道，用共轭梯度法求解对称正定线性方程组的第次迭代实质上是求使得 (5?5?2) 当并非对称正定矩阵时，就不一定有极小值，因此直接用共轭梯度法来求解一般线性方程组是行不通的，然而这种思想却是可以推广到一般情形的。残量极小化方法就是求使得 采用不同的方法来求解这一优化问题，就会得到求解方程组(5?5?1)的各种不同的方法，其中有代表性的方法主要有两种:一种是用于求解不定线性方程组的极小残量法，即所谓MINRES方法，详见[14];另一种是求解非对称线性方程组的广义极小残量法，即所谓GMRES方法，详见[16]。 5?5?3 残量正交化方法 容易证明，当对称正定时，(5?5?2)成立的充分必要条件中 残量正交化方法就是从这一条件出发来构造求解方程组(5?5?1)的迭代方法的，这方面较为典型的方法有:用于求解对称不定线性方程组的SYMMLQ方法(详见[14])和用于求解非对称线性方程组的Arnoldi方法(详见[16])。