Теорема Штурмса - Sturms theorem

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

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

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

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

Теорема

В Штурмовая цепь или же Последовательность Штурма из одномерный многочлен п(Икс) с действительными коэффициентами - это последовательность многочленов ${\displaystyle P_{0},P_{1},\ldots ,}$ такой, что

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

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

Количество вариации знаков в ξ последовательности Штурма п - количество смен знака (без учета нулей) в последовательности действительных чисел

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

Здесь обозначено это количество вариаций знака. V(ξ).

Теорема Штурма утверждает, что если п это многочлен без квадратов, количество различных действительных корней п в полуоткрытый интервал (а, б] является V(а) − V(б) (здесь, а и б настоящие числа такие, что а < б).^[1]

Теорема распространяется на неограниченные интервалы, определяя знак при +∞ полинома как знак его ведущий коэффициент (то есть коэффициент при члене высшей степени). В –∞ знак многочлена - это знак его старшего коэффициента для многочлена четной степени и противоположный знак для многочлена нечетной степени.

В случае многочлена без квадратов, если ни один из а ни б является кратным корнем п, тогда V(а) − V(б) это количество отчетливый настоящие корни п.

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

Пример

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

${\displaystyle {\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}}}$

Остальная часть Евклидово деление из п₀ к п₁ является ${\displaystyle -{\tfrac {3}{16}}x^{2}-{\tfrac {3}{4}}x-{\tfrac {15}{16}};}$ умножая это на −1 мы получаем

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

Следующее деление п₁ к п₂ и умножая остаток на −1, мы получаем

${\displaystyle p_{3}(x)=-32x-64}$.

Теперь разделение п₂ к п₃ и умножая остаток на −1, мы получаем

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

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

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

${\displaystyle V(-\infty )-V(+\infty )=3-1=2,}$

что показывает, что п имеет два настоящих корня.

В этом можно убедиться, отметив, что п(Икс) может быть учтено как (Икс² − 1)(Икс² + Икс + 1), где первый фактор имеет корни −1 и 1, а второй фактор не имеет реальных корней. Это последнее утверждение вытекает из квадратичная формула, а также из теоремы Штурма, которая дает знаковые последовательности (+, –, –) в −∞ и (+, +, –) в +∞.

Обобщение

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

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

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

такой, что

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

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

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

Использование псевдоостаточных последовательностей

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

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

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

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

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

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

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

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

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

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

Заявление

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

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

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

Смотрите также

• Теорема Рауса – Гурвица
• Теорема Гурвица (комплексный анализ)
• Правило знаков Декарта
• Теорема Руше
• Свойства полиномиальных корней
• Теорема Гаусса – Лукаса
• Неравенство Турана

Рекомендации

1. (Басу, Поллак и Рой 2006 )
2. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., «Теорема Штурма», Архив истории математики MacTutor, Сент-Эндрюсский университет.

• Басу, Саугата; Поллак, Ричард; Рой, Мари-Франсуаза (2006). «Раздел 2.2.2». Алгоритмы в реальной алгебраической геометрии (PDF) (2-е изд.). Springer. С. 52–57. ISBN  978-3-540-33098-1.
• Штурм, Жак Шарль Франсуа (1829). "Mémoire sur la résolution des équations numériques". Bulletin des Sciences de Férussac. 11: 419–425.
• Сильвестр, Дж. Дж. (1853 г.). «К теории сизигетических отношений двух рациональных интегральных функций, включающей приложение к теории функций Штурма и теории наибольшей алгебраической общей меры» (PDF). Фил. Пер. R. Soc. Лондон. 143: 407–548. Дои:10.1098 / рстл.1853.0018. JSTOR  108572.
• Томас, Джозеф Миллер (1941). «Теорема Штурма для кратных корней». Национальный математический журнал. 15 (8): 391–394. Дои:10.2307/3028551. JSTOR  3028551. МИСТЕР  0005945.
• Heindel, Ли Э. (1971), "Целочисленные арифметические алгоритмы для полиномиального определения действительного нуля", Proc. SYMSAC '71: 415, Дои:10.1145/800204.806312, МИСТЕР  0300434
• Пантон, Дон Б .; Вердини, Уильям А. (1981). «Программа fortran для применения теоремы Штурма при подсчете внутренней нормы прибыли». J. Financ. Quant. Анальный. 16 (3): 381–388. Дои:10.2307/2330245. JSTOR  2330245.
• Акритас, Алкивиадис Г. (1982). «Размышления о паре теорем Будана и Фурье». Математика. Mag. 55 (5): 292–298. Дои:10.2307/2690097. JSTOR  2690097. МИСТЕР  0678195.
• Петерсен, Пол (1991). «Многомерная теория Штурма». Конспект лекций в комп. Наука. Конспект лекций по информатике. 539: 318–332. Дои:10.1007/3-540-54522-0_120. ISBN  978-3-540-54522-4. МИСТЕР  1229329.
• Яп, Чи (2000). Фундаментальные проблемы алгоритмической алгебры. Oxford University Press. ISBN  0-19-512516-9.
• Rahman, Q. I .; Шмайссер, Г. (2002). Аналитическая теория многочленов. Монографии Лондонского математического общества. Новая серия. 26. Оксфорд: Oxford University Press. ISBN  0-19-853493-0. Zbl  1072.30006.
• Баумоль, Уильям. Экономическая динамика, глава 12, раздел 3, «Качественная информация о настоящих корнях»
• D.G. Хук и П. Р. Макари, "Использование последовательностей Штурма для скобок действительных корней полиномиальных уравнений" в Graphic Gems I (изд. А. Гласснера), Academic Press, стр. 416–422, 1990.