文档章节

牛顿迭代求sqrt函数

smart_w
 smart_w
发布于 2016/01/26 12:06
字数 392
阅读 75
收藏 0
点赞 1
评论 0

经验 : 求出根号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
粉丝 30
博文 71
码字总数 19544
作品 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
《c程序设计》的算法归纳

文章由算法源码吧(www.sfcode.cn)收集 递归法转换整数为字符 void convert(int n) {int t; if((t=n/10)!=0) convert(t); putch(n%10+'0'); } 判断素数 int isPrime(int n) {int i; for(i=2;i......

文艺小青年
2017/07/06
0
0
优化算法——牛顿法(Newton Method)

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

google19890102
2014/11/13
0
0
常见的几种最优化方法(梯度下降法、牛顿法、拟牛顿法、共轭梯度法等)

梯度下降法 梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般情况下,其解不保证是全局最优解,梯度下降法的速...

luanpeng825485697
04/21
0
0
机器学习之牛顿法

泰勒公式 首先看泰勒公式,对于函数,如果函数平滑且某点存在各阶导数,则可以用一个多项式来描述该点邻域的近似值。公式如下: 牛顿法 牛顿法一般用来求解方程的根和求解极值。 数值优化算法...

超人汪小建
2017/11/16
0
0
为什么要学习函数式编程?因为如果你手里只有锤子,看什么都像钉子

摘要:函数式编程是一种“编程范式”,也就是如何编写程序的方法论,其主要思想是把运算过程尽量写成一系列嵌套的函数调用。那么在函数式编程比较火爆的今天,我们为什么要学习它呢?学习函数...

萌萌怪兽
04/20
0
0
牛顿法 Newton Method

今天我们要介绍一种收敛速度更快的算法:Newton Method(或者叫 Newton’s Method)。 可能大家知道有两个算法同时叫做牛顿法,一个是用迭代法来求方程的根的方法,另一个是 optimization 里...

GarfieldEr007
2016/01/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

数据结构与算法2

一个数组的例子,实现查找,显示和删除的功能。 public class array {public static void main(String[] args){long[] arr;arr = new long[100];int nElems = 0;int j;...

沉迷于编程的小菜菜
10分钟前
0
0
Python3 基于 requests 批量下载图片

Python3 基于 requests 批量下载图片 import requestsheaders = {'Accept': 'text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8','Accept-Encod......

leeyi
11分钟前
0
0
Sparkstreaming and Kafka

简介 Kafka 0.10的Spark Streaming集成设计与0.8 Direct Stream方法类似。 它提供了简单的并行性,Kafka分区和Spark分区之间的1:1对应关系,以及对偏移量和元数据的访问。 但是,由于较新的...

刺猬一号
15分钟前
0
0
java获取当前时间所在一周的周一和周日日期

/** * 当前时间所在一周的周一和周日时间 * @param time 当前时间 * @return */ public static Map getWeekDate(String time) { Map map = new HashedMap(); SimpleDateFormat sdf = new Si......

小弱鸡
43分钟前
0
0
Redis数据的导出和导入(dump和load方式)

网上有些文章已经不再适用,本人也是踩了些坑,在此记录下。 迁移redis数据一般有如下3种方式: 第三方工具redis-dump,redis-load aof机制,需要开启aof功能 rdb存储机制 这里介绍第一种方式...

iplusx
47分钟前
1
0
ElasticSearch 高亮显示大文档搜索结果

2016年12月,我们开始研究Ambar——一个文档搜索系统。Ambar使用ElasticSearch作为核心搜索引擎。 在Ambar开发的过程中,我们处理了很多与ES相关的问题,我们想分享我们得到的宝贵经验。让我...

九州暮云
今天
1
0
Python 使用 pywifi 模块 破解wifi密码

git https://github.com/awkman/pywifi 常见常量 from pywifi import const# Define interface status.IFACE_DISCONNECTED = 0IFACE_SCANNING = 1IFACE_INACTIVE = 2IFACE_CONNEC......

阿豪boy
今天
1
0
phpstorm使用Iedis

phpstorm的redis插件Iedis是真好用 看了网上挺多的文章,但是由于我系统还是ubuntu,就有点尴尬了,现在破解之后,留个笔记,即使自己之后有需要也可以很快翻阅 先下载资源 资源下载 zip压缩...

贤郎--均灵
今天
0
0
第三章 spring-bean之FactoryBeanRegistrySupport(4)

前言 从FactoryBeanRegistrySupport类的名字可以看出FactoryBeanRegistrySupport负责FactoryBean的注册与支持。如果想知道FactoryBean相关的资料,请阅读spring-bean中关于FactoryBean的解读...

鸟菜啊
今天
0
0
CentOS “Destination Host Unreachable”问题解决办法

挑战极速安装CentOS时遇到局域网主机不能通信的情况: [root@zjd network-scripts]# ping 8.8.8.8PING 8.8.8.8 (8.8.8.8) 56(84) bytes of data.64 bytes from 8.8.8.8: icmp_seq=1 ttl=......

wffger
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部