当前位置：文档之家 › 求解线性逆问题的谱共轭梯度法

求解线性逆问题的谱共轭梯度法

  • 格式：pdf
  • 大小：6.22 MB
  • 文档页数：7

(2 0 1 4 G X N S F F A 1 1 8 0 0 1 ) ， 广西高校中青年教师基础能力提升项
目（ k y 2 0 1 6 Y B 1 6 7 ) 和桂林电子科技大学研究生教育创新计划项 目（ 2 0 1 6 Y J C X 4 6 ) 资助。 通信作者： 王 硕 （ 1987
—），女 ， 讲师， 主要从事最优化方法
收稿日期= 20 1 6 -0 3 -1 5 修 回日期= 20 1 6 -0 4 -1 5 作者简介： 王华军（ 1 9 9 0 —）， 男， 硕士研究生， 主要从事优化算法
在反问题中的应用研究。 * 国家自然科学基金项目 （ 11361018) ， 广西自然科学基金项目
近年来， 文 献 [5-?]用 谱 共 轭 梯 度 法 求 解 线 性 和 非 线 性优化问题.得到很好的数值效果.因此•本文希望把 谱 共 轭 梯 度 法 应 用 到 线 性 逆 问 题 中 .【 拟 解 决 的关 键 问题】 针对线性逆问题， 提出一个新的谱共轭梯度法， 在理论上证明新提共轭梯度法的下降性和全局收敛 性， 并把该方法虛用到卷积方程反潢和图像处理的反 演中.
Abstract
Key words 0
引言
进展】 对于线性逆问题的研究*已有不少数值解法•文 献 .〔 營 : ]提 出 迭 代 T' lkhon。 '#鹰.则化方:法求解该_ 问题s 取得了较好_的数慎效'果 < 文献_[3 ]提出了 L@v_i(|nbe.rg「 M. arquard. t. 方 法 求 .解 该 .间 題 且 在 数 值 试 验 中 ， 用偏_ 差原则作为停止准则， 但 该 方 法 所 需 C P U 时间 较 长 .文 献 [ 4 ] 提 出 并 讨 论 了 一 类 N C P S 逆 问 题 . 【 本研 究切 入点】 谱共轭梯度法是一类非常重要的优化方 法， 他是将谱梯度法和共轭梯度法的思想相结合的一 种方法， 具有迭代简单、 易于编程以及存储要求低等 优点， 所以一般适用于求解太规模无约束优化问题.
w w . cnki. n et/k c m s/d e ta il/4 5 . 1206. G3. 20161121. 1546. 026. htm l
A Spectral Conjugate Gradient Method for Solving Line­ ar Inverse Problems
【 研究意义】 在理论研究和工程实践中， 许多问题 的解决需要根据观测数据来恢复或重构物理介质的 结构信息， 通 常 称 这 类 问 题 为 逆 问 题 . 逆问题分 为 线 性逆问题和非线性逆问题， 其中线性逆问题广泛出现 在地球物理学、 图像处理、 地下水文学、 全球海洋模 拟、 肿瘤检测、 非 破 坏 性 检 测 等 领 域 中 [1].【 前人研究
： In this study?a n e w spectral conjugate gradient m e t h o d is presented to solve linear in­ verse prob l e m s ?w h i c h are transferred into the linear unconstrained optimization with T i k h o n o v
王 华 军 . 王 硕 曹 义 超
求解线性逆问题的谱共轭梯度法+
WANG Huajun.WANG ShuoXAO Yichao
(桂 林 电 子 科 技 大 学 数 学 与 计 算 科 学 学 院 4广 西 桂 林 541004)
(School of M a t h e m a t i c s a nd Computational Science, Guilin University of Electronic T e c h n o l o ­ gy? Guilin, Guangxi? 541004 ?China)
regularization. T h e global convergence of the proposed s c h e m e is analyzed. T h e n e w algorithm is c o m p a r e d with L a n d w e b e r ,T S V D an d T V m e t h o d s , a n d numerical results illustrate the effi­ ciency of this method. ： linear inverse problems,spectral conjugate gradient m e t h o d ?T i k h o n o v regularization
»E - m a il ： o p tim iz a tio n _ z h u @ 1 6 3 . Corrib
416
Guangxi Sciences， Vol. 23 No. 5, October 2016
1
广西科学 G u a n g x i Sciences 2 0 1 6 ， 2 3 ( 5 ) : 4 1 6 〜4 2 1 ， 427
网络优先数字出版时间： 2016-11_21 网络优先数字出版地址： h ttp ://w 【 DOI】 10.
13656/ki.gxkx. 013
摘要： 针对 线 性 逆 问 题 ， 把 原 问 题 的 算 子 方 程 转 化 为 带 有 T ik h o n o v 正 则 项 的 无 约 束 优 化 问 题 ， 提出一个求解线
性逆问题的新谱共轭梯度法， 并证明算法的全局收敛性. 数值结果表明， 新算法是有效的.
关键词 ： 线 性 逆 问 题 谱 共 轭 梯 度 法 T ik h o n o v 正则项 中图分类号： 0224 文献标识码： A 文章编号： 1005-9164(2016)05-0416-06

