[演算法] 平方收斂與超線性收斂

這次要介紹演算法中的兩種收斂速度 (Speed of convergence)：

1. 平方收斂 (Quadratic Convergence)
2. 超線性收斂 (Superlinear Convergence)

首先介紹 Quadratic Convergence 定義：

===========================

Definition: (Quadratic Convergence)

一個演算法被稱作是 具有二次收斂(Quadratically Convergent) 如果下列條件成立：

若將此演算法應用到二階型態的成本函數 $J: \mathbb{R}^n \rightarrow \mathbb{R}$：

$$J(u) = u^T A u + b^T u + c, \ A \succ 0$$ 其最佳解可以在 $n$ 步或者少於 $n$ 步之內被求得。

===========================

Comments:
1. 最陡坡度法 Steepest Descents Algorithm (fixed step & optimal step) 都不具備 Quadratic Convergence。(事實上最陡坡度法在搜尋解的時候會有 (歪來歪去!?) Zig-zag 的本質，這使得此法再在某些情況會收斂的異常緩慢甚至永遠不收斂...)

2. 牛頓法 (Newton-Raphson Algorithm)為Quadratic Convergence。關於牛頓法請參考：[最佳化] Generalized Newton Raphson Algorithm

3. Conjugate Direction Algorithm 為 Quadratic Convergence。有興趣的讀者請參考 Conjugate Direction Method 系列文章：[最佳化理論] Conjugate Direction Methods (0) -Basic Theory

再來要介紹的是超線性收斂(Superlinear Convergence)

===========================
Definition (Superlinear Convergence)
一個 sequence $\{ u^k\}_{k=1}^{\infty} \in \mathbb{R}^n$ 被稱作是超線性收斂 superlinear convergence 到 $u^*$ 如果下列條件成立：
給定 任意 $\theta \in (0,1)$，我們有 $\frac{||u^k - u^*||}{\theta^k} \rightarrow 0$；亦即
$$\displaystyle \lim_{k \rightarrow \infty} \frac{||u^k - u^*||}{\theta^k} \rightarrow 0 \ \ \ \ \square$$ ===========================

Comments:
1. 超線性收斂顧名思義就是其收斂速度非常的快。比線性收斂更快。我們現在用下面幾個(收斂的)例子便可以看出超線性收斂確實是快!  比如說甚至 $exp(-k)$ 函數都不是超線性收斂。
2. Conjugate Direction Algorithm 具備 Superlinear Convergence。

現在來看看幾個例子：

===========================

Example 1:

$u^k = 1/k$ 是否為超線性收斂到 $u^* =0 ?$

Sol: NO!
由定義我們可以任意選 $\theta \in (0,1)$，故如果今天我們選 $\theta =1/2$，則
$$\displaystyle \lim_{k \rightarrow \infty} \frac{||u^k - u^*||}{\theta^k} = \displaystyle \lim_{k \rightarrow \infty} \frac{1/k}{(1/2)^k} =   \displaystyle \lim_{k \rightarrow \infty} \frac{2^k}{k} \nrightarrow 0$$ 事實上上述極限不收斂 $(\rightarrow \infty)$ $\square$

===========================

Example 2

$u^k = 1/k^2$ 是否為超線性收斂到 $u^* =0 ?$

Sol: NO!
同上題，選 $\theta = 1/2$ 仍然讓此Sequence爆掉。

===========================

Example 3
$u^k = e^{-k}$ 是否為超線性收斂 到 $u^* = 0?$

Sol: No
注意到 $exp = 2.7183xxx$，故如果我們選 $\theta = 1/3$ 則
$$\displaystyle \lim_{k \rightarrow \infty} \frac{||u^k - u^*||}{\theta^k} = \displaystyle \lim_{k \rightarrow \infty} \frac{e^{-k}}{(1/3)^k} =   \displaystyle \lim_{k \rightarrow \infty} 3^k{e^{-k}} =  \displaystyle \lim_{k \rightarrow \infty} 3^k (2.7183....)^{-k} \nrightarrow 0$$ $\square$
===========================

Example 4
$u^k = e^{-k^2}$ 是否為超線性收斂 到 $u^* = 0?$

Sol: YES
觀察
$$\displaystyle \lim_{k \rightarrow \infty} \frac{||u^k - u^*||}{\theta^k} = \displaystyle \lim_{k \rightarrow \infty} \frac{e^{-k^2}}{\theta^k}$$
注意到上式中的 $\frac{e^{-k^2}}{\theta^k}$ 可改寫為
$${e^{ - {k^2}}}{\theta ^{ - k}} = {e^{ - {k^2}}}{e^{\ln {\theta ^{ - k}}}} = {e^{ - {k^2} + k\ln \frac{1}{\theta }}}$$ 注意到不管 $\theta \in (0,1)$ 怎麼選，前方的 $-k^2$ 項都主導整個收斂速度，故上式收斂到 $u^* =0$，亦即 $u^k = e^{-k^2}$ 為超線性收斂 到 $u^* = 0$ $\square$

===========================

Example 5
$u^k = (1/k)^k$ 是否為超線性收斂 到 $u^* = 0?$

Sol: YES
由定義可知
$$\mathop {\lim }\limits_{k \to \infty } \frac{{\left\| {{u^k} - {u^*}} \right\|}}{{{\theta ^k}}} = \mathop {\lim }\limits_{k \to \infty } \frac{{{{\left( {1/k} \right)}^k}}}{{{\theta ^k}}} \ \ \ \ (\star)$$ 現在我們觀察
$$\frac{{{{\left( {1/k} \right)}^k}}}{{{\theta ^k}}} = {k^{ - k}}{\theta ^{ - k}} = {\left( {k\theta } \right)^{ - k}}$$ 又因為 $0 < \theta < 1$，亦即無論 $\theta$ 怎麼選，式 $(\star)$ 都必收斂
$$\mathop {\lim }\limits_{k \to \infty } {\left( {k\theta } \right)^{ - k}} \to 0$$ 故 $u^k = (1/k)^k$ 為超線性收斂。$\square$