收敛速度

在数值分析中, 一个收敛序列向其极限逼近的速度称为收敛速度. 该概念多用于最优化算法中; 其被定义为一个叠代序列向其局部最优值逼近 (假设计算过程收敛, 并能逹到最优值) 的速度, 是评价一个叠代法于该问题中发挥的性能的一个重要指标.

定义

收敛速度以收敛阶衡量, 亦可以收敛因子描述; 依计算方法的不同, 有下述两种收敛阶及收敛因子.

商收敛因子及商收敛阶

• 商收敛因子$Q_{p}$的定义式如下:

$Q_{p}=\limsup _{k\rightarrow \infty }{\frac {||x_{k+1}-x^{*}||_{2}}{||x_{k}-x^{*}||_{2}^{p}}},p\in [1,+\infty ]$

商收敛因子也称Q—因子, 商收敛阶也称Q—收敛阶. 利用商收敛因子, 对收敛速度进行描述的方式如下:

1. 如果$Q_{1}=0$, 则称$\{x_{k}\}$是Q—超线性收敛于$x^{*}$; 如果$0<Q_{1}<1$, 则称$\{x_{k}\}$是Q—线性收敛于$x^{*}$; 如果$Q_{1}\geq 1$, 则称$\{x_{k}\}$是Q—次线性收敛于$x^{*}$.
2. 如果$Q_{2}=0$, 则称$\{x_{k}\}$是Q—超平方收敛于$x^{*}$; 如果$0<Q_{2}<+\infty$, 则称$\{x_{k}\}$是Q—平方收敛于$x^{*}$; 如果$Q_{2}=+\infty$, 则称$\{x_{k}\}$是Q—次平方收敛于$x^{*}$.

注意: Q—线性收敛与Q—平方收敛, 以及Q—次线性收敛与Q—次平方收敛的评判标准有些微差别. “Q—平方收敛”也称为“Q—二次收敛”.

依照Q—平方收敛 (不是Q—线性收敛) 的定义, 可以定义Q—立方收敛 (将$Q_{2}$改为$Q_{3}$), Q—四次方收敛等更高Q—收敛阶.

• 商收敛阶$O_{Q}$的定义式如下:

$O_{Q}=\inf\{p|p\in [1,+\infty ){\text{ 且 }}Q_{p}=+\infty \}$

对比商收敛因子的描述, 商收敛阶是指求出一个数$n\geq 1$ (不一定是整数), 使得对于$\forall t_{1}\geq n$, 点列$\{x_{k}\}$都是Q—次$t_{1}$次方收于, 且对于$t_{2}<n$, $\{x_{k}\}$都是Q—$t_{2}$次方收敛. 而这个数$n$就是点列的商收敛阶.

根收敛因子及根收敛阶

• 根收敛因子$R_{p}$的定义式如下:

