收斂速度

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

## 定義

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

### 商收斂因子及商收斂階

* **商收斂因子** $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_ 平方收斂；另言之，牛頓法的收斂速度是二次的. 

## 參考文獻