Теорема Штурма

В математике последовательность Штурма p одномерного многочлена $—$ это последовательность многочленов, связанных с $p$ и его производной с помощью варианта алгоритма Евклида для многочленов . Теорема Штурма выражает число различных вещественных корней числа $p,$ расположенных на интервале, через число смен знаков значений последовательности Штурма на границах интервала. Применительно к интервалу всех действительных чисел он дает общее количество действительных корней числа $p$ . ^[1]

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

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

Последовательность Штурма и теорема Штурма названы в честь Жака Шарля Франсуа Штурма , открывшего эту теорему в 1829 году. ^[2]

Теорема

Цепочка Штурма или последовательность Штурма одномерного полинома $P (x)$ с действительными коэффициентами - это последовательность полиномов $P_{0},P_{1},\ldots ,$ такой, что

{\begin{aligned}P_{0}&=P,\\P_{1}&=P',\\P_{i+1}&=-\operatorname {rem} (P_{i-1},P_{i}),\end{aligned}}

для $i \geq 1$ , где $P'$ — производная от $P$ , и $\operatorname {rem} (P_{i-1},P_{i})$ является остатком евклидова деления $P_{i-1}$ к $P_{i}.$ степени $P.$ Длина последовательности Штурма не превышает

Число смен знака в точке $ξ$ последовательности Штурма числа $P$ — это количество смен знака (без учета нулей) в последовательности действительных чисел.

P_{0}(\xi ),P_{1}(\xi ),P_{2}(\xi ),\ldots .

Это количество изменений знака обозначено здесь $V (ξ)$ .

Теорема Штурма утверждает, что, если $P$ — многочлен без квадратов , количество различных действительных корней $P$ в полуоткрытом интервале $(a, b]$ равно $V (a) - V (b)$ (здесь $a$ и $b$ суть действительные числа такие, что $a < b$ ). ^[1]

Теорема распространяется на неограниченные интервалы, определяя знак $+\infty$ многочлена как знак его старшего коэффициента (то есть коэффициента члена высшей степени). При $-\infty$ знаком многочлена является знак его старшего коэффициента для многочлена четной степени и противоположный знак для многочлена нечетной степени.

В случае многочлена, не свободного от квадратов, если ни $,$ ни $b$ не являются кратными корнями $p$ , то $V (a) - V (b)$ — это количество различных действительных корней $P.$ a

Доказательство теоремы следующее: когда значение $x$ увеличивается от $a$ до $b$ , оно может проходить через ноль некоторого $P_{i}$ ( $я > 0$ ); когда это происходит, количество изменений знака $(P_{i-1},P_{i},P_{i+1})$ не меняется. Когда $x$ проходит через корень $P_{0}=P,$ количество вариаций знака $(P_{0},P_{1})$ уменьшается от 1 до 0. Это единственные значения $x,$ при которых может меняться какой-либо знак.

Пример

Предположим, мы хотим найти количество корней в некотором диапазоне для многочлена $p(x)=x^{4}+x^{3}-x-1$ . Так

{\begin{aligned}p_{0}(x)&=p(x)=x^{4}+x^{3}-x-1\\p_{1}(x)&=p'(x)=4x^{3}+3x^{2}-1\end{aligned}}

Остаток деления евклидова $p 0$ на $p 1$ равен $-{\tfrac {3}{16}}x^{2}-{\tfrac {3}{4}}x-{\tfrac {15}{16}};$ умножив его на $-1,$ получим

p_{2}(x)={\tfrac {3}{16}}x^{2}+{\tfrac {3}{4}}x+{\tfrac {15}{16}}

.

Затем разделив $p 1$ на $p 2$ и умножив остаток на $-1$ , получим

p_{3}(x)=-32x-64

.

Теперь разделив $p 2$ на $p 3$ и умножив остаток на $-1$ , получим

p_{4}(x)=-{\tfrac {3}{16}}

.

Поскольку это константа, на этом вычисление последовательности Штурма завершается.

Чтобы найти число действительных корней $p_{0}$ необходимо вычислить последовательности знаков этих многочленов в точках $-\infty$ и $\infty$ , которые равны соответственно $(+, -, +, +, -)$ и $(+, +, +, -, -)$ . Таким образом

V(-\infty )-V(+\infty )=3-1=2,

где $V$ обозначает количество смен знака в последовательности, что показывает, что $p$ имеет два вещественных корня.

В этом можно убедиться, заметив, что $p (x)$ можно факторизовать как $(x 2 - 1)(х 2 + x + 1)$ , где первый сомножитель имеет корни $-1$ и $1$ , а второй сомножитель не имеет действительных корней. Это последнее утверждение следует из квадратичной формулы , а также из теоремы Штурма, которая дает последовательности знаков $(+, -, -)$ в $-\infty$ и $(+, +, -)$ в $+\infty$ .

Обобщение

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

Обобщенная последовательность Штурма — это конечная последовательность полиномов с вещественными коэффициентами.

P_{0},P_{1},\dots ,P_{m}

такой, что

степени уменьшаются после первой: $\deg P_{i}<\deg P_{i-1}$ для $i = 2, ..., м$ ;
$P_{m}$ не имеет реального корня или не имеет смены знака вблизи своих реальных корней.
если $P i (ξ) = 0$ для $0 < i < m$ и $ξ$ - действительное число, то $P i -1 (ξ) P i + 1 (ξ) < 0$ .

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

При вычислении исходной последовательности Штурма методом евклидова деления может случиться так, что кто-то встретит многочлен, множитель которого никогда не бывает отрицательным, например $x^{2}$ или $x^{2}+1$ . В этом случае, если продолжить вычисление с заменой многочлена на его частное по неотрицательному множителю, получится обобщенная последовательность Штурма, которую также можно использовать для вычисления количества действительных корней, поскольку доказательство теоремы Штурма все еще применимо ( из-за третьего условия). Иногда это может упростить вычисление, хотя обычно трудно найти такие неотрицательные коэффициенты, за исключением четных степеней $x$ .

Использование последовательностей псевдоостатков

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

Чтобы избежать вычислений с рациональными числами , обычным методом является замена евклидова деления для псевдоделением вычисления наибольших общих делителей полинома . Это равнозначно замене остаточной последовательности алгоритма Евклида последовательностью псевдоостатка , причем псевдоостаточной последовательностью является последовательность $p_{0},\ldots ,p_{k}$ многочленов таких, что существуют константы $a_{i}$ и $b_{i}$ такой, что $b_{i}p_{i+1}$ является остатком евклидова деления $a_{i}p_{i-1}$ к $p_{i}.$ (Различные виды последовательностей псевдоостатков определяются выбором $a_{i}$ и $b_{i};$ обычно, $a_{i}$ выбран для того, чтобы не вводить знаменатели при евклидовом делении, и $b_{i}$ – общий делитель коэффициентов результирующего остатка; см . в разделе «Последовательность псевдоостатка» подробности .)Например, остаточная последовательность алгоритма Евклида представляет собой последовательность псевдоостатка с $a_{i}=b_{i}=1$ для каждого $i$ , а последовательность Штурма многочлена представляет собой последовательность псевдоостатка с $a_{i}=1$ и $b_{i}=-1$ для каждого $я$ .

Различные последовательности псевдоостатков были разработаны для вычисления наибольших общих делителей многочленов с целыми коэффициентами без введения знаменателей (см. Последовательность псевдоостатков ). Все их можно сделать обобщенными последовательностями Штурма, выбрав знак $b_{i}$ быть противоположным знаку $a_{i}.$ Это позволяет использовать теорему Штурма с последовательностями псевдоостатков.

Изоляция корня

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

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

Изоляция корня также полезна для вычислений с алгебраическими числами . Для вычислений с алгебраическими числами общий метод состоит в том, чтобы представить их в виде пары многочлена, корнем которого является алгебраическое число, и интервала изоляции. Например ${\sqrt {2}}$ может быть однозначно представлено $(x^{2}-2,[0,2]).$

Теорема Штурма обеспечивает способ выделения действительных корней, который менее эффективен (для многочленов с целыми коэффициентами), чем другие методы, включающие правило знаков Декарта . Однако в некоторых случаях он остается полезным, в основном для теоретических целей, например, для алгоритмов реальной алгебраической геометрии , в которых используются бесконечно малые числа . ^[3]

Для выделения действительных корней начинают с интервала $(a,b]$ содержащий все действительные корни или интересующие корни (часто, обычно в физических задачах, интересны только положительные корни), и можно вычислить $V(a)$ и $V(b).$ Для определения этого начального интервала можно использовать границы размера корней (см. Свойства полиномиальных корней § Границы (комплексных) полиномиальных корней ). Затем этот интервал делят пополам, выбирая $c$ в середине $(a,b].$ Вычисление $V(c)$ дает количество действительных корней в $(a,c]$ и $(c,b],$ и можно повторить одну и ту же операцию на каждом подинтервале. Если во время этого процесса встречается интервал, не содержащий корня, его можно исключить из списка рассматриваемых интервалов. Когда кто-то встречает интервал, содержащий ровно один корень, его можно прекратить делить, поскольку это интервал изоляции. В конце концов процесс останавливается, когда остаются только изолирующие интервалы.

Этот процесс изоляции можно использовать с любым методом вычисления количества действительных корней в интервале. Теоретический анализ сложности и практический опыт показывают, что методы, основанные на правиле знаков Декарта, более эффективны. Отсюда следует, что в настоящее время последовательности Штурма редко используются для изоляции корней.

Приложение

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

Пусть $P (x)$ и $Q (x)$ — два полинома с действительными коэффициентами, такие что $P$ и $Q$ не имеют общего корня, а $P$ не имеет кратных корней. Другими словами, $P$ и $P'Q многочлены$ — взаимно простые . Это ограничение на самом деле не влияет на общность дальнейшего, поскольку вычисления НОД позволяют свести общий случай к этому случаю, а стоимость вычисления последовательности Штурма такая же, как и для НОД.

Пусть $W (a)$ обозначает количество изменений знака в $точке a$ обобщенной последовательности Штурма, начиная с $и$ P $' Q.$ P Если $a < b$ — два действительных числа, то $W (a) - W (b)$ — это количество корней $P$ в интервале $(a,b]$ такой, что $Q (a) > 0$ минус количество корней в том же интервале, таких что $Q (a) < 0$ . В сочетании с общим количеством корней $P$ в том же интервале, заданном теоремой Штурма, это дает количество корней $P$ таких, что $Q (a) > 0$ , и количество корней $P$ таких, что $Q (a) < 0$ . ^[1]

См. также

Ссылки

^ Jump up to: ^а ^б ^с ( Басу, Поллак и Рой, 2006 г. )
^ О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. «Теорема Штурма» . MacTutor Архив истории математики . Университет Сент-Эндрюс .
^ ( де Моура и Пассмор, 2013 )

Басу, Саугата; Поллак, Ричард ; Рой, Мари-Франсуаза (2006). «Раздел 2.2.2». Алгоритмы реальной алгебраической геометрии (2-е изд.). Спрингер . стр. 52–57. ISBN 978-3-540-33098-1 .
Штурм, Жак Шарль Франсуа (1829). «Память при решении числовых уравнений». Научный бюллетень Ферюссака . 11 : 419–425.
Сильвестр, Джей-Джей (1853). «К теории сизигетических отношений двух рациональных целых функций, включающей приложение к теории функций Штурма и теории наибольшей алгебраической общей меры» . Фил. Пер. Р. Сок. Лонд . 143 : 407–548. дои : 10.1098/rstl.1853.0018 . JSTOR 108572 .
Томас, Джозеф Миллер (1941). «Теорема Штурма для кратных корней». Национальный математический журнал . 15 (8): 391–394. дои : 10.2307/3028551 . JSTOR 3028551 . МР 0005945 .
Хейндель, Ли Э. (1971). Алгоритмы целочисленной арифметики для определения полиномиального действительного нуля . Учеб. СИМСАК '71 . п. 415. дои : 10.1145/800204.806312 . МР 0300434 . S2CID 9971778 .
де Моура, Леонардо; Пассмор, Грант Олни (2013). «Вычисления в реальных замкнутых бесконечно малых и трансцендентных расширениях рациональных чисел» . Автоматизированный вычет – CADE-24 . Конспекты лекций по информатике. Том. 7898. с. 178-192. дои : 10.1007/978-3-642-38574-2_12 . ISBN 978-3-642-38573-5 . S2CID 9308312 .
Пантон, Дон Б.; Вердини, Уильям А. (1981). «Программа на Фортране для применения теоремы Штурма при расчете внутренней нормы доходности». Дж. Финанс. Квант. Анал . 16 (3): 381–388. дои : 10.2307/2330245 . JSTOR 2330245 . S2CID 154334522 .
Акритас, Алкивиадис Г. (1982). «Размышления о паре теорем Будана и Фурье». Математика. Маг . 55 (5): 292–298. дои : 10.2307/2690097 . JSTOR 2690097 . МР 0678195 .
Педерсен, Пол (1991). «Многомерная теория Штурма». В Мэттсоне, Гарольд Ф.; Мора, Тео; Рао, TRN (ред.). Прикладная алгебра, алгебраические алгоритмы и коды, исправляющие ошибки, 9-й международный симпозиум, AAECC-9, Новый Орлеан, Луизиана, США, 7–11 октября 1991 г., Труды . Конспекты лекций по информатике. Том. 539. Берлин: Шпрингер. стр. 318–332. дои : 10.1007/3-540-54522-0_120 . ISBN 978-3-540-54522-4 . МР 1229329 .
Да, Чи (2000). Фундаментальные проблемы алгоритмической алгебры . Издательство Оксфордского университета . ISBN 0-19-512516-9 .
Рахман, QI; Шмайссер, Г. (2002). Аналитическая теория полиномов . Монографии Лондонского математического общества. Новая серия. Том. 26. Оксфорд: Издательство Оксфордского университета . ISBN 0-19-853493-0 . Збл 1072.30006 .
Баумол, Уильям. Экономическая динамика , глава 12, раздел 3, «Качественная информация о реальных корнях»
Д. Г. Хук и П. Р. Макари, «Использование последовательностей Штурма для заключения в скобки действительных корней полиномиальных уравнений» в журнале Graphic Gems I (под ред. А. Гласснера), Academic Press, стр. 416–422, 1990.

[bpr-1] Jump up to: ^а ^б ^с ( Басу, Поллак и Рой, 2006 г. )

[2] О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. «Теорема Штурма» . MacTutor Архив истории математики . Университет Сент-Эндрюс .

[mpi-3] ( де Моура и Пассмор, 2013 )

[1]

[2]

[3]