(六)最速下降法

news/2024/4/16 3:48:34

本文主要内容如下:

  • 1. 最速下降法
  • 2. 抛物型多元二次函数优化问题的步长选取
  • 3. 抛物型多元二次函数等值线/面的几何分析
  • 4. 基于最速下降法的 “变步长Richardson 迭代法” 的收敛性分析

1. 最速下降法

数值求解极小值问题的基本思想在于从给定的初始点 x ⃗ 0 \vec{x}_0 x 0 出发,沿某一搜索方向 d ⃗ 0 \vec{d}_0 d 0 进行搜索,同时通过确定最佳步长 α 0 \alpha_0 α0 使函数值沿该搜索方向下降最大。依此方式不断进行,形成函数值下降的迭代算法,即:
x ⃗ k + 1 = x ⃗ k + α k d ⃗ k ( k = 0 , 1 , 2 , … ) f ( x ⃗ k + 1 ) < f ( x ⃗ k ) \vec{x}_{k+1}=\vec{x}_k+\alpha_k\vec{d}_k\ (k=0,1,2,\dots)\\\ \\ f(\vec{x}_{k+1})<f(\vec{x}_k) x k+1=x k+αkd k (k=0,1,2,) f(x k+1)<f(x k)
对于任意的 n n n 元函数 f ( x ⃗ ) ( x ⃗ ∈ R n ) f(\vec{x})\ (\vec{x}\in\mathbb{R}^n) f(x ) (x Rn) 的方向导数(反映函数在当前位置沿任意方向的变化快慢):
d f ( x ⃗ ) d r ⃗ ∣ x ⃗ = x ⃗ 0 = lim ⁡ Δ r → 0 f ( x 1 + Δ x 1 , x 2 + Δ x 2 , … , x n + Δ x n ) − f ( x 1 , … , x n ) Δ r = g r a d ( f ) ∣ x ⃗ = x ⃗ 0 ⋅ r ⃗ \begin{aligned} &\left.\dfrac{df(\vec{x})}{d\vec{r}}\right|_{\vec{x}=\vec{x}_0}=\lim_{\Delta r\rightarrow0}\dfrac{f(x_1+\Delta x_1,x_2+\Delta x_2,\dots,x_n+\Delta x_n)-f(x_1,\dots,x_n)}{\Delta r}\\\\ &\qquad\qquad\quad=\left.grad(f)\right|_{\vec{x}=\vec{x}_0}\cdot\vec{r} \end{aligned} dr df(x ) x =x 0=Δr0limΔrf(x1+Δx1,x2+Δx2,,xn+Δxn)f(x1,,xn)=grad(f)x =x 0r
其中, r ⃗ = 1 Δ r [ Δ x 1 , Δ x 2 , … , Δ x n ] \vec{r}=\dfrac{1}{\Delta r}\begin{bmatrix}\Delta x_1,\Delta x_2,\dots,\Delta x_n\end{bmatrix} r =Δr1[Δx1,Δx2,,Δxn] 为任意单位方向, Δ r = Δ x 1 2 + ⋯ + Δ x n 2 \Delta r=\sqrt{\Delta x_1^2+\dots+\Delta x_n^2} Δr=Δx12++Δxn2

上式说明:函数的负梯度方向是函数值在该点下降最快的方向。 因此,很容易想到利用负梯度作为搜索方向,这便是为何将其称为最速下降法(Steepest Descent)或梯度法,即
x ⃗ k + 1 = x ⃗ k − α k ▽ f ( x ⃗ k ) ( k = 0 , 1 , 2 , … ) \vec{x}_{k+1}=\vec{x}_k-\alpha_k\bigtriangledown f(\vec{x}_k)\ (k=0,1,2,\dots) x k+1=x kαkf(x k) (k=0,1,2,)
搜索方向确定后,步长还有待确定。我们希望函数沿着搜索方向上能够“前进”到该方向上的极小值,如图所示:


换而言之,每步搜寻所采取的最佳步长 α \alpha α 的确定是通过在搜索方向上进行一维极小值问题的求解 (试探法,插值法…) 获得,即
min ⁡ α f [ x ⃗ k − α ▽ f ( x ⃗ k ) ] = min ⁡ α ϕ ( α ) \min_{\alpha}f[\vec{x}_k-\alpha\bigtriangledown f(\vec{x}_k)]=\min_{\alpha}\phi(\alpha) αminf[x kαf(x k)]=αminϕ(α)
根据一元极值问题的必要条件:
ϕ ′ ( α ) = − { ▽ f [ x ⃗ k − α ▽ f ( x ⃗ k ) ] } T ⋅ [ ▽ f ( x ⃗ k ) ] = − [ ▽ f ( x ⃗ k + 1 ) ] T ⋅ [ ▽ f ( x ⃗ k ) ] = 0 \phi'(\alpha)=-\{\bigtriangledown f[\vec{x}_k-\alpha\bigtriangledown f(\vec{x}_k)]\}^T\cdot[\bigtriangledown f(\vec{x}_k)]=-[\bigtriangledown f(\vec{x}_{k+1})]^T\cdot[\bigtriangledown f(\vec{x}_k)]=0 ϕ(α)={f[x kαf(x k)]}T[f(x k)]=[f(x k+1)]T[f(x k)]=0
这说明了在最速下降法中, 相邻两个迭代点上的函数梯度相互垂直,即相邻两个搜索方向互相垂直 ,形成“之”字形的直齿锯齿现象。


