上次在《共轭梯度法的推导》讲解了共轭梯度法和梯度下降法的推导，本次用实例看一下它们之间的差异。

共轭梯度法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ConjugateGradient1[A_, b_] :=
 Module[{x, r, p, k, \[Alpha], \[Beta], n = Length[b]},
  x[0] = Table[0., n];
  
  r[0] = b - A . x[0];
  p[0] = r[0];
  k = 0;
  Print[Norm[r[k]]/n, ",", x[k]];
  
  While[k < 100,
   \[Alpha][k] = ConjugateTranspose[r[k]] . r[k]/
    ConjugateTranspose[p[k]] . A . p[k];
   x[k + 1] = x[k] + \[Alpha][k] p[k];
   r[k + 1] = r[k] - \[Alpha][k] (A . p[k]);
   
   Print[Norm[r[k + 1]]/n, ",", x[k + 1]];
   If[Norm[r[k + 1]]/n < 10^-6, Break[]];
   
   \[Beta][k] = ConjugateTranspose[r[k + 1]] . r[k + 1]/
    ConjugateTranspose[r[k]] . r[k];
   p[k + 1] = r[k + 1] + \[Beta][k] p[k];
   k++];
  
  x[k + 1]
  ]

梯度下降法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
GradientDescent[A_, b_] :=
 Module[{x, r, k, \[Alpha], n = Length[b]},
  x[0] = Table[0., n];
  
  k = 0;
  
  While[k < 100,
   r[k] = b - A . x[k];
   \[Alpha][k] = ConjugateTranspose[r[k]] . r[k]/
    ConjugateTranspose[r[k]] . A . r[k];
   x[k + 1] = x[k] + \[Alpha][k] r[k];
   
   Print[Norm[r[k]]/n, ",", x[k]];
   If[Norm[r[k]]/n < 10^-6, Break[]];
   k++];
  
  x[k + 1]
  ]

A 是实对称正定矩阵

  • 例 
1
2
3
4
5
A = {{1, 4}, {4, 1}};
b = {9, 6};

f1[x1_, x2_] = 
 Transpose[{x1, x2}] . A . {x1, x2} - 2 Transpose[b] . {x1, x2};

共轭梯度法

In[]:= 
1
ConjugateGradient1[A, b]
Out[]:=

梯度下降法

In[]:= 
1
GradientDescent[A, b]
Out[]:=

明显可以看出共轭梯度法比梯度下降法用了更少的步数达到更高的精度，收敛更快。从下面的图形它们走过的路径也可以看出这一点。绿色的线画的是 函数的等高线，红色箭头是共轭梯度法的路径，黑色箭头是梯度下降法的路径。梯度下降法走的是梯度下降最快的方向，然后走垂直的方向，共轭梯度法走的是共轭方向。就像我们下山的时候，沿着山谷走并不是到达谷底最快的路径。

图中蓝色线还画了函数

的等高线，该函数可以用于推导非实对称正定矩阵时的共轭梯度法，下一次讲解该算法。

请大家多多关注、点赞、收藏、转发，让更多有需要的人可以看到，以后会分享更多实用的算法。

万分感谢！🙏