圖解牛頓的方法

如果起初沒有成功，請嘗試重試

牛頓和拉夫森

我們將在此博客中介紹的方法也稱為Newton-Raphson方法。 從名字上，您可能會想象牛頓和拉弗森作為一個團隊一起工作，像夥伴一樣提出這個想法。 但實際上，他們是獨立發現它的。 這似乎是牛頓的共同主題。 還記得他是如何與萊布尼茨一起發現微積分的嗎？ 這個傢伙為什麼在別人也有確切時間的時候有這麼多想法？ 實際上，這很有可能，因為對於一個領域中研究前沿的多個人來說，下一步通常不會太含糊。

這是多個獨立團隊發現Intel芯片（Spectree和Meltdown）中的安全漏洞的原因。

但是，無論如何，有足夠的歷史，讓我們瞭解一下它是如何工作的。

什麼是x？

代數（從阿拉伯語，Al-Jabr衍生而來的部分）的本質是求解未知量的方程。 例如，在以下位置找到x：

2x + 5 = 7 __（1）

可以很容易地看出，上述方程的解為x = 1。 另一種看待這種情況的方法是將所有內容放到一邊，並調用表達式y。 我們得到：y = 2x-2。 然後，我們可以看到嘗試找到y = 0的x。

但是，當以x表示y的表達式變得越來越複雜時，會發生什麼呢？ 我們能否找到滿足y = 0的x的全部（或至少之一）？ 例如，下面的圖1顯示了y與x可能具有的一些更復雜的關係。 在所有情況下，x = 1時都滿足y = 0（儘管可能不是唯一的）。

> Figure 1: Different functions that all have zeros at x=1.

如果線性函數最簡單，那麼排名第二的可能是二次方（涉及x²）。 現在，如果我們有一個二次方程，我們將如何求解呢？ 好吧，我們可以簡單地使用二次公式（當只有一個變量x時）。 但是讓我們再假設一下，我們不知道這個公式。 我們只知道如何求解方程式（1）這樣的線性系統。 我們是否可以使用求解線性方程的知識來求解非線性（在這種情況下為二次方程）？

y =x²__（2）

好吧，我們可以，但前提是我們要堅持不懈。 讓我們從任意隨機點x開始。 現在，在此x處計算二次函數的值，並將其稱為y。 我們的工具是線性方程求解器，但我們有一個二次方程。 因此，讓我們將二次方程式轉換為線性方程式。 為此，只需使用線性方程式（使用泰勒級數）近似二次方程式即可。 當我們求解該線性方程時，我們將得到x的"答案"。 但是我們不能指望這個答案是"正確的"，因為我們"作弊"了-解決了線性方程，而不是二次方程。 由於精神錯亂的定義是在做同樣的事情並且期望得到不同的結果，因此我們不斷重複此過程。 唯一的區別是這一次我們使用線性方程式的先前解作為起點。 最終，這個過程將我們引到二次方程的解，如下所示。

> Figure 2: Newton Raphson iterations for a parabola taking us closer and closer to one of the points where the parabola intersects the x-axis.

擴大尺寸

現在，您可能已經看到了與之前的可視化非常相似的內容。 但是，這如何擴展到多個維度？ 例如，假設我們現在有兩個變量x和y，而不是一個變量x。 將方程式（2）擴展到二維的最自然的方法是：

z =x²+y²__（3）

其圖如下所示：

> Figure 3: A paraboloid, a kind of quadratic equation in multiple dimensions. Here, x and y are the dimensions and the z-axis represents the functional form of the paraboloid.

像以前一樣，我們要求解z = 0。 這發生在上圖中的綠色圓圈處，這是我們的拋物面方程與x-y平面相交的地方。 但是綠色圓圈是無數個點，而不是一，二或三。 這很自然，因為我們將變量的數量增加到兩個，但方程式的數量保持不變。 為了獲得有限數量的解，我們需要將相同數量的方程作為變量，即兩個。

我們可以為第二個方程式選擇很多候選人。 為簡單起見，讓我們複製現有的方程式並對其進行少量移動。 就像這樣，我們現在有兩個方程式。

> Figure 3: We want to demonstrate solving multiple equations. To keep things simple, we just take the existing equation of our paraboloid and replicate it to form the second one.

同樣，第二個方程也與x-y平面相交成一個圓，兩個圓在兩個不同的點相交，這是方程組的解。 這是下圖中的兩個黃點。

> Figure 4: The two paraboloids representing our two quadratic equations intersecting at two points.

現在，我們如何使用以前的方法來獲得這些解決方案之一？

我們將從x-y平面上的任意隨機點開始（如下圖5所示的粉紅色點）。 這可以投影到綠色拋物面上的綠點（這是我們的第一個二次方程），而可以投影到黃色拋物面上的黃點（我們的第二個二次方程）。 然後，我們可以在綠色和黃色點繪製綠色和黃色拋物面的最佳線性近似。 由於線性方程是平面，因此給了我們綠色和黃色的平面。 這些平面將在紫色線上相交，並進一步在某個點與x-y平面相交。 這一點是兩個線性方程組（兩個拋物線的近似）的解。

> Figure 5: NR iterations - we repeatedly solve the system of linear equations obtained by approximating the two quadratic equations. This leads us closer and close to one of the real solutions of the original quadratic system.

當然，這不是二次方程組的解，因為我們"欺騙"並用線性方程近似。 但是，然後我們從這個新點開始重複整個過程。 並且一次又一次地將我們帶到兩個二次方程的解（兩個黃點）之一。

如果我們想要第二種解決方案怎麼辦？ 好吧，然後我們從一個不同的隨機起點開始，然後重複該過程，直到找到從未見過的解決方案。

注意：您會在優化的背景下看到Newton Raphson，而在這裡，我們將其描述為一種求解方程式的方法。 但是，當我們注意到優化通常涉及找到梯度（導數向量）並將其設置為零時，它確實會減少求解方程組的問題。

查看此博客的視頻版本：

(本文翻譯自Rohit Pandey的文章《Newton's method: the visual intuition.》，參考：https://towardsdatascience.com/newtons-method-the-visual-intuition-12a346f4d89)