泰勒級數+牛頓迭代公式+最簡單的C語言求根號的值

無意間看見一哥們討論Tecent的兩道面試題，其中一道題目就是求根號2的值，並且保留指點的小數位。我想我一定是不能進Tecent了，並且我一定是一個數學小白，不，就是一個小白。查了一些資料。mark一下先...

泰勒級數

泰勒級數的冥級數如下所示：

取前面兩項等於0得：f(a) + f'(a)(x-a) = 0;

化簡後得：x = a - f(a)/f'(a);

其中a為自變量的取值，x為a的一個近視解，使用x0代替a，x1代替x，則上式可表示為：x1 = x0 - f(x0)/f'(x0);

牛頓迭代公式

牛頓迭代法結論其實就是取泰勒級數前兩項等於0求得的，為：x(n+1) = x(n) - f(x(n))/f'(x(n));

思路如下：

假設有一條曲線C，在曲線上面任選一點x0 = 1, 求的曲線的值為f(1), 即(1, f(1))為曲線上得一點。過點(1, f(1))， 作一條曲線C的切線，切線與X軸相交於點x1。同理使用x1求得x2、x3、x4......。所求得的一些列與X軸相交的點位曲線與X軸相交點得近視值。如設定某一誤差e，當x(n+1)-x(n) < e,則可認為x(n+1)是曲線的一個近視解。因為x(n+1)作為曲線的解誤差為可以接受的e。

其實，對於某個點，相對於曲線的切線方程是確定的，即為：f(x0) = f'(x0)(x - x0), 其中f'(x0)為切線的斜率。化簡即為x1 = x0 - f(x0)/f'(x0);和泰勒級數中求得的公式不謀而合。由此可得牛頓迭代公式為：x(n+1) = x(n) - f(x(n))/f'(x(n));

最簡單的C語言求根號2

采用上述方法求得了曲線的近視解，如要求根號2，可假設f(x) = x^2 - 2 = 0;即曲線x^2 -2 = 0的解即為根號2的值，通過控制誤差的大小，即可求得根號2的保留小數點位數的取值。如要取得小數點為8為的根號2的值，可取誤差e=0.00000001， 即誤差為10的負8次方。取根號2小數點保留10位的最簡單C代碼如下：

1. #include <stdio.h>
3. int main() {
5. int i = 0;
6. float x1 = 1, x2 = 0;
7. float diff = 0; //diff為兩次近視值之間的差，如果此差小於某一個誤差值，即結束迭代
9. do {
10. x2 = x1 - (x1*x1-2)/(2*x1); //如迭代公式所示，求x1的一個近視值x2
12. if (x2 > x1) //abs不適合求float數的絕對值，所以采用sb的判斷語句
13. diff = x2 - x1;
14. else
15. diff = x1 - x2; //可以看到，誤差的計算方式就是兩次迭代值之間的正差
17. if (diff < 0.0000000001) //小數點後位數控制誤差大小
18. break;
20. printf("%.10f, %.10f\n", x1, x2);
21. x1 = x2; //改變x1的值為前一次跌打x2的值，繼續迭代
22. } while (1);
24. return 0;
25. }

運行結果如下：

1. # ./a.out
2. 1.0000000000, 1.5000000000
3. 1.5000000000, 1.4166666269
4. 1.4166666269, 1.4142156839
5. 1.4142156839, 1.4142135382

btw，根號2的值也就是方程x^2 - 2 = 0的解。而以上輸出中第2列均為方程的解，只是精度不同而已。而精度的控制就靠diff和0.0000000001控制了。當然，代碼寫得很sb，並且條件全都寫死在代碼裡面，旨在用最簡單的代碼講清楚怎樣使用牛頓迭代法求根號的值。

另外，大家別噴我，上述代碼肯定不是最簡單的，只是想要表達比較簡潔，希望能夠更清楚的看出牛頓迭代法的使用。