最优化方法:共轭梯度法(Conjugate Gradient)
http://blog.csdn.net/pipisorry/article/details/39891197
共轭梯度法(Conjugate Gradient)
共轭梯度法(英语:Conjugate gradient method)。是求解数学特定线性方程组的数值解的方法。当中那些矩阵为对称和正定。共轭梯度法是一个迭代方法。它适用于稀疏矩阵线性方程组,由于这些系统对于像Cholesky分解这种直接方法太大了。这种方程组在数值求解偏微分方程时非经常见。
共轭梯度法也能够用于求解无约束的最优化问题。
在数值线性代数中,共轭梯度法是一种求解对称正定线性方程组的迭代方法。
共轭梯度法能够从不同的角度推导而得,包含作为求解最优化问题的共轭方向法的特例,以及作为求解特征值问题的Arnoldi/Lanczos迭代的变种。
title=%E5%8F%8C%E5%85%B1%E8%BD%AD%E6%A2%AF%E5%BA%A6%E6%B3%95&action=edit&redlink=1" class="new" title="双共轭梯度法(页面不存在)">双共轭梯度法
基础
共轭向量
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcGlwaXNvcnJ5/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" width="607" height="154" alt="" />
显然,共轭向量是线性无关向量.
初等变分原理
最速下降算法的有关性质
范数的‖・‖A的定义为‖x‖A=(Ax,x)。
上面定理表明,最速下降法从不论什么一向量x(0)出发,迭代产生的数列总是收敛到原方程Ax=b的解.而收敛速度的快慢则由A的特征值分布所决定.当A的最小特征值和最大特征值相差非常大时λ1<<λn,最速下降法收敛速度非常慢,非常少用于实际计算.
分析最速下降法收敛较慢的原因,能够发现,负梯度方向从局部来看是二次函数的最快下降方向,可是从总体来看,却并不是最好.对于对称正定矩阵A,共轭梯度法考虑选择关于A共轭的向量p1,p2,...取代最速(0)下降法中的负梯度方向,使迭代法对随意给定的初始点x具有有限步收敛性,即经有限步就能够(在理论上)得到问题的准确解.
共轭梯度算法
计算共轭梯度算法同一时候构造出关于A共轭的向量pi
求解Ax = b的算法。当中A是实对称正定矩阵。
- x0 := 0
- k := 0
- r0 := b-Ax
- repeat until rk is "sufficiently small":
- k := k + 1
- if k = 1
- p1 := r0
- else
- pk:=rk− 1+rk− 1⊤ rk− 1rk− 2⊤ rk− 2 pk− 1{\displaystyle p_{k}:=r_{k-1}+{\frac {r_{k-1}^{\top }r_{k-1}}{r_{k-2}^{\top }r_{k-2}}}~p_{k-1}}
- end if
- α k:=rk− 1⊤ rk− 1pk⊤ Apk{\displaystyle \alpha _{k}:={\frac {r_{k-1}^{\top }r_{k-1}}{p_{k}^{\top }Ap_{k}}}}
- xk := xk-1 + αk pk
- rk := rk-1 - αk A pk
- end repeat
- 结果为xk
- 或者
-
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcGlwaXNvcnJ5/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />
共轭梯度法评价
其长处是所需存储量小,具有步收敛性。稳定性高,并且不须要不论什么外来參数。
from:http://blog.csdn.net/pipisorry/article/details/39891197
ref: [wiki 共轭梯度法] [wiki 共轭梯度法的推导]
[数值分析 钟尔杰]
最新文章
- SpringMVC学习(一)
- PHP版微信公共平台消息主动推送,突破订阅号一天只能发送一条信息限制
- Java——Swing
- [CareerCup] 18.13 Largest Rectangle of Letters
- 回车键转tab键
- ha456.jar打开dump文件报Unsupported major.minor version 51.0异常
- .net core 1.0 Web MVC 自定义认证过程
- mysql 怎么登录
- OSGi 对软件复杂度的影响
- LCIS tyvj1071 DP优化
- Java学习笔记--Swing用户界面组件
- C语言读写伯克利DB 3
- HashMap的扩容机制---resize()
- vue路由\导航刷新后:ative\localStorage\url截取参数
- Spring学习14-源码下载地址
- Gridview各种功能+AspNetPager+Ajax实现无刷新存储过程分页 (留着用)
- Python中的相对文件路径的调用
- December 14th 2016 Week 51st Wednesday
- memcached安装【转】
- jxls-2.x导出excel入门——基本操作
热门文章
- 微信小程序开发-滑动操作
- 微软BI 之SSRS 系列 - 在 Cube 中通过 MDX 查询实现基于父子递归关系的汇总报表
- SQLServer中char、varchar、nchar、nvarchar的区别
- 算法笔记_204:第四届蓝桥杯软件类决赛真题(Java语言C组)
- string format 格式化小数位
- MongoDB副本集配置系列四:节点的关闭顺序
- 在Ubuntu上安装pyenv 相关问题Common build problems
- iOS 9 时代,iOS 7 占比接近 10% 该何去何从?
- Jmeter-maven-plugin高级配置之选择测试脚本(转)
- WD backup西部盘数据备份