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

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

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

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

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

Теорема

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

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

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

Число изменений знака в точке $ξ$ последовательности Штурма числа $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$ знак полинома является знаком его старшего коэффициента для полинома четной степени и противоположным знаком для полинома нечетной степени.

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

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

Пример

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

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

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

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}}

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

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

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

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

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

Обобщение

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

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

P_{0},P_{1},\точки ,P_{м}

такой что

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

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

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

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

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

Чтобы избежать вычислений с рациональными числами , распространенным методом является замена евклидова деления псевдоделением для вычисления наибольших общих делителей многочленов . Это равносильно замене последовательности остатков алгоритма Евклида на последовательность псевдоостатка , причем последовательность псевдоостатка является последовательностью многочленов, такой что существуют константы и такие, что является остатком от евклидова деления на ( Различные виды последовательностей псевдоостатка определяются выбором и обычно выбирается для того, чтобы не вводить знаменатели во время евклидова деления, и является общим делителем коэффициентов полученного остатка; подробности см. в разделе Последовательность псевдоостатка .) Например, последовательность остатков алгоритма Евклида является последовательностью псевдоостатка с для каждого $i$ , а последовательность Штурма многочлена является последовательностью псевдоостатка с и для каждого $i$ . $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$ $a_{i}=1$ $b_{i}=-1$

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

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

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

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

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

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

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

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

Приложение

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

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

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

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

Ссылки

^ abc (Басу, Поллак и Рой 2006)
^ О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. "Теорема Штурма". Архив истории математики Мактьютора . Университет Сент-Эндрюс .
^ (де Моура и Пассмор 2013)

Basu, Saugata; Pollack, Richard ; Roy, Marie-Françoise (2006). "Section 2.2.2". Алгоритмы в реальной алгебраической геометрии (2-е изд.). Springer . стр. 52–57. ISBN 978-3-540-33098-1.
Штурм, Жак Шарль Франсуа (1829). «Мемуар о разрешении числовых уравнений». Бюллетень наук де Ферюссак . 11 : 419–425.
Сильвестр, Дж. Дж. (1853). «О теории сизигических отношений двух рациональных целых функций, включающей приложение к теории функций Штурма и теории наибольшей алгебраической общей меры». Phil. Trans. R. Soc. Lond . 143 : 407–548. doi : 10.1098/rstl.1853.0018 . JSTOR 108572.
Томас, Джозеф Миллер (1941). «Теорема Штурма для кратных корней». National Mathematics Magazine . 15 (8): 391–394. doi :10.2307/3028551. JSTOR 3028551. MR 0005945.
Хайндель, Ли Э. (1971). Целочисленные арифметические алгоритмы для определения полиномиального действительного нуля . Proc. SYMSAC '71 . стр. 415. doi :10.1145/800204.806312. MR 0300434. S2CID 9971778.
de Moura, Leonardo; Passmore, Grant Olney (2013). "Computation in Real Closed Infinitesimal and Transcendental Extensions of the Rationals". Автоматизированная дедукция – CADE-24 . Lecture Notes in Computer Science. Vol. 7898. p. 178-192. doi :10.1007/978-3-642-38574-2_12. ISBN 978-3-642-38573-5. S2CID 9308312.
Panton, Don B.; Verdini, William A. (1981). «Программа на Фортране для применения теоремы Штурма при подсчете внутренних ставок доходности». J. Financ. Quant. Anal . 16 (3): 381–388. doi :10.2307/2330245. JSTOR 2330245. S2CID 154334522.
Акритас, Алкивиадис Г. (1982). «Размышления о паре теорем Будана и Фурье». Math. Mag . 55 (5): 292–298. doi :10.2307/2690097. JSTOR 2690097. MR 0678195.
Pedersen, Paul (1991). "Многомерная теория Штурма". В Mattson, Harold F.; Mora, Teo; Rao, TRN (ред.). Прикладная алгебра, алгебраические алгоритмы и коды исправления ошибок, 9-й международный симпозиум, AAECC-9, Новый Орлеан, Луизиана, США, 7–11 октября 1991 г., Труды . Заметки лекций по информатике. Том 539. Берлин: Springer. стр. 318–332. doi :10.1007/3-540-54522-0_120. ISBN 978-3-540-54522-4. МР 1229329.
Яп, Чи (2000). Фундаментальные проблемы алгоритмической алгебры. Oxford University Press . ISBN 0-19-512516-9.
Рахман, К.И.; Шмайссер, Г. (2002). Аналитическая теория многочленов . Монографии Лондонского математического общества. Новая серия. Том 26. Оксфорд: Oxford University Press . ISBN 0-19-853493-0. Збл 1072.30006.
Баумоль, Уильям. Экономическая динамика , глава 12, раздел 3, «Качественная информация о действительных корнях»
DG Hook и PR McAree, «Использование последовательностей Штурма для заключения в скобки действительных корней полиномиальных уравнений» в Graphic Gems I (ред. A. Glassner), Academic Press, стр. 416–422, 1990.