梯度下降法和牛頓法計算開根號

本文將介紹如何不調包，只能使用加減乘除法實現對根號x的求解。主要介紹梯度下降和牛頓法者兩種方法，并給出 C++ 實現。

梯度下降法

思路/步驟

1. 轉化問題，將 $\sqrt{x}$ 的求解轉化為最小化目標函數：$L(t)$，$L(t)=(t^2?x)$ ，當 $L$ 趨近于 0 時，$t$ 就是我們想要的結果；
2. 迭代尋找使得 $L$ 變小的 $t$ ，
3. 最終得到足夠小的 $L$ 時的 $t$ ，即使得 $L\to 0$， 得到結果 $t$
4. 求解 $L$ 的極小值，就是導數為 0 的點

如何迭代

OK，現在的問題就是要如何進行迭代，從而得到盡可能小的 $L$，為此，我們要使得隨著每一次迭代中 $t$ 的變化，$L$ 都朝著更小的方向變化一個合適的步長。

確定如何迭代，無非就是要確定每次迭代的方向和步長。

最自然的想法，我們使得 $t$ 朝政府兩個方向都移動一個很小的步長，然后比一比，看哪個的 $L$ 更小了，就向哪個方向移動。即：

• 若 $L(t+\Delta t)<L(t)$ ，則 $t_1=t+\Delta t$；
• 若 $L(t?\Delta t)<L(t)$ ，則 $t_1=t?\Delta t$；

注意這里的 $\Delta t$ 應當是一個大于零的無窮小數，即 $0^{+}$ 。

我們接下來再對上面的式子進行一點變化：

• 若 $L(t+\Delta t)?L(t)<0$ ，則 $t_1=t+\Delta t$；
• 若 $L(t)?L(t?\Delta t)>0$ ，則 $t_1=t?\Delta t$；

將這兩個式子寫在一起：
$$t_1=t?\frac{L(t+\Delta t)?L(t)}{|L(t+\Delta t)?L(t)|}?\Delta t$$
這里的 $\frac{L(t+\Delta t)?L(t)}{|L(t+\Delta t)?L(t)|}$ 用來指示正負號。再進行一點變形：
$$\begin{array}{rl}{t}_1& =t?\frac{L(t+\Delta t)?L(t)}{|L(t+\Delta t)?L(t)|}?\Delta t\\ & =t?\frac{\frac{L(t+\Delta t)?L(t)}{\Delta t}}{|\frac{L(t+\Delta t)?L(t)}{\Delta t}|}?\Delta t\\ & =t?\frac{L(t+\Delta t)}{\Delta t}\frac{\Delta t}{|\frac{L(t+\Delta t)?L(t)}{\Delta t}|}\\ & =t?\alpha L^{\prime }(t),\alpha =\frac{\Delta t}{|\frac{L(t+\Delta t)?L(t)}{\Delta t}|}\to 0^{+},L^{\prime }(t)=\frac{L(t+\Delta t)?L(t)}{\Delta t}\end{array}\text{\hspace{1em}?}$$

1. 當a取無窮小時，雖然一定保證下降，但效率太慢

2. 日常設計的很多函數，可以允許使用相對大一些的步長，比如 $\alpha =0.01$。理由是，若步長大了，出現跳過合適位置，使得 $L(t1)>L(t0)$。再下一個時刻，依舊可能跳回來使得 $L(t2)<L(t1)$

3. 大的步長不能保證一定收斂，但是大部分時候是可以很好的工作，也因此，步長 $\alpha$，我們稱之為學習率，通常會給一個相對小的數字，但不會太小。

4. 總之，學習率一般需要在不同的模型任務中手動調試。

代碼

float sqrt_grad_decent(float x) {float t = x / 2;float L = (t * t - x) * (t * t - x);float alpha = 0.001;while ( L > 1e-5 ) {float delta = 2 * (t * t - x) * 2 * t;t = t - alpha * delta;L = (t * t - x) * (t * t - x);printf("t=%f\n", t);}return t;
}

總結

1. 梯度下降法是通過觀察局部，決定如何調整的算法。如果函數具有多個極值，則可能陷入局部極值，此時初始點的選擇直接影響收斂結果

2. 大的步長在一定程度上可能跨過局部極值，但也可能造成震蕩導致不收斂

3. 步長的選擇，需要根據函數的特性來找到合適取值，若導數特別大時，則步長取小，導數小時，步長可大。否則很容易造成收斂問題

4. 存在一類算法，可以在一定范圍內搜索一個合適步長，使得每一次迭代更加穩定

牛頓法1

梯度下降法常用語求解函數極小值的情況，而牛頓法常用于求解函數零點的情況，即 $L=0$ 時方程的根。

思路/步驟

1. 轉化問題，將求解 $\sqrt{x}$ 轉換為求解 $L(t)=t^2?x=0$ 時的根，即函數的零點
2. 迭代尋找 $t$

如何迭代

用曲線在 $t_0$ 處切線與 $x$ 軸的交點作為 $t_1$ ，來逼近函數的零點。圖/牛頓法

切線斜率，同樣可以用導數來表示 。

考慮兩個坐標系：原坐標系 $o1$ ，新坐標系 $o2$ ，其中 $o2$ 以 $o1$ 中的 $(x_1,f(x_1))$ 為原點。則在 $o2$ 坐標系中，下圖紅色切線可表示為：
$$f_{o2}(x)=f^{\prime }(x_1)x$$
則該切線與 $x$ 軸交點：
$$f_{o2}(x_2)=f^{\prime }(x_1)(x_2?x_1)=?f(x_1)$$
則有：
$$\begin{gathered} x_2?x_1=?\frac{f(x_1)}{f^{\prime }(x_1)} \\ {x}_2=x_1?\frac{f(x_1)}{f^{\prime }(x_1)} \end{gathered}$$

代碼

我們經過上一小節已經知道迭代的方法：
$$t_1=t?\frac{L(t)}{L^{\prime }(t)}$$
代碼：

float sqrt_newton1(float x) {float t = x / 2;float L = t * t - x;while ( abs(L) > 1e-5 ) {float dL = 2 * t;t = t - L / dL;L = t * t - x;}return t;
}

牛頓法2

思路

既然牛頓法是對函數求零點，那我們能不能對函數的導函數求零點呢？這樣就可以得到函數的極值了。

與梯度下降法的目標函數 $L(t)=(t^2?x)$ 是相同的，而區別在于，迭代式不同 $t_1=t?\frac{f^{\prime }(t)}{f^{\prime \prime }(t)}$，并且其中步長（學習率）為 1。

代碼

float sqrt_newton2(float x) {float t = x / 2;float L = (t * t - x) * (t * t - x);while ( L > 1e-5 ) {float dL = 2 * (t * t - x) * 2 * t;float d2L = 12 * t * t - 4 * x;t = t - dL / d2L;L = (t * t - x) * (t * t - x);}return t;
}

Ref

1. 牛頓法