ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ ....................................................................4
Разложение полинома на множители - состояние проблемы ..........4
Постановка задачи .....................................................9
Структура диссертации ................................................11
ГЛАВА I Задача о дихотомии и критерий ее обусловленности ..................14
§ 1 Объекты, порождаемые полиномом ...................................14
1.1 Разностные уравнения .........................................14
1.2 Матричные пучки ..............................................15
1.2.1 Общие свойства регулярных матричных пучков ............ 15
1.2.2 Регулярность пучка порожденного полиномом ..............16
1.3 Функция Грина ................................................17
§ 2 Критерии дихотомии ...............................................19
2.1 Ряд Лорана ...................................................19
2.2 Матричное представление критериев дихотомии ..................19
2.3 Различные критерии дихотомии и оценки для них ................21
2.3.1 Квадратичная форма //, .................................21
2.3.2 Квадратичная форма Я* ........................:.........23
2.3.3 Квадратичная форма Я3 ..................................25
2.4 Критерии дихотомии и функция Грина............................28
§ 3 Вычисление критерия дихотомии ....................................31
3.1 Приближенная функция Грима ................................. 31
3/2 Последовательности и Я^1 и оценки скорости сходимости ........33
2
3.3 Рекуррентные формулы для элементов последовательностей И\к> и и оценки скорости ................................................34
ГЛАВА II Решение задачи о дихотомии корней полинома ......................39
§ 4 Алгоритм разложения полинома на множители .......................39
4.1 Описание алгоритма —.........................................39
4.2 Формулировка теорем сходимости ..............................41
4.3 Выбор числа итераций ........................................42
4.3 Пример работы алгоритма .................................... 43
§ 5 Метод ортогональных исключений .................................50
5.1 Некоторые замечания ....................................... 50
5.2 Обусловленность системы уравнений ...........................51
§ 6 Применение ортогональных исключений к маричному пучку ...59
6.1 Оценки различных канонических разложений ....................59
6.2 Изменения приводящих матриц при ортогональных исключениях ... 68
■
6.3 Оценки для предельных матриц ................................70
Заключение .............................................................. 76
ПРИЛОЖЕНИЕ ...............................................................77
§ 7 Решения разностных уравнений и корни полинома ..................77
§ 8 Функция Грина как решение разностного уравнения ................83
§ 9 Один из вариантов алгоритма ....................................85
§ 10 Вспомогательные утверждения о матричных пучках ................86
§ 11 Теорема о специальном каноническом разложении .................92
11.1 Формулировка теоремы о специальном каноническом разложении . 92
11.2 Симметрические функции .....................................95
11.3 Доказательство теоремы о специальном каноническом разложении 97 ЛИТЕРАТУРА ...................................................................... 103
4
Введение
Разложение полинома на множители - состояние проблемы
Задача о разложении полин(ша па множители всегда актуальна. Ома постоянно возникает в самых разных областях как самой математики, так и других наук. Эту проблему приходится решать при исследовании распределений целочисленных случайных величин, постановке краевых условий для уравнений математической физики, изучении устойчивости решений дифференциальных и разностных уравнений и по многих других случаях.
Пусть задан полином Дх) степени п:
Д*) = /0 + /|* + ... + /п*4- ■ . (0.1)
Для исследования расположения корней /(х) до сих пор применяются методы, основы которых закладывались в работах Эрмита, Якоби, Борхардта и других ученых еще в 19-ом и в начале 20-го пека. В частности, один известный численный алгоритм нахождения корней полинома был впервые предложен Лобачевским (1834г.), переоткрыт Греффе (1837г.), усовершенствован Энке (1841г.) и в своем окончательном варианте подробно изложен Крыловым в книге [15). Он базируется на выражении коэффициентов полинома через его корни и заключается в построении и анализе цепочки вспомогатель- • мых полиномов к = 0,1,2,.., корни которых суть возведенные в степень 2* корни
(0.1). Этот алгоритм неплохо зарекомендовал себя в случае полиномов неъысоких степеней с вещественными корнями. Однако, при высоких степенях он не только требует больших вычислительных затрат, но и выдает ненадежные результаты (особенно при наличии близких по модулю н комплексно сопряженных корней).
Заметим, что для изучения расположения корней полинома на комплексной плоскости нередко используются матрицы. Одним из примеров такого подхода является хорошо известный критерий Раусса-Гурвица {[10], гл.11, §7).
В качестве другого примера применении матричной техники рассмотрим одну из наиболее поздних (192її) и полных работ этого цикла - статью А. Кона [20). Эта классическая работа, содержание которой как нельзя более соответствует обсуждаемой проблеме, обобщает изложенные в [22] результаты И. Шура. В ней описан достаточно простой способ подсчета числа корней полинома, лежащих внутри и вис единичного круга.
Предложенный Коном алгоритм основан на следующих утверждениях об исходном (0.1) и полученном из него вспомогательном /*(х) = г"/(1/х) полиномах (операция + означает комлексное сопряжение и инверсию относительно единичной окружности корней (0.1))
Лемма 0.1 Пусть |/„| > \}и\. Составим повыв полхп*ол\ /()>(х) степени не оышеп — 1 по формула
=Ал*) - /./•(*>•
Таг да /(х) имеет внутри единичного круга одним корнем больше, чем /*1*(а:) .
Лемма 0.2 Пусть |/п| < |/0|. Тогда полином
/<■>(*) = /о/С») - /./•(*).
степень которого не превышает п - 1, имеет внутри единичного круга столько же корней, что и исходный полином /(*).
Лемма 0.3 Пусть
/п = е/о,Уп-»з = е/])•••)/п-^+1 “ » 1^1 = 1»^ ^ 12]*
но
/и-А: ф Є}к*
Положим
. /п-к-с/к
6
тогда полином
S(,)(r) = (т* + 2$ign[b))f(x),
степени п + к удоскхстворяст условиям леммы 0.2. В результате применения к нему предписанной т<ш процедуры получается новый полином степени п
<т = Л||М-1&,.9(|’-М
который, ь сво'іо очередь, удовлетворяет условиям леммы 0.1 и имеет внутри единичного круга столько же корней, что и исходный полином f(x).
Лемма 0.4 Пусть /»_* = г/* для всех к. Тогда полином
/<"(*) = x»"/'(l/*>,
сшелемь которого не превышает л — 1, имеет внутри единичного круга столько же корней, что и исходный полином /(х).
Очевидно, что всегда можно организовать вычислительный процесс так, чтобы на каждом шаге уменьшать степень полинома на единицу, применяя к нему одну из четырех приведенных пышс лемм. В результате через п — 1 шагов число корней полинома внутри и вне единичною круга Судет известно.
В своей статье Кон вводит матрицу //<-, которую для дальнейшею использования удобно представить в виде
Ht = А* А — ВВ* у (0/2)
где треугольные матрицы А, В записываются через коэффициенты исследуемого полинома
//о /, ... /»-. и
/о ... /я-2 , -П = /п-1 /»
/о V /і /я-1 /п
Здесь звездочка, как обычно, означает транспонирование и комплексное сопряжение. Относительно матрицы Нг доказана следующая важная
7
Теорема 0.1 Вели среди собственных чисел эрмитовой матрицы Нг имеется I пело- • житпельмых и тп отрицательных (I + т = п), то I корней полинома (0.1) по .чодулю меньше единицы и т - больше единицы.
Это утверждение нуждается в комментариях. Формулировка теоремы предполагает, что хютрпца Н, иевырождема и Кон трактует это как неравенство нулю се определителя. Но, как известно, определитель матрицы есть величина вычислительно неустойчивая, поэтому правильнее было бы предполагать хорошую обусловленность. Последнее означает, что связанная с Нс числовая характеристика
не слишком велика (здесь <7т4Т(Нс) и оть{Нс) сеть максимальное и минимальное сингулярные числа). Следует отметить, что атому условию не удовлетворяют матрицы //с, построенные по описанным в лемме 0.1 полиномам и близким к ним. Действительно, для таких полиномов матрицы А'А и ВВ* (см. (0.3)) равны или "почти” равны. Следовательно, матрица Не оказывается нулевой или "почти" нулевой.
Пример. Корни полинома 1 — 2.5x4 х2 равны 2 и 0.5 и, очевидно, хорошо отделены от единичной окружности. В то же время
следовательно матрица = 0 и не может быть использована для изучения расположения корней.
Условие невырожденности //с нарушается также для полиномов, среди корней которых есть нулевые и бесконечные или очень маленькие и очень большие.
Пример. Для полинома /(*) = 0 + х + 2х2 + О*3 находим
/ООО /Ш) =05 4
0 4 10