美文网首页
牛顿迭代法求根C++

牛顿迭代法求根C++

作者: 小pb | 来源:发表于2019-12-26 13:48 被阅读0次

题目描述:

计算一个数字的立方根,不使用库函数

首先最常见的方法是二分法进行求值,这里主要注意精度,还有就是二分法的求值,但是这种方法有时候不满足题目给的时间复杂度的要求,那么需要一种新的方法来进行求值。
所以这里给出牛顿迭代法:

牛顿迭代法

这里应该大学都知道,一个函数f(x) = x^3-y 的可以在坐标系上画出它的图。


牛顿迭代法.png

随便找一个曲线上的A点(为什么随便找,根据切线是切点附近的曲线的近似,应该在根点附近找,但是很显然我们现在还不知道根点在哪里),做一个切线,切线的根(就是和x轴的交点)与曲线的根,还有一定的距离。牛顿、拉弗森们想,没关系,我们从这个切线的根出发,做一根垂线,和曲线相交于B点,继续重复刚才的工作:

牛顿迭代法2.png

之前说过,B点比之前A点更接近曲线的根点,牛顿、拉弗森们很兴奋,继续重复刚才的工作:
经过多次迭代后会越来越接近曲线的根(下图进行了50次迭代,哪怕经过无数次迭代也只会更接近曲线的根,用数学术语来说就是,迭代收敛了):

众所周知,f'(x) 是f(x)的导数,也是在某点上的一个切线方程。
牛顿它们根据上面的方法,不断的逼近根的方法,可以总结为以下的表示方法。

Xn+1 = Xn - f(Xn)/ f'(Xn)

从而对于求立方根的时候,我们可以假设

f(x) = X^3 - y

求y的立方根表示, f(x)=0的时候,求x的值这样的数学模型。
根据上面的公式,我们可以得到

Xn+1 =  Xn- (Xn^3 -y)/(3*Xn^2) = (2*Xn +y/(Xn*Xn))/3

根绝这里的公式,我们就可以写出立方根的解法了。

#include <iostream>
using namespace std;

// 牛顿迭代法
// f(x) = X^3 - y, 当f(x) =0时,求x
// 根据牛顿迭代法。Xn+1 = Xn - f(Xn)/ f'(Xn)
// 所以 xn+1 =  x- (X^3 -y)/(3X^2) = X*2/3 + y/(*X^2) * 1/3
// Xn+1 = (X)/3
inline double abs(double x){return (x>0?x:-x);}
double getcudeRoot(double y) {
   double x =1.0;
   for (x = 1.0; abs(x*x*x -y) > 1e-6; x=(2*x+y/x/x)/3);
   return x;
}


int main() {
    double input;
    while (cin >> input) {
        printf("%.1f\n", getcudeRoot(input));
    }
    return 0;
}

参考:
牛顿迭代法

相关文章

  • 牛顿迭代法求根C++

    题目描述: 首先最常见的方法是二分法进行求值,这里主要注意精度,还有就是二分法的求值,但是这种方法有时候不满足题目...

  • 1.3求根之牛顿迭代法

    目录 [TOC] 前言 今天我们讲的是具有收敛速度快,能求重根的解方程之法,牛顿迭代法。 (一)牛顿迭代法的分析 ...

  • 【实验一】方程求根:牛顿迭代法

    如果有时间,我会渐渐的把数值分析的实验写完。总共8个实验,今天写的是方程求根里的通过牛顿迭代法求一元多次方程的根。...

  • c++牛顿迭代法

    首先牛顿迭代法可以理解为,X=X0-f/f', X0=X依次往下推,即可求出范围内的根; 本示例先创建一个方法,初...

  • 2.牛顿迭代二阶梯度法求多元非线性函数的极小值,以及Hessia

    牛顿迭代求最小值有点区别于求牛顿迭代求根先复习一下 牛顿迭代求根 是如下表达式 因为是求根,那么函数和轴相交的地方...

  • 每日一问之初识牛顿迭代法(Newton's method)

    什么是牛顿迭代法? 今天在刷 LeetCode 的 sqrt(x) 这道题的时候,看到别人的解法中有使用牛顿迭代法...

  • 记--平方根的算法

    Java实现牛顿迭代法: C/C++实现3d游戏引擎算法实现1/sqrt(x),改一下返回值成为sqrt()算法:...

  • 牛顿法开根

    牛顿迭代法(Newton's method)又称为牛顿-拉夫逊方法(Newton-Raphson method)。...

  • 无约束凸优化算法

    本章涉及知识点1、scipy库求解全局最优和局最优2、多元函数的极值求解算法3、牛顿迭代法算法4、牛顿迭代法求解多...

  • 吹水牛顿迭代法

    因为吹水的能力不佳,所以要先打个草稿,今天的吹水过程大概是:1、牛顿迭代法的演绎过程2、牛顿迭代法求n次方根3、牛...

网友评论

      本文标题:牛顿迭代法求根C++

      本文链接:https://www.haomeiwen.com/subject/tzikoctx.html