您的位置: 首页  >  文章  >  最速下降法和共轭梯度法

最速下降法和共轭梯度法

分类: 文章 • 2023-11-13 19:04:58

方法原理

求解特殊类型(对称正定矩阵A)的线性方程组

Ax=b

二次型引理: 上述问题Ax=b等价于极小化二次型
q(x)=xTAx−2xTb

对于∀x,沿着从x出发的任意v的射线x+tv都可以在t=t^处求得其在该射线上的极小值

q(x+t^v)=q(x)−⟨v,b−Ax⟩2⟨v,Av⟩,t^=⟨v,b−Ax⟩⟨v,Av⟩

可以看出:

  • 对于不满足b−Ax=0的x,总可以有很多方向v使得从x到x+t^v,二次型q(x)的值出现减少,这样的x不能极小化q(x);
  • 对于满足b−Ax=0的x0,q(x)沿着各射线的极值点就在x0处取得.

利用迭代求解Ax=b,利用某种规则在第k次迭代中选取一个方向v(k):

x(k+1)=x(k)+tkv(k),tk=⟨v(k),b−Ax(k)⟩⟨v(k),Av(k)⟩

关键在于如何寻找搜索方向v(k)!!!

最速下降法

搜索方向v(k)使用二次型q在x(k)的负梯度∇q=2Ax−2b

v(k)=b−Ax(k)

但是最速下降法的速度并非最速的,它其实走了很多弯路,实际速度很慢.
最速下降法和共轭梯度法

相关推荐