Отделение действительных корней многочлена: метод цепных дробей

Введение 

Самые ранние из известных  аналогов алгебраических уравнений  содержатся в папирусе Ринда и, очевидно, компилированы из более ранних работ египтянином Амесом приблизительно в 1650 или 1700 г. до нашей эры. Мы находим, например, следующую задачу: «Количество и его седьмая часть, сложенные вместе, дают 19. Чему равно количество?». Очевидно, задача состоит в том, чтобы решить уравнение х + (l/7)x = 19, как мы сказали бы сегодня. Из-за недостатка удобных алгебраических обозначений египтяне пользовались громоздким методом, известным впоследствии как метод «ложного положения». Хотя иногда утверждают, что греки умели решать уравнения второй степени, в общем ни египтяне, ни греки не сделали сколько-нибудь заметного продвижения с современной точки зрения. Арабы достигли большего, но только во времена Ренессанса, когда итальянские математики пятнадцатого и шестнадцатого столетий (Тарталья, Кардано и Феррари) преуспели в решении через радикалы общих уравнений третьей и четвертой степени, были выполнены работы, представляющие длительный интерес. В семнадцатом и восемнадцатом столетиях предпринимались многочисленные попытки решить общее уравнение пятой степени; было также достигнуто более глубокое понимание природы корней алгебраического уравнения (особенно после работы Декарта), но, несмотря на все это, никому не удалось решить в радикалах уравнение пятой степени. Естественно, что математики задались вопросом, возможно ли вообще такое решение. Ответ дал Руффини (1804), первым показавший невозможность алгебраического решения уравнения пятой степени. Позднее Абель (1826) доказал, что невозможно в общем случае решать алгебраические уравнения степени выше четвертой. В начале девятнадцатого века внимание математиков уже сосредоточилось на численных методах решения общих полиномиальных уравнений с целыми коэффициентами. В этот период у Фурье возникла идея разделить процесс на два шага, т.е. сначала отделить вещественные корни, а затем аппроксимировать их с любой желаемой степенью точности. (В соответствии с хорошо известным в математике подходом: если проблема слишком трудна, чтобы решить ее целиком, расщепляют ее на более простые.)

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

Как только прояснились цели, последовали и успехи. В начале девятнадцатого столетия Бюдан и Фурье представили две различные (но эквивалентные) теоремы, позволяющие определять максимум возможного числа вещественных корней уравнения с вещественными коэффициентами на данном интервале. Теорема Бюдана появилась в 1807 г. в работе «Nouvelle methode pour la resolution des equations numeriques», а теорема Фурье была впервые опубликована в 1820 г. в «Le bulletin des sciences par la societephilomatique de Paris». В силу значимости этих двух теорем возникли большие разногласия относительно приоритетных прав. В своей книге Biographies of distinguished scientific men, с. 383, Араго (1859) сообщает, что Фурье «счел необходимым получить подтверждение бывших студентов Политехнической школы или профессоров университета», чтобы доказать, что он преподавал свою теорему в 1796, 1797 и 1803 гг. Основываясь на предложении Фурье, Штурм представил в 1829 г.улучшенную теорему, применение которой дает точное число вещественных корней полиномиального уравнения из Z[x] без кратных нулей на вещественном интервале; таким образом, он решил проблему отделения вещественных корней (Bocher, 1911-1912). С 1830 г. метод Штурма становится единственным широко известным и используемым, и, следовательно, теорема Бюдана предается забвению. По нашим сведениям, теорему Бюдана можно найти только в статье Винсента и в работах автора, в то время как предложение Фурье появляется почти во всех текстах по теории уравнений. Теорема Бюдана заслуживает специального внимания, она составляет основу теоремы Винсента 1836 г. которая, в свою очередь, составляет основу метода цепных дробей 1978 г. (Akritas, 1980а, 1980b) отделения вещественных корней уравнения, метода, превосходящего метод Штурма по эффективности.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Отделение действительных корней многочлена: метод цепных дробей

Два метода цепных дробей отделения вещественных корней

Из приведенного обсуждения очевидно, что вычисление неполных частных a₁,a₂,...,a_m для подстановок вида (V3), которые приводят к уравнению ровно с одной переменой знаков,  составляет процедуру отделения вещественного корня. [Из теоремы Бюдана нам известно, что значение какого-то неполного частного a_i вычислено, если в последовательности коэффициентов уравнения р(a_i + х) = 0 больше перемен знаков, чем у уравнения р(a_i + 1 + х) = 0.] Имеются два метода цепных дробей: Винсента, 1836 г., и автора 1978 г., соответствующие двум различным способам вычисления неполных частных а_i. Как мы увидим ниже, различие между этими двумя методами можно рассматривать как аналог различия между интегралами Римана и Лебега. То есть хорошо известно, что сумма 1 + 1 + 1 + 1 + 1 может вычисляться следующими двумя способами: i. 1 + 1 = 2, 2+1 = 3, 3 + 1=4, 4+1 = 5 (Риман). ii. 5-1=5 (Лебег).

