牛顿迭代法求平方根--C++简单实现

1. 简介

牛顿迭代法是求近似根的一种方法。

以求平方根为例。
如$x^2=m$
令$f(x)=x^2-m$
则$f^{\prime }(x)=2x$
函数$f(x)$在$x_0$处的切线方程为
$g(x)=f^{\prime }(x_0)(x-x_0)+f(x_0)$

令该切线与x轴交点为$(x_1,0)$
$x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}$

$x_1=x_0-\frac{x_0^2-m}{2x_0}$

重复上述迭代过程，直到$x_{n+1}-x_n$小于某一精度

2. 实现

迭代即可

• cpp

#include 
#include 
#include 

double my_sqrt(double x)
{
    double x0 = 1;
    double x1 = x0 - (x0 * x0 - x)/(2*x0);

    while ( std::abs(x0-x1) > 1e-6) {
        x0 = x1;
        x1 -= (x1*x1 - x) / (2*x1);
    }


    return x0;
}

int main(int argc, char *argv[])
{

     std::cout << my_sqrt(2) << std::endl;
     std::cout << my_sqrt(3) << std::endl;
     std::cout << my_sqrt(5) << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

• go

package main

import (
	"fmt"
	"math"
)

func New_ton(x ,z float64) float64{
 
 	return z - (z*z - x) / (2 * z)
}

func Sqrt(x float64) float64 {
	
	z := 1.0
	
	
	for z0:= New_ton(x, z); math.Abs(z-z0) > 1e-6; z0 = New_ton(x,z0) {
		z = z0
	}
	
	return z
}

func main() {
	fmt.Println(Sqrt(2))
	fmt.Println(Sqrt(3))
	fmt.Println(Sqrt(5))
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3. Ref

go_tutorial