收斂速度

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

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

### 商收斂因子及商收斂階
***商收斂因子**Q_p的定義式如下:
::Q_p=\limsup_{k\rightarrow\infty}\frac{||x_{k+1}-x^*||_2}{||x_k-x^*||^p_2}, p\in [1,+\infty]

**商收斂因子**也稱***Q''—因子''', '''商收斂階'''也稱***Q*—收斂階*'. 利用商收斂因子, 對收斂速度進行描述的方式如下: 
#如果Q_1=0, 則稱\{x_k\}是***Q''—超線性收斂'''於<math>x^*</math>; 如果<math>0<Q_1<1</math>, 則稱<math>\{x_k\}</math>是***Q*—線性收斂*'於x^*; 如果Q_1\ge 1, 則稱\{x_k\}是***Q''—次線性收斂'''於<math>x^*</math>. 
#如果<math>Q_2=0</math>, 則稱<math>\{x_k\}</math>是***Q*—超平方收斂*'於x^*; 如果0, 則稱\{x_k\}是***Q''—平方收斂'''於<math>x^*</math>; 如果<math>Q_2=+\infty</math>, 則稱<math>\{x_k\}</math>是***Q*—次平方收斂*'於x^*. 

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

依照***Q''—平方收斂''' ('''不是''Q''—線性收斂''') 的定義, 可以定義''Q''—立方收斂 (將<math>Q_2</math>改為<math>Q_3</math>), ''Q''—四次方收斂等更高''Q''—收斂階. 


*'''商收斂階'''<math>O_Q</math>的定義式如下: 
::<math>O_Q=\inf\{p|p\in [1,+\infty)\text{ 且 }Q_p=+\infty\}</math>

對比商收斂因子的描述, 商收斂階是指求出一個數<math>n\ge1</math> (不一定是[[整數]]), 使得對於<math>\forall t_1\ge n</math>, 點列<math>\{x_k\}</math>都是''Q''—次<math>t_1</math>次方收於, 且對於<math>t_2<n</math>, <math>\{x_k\}</math>都是''Q''—<math>t_2</math>次方收斂. 而這個數<math>n</math>就是點列的商收斂階. 


=== 根收斂因子及根收斂階 ===
*'''根收斂因子'''<math>R_p</math>的定義式如下:
::<math>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.</math>

'''根收斂因子'''也稱***R*—因子*', **根收斂階**也稱***R''—收斂階'''. 利用根收斂因子, 對收斂速度進行描述的方式如下: 
#如果<math>R_1=0</math>, 則稱<math>\{x_k\}</math>是***R*—超線性收斂*'於x^*; 如果0, 則稱\{x_k\}是***R''—線性收斂'''於<math>x^*</math>; 如果<math>R_1= 1</math>, 則稱<math>\{x_k\}</math>是***R*—次線性收斂*'於x^*. 
#如果R_2=0, 則稱\{x_k\}是***R''—超平方收斂'''於<math>x^*</math>; 如果<math>0<R_2<1</math>, 則稱<math>\{x_k\}</math>是***R*—平方收斂*'於x^*; 如果R_2\ge+\infty, 則稱\{x_k\}是***R''—次平方收斂'''於<math>x^*</math>.
 
'''注意: ''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\ge1 (不一定是整數), 使得對於\forall t_1\ge n, 點列\{x_k\}都是*R*—次t_1次方收於, 且對於t_2, \{x_k\}都是*R*—\ \ t_2次方收斂. 而這個數n就是點列的根收斂階. 

### 兩種收斂階的聯繫
對於一個收斂點列而言, 其*Q*—收斂階不大於其*R*—收斂階, 即
:O_Q\le 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.
據上作出計算如下, 
::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}}
故數列為*Q*線性收斂; *Q*收斂階為1; 
::R_1=\limsup_{k\rightarrow\infty}(a^{2k}+b^{2k})^{1/2k}=\max\{a,b\}
故數列為*R*線性收斂; *R*收斂階為1.

### 優化算法的疊代點列
#### 牛頓法
注: 此处的*牛頓法*指應用於最優化的牛頓法.

可以證明, 如果牛頓法的目標函數f(x)的二階導數f^{\prime\prime}(x)在其收斂點x_\infty處Lipschitz連續, 則滿足不等式
:0
此說明牛頓法的疊代點列是*Q*平方收斂; 另言之, 牛頓法的收斂速度是二次的. 

## 參考文獻