Обусловленность разложения полинома на множители тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Бибердорф, Элина Арнольдовна

• Бибердорф, Элина Арнольдовна
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Бибердорф, Элина Арнольдовна

ВВЕДЕНИЕ.

Разложение полинома на множители - состояние проблемы

Постановка задачи

Структура диссертации

ГЛАВА I Задача о дихотомии и критерий ее обусловленности

§ 1 Объекты, порождаемые полиномом

1.1 Разностные уравнения

1.2 Матричные пучки

1.2.1 Общие свойства регулярных матричных пучков .'.

1.2.2 Регулярность пучка порожденного полиномом

1.3 Функция Грина

§ 2 Критерии дихотомии

2.1 Ряд Лорана

2.2 Матричное представление критериев дихотомии

2.3 Различные критерии дихотомии и оценки для них

2.3.1 Квадратичная форма Н

2.3.2 Квадратичная форма Я

2.3.3 Квадратичная форма #

2.4 Критерии дихотомии и функция Грина.

§ 3 Вычисление критерия дихотомии

3.1 Приближенная функция Грина.

3.2 Последовательности Н^ и и оценки скорости сходимости к) т(к)

3.3 Рекуррентные формулы для элементов последовательностей Щ и Н3 и оценки скорости

ГЛАВА II Решение задачи о дихотомии корней полинома

§ 4 Алгоритм разложения полинома на множители

4.1 Описание алгоритма ----'.

4.2 Формулировка теорем сходимости

4.3 Выбор числа итераций

4.3 Пример работы алгоритма

§ 5 Метод ортогональных исключений.

5.1 Некоторые замечания

5.2 Обусловленность системы уравнений

§ б Применение ортогональных исключений к маричному пучку

6.1 Оценки различных канонических разложений

6.2 Изменения приводящих матриц при ортогональных исключениях . 68 6-3 Оценки для предельных матриц

Введение диссертации (часть автореферата) на тему «Обусловленность разложения полинома на множители»

Разложение полинома на множители - состояние проблемы

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

Пусть задан полином /(ж) степени п:

И = /о + Л х + . + /пхп. ■ . (0.1)

Для исследования расположения корней /(ж) до сих пор применяются методы, основы которых закладывались в работах Эрмита, Якоби, Борхардта и других ученых еще в 19-ом и в начале 20-го века. В частности, один известный численный алгоритм нахождения корней полинома был впервые предложен Лобачевским (1834г.), переоткрыт Греффе (1837г.), усовершенствован Энке (1841г.) и в своем окончательном варианте подробно изложен Крыловым в книге [15]. Он базируется на выражении коэффициентов полинома через его корни и заключается в построении и анализе цепочки вспомогательных полиномов узМ(ж), к = 0,1,2,., корни которых суть возведенные в. степень 2к корни (0.1). Этот алгоритм неплохо зарекомендовал себя в случае полиномов невысоких степеней с вещественными корнями. Однако, при высоких степенях он не только требует больших вычислительных затрат, но и выдает ненадежные результаты (особенно при наличии близких по модулю и комплексно сопряженных корней).

Заметим, что для изучения расположения корней полинома на комплексной плоскости нередко используются матрицы. Одним из примеров такого подхода является хорошо известный критерий Раусса-Гурвица ([10], гл.II, §7). 5

В качестве другого примера применении матричной техники рассмотрим одну из наиболее поздних (1921г) и полных работ этого цикла - статью А. Кона [20]. Эта классическая работа, содержание которой как нельзя более соответствует обсуждаемой проблеме, обобщает изложенные в [22] результаты И. Шура. В ней описан достаточно простой способ подсчета числа корней полинома, лежащих внутри и вне единичного круга.

