跳至內容

收斂速度

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

數值分析中, 一個收斂序列向其極限逼近的速度稱為收斂速度. 該概念多用於最佳化演算法中; 其被定義為一個疊代序列向其局部最優值逼近 (假設計算過程收斂, 並能逹到最優值) 的速度, 是評價一個疊代法於該問題中發揮的效能的一個重要指標.

定義

[編輯]

收斂速度以收斂階衡量, 亦可以收斂因子描述; 依計算方法的不同, 有下述兩種收斂階及收斂因子.[1]

商收斂因子及商收斂階

[編輯]
  • 商收斂因子的定義式如下:

商收斂因子也稱Q—因子, 商收斂階也稱Q—收斂階. 利用商收斂因子, 對收斂速度進行描述的方式如下:

  1. 如果, 則稱Q—超線性收斂; 如果, 則稱Q—線性收斂; 如果, 則稱Q—次線性收斂.
  2. 如果, 則稱Q—超平方收斂; 如果, 則稱Q—平方收斂; 如果, 則稱Q—次平方收斂.

注意: Q—線性收斂與Q—平方收斂, 以及Q—次線性收斂與Q—次平方收斂的評判標準有些微差別. 「Q—平方收斂」也稱為「Q—二次收斂」.

依照Q—平方收斂 (不是Q—線性收斂) 的定義, 可以定義Q—立方收斂 (將改為), Q—四次方收斂等更高Q—收斂階.


  • 商收斂階的定義式如下:

對比商收斂因子的描述, 商收斂階是指求出一個數 (不一定是整數), 使得對於, 點列都是Q—次次方收於, 且對於, 都是Q次方收斂. 而這個數就是點列的商收斂階.


根收斂因子及根收斂階

[編輯]
  • 根收斂因子的定義式如下:

根收斂因子也稱R—因子, 根收斂階也稱R—收斂階. 利用根收斂因子, 對收斂速度進行描述的方式如下:

  1. 如果, 則稱R—超線性收斂; 如果, 則稱R—線性收斂; 如果, 則稱R—次線性收斂.
  2. 如果, 則稱R—超平方收斂; 如果, 則稱R—平方收斂; 如果, 則稱R—次平方收斂.

注意: R—次線性收斂與R—次平方收斂的評判標準有些微差別. 「R—平方收斂」也稱為「R—二次收斂」.

依照R—平方收斂 (不是R—線性收斂) 的定義, 可以定義R—立方收斂 (將改為), R—四次方收斂等更高R—收斂階.


  • 根收斂階的定義式如下:

對比根收斂因子的描述, 根收斂階是指求出一個數 (不一定是整數), 使得對於, 點列都是R—次次方收於, 且對於, 都是R次方收斂. 而這個數就是點列的根收斂階.


兩種收斂階的聯繫

[編輯]

對於一個收斂點列而言, 其Q—收斂階不大於其R—收斂階, 即

有時, 一個數列的R—收斂階可能很高, 但其Q—收斂階可能很低. 當然可以證明, 一個R—收斂階高的點列至少比某些Q—收斂低的點列收斂得更快.

實例

[編輯]

數列

[編輯]

有如下數列:

容易計算: , 故該數列是Q線性收斂的; 滿足集合, 此集合的下確界, 故該數列的收斂階為. 而同理, 可計算得該數列是R線性收性, R收斂階為.

向量列

[編輯]

有如下向量列:

.

據上作出計算如下,

故數列為Q線性收斂; Q收斂階為;

故數列為R線性收斂; R收斂階為.

優化演算法的疊代點列

[編輯]

牛頓法

[編輯]

注: 此處的牛頓法應用於最佳化的牛頓法.

可以證明, 如果牛頓法的目標函數的二階導數在其收斂點Lipschitz連續, 則滿足不等式

此說明牛頓法的疊代點列是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 (中文(簡體)).