收斂速度

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

定義

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

商收斂因子及商收斂階

• 商收斂因子$Q_p$的定義式如下:

$Q_p=\underset{k\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{||x_{k+1}-x^{*}|{|}_2}{||x_k-x^{*}|{|}_2^p},p\in [1,+\mathrm{\infty }]$

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

1. 如果$Q_1=0$, 則稱$\{x_k\}$是Q—超線性收斂於$x^{*}$; 如果$0<Q_1<1$, 則稱$\{x_k\}$是Q—線性收斂於$x^{*}$; 如果$Q_1\ge 1$, 則稱$\{x_k\}$是Q—次線性收斂於$x^{*}$.
2. 如果$Q_2=0$, 則稱$\{x_k\}$是Q—超平方收斂於$x^{*}$; 如果$0<Q_2<+\mathrm{\infty }$, 則稱$\{x_k\}$是Q—平方收斂於$x^{*}$; 如果$Q_2=+\mathrm{\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,+\mathrm{\infty })\text{ 且 }{Q}_p=+\mathrm{\infty }\}$

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

根收斂因子及根收斂階

• 根收斂因子$R_p$的定義式如下:

$R_p=\{\begin{array}{cc}\underset{k\to \mathrm{\infty }}{\mathrm{lim\; sup}}||x_k-x^{*}|{|}_2^{1/k},& \text{ when }p=1,\\ \underset{k\to \mathrm{\infty }}{\mathrm{lim\; sup}}||x_k-x^{*}|{|}_2^{1/p^k},& \text{ when }p>1.\end{array}$

根收斂因子也稱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\ge +\mathrm{\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,+\mathrm{\infty })\text{ 且 }{R}_p=1\}$

對比根收斂因子的描述, 根收斂階是指求出一個數$n\ge 1$ (不一定是整數), 使得對於$\mathrm{\forall }{t}_1\ge n$, 點列$\{x_k\}$都是R—次$t_1$次方收於, 且對於$t_2<n$, $\{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_{\mathrm{\infty }}=0.$

容易計算: $Q_1=\frac{1}{2}$, 故該數列是Q線性收斂的; 滿足$Q_p=+\mathrm{\infty }$的$p$的集合為$\{x|x>1\}$, 此集合的下確界為$1$, 故該數列的收斂階為$1$. 而同理, 可計算得該數列是R線性收性, R收斂階為$1$.

向量列

有如下向量列:

$v^{(1)}=(a,b{)}^{𝐓},v^{(2)}=(a^2,b^2{)}^{𝐓},\cdots ,v^{(k)}=(a^k,b^k{)}^{𝐓},\cdots ,v^{(\mathrm{\infty })}=(0,0{)}^{𝐓}.(0<a^2+b^2<1)$.

據上作出計算如下,

$Q_1=\underset{k\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{\Vert (a^{k+1},b^{k+1}{)}^{𝐓}{\Vert }_2}{\Vert (a^k,b^k{)}^{𝐓}{\Vert }_2}=\underset{k\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{\sqrt{(a^{k+1}{)}^2+(b^{k+1}{)}^2}}{\sqrt{(a^k{)}^2+(b_k{)}^2}}<\underset{k\to \mathrm{\infty }}{\mathrm{lim\; sup}}\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=\underset{k\to \mathrm{\infty }}{\mathrm{lim\; sup}}(a^{2k}+b^{2k}{)}^{1/2k}=\max \{a,b\}<1,$

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

優化算法的疊代點列

牛頓法

注: 此处的牛頓法指應用於最優化的牛頓法.

可以證明, 如果牛頓法的目標函數$f(x)$的二階導數$f^{\prime \prime }(x)$在其收斂點$x_{\mathrm{\infty }}$處Lipschitz連續, 則滿足不等式

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

此說明牛頓法的疊代點列是Q平方收斂; 另言之, 牛頓法的收斂速度是二次的.