java - 牛顿在Java中查找复杂根的方法

我在Java类中遇到了一个项目，但遇到了麻烦。
该项目基本上是在屏幕上标记坐标，从中创建一个（复杂的）多项式，然后使用牛顿方法使用随机猜测来求解多项式，并在屏幕上绘制猜测的路径。
我没有任何图纸，标记等问题。
但是由于某种原因，我的牛顿方法算法随机遗漏了根。有时它没有命中任何一个，有时却错过了一两个。我已经花了几个小时来更改内容，但是我真的无法提出解决方案。
当根丢失时，通常我在数组中得到的值要么收敛到无穷大要么负无穷大（非常高的数字）
任何帮助将非常感激。

> // Polynomial evaluation method.
   public Complex evalPoly(Complex complexArray[], Complex guess) {
        Complex result = new Complex(0, 0);
        for (int i = 0; i < complexArray.length; i++) {
            result = result.gaussMult(guess).addComplex(complexArray[complexArray.length - i - 1]);
        }
        return result;
    }

> // Polynomial differentation method.
    public Complex[] diff(Complex[] comp) {
        Complex[] result = new Complex[comp.length - 1];
        for (int j = 0; j < result.length; j++) {
            result[j] = new Complex(0, 0);
        }
        for (int i = 0; i < result.length - 1; i++) {
            result[i].real = comp[i + 1].real * (i + 1);
            result[i].imaginary = comp[i + 1].imaginary * (i + 1);
        }
        return result;
    }

> // Method which eliminates some of the things that I don't want to go into the array
    public boolean rootCheck2(Complex[] comps, Complex comp) {
        double accLim = 0.01;
        if (comp.real == Double.NaN)
            return false;
        if (comp.real == Double.NEGATIVE_INFINITY || comp.real == Double.POSITIVE_INFINITY)
            return false;
        if (comp.imaginary == Double.NaN)
            return false;
        if (comp.imaginary == Double.NEGATIVE_INFINITY || comp.imaginary == Double.POSITIVE_INFINITY)
            return false;
        for (int i = 0; i < comps.length; i++) {
            if (Math.abs(comp.real - comps[i].real) < accLim && Math.abs(comp.imaginary - comps[i].imaginary) < accLim)
                return false;
        }
        return true;
    }

> // Method which finds (or attempts) to find all of the roots
  public Complex[] addUnique2(Complex[] poly, Bitmap bitmapx, Paint paint, Canvas canvasx) {
        Complex[] rootsC = new Complex[poly.length - 1];
        int iterCount = 0;
        int iteLim = 20000;
        for (int i = 0; i < rootsC.length; i++) {
            rootsC[i] = new Complex(0, 0);
        }
        while (iterCount < iteLim && MainActivity.a < rootsC.length) {
            double guess = -492 + 984 * rand.nextDouble();
            double guess2 = -718 + 1436 * rand.nextDouble();
            if (rootCheck2(rootsC, findRoot2(poly, new Complex(guess, guess2), bitmapx, paint, canvasx))) {
                rootsC[MainActivity.a] = findRoot2(poly, new Complex(guess, guess2), bitmapx, paint, canvasx);
                MainActivity.a = MainActivity.a + 1;
            }
            iterCount = iterCount + 1;
        }
        return rootsC;
    }

> // Method which finds a single root of the complex polynomial.
    public Complex findRoot2(Complex[] comp, Complex guess, Bitmap bitmapx, Paint paint, Canvas canvasx) {
        int iterCount = 0;
        double accLim = 0.001;
        int itLim = 20000;
        Complex[] diffedComplex = diff(comp);
        while (Math.abs(evalPoly(comp, guess).real) >= accLim && Math.abs(evalPoly(comp, guess).imaginary) >= accLim) {
            if (iterCount >= itLim) {
                return new Complex(Double.NaN, Double.NaN);
            }
            if (evalPoly(diffedComplex, guess).real == 0 || evalPoly(diffedComplex, guess).imaginary == 0) {
                return new Complex(Double.NaN, Double.NaN);
            }
            iterCount = iterCount + 1;
            guess.real = guess.subtractComplex(evalPoly(comp, guess).divideComplex(evalPoly(diffedComplex, guess))).real;
            guess.imaginary = guess.subtractComplex(evalPoly(comp, guess).divideComplex(evalPoly(diffedComplex, guess))).imaginary;
            drawCircles((float) guess.real, (float) guess.imaginary, paint, canvasx, bitmapx);
        }
        return guess;
    }

> // Drawing method
    void drawCircles(float x, float y, Paint paint, Canvas canvasx, Bitmap bitmapx) {
        canvasx.drawCircle(x + 492, shiftBackY(y), 5, paint);
        coordPlane.setAdjustViewBounds(false);
        coordPlane.setImageBitmap(bitmapx);
    }

}

最佳答案

错误1

线

guess.real = guess.subtractComplex(evalPoly(comp, guess).divideComplex(evalPoly(diffedComplex, guess))).real;
guess.imaginary = guess.subtractComplex(evalPoly(comp, guess).divideComplex(evalPoly(diffedComplex, guess))).imaginary;

首先引入不必要的复杂性，其次引入导致其偏离牛顿方法的错误。第二行中使用的guess与第一行中使用的guess不同，因为实际部分已更改。

为什么不像评估程序那样使用复杂的分配

guess = guess.subtractComplex(evalPoly(comp, guess).divideComplex(evalPoly(diffedComplex, guess)));

错误2（更新）

在微分多项式的计算中，您错过了

for (int i = 0; i < result.length - 1; i++) {
   result[i].real = comp[i + 1].real * (i + 1);
   result[i].imaginary = comp[i + 1].imaginary * (i + 1);

它应该是i < result.length或i < comp.length - 1。当然，使用错误的导数将导致迭代中不可预测的结果。



根边界和初始值

您可以为每个多项式分配一个外部根边界，例如

R = 1+max(abs(c[0:N-1]))/abs(c[N])

在此圆上或附近使用随机或等距的3*N点，应会增加到达每个根的概率。

但是，找到所有根的通常方法是使用多项式放气，即，将与已经找到的根近似相对应的线性因子分开。然后，使用完整多项式的几个附加的牛顿步骤将恢复最大精度。



牛顿分形

每个根都有一个吸引盆地或域，域之间有分形边界。在重建与



我计算出牛顿分形，表明对根的两个的吸引和对另两个根的无知是其背后数学的特征，而不是实施牛顿方法的错误。



相同颜色的不同阴影属于同一根的域，其中亮度对应于到达根周围白色区域的步骤数。