Java находит нулевые точки с бесконечным циклом алгоритма Ньютона

У меня возникла проблема с методом, который берет многочлен типа f(x)=x²+1 и вычисляет возможные нулевые точки с помощью алгоритма Ньютона.
Я указал требования к конкретным переменным, поэтому, даже если название не подходит или переменная не нужна, я должен их использовать:/
Многочлен, который я даю своему методу в качестве параметра, представляет собой двойной массив: для f(x)=x²+1 это будет {1.0,0.0,1.0}, поэтому он построен как 1.0*x^0 + 0.0*x^1+1.0*x^2

Для моего кода:
x0 — это начальное значение алгоритма Ньютона, а eps — точность вычислений.

Я следовал моим инструкциям и получил следующий код:

public static double newton(double[] a, double x0, double eps) { 
    double z;
    double xn; 
    double xa = x0; 
    double zaehler;
    double nenner;

    do {
        zaehler = horner(a, xa);
        nenner = horner(ableit(a), xa);
        if(nenner == 0) {
            return Double.POSITIVE_INFINITY;
        }
        xn = xa - (zaehler/nenner);
        xa = xn;
    } while((Math.abs(horner(a, xn))) >= eps);
    z = xn;
    return 0;
}

метод horner() вычисляет значение y данной функции для заданного значения x.

Моя проблема заключается в том, что если функция не имеет нулевой точки, такой как x²+1, и я начинаю с x0=1 и eps=0.1, я получаю возврат бесконечности.
Но если я начинаю с x0=10 и eps=0.1например, я создаю бесконечный цикл.

Как с этим справиться или это общая проблема с алгоритмом Ньютона?!
Единственный способ установить фиксированный максимум итераций? Кодекс работает для многочленов, имеющих хотя бы одну нулевую точку!


java infinite-loop algorithm math newtons-method
person KilledByCheese    schedule 02.12.2018    source источник
comment
Вы можете подсчитать количество циклов или отслеживать результат, ожидая, что они будут приближаться.   -  person Geno Chen    schedule 02.12.2018
comment
Возможный дубликат Infinite Loop: определение и выход из бесконечного цикла< /а>   -  person Robin Green    schedule 02.12.2018
comment
Имена переменных затрудняют чтение вашего кода для не говорящих по-немецки (?).   -  person Sneftel    schedule 02.12.2018
comment
Всегда смотрите на график своей функции, чтобы попытаться получить некоторое представление о ней. Я часто использую Wolfram Alpha для таких вопросов.   -  person President James K. Polk    schedule 02.12.2018

Ответы (1)


arrow_upward
2
arrow_downward

Метод Ньютона-Рафсона требует существования действительного корня x такого, что f(x)=0. Функция, которую вы используете x^2+1, не имеет реальных корней, поэтому ваш алгоритм не будет работать в этом случае (как и в других, где нет корня).

Поскольку x^2+1 >= 1 для всех реальных x подразумевает horner(a, xn) >= 1, то цикл

while((Math.abs(horner(a, xn))) >= eps)

не завершится на eps < 1.

Может быть, прежде чем начать итерацию, вам следует проверить наличие нуля. Например. если старший (по степени x) ненулевой коэффициент нечетен, то будет реальный нуль.

Или расширить свой алгоритм так, чтобы он предварительно пытался найти некоторые реальные aи b такие, что f(a)f(b) <= 0 (тогда между a и b есть корень).

person Maksim    schedule 02.12.2018