在數值分析中, 一個收斂序列向其極限逼近的速度稱為收斂速度. 該概念多用於最佳化演算法中; 其被定義為一個疊代序列向其局部最優值逼近 (假設計算過程收斂, 並能逹到最優值) 的速度, 是評價一個疊代法於該問題中發揮的效能的一個重要指標.
收斂速度以收斂階衡量, 亦可以收斂因子描述; 依計算方法的不同, 有下述兩種收斂階及收斂因子.[1]
商收斂因子及商收斂階[編輯]
- 商收斂因子
的定義式如下:
![{\displaystyle Q_{p}=\limsup _{k\rightarrow \infty }{\frac {||x_{k+1}-x^{*}||_{2}}{||x_{k}-x^{*}||_{2}^{p}}},p\in [1,+\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e270b87795e428c42b0c1a0df72f1d41bf1b8812)
商收斂因子也稱Q—因子, 商收斂階也稱Q—收斂階. 利用商收斂因子, 對收斂速度進行描述的方式如下:
- 如果
, 則稱
是Q—超線性收斂於
; 如果
, 則稱
是Q—線性收斂於
; 如果
, 則稱
是Q—次線性收斂於
.
- 如果
, 則稱
是Q—超平方收斂於
; 如果
, 則稱
是Q—平方收斂於
; 如果
, 則稱
是Q—次平方收斂於
.
注意: Q—線性收斂與Q—平方收斂, 以及Q—次線性收斂與Q—次平方收斂的評判標準有些微差別. 「Q—平方收斂」也稱為「Q—二次收斂」.
依照Q—平方收斂 (不是Q—線性收斂) 的定義, 可以定義Q—立方收斂 (將
改為
), Q—四次方收斂等更高Q—收斂階.
- 商收斂階
的定義式如下:
![{\displaystyle O_{Q}=\inf\{p|p\in [1,+\infty ){\text{ 且 }}Q_{p}=+\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4bf8e98a62649a50e72db343ab12ab4602e9f29d)
對比商收斂因子的描述, 商收斂階是指求出一個數
(不一定是整數), 使得對於
, 點列
都是Q—次
次方收於, 且對於
,
都是Q—
次方收斂. 而這個數
就是點列的商收斂階.
根收斂因子及根收斂階[編輯]
- 根收斂因子
的定義式如下:
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47f8a49c00149206239845e3edc46fa6fe941207)
根收斂因子也稱R—因子, 根收斂階也稱R—收斂階. 利用根收斂因子, 對收斂速度進行描述的方式如下:
- 如果
, 則稱
是R—超線性收斂於
; 如果
, 則稱
是R—線性收斂於
; 如果
, 則稱
是R—次線性收斂於
.
- 如果
, 則稱
是R—超平方收斂於
; 如果
, 則稱
是R—平方收斂於
; 如果
, 則稱
是R—次平方收斂於
.
注意: R—次線性收斂與R—次平方收斂的評判標準有些微差別. 「R—平方收斂」也稱為「R—二次收斂」.
依照R—平方收斂 (不是R—線性收斂) 的定義, 可以定義R—立方收斂 (將
改為
), R—四次方收斂等更高R—收斂階.
- 根收斂階
的定義式如下:
![{\displaystyle O_{R}=\inf\{p|p\in [1,+\infty ){\text{ 且 }}R_{p}=1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4767a98986059c019a4dc6e76f7b1e6b42cfdff)
對比根收斂因子的描述, 根收斂階是指求出一個數
(不一定是整數), 使得對於
, 點列
都是R—次
次方收於, 且對於
,
都是R—
次方收斂. 而這個數
就是點列的根收斂階.
兩種收斂階的聯繫[編輯]
對於一個收斂點列而言, 其Q—收斂階不大於其R—收斂階, 即
![{\displaystyle O_{Q}\leq O_{R}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32d36292e57fd52ccd2037256e6d5f5c6a807998)
有時, 一個數列的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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca7ee3bdf7dd74e9e4dc11f3cba474a3f50a7246)
容易計算:
, 故該數列是Q線性收斂的; 滿足
的
的集合為
, 此集合的下確界為
, 故該數列的收斂階為
. 而同理, 可計算得該數列是R線性收性, R收斂階為
.
向量列[編輯]
有如下向量列:
.
據上作出計算如下,
![{\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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3981236d9378152bf29d7b1b02edf61c88ea868f)
故數列為Q線性收斂; Q收斂階為
;
![{\displaystyle R_{1}=\limsup _{k\rightarrow \infty }(a^{2k}+b^{2k})^{1/2k}=\max\{a,b\}<1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1547434014d634299ad22b335fb823a713dabfc9)
故數列為R線性收斂; R收斂階為
.
優化演算法的疊代點列[編輯]
牛頓法[編輯]
注: 此處的牛頓法指應用於最佳化的牛頓法.
可以證明, 如果牛頓法的目標函數
的二階導數
在其收斂點
處Lipschitz連續, 則滿足不等式
![{\displaystyle 0<{\frac {|x_{k+1}-x_{\infty }|}{|x_{k}-x_{\infty }|}}<+\infty .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/311d58acde30464aaad82887b9f39919ae598bb1)
此說明牛頓法的疊代點列是Q平方收斂; 另言之, 牛頓法的收斂速度是二次的. [2]
參考文獻[編輯]
- ^ Ortega, J R; Rheinboldt, WC. Iterative Solution of Nonlinear Equations in Several Variables. London: Academic Press. 1970.
- ^ 袁亞湘. 非線性優化計算方法. 北京: 科學出版社. 2008年2月: 17. ISBN 978-7-03-020883-5 (中文(簡體)).