1. Метод цепных дробей Винсента

 В основе метода  цепных дробей Винсента (1836 г.) лежит вычисление какого-то неполного частного а_i с помощью серии единичных приращений,              а_i := а_i + 1, с каждым из которых мы должны выполнить сдвиг р_ti(х) := p_ti(1 + x) [для некоторого полиномиального уравнения р_ti(х) = 0] и проверить изменение числа перемен знаков. Этот подход «в лоб» приводит к методу с экспоненциальным поведением, и, следовательно, его практическая ценность невелика. Специального алгоритма для этого метода мы не приводим. В качестве примера метода Винсента отделим корни полиномиального уравнения

 р(х) = (х - α)(x - β) = 0,          (А1)

где α = 5 ∙ 10⁹  + ε и β = α + 1. Рассмотрим a₁^(α) первое неполное частное для α, которое равно 5 • 10⁹. При использовании метода Винсента мы первоначально полагаем a₁^(α) := 1, р_ti(х) := р(х) и вычисляем р_ti(х) := р_ti(1 + х). Поскольку число перемен знаков в последовательности коэффициентов преобразованного полинома p_ti(х) не изменилось, мы даем приращение a₁^(α) :=a₁^(α) + 1, вычисляем новый полином р_ti(х) := р_ti(1 + х), снова проверяя число перемен знаков. Этот процесс повторяется 5 • 10⁹ раз, и на самой быстрой ЭВМ это займет несколько лет. Однако метод Винсента весьма эффективен, когда значения неполных частных маленькие.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Метод цепных  дробей Акритаса

Напротив, метод цепных дробей, разработанный автором в 1978 г., заключается в немедленном вычислении какого-либо неполного частного а_i в качестве нижней границы b значений положительных корней некоторого полинома р_ti(х), т.е., пользуясь правилом Коши , мы немедленно определяем b и полагаем a_i := b. [Напомним, что вычисление нижней границы b_lo значений положительных корней некоторого полиномиального уравнения р(х) = 0 эквивалентно вычислению верхней границы b_{lo - inv} значений положительных корнейуравнения р(1/х) = 0 с последующим обращением, т.е. b_lo := 1/b_lo-inv.] Положив a_i := b, b >= 1, мы должны только выполнить для соответствующего полинома р_ti(х) подстановку х := b + x, для чего потребуется приблизительно столько же времени, что и для под- подстановки х := 1+х; поэтому, пользуясь этим методом, мы экономим огромное количество машинного времени, и (А1) решается за несколько секунд. Подробный алгоритм этого метода представлен ниже.

Отметим, что для всех i мы имеем a_i = [α₃] где α₃ — наименьший положительный корень некоторого полиномиального уравнения. Следовательно, очевидно, что в общем случае, чтобы вычислить [α₃], правило Коши применяется несколько раз; например, чтобы вычислить [5 • 10⁹ + ε] для полинома (А1), его нужно применить 18 раз. Однако, поскольку число применений правила Коши очень мало по сравнению со значением а_i и не может быть предопределено, мы можем безопасно считать, что в нашем обсуждении        b = [α₃]. Эта интерпретация каждого а_i как нижней границы значений положительных корней полинома р(х) = 0 становится более понятной, если мы примем во внимание, что наша цель положительных корней внутрь интервала (0,1), а все остальные —внутрь интервала (1,∞) или наоборот. Следующие леммы существенны для дальнейшего.

Лемма 1. Пусть р(х) = 0 — полиномиальное уравнение степени d >= 2 от одной неизвестной с целыми коэффициентами и без кратных корней, имеющее р вещественных корней внутри  интервала (0,1), 2 <= р <= d, и пусть ∆_p > 0 — наименьшее расстояние между любыми двумя из этих корней. Тогда инверсия х := 1/х, примененная к р(х) = 0, отображает эти р корней в интервал(1,∞), где теперь наименьшее расстояние между любыми двумя корнями равно     ∆'_p > ∆_p.

Доказательство. Пусть 0 < α₁ < ••• < α_i < α_j < ••• < α_m < α_n < ••• < α_p < 1 суть р корней уравнения р(х) = 0 внутри интервала (0,1), и предположим, что  ∆_p = α_j - α_i, в то время как ∆'_p = 1/α_m - 1/α„. Поскольку ∆'_p = (α„ – α_m)/α_mα„ > α_n -  α_m >=α_j – α_i = ∆_p, лемма доказана.

Лемма 2. Пусть р(х) = 0 — полиномиальное уравнение степени d >= 2 от одной неизвестной с целыми коэффициентами и без кратных корней, имеющее два комплексно-сопряженных корня α₁ и α₂ внутри круга с центром (1/2,0) и радиусом 1/2; более того, пусть δ_p = |α₁ — α₂|. Тогда инверсия х := 1/х, примененная к уравнению р(х) = 0, отображает α₁ и α₂ в полуплоскость с вещественной частью > 1, где теперь расстояние между ними δ_p'>δ_p.

Доказательство аналогично предыдущему.

 

 

 

 

 

 

 

 

 

3. Различия между  двумя методами цепных дробей

Ниже мы продолжаем уточнять различия между двумя методами цепных дробей для отделения вещественных корней полиномиального уравнения. Рассмотрим бесконечное двоичное дерево, с каждой вершиной которого мы ассоциируем тройку вида {рм(x),М(х),vm}, где полином рм(x) получен из исходного полинома р(х) подстановкой х :— М(х) = (а₁х + a₀)/(b₁x + b₀) и vм — число перемен знаков в последовательности коэффициентов полинома рм(х). [Необходимо ассоциировать с каждым преобразованным полиномом соответствующую функцию М(х) так, чтобы в конце мы могли легко получить изолирующие интервалы корней.] Если р(х) = 0 — исходное полиномиальное уравнение с v переменами знаков в последовательности коэффициентов, то корень дерева соответствует тройке {рм(х) := p(х), М(х) := х, vм := v]. Путь от каждой вершины к правому потомку соответствует подстановке х := 1 + х, в то время как путь к левому потомку соответствует подстановке х := 1/(1 + х); отметим, что для любого неполного частного a_i ряд а_i последовательных подстановок вида х := 1 + х, за которыми следует х := 1/(1 + х), эквивалентен подстановке х := a_i + 1/x, за которой следует х := 1 + х. Все вершины, принадлежащие какому-либо пути, конечному или бесконечному, будут рассматриваться как элементы непересекающихся множеств трех типов. Множество типа V₀, V₁ или V_n содержит вершины, соответствующие полиномам с нулем, одной или несколькими переменами знаков соответственно. Множества типов V₀ или V₁называются терминальными множествами. В случае множеств, принадлежащих одному и тому же пути, говорят, что множество X предшествует множеству Y, если и только если для всех х в X и всех у в Y длина пути(х)<длина пути(у). В терминальном множестве вершина, связанная кратчайшим путем с корнем, будет называться терминальной вершиной или терминальным узлом. С учетом этих определений различие между двумя методами цепных дробей для отделения вещественных корней полиномиального уравнения показано на рис. 1.

p(x) = 0

x:=1 + x

(a_i:= a_i + 1)

 

 

 

(a_i:= b)x:=b+x              V₁ – терминальный узел

Рис. 1

Геометрическая интерпретация двух различных способов вычисления значения некоторого а_i (длины ветви).

Гипотеза. Пусть р(х) = с_nхⁿ + ••• + c₁x + с₀ = 0 — полиномиальное уравнение степени n > 1 с рациональными коэффициентами и без кратных корней, соответствующее корню двоичного дерева. Предположим, кроме того, что подстановка

x:= a₁ + ^{_____________1_______________}

          a₂ + ^{_________1________________}

                               ^{. . . . .}

                              + ^{_____1_______}

                                                              a_h +

где a₁ — произвольное неотрицательное целое число, а а₂, ... ,а_h, 1 <= h <= m, — положительные целые элементы, преобразует уравнение р(х) = 0 в новое уравнение, соответствующее терминальному узлу типа или V₀ или V₁. Тогда для всех k, 1 <= k <= h, мы имеем а_k = O[|p(x)|_∞].    (А2)

4. Обсуждение

Экспоненциальность методов непрерывных дробей обусловлена одной или обеими из следующих двух причин : (а) числом подстановок вида х ← х + 1, которые нужно выполнить для вычисления неполного частного а_i и (b) увеличением размера целых коэффициентов полиномов, получающихся после подстановок вида х ← х + а_i.                                                                             Метод непрерывных дробей Винсента 1836 г. экспоненциален как по (а), так и по (b), в то время как метод непрерывных дробей автора 1978 г. теоретически экспоненциален только из-за возрастания размера целых коэффициентов, т.е., пользуясь правилом Коши, автору удалось исключить экспоненциальность, обусловленную фактором (а). Однако по теореме Кузьмина мы не можем теоретически ограничить размер неполных частных а_i и, следовательно, не можем контролировать рост коэффициентов. Тем не менее, благодаря тому, что (для того, чтобы изолировать корни) мы вычисляем очень мало неполных частных а_i, снова пользуясь теоремой Кузьмина, мы видим, что вероятность больших неполных частных практически равна нулю, и, следовательно, наша гипотеза хорошо обоснована. Суммируя сказанное выше, мы получаем следующий алгоритм, который является единственным алгоритмом с полиномиальным временем работы, использующим цепные дроби.

 

 

 

 

 

 

 

5. Работа алгоритма

Метод цепных дробей 1978 г. для отделения вещественных корней уравнения Вход: p(x) = 0, полиномиальное уравнение с целыми коэффициентами и без кратных корней.                                                                                                  Выход: Изолирующие интервалы вещественных корней полинома р(х) или точные значения корней.

1. [Инициализация] Положить  p_w(x) := р(х); если р_w(0) = 0, то выдать замкнутый интервал [0,0] и положить p_w(х) :— p_w(x)/x; pn-flag := 0; ti-flag := 0; Т := ø и вычислить число v перемен знаков в последовательности коэффициентов полинома p_w(x). [Т — множество определенных выше троек {рм(х), М(x), vм},где М(х) = (а₁х + а₀)/(b₁х + b₀). Если pn-flag = 0, то мы отделяем положительные корни, а если pn-flag = 1, то отделяем отрицательные; ti-flag — флаг сдвига-инверсии.]

2. [v = 0 или v = 1?] Если v = 0 или v = 1, то из правила знаков Кардано-Декарта мы знаем, что у p_w(x) нет положительных корней или есть ровно один положительный корень соответственно; в последнем случае (0,∞) — его изолирующий интервал — подается на выход. В любом из этих случаев подстановки не нужны; если pn-flag = 0, то перейти к шагу 10, иначе выход.

2а. [v > 1] В этой точке нам известно, что v > 1, и p_w(x) требует дальнейшего исследования. Положить рм(х) := p_w(x), М(х) := х, vм := v и перейти к шагу 4.

3. [Проверка завершения] Если Т ≠ ø, то удалить первую тройку {рм(x),М(x),vм} и перейти к шагу 4; если Т = ø и pn-flag = 0, то перейти к шагу 1, иначе выход.

4. [Вычисление b] Пользуясь правилом Коши вычислить нижнюю границу b значений положительных корней полинома рм(x); если b < 1, то перейти к шагу 6.

5. [х := b + х, b >= 1] Положить рм(x) := pм(b + х); М(х) := M(b + х) (vм не меняется). Если рм(0) = 0, то мы нашли (рациональный) корень исходного уравнения, в этом случае вывести замкнутый интервал [а₀/b₀, а₀/b₀] [полученный из соответствующего полинома М(x)] и положить рм(x) := pм(х)/х.

6. [х := 1 + х] Положить v’ := vм; pм₁(х) := рм(1 + x); М1(х) := М(1 + х). Если pм₁(0) = 0, то мы нашли (рациональный) корень исходного уравнения, в этом случае вывести замкнутый интервал [а₀/b₀, а₀/b₀] [полученный из соответствующего полинома М(x)] и положить pм₁(x) := pм₁(x)/x. Перейти к шагу 8.

7. [х := 1/(1 +-х)] Если v’ = vм₁, то выполнять {ti-flag := 0; перейти к шагу 3}. В этой точке нам известно, что v' ≠ vм₁, а это означает наличие корней уравнения рм(x) = 0 в интервале (0,1); положить р_i(x) := рм(1/х), обеспечивая условие lс[р_i(x)] > 0 [в случае необходимости умножить p_i(x) на (-1)]; М_i (x) := M(1/x); pм₁ (x) := p_i(1 + x); М1(х) := М_i (1 + x).

8. [Изменить ti-flag] ti-flag := ti-flag + 1; вычислить vм₁ , число перемен знаков в последовательности коэффициентов поли- полинома pм₁ (x). Как на шаге 2, если vм₁ = 0 или vм₁ = 1, то из правила знаков Кардано-Декарта мы знаем, что у pм₁(x) или нет положительных корней, или есть один положительный корень; в последнем случае вывести его изолирующий интервал, равный (i) (0,a₀/b₀), если a₁ = 0 и b₁ > 0, (ii) (а₀/b₀,∞), если a₁ > 0 и b₁ = 0, и (iii) открытому интервалу с неупорядоченными концевыми точками a₀/b₀, a₁/b₁ в остальных случаях [полученному, конечно, во всех случаях по соответствующей функции М1(x)]. Если vм₁ > 1, то добавить тройку {pм₁(x),M1(x),vм₁} к множеству Т.