Предложенный Коном алгоритм основан на следующих утверждениях об исходном (0.1) и полученном из него вспомогательном /*(ж) = хп/(1/х) полиномах (операция * означает комлексное сопряжение и инверсию относительно единичной окружности корней (0.1))

Лемма 0.1 Пусть \fn\ > |/0|. Составим новый полином /^(ж) степени не выше п — 1 по формуле: г/(1)(®)=/«Л®)-/о /*(*)•

Тогда /(х) имеет внутри единичного круга одним корнем больше, чем .

Лемма 0.2 Пусть \/п\ < |/0|. Тогда полином

1)00=/о/(*)-/»/•(*), степень которого не превышает п—1, имеет внутри единичного круга столько же корней, что и исходный полином /(ж).

Лемма 0.3 Пусть но

Положим

1п - е/о, 1п~1 = £¡1,., ¡п-к+1 ~ еД-1, |е| = 1, к <

1п—к

6 = п тогда полином степени п + к удовлетворяет условиям леммы 0.2. В результате применения к нему предписанной там процедуры получается новый полином, степени п который, в свою очередь, удовлетворяет условиям леммы 0.1 и имеет внутри единичного круга столько же корней, что и исходный полином /(ж).

Лемма 0.4 Пусть /пй = еД для всех к. Тогда полином степень которого не превышает п — 1, имеет внутри единичного круга столько же корней, что и исходный полином /(х).

Очевидно, что всегда можно организовать вычислительный процесс так, чтобы на каждом шаге уменьшать степень полинома на единицу, применяя к нему одну из четырех приведенных выше лемм. В результате через п — 1 шагов число корней полинома внутри и вне единичного круга будет известно.

В своей статье Кон вводит матрицу Дс, которую для дальнейшего использования удобно представить в виде

Нс = А* А - В В*, (0.2) где треугольные матрицы А, В записываются через коэффициенты исследуемого полинома

А = к ¡1 ■■■ /п—1 \ о • • • /п-2

-В = /п п—1 /п о

0.3) Л • • • /п-1 /п /

Здесь звездочка, как обычно, означает транспонирование и комплексное сопряжение.

Относительно матрицы Нс доказана следующая важная 7

Теорема 0.1 Если среди собственных чисел эрмитовой матрицы Нс имеется I положительных и т отрицательных (I + т = п). то I корней полинома (0.1) по модулю меньше единицы и т - больше единицы.

Это утверждение нуждается в комментариях. Формулировка теоремы предполагает, что матрица Нс невырождена и Кон трактует это как неравенство нулю ее определителя. Но, как известно, определитель матрицы есть величина вычислительно неустойчивая, поэтому правильнее было бы предполагать хорошую обусловленность. Последнее означает, что связанная с Нс числовая характеристика тт \ с) ~-7Т7Т >

О тгп\*1с} не слишком велика (здесь оштах(Нс) и <Ут{п{Нс) есть максимальное и минимальное сингулярные числа). Следует отметить, что этому условию не удовлетворяют матрицы Нс, построенные по описанным в лемме 0.4 полиномам и близким к ним. Действительно, для таких полиномов матрицы А* А и В В* (см. (0.3)) равны или "почти" равны. Следовательно, матрица Нс оказывается нулевой или "почти" нулевой.

Пример. Корни полинома 1 — 2.5ж + ж2 равны 2 и 0.5 и, очевидно, хорошо отделены от единичной окружности. В то же время 1 -2.5 \

А = В* О следовательно матрица Нс = 0 и не может быть использована для изучения расположения корней.

Условие невырожденности Нс нарушается также для полиномов, среди корней которых есть нулевые и бесконечные или очень маленькие и очень большие.

Пример. Для полинома /(ж) = 0 х + 2х2 + 0ж3 находим

00 о \

Яс(/)= 0 5 4 0 4 10 у 8

Пусть /(ж) - любой другой полином, коэффициенты которого мало отличаются от коэффициентов /(ж). Видно, что матрица #с(/) будет плохо обусловлена и ее нельзя использовать для определения числа корней / внутри и вне единичного круга. Можно построить и более сложные примеры неприменимости матрицы Нс для нахождения числа корней полинома больших и меньших по модулю единицы.

Указанное обстоятельство иллюстрирует тот важный факт, что практически все известные сегодня алгоритмы требуют, чтобы младший и старший коэффициенты полинома (0.1) были бы соизмеримы с нормой вектора его коэффициентов ||/|| = (Е)т=о /т)1^2

1/о|> с/И/И, |/„|> суЦ/11, (0.4) где постоянная с/ не должна быть много меньше единицы.

Можно сделать следующее общее заключение. Существующие способы анализа расположения корней полинома относительно единичного круга достаточно просты, но чувствительны к вычислительным погрешностям. Использование с этой целью матрицы Кона Нс, как было показано на простых примерах, может приводить к ложным результатам даже тогда, когда эти корни хорошо разделены. Отметим, что со времени изобретения большинства известных алгоритмов порядки исследуемых полиномов значительно возросли и, как следствие, возросла роль ошибок округлений, что может решающим образом сказаться на точности вычислений. Стала очевидной необходимость создания устойчивых алгоритмов нового поколения, работа которых сопровождается оценками погрешностей результатов.

В течении 1996 года С.К. Годунов и 0. Богмат проводили численные эксперименты с описанным выше алгоритмом Кона (результаты опубликованы не были). На основании этих исследований С.К. Годуновым был сделан вывод о необходимости кардинального пересмотра всего подхода к проблеме с привлечением современных алгоритмов линейной алгебры для анализа матричных спектров.

Настоящая диссертация посвящена реализации основной идеи этого подхода, за9 ключающейся в установлении связи корней исследуемого полинома (0.1) с собственными числами матричного пучка (А, В), построенного по формулам (0.3). Это позволяет свести вопрос об отделении корней полинома к решению хорошо проработанной задачи дихотомии матричного спектра единичной окружностью (а заодно и снять обременительные в ряде случаев ограничения (0.4).

Задача о дихотомии матричного спектра также имеет свою историю. Дихотомия спектра оператора мнимой осью исследована в [14], где авторы предлагают анализировать расположение спектра с помощью индефинитной квадратичной формы. В статье [9] С.К. Годунов заменил индефинитную форму положительно определенной, в [5] был введен ее аналог для дихотомии единичной окружностью, в [21] - для эллиптической дихотомии. В [4] А.Я. Булгаков показал, что эрмитова матрица Н из [9] (аналог матрицы Ляпунова) и проекторы Р и I — Р на инвариантные подпространства матрицы являются решениями некоторой системы матричных уравнений, которую можно считать обобщением классического уравнения Ляпунова. Отметим, что хотя рассуждения А.Я. Булгакова напоминают проведенные в [14], но переход к знакоопределенным формам открыл новые возможности численного анализа дихотомии. Действительно, обобщенные уравнения Ляпунова допускают единственное решение только если дихотомия спектра имеет место, причем удаление точек спектра от кривой (мнимой оси, окружности или эллипса) оценивается через норму ||Я||. Использование знакоопределенных форм сделало возможным появление современных алгоритмов решения спектральных задач для несамосопряженных операторов с гарантированной точностью.

Постановка задачи

Требуется исследовать расположение корней полинома (0.1). Условия (0.4) здесь не ставятся (полином может иметь нулевые и бесконечные корни) и единственным ограничением является требование отсутствия корней на единичной окружности. Иными

10 словами, /(ж) может быть представлен как произведение двух других полиномов ж) = Сд(х)к(х), д{х) = до + 9\Х + . •. + Я1-1Х1-1 +х1 = (х- Ах) (ж - А2). {х - А г), (0.5) г(ж) = 1 + + . + кххт~х + /¿0жт = (уахх - 1){ц2Х - 1). (цтх - 1), где I + то = п. Это означает также, что если ввести обратный к Л(ж) полином к{п{х) = хтк(1/х), то его корни ^х,., /«т, как и корни Ах,. , А; полинома д(ж), лежат внутри некоторого круга радиуса р < 1 и выполнены неравенства

А,|<р<1, Ы </><!• (0-6)

Основная задача, решению которой посвящена диссертация, формулируется теперь классически просто: для заданного полинома /(ж) определить, есть ли среди его корней лежащие на единичной окружности и, если таковых нет, найти коэффициенты сомножителей д{х) и /г(ж).

В современной вычислительной практике встречаются полиномы больших степеней и их корни могут скапливаться вблизи единичной окружности таким образом, что становятся от нее неотделимы в компьютерном представлении. По этой причине возникает необходимость отыскания кольца с внутренним радиусом р < 1 и внешним радиусом 1/р > 1, в котором можно гарантировать отсутствие корней /(ж). Такую задачу можно назвать задачей дихотомии корней полинома единичной окружностью.

Основными результатами данной диссертации являются алгоритм отыскания входящих в (0.5) сомножителей д(х), к(х) и способ оценки радиуса дихотомии р. Отличительными особенностями этого алгоритма являются

1. вычисление коэффициентов полиномов д(х) и Н(х) с гарантированной точностью;

2. диагностика ситуации, когда корни /(ж) лежат слишком близко к единичной окружности и счет с гарантированной точностью невозможен.

В качестве исходных данных для вычислительного процесса используются коэффициенты полинома /(ж), параметр ртах (максимально допустимая граница для модулей корней р < ртах < 1, см. (0.6)), а также параметр относительной точности вычисления коэффициентов е.

11

На выходе для коэффициентов полиномов д(х) и к(х) будут получены приближенные значения ~дЦ, /г?, удовлетворяющие соотношениям тахШ ~9% \\h~4} < е||/||, ■ (0.7) а также числовые параметры ро, р\ оценивающие расстояние корней до единичной окружности: 0 < ро < р < р\ < 1.

Если р\ превосходит ртах (что свидетельствует о практическом отсутствии дихотомии), то вычислительный процесс прерывается с выдачей соответствующего сообщения.

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

Структура диссертации

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

Заключение диссертации по теме «Вычислительная математика», Бибердорф, Элина Арнольдовна

Основные результаты диссертации

1 Предложен новый эффективный алгоритм разложения полинома на множители, соответствующие его корням, лежащим строго внутри и строго вне единичного круга, допускающий вычисления с гарантированной оценкой точности результата

§4).

2 Получены доказательства теорем о сходимости этого алгоритма (§ 6).

3 Разработан подход к проблеме разложения полинома на множители, использующий современные вычислительные методы линейной алгебры. Введены критерии дихотомии #2 и Яз, с помощью которых обусловленность задачи о дихотомии корней полинома может быть оценена количественно (§2).

4 Обоснованы неравенства, связывающие матрицы Я2 и Яз с радиусом дихотомии р

§2).

5 Приведен способ приближенного вычисления матриц Яг и Яз и получены оценки его сходимости (§ 3).

Материал диссертации изложен в работах [2], [3].

Результаты обсуждались на семинарах ИМ СО РАН, ИВМ и МГ СО РАН.

Я глубоко признательна своему научному руководителю С.К.Годунову за постановку проблемы, очень важные и полезные для меня научные обсуждения. Особую благодарность я выражаю А.М.Блохину (ИМ СО РАН) и В.В.Вечеславову (ИЯФ СО РАН) за всемерную помощь, поддержку и терпение. Мне хочется также сказать большое спасибо другим сотрудникам Института математики, Института вычислительной математики и математической геофизики и Института ядерной физики СО РАН за доброжелательные и заинтересованные дискуссии по относящимся к моей работе темам.

77

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Бибердорф, Элина Арнольдовна, 2000 год

1. Бибердорф Э.А., Попова Н.И. Решение линейных систем с гарантированной оценкой точности результатов. Ч. 1. Препринт 99-49 ИЯФ. Новосибирск, 1999.

2. Бибердорф Э.А. Современный аспект проблемы разложения полинома на множители. Методические материалы. Издательский центр НГУ, 1999.

3. Бибердорф Э.А. Критерий дихотомии корней полинома единичной окружностью // Сиб. журн. инд. мат., 2000, Т. 3, N 1, С. 16-32

4. Булгаков А.Я. Обоснование гарантированной точности выделения инвариантных подпространств несамосопряженных матриц // Тр. Ин-та математики /АН СССР Сиб. отд-ние, 1989, Т. 15, С. 12-92.

5. Булгаков А.Я., Годунов С.К. Круговая дихотомия матричного спектра // Сиб. мат. журн. 1988, Т. 29, N 5, С. 59-70.

6. Гельфонд А.О. Исчисление конечных разностей. М., 1959.

7. Годунов С.К.j Рябенький В.С. Введение в теорию разностных схем. М., 1962.

8. Годунов С.К. Уравнения математической физики. М., 1971.

9. Годунов С.К. Задача о дихотомии спектра матрицы // Сиб. мат. журн. 1986, Т 27, N 5, С. 24-37.

10. Годунов С.К. Обыкновенные дифференциальные уравнения с постоянными коэффициентами. Т.1. Новосибирск, 1994.

11. Годунов С.К., Антонов А.Г., Кирилюк О.П., Костин В.И. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. Новосибирск. Наука. 1992.

12. Годунов С.К. Современные аспекты линейной алгебры. Новосибирск. Научная книга. 1997.

13. Гончаров В. Л. Из области комбинаторики // Изв. АН СССР. Сер. математика. 1944. Т.8, N 1.

14. Далецкий Ю.Л., Крейн М.Г. Устойчивость решений дифференциальных уравнений в банаховом пространстве. М.: Наука, 1970.

15. Крылов А.Н. Лекции о приближенных вычислениях. Изд. Ак. Наук СССР, 1933.

16. Кузнецов С. В. О построении спектральных графиков для несимметрических матриц. Препринт N8 Института Математики СО РАН, Новосибирск, 1993.

17. Малыш,ев А.Н. Введение в вычислительную линейную алгебру. Новосибирск: Наука, 1991.

18. Савельев Л.Я. Максимум длин серий // Дискретная математика. М., 1999. Т.Н. Вып.1.

19. Феллер Л.Я. Введение в вычислительную линейную алгебру. Новосибирск: Наука, 1991.

20. Cohn А. Uber die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise.

21. Godunov S.K. Sadkarie M. Elliptic Dichotomyof a Matrix Spectrum'// Linear Algebra and its Applications 248, 1996, 205-232.

22. Schur /.Uber Potenzreihen, die im Innern des Einheitskreises beschränkt sind // Journ. f. Math. 147, 1917, S. 205-232.