Теорема Винсента

В математике теорема Винсента , названная в честь Александра Жозефа Идульфа Винсента, — это теорема, которая выделяет действительные корни многочленов с рациональными коэффициентами.

Хотя теорема Винсента является основой самого быстрого метода выделения действительных корней многочленов, она была почти полностью забыта, будучи затменной теоремой Штурма ; следовательно, она не появляется ни в одной из классических книг по теории уравнений (XX века), за исключением книги Успенского . Представлены два варианта этой теоремы, а также несколько (цепные дроби и бисекция) методов выделения действительных корней, полученных из них.

Пусть c ₀ , c ₁ , c ₂ , ... — конечная или бесконечная последовательность действительных чисел. Предположим, что l < r и выполняются следующие условия:

1. Если r = l +1, то числа c _l и c _r имеют противоположные знаки.
2. Если r ≥ l +2, то числа c _{l +1} , ..., c _{r −1} равны нулю, а числа c _l и c _r имеют противоположные знаки.

Это называется изменением знака или сменой знака между числами c _l и c _r .

При работе с многочленом p ( x ) от одной переменной число изменений знака p ( x ) определяется как число изменений знака в последовательности его коэффициентов.

Представлены две версии этой теоремы: версия с непрерывными дробями , принадлежащая Винсенту, ^{[1] [2] [3]} и версия с делением пополам, принадлежащая Алесине и Галуцци. ^{[4] [5]}

Если в полиномиальном уравнении с рациональными коэффициентами и без кратных корней произвести последовательные преобразования вида

