數值分析——近似當中的精確
小編說：
謝謝大家對我們的關注，我們是由一大群來自各個領域的小夥伴輪流寫文章來分享自己對不同領域的理解，和一些心得，希望能夠為大家科普一些有趣的東西，也方便不同領域的童鞋的互相的了解與合作，因為一個領域發展的很完善的東西說不定就解決了另外一個領域的懸而未決的問題。
這篇文章介紹的是數學當中的一個偏應用領域的分支——數值分析——的基本思想和方法。數學是門有千年以上歷史的學科，它的發展特點之一是對自身概念體系的嚴格化。譬如微積分的概念在最初發展時，並沒有非常嚴格的基礎。在17世紀牛頓、萊布尼茨開創微積分理論的時候，諸如「無窮小」這樣的概念被頻繁使用，但卻並沒有被很好地定義，以致於在很長一段時間內微積分學說都因為不夠嚴謹而備受質疑。為微積分做嚴格化的努力持續了很長時間，直到150年後的19世紀，它的基礎才被柯西和魏爾斯特拉斯等人嚴格建立起來：通過epsilon - delta語言定義了極限，然後基於極限再定義了導數，以至於發展出後面的一系列理論。這樣微積分理論才無可辯駁地被數學家廣為接受。
現代數學發展到上世紀，細化出了眾多的分支。在數學的標準之下，這些分支無一例外，都是非常「嚴格」的。然而在這其中，卻出現了一門」不那麼嚴格」的學科——數值分析，或者狹義上所說的應用數學。
數值分析的發展伴隨著計算機技術的廣泛使用。這裡我們需要舉一個例子來說明它的必要性。假設我們現在要做科學計算，而算式當中用到了根號，譬如「根號10」。這個時候我們就需要知道精確到多少位是什麼樣子的。在數學的其他分支中，我們很少需要了解一個無理數的小數點後若干位是長什麼樣子的，但是在科學計算中我們就非常有必要知道。那麼問題來了，我們如何計算呢？或者一般地說，對任意一個數x，我們該如何計算它的根號呢？我們日常使用的計算器都會實現開根號的演算法。一個非常著名的方法是牛頓迭代法：首先隨便找一個數r，然後依次計算
那麼不難說明，這樣產生的數列 r_n 會逐漸逼近根號x。這個算式當中的每一個運算（加法，乘法，除法）都是可以被計算機執行的，因此我們可以把它寫成程序，放入計算機中，用來進行開根運算。然而數值分析的工作不止於此。在完成了「近似」的任務以後，還有必要進行定量分析。對應於上面這個例子就是：演算法給出的r_n，到底在什麼樣的精度上逼近"根號x"了呢？如果不回答這個問題，那麼我們對於這個計算仍然是缺少信心的，因為我們不知道這個近似解到底有多大的誤差，以及是不是符合精度上的要求。
用牛頓迭代法求二次函數的根（來源：維基百科）
數值分析中的關於收斂速度的理論證明了，上面的牛頓法是「平方收斂」的。也就是說，每進行一次迭代，r_ 與真實值的誤差大致上跟前一個 r_n 的誤差的平方在一個量級。這意味著每進行一次迭代，r_n 中正確的小數位數大致上會加倍。有了這樣的理論保證，我們就不難推算出演算法會在大約多少步以後達到預期的精度了。
（註：實際中計算器使用的開根演算法和上述可能並非完全一致，而一般是改進過的或者其他效率高的演算法。）
數值分析的發展一直遵循了上面的路徑：構造某種數學工具來計算一個東西的數值解（近似解），然後運用數學理論來分析這個數值解離真實解到底差多遠，或者說，解的誤差有多大。一個好的演算法，應該可以利用相對少的計算資源，來達到期望的誤差。
數值分析經過多年的發展，特別是依賴於計算機技術的普及進步，在很多領域得到了應用。文章的剩下部分就選幾個相對熱門的方向嘗試作一些介紹。
微分方程數值解
微分方程常常來源於物理和工程學。在航天領域中，飛行器的軌跡可以由常微分方程近似。溫度在介質中的傳導由經典的熱方程描述，物質的波動可以通過波方程研究，還有著名的流體力學方程可以描述流體（氣體或液體）隨時間的狀態改變。以上這三種方程都是偏微分方程。
非常可惜的是，對於大多數微分方程，我們都無法用顯式表達出它們的解。特別是加上一些複雜的初始和邊界條件以後，顯式求解就顯得更加不可能了。這時數學家們能做的往往只能是保證方程的解是存在的和唯一的。更有甚者，例如大名鼎鼎的Navier–Stokes方程，也就是上面提到的流體力學方程，我們對於它的解到底存不存在都搞不清楚。美國克雷數學研究所在2000年挑選出了千禧年的七大數學難題，設置每道題100萬美元的獎金，獎勵給成功給出解答的人，其中一個問題就是Navier–Stokes方程。順便值得一提的是，這七個問題中至今為止只有一個被成功解決（龐加萊猜想被證明為真），但神秘的獲獎者俄羅斯人佩雷爾曼卻拒絕了領獎以及百萬獎金。
對於微分方程，由於顯式求解不是一個選項，數值求解就變得尤為重要。在這方面非常多的演算法被發展出來，例如最為簡單的有限差分方法，還有極其成功的有限元法以及有限體積法。它們的思想都是把連續的函數用一些離散的點表示，進而把連續的微分方程轉化為離散的代數方程，使得問題可以被求解。
微分方程的一個應用實例是天氣預報。可能很多人並不了解，現代的天氣預報已經主要憑藉數值方法來生成了。大氣是流體，所以它的狀態變化可以藉助流體動力方程描述。如果把用各種方法收集到的氣象信息作為初始條件輸入到這些大氣動力模型當中，並且由計算機求解，就可以預測未來一段時間內的天氣情況。最早的數值天氣預報模型非常糟糕，「就算預測第二天的天氣跟前一天一模一樣，準確率也比數學模型要來得高」，我的數值代數老師在課上這樣講。但是由於模型的改進和計算機性能的大幅提升，現今數值預測方法已經成為主流，並且越來越少地需要人工干預了。今天世界上的很多計算能力最強的超算（超級計算機）都被用來進行天氣預報的計算。
最優化問題
最優化問題尋求某個問題的最優解，一般情況下我們希望最小化（或者最大化）一個函數。一類傳統的方法是迭代法。迭代法從一個初始點開始，不斷尋找新的點，使得函數在新點上取值更小，如此循環下去，以期望找到函數的極小點。尋找新點的方法很多，例如可以求得函數在當前位置沿各個方向的偏導數，然後沿著斜率最大的方向下降，這個方法就叫做梯度下降法。在處理二次函數的優化問題時，有特別的共軛梯度法，它相比梯度下降法收斂速度快了很多。
梯度下降法的示意圖（來源：維基百科）
由於深度學習的興起，梯度下降法在統計學習中受到了前所未有的重視。被稱為「隨機梯度下降」的演算法在每次迭代時只選擇一個或者若干個樣本進行優化，從而避免了為整個樣本集的計算梯度的巨大運算量，大大降低了運算複雜度。這使得大數據集上的機器學習成為可能。同時神經網路由於其驚人的優秀表現，成為當下很多人工智慧領域的首選工具。除了神經網路，梯度下降演算法也被應用到邏輯回歸（logistic regression）、支持向量機（SVM）等機器學習的計算當中。
矩陣的特徵空間
矩陣的特徵值和特徵向量問題是數學裡的經典內容。在理論層面，關於矩陣的特徵值和特徵向量有著非常豐富完備的結論；但在數值上對它們求解則往往是一個相當棘手的問題。在實際應用當中，對於「對稱矩陣」的特徵空間求解在統計中的主成分分析（PCA）和圖論中的譜方法（spectral graph theory）都有重要的應用。求解這樣的問題，在傳統上有QR演算法，而在最近divide-and-conquer演算法因為其效率和穩定性而受到了重視。
在本文的最後寫一點個人的想法，作為結束。數值分析在某種意義上起源於人類的好奇心，因為我們想知道諸如「根號10」、π、e 這樣的數到底等於多少。到了後來我們慢慢發現，計算這些數值的重要性，已經遠遠超過了滿足我們好奇心的程度。如果去仔細研究對這些數的一些近似方法，你會發現它們跟純理論的關係實際上是非常緊密的。所以今天我們在一些數值方法上遇到了瓶頸，例如對於流體的湍流效應不能很精確地求解，那在Navier–Stokes方程理論上的突破也許是解決問題的一條路徑。
在另一方面，我們對於未來的預測永遠都是有精度上的限制的，這是因為計算機的性能不可能無限強大，而我們對初始條件也不可能做到無限細分。這在某種程度上可能還原了數值分析的原本意義——我們可以無限地逼近真實的解，但可能永遠都無法達到那個真實的解。
作者介紹：
本文作者許文放，現就讀於賓州州立大學數學系，研究方向是偏微分方程數值解和圖論。
版權聲明：
本文採用若干網路圖片，版權歸原作者所有。本文版權歸作者許文放（以下簡稱「作者」）所有，未經作者授權不得轉載、摘編或利用其它方式使用本文內容。已獲得作者本人授權使用作品的，應在授權範圍內使用，並註明「來源：微信公眾號 跨行業俱樂部」。違反上述聲明者，作者將追究其相關法律責任。
TAG:跨行業俱樂部 |