华为OJ1964-求解立方根（牛顿迭代法）

发表于   |   分类于   |  

一、题目描述

描述：

  • 计算一个数字的立方根，不使用库函数。
  • 函数原型double getCubeRoot(double input)

输入：

待求解参数 double类型

输出：

输出参数的立方根，保留一位小数

样例输入：

1
216

样例输出：

1
6.0


二、解题报告

本题要求一个数的立方根的近似值，精确到小数点后的一位。这里使用 牛顿迭代法 求近似值。

牛顿迭代法，又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。方法使用函数$f(x)$的泰勒级数的前面几项来寻找方程$f(x) = 0$的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程$f(x) = 0$的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收敛。另外该方法广泛用于计算机编程中。

设 $r$ 是的根，选取 $x_0$ 作为 $r$ 的初始近似值：

  • 过点$(x_0,f(x_0))$做曲线$y=f(x)$的切线L，L的方程为 $y=f(x_0)+f’(x_0)(x-x_0)$，求出L与x轴交点的横坐标 $x_1 = x_0-\frac{f(x_0)}{f’(x_0)}$，称 $x_1$为 $r$ 的一次近似值。

  • 过点 $(x_1,f(x_1))$ 做曲线 $y=f(x)$ 的切线，并求该切线与x轴交点的横坐标 $x_2 = x_1-\frac{f(x_1)}{f’(x_1)}$，称 $x_2$ 为 $r$ 的二次近似值。

  • 重复以上过程，得 $r$ 的近似值序列。其中， $x_{n+1} = x_n-\frac{f(x_n)}{f’(x_n)}$ 称为 $r$ 的 $n+1$ 次近似值，上式称为牛顿迭代公式。

首先确定我们的函数 $f(x)$：

$$f(x) = x^3 - m$$

其中 $m$ 是一个常数，程序的输入。求导函数：

$$f’(x) = 3x^2$$

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <iomanip>
using namespace std;
#define E 0.01

double f(double x, double num) // 函数
{
	return x*x*x-num;
}

double _f(double x)  // 导函数
{
	return 3*x*x;
}

double getCubeRoot(double input)
{
	double x0;  
	double r = 1;
	do
	{
		x0 = r;
		r = x0 - f(x0,input)/_f(x0);
	} while(f(r,input) > E || f(r,input) < -E);
	
	return r;
}

int main()
{
	double x;
	cin >> x;
	double result = getCubeRoot(x); 
	cout << fixed << showpoint << setprecision(1) << result << endl;
	return 0;
}