收敛速度

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

商收敛因子及商收敛阶

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

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

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

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

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

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

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

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

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

根收敛因子及根收敛阶

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

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

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

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

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

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

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

两种收敛阶的联系

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

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

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

数列

有如下数列:

${\displaystyle 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.}$ 

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

向量列

有如下向量列:

${\displaystyle 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)}$ .

据上作出计算如下,

${\displaystyle 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收敛阶为${\displaystyle 1}$ ;

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

故数列为R线性收敛; R收敛阶为${\displaystyle 1}$ .

优化算法的迭代点列

牛顿法

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

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

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

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

1. ^ Ortega, J R; Rheinboldt, WC. Iterative Solution of Nonlinear Equations in Several Variables. London: Academic Press. 1970. 
2. ^ 袁亚湘. 非線性優化計算方法. 北京: 科学出版社. 2008年2月: 17. ISBN 978-7-03-020883-5 （中文（简体））.  使用|accessdate=需要含有|url= (帮助)