2.4.1　利用牛頓迭代法求平方根

雖然Java自帶了數學函數庫Math，但是該庫僅支持開方運算中的開平方，并不支持開N次方的運算，連計算三次方根也無能為力。比如求解27的三次方根，中學生都知道27的三次方根為3，但求三次方根的Java代碼該怎么寫呢？換句話說，Math庫的開平方函數sqrt是怎樣實現的呢？開三次方與開二次方，乃至開N次方，本質上解法是一樣的，只要掌握了具體的解題思路，開多少次方均可觸類旁通。現在問題在于，Java的基礎運算只有加減乘除四則運算，如何才能利用四則運算實現開N次方根的功能呢？

在計算器發明之前，普通人要計算一個數的N次方根，可以先猜個約數，求得該約數的N次方，再與這個數比較，結果比這個數大則約數改小，結果比這個數小則約數改大。如此重復多次，直到約數的N次方足夠接近這個數，那么該約數即可近似為這個數的N次方根。然而落實到編碼上就不容易了，一方面約數怎么猜，另一方面約數改小要改多小，約數改大又要改多大，這些都是很模糊的說法，沒法寫到代碼里面。因為人類動腦子的同時用到了經驗，猜多猜少依據的是后天獲得的經驗，但一段簡單的計算機程序猶如學齡前幼兒，什么經驗都沒有，連瞎猜也不會，必須告訴它準確無誤的做法才行。也就是說，每行程序代碼都得由明確的數字與符號組成，就像求解方程式那樣，嚴格按照式子開展運算，這樣才能求得精確的數值。

僅僅依靠加減乘除就想計算N次方根，這不是天方夜譚，而是一種巧妙的數學解法，叫作“牛頓迭代法”。顧名思義，該解法是牛頓發現的，正如蘋果砸到牛頓頭上促使他發現了萬有引力定律一樣，牛頓對著N次方程式的函數曲線冥思苦想發現了牛頓迭代法。假定某個數字為a，它的N次方根為x，則方程式可寫作a=xⁿ。把a挪到等號右邊，此時方程式變為0=x²－a，對應的函數式為f(x)=xⁿ－a，其中f(x)=0的時候可求得方根x的數值。

簡單起見，假設n=2、a=2，則函數式f(x)=xⁿ－a可簡化為f(x)=x²－2，該式子對應一條二次函數曲線，具體如圖2-1所示。

圖2-1　f(x)=x²－2的函數曲線

從圖2-1可見，該曲線經過坐標點(0,-2)，并且它與x軸有兩個交點，其中右邊的交點落在(1,0)與(2,0)之間，這里將該交點記作x₀，顯然x₀的橫坐標數值即為原函數式的解。為了求得x₀的橫坐標，牛頓想了一個辦法，他先在x軸上挑一個坐標點(3.5,0)，并將該點記作x₁。接著在x₁畫一條垂線與曲線f(x)交匯，并在交點處描繪函數曲線的切線，切線與x軸相交于坐標點x₂。繼續在x₂畫一條垂線與曲線f(x)交匯，仍在交點處描繪函數曲線的切線，新切線與x軸相交于坐標點x₃。此時添加了垂線和切線的坐標系空間，如圖2-2所示。

圖2-2　對函數曲線交替做垂線與切線的示意圖

觀察這幾個點的位置，可知x₁到x₂再到x₃，其值逐漸逼近x₀，倘若在x₃位置重復畫垂線、描繪切線的操作，新求得的x_m必然越來越趨向于x₀，如此便能計算出方根的近似值。

在坐標系上畫垂線很容易，但描繪曲線某點的切線就不簡單了，因為你不知道該切線的斜率是多少。從幾何角度看，切線與曲線只有一個交點，且在交點處二者近乎重合。物理學上有一個自由落體運動公式，其中g表示重力加速度（值為9.8m/s²），t為下落時間，S為下落高度，這個自由落體曲線與前面講的二次函數曲線相似，此時切線的斜率等價于物體在該時間點的瞬時速度V=gt。在代數學體系中，函數式f(x)對應的斜率式子為f'(x)，它被稱作原函數式的導數，意思是引導方向的函數。就式子f(x)=xⁿ-a而言，它的導數為f'(x)=nx^n-1，倘若已知x的具體值，則f'(x)求得的導數即為該點切線的斜率。

假設從坐標點x_m開始做曲線方程f(x)=x_n－a的垂線，并在垂線與曲線的交點處做切線，且該切線與x軸相交于x_m + 1點，則包含曲線、垂線、切線在內的坐標系如圖2-3所示。

圖2-3　函數曲線在x_m處的垂線與切線

此時可求得垂線與曲線的交點坐標為，根據斜率公式可得，分別代入，方程式變為，一番計算后求得，該結果正是點的橫坐標值。由求得的數值之后，還可如法炮制求得、等各點的數值，并且、越來越接近點，如此反復迭代多次，的數值將非常逼近方根的真實值。以上求解的整個過程便構成了牛頓迭代法，通過多次迭代運算，從而求得N次方程式的方根近似值。

當然，上述的迭代式無疑太復雜了，因為該式子為N次方程的迭代式。對于二次方程式來說，可將n=2代入，于是迭代式可逐步簡化，，最終得到的便是求平方根所需的迭代式。

接下來，利用求平方根的迭代式計算數字2的平方根，且令變量Xm從數字自身開始迭代3次，據此編寫的示例代碼如下（完整代碼見本章源碼的src\com\arithmetic\Pingfanggen.java）：

        double number=2;                  // 需要求平方根的數值
        double Xm=number;                  // 每次迭代后的數值
        Xm=(Xm + number/Xm) / 2;          // 第一次迭代后的平方根
        System.out.println(number+"的平方根="+Xm);
        Xm=(Xm + number/Xm) / 2;          // 第二次迭代后的平方根
        System.out.println(number+"的平方根="+Xm);
        Xm=(Xm + number/Xm) / 2;          // 第三次迭代后的平方根
        System.out.println(number+"的平方根="+Xm);

運行上面的求方根代碼，打印出來的日志如下：

2.0的平方根=1.5
2.0的平方根=1.4166666666666665
2.0的平方根=1.4142156862745097

由日志可見，僅需3次迭代，求得的平方根數值1.414就精確到了小數點后面3位。

把代碼里的number取值改成3，準備求數字3的平方根，重新運行修改后的求方根代碼，打印出來的日志如下：

3.0的平方根=2.0
3.0的平方根=1.75
3.0的平方根=1.7321428571428572

可見3次迭代之后，計算出來的1.732依然精確到了小數點后面3位，說明通過牛頓迭代法求方根的效率很高。同理，可由式子推出3次方根、4次方根的迭代計算代碼，有興趣的讀者不妨動手實踐。