Корень полинома нахождение бисекции

Question

Если я нахожу корни многочлена, используя метод деления пополам, и в некоторых случаях в зависимости от многочлена корни могут быть отрицательными или положительными.

Я понимаю, что могу определить, могут ли корнибудут отрицательными или положительными, основанными на результате оценки полинома ... однако я не уверен, что бы я использовал как х.

Может ли кто-нибудь дать здесь какое-то понимание?

Answer 1

Тот факт, что корни могут быть отрицательными или положительными, не имеет ничего общего с методом деления пополам. Существование корня может быть доказано с помощью теоремы о промежуточном значении из исчисления.

Таким образом, все, что вам нужно сделать, это найти точки x1 и x2, чтобы y(x1) было отрицательным, а y(x2) - положительным. Тогда вы знаете из IVT, что есть корень между x1 и x2. Вы делаете это, выполняя бинарный поиск по этому интервалу. Если y(x3) = y((x1+x2)/2) отрицательно, то вы повторяете поиск пополам на интервале [x3,x2]. В противном случае, если оно положительное, ищите в интервале [x1,x3].

Не имеет значения, является ли корень отрицательным или положительным. Я не уверен, что это отвечает на ваш вопрос, но я надеюсь, что это поможет вам понять алгоритм.

Answer 2

Возможно, вы найдете это полезным.

с использованием системы;

Пространство имен Bisection_Method

{

class Program

{

    public double midPoint (double xl, double xu)

{

    return (xl + xu) / 2;

}

    public double function(double x)

    {

        return (x*x-2);

    }

    static void Main(string[] args)

    {

        Program root = new Program();

        double xm=0, xl=1, xu=2, check=0;

        for (int x = 0; x < 20; x++)

        {

            xm = (xl + xu) / 2;

            check = root.function(xl) * root.function(xm);

            if (check < 0)

                xu = xm;

            else if (check > 0)

                xl = xm;

            else if (check == 0)

            {

                break;

            }

        }

        Console.WriteLine("The Approximate of the Root is {0}", xm);

    }

}

}

http://mustafa.amnbytes.com/2012/09/bisection-method-program-in-c.html

Answer 3

Чтобы использовать алгоритм деления пополам, сначала нужно найти интервал, содержащий корень. Стандартный алгоритм для этого приведен в Теорема Штурма .

Однако стандартный алгоритм деления пополам ожидает, что знаки значений функций в конечных точках будут разными. Это может быть проблемой. Простейшим примером является x ^ 2, у которого один корень 0 порядка 2. Поскольку x ^ 2 положителен для всех ненулевых x, вы не можете найти интервал, содержащий корень, подходящий для использования с алгоритмом деления пополам.

Answer 4

Многие корневые искатели позволяют пользователю указывать начальную точку или точки для начала поиска. Это позволяет пользователям пытаться «поиграть» с результатами, чтобы найти разные корни, или позволить искателю сходиться к корню.

Если нет смысла разрешать пользователю указывать начальные значения, вы можете начать с определения нескольких точек:

• -1, 0, 1
• -10, 0, 10
• -100, 0, 100
• и т.д.

Если входные данные являются нечетным полиномом, это в конечном итоге обнаружит подходящий диапазон для деления пополам. Если вход является четным полиномом, вы можете никогда не поймать изменения знака (рассмотрите f (x) = x ^ 2 - он никогда не будет отрицательным), поэтому будьте готовы сдаться после определенного (настраиваемого?) Количества проб.

Я предложил увеличить диапазоны на 10 степеней здесь; поскольку метод деления пополам каждый раз сокращает диапазон пополам, возможно, это слишком консервативный подход. (Потребуется от двух до трех итераций деления пополам, чтобы уменьшить диапазон до следующей «более жесткой» скобки.) Возможно, лучше было бы увеличить прыжки:

• -10, 0, 1
• -1000, 0, 1000
• -100000, 0, 100000
• и т.д.

Это будет выполнять меньше зондов, но потребует больше деления пополам. Попробуйте несколько полиномов и проследите время выполнения для поиска корней с обоими предложениями.