文档章节

牛顿迭代求sqrt函数

smart_w
 smart_w
发布于 2016/01/26 12:06
字数 392
阅读 79
收藏 1

经验 : 求出根号a的近似值:首先随便猜一个近似值x,然后不断令x等于x和a/x的平均数,迭代个六七次后x的值就已经相当精确了。

例如,我想求根号2等于多少。假如我猜测的结果为4,虽然错的离谱,但你可以看到使用牛顿迭代法后这个值很快就趋近于根号2了:

(       4  + 2/4        ) / 2 = 2.25

(     2.25 + 2/2.25     ) / 2 = 1.56944..

( 1.56944..+ 2/1.56944..) / 2 = 1.42189..

( 1.42189..+ 2/1.42189..) / 2 = 1.41423..

…. 

其实上面原理:就是跳跃不断逼近,因为(x+a/x)/2正好接近f(x)=x^2 的 x^2-a=0的根

这种算法的原理很简单,我们仅仅是不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根,这个函数的导数是2x。也就是说,函数上任一点(x,f(x))处的切线斜率是2x。那么,x-f(x)/(2x)就是一个比x更接近的近似值。代入 f(x)=x^2-a得到x-(x^2-a)/(2x)合并展开等于(x+a/x)/2

然后不断逼近exp的方式求根号sqrt的值

具体代码如下:

package main

import (
	"fmt"
	"math"
)

const (
	eps = 0.000001
)

func SqrtByNewton(x float64) float64 {
	var val float64 = x
	var last float64
	var cal float64
	for {
		last = val
		val = (val + x/val) / 2
		cal = math.Abs(val - last)
		if cal < eps {
			break
		}
	}
	return val
}

func main() {
	fmt.Printf("result: %v \n", math.Sqrt(4.0))
	fmt.Printf("my result: %v \n", SqrtByNewton(4.0))
}

/*
输出结果:
result: 2 
my result: 2.000000000000002
*/



© 著作权归作者所有

共有 人打赏支持
上一篇: 求π的方法
下一篇: 探索与回溯算法
smart_w
粉丝 32
博文 74
码字总数 23007
作品 0
武汉
程序员
私信 提问
牛顿迭代法(Newton's Method)

牛顿迭代法(Newton's Method) 简介 牛顿迭代法(简称牛顿法)由英国著名的数学家牛顿爵士最早提出。但是,这一方法在牛顿生前并未公开发表。 牛顿法的作用是使用迭代的方法来求解函数方程的根...

angel_kitty
2017/03/11
0
0
【转帖】一个Sqrt函数引发的血案

源码下载地址:http://blog.redfox66.com/post/2010/10/06/sotry-about-sqrt.aspx 好吧,我承认我标题党了,不过既然你来了,就认真看下去吧,保证你有收获。 我们平时经常会有一些数据运算的...

戴威
2011/11/25
207
2
[LeetCode]牛顿迭代法求平方根

题目 Implement int sqrt(int x). Compute and return the square root of x. 思路 用Math.sqrt就没什么意义了 二分法估计也行,但是估计没有牛顿下山法快 牛顿下山法 公式推导: 在x0处的值...

Finley.Hamilton
2014/11/03
0
0
最优化问题综述

转载:http://blog.csdn.net/acelit/article/details/63685878 1 优化问题分类 优化问题一般可分为两大类:无约束优化问题和约束优化问题,约束优化问题又可分为含等式约束优化问题和含不等式...

weixin_37589896
2017/11/27
0
0
优化算法——牛顿法(Newton Method)

一、牛顿法概述 除了前面说的梯度下降法,牛顿法也是机器学习中用的比较多的一种优化算法。牛顿法的基本思想是利用迭代点处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近...

google19890102
2014/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

全屋WiFi彻底无死角 这才是终极解决方案

无线网络现在不仅在家庭中不可或缺,在酒店、医院、学校等场景中的需求也越来越多。尤其是这些场景中,房间多但也需要每个房间都能够完美覆盖WiFi,传统的吸顶式AP就无法很好的解决问题。 H3...

linux-tao
26分钟前
0
0
Python日期字符串比较

需要用python的脚本来快速检测一个文件内的二个时间日期字符串的大小,其实实现很简单,首先一些基础的日期格式化知识如下 复制代码 %a星期的简写。如 星期三为Web %A星期的全写。如 星期三为...

dragon_tech
26分钟前
0
0
ORA 各种oraclesql错误

ORA-00001: 违反唯一约束条件 (.) ORA-00017: 请求会话以设置跟踪事件 ORA-00018: 超出最大会话数 ORA-00019: 超出最大会话许可数 ORA-00020: 超出最大进程数 () ORA-00021: 会话附属于其它某...

青峰Jun19er
30分钟前
2
0
没错,老板让我写个 BUG!

前言 标题没有看错,真的是让我写个 bug! 刚接到这个需求时我内心没有丝毫波澜,甚至还有点激动。这可是我特长啊;终于可以光明正大的写 bug 了🙄。 先来看看具体是要干啥吧,其实主要就是...

crossoverJie
43分钟前
54
0
开源软件会被云杀死吗 ?

本文转载云头条,原作者:Michael Stiefel是Reliable Software公司的负责人,是一名软件架构和开发顾问。 文章要点 虽然开源开发不会消失,但商业开源厂商的未来不是很有希望。随着全面管理的...

linuxCool
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部