文档章节

牛顿迭代求sqrt函数

smart_w
 smart_w
发布于 2016/01/26 12:06
字数 392
阅读 75
收藏 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
粉丝 31
博文 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
199
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

没有更多内容

加载失败,请刷新页面

加载更多

TypeScript基础入门之高级类型的索引类型(Index types)

转发 TypeScript基础入门之高级类型的索引类型(Index types) 高级类型 索引类型(Index types) 使用索引类型,编译器就能够检查使用了动态属性名的代码。 例如,一个常见的JavaScript模式是从...

durban
9分钟前
0
0
利用碎片化时间Get Linux系统

起初,我做着一份与IT毫无关系的工作,每月领着可怜的工资,一直想改变现状,但无从下手,也就是大家熟知的迷茫。我相信,每一个人都会或多或少的经历过迷茫,迷茫每一个选择,迷茫工作或者生...

Linux就该这么学
44分钟前
0
0
图像显示深入学习一:Activity启动过程

一个月左右写了图像显示深入学习之文章开篇文章表明了自己近期的计划,前半年重新学习了opengl es,c++以及Linux的一些知识,觉得是时候开始看图像这一块的源码了,边看边补缺补漏吧。 作为该...

JerryLin123
今天
2
0
给MySQL授权远程访问

putty登录服务器; 登录MySQL: mysql -u root -p 新建远程用户: CREATE USER 'myusername' IDENTIFIED BY 'mypassword'; 授权: grant all on *.* to john@'101.102.103.104' identified by......

sweethome
今天
2
0
在t-io老巢造谣,不过有造谣的就会有反造谣的!

只发当事人的截图,不发表评论,以免有引导嫌疑 PS: 截图是由不同的人发过来的 本人已经不在此微信群 图3:有造谣的,就有反造谣的 图4是2018-09-23的t-io官方群的一个发言小统计,有助于让...

talent-tan
今天
104
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部