合集下载

共轭梯度法程序

共轭梯度法程序

一、共轭梯度法共轭梯度法（Conjugate Gradient）是共轭方向法的一种，因为在该方向法中每一个共轭向量都是依靠赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法。

由于此法最先由Fletcher和Reeves （1964）提出了解非线性最优化问题的，因而又称为FR 共轭梯度法。

由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。

共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向d仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便，效果好。

二、共轭梯度法的原理设有目标函数f（X）=1/2X T HX+b T X+c 式1 式中，H作为f（X）的二阶导数矩阵，b为常数矢量，b=[b1,b2,b3,...b n]T 在第k次迭代计算中，从点X（k）出发，沿负梯度方向作一维搜索，得S(K)=-∆f（X（k））式2 X(k+1)=X(k)+ɑ(k)S(k) 式3在式中，ɑ（k）为最优步长。

设与S(k）共轭的下一个方向S(k+1)由点S(k）和点X(k+1)负梯度的线性组合构，即S (k+1)=-∆f （X （k+1））+β(k)S (k) 式4 根据共轭的条件有[S (k)]T ∆2f （X (k)）S (k+1)=0 式5 把式2和式4带入式5，得-[∆f(X (k))]T ∆2f （X (k)）[-∆f （X （k+1））+β(k)S (k) ]=0 式6 对于式1，则在点X (k)和点X (k+1)的梯度可写为∆f(X (k))=HX (k)+b 式7 ∆f （X （k+1）)=HX (k+1)+b 式8 把上面两式相减并将式3代入得ɑ(k)H S (k)=∆f （X （k+1）)-∆f(X (k)) 式9 将式4和式9两边分别相乘，并代入式5得-[∆f （X （k+1）)+β(k)∆f(X (k))]T [∆f （X （k+1）)-∆f(X (k)]=0 式10 将式10展开，并注意到相邻两点梯度间的正交关系，整理后得 β（k ）=22||))((||||))1((||k X f k X f ∆+∆ 式11把式11代入式4和式3，得 S （k+1）=-∆f （X (k)）+β（k ）S （k ）X (k+1)=X （k ）+ɑ（k ）S （k ）由上可见，只要利用相邻两点的梯度就可以构造一个共轭方向。

计算方法——共轭梯度法求解线性方程组

计算方法——共轭梯度法求解线性方程组

x( k 1) x( k ) k d ( k )
(2)
(k)
共轭梯度法中关键的两点是迭代格式(2)中最佳步长k 和搜索方向 d
(k) (k)
的确定。其
中k 可以通过一元函数f(x +d )的极小化来求得，其表达式为公式(3)；取 d (0) = r(0) = b-Ax(0)，则 d(k+1) = r(k+1) +kd(k)，要求 d(k+1)满足 (d(k+1) , Ad(k)) = 0，可得k 的表达 式(4)。
计算方法上机报告
计算方法上机报告
1 共轭梯度法求解线性方程组
1.1 算法原理及程序框图 当线性方程组 Ax = b 的系数矩阵 A 是对称正定矩阵是，可以采用共轭梯度法对该 方程组进行求解，可以证明，式(1)所示的 n 元二次函数 1 f ( x ) x T Ax bT x (1) 2 取得极小值点 x*是方程 Ax = b 的解。共轭梯度法是把求解线性方程组的问题转化为求 解一个与之等价的二次函数极小化的问题。从任意给定的初始点出发，沿一组关于矩 阵 A 的共轭方向进行线性搜索，在无舍入误差的假定下，最多迭代 n 次（其中 n 为矩 阵 A 的阶数） ，就可求得二次函数的极小点，也就求得线性方程组 Ax = b 的解。其迭 代格式为公式(2)。
4
1 1
1 0 ，b 2 1 0 1 1 2
计算方法上机报告
矩阵 A 的阶数取 200 进行求解。 由于该线性方程组的系数矩阵阶数比较大，而且具有一定的规律，因此首先用 matlab 编程将系数矩阵、右端项以及阶数保存在 D 盘根目录的三个文件中（生成系数 矩阵， 右端项以及阶数的程序见附录 2） ， 然后运行共轭梯度法程序进行方程组的求解。 最终的运行结果为图 4 和图 5。程序运行之后 D 盘根目录下生成的文件如图 6 所示。
共轭梯度法反演

共轭梯度法反演


2019年10月29日3时8分
11
二、共轭梯度法反演的基本原理
2.3 共轭梯度法
共轭向量的构造
设有一组n 维彼此关于n×n 的正定对称矩阵A共轭的
向量 d0 d1 ... dn1，能够使我们分别沿着这n个共轭
向量所指的方向各搜索一次,就可以达到极值点x*。
设有一组线性无关的向量u0 u1 ... un1 ,可以通过对
15
二、共轭梯度法反演的基本原理
2.4 共轭梯度法共轭梯度法基本步骤


(xk
)



( xk 1

dk 1 )
' (xk
)T
d k 1

0
由(2)式， ' (xk ) Axk b rk
0 ( Axk b)T dk 1 ( A( xk 1 k dk ) b)T dk 1
考虑线性方程组 Ax b,其中A对称正定
作二次泛函 (x) : Rn R
得目标函数： x

1 2
( Ax,
x)

(b,
x)

1 2
xT
Ax

xT b
(1)
则
解线性方程组Ax b等价于求目标
函数 ( x)的最小值点(极小值点)
2019年10月29日3时8分
6
二、共轭梯度法反演的基本原理
从而， k

rkT pk pkT Apk
(11)
将上式带入(10)式可得：
x*

xn

x0

n 1 i0
riT pi piT Api
di
共轭梯度法总结

共轭梯度法总结

共轭梯度法总结
共轭梯度法总结
一、什么是共轭梯度法
共轭梯度法（Conjugate Gradient Method），是一种用于求解线性方程组的迭代优化算法，它是一种搜索梯度的迭代算法。

共轭梯度法的基本思想是沿梯度的反方向搜索，并在每一步令搜索的方向接近更新的局部梯度。

它是一种非常有效的求解有约束的非线性优化问题的方法，是求解线性方程组的有效算法。

共轭梯度法可以看作是一种极小化函数的迭代方法，它最主要的思想是不断更新梯度的方向，从而寻找函数值最小的点。

二、共轭梯度法的原理
共轭梯度法是一种迭代优化算法，它以凸二次型函数为例，可以用来求解最小值问题。

它的基本思想是：
（1）首先求得函数的梯度，即每一步优化的搜索方向，使梯度变为最小；
（2）以梯度的反方向搜索，令搜索的方向接近更新的局部梯度，而不是与旧的梯度成正比的步长；
（3）逐步更新搜索的方向为新的梯度；
（4）重复这个过程，直到所有的自变量满足限制条件。

三、共轭梯度法的优缺点
共轭梯度法最大的优点是它具有收敛速度快，可以在有限的迭代步数内收敛到最优解；另外，它还具有计算量小，不需要计算精确的
Hessian矩阵的优点。

共轭梯度法的缺点是它不能用来求解非凸优化问题，因为它只能求解凸优化问题；另外，它也不能用于强不可约的优化问题。