由于锯齿现象,当迭代点接近极小点时,搜索的步长变得越来越小,因而收敛速度减慢,这种情况似乎与“最速下降”的名称相矛盾,这主要是因为梯度是函数的局部性质 (从局部上看,在一点附近函数的下降是快的),但从整体上看则走了许多弯路,函数的下降并不算快。不过最速下降法最初的几步往往可以下降的较快

2. 抛物型多元二次函数优化问题的步长选取

对于抛物型多元二次函数:
g ( x ⃗ ) = 1 2 x ⃗ T A x ⃗ − b ⃗ T x ⃗ + c ( A ∈ S P D ; c ∈ R ) g(\vec{x})=\frac{1}{2}\vec{x}^T\bold{A}\vec{x}-\vec{b}^T\vec{x}+c(\bold A\in SPD;c\in\mathbb{R}) g(x )=21x TAx b Tx +cASPD;cR
若采用最速下降法求解其最小值:

  • 搜索方向:
    − ▽ g = − A x ⃗ k + b ⃗ = r ⃗ k -\bigtriangledown g=-\bold{A}\vec{x}_k+\vec{b}=\vec{r}_k g=Ax k+b =r k
    其中, r ⃗ k \vec{r}_k r k 为迭代法求解线性方程组 A x ⃗ = b ⃗ \bold A \vec{x}=\vec{b} Ax =b k k k 步的残差。

  • 搜索路径:
    x ⃗ k + 1 = x ⃗ k + α k r ⃗ k r ⃗ k + 1 T ⋅ r ⃗ k = 0 \vec{x}_{k+1}=\vec{x}_k+\alpha_{k}\vec{r}_k\\\ \\ \vec{r}_{k+1}^{\ T}\cdot\vec{r}_k=0 x k+1=x k+αkr k r k+1 Tr k=0

对于这种情况,在求解最佳步长时,可以不用在搜索方向上进行一维搜索的数值计算,可以通过理论的方式直接推导出 α k \alpha_{k} αk 的计算表达式:
α k = r ⃗ k T ⋅ r ⃗ k r ⃗ k T ⋅ A ⋅ r ⃗ k \alpha_{k}=\dfrac{\vec{r}_k^{\ T}\cdot\vec{r}_k}{\vec{r}_k^{\ T}\cdot\bold{A}\cdot\vec{r}_k} αk=r k TAr kr k Tr k

证明:
0 = r ⃗ k + 1 T ⋅ r ⃗ k = ( b ⃗ − A ⋅ x ⃗ k + 1 ) T ⋅ r ⃗ k = [ b ⃗ − A ⋅ ( x ⃗ k + α k r ⃗ k ) ] T ⋅ r ⃗ k = [ ( b ⃗ − A ⋅ x ⃗ k ) − α k A ⋅ r ⃗ k ) ] T ⋅ r ⃗ k = r ⃗ k T ⋅ r ⃗ k − α k r ⃗ k T ⋅ A ⋅ r ⃗ k \begin{aligned} &0=\vec{r}_{k+1}^{\ T}\cdot\vec{r}_k\\\\ &\ \ =(\vec{b}-\bold{A}\cdot\vec{x}_{k+1})^{\ T}\cdot\vec{r}_k\\\\ &\ \ =[\vec{b}-\bold{A}\cdot(\vec{x}_k+\alpha_{k}\vec{r}_k)]^{\ T}\cdot\vec{r}_k\\\\ &\ \ =[(\vec{b}-\bold{A}\cdot\vec{x}_k)-\alpha_{k}\bold{A}\cdot\vec{r}_k)]^{\ T}\cdot\vec{r}_k\\\\ &\ \ =\vec{r}_k^{\ T}\cdot\vec{r}_k-\alpha_{k}\vec{r}_k^{\ T}\cdot\bold{A}\cdot\vec{r}_k\\\\ \end{aligned} 0=r k+1 Tr k  =(b Ax k+1) Tr k  =[b A(x k+αkr k)] Tr k  =[(b Ax k)αkAr k)] Tr k  =r k Tr kαkr k TAr k
故,
α k = r ⃗ k T ⋅ r ⃗ k r ⃗ k T ⋅ A ⋅ r ⃗ k ( ∗ ) \alpha_{k}=\dfrac{\vec{r}_k^{\ T}\cdot\vec{r}_k}{\vec{r}_k^{\ T}\cdot\bold{A}\cdot\vec{r}_k}\quad(*) αk=r k TAr kr k Tr k()

