求解a的N次方根

求解a的N次方根

牛顿迭代法

一阶泰勒展式:\(f(x) = f(x_0)+f^{'}(x_0)*(x-x_0)\)

假设\(f(x)=x^N-a=0\),N=2时,\(f(x)=x^2-a \quad f^{'}(x)=2x\)

通过等式\(f(x)=x_0^2-a+2x_0(x-x_0)=0\)

得到\(x=\frac12(x_0+\frac{a}{x_0})\)

通过迭代可以逼近算出真实值。

对应任意的N,计算公式为
\(x_{n+1} = \frac1N((N-1)x_n+\frac{a}{x_n^{N-1}})\)

分析:

Newton迭代法求单根时,收敛速度很快(平方收敛)。

但如果方程根是重根,则收敛速度较慢,且重数越高速度越慢

代码:

#include <cmath>#include <iostream>#include <iomanip>using namespace std;double Newton(double x, int N, double delta) {    if (x <= 0 || N <= 0) {        return 0;    }    double x0 = 1;    double x1 = ((N - 1) + x) / N;;    while (abs(x1 - x0) > delta) {        x0 = x1;        x1 = ((N - 1) * x0 + x / pow(x0, N - 1)) / N;    }    return x1;}const double DELTA = 0.0000001;int main() {    cout << setprecision(20) << Newton(2, 2, DELTA) << endl;    cout << setprecision(20) << Newton(8, 1, DELTA) << endl;    cout << setprecision(20) << Newton(8, 2, DELTA) << endl;    cout << setprecision(20) << Newton(8, 3, DELTA) << endl;    cout << setprecision(20) << Newton(8, 4, DELTA) << endl;    return 0;}

推荐阅读