题目描述
给定一个浮点数n,求它的三次方根。
相当于求方程 f(x) = x^3 - n = 0 的解
算法
一般牛顿迭代法
迭代函数:
φ(x) = x - f(x) / f’(x)
由迭代函数可以看出,牛顿法适用于求解某些非线性方程。
一般牛顿法,在根的附近局部平方收敛。
(书中介绍到,由于牛顿法是局部收敛,因此牛顿法对初值要求比较严格,初值只有在根的附近才能保证收敛。实际上,常用二分法或逐步搜索法选取好的初值)
(书中后文有介绍“引入下山因子的牛顿下山法”和其他改进后的牛顿法)
因其对初值有一定要求,因此适当选取初值,会对收敛性和收敛速度产生积极影响。
(书中证明了:求平方根时,一般牛顿迭代法对于任意初值 x > 0 都是收敛的)
本次初值采用 n (亦可 n/2 ,或任意实数)
(初值越接近根越好)
时间复杂度
本人能力有限,见谅 :)欢迎各位大佬补充!
参考文献
数值分析 / 王金铭主编.—2版.—大连:大连理工大学出版社,2010.8(2012.1重印)
高等学校理工科数学类规划教材
ISBN 978-7-5611-3753-6
C++ 代码
#include <iostream>
#include <cmath>
using namespace std;
const double delta = 1e-8;
double f(double x, double n) //x为初值
{
x = x - (x*x*x - n) / (3*x*x);
if (fabs(n - x*x*x) < delta)
return x;
return f(x, n);
}
int main()
{
double n;
scanf("%lf", &n);
printf("%.6lf\n", f(n, n));
return 0;
}
按牛顿迭代法,应该可以求任意x开n次方根(不知道在面对比较大的数据时有无弊端,请大佬指正:)
例:开数x的4次方根
牛顿迭代法,主要用于求解一元多次方程的零解,所以把 开n次方根问题 转化成 一个求零解的问题 就ok了。
在数据取值较大时,不会有明显弊端,但在次方数n变大后,可能出现求解速度缓慢,甚至无法求解的情况(收敛速度和收敛性),也可能极度依赖初值,比如:迭代初值为5,可以求解;但迭代初值为500,则无法求解。
据我所学到的知识来说,用牛顿迭代法 开平方 时,此方法 绝对收敛 且 完全不依赖初值。(前文中有所描述,感兴趣可搜索 其他改进后的牛顿法)
想到一块去了