综上所述,上述多元二次函数的优化问题的求解格式为:

  1. r ⃗ k = b ⃗ − A ⋅ x ⃗ k \vec{r}_k=\vec{b}-\bold{A}\cdot\vec{x}_k r k=b Ax k

  2. x ⃗ k + 1 = x ⃗ k + r ⃗ k T ⋅ r ⃗ k r ⃗ k T ⋅ A ⋅ r ⃗ k r ⃗ k \vec{x}_{k+1}=\vec{x}_k+\dfrac{\vec{r}_k^{\ T}\cdot\vec{r}_k}{\vec{r}_k^{\ T}\cdot\bold{A}\cdot\vec{r}_k}\vec{r}_k x k+1=x k+r k TAr kr k Tr kr k

其中, k = 0 , 1 , 2 , 3 … k=0,1,2,3\dots k=0,1,2,3

最后指出,上述求解格式也可用于求解非多元二次函数的其他函数的优化问题,这是因为,根据多元泰勒展开式:
f ( x ⃗ ) = f ( x ⃗ 0 ) + ▽ [ f ( x ⃗ 0 ) ] T ⋅ ( x ⃗ − x ⃗ 0 ) + 1 2 ( x ⃗ − x ⃗ 0 ) T ⋅ H ( x ⃗ 0 ) ⋅ ( x ⃗ − x ⃗ 0 ) + … f(\vec{x})=f(\vec{x}_0)+\bigtriangledown[f(\vec{x}_0)]^T\cdot(\vec{x}-\vec{x}_0)+\frac{1}{2}(\vec{x}-\vec{x}_0)^T\cdot\bold{H}(\vec{x}_0)\cdot(\vec{x}-\vec{x}_0)+\dots f(x )=f(x 0)+[f(x 0)]T(x x 0)+21(x x 0)TH(x 0)(x x 0)+
其中,海塞矩阵
H ( x ⃗ 0 ) = [ ∂ 2 f ∂ x 1 2 ∂ 2 f ∂ x 1 ∂ x 2 … ∂ 2 f ∂ x 1 ∂ x n ∂ 2 f ∂ x 2 ∂ x 1 ∂ 2 f ∂ x 2 2 … ∂ 2 f ∂ x 2 ∂ x n ⋮ ⋮ ⋮ ∂ 2 f ∂ x n ∂ x 1 ∂ 2 f ∂ x n ∂ x 2 … ∂ 2 f ∂ x n 2 ] \bold{H}(\vec{x}_0)= \begin{bmatrix} \dfrac{\partial^2f}{\partial x_1^2} & \dfrac{\partial^2f}{\partial x_1\partial x_2} & \dots & \dfrac{\partial^2f}{\partial x_1\partial x_n}\\\\ \dfrac{\partial^2f}{\partial x_2\partial x_1} & \dfrac{\partial^2f}{\partial x_2^2} & \dots & \dfrac{\partial^2f}{\partial x_2\partial x_n}\\\\ \vdots &\vdots & &\vdots\\\\ \dfrac{\partial^2f}{\partial x_n\partial x_1} & \dfrac{\partial^2f}{\partial x_n\partial x_2} & \dots & \dfrac{\partial^2f}{\partial x_n^2} \end{bmatrix} H(x 0)= x122fx2x12fxnx12fx1x22fx222fxnx22fx1xn2fx2xn2fxn22f
这说明在局部上,函数均可通过二次函数进行近似,即
{ A ≈ H ( x ⃗ 0 ) b ⃗ ≈ ▽ [ f ( x ⃗ 0 ) ] c ≈ f ( x ⃗ 0 ) \begin{cases} \bold A\approx \bold{H}(\vec{x}_0)\\\\ \vec{b}\approx \bigtriangledown[f(\vec{x}_0)]\\\\ c\approx f(\vec{x}_0) \end{cases} AH(x 0)b [f(x 0)]cf(x 0)

3. 抛物型多元二次函数等值线/面的几何分析

前述抛物型多元二次函数的等值线、等值面方程为:
1 2 x ⃗ T A x ⃗ − b ⃗ T x ⃗ + c = β , ( A 为正定 / 负定对称矩阵, β ∈ [ min ⁡ f , max ⁡ f ] ) \dfrac{1}{2}\vec{x}^T\bold A\vec{x}-\vec{b}^{\ T}\vec{x}+c=\beta,\ (A为正定/负定对称矩阵,\beta\in[\min{f},\max{f}]) 21x TAx b  Tx +c=β, (A为正定/负定对称矩阵,β[minf,maxf])
将上述一般形式转变为标准形式:

  • 平移变换 x ⃗ = y ⃗ + x ⃗ 0 \vec{x}=\vec{y}+\vec{x}_0\quad x =y +x 0(其中, x ⃗ 0 \vec{x}_0 x 0 为待定的常向量)
    1 2 x ⃗ T A x ⃗ − b ⃗ T x ⃗ + c = 1 2 ( y ⃗ + x ⃗ 0 ) T A ( y ⃗ + x ⃗ 0 ) − b ⃗ T ( y ⃗ + x ⃗ 0 ) + c = 1 2 y ⃗ T A y ⃗ + y ⃗ T ( A x ⃗ 0 − b ⃗ ) + 1 2 x ⃗ 0 T A x ⃗ 0 − b ⃗ T x ⃗ 0 + c ( 令  x ⃗ 0 = A − 1 b ⃗ ) = 1 2 y ⃗ T A y ⃗ − 1 2 b ⃗ T A − 1 b ⃗ + c = β \begin{aligned} &\quad\dfrac{1}{2}\vec{x}^T\bold A\vec{x}-\vec{b}^{\ T}\vec{x}+c\\\\ &=\dfrac{1}{2}(\vec{y}+\vec{x}_0)^T\bold A(\vec{y}+\vec{x}_0)-\vec{b}^{\ T}(\vec{y}+\vec{x}_0)+c\\\\ &=\dfrac{1}{2}\vec{y}^{\ T}\bold A\vec{y}+\vec{y}^{\ T}(\bold A \vec{x}_0-\vec{b})+\dfrac{1}{2}\vec{x}_0^{\ T}\bold A\vec{x}_0-\vec{b}^{\ T}\vec{x}_0+c\ (令\ \vec{x}_0=\bold A^{-1}\vec{b})\\\\ &=\dfrac{1}{2}\vec{y}^{\ T}\bold A\vec{y}-\dfrac{1}{2}\vec{b}^{\ T}\bold A^{-1}\vec{b}+c=\beta\\\\ \end{aligned} 21x TAx b  Tx +c=21(y +x 0)TA(y +x 0)b  T(y +x 0)+c=21y  TAy +y  T(Ax 0b )+21x 0 TAx 0b  Tx 0+c ( x 0=A1b )=21y  TAy 21b  TA1b +c=β

  • 旋转操作 y ⃗ = Q z ⃗ , Q T A Q = D \vec{y}=\bold{Q}\vec{z},\bold{Q^TAQ=D} y =Qz QTAQ=D (正交合同),其中, A \bold A A的特征对为 u ⃗ i − λ i A \vec{u}_i-\lambda^A_i u iλiA
    Q = [ u ⃗ 1 u ⃗ 2 … u ⃗ n ] D = [ λ 1 A λ 2 A ⋱ λ n A ] \begin{aligned} &\bold Q=\begin{bmatrix}\vec{u}_1&\vec{u}_2&\dots&\vec{u}_n\end{bmatrix}\\\ \\ &\bold D=\begin{bmatrix}\lambda^A_1\\\\&&\lambda^A_2\\\\&&&\ddots\\\\&&&&\lambda^A_n \end{bmatrix} \end{aligned}  Q=[u 1u 2u n]D= λ1Aλ2AλnA
    则有:
    1 2 x ⃗ T A x ⃗ − b ⃗ T x ⃗ + c = 1 2 y ⃗ T A y ⃗ − 1 2 b ⃗ T A − 1 b ⃗ + c = 1 2 z ⃗ T D z ⃗ − 1 2 b ⃗ T A − 1 b ⃗ + c = β \begin{aligned} &\quad\dfrac{1}{2}\vec{x}^T\bold A\vec{x}-\vec{b}^{\ T}\vec{x}+c\\\\ &=\dfrac{1}{2}\vec{y}^{\ T}\bold A\vec{y}-\dfrac{1}{2}\vec{b}^{\ T}\bold A^{-1}\vec{b}+c\\\\ &=\dfrac{1}{2}\vec{z}^{\ T}\bold D\vec{z}-\dfrac{1}{2}\vec{b}^{\ T}\bold A^{-1}\vec{b}+c=\beta\\\\ \end{aligned} 21x TAx b  Tx +c=21y  TAy 21b  TA1b +c=21z  TDz 21b  TA1b +c=β

    z ⃗ T D z ⃗ = β − 2 c + b ⃗ T A − 1 b ⃗ ≜ α { > 0 ( A 为正定矩阵 ) < 0 ( A 为负定矩阵 ) \vec{z}^{\ T}\bold D\vec{z}=\beta-2c+\vec{b}^{\ T}\bold A^{-1}\vec{b}\triangleq\alpha \begin{cases} \ >0\ (A为正定矩阵)\\\\ \ <0\ (A为负定矩阵) \end{cases} z  TDz =β2c+b  TA1b α  >0 (A为正定矩阵) <0 (A为负定矩阵)

    z ⃗ T D z ⃗ = α ⟹ z 1 2 α λ 1 A + z 2 2 α λ 2 A + ⋯ + z n 2 α λ n A = 1 \vec{z}^{\ T}\bold D\vec{z}=\alpha\Longrightarrow \dfrac{z_1^2}{\dfrac{\alpha}{\lambda^A_1}}+\dfrac{z_2^2}{\dfrac{\alpha}{\lambda^A_2}}+\dots+\dfrac{z_n^2}{\dfrac{\alpha}{\lambda^A_n}}=1 z  TDz =αλ1Aαz12+λ2Aαz22++λnAαzn2=1
    其中,
    z ⃗ = Q T ( x ⃗ − A − 1 b ⃗ ) \vec{z}=\bold{Q}^T(\vec{x}-\bold A^{-1}\vec{b}) z =QT(x A1b )
    通过标准型可以较容易地知道“椭圆“ 的相关信息:

  • k k k 轴所在直线的一般方程(面的交线)为:
    z i = 0 ( i = 1 , 2 , … , n 且 i ≠ k ) z_i=0\ (i=1,2,\dots,n且i\ne k) zi=0 (i=1,2,,ni=k)
    k k k 轴对应的单位方向与 z i = 0 ( i = 1 , 2 , … , n 且 i ≠ k ) z_i=0\ (i=1,2,\dots,n且i\ne k) zi=0 (i=1,2,,ni=k) 定义的 n − 1 n-1 n1 个平面的法线 u ⃗ i ( i = 1 , 2 , … , n 且 i ≠ k ) \vec{u}_i\ (i=1,2,\dots,n且i\ne k) u i (i=1,2,,ni=k) 正交,这说明 k k k轴所在方向即为特征向量 u ⃗ k \vec{u}_k u k 所在的方向。并且轴线方向不因等值面 β \beta β 的不同而改变,即所有椭圆等值面的轴具有相同的方向且同心,这意味着倘若初始点任意选择,并不再选择负梯度方向作为搜索方向,而选择 A \bold A A 的特征方向作为搜索方向(即平行于各轴进行搜索),那么至多 n 步便能寻得最小值

  • 各个半轴长为:
    a i = α λ i A a_i=\sqrt{\dfrac{\alpha}{\lambda^A_i}} ai=λiAα
    即,某一特定的等值线,特征值越大的方向,椭圆越扁平

另外,梯度沿着等值线、等值面的外法线方向,那么轴线上的各点梯度便指向 ”椭圆“ 中心,说明:若初始点恰巧选择在 ”椭圆“ 的轴线,最速下降法仅一步便可以求得上述优化问题的解

4. 基于最速下降法的 “变步长Richardson 迭代法” 的收敛性分析

求解线性方程组:
A x ⃗ = b ⃗ ( A ∈ S P D ) \bold A \vec{x}=\vec{b}\quad (\bold A\in SPD) Ax =b (ASPD)
等价于求解如下二次函数的极小值点:
g ( x ⃗ ) = 1 2 x ⃗ T A x ⃗ − b ⃗ T x ⃗ + c ( A ∈ S P D ) g(\vec{x})=\frac{1}{2}\vec{x}^T\bold{A}\vec{x}-\vec{b}^T\vec{x}+c\quad (\bold A\in SPD) g(x )=21x TAx b Tx +c(ASPD)
基于最速下降法可以得出 “变步长Richardson 迭代法”,即参数 α \alpha α 不再取为固定值,求解格式如下:
{ r ⃗ k = b ⃗ − A ⋅ x ⃗ k α k = r ⃗ k T ⋅ r ⃗ k r ⃗ k T ⋅ A ⋅ r ⃗ k x ⃗ k + 1 = x ⃗ k + α k r ⃗ k \begin{cases} \vec{r}_k=\vec{b}-\bold{A}\cdot\vec{x}_k\\\\ \alpha_k=\dfrac{\vec{r}_k^{\ T}\cdot\vec{r}_k}{\vec{r}_k^{\ T}\cdot\bold{A}\cdot\vec{r}_k}\\\\ \vec{x}_{k+1}=\vec{x}_k+\alpha_k\vec{r}_k \end{cases} r k=b Ax kαk=r k TAr kr k Tr kx k+1=x k+αkr k
现对这种方法的收敛性及收敛速度进行分析:(方程组的精确解为 x ⃗ \vec{x} x )


E ( x ⃗ k ) ≜ 1 2 e ⃗ k T A e ⃗ k = 1 2 ( x k ⃗ − x ⃗ ) T A ( x k ⃗ − x ⃗ ) = g ( x ⃗ k ) + 1 2 x ⃗ T A x ⃗ \begin{aligned} E(\vec{x}_k)\triangleq\frac{1}{2}\vec{e}_k^T\bold A\vec{e}_k =\frac{1}{2}(\vec{x_k}-\vec{x})^T\bold A(\vec{x_k}-\vec{x}) =g(\vec{x}_k)+\frac{1}{2}\vec{x}^T\bold A\vec{x} \end{aligned} E(x k)21e kTAe k=21(xk x )TA(xk x )=g(x k)+21x TAx

x ⃗ k + 1 = x ⃗ k + α k r ⃗ k ⟹ e ⃗ k + 1 = e ⃗ k + α k r ⃗ k r ⃗ k = b ⃗ − A x ⃗ k = A x ⃗ − A x ⃗ k = − A e ⃗ k ⟹ e ⃗ k = − A − 1 r ⃗ k \vec{x}_{k+1}=\vec{x}_k+\alpha_k\vec{r}_k \Longrightarrow \vec{e}_{k+1}=\vec{e}_k+\alpha_k\vec{r}_k\\\ \\ \vec{r}_k=\vec{b}-\bold A\vec{x}_k=\bold A\vec{x}-\bold A\vec{x}_k=-\bold A\vec{e}_k \Longrightarrow \vec{e}_k=-\bold A^{-1}\vec{r}_k x k+1=x k+αkr ke k+1=e k+αkr k r k=b Ax k=Ax Ax k=Ae ke k=A1r k
那么
E ( x ⃗ k ) − E ( x ⃗ k + 1 ) E ( x ⃗ k ) = e ⃗ k T A e ⃗ k − e ⃗ k + 1 T A e ⃗ k + 1 e ⃗ k T A e ⃗ k = e ⃗ k T A e ⃗ k − ( e ⃗ k + α k r ⃗ k ) T A ( e ⃗ k + α k r ⃗ k ) e ⃗ k T A e ⃗ k = − 2 α k r ⃗ k T A e ⃗ k − α k 2 r ⃗ k T A r ⃗ k e ⃗ k T A e ⃗ k = ( r ⃗ k T r ⃗ k ) 2 ( r ⃗ k T A r ⃗ k ) ( r ⃗ k T A − 1 r ⃗ k ) ≥ 4 λ m i n A λ m a x A ( λ m i n A + λ m a x A ) 2 ( K a n t o r v i c h 不等式) \begin{aligned} &\quad\dfrac{E(\vec{x}_k)-E(\vec{x}_{k+1})}{E(\vec{x}_k)}\\\\ &=\dfrac{\vec{e}_k^T\bold A\vec{e}_k-\vec{e}_{k+1}^T\bold A\vec{e}_{k+1}}{\vec{e}_k^T\bold A\vec{e}_k}\\\\ &=\dfrac{\vec{e}_k^T\bold A\vec{e}_k-(\vec{e}_k+\alpha_k\vec{r}_k)^T\bold A(\vec{e}_k+\alpha_k\vec{r}_k)}{\vec{e}_k^T\bold A\vec{e}_k}\\\\ &=\dfrac{-2\alpha_k\vec{r}_k^T\bold A\vec{e}_k-\alpha_k^2\vec{r}_k^T\bold A\vec{r}_k}{\vec{e}_k^T\bold A\vec{e}_k}\\\\ &=\dfrac{(\vec{r}_k^T\vec{r}_k)^2}{(\vec{r}_k^T\bold A\vec{r}_k)(\vec{r}_k^T\bold A^{-1}\vec{r}_k)}\\\\ &\ge\dfrac{4\lambda^A_{min}\lambda^A_{max}}{(\lambda^A_{min}+\lambda^A_{max})^2}(Kantorvich 不等式) \end{aligned} E(x k)E(x k)E(x k+1)=e kTAe ke kTAe ke k+1TAe k+1=e kTAe ke kTAe k(e k+αkr k)TA(e k+αkr k)=e kTAe k2αkr kTAe kαk2r kTAr k=(r kTAr k)(r kTA1r k)(r kTr k)2(λminA+λmaxA)24λminAλmaxAKantorvich不等式)
从而有:
E ( x ⃗ k + 1 ) ≤ [ 1 − 4 λ m i n A λ m a x A ( λ m i n A + λ m a x A ) 2 ] E ( x ⃗ k ) = ( λ m i n A − λ m a x A λ m i n A + λ m a x A ) 2 E ( x ⃗ k ) E(\vec{x}_{k+1})\le\left[1-\dfrac{4\lambda^A_{min}\lambda^A_{max}}{(\lambda^A_{min}+\lambda^A_{max})^2}\right]E(\vec{x}_k) =\left(\dfrac{\lambda^A_{min}-\lambda^A_{max}}{\lambda^A_{min}+\lambda^A_{max}}\right)^2E(\vec{x}_k) E(x k+1)[1(λminA+λmaxA)24λminAλmaxA]E(x k)=(λminA+λmaxAλminAλmaxA)2E(x k)
那么
0 ≤ E ( x ⃗ k ) ≤ ( λ m i n A − λ m a x A λ m i n A + λ m a x A ) 2 k E ( x ⃗ 0 ) 0\le E(\vec{x}_{k})\le\left(\dfrac{\lambda^A_{min}-\lambda^A_{max}}{\lambda^A_{min}+\lambda^A_{max}}\right)^{2k}E(\vec{x}_0) 0E(x k)(λminA+λmaxAλminAλmaxA)2kE(x 0)

lim ⁡ k → ∞ E ( x ⃗ k ) = 0 \lim_{k\rightarrow\infty}E(\vec{x}_{k})=0 klimE(x k)=0
因为 A \bold A A 为对称正定矩阵,当且仅当 x ⃗ k = x ⃗ \vec{x}_k=\vec{x} x k=x 时, E ( x ⃗ k ) = 0 E(\vec{x}_k)=0 E(x k)=0,故基于最速下降法的 “变步长Richardson 迭代法”必定收敛,且收敛速度至少为:
( λ m i n A − λ m a x A λ m i n A + λ m a x A ) 2 = [ c o n d ( A ) 2 − 1 c o n d ( A ) 2 + 1 ] 2 \left(\dfrac{\lambda^A_{min}-\lambda^A_{max}}{\lambda^A_{min}+\lambda^A_{max}}\right)^2=\left[\dfrac{cond(\bold A)_2-1}{cond(\bold A)_2+1}\right]^2 (λminA+λmaxAλminAλmaxA)2=[cond(A)2+1cond(A)21]2
优于Richardson 迭代法的最佳收敛速度。

那么,当对称正定矩阵 A \bold A A 的最大特征值越接近于最小特征值时,收敛速度越快,换而言之,等值线的椭圆长轴短轴长度越接近时收敛速度越快,最佳的情况是等值线为同心圆,此时仅需一步便可得到精确解。而若椭圆偏心率越大,越扁平,即最大特征值与最小特征值相差越大,收敛速度便会越小。


http://www.ppmy.cn/news/804574.html

相关文章

【机器学习】- 作业2: 基于线性分析的大学综合得分预测

驭风计划是由清华大学老师教授的&#xff0c;其分为四门课&#xff0c;包括: 机器学习(张敏教授) &#xff0c; 深度学习(胡晓林教授), 计算机语言(刘知远教授) 以及数据结构与算法(邓俊辉教授)。本人是综合成绩第一名&#xff0c;除了数据结构与算法其他单科均为第一名。代码和…

自动驾驶决策规划算法第一章

前置学习内容&#xff1a; 【自动驾驶】【零基础】基础自动驾驶控制算法笔记 注意&#xff1a;最好学习前置控制算法&#xff0c;因为决策规划仿真中需要用到 感谢&#xff1a;忠厚老实的老王 下面是他的主页&#xff1a;忠厚老实的老王的个人空间_哔哩哔哩_bilibili 目录 序…

解读测试能力素质模型

软件测试的能力素质模型(Job Model)&#xff0c;是对不同层级测试工程的能力要求进行明确的定义。目的是为了对每位工程师的能力进行科学的评估&#xff0c;然后分配合理的工作&#xff0c;也帮助大家明确职业规划的方向。 淘宝测试工程师的最常用的有4个&#xff0c;分别是&am…

CVSS得分计算公式

CVSS得分计算公式 Base Metrics计算方式 基础分&#xff08;Base Score&#xff0c;简称BS&#xff09;是通过影响子因子分数&#xff08;Impact sub score&#xff0c;简称ISC&#xff09;和可用性子因子分数&#xff08;Exploitability sub score&#xff0c;简称ESC&#…

理解Lucene得分计算公式

Lucene通过计算文档的得分来确定查询结果文档的相似度。如果你希望通过干预Lucene查询来改变查询结果的排序&#xff0c;你就需要对Lucene的得分计算有所理解。Lucene得分计算公式如下所示&#xff1a; score(q,d) coord(q,d)queryNorm(q)∑( tf(t in d)idf(t)^2t.getBoos…

【LeetCode: 16. 最接近的三数之和 | 双指针专题 】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

VMware16.0安装教程和创建

许可证&#xff1a; ZF3R0-FHED2-M80TY-8QYGC-NPKYFYF390-0HF8P-M81RQ-2DXQE-M2UT6ZF71R-DMX85-08DQY-8YMNC-PPHV8设置网络 添加镜像 下载centos7镜像网址https://mirrors.aliyun.com/centos/7/isos/x86_64/?spma2c6h.25603864.0.0.d7724511YPrZpg win10镜像地址https://ww…

vue app状态栏颜色

if(window.plus){ plus.navigator.setStatusBarBackground(#0344fb); }

uni-app 获取手机状态栏高度

<template> <view> <view :style"height:statusBarHeightpx"></view> </view> </template> <script> export default{ data(){ return{ statusBarHeight:0,//状态栏高度 } }, onLoad(){ this.statusBarHeight plus.nav…

准确获取系统顶部状态栏,顶部导航栏的高度

看到许多文章通过获取 decorView 的 top 或者 getWindowManager().getDefaultDisplay() 的方法来获取状态栏的高度&#xff0c;在转屏或者切换的时候会比较容易出错&#xff0c;这里推荐一种更加准确的方法&#xff1a; 在Frameworks目录下&#xff0c;状态栏的高度和导航栏的…

仿iphone顶部状态栏_无需第三方APP,苹果iPhone手机屏幕录制的方法

有些小伙伴在使用iPhone手机玩游戏的时候&#xff0c;很想把自己玩的游戏录个高清视频&#xff0c;再添加自己的原声解说&#xff0c;做个教程&#xff0c;分享到网上或发送给朋友&#xff0c;或者看到喜欢的直播需要录制下来&#xff0c;以后欣赏或分享给他人&#xff0c;但不…

移动端:js如何获取当前手机的状态栏高度

废话不多说&#xff0c;直接直接上代码&#xff1a; //获取当前手机状态栏高度 let immersed 0; let ms (/Html5Plus\/.\s\(.*(Immersed\/(\d\.?\d*).*)\)/gi).exec(navigator.userAgent); if(ms&&ms.length>3) { // 当前环境为沉浸式状态栏模式immersed parseF…

iOS--状态栏的调整控制方法

在不同的需求场景中&#xff0c;我们会遇到把状态栏字体颜色显示为深色或者浅色&#xff0c;也可能会遇到需要隐藏状态栏的情况&#xff0c;下面就是对状态栏的一些基本操作&#xff0c;注意&#xff0c;代码是写到Viewcontroller中哦&#xff0c;直接写就是了&#xff0c;系统…

ios底部栏设计规范_iOS平台的移动UI设计规范

一、状态栏和导航栏 1、状态栏(Status Bars)就是iPhone最上方用来显示时间、运营商信息、电池电量的那个很窄的区域。 2、导航栏(Navigation Bars)就是状态栏之下的区域,一般来说导航栏中间是页面标题,左右是放置功能图标的区域。 在iPhone6/7/8设计中,状态栏的高度为20pt(4…

如果ios头部状态栏挡住了导航栏,能看到内容从下面穿过的解决方法。

如上图&#xff0c;内容从导航栏头顶穿过会显示出来(ios系统)。解决方法&#xff1a; https://jingyan.baidu.com/article/0964eca26d9cbd8285f5369f.html html5移动端Meta设置 听语音 |浏览&#xff1a;1262|更新&#xff1a;2016-05-26 19:08 html5移动端Meta设置 工具/原料…

uniapp实现自适应手机状态栏高度的顶部导航栏

<!-- 顶部导航栏 --> <template><view><block v-if"!onlyShowStatusBar"><image :src"imgSrc" v-if"imgSrc" class"bg-img" mode"widthFix"></image><view class"title-bar-ap…

android 状态栏wifi,【技术贴】教你修改状态栏里的wifi、信号、电量图标(转自论坛)...

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼 原帖地址:http://www.miui.com/forum.php?mod=viewthread&tid=1745173 素材地址:http://pan.baidu.com/share/link?shareid=2354935872&uk=1009070904 首先,你要有一个主题包(这儿就拿个例子。比如,我要替换xxx.mtz…

android 状态栏显示流程,基于Android系统的跨屏状态栏实现方法与流程

本发明属于车机应用技术领域,具体涉及一种基于Android系统的跨屏状态栏实现方法。 背景技术: 目前,燃油车、新能源车等各类型车辆迅速发展。同时,与手持移动终端的发展趋势相似——从以黑莓品牌为代表的全键盘手机演进至以苹果品牌的全触控手机——车机系统同样在发生明显变…

苹果状态栏HTML,iphoneX 适配客户端H5页面的方法教程

前言 目前,很多APP设计师小伙伴已经开始转向H5前端开发啦,但是解决所有iPhone和安卓机型的适配问题是我们的重中之重。无论是设计APP还是写前端H5.都是要考虑移动端的兼容性。 由于iphoneX做了全面屏并且还保留一块小刘海,因此很多以前的移动端H5页面需要结合App客户端做出相…

ios的状态栏(UIStatusBar)

http://my.oschina.net/shede333/blog/304560
最新文章