本文介绍: 牛顿迭代法(Newtons method)又称为牛顿-拉夫逊(拉弗森)方法(Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程方法。牛顿迭代法实质是一种求根算法,这意味着它的目标是找到函数 f(x)=0 的值 x。在几何可以将其视为 x 的值,这时函数x相交

Newtons iteration method 是在实数域和复数域利用切线不断逼近方程根的一种求高次曲线方程方法区别梯度下降法,它是二阶导,收敛速度比较快,对于非凸函数,牛顿法容易受到鞍点或者最大值点的吸引。由于牛顿迭代法局部收敛,初始值选取不当的话,很容易无法收敛。

目录

1 基本介绍

2 公式推导

3 牛顿迭代法的应用

3.1 求倒数

3.2 开根号

 3.2 马克尔的方法

4 收敛性分析


1 基本介绍

        牛顿迭代法(Newtons method)又称为牛顿-拉夫逊(拉弗森)方法(Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程方法

牛顿迭代法实质是一种求根算法,这意味着它的目标是找到函数 f(x)=0 的值 x。在几何可以将其视为 x 的值,这时函数x相交

2 公式推导

 对于 f(x) = 0求解此时方程的根x0,任取xk近似作为方程的根,利用切线逼近法,可知对于在点(x^k,f(x^k))做切线与x轴的交点的横坐标x^{k+1}一定xk更加逼近x^0

由此可以得到  f'(x^k) = f(x^k)/(x^k-x^{k+1})

化简后得到此时的近似值  x^{k+1} = x^k - f(x^k)/f'(x^k),这就是牛顿迭代法公式

3 牛顿迭代法应用

3.1 求倒数

        有些芯片设计的对于求倒数的方法就是使用的牛顿迭代法,对于求解a的倒数y,有公式y = 1/a,对于牛顿迭代法设置初值,那么a就是已知数,y自变量,由此得到f(y) = 1/y - a,求解f(y) = 0的根,带入到牛顿迭代公式中得到x^{k+1} = x^k * (2 - a * x^k) ,这就是求导数的牛顿迭代公式,在ARM Neon中有专门的Intrinsic 指令 float32×4_t  x^{k+1} = vmulq_f32(vrecpsq_f32(a, x^k), x^k)来并行求倒数;由于计算机中的直接求倒数一般精度不够或者运行效率比较低,因此可以使用牛顿迭代法来求,在卷积计算中,经常会遇到除法运算,实质上就是求倒数。

3.2 开根号

        对于开根号某些芯片也是利用牛顿迭代法,对a开根号得到y,有公式$ y = sqrt a $,对于牛顿迭代设置初值,那么a就是已知数,y自变量,由此得到f(y) = y^2 - a,求解f(y) = 0的根,带入到牛顿迭代公式中得到$ x^{k+1}= x^k/2 + a / (2 * x^k) $ ,这就是牛顿迭代法开根号的公式

3.1 直接的实现

        一般会要求算出的精度,满足精度的情况下就停止运算代码如下

double sqrt(double x) { 
	if(x == 0) return 0; 
	double result = x; 
	double lastValue = 0;
	while(fabs(result - lastValue) > EPS) 
	{ 
		lastValue = result; 
		result = result / 2.0f + x / 2.0f / result; 
	}
 	return (double)result;
 }

 3.2 马克尔的方法

        据说非常高效,比3.1的代码快几十倍,比C++标准函数sqrt快几倍

int sqrt(float x) { 
	if(x == 0) return 0; 
	float result = x; 
	float xhalf = 0.5f*result; 
	int i = *(int*)&result; 
	i = 0x5f375a86- (i>>1); // what the fuck? 
	result = *(float*)&i; 
	result = result*(1.5f-xhalf*result*result); // Newton step, repeating increases accuracy 
	result = result*(1.5f-xhalf*result*result); 
	return 1.0f/result; 
}

4 收敛性分析

        参考牛顿法及其收敛性分析

原文地址:https://blog.csdn.net/m0_47324800/article/details/134734520

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_23332.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注