查看“︁收斂速度”︁的源代码

{{Refimprove|time=2017-09-06T17:45:30+00:00}}
{{noteTA|G1=Math|G2=IT}}
在[[數值分析]]中, 一個收斂序列向其[[極限 (數列) |極限]]逼近的速度稱為'''收斂速度'''. 該概念多用於[[最優化]][[算法]]中; 其被定義為一個疊代序列向其'''局部最優值'''逼近 (假設計算過程收斂, 並能逹到最優值) 的速度, 是評價一個[[疊代法]]於該問題中發揮的性能的一個重要指標. 

== 定義 ==
收斂速度以收斂階衡量, 亦可以收斂因子描述; 依計算方法的不同, 有下述兩種收斂階及收斂因子.<ref>{{cite journal en |last=Ortega|first=J R|last2=Rheinboldt|first2=WC|title=Iterative Solution of Nonlinear Equations in Several Variables|year=1970|url=https://archive.org/details/iterativesolutio0000orte|location=London|publisher=Academic Press}}</ref>

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

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

'''注意: '''''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''—超線性收斂'''於<math>x^*</math>; 如果<math>0<R_1<1</math>, 則稱<math>\{x_k\}</math>是'''''R''—線性收斂'''於<math>x^*</math>; 如果<math>R_1= 1</math>, 則稱<math>\{x_k\}</math>是'''''R''—次線性收斂'''於<math>x^*</math>. 
#如果<math>R_2=0</math>, 則稱<math>\{x_k\}</math>是'''''R''—超平方收斂'''於<math>x^*</math>; 如果<math>0<R_2<1</math>, 則稱<math>\{x_k\}</math>是'''''R''—平方收斂'''於<math>x^*</math>; 如果<math>R_2\ge+\infty</math>, 則稱<math>\{x_k\}</math>是'''''R''—次平方收斂'''於<math>x^*</math>.
 
'''注意: ''R''—次線性收斂與''R''—次平方收斂的評判標準有些微差別. 「''R''—平方收斂」也稱為「''R''—二次收斂」. 

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


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

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


=== 兩種收斂階的聯繫 ===
對於一個收斂點列而言, 其''Q''—收斂階不大於其''R''—收斂階, 即
:<math>O_Q\le O_R.</math>
有時, 一個數列的''R''—收斂階可能很高, 但其''Q''—收斂階可能很低. 當然可以證明, 一個''R''—收斂階高的點列至少比某些''Q''—收斂低的點列收斂得更快.

== 實例 ==
=== 數列 ===
有如下數列:
:<math>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.</math>
容易計算: <math>Q_1=\frac{1}{2}</math>, 故該數列是''Q''線性收斂的; 滿足<math>Q_p=+\infty</math>的<math>p</math>的[[集合 (數學)|集合]]為<math>\{x|x>1\}</math>, 此集合的[[下確界]]為<math>1</math>, 故該數列的收斂階為<math>1</math>. 而同理, 可計算得該數列是''R''線性收性, ''R''收斂階為<math>1</math>.

=== 向量列 ===
有如下[[向量]]列: 
:<math>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)</math>.
據上作出計算如下, 
::<math>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, </math>
故數列為''Q''線性收斂; ''Q''收斂階為<math>1</math>; 
::<math>R_1=\limsup_{k\rightarrow\infty}(a^{2k}+b^{2k})^{1/2k}=\max\{a,b\}<1, </math>
故數列為''R''線性收斂; ''R''收斂階為<math>1</math>.

=== 優化算法的疊代點列 ===
==== 牛頓法 ====
注: 此处的''牛頓法''指[[應用於最優化的牛頓法]].

可以證明, 如果牛頓法的目標函數<math>f(x)</math>的二階導數<math>f^{\prime\prime}(x)</math>在其收斂點<math>x_\infty</math>處[[利普希茨連續|Lipschitz連續]], 則滿足不等式
:<math>0<\frac{|x_{k+1}-x_\infty|}{|x_k-x_\infty|}<+\infty.</math>
此說明牛頓法的疊代點列是''Q''平方收斂; 另言之, 牛頓法的收斂速度是二次的. <ref> {{Cite book | author = 袁亞湘 | title = 非線性優化計算方法 | location = 北京 | publisher = 科學出版社 | date = 2008年2月 | pages = 17 | ISBN = 978-7-03-020883-5 | accessdate = 2017-09-14 | language = zh-hans  }} </ref>

== 參考文獻 ==
<references />

[[Category:数值分析]]
[[Category:率|Convergence]]