Отделение корней многочлена

Сообщение №35217 от AL2010 04 июля 2010 г. 09:43
Тема: Отделение корней многочлена

Имеется многочлен 15-й степени с вещественными коэффициентами. Требуется найти все его корни.

Для определения интервала, на котором лежат ВСЕ корни многочлена, есть известные формулы (нижняя граница отрицательных корней и верхняя граница положительных корней). Теперь нужно определить подынтервалы, содержащие только ОДИН корень (чтобы потом на каждом таком подынтервале уточнить значение корня). Сейчас для этого использую очевидный способ: вычисляю многочлен с некоторым малым шагом по аргументу и ищу подынтервалы, на концах которых многочлен имеет различные знаки. Проблема, возникающая при этом, тоже очевидна: если длина подынтервала меньше величины шага, корень можно пропустить. Это возможно при сколь угодно малом конечном шаге.

Есть ли ещё какой-нибудь метод определения всех таких подынтервалов? Слышал про теорему Штурма, но она, вроде бы (или я ошибаюсь?), позволяет определить только общее количество корней на данном отрезке, а мне, наоборот, надо определить отрезки, содержащие только по одному корню.

В общем, если кто посоветует, как быть, или отошлёт к конкретной литературе, буду признателен.


Отклики на это сообщение:

> Имеется многочлен 15-й степени с вещественными коэффициентами. Требуется найти все его корни.

> Для определения интервала, на котором лежат ВСЕ корни многочлена, есть известные формулы (нижняя граница отрицательных корней и верхняя граница положительных корней). Теперь нужно определить подынтервалы, содержащие только ОДИН корень (чтобы потом на каждом таком подынтервале уточнить значение корня). Сейчас для этого использую очевидный способ: вычисляю многочлен с некоторым малым шагом по аргументу и ищу подынтервалы, на концах которых многочлен имеет различные знаки. Проблема, возникающая при этом, тоже очевидна: если длина подынтервала меньше величины шага, корень можно пропустить. Это возможно при сколь угодно малом конечном шаге.

> Есть ли ещё какой-нибудь метод определения всех таких подынтервалов? Слышал про теорему Штурма, но она, вроде бы (или я ошибаюсь?), позволяет определить только общее количество корней на данном отрезке, а мне, наоборот, надо определить отрезки, содержащие только по одному корню.

Успех поиска зависит от количества разрядов калькулятора. Если, например, вещественные коэффициенты имеют погрешность не менее 7 знака, то шаг поиска нужно брать в 9 или 10 знаке (учитывая то, что относительные погрешности при возведении искомого корня в 15 степень складываются 15 раз, что соответствует 2 добавочным знакам). Если же коэффициенты занимают все разряды калькулятора, то придется искать интервалы с помощью производных от многочлена.


Для разделения корней есть метод Штурма. Подозреваю, что он реализован в каждом приличном мат.пакете (в PARI/GP точно есть, в других - не проверял).
Вот его описание в википедии:

Ряд Штурма


> Для разделения корней есть метод Штурма. Подозреваю, что он реализован в каждом приличном мат.пакете (в PARI/GP точно есть, в других - не проверял).
> Вот его описание в википедии:

Спасибо, но описание я уже читал (см. моё исходное сообщение). Но как именно с помощью теоремы Штурма определить не КОЛИЧЕСТВО корней на данном отрезке, а все ОТРЕЗКИ, содержащие по одному корню? Не могу сообразить.


> Спасибо, но описание я уже читал (см. моё исходное сообщение). Но как именно с помощью теоремы Штурма определить не КОЛИЧЕСТВО корней на данном отрезке, а все ОТРЕЗКИ, содержащие по одному корню? Не могу сообразить.

Сначала избавится от кратных корней деля данный многочлен f(x) на НОД(f(x),f'(x)). Затем найти интервал содержащий все корни f(x) (т.е. в количестве равным его степени), например, наращивая k в интервале вида (-2^k,2^k) или сразу воспользовавшись какой-нибудь оценкой для абсолютной величин корней многочлена. А затем уже - используете метод деления отрезка пополам для разделения корней.


> Сначала избавится от кратных корней деля данный многочлен f(x) на НОД(f(x),f'(x)). Затем найти интервал содержащий все корни f(x) (т.е. в количестве равным его степени), например, наращивая k в интервале вида (-2^k,2^k) или сразу воспользовавшись какой-нибудь оценкой для абсолютной величин корней многочлена. А затем уже - используете метод деления отрезка пополам для разделения корней.

Найти интервал, содержащий ВСЕ корни многочлена, как раз не проблема (я писал, что существуют формулы для определения верхней границы положительных и нижней границы отрицательных корней). Это уже сделано. Теперь стоит вопрос: как разделить этот большой интервал на несколько маленьких, каждый из которых будет содержать по одному корню? Я сейчас просто тупо вычисляю многочлен f(x) на "большом" интервале с некоторым малым шагом по x и ищу подынтервалы, на границах которых f(x) имеет разные знаки. Затем на каждом таком подынтервале уточняю значение корня методом Ньютона (или, если он не сходится, делением пополам). Есть ли другой, более эффективный способ отыскания границ интервалов, содержащих единственный корень? Штурм в этом поможет?


> Найти интервал, содержащий ВСЕ корни многочлена, как раз не проблема (я писал, что существуют формулы для определения верхней границы положительных и нижней границы отрицательных корней). Это уже сделано. Теперь стоит вопрос: как разделить этот большой интервал на несколько маленьких, каждый из которых будет содержать по одному корню?

Делите интервал пополам для каждой половины:
i) с помощью системы Штурма определяете число корней в ней содержащихся;
ii) если число корней в ней равно 1, то корень локализован;
iii) если же число корней > 1, то снова (рекурсивно) делите пополам и повторяете анализ для половинок;
iv) если число корней равно 0, то выкидываете эту половину из рассмотрения.


> Делите интервал пополам для каждой половины:
> i) с помощью системы Штурма определяете число корней в ней содержащихся;
> ii) если число корней в ней равно 1, то корень локализован;
> iii) если же число корней > 1, то снова (рекурсивно) делите пополам и повторяете анализ для половинок;
> iv) если число корней равно 0, то выкидываете эту половину из рассмотрения.

Спасибо, попробую.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100