$R_{p}=\left\{{\begin{aligned}\limsup _{k\rightarrow \infty }||x_{k}-x^{*}||_{2}^{1/k},&{\mbox{ when }}p=1,\\\limsup _{k\rightarrow \infty }||x_{k}-x^{*}||_{2}^{1/p^{k}},&{\mbox{ when }}p>1.\end{aligned}}\right.$

根收敛因子也称R—因子, 根收敛阶也称R—收敛阶. 利用根收敛因子, 对收敛速度进行描述的方式如下:

1. 如果$R_{1}=0$, 则称$\{x_{k}\}$是R—超线性收敛于$x^{*}$; 如果$0<R_{1}<1$, 则称$\{x_{k}\}$是R—线性收敛于$x^{*}$; 如果$R_{1}=1$, 则称$\{x_{k}\}$是R—次线性收敛于$x^{*}$.
2. 如果$R_{2}=0$, 则称$\{x_{k}\}$是R—超平方收敛于$x^{*}$; 如果$0<R_{2}<1$, 则称$\{x_{k}\}$是R—平方收敛于$x^{*}$; 如果$R_{2}\geq +\infty$, 则称$\{x_{k}\}$是R—次平方收敛于$x^{*}$.

注意: R—次线性收敛与R—次平方收敛的评判标准有些微差别. “R—平方收敛”也称为“R—二次收敛”.

依照R—平方收敛 (不是R—线性收敛) 的定义, 可以定义R—立方收敛 (将$R_{2}$改为$R_{3}$), R—四次方收敛等更高R—收敛阶.

• 根收敛阶$O_{R}$的定义式如下:

$O_{R}=\inf\{p|p\in [1,+\infty ){\text{ 且 }}R_{p}=1\}$

对比根收敛因子的描述, 根收敛阶是指求出一个数$n\geq 1$ (不一定是整数), 使得对于$\forall t_{1}\geq n$, 点列$\{x_{k}\}$都是R—次$t_{1}$次方收于, 且对于$t_{2}<n$, $\{x_{k}\}$都是R—$\ \ t_{2}$次方收敛. 而这个数$n$就是点列的根收敛阶.

两种收敛阶的联系

对于一个收敛点列而言, 其Q—收敛阶不大于其R—收敛阶, 即

$O_{Q}\leq O_{R}.$

有时, 一个数列的R—收敛阶可能很高, 但其Q—收敛阶可能很低. 当然可以证明, 一个R—收敛阶高的点列至少比某些Q—收敛低的点列收敛得更快.

实例

数列

有如下数列:

$a_{1}=1,\ a_{2}={\frac {1}{2}},\ a_{3}={\frac {1}{4}},\ a_{4}={\frac {1}{8}},\ \cdots ,\ a_{k}={\frac {1}{2^{k-1}}},\ \cdots ,\ a_{\infty }=0.$

容易计算: $Q_{1}={\frac {1}{2}}$, 故该数列是Q线性收敛的; 满足$Q_{p}=+\infty$的$p$的集合为$\{x|x>1\}$, 此集合的下确界为$1$, 故该数列的收敛阶为$1$. 而同理, 可计算得该数列是R线性收性, R收敛阶为$1$.

向量列

有如下向量列:

$v^{(1)}=(a,b)^{\mathbf {T} },\ v^{(2)}=(a^{2},b^{2})^{\mathbf {T} },\ \cdots ,\ v^{(k)}=(a^{k},b^{k})^{\mathbf {T} },\ \cdots ,\ v^{(\infty )}=(0,0)^{\mathbf {T} }.(0<a^{2}+b^{2}<1)$.

据上作出计算如下,

$Q_{1}=\limsup _{k\rightarrow \infty }{\frac {\|(a^{k+1},b^{k+1})^{\mathbf {T} }\|_{2}}{\|(a^{k},b^{k})^{\mathbf {T} }\|_{2}}}=\limsup _{k\rightarrow \infty }{\frac {\sqrt {(a^{k+1})^{2}+(b^{k+1})^{2}}}{\sqrt {(a^{k})^{2}+(b_{k})^{2}}}}<\limsup _{k\rightarrow \infty }{\frac {\sqrt {(a^{2k}+b^{2k})(a^{2}+b^{2})}}{\sqrt {a^{2k}+b^{2k}}}}={\sqrt {a^{2}+b^{2}}}<1,$

故数列为Q线性收敛; Q收敛阶为$1$;

$R_{1}=\limsup _{k\rightarrow \infty }(a^{2k}+b^{2k})^{1/2k}=\max\{a,b\}<1,$

故数列为R线性收敛; R收敛阶为$1$.

优化算法的叠代点列

牛顿法

注: 此处的牛顿法指应用于最优化的牛顿法.

可以证明, 如果牛顿法的目标函数$f(x)$的二阶导数$f^{\prime \prime }(x)$在其收敛点$x_{\infty }$处Lipschitz连续, 则满足不等式

$0<{\frac {|x_{k+1}-x_{\infty }|}{|x_{k}-x_{\infty }|}}<+\infty .$

此说明牛顿法的叠代点列是Q平方收敛; 另言之, 牛顿法的收敛速度是二次的.