今天是週四高等數學專題的第7篇文章。
之前的文章和大家聊了許多數學上的理論，今天和大家聊點有用的東西。
我們都知道，工業上的很多問題經過抽象和建模之後，本質還是數學問題。而說到數學問題就離不開方程，在數學上我們可以用各種推算、公式，但是有沒有想過在計算機領域我們如何解一個比較複雜的方程？
如果之前沒有想過，那你可能得想一想，因為以後很有可能會在面試題當中遇到。
二分法
我們要介紹的第一個方法是二分法。
說到二分法大家應該都不陌生，老實說我第一次在高數課本上看到二分法這三個字的時候，其實是蠻震驚的。後來當我又在統計等數學書上看到許多其他算法之後，才慢慢習以為常。在我轉行做算法的這幾年當中，我越來越意識到，數學的重要性。雖然這並不意味著你一定要成為數學高手，但如果你還沒畢業的話，至少數學課好好聽講還是很有必要的。
我們說回二分法，如果學過二分法，會覺得這是一個非常簡單的算法，但如果你們做過LeetCode第四題，又會發現純二分法的題也可以這麼難。如果只是單純地講解二分法的原理，我們是很難完完全全將這個算法吃透的。為了達到這點，我思考了很久，最終決定仿照看山是不是山的禪宗理論，將二分法也分成三個層次。
首先是第一個層次，即我們每次將一個東西分成兩半。
這個應該是我們最初也是最直觀的觀念，比如最經典的金幣問題。說是我們有若干個個硬幣，其中有一個是金幣，金幣的重量更重，其他的硬幣重量相等。我們只有一個天平，怎麼樣用最少的次數找出金幣。
在這個問題當中，我們需要不停地將硬幣分成兩個部分，用天平鎖定其中的一個。通過不斷重複上述操作，快速找到答案。
在第二個層次當中，二分法不再是簡單地將物體一分為二，而是一個折半查找的函數。這也是本文重點要介紹的解方程的方法。
如果有函數 f(x) ，它在區間[a, b]上遞增或者遞減，並且 f(a)*f(b) < 0。那麼我們知道函數必然有一個等於0的解，而且這個解我們可以用二分法來求近似解。
在上圖當中，f(x)遞增，並且f(a) < 0, f(b) > 0。我們繼續獲取了a和b的中點 x0。根據上圖，我們又得到 f(x0) > 0，所以我們可以把 x0 看成是新的b。於是我們繼續尋找a和 x0 的中點，重複上述過程，由於我們最大的誤差就是區間的長度，所以當我們區間的長度縮減到足夠小，那麼就說明我們已經找到了一個足夠近似的解。
在二分法當中，我們沒進行一次二分迭代，區間的長度就會縮減一半，這是一個指數級的縮減。所以即使一開始的區間很大，經過二分迭代也可以迅速縮減，得到一個非常精準的結果，並且和泰勒級數一樣，除了能得到一個足夠精確的值之外，還能得到誤差的範圍。
我們再深入一些思考，會發現有些條件我們還可以再鬆動鬆動。比如我們真的需要函數是嚴格遞增或者遞減嗎？比如我們來看下面這張圖：
在(b2, b1)區間內，函數並不是嚴格遞減的，而是先遞減再遞增的。但是這並不會影響結果的正確性，因為在這個問題當中，二分法並不是通過判斷 f(x0) 和a處函數值的大小來縮小區間的，而是通過f(x0)的正負性。也就是說，只需要滿足 f(a)*f(b) < 0，並且函數連續且等於0的點只有一個，就可以使用二分來進行查找。
深入思考，就進入了二分法的第三個層次，即放下遞增的限制，回到折半這個原始的概念上來。
二分法的本質就是查找空間折半，至於函數遞增或者是數組當中元素遞增都只是表象，只是我們進行折半的條件。換句話說如果我們能找到其他的條件來折半搜索空間，那麼我們一樣可以得到二分的效果，並不用拘泥於是否有序。
也就是說我們繞了一圈，最後又回到了將“物體”一分為二這個最基本的概念上來。只是我們經過這麼一波折騰，表面上看和最初的理解一樣，但其實早已天差地別了。
沒想到算法領域也能玩一把禪宗，看山是山，看山不是山，最後回到看山還是山。
牛頓迭代法
看完了二分法，我們再來看另一個快速求根的方法，和二分法一樣，它也是迭代逼近的方法，但是逼近的速度更快。這個方法最早是牛頓提出的，因此也被稱為牛頓迭代法，我想牛頓這個名字寫出來，大家應該都能get到它的分量。
牛頓迭代法的名頭看起來很唬人，但是原理真的不難，說白了只有一句話，就是通過切線去逼近，比如我們來看下圖：
在上圖當中，我們要求 f(x)=0 的根，我們先找到了一個 xn點，我們在 xn 處進行求導取得了它的切線。顯然只要這個切線的斜率不為0，那麼我們一定可以獲得它和x軸的交點。我們將這個交點作為下一個取值，也就是 xn+1的點。我們重複上述過程進行迭代，很快就可以得到一個足夠接近的解。
對於點 xn 處的切線而言，它的斜率是 f'(xn)，截距b就是 f(xn)。它的切線方程很好得到，就是：
我們利用這個方程，可以求到它和x軸的交點，也就是xn+1的值：
解下這個方程，可以得到：
上面這個式子就是牛頓迭代法的迭代公式，這是一個非常牛的方法，比二分法要厲害得多，因為它的收斂速度更快，並且計算也並不複雜。
我們來看下它的威力，我們來看知乎鍵山小鞠[1] 大神回答裡的一個例子：
我們利用 f(x) = sin(x) 來求 π 的值，我們都知道在 [π/2, π] 區間內， sin(π) = 0，所以我們求 f(x) = 0 的解就可以間接求出π的值。
在這個問題下，迭代公式為：
我們以 x0 = 3 為迭代起始點，進行迭代，得到的結果如下：
<code>x0=3.0(1位)
x1=3.1411...(4位)
x2=3.14159265357...(11位)
x3=3.1415926535897932384626433832795020...(34位)
x4=3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706786...(102位)
x5=3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412734...(301位)/<code>
可以看到，短短經過五次迭代，我們計算得到的圓周率已經超過了300位，每次迭代我們的精度都會提升三倍以上，這是非常令人震驚的。
無法收斂的情況
但令人遺憾的是並不是所有方程使用牛頓迭代法都可以有這麼好的效果，對於一些方程，甚至可能會出現越走越偏的情況。我們再舉個例子，比如方程:
如果我們畫出它的迭代過程，是這樣的：
我們觀察一下上面的迭代公式也可以看得出來，我們把 -1/f'(xn) 看成是係數，我們對 f(x) 求導算下這個係數，可以得到它的係數是3*x^{2/3}，觀察一下就能發現隨著x的增大，這個係數也是在增大的。也就是說，隨著我們的迭代，這個值會變得越來越大，也就意味著我們的振幅越來越大，也就離收斂越來越遠。
雖然少數情況下牛頓迭代法不能收斂，但是大多數情況下它效果都非常好。二分法固定每次縮短一半的區間，而牛頓迭代法的迭代效率往往更高，一般情況下使用牛頓迭代法可以獲得更快的收斂速度。和二分法相比，牛頓迭代法的公式也並不難寫，並且它在機器學習當中也有應用，學會它真的非常划算！
今天關於二分和牛頓迭代法的文章就到這裡，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
[1]
知乎: "https://www.zhihu.com/question/20690553"
閱讀更多 承志的算法課堂 的文章
