牛顿法对某些多项式发散

Question

我已经尝试对多项式实施牛顿法。喜欢：

double xn=x0;
double gxn=g(w, n, xn);

int i=0;
while(abs(gxn)>e && i<100){
    xn=xn-(gxn/dg(w, n, xn));
    gxn=g(w, n, xn);

    i++;
}

其中 g(w, n, xn) 计算函数值，dg(w, n, xn) 计算导数。

As x0 我使用起点 M，这是我使用 Sturm 定理找到的。

我的问题是这种方法对于某些多项式是发散的，例如 x^4+2x^3+2x^2+2x+1。也许它不规则，但我注意到当方程的解为负数时会发生这种情况。我在哪里可以找到解释？

编辑： dg

double result=0;
for(int i=0; i<n+1; i++)
    result+=w[i]*(n-i)*pow(x, n-i-1);

其中 n 是多项式的次数

Answer 1

我不知道你为什么会说它有分歧。

我实现了与你类似的牛顿法：

double g(int w[], int n, double x) {
    double result = 0;
    for (int i = 0; i < n + 1; i++)
        result += w[i] * pow(x, n - i);
    return result;
}

double dg_dx(int w[], int n, double x) {
    double result = 0;
    for (int i = 0; i < n ; i++)
        result += w[i] * (n - i) * pow(x, n - i - 1);
    return result;
}

int main() {

    double xn = 0;        // Choose initial value. I chose 0.
    double gx;
    double dg_dx_x;
    int w[] = { 1, 2, 2, 2, 1 };
    int i = 0;
    int n = 4;

    do {
        gx = g(w, n, xn);
        dg_dx_x = dg_dx(w, n, xn);
        xn = xn - (gx / dg_dx_x);
        i++;
    } while (abs(gx) > 10e-5 && i < 100);

    std::cout << xn << '\n';
}

并且它产生 -0.997576，接近解 -1。

牛顿法对某些多项式发散

Newton's method is divergent for some polynomials

c++

polynomial-math

newtons-method

convergence