牛顿迭代法求平方根

《牛顿迭代法求平方根》由会员分享，可在线阅读，更多相关《牛顿迭代法求平方根（4页珍藏版）》请在金锄头文库上搜索。

1、牛顿迭代法求平方根牛顿迭代法求平方根求求 n n 的平方根，先假设一猜测值的平方根，先假设一猜测值X0 = 1，然后根据以下公式求出，然后根据以下公式求出X1，再将，再将X1代代 入公式右边，继续求出入公式右边，继续求出X2通过有效次迭代后即可求出通过有效次迭代后即可求出 n n 的平方根，的平方根，Xk+1( (迭代公式迭代公式) )简单推导简单推导假设f(x)是关于X的函数:求出f(x)的一阶导，即斜率:简化等式得到:然后利用得到的最终式进行迭代运算直至求到一个比较精确的满意值，为什么可以 用迭代法呢?理由是中值定理(Intermediate Value Theorem):如果f函数在闭区

2、间a,b内连续，必存在一点x使得f(x) = c，c是函数f在闭区 间a,b内的一点 我们先猜测一X初始值，例如 1，当然地球人都知道除了 1 本身之外任何数的平方 根都不会是 1。然后代入初始值，通过迭代运算不断推进，逐步靠近精确值，直到得到我们主观认为比较满意的值为止。例如要求 768 的平方根，因为252 = 625， 而302 = 900，我们可先代入一猜测值 26，然后迭代运算，得到较精确值: 27.7128。回到我们最开始的那个”莫名其妙”的公式，我们要求的是N的平方根，令x2 = n，假设一关于X的函数f(x)为:f(X) = X2 - n求f(X)的一阶导为:f(X) = 2X

3、代入前面求到的最终式中:Xk+1 = Xk - (Xk2 - n)/2Xk化简即得到我们最初提到的那个求平方根的神奇公式了:用泰勒公式推导用泰勒公式推导我之前介绍过在The Art and Science of C一书中有用到泰勒公式求平方根的算法，其 实牛顿迭代法也可以看作是泰勒公式(Taylor Series)的简化，先回顾下泰勒公式:仅保留等式右边前两项:令f(X0+) = 0，得到:再令X1 = X0 + 0，得到1依此类推可知:转化为:引申引申从推导来看，其实牛顿迭代法不仅可以用来求平方根，还可以求立方根，甚至更复 杂的运算。同样，我们还可以利用 pascal 语言来实现下那个最简单

4、的求平方根的公式(尽管我 们可以直接用sqrt()完成)program asd (input,output); var a,x,n,i:real; begin writeln(Please input a!); read(a); x:=1; n:=1000; i:=1; while i=n do begin x:=(x+(a/x)/2; i:=i+1; end; writeln(x:10:3); readln; end.2007 年赣州市信息学奥赛高中组上机测试题第 2 题：编程求平方根（15 分）任给常数 b，编程求 b 的算术平方根 ，要求准确到小数点后 3 位，注意不能调用高级语言 系统的开平方根函数。输入输出样例：输入：b=7输出：2.646确定迭代关系式: x:=(x+(b/x)/2;program asd (input,output); var a,x,n,i:real; begin writeln(Please input b!); read(b); x:=1; n:=1000; i:=1; while i=n do begin x:=(x+(b/x)/2; i:=i+1; end; writeln(x:10:3); readln; end.