求方程的近似解

问题描述：求一个方程的近似解，例如不用编程语言的库函数求一个数的方根。

分析：这是我曾经的一个企业面试题目，对于这种题目，大家可能会感到非常奇怪，因为编程语言本身都提供了库函数或者接口，直接调用就可以求方根。然而考官却不让用库函数和接口，那就意味着我们只能用其他方法了，考官其实想考察的是你的数学基础了，考察你会不会灵活应用所学的数学知识。对于这个问题，有很多解法，比如采用二分法等，但是采用二分法可能只能对平方根有效，对于立方根可能就没有办法了，甚至更高。而且采用这种方法的比较次数过多，时间复杂度会更高，相比较穷举肯定会好很多。这里我提供一种方法可以利用较少的次数，找到解，我的这种方法，需要大家学过高等数学，才会看懂。这个方法的名字叫做“牛顿迭代法”，听到牛顿，大家肯定会想到微积分吧！下面，下面正式开始介绍：

牛顿迭代法是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，就是使用迭代的方法来求解函数方程的根。简单地说，牛顿法就是不断求取切线的过程。

多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。方法使用函数f(x）的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收敛。该方法被广泛用于计算机编程中。

看到这里应该明白了吧。

我举一个具体的例子，并且编程实现：

题目：编写程序求一个整数的平方根，精确到小数点后三位。

Java代码如下，代码写法比较通用，读者可以很容易的转换为其他语言实现。

 1 import java.lang.Math;
 2 import java.util.Scanner;
 3 import java.text.*;
 4 public class sqr {
 5     public static double SQR(int n){
 6         double x1=1,x2;
 7         x2=x1/2.0+n/(2*x1);
 8         while(Math.abs(x2-x1)>1e-4){
 9             x1=x2;
10             x2=x1/2.0+n/(2*x1);
11         }
12         return x2;
13     }
14     public static void main(String[] args) {
15         // TODO 自动生成的方法存根
16        Scanner scan=new Scanner(System.in);
17        
18        DecimalFormat df=new DecimalFormat("#.000");
19        int n=scan.nextInt();
20        System.out.print(n+"的算术平方根是：");
21        System.out.println(df.format(SQR(n)));
22     }
23 
24 }

输出结果为：

3
3的算术平方根是：1.732

通过这个面试题目，引出了牛顿迭代法，因此一定要掌握牛顿迭代法，不仅可以解决方根问题，还可以求解近似方程问题，以及其他问题，该方法被广泛用于计算机编程中。