${\displaystyle x=a_{1}+{\frac {1}{x'}},\quad x'=a_{2}+{\frac {1}{x''}},\quad x''=a_{3}+{\frac {1}{x'''}},\ldots }$

где - любые положительные числа, большие или равные единице, то после ряда таких преобразований полученное преобразованное уравнение либо имеет нулевые изменения знака, либо имеет одно изменение знака. В первом случае нет корня, тогда как во втором случае есть один положительный действительный корень. Кроме того, соответствующий корень предложенного уравнения аппроксимируется конечной цепной дробью: ^{[1] [2] [3]}${\displaystyle а_{1},а_{2},а_{3},\ldots }$

${\displaystyle a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots }}}}}}}$

Более того, если можно найти бесконечно много чисел, удовлетворяющих этому свойству, то корень будет представлен (бесконечной) соответствующей цепной дробью.${\displaystyle а_{1},а_{2},а_{3},\ldots }$

Приведенное выше утверждение является точным переводом теоремы, найденной в оригинальных работах Винсента; ^{[1] [2] [3]} однако для более ясного понимания необходимы следующие замечания:

• Если обозначает многочлен, полученный после n подстановок (и удаления знаменателя), то существует N такое, что для всех либо не имеет изменения знака, либо имеет одно изменение знака. В последнем случае имеет единственный положительный действительный корень для всех .${\displaystyle f_{n}(x)}$${\displaystyle n\geq N}$${\displaystyle f_{n}(x)}$${\displaystyle f_{n}(x)}$${\displaystyle n\geq N}$
• Непрерывная дробь представляет собой положительный корень исходного уравнения, а исходное уравнение может иметь более одного положительного корня. Более того, предполагая , мы можем получить только корень исходного уравнения, который > 1. Чтобы получить произвольный положительный корень, нам нужно предположить, что .${\displaystyle a_{1}\geq 1}$${\displaystyle a_{1}\geq 0}$
• Отрицательные корни получаются путем замены x на − x , в этом случае отрицательные корни становятся положительными.

Пусть p ( x ) — действительный многочлен степени deg( p ), имеющий только простые корни. Можно определить положительную величину δ так, что для каждой пары положительных действительных чисел a , b с , каждый преобразованный многочлен вида${\displaystyle |ba|<\delta }$

${\displaystyle f(x)=(1+x)^{\deg(p)}p\left({\frac {a+bx}{1+x}}\right)}$

1

имеет ровно 0 или 1 вариацию знака. Второй случай возможен тогда и только тогда, когда p ( x ) имеет единственный корень в пределах ( a , b ).

Из уравнения ( 1 ) получается следующий критерий для определения того, имеет ли многочлен корни в интервале ( a , b ):

Выполнить над p ( x ) замену

${\displaystyle x\leftarrow {\frac {a+bx}{1+x}}}$

и подсчитать количество изменений знака в последовательности коэффициентов преобразованного многочлена; это число дает верхнюю границу количества действительных корней p ( x ) внутри открытого интервала ( a , b ). Точнее, количество ρ _ab ( p ) действительных корней в открытом интервале ( a , b ) — с учетом кратностей — многочлена p ( x ) в R [ x ], степени deg( p ), ограничено сверху количеством изменений знака var _ab ( p ), где

${\displaystyle \operatorname {var} _{ab}(p)=\operatorname {var} \left((1+x)^{\deg(p)}p\left({\frac {a+bx}{1+x}}\right)\right),}$

${\displaystyle \operatorname {var} _{ab}(p)=\operatorname {var} _{ba}(p)\geq \rho _{ab}(p).}$

Как и в случае с правилом знаков Декарта , если var _ab ( p ) = 0, то следует, что ρ _ab ( p ) = 0, а если var _ab ( p ) = 1, то следует, что ρ _ab ( p ) = 1.

Частным случаем «теста корней a_b» Алесины–Галуцци является «тест корней 0_1» Будана .

Подробное обсуждение теоремы Винсента, ее расширения, геометрической интерпретации задействованных преобразований и трех различных доказательств можно найти в работе Алесины и Галуцци. ^{[4] [5]} Четвертое доказательство принадлежит Островскому ^[6], который заново открыл частный случай теоремы, сформулированной Обрешковым , ^[7] стр. 81, в 1920–1923 гг.

Для доказательства (обеих версий) теоремы Винсента Алесина и Галуцци показывают, что после ряда преобразований, упомянутых в теореме, многочлен с одним положительным корнем в конечном итоге имеет одну вариацию знака. Чтобы показать это, они используют следующее следствие из теоремы Обрешкова 1920–1923 годов, упомянутой ранее; то есть следующее следствие дает необходимые условия, при которых многочлен с одним положительным корнем имеет ровно одну вариацию знака в последовательности своих коэффициентов; см. также соответствующий рисунок.

Следствие. ( Теорема Обрешкова о конусе или секторе, 1920–1923 ^[7] с. 81): Если действительный многочлен имеет один простой корень x ₀ , а все остальные (возможно, кратные) корни лежат в секторе

${\displaystyle S_{\sqrt {3}}=\left\{x=-\alpha +i\beta \ :\ |\beta |\leq {\sqrt {3}}|\alpha |,\alpha >0\right\}}$

то последовательность ее коэффициентов имеет ровно одно изменение знака.

Рассмотрим теперь преобразование Мёбиуса.

${\displaystyle M(x)={\frac {ax+b}{cx+d}},\qquad a,b,c,d\in \mathbb {Z} _{>0}}$

и три круга, показанные на соответствующем рисунке; ​​предположим, что ⁠ а/с⁠ < ⁠б/г⁠ .

• (Желтый) круг

${\displaystyle \left|x-{\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\right|={\tfrac {1}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

диаметр которого лежит на действительной оси, с конечными точками ⁠а/с⁠ и ⁠б/г⁠ , отображается обратным преобразованием Мёбиуса

${\displaystyle M^{-1}(x)={\frac {dx-b}{-cx+a}}}$

на мнимую ось. Например, точка

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)+{\tfrac {i}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

отображается на точку − i  ⁠г/с⁠ . Внешние точки отображаются на полуплоскость с Re( x ) < 0 .

• Два круга (видны только их синие полумесяцы) с центром

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\pm {\tfrac {i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

и радиус

${\displaystyle {\tfrac {1}{\sqrt {3}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

отображаются обратным преобразованием Мёбиуса

${\displaystyle M^{-1}(x)={\frac {dx-b}{-cx+a}}}$

на линии Im( x ) = ± √ 3 Re( x ) . Например, точка

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)-{\tfrac {3i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

сопоставляется с точкой

${\displaystyle {\tfrac {-d}{2c}}\left(1-i{\sqrt {3}}\right).}$

Внешние точки (те, что находятся за пределами восьмерки) отображаются на секторе.${\displaystyle S_{\sqrt {3}}}$

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

В своих фундаментальных работах ^{[1] [2] [3]} Винсент представил примеры, которые точно показывают, как использовать его теорему для выделения действительных корней многочленов с цепными дробями . Однако полученный метод имел экспоненциальное время вычислений, факт, который математики должны были осознать тогда, как это осознал Успенский ^[8] стр. 136, столетие спустя.

Экспоненциальная природа алгоритма Винсента обусловлена ​​способом вычисления частичных частных a _i (в теореме Винсента). То есть, чтобы вычислить каждое частичное частное a i ₍ то есть, чтобы определить, где корни лежат на оси x ), Винсент использует теорему Будана как «тест на отсутствие корней» ; другими словами, чтобы найти целую часть корня, Винсент выполняет последовательные подстановки вида x ← x +1 и останавливается только тогда, когда многочлены p ( x ) и p ( x +1) различаются по числу изменений знака в последовательности своих коэффициентов (то есть когда число изменений знака p ( x +1) уменьшается).

См. соответствующую диаграмму, где корень лежит в интервале (5, 6). Легко сделать вывод, что если корень находится далеко от начала координат, то нахождение его целой части таким способом занимает много времени, отсюда и экспоненциальная природа метода Винсента. Ниже приведено объяснение того, как этот недостаток преодолевается.

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

Причиной этого стало появление теоремы Штурма в 1827 году, которая решила проблему изоляции действительных корней за полиномиальное время, определив точное число действительных корней, которые имеет многочлен в действительном открытом интервале ( a , b ). Полученный (Штурмов) метод вычисления действительных корней многочленов был единственным широко известным и используемым с тех пор — примерно до 1980 года, когда он был заменен (почти во всех системах компьютерной алгебры ) методами, полученными из теоремы Винсента, самым быстрым из которых был метод Винсента–Акритаса–Стржебонского (VAS). ^[9]

Серрет включил в свою «Алгебру» ^[10] , стр. 363–368, теорему Винсента вместе с ее доказательством и направил всех заинтересованных читателей к работам Винсента за примерами того, как она используется. Серрет был последним автором, упомянувшим теорему Винсента в 19 веке.

В 20 веке теорему Винсента невозможно найти ни в одной книге по теории уравнений; исключением являются лишь книги Успенского ^[8] и Обрешкова ^[7] , где во второй из них приводится только формулировка теоремы.

Именно в книге Успенского [ ^8] Акритас нашел теорему Винсента и сделал ее темой своей докторской диссертации «Теорема Винсента в алгебраических манипуляциях», Университет штата Северная Каролина, США , 1978. Крупным достижением того времени было получение оригинальной статьи Винсента 1836 года, которая ускользнула от Успенского , что привело к большому недоразумению . Оригинальная статья Винсента 1836 года была предоставлена ​​Акритасу благодаря похвальным усилиям (межбиблиотечный абонемент) библиотекаря в библиотеке Университета Висконсин-Мэдисон, США .

Выделение действительных корней многочлена — это процесс нахождения открытых непересекающихся интервалов, таких, что каждый содержит ровно один действительный корень и каждый действительный корень содержится в некотором интервале. Согласно французской математической школе 19 века, это первый шаг в вычислении действительных корней, второй — их приближение с любой степенью точности; причем основное внимание уделяется положительным корням, поскольку для выделения отрицательных корней многочлена p ( x ) замените x на − x ( x ← − x ) и повторите процесс.

Теорему Винсента с непрерывными дробями можно использовать для выделения положительных корней заданного многочлена p ( x ) степени deg( p ). Чтобы увидеть это, представим преобразованием Мёбиуса

${\displaystyle M(x)={\frac {ax+b}{cx+d}},\qquad a,b,c,d\in \mathbb {N} }$

непрерывная дробь, которая приводит к преобразованному многочлену

${\displaystyle f(x)=(cx+d)^{\deg(p)}p\left({\frac {ax+b}{cx+d}}\right)}$

2

с одним изменением знака в последовательности его коэффициентов. Тогда единственный положительный корень f ( x ) (в интервале (0, ∞)) соответствует тому положительному корню p ( x ), который находится в открытом интервале с конечными точками и . Эти конечные точки не упорядочены и соответствуют M (0) и M (∞) соответственно.${\displaystyle {\frac {b}{d}}}$${\displaystyle {\frac {a}{c}}}$

Таким образом, чтобы выделить положительные корни многочлена, все, что нужно сделать, это вычислить — для каждого корня — переменные a , b , c , d соответствующего преобразования Мёбиуса.

${\displaystyle M(x)={\frac {ax+b}{cx+d}}}$

что приводит к преобразованному полиному, как в уравнении ( 2 ), с одним изменением знака в последовательности его коэффициентов.

Важное наблюдение: переменные a , b , c , d преобразования Мёбиуса

${\displaystyle M(x)={\frac {ax+b}{cx+d}}}$

(в теореме Винсента), приводящее к преобразованному полиному — как в уравнении ( 2 ) — с одним изменением знака в последовательности его коэффициентов, может быть вычислено:

• либо с помощью непрерывных дробей , что приводит к методу непрерывных дробей Винсента–Акритаса–Стржебонского (VAS) , ^[9]
• или путем деления пополам , что приводит (среди прочих) к методу деления пополам Винсента–Коллинза–Акритаса (VCA) . ^[11]

«Двусекционная часть» этого важнейшего наблюдения появилась как специальная теорема в работах Алесины и Галуцци. ^{[4] [5]}

Все методы, описанные ниже (см. статью о теореме Будана для их исторического обоснования), должны вычислять (один раз) верхнюю границу ub значений положительных корней рассматриваемого многочлена. Исключением является метод VAS, где дополнительно нижние границы lb должны вычисляться почти на каждом цикле основного цикла. Чтобы вычислить нижнюю границу lb многочлена p ( x ), вычислите верхнюю границу ub многочлена и установите .${\displaystyle x^{\deg(p)}p\left({\frac {1}{x}}\right)}$${\displaystyle lb={\frac {1}{ub}}}$

Превосходные (верхние и нижние) границы значений только положительных корней многочленов были разработаны Акритасом, Стржебонским и Вигкласом на основе предыдущей работы Дору Стефанеску. Они описаны в докторской диссертации П.С. Вигкласа ^[12] и в других местах. ^[13] Эти границы уже были реализованы в системах компьютерной алгебры Mathematica , SageMath , SymPy , Xcas и т.д.

Все три метода, описанные ниже, следуют превосходному изложению Франсуа Булье, ^[14] стр. 24.

Только один метод непрерывных дробей вытекает из теоремы Винсента. Как указано выше, он появился в 1830-х годах, когда Винсент представил в статьях ^{[1] [2] [3]} несколько примеров, показывающих, как использовать его теорему для выделения действительных корней многочленов с непрерывными дробями . Однако полученный метод имел экспоненциальное время вычисления. Ниже приводится объяснение того, как этот метод развивался.

Это второй метод (после VCA), разработанный для обработки экспоненциального поведения метода Винсента.

Метод непрерывных дробей VAS является прямой реализацией теоремы Винсента. Первоначально он был представлен Винсентом с 1834 по 1938 год в работах ^{[1] [2] [3]} в экспоненциальной форме; а именно, Винсент вычислял каждое неполное частное a i _с помощью ряда единичных приращений a _i ← a _i + 1, которые эквивалентны подстановкам вида x ← x + 1.

Метод Винсента был преобразован в форму полиномиальной сложности Акритасом, который в своей докторской диссертации 1978 года ( теорема Винсента в алгебраических манипуляциях , Университет штата Северная Каролина, США) вычислил каждое частичное частное a _i как нижнюю границу lb значений положительных корней многочлена. Это называется идеальной положительной нижней границей корня, которая вычисляет целую часть наименьшего положительного корня (см. соответствующий рисунок). А именно, теперь положим a _i ← lb или, что эквивалентно, выполним подстановку x ← x + lb , которая занимает примерно столько же времени, сколько и подстановка x ← x + 1.

Наконец, поскольку идеальной положительной нижней границы корня не существует, Стржебонский ^[15] ввел в 2005 году замену , всякий раз, когда ; в общем случае и значение 16 было определено экспериментально. Более того, было показано ^[15] , что метод VAS ( непрерывных дробей ) быстрее, чем самая быстрая реализация метода VCA (бисекции), ^[16] факт, который был подтвержден ^[17] независимо; точнее, для полиномов Миньотта высокой степени VAS примерно в 50 000 раз быстрее, чем самая быстрая реализация VCA.${\displaystyle x\leftarrow lb_{вычислено}*x}$${\displaystyle lb_{вычислено}>16}$${\displaystyle lb>lb_{вычислено}}$

В 2007 году Шарма ^[18] опроверг гипотезу об идеальной положительной нижней границе и доказал, что VAS по-прежнему полиномиален по времени.

VAS — это алгоритм по умолчанию для изоляции корней в системах Mathematica , SageMath , SymPy , Xcas .

Для сравнения метода Штурма и VAS используйте функции realroot(poly) и time(realroot(poly)) из Xcas . По умолчанию для выделения действительных корней поли realroot использует метод VAS; для использования метода Штурма напишите realroot(sturm, poly). См. также внешние ссылки на приложение А. Беркакиса для устройств Android, которое делает то же самое.

Вот как работает VAS( p , M ), где для простоты не учтен вклад Стржебонского:

• Пусть p ( x ) — многочлен степени deg( p ) такой, что p (0) ≠ 0. Чтобы выделить его положительные корни, свяжите с p ( x ) преобразование Мёбиуса M ( x ) = x и повторяйте следующие шаги, пока есть пары { p ( x ), M ( x )} для обработки.
• Используйте правило знаков Декарта для p ( x ), чтобы вычислить, если это возможно, (используя число var вариаций знаков в последовательности его коэффициентов) количество его корней внутри интервала (0, ∞). Если корней нет, верните пустой набор, ∅, тогда как если есть один корень, верните интервал ( a , b ), где a = min( M (0), M (∞)), а b = max( M (0), M (∞)); если b = ∞, положим b = ub , где ub — верхняя граница значений положительных корней p ( x ). ^{[12] [13]}
• Если есть два или более изменения знака, правило знаков Декарта подразумевает, что внутри интервала (0, ∞) может быть ноль, один или несколько действительных корней; в этом случае рассмотрим отдельно корни p ( x ), которые лежат внутри интервала (0, 1), от тех, которые лежат внутри интервала (1, ∞). Для 1 необходимо провести специальную проверку.
  • Чтобы гарантировать наличие корней внутри интервала (0, 1), используется идеальная нижняя граница lb ; то есть целая часть наименьшего положительного корня вычисляется с помощью нижней границы ^{[12] [13]} , по значениям положительных корней p ( x ). Если , то выполняется подстановка в p ( x ) и M ( x ), тогда как если используются подстановки x ← x +1 для нахождения целой части корня(ей).${\displaystyle lb_{вычислено}}$${\displaystyle lb_{вычислено}>1}$${\displaystyle x\leftarrow x+lb_{вычислено}}$${\displaystyle lb_{вычислено}\leq 1}$
  • Для вычисления корней внутри интервала (0, 1) выполните замену p ( x ) и M ( x ) и обработайте пару${\displaystyle x\leftarrow {\frac {1}{1+x}}}$

${\displaystyle \left\{(1+x)^{\deg(p)}p\left({\tfrac {1}{1+x}}\right),M({\tfrac {1}{1+x}})\right\},}$

тогда как для вычисления корней в интервале (1, ∞) выполните замену x ← x + 1 на p ( x ) и M ( x ) и обработайте пару { p (1 + x ), M (1 + x )}. Вполне может оказаться, что 1 является корнем p ( x ), и в этом случае M (1) является корнем исходного многочлена, а интервал изоляции сводится к точке.

Ниже приведено рекурсивное представление VAS( p , M ).

ВАШ ( p , M ):

Входные данные : одномерный, свободный от квадратов многочлен степени deg( p ) и преобразование Мёбиуса .${\displaystyle p(x)\in \mathbb {Z} [x],p(0)\neq 0}$

${\displaystyle M(x)={\frac {ax+b}{cx+d}}=x,\qquad a,b,c,d\in \mathbb {N} .}$

Выходные данные : список изолирующих интервалов положительных корней p ( x ).

1 var ← число вариаций знака p ( x ) // Правило знаков Декарта ;2 если  var = 0, то ВОЗВРАТ ∅;3 если  var = 1, то RETURN {( a , b )} // a = min( M (0), M (∞)), b = max( M (0), M (∞)), но если b = ∞, то устанавливаем b = ub , где ub — верхняя граница значений положительных корней p ( x );4 lb ← идеальная нижняя граница положительных корней p ( x );5 если  lb ≥ 1 , то  p ← p ( x + lb ), M ← M ( x + lb );6 п 01 ← ( x + 1) град( п )  п ( ⁠1/х + 1⁠ ), М 01 ← М ( ⁠1/х + 1⁠ ) ​​// Ищем действительные корни в (0, 1);7 м ← М (1) // Является ли 1 корнем?8 p 1∞ ← p ( x + 1), M 1∞ ← M ( x + 1) // Ищем действительные корни в (1, ∞);9 если  p (1) ≠ 0 , то
10 ВОЗВРАТ VAS( p 01 , M 01 ) ∪ VAS( p 1∞ , M 1∞ )11 иначе
12 ВОЗВРАТ VAS( p 01 , M 01 ) ∪ {[ m , m ]} ∪ VAS( p 1∞ , M 1∞ )13 конец

Замечания

• Для простоты вклад Стржебонского не включен.
• В приведенном выше алгоритме с каждым полиномом связано преобразование Мёбиуса M ( x ).
• В строке 1 применяется правило знаков Декарта .
• Если удалить строки 4 и 5 из VAS( p , M ), то полученный алгоритм будет экспоненциальным алгоритмом Винсента.
• Любая замена, выполняемая над многочленом p ( x ), также выполняется над соответствующим преобразованием Мёбиуса M ( x ) (строки 5, 6 и 8).
• Изолирующие интервалы вычисляются с помощью преобразования Мёбиуса в строке 3, за исключением целочисленных корней, вычисляемых в строке 7 (также 12).

Применим метод VAS к p ( x ) = x ³ − 7 x + 7 (обратите внимание: M ( x ) = x ).

VAS( x 3 − 7 x + 7, x )1 var ← 2 // число изменений знака в последовательности коэффициентов p ( x ) = x 3 − 7 x + 74 фунт ← 1 // идеальная нижняя граница — найдена с использованием вычисленного фунта и подстановки(й) x ← x + 15 п ← х 3 + 3 х 2 − 4 х + 1, М ← х + 16 п 01 ← х 3 − х 2 − 2 х + 1, М 01 ← ⁠х + 2/х + 1⁠
7 м ← 18 п 1∞ ← х 3 + 6 х 2 + 5 х + 1, М 1∞ ← х + 210 ВОЗВРАТ VAS( x 3 − x 2 − 2 x + 1, ⁠х + 2/х + 1⁠ ) ​​∪ ВАС( х 3 + 6 х 2 + 5 х + 1, х + 2)

Список интервалов изоляции: { }.

Список пар { p , M } для обработки:

${\displaystyle \left\{\left\{x^{3}-x^{2}-2x+1,{\tfrac {x+2}{x+1}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}.}$

Удалите первый и обработайте его.

ВАС( х 3 - х 2 - 2 х + 1, ⁠х + 2/х + 1⁠ )1 var ← 2 // число изменений знака в последовательности коэффициентов p ( x ) = x 3 − x 2 − 2 x + 14 lb ← 0 // идеальная нижняя граница — найдена с использованием вычисленного lb и подстановки(й) x ← x + 16 п 01 ← х 3 + х 2 − 2 х − 1, М 01 ← ⁠2 х + 3/х + 1⁠
7 м ← ⁠3/2⁠
8 п 1∞ ← х 3 + 2 х 2 − х − 1, М 1∞ ← ⁠х + 3/х + 2⁠
10 ВОЗВРАТ VAS( x 3 + x 2 − 2 x − 1, ⁠2 х + 3/х + 2⁠ ) ​​∪ VAS( х 3 + 2 х 2 - х - 1, ⁠х + 3/х + 2⁠ )

Список интервалов изоляции: { }.

Список пар { p , M } для обработки:

${\displaystyle \left\{\left\{x^{3}+x^{2}-2x-1,{\tfrac {2x+3}{x+2}}\right\},\left\{x^{3}+2x^{2}-x-1,{\tfrac {x+3}{x+2}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}.}$

Удалите первый и обработайте его.

ВАС( х 3 + х 2 - 2 х - 1, ⁠2 х + 3/х + 2⁠ )1 var ← 1 // число изменений знака в последовательности коэффициентов p ( x ) = x 3 + x 2 − 2 x − 13 ВОЗВРАТ {( ⁠3/2⁠ , 2)}

Список интервалов изоляции: {( ⁠3/2⁠ , 2)}.

Список пар { p , M } для обработки:

${\displaystyle \left\{\left\{x^{3}+2x^{2}-x-1,{\tfrac {x+3}{x+2}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}.}$

Удалите первый и обработайте его.

ВАС( х 3 + 2 х 2 - х - 1, ⁠х + 3/х + 2⁠ )1 var ← 1 // число изменений знака в последовательности коэффициентов p ( x ) = x 3 + 2 x 2 − x − 13 ВОЗВРАТ {(1, ⁠3/2⁠ )}

Список интервалов изоляции: {(1, ⁠3/2⁠ ), ( ⁠3/2⁠ , 2)}.

Список пар { p , M } для обработки:

${\displaystyle \left\{\left\{x^{3}+6x^{2}+5x+1,x+2\right\}\right\}.}$

Удалите первый и обработайте его.

ВАШ( х 3 + 6 х 2 + 5 х + 1, х + 2)1 var ← 0 // количество изменений знака в последовательности коэффициентов p ( x ) = x 3 + 6 x 2 + 5 x + 12 ВОЗВРАТ ∅

Список интервалов изоляции: {(1, ⁠3/2⁠ ), ( ⁠3/2⁠ , 2)}.

Список пар { p , M } для обработки: ∅ .

Законченный.

Следовательно, два положительных корня многочлена p ( x ) = x ³ − 7 x + 7 лежат внутри интервалов изоляции (1, ⁠3/2⁠ ) ​​и ( ⁠3/2⁠ , 2) }. Каждый корень можно аппроксимировать (например) путем деления пополам интервала изоляции, в котором он находится, до тех пор, пока разность конечных точек не станет меньше 10 ⁻⁶ ; следуя этому подходу, корни оказываются равными ρ ₁ = 1,3569 и ρ ₂ = 1,69202 .

Существуют различные методы деления пополам, полученные из теоремы Винсента; все они представлены и сравнены в другом месте. ^[19] Здесь описаны два наиболее важных из них, а именно метод Винсента–Коллинза–Акритаса (VCA) и метод Винсента–Алесины–Галуцци (VAG).

Метод Винсента–Алесины–Галуцци (VAG) является самым простым из всех методов, выведенных из теоремы Винсента, но имеет наиболее трудоемкую проверку (в строке 1) для определения того, имеет ли многочлен корни в интересующем интервале; это делает его самым медленным из методов, представленных в этой статье.

Напротив, метод Винсента–Коллинза–Акритаса (VCA) более сложен, но использует более простой тест (в строке 1), чем VAG. Это, наряду с определенными улучшениями ^[16], сделало VCA самым быстрым методом деления пополам.

Это был первый метод, разработанный для преодоления экспоненциальной природы оригинального подхода Винсента, и он имел довольно интересную историю, что касается его названия. Этот метод, который изолирует действительные корни, используя правило знаков Декарта и теорему Винсента, изначально назывался модифицированным алгоритмом Успенского его изобретателями Коллинзом и Акритасом. ^[11] После изучения таких названий, как «метод Коллинза–Акритаса» и «метод Декарта» (слишком запутанно, если принять во внимание статью Фурье ^[20] ), именно Франсуа Булье из Лилльского университета дал ему название метод Винсента–Коллинза–Акритаса (VCA), ^[14] стр. 24, основываясь на том факте, что «метод Успенского» не существует ^[21] и также не существует «метод Декарта». ^[22] Лучшая реализация этого метода принадлежит Руйе и Циммерману, ^[16] и на сегодняшний день это самый быстрый метод деления пополам. Он имеет ту же самую сложность в худшем случае , что и алгоритм Штурма, но почти всегда намного быстрее. Он был реализован в пакете Maple RootFinding .

Вот как работает VCA( p , ( a , b )):

• Дан многочлен p _orig ( x ) степени deg( p ), такой, что p _orig (0) ≠ 0, положительные корни которого должны быть изолированы, сначала вычислите верхнюю границу, ^{[12] [13]} ub для значений этих положительных корней и установите p ( x ) = p _orig ( ub * x ) и ( a , b ) = (0, ub ). Все положительные корни p ( x ) лежат в интервале (0, 1), и между ними и корнями p _orig ( x ), которые все лежат в интервале ( a , b ) = (0, ub ) (см. соответствующий рисунок), существует биекция ; эта биекция выражается как α _{( a , b )} = a + α _(0,1) ( b − a ). Аналогично, существует биекция между интервалами (0, 1) и (0, ub ).

• Повторяйте следующие шаги, пока есть пары { p ( x ),( a , b )} для обработки.
• Используйте " тест 0_1 корней " Будана на p ( x ) для вычисления (используя число var вариаций знаков в последовательности его коэффициентов) числа его корней внутри интервала (0, 1). Если корней нет, верните пустой набор, ∅, а если есть один корень, верните интервал ( a , b ).
• Если есть два или более вариаций знака, то « тест корней 0_1 » Будана подразумевает, что внутри интервала (0, 1) может быть ноль, один, два или более действительных корней. В этом случае разделите его пополам и рассмотрите отдельно корни p ( x ) внутри интервала (0, ⁠1/2⁠ ) ​​— и которые соответствуют корням p _orig ( x ) внутри интервала ( a , ⁠1/2⁠ ( a + b )) из тех, что находятся внутри интервала ( ⁠1/2⁠ , 1) и соответствуют корням p _orig ( x ) внутри интервала ( ⁠1/2⁠ ( a + b ), b ); то есть обработать, соответственно, пары

${\displaystyle \left\{2^{\deg(p)}p({\tfrac {x}{2}}),(a,{\tfrac {1}{2}}(a+b))\right\},\quad \left\{2^{\deg(p)}p({\tfrac {1}{2}}(x+1)),({\tfrac {1}{2}}(a+b),b)\right\}}$

(см. соответствующий рисунок). Вполне может оказаться, что ⁠1/2⁠ является корнем p ( x ), в этом случае ⁠1/2⁠ ( a + b ) является корнем p _orig ( x ), а интервал изоляции сводится к точке.

Ниже приведено рекурсивное представление исходного алгоритма VCA( p , ( a , b )).

VCA ( п , ( а , б ))

Вход : Одномерный, свободный от квадратов многочлен p ( ub * x ) ∈ Z [ x ], p (0) ≠ 0 степени deg( p ), и открытый интервал ( a , b ) = (0, ub ), где ub — верхняя граница значений положительных корней p ( x ). (Все положительные корни p ( ub * x ) находятся в открытом интервале (0, 1)).
Выход : Список изолирующих интервалов положительных корней p ( x )

1 var ← число вариаций знака ( x + 1) deg( p ) p ( ⁠1/х + 1⁠ ) ​​// Тест Будана на наличие 0_1 корней ;2 если  var = 0 , то ВОЗВРАТ ∅;3 если  var = 1 , то ВОЗВРАТ {( a , b )};4 п 0 ⁠1/2⁠ ← 2 градуса( п ) п ( ⁠х/2⁠ ) ​​// Ищем действительные корни в (0, ⁠1/2⁠ );5 м ← ⁠1/2⁠ ( а + б ) // Есть ⁠1/2⁠ корень?6 п ⁠1/2⁠ 1 ← 2 град( п ) п ( ⁠х + 1/2⁠ ) ​​// Ищем действительные корни в ( ⁠1/2⁠ , 1);7 если  р ( ⁠1/2⁠ ) ​​≠ 0 тогда
8 ВОЗВРАТ VCA ( p 0 ⁠1/2⁠ , ( а , м )) ∪ VCA ( п ⁠1/2⁠ 1 , ( м , б ))9 еще
10 ВОЗВРАТ VCA ( p 0 ⁠1/2⁠ , ( а , м )) ∪ {[ м , м ]} ∪ VCA ( п ⁠1/2⁠ 1 , ( м , б ))11 конец

Замечание

• В приведенном выше алгоритме с каждым полиномом связан интервал ( a , b ). Как показано в другом месте, ^[22] стр. 11, преобразование Мёбиуса также может быть связано с каждым полиномом, в этом случае VCA больше похож на VAS.
• В строке 1 применяется « тест корней 0_1 » Будана .

Учитывая многочлен p _orig ( x ) = x ³ − 7 x + 7 и рассматривая в качестве верхней границы ^{[12] [13]} значения положительных корней ub = 4 , аргументы метода VCA равны: p ( x ) = 64 x ³ − 28 x + 7 и ( a , b ) = (0, 4) .

1 var ← 2 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠1/х + 1⁠ ) ​​= 7 х 3 − 7 х 2 − 35 х + 434 п 0 ⁠1/2⁠ ← 64 х 3 − 112 х + 565 м ← 26 п ⁠1/2⁠ 1 ← 64 х 3 + 192 х 2 + 80 х + 87 стр. ( ⁠1/2⁠ ) ​​= 18 ВОЗВРАТ VCA(64 x 3 − 112 x + 56, (0, 2)) ∪ VCA(64 x 3 + 192 x 2 + 80 x + 8, (2, 4))

Список интервалов изоляции: { }.

Список пар { p , I } для обработки:

${\displaystyle \left\{\left\{64x^{3}-112x+56,(0,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Удалите первый и обработайте его.

VCA(64 x 3 − 112 x + 56, (0, 2))1 var ← 2 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠1/х + 1⁠ ) ​​= 56 х 3 + 56 х 2 − 56 х + 84 п 0 ⁠1/2⁠ ← 64 х 3 − 448 х + 4485 м ← 16 п ⁠1/2⁠ 1 ← 64 х 3 + 192 х 2 − 256 х + 647 стр. ( ⁠1/2⁠ ) ​​= 88 ВОЗВРАТ VCA(64 x 3 − 448 x + 448, (0, 1)) ∪ VCA(64 x 3 + 192 x 2 − 256 x + 64, (1, 2))

Список интервалов изоляции: { }.

Список пар { p , I } для обработки:

${\displaystyle \left\{\left\{64x^3-448x+448,(0,1)\right\},\left\{64x^3+192x^2-256x+64,(1,2)\right\},\left\{64x^3+192x^2+80x+8,(2,4)\right\}\right\}.}$

Удалите первый и обработайте его.

VCA(64 x 3 − 448 x + 448, (0, 1))1 var ← 0 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠1/х + 1⁠ ) ​​= 448 х 3 + 896 х 2 + 448 х + 642 ВОЗВРАТ ∅

Список интервалов изоляции: { }.

Список пар { p , I } для обработки:

${\displaystyle \left\{\left\{64x^{3}+192x^{2}-256x+64,(1,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Удалите первый и обработайте его.

VCA(64 x 3 + 192 x 2 − 256 x + 64, (1, 2))1 var ← 2 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠1/х + 1⁠ ) ​​= 64 х 3 − 64 х 2 − 128 х + 644 п 0 ⁠1/2⁠ ← 64 х 3 + 384 х 2 − 1024 х + 5125 м ← ⁠3/2⁠
6 п ⁠1/2⁠ 1 ← 64 х 3 + 576 х 2 − 64 х + 647 стр. ( ⁠1/2⁠ ) ​​= −88 ВОЗВРАТ VCA(64 x 3 + 384 x 2 − 1024 x + 512, (1, ⁠3/2⁠ )) ∪ VCA(64 x 3 + 576 x 2 − 64 x − 64, ( ⁠3/2⁠ , 2))

Список интервалов изоляции: { }.

Список пар { p , I } для обработки:

${\displaystyle \left\{\left\{64x^{3}+384x^{2}-1024x+512,\left(1,{\tfrac {3}{2}}\right)\right\},\left\{64x^{3}+576x^{2}-64x-64,\left({\tfrac {3}{2}},2\right)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Удалите первый и обработайте его.

VCA(64 x 3 + 384 x 2 − 1024 x + 512, (1, ⁠3/2⁠ ))1 var ← 1 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠1/х + 1⁠ ) ​​= 512 х 3 + 512 х 2 − 128 х − 643 ВОЗВРАТ {(1, ⁠3/2⁠ )}

Список интервалов изоляции: {(1, ⁠3/2⁠ )}.

Список пар { p , I } для обработки:

${\displaystyle \left\{\left\{64x^{3}+576x^{2}-64x-64,\left({\tfrac {3}{2}},2\right)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Удалите первый и обработайте его.

VCA(64 x ³ + 576 x ² − 64 x − 64, ( ⁠3/2⁠ , 2))

1 var ← 1 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠1/х + 1⁠ ) ​​= −64 х 3 − 256 х 2 + 256 х + 5123 ВОЗВРАТ {( ⁠3/2⁠ , 2)}

Список интервалов изоляции: {(1, ⁠3/2⁠ ), ( ⁠3/2⁠ , 2)}.

Список пар { p , I } для обработки:

${\displaystyle \left\{\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Удалите первый и обработайте его.

VCA(64 x 3 + 192 x 2 + 80 x + 8, (2, 4))1 var ← 0 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠1/х + 1⁠ ) ​​= 8 х 3 + 104 х 2 + 376 х + 3442 ВОЗВРАТ ∅

Список интервалов изоляции: {(1, ⁠3/2⁠ ), ( ⁠3/2⁠ , 2)}.

Список пар { p , I } для обработки: ∅ .

Законченный.

Следовательно, два положительных корня многочлена p ( x ) = x ³ − 7 x + 7 лежат внутри интервалов изоляции (1, ⁠3/2⁠ ) ​​и ( ⁠3/2⁠ , 2) }. Каждый корень можно аппроксимировать (например) путем деления пополам интервала изоляции, в котором он находится, до тех пор, пока разность конечных точек не станет меньше 10 ⁻⁶ ; следуя этому подходу, корни оказываются равными ρ ₁ = 1,3569 и ρ ₂ = 1,69202 .

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

Вот как работает VAG( p , ( a , b )):

• Для заданного полинома p ( x ) степени deg( p ), такого, что p (0) ≠ 0, положительные корни которого должны быть изолированы, сначала вычислите верхнюю границу ^{[12] [13]} ub для значений этих положительных корней и установите ( a , b ) = (0, ub ). Все положительные корни p ( x ) лежат в интервале ( a , b ).
• Повторяйте следующие шаги, пока есть интервалы ( a , b ), которые необходимо обработать; в этом случае многочлен p ( x ) остается прежним.
• Используйте тест Алесины–Галуцци «a_b roots test» на p ( x ), чтобы вычислить (используя число var вариаций знаков в последовательности его коэффициентов) число его корней внутри интервала ( a , b ). Если корней нет, верните пустой набор, ∅, а если есть один корень, верните интервал ( a , b ).
• Если есть два или более вариаций знака, то "тест корней a_b" Алесины–Галуцци подразумевает, что внутри интервала ( a , b ) может быть ноль, один, два или более действительных корней. В этом случае разделите его пополам и рассмотрите отдельно корни p ( x ) внутри интервала ( a , ⁠1/2⁠ ( a + b )) из тех, что находятся внутри интервала ( ⁠1/2⁠ ( a + b ), b ); то есть обработать, соответственно, интервалы ( a , ⁠1/2⁠ ( а + б )) и ( ⁠1/2⁠ ( a + b ), b ). Вполне может оказаться, что ⁠1/2⁠ ( a + b ) является корнем p ( x ), и в этом случае интервал изоляции сводится к точке.

Ниже приведено рекурсивное представление VAG( p , ( a , b )).

VAG ( p , ( a , b ))
Вход : Одномерный, свободный от квадратов многочлен p ( x ) ∈ Z [ x ], p (0) ≠ 0 степени deg( p ) и открытый интервал ( a , b ) = (0, ub ), где ub — верхняя граница значений положительных корней p ( x ).
Выход : Список изолирующих интервалов положительных корней p ( x ).

1 var ← число вариаций знака ( x + 1) deg( p )  p ( ⁠а + бх/1 + х⁠ ) ​​// Тест корней a_b Алесины–Галуцци;2 если  var = 0 , то ВОЗВРАТ ∅;3 если  var = 1 , то ВОЗВРАТ {( a , b )};4 м ← ⁠1/2⁠ ( a + b ) // Разделим интервал ( a , b ) на две равные части;5 если  p ( m ) ≠ 0 , то
6 ВОЗВРАТ VAG( p , ( a , m )) ∪ VAG( p , ( m , b ))7 иначе
8 ВОЗВРАТ VAG( p , ( a , m )) ∪ {[ m , m ]} ∪ VAG( p , ( m , b ))9 конец

Замечания

• По сравнению с VCA приведенный выше алгоритм чрезвычайно прост; в отличие от него, VAG использует трудоемкий «тест корней a_b» , что делает его намного медленнее, чем VCA. ^[19]
• Как отмечают Алесина и Галуцци, ^[5] стр. 189, существует вариант этого алгоритма, созданный Донато Саэли. Саэли предложил использовать медиану конечных точек вместо их средней точки ⁠1/2⁠ ( a + b ) . Однако было показано ^[19] , что использование медианы конечных точек в целом намного медленнее, чем версия «средней точки».

Учитывая многочлен p ( x ) = x ³ − 7 x + 7 и рассматривая в качестве верхней границы ^{[12] [13]} значения положительных корней ub = 4, аргументы VAG равны: p ( x ) = x ³ − 7 x + 7 и ( a , b ) = (0, 4).

1 var ← 2 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠4 х/х + 1⁠ ) ​​= 43 х 3 − 35 х 2 − 7 х + 74 м ← ⁠1/2⁠ (0 + 4) = 25 п ( м ) = 18 ВОЗВРАТ VAG( x 3 − 7 x + 7, (0, 2)) ∪ VAG( x 3 − 7 x + 7, (2, 4)

Список интервалов изоляции: {}.

Список интервалов для обработки: {(0, 2), (2, 4)}.

Удалите первый и обработайте его.

VAG( х 3 − 7 х + 7, (0, 2))1 var ← 2 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠2 х/х + 1⁠ ) ​​= х 3 − 7 х 2 + 7 х + 74 м ← ⁠1/2⁠ (0 + 2) = 15 п ( м ) = 18 ВОЗВРАТ VAG( x 3 − 7 x + 7, (0, 1)) ∪ VAG( x 3 − 7 x + 7, (1, 2)

Список интервалов изоляции: {}.

Список интервалов для обработки: {(0, 1), (1, 2), (2, 4)}.

Удалите первый и обработайте его.

VAG( х 3 − 7 х + 7, (0, 1))1 var ← 0 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠х/х + 1⁠ ) ​​= х 3 + 7 х 2 + 14 х + 72 ВОЗВРАТ ∅

Список интервалов изоляции: {}.

Список интервалов для обработки: {(1, 2), (2, 4)}.

Удалите первый и обработайте его.

VAG( х 3 − 7 х + 7, (1, 2))1 var ← 2 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠2 х + 1/х + 1⁠ ) ​​= х 3 − 2 х 2 − х + 14 м ← ⁠1/2⁠ (1 + 2) = ⁠3/2⁠
5 п ( м ) = − ⁠1/8⁠
8 ВОЗВРАТ VAG( x 3 − 7 x + 7, (1, ⁠3/2⁠ )) ∪ VAG( x 3 − 7 x + 7, ( ⁠3/2⁠ , 2))

Список интервалов изоляции: {}.

Список интервалов для обработки: {(1, ⁠3/2⁠ ), ( ⁠3/2⁠ , 2), (2, 4)}.

Удалите первый и обработайте его.

VAG( х 3 − 7 х + 7, (1, ⁠3/2⁠ ))1 var ← 1 // число изменений знака в последовательности коэффициентов 2 3 ( x + 1) 3 p ( ⁠⁠3/2⁠ х + 1/х + 1⁠ ) ​​= х 3 + 2 х 2 − 8 х − 83 ВОЗВРАЩЕНИЕ (1, ⁠3/2⁠ )

Список интервалов изоляции: {(1, ⁠3/2⁠ )}.

Список интервалов для обработки: {( ⁠3/2⁠ , 2), (2, 4)}.

Удалите первый и обработайте его.

VAG( х 3 − 7 х + 7, ( ⁠3/2⁠ , 2))1 var ← 1 // число изменений знака в последовательности коэффициентов 2 3 ( x + 1) 3 p ( ⁠2 х + ⁠3/2⁠/х + 1⁠ ) ​​= 8 х 3 + 4 х 2 − 4 х − 13 ВОЗВРАТ ( ⁠3/2⁠ , 2)

Список интервалов изоляции: {(1, ⁠3/2⁠ ), ( ⁠3/2⁠ , 2)}.

Список интервалов для обработки: {(2, 4)}.

Удалите первый и обработайте его.

VAG( х 3 − 7 х + 7, (2, 4))1 var ← 0 // число изменений знака в последовательности коэффициентов ( x + 1) 3 p ( ⁠4 х + 2/х + 1⁠ ) ​​= 344 х 3 + 376 х 2 + 104 х + 82 ВОЗВРАТ ∅

Список интервалов изоляции: {(1, ⁠3/2⁠ ), ( ⁠3/2⁠ , 2)}.

Список интервалов для обработки: ∅.

Законченный.

Следовательно, два положительных корня многочлена p ( x ) = x ³ − 7 x + 7 лежат внутри интервалов изоляции (1, ⁠3/2⁠ ) ​​и ( ⁠3/2⁠ , 2) }. Каждый корень можно аппроксимировать (например) путем деления пополам интервала изоляции, в котором он находится, до тех пор, пока разность конечных точек не станет меньше 10 ⁻⁶ ; следуя этому подходу, корни оказываются равными ρ ₁ = 1,3569 и ρ ₂ = 1,69202 .

• Свойства корней полинома
• Алгоритм поиска корня
• Формулы Виета
• Метод Ньютона

• Беркакис, Антонис: RealRoots, бесплатное приложение для устройств Android для сравнения метода Штурма и VAS
• https://play.google.com/store/apps/details?id=org.kde.necessitas.berkakis.realroots