В математике , то последовательность Штурма из однофакторного полинома р представляет собой последовательность полиномов , ассоциированных с р и ее производной по варианту алгоритма Евклида для многочленов . Теорема Штурма выражает число различных действительных корней из р , расположенного в интервале с точкой зрения числа изменений знаков значений последовательности Штурма в пределах интервала. Применительно к интервалу всех действительных чисел он дает общее количество действительных корней p . [1]
В то время как основная теорема алгебры легко дает общее количество комплексных корней, считая с кратностью , она не дает процедуры для их вычисления. Теорема Штурма подсчитывает количество различных действительных корней и помещает их в интервалы. Разделяя интервалы, содержащие некоторые корни, он может изолировать корни на произвольные небольшие интервалы, каждый из которых содержит ровно один корень. Это дает самый старый алгоритм изоляции действительного корня и алгоритм поиска корня произвольной точности для одномерных многочленов.
Для вычислений над действительными числами теорема Штурма менее эффективна, чем другие методы, основанные на правиле знаков Декарта . Тем не менее, она работает на каждом реальном замкнутом поле , и, следовательно, остается фундаментальным для теоретического изучения вычислительной сложности из разреши и кванторной ликвидации в теории первого порядка действительных чисел.
Последовательность Штурма и теорема Штурма названы в честь Жака Шарля Франсуа Штурма , который открыл теорему в 1829 году. [2]
Теорема
Цепь Штурма или последовательность Штурма из однофакторного полинома P ( х ) с вещественными коэффициентами представляет собой последовательность полиномов такой, что
для i ≥ 1 , где P ' - производная от P , иэто остаток от евклидовой деления из от Длина последовательности Sturm самое большее степень P .
Количество изменений знака в ξ последовательности Штурма для P - это количество изменений знака (без учета нулей) в последовательности действительных чисел.
Это количество изменений знака обозначено здесь V ( ξ ) .
Теорема Штурма утверждает, что если P - многочлен без квадратов , количество различных действительных корней P в полуоткрытом интервале ( a , b ] равно V ( a ) - V ( b ) (здесь a и b являются действительные числа такие, что a < b ). [1]
Теорема распространяется на неограниченные интервалы, определяя знак в + ∞ многочлена как знак его старшего коэффициента (то есть коэффициента при члене наивысшей степени). На –∞ знак многочлена - это знак его старшего коэффициента для многочлена четной степени и противоположный знак для многочлена нечетной степени.
В случае не-бесквадратного полином, если ни , ни Ь является кратным корнем р , то V ( ) - V ( б ) представляет собой количество различных вещественных корней P .
Доказательство теоремы заключается в следующем: когда значение x увеличивается от a до b , оно может пройти через нуль некоторого( i > 0 ); когда это происходит, количество вариаций знакане меняется. Когда x проходит через корень количество вариаций знака уменьшается от 1 до 0. Это единственные значения x, у которых может измениться знак.
Пример
Предположим, мы хотим найти количество корней в некотором диапазоне для многочлена . Так
Остальная часть евклидовой деления из р 0 от р 1 являетсяумножая его на −1, получаем
- .
Затем разделив p 1 на p 2 и умножив остаток на −1 , получим
- .
Разделив теперь p 2 на p 3 и умножив остаток на −1 , получим
- .
Поскольку это константа, на этом завершается вычисление последовательности Штурма.
Чтобы найти количество настоящих корней нужно вычислить последовательности знаков этих многочленов в точках −∞ и ∞ , которые соответственно равны (+, -, +, +, -) и (+, +, +, -, -) . Таким образом
что показывает, что p имеет два действительных корня.
Это можно проверить, отметив, что p ( x ) можно разложить на множители как ( x 2 - 1) ( x 2 + x + 1) , где первый множитель имеет корни -1 и 1 , а второй множитель не имеет действительных корней. Это последнее утверждение вытекает из формулы корней квадратного уравнения , а также из теоремы Штурма, которая дает знаковые последовательности (+, -, -) в точке −∞ и (+, +, -) в точке + ∞ .
Обобщение
Последовательности Штурма были обобщены в двух направлениях. Чтобы определить каждый многочлен в последовательности, Штурм использовал отрицательное значение остатка от евклидова деления двух предыдущих. Теорема остается верной, если заменить отрицательное значение остатка произведением или частным положительной константой или квадратом многочлена. Также полезно (см. Ниже) рассматривать последовательности, в которых второй многочлен не является производной первого.
Обобщенная последовательность Штурма конечная последовательность многочленов с вещественными коэффициентами
такой, что
- градусы убывают после первого: для i = 2, ..., m ;
- не имеет реального корня и не меняет знака рядом с его настоящими корнями.
- если P i ( ξ ) = 0 для 0 < i < m и ξ действительное число, то P i −1 ( ξ ) P i + 1 ( ξ ) <0 .
Последнее условие означает, что два последовательных многочлена не имеют общего действительного корня. В частности, исходная последовательность Штурма является обобщенной последовательностью Штурма, если (и только если) полином не имеет кратного действительного корня (в противном случае первые два полинома его последовательности Штурма имеют общий корень).
При вычислении исходной последовательности Штурма евклидовым делением может случиться так, что вы встретите многочлен с множителем, который никогда не бывает отрицательным, например или же . В этом случае, если продолжить вычисление с полиномом, замененным его частным на неотрицательный множитель, получится обобщенная последовательность Штурма, которую также можно использовать для вычисления числа действительных корней, поскольку доказательство теоремы Штурма все еще применимо ( из-за третьего условия). Иногда это может упростить вычисление, хотя обычно трудно найти такие неотрицательные множители, за исключением четных степеней x .
Использование псевдоостаточных последовательностей
В компьютерной алгебре рассматриваемые полиномы имеют целые коэффициенты или могут быть преобразованы в целые коэффициенты. Последовательность Штурма полинома с целыми коэффициентами обычно содержит многочлены, коэффициенты которых не являются целыми числами (см. Пример выше).
Чтобы избежать вычислений с рациональными числами , общий метод заключается в замене евклидового деления на псевдо-делениях для вычисления полиномиальных наибольших общих делителей . Это равносильно замене последовательности остатка от алгоритма Евклида с помощью последовательности псевдо-остатка , последовательность оставшейся псевдо быть последовательность многочленов таких, что существуют константы а также такой, что остаток от евклидова деления от (Различные виды последовательностей псевдоостаточных остатков определяются выбором а также как правило, выбрано, чтобы не вводить знаменатели во время евклидова деления, и - общий делитель коэффициентов полученного остатка; подробности см. в разделе Псевдоостаточная последовательность .) Например, остаточная последовательность алгоритма Евклида представляет собой последовательность псевдоостаточных остатков сдля каждого i , а последовательность Штурма полинома является псевдоостаточной последовательностью с а также для каждого i .
Различные последовательности псевдоостаточных остатков были разработаны для вычисления наибольших общих делителей многочленов с целыми коэффициентами без введения знаменателей (см. Последовательность псевдоостаточных чисел ). Все они могут быть превращены в обобщенные последовательности Штурма, выбрав знак быть противоположным знаку Это позволяет использовать теорему Штурма с последовательностями псевдоостаточных остатков.
Изоляция корня
Для полинома с действительными коэффициентами изоляция корня состоит в нахождении для каждого действительного корня интервала, который содержит этот корень и никаких других корней.
Это полезно для поиска корня , позволяя выбрать корень и обеспечивая хорошую отправную точку для быстрых численных алгоритмов, таких как метод Ньютона ; это также полезно для подтверждения результата, так как если метод Ньютона сходится за пределами интервала, можно сразу сделать вывод, что он сходится к неправильному корню.
Изоляция корня также полезна для вычислений с алгебраическими числами . Для вычислений с алгебраическими числами общий метод состоит в том, чтобы представить их в виде пары многочлена, для которого алгебраическое число является корнем, и интервала изоляции. Например может быть однозначно представлена
Теорема Штурма предоставляет способ выделения действительных корней, который менее эффективен (для многочленов с целыми коэффициентами), чем другие методы, использующие правило знаков Декарта . Однако в некоторых случаях он остается полезным, в основном для теоретических целей, например для алгоритмов реальной алгебраической геометрии, которые включают бесконечно малые величины .
Для выделения настоящих корней начинают с интервала содержащий все действительные корни или интересующие корни (часто, как правило, в физических задачах, интересны только положительные корни), и вычисляется а также Для определения этого начального интервала можно использовать границы размера корней (см. Свойства корней полинома § Границы (комплексных) корней полинома ). Затем этот интервал делится на два, выбирая c в середине Расчет обеспечивает количество настоящих корней в а также и можно повторить ту же операцию на каждом подынтервале. Когда во время этого процесса встречается интервал, не содержащий корня, он может быть исключен из списка интервалов для рассмотрения. Когда встречается интервал, содержащий ровно один корень, его можно перестать делить, так как это интервал изоляции. В конечном итоге процесс останавливается, когда остаются только изолирующие интервалы.
Этот процесс выделения может использоваться с любым методом для вычисления числа действительных корней в интервале. Теоретический анализ сложности и практический опыт показывают, что методы, основанные на правиле знаков Декарта , более эффективны. Отсюда следует, что в настоящее время последовательности Штурма редко используются для изоляции корней.
Заявление
Обобщенные последовательности Штурма позволяют подсчитывать корни многочлена, где другой многочлен положительный (или отрицательный), без явного вычисления этих корней. Если известен изолирующий интервал для корня первого многочлена, это позволяет также найти знак второго многочлена в этом конкретном корне первого многочлена без вычисления лучшего приближения корня.
Пусть P ( x ) и Q ( x ) - два полинома с действительными коэффициентами, такие, что P и Q не имеют общего корня, а P не имеет кратных корней. Другими словами, P и P ' Q - взаимно простые многочлены . Это ограничение не влияет на общность дальнейшего, поскольку вычисления GCD позволяют свести общий случай к этому случаю, а стоимость вычисления последовательности Штурма такая же, как и для GCD.
Пусть W ( ) обозначает число вариаций знака при обобщенной последовательности Sturm , начиная с 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 c ( Басу, Поллак и Рой, 2006 )
- ^ О'Коннор, Джон Дж .; Робертсон, Эдмунд Ф. , "Теорема Штурма" , Архив истории математики 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. DOI : 10,1098 / rstl.1853.0018 . JSTOR 108572 .
- Томас, Джозеф Миллер (1941). «Теорема Штурма для кратных корней». Национальный математический журнал . 15 (8): 391–394. DOI : 10.2307 / 3028551 . JSTOR 3028551 . Руководство по ремонту 0005945 .
- Heindel, Lee E. (1971), "Целочисленные арифметические алгоритмы для полиномиального определения действительного нуля", Proc. SYMSAC '71 : 415, DOI : 10,1145 / 800204,806312 , МР 0300434
- Пантон, Дон Б .; Вердини, Уильям А. (1981). «Программа fortran для применения теоремы Штурма при подсчете внутренней нормы прибыли». J. Financ. Quant. Анальный . 16 (3): 381–388. DOI : 10.2307 / 2330245 . JSTOR 2330245 .
- Акритас, Алкивиадис Г. (1982). «Размышления о паре теорем Будана и Фурье». Математика. Mag . 55 (5): 292–298. DOI : 10.2307 / 2690097 . JSTOR 2690097 . Руководство по ремонту 0678195 .
- Петерсен, Пол (1991). «Многомерная теория Штурма». Конспект лекций в комп. Наука . Конспект лекций по информатике. 539 : 318–332. DOI : 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. Zbl 1072.30006 .
- Баумоль, Уильям. Экономическая динамика , глава 12, раздел 3, «Качественная информация о реальных корнях»
- Д.Г. Хук и П.Р. Макари, «Использование последовательностей Штурма для скобок действительных корней полиномиальных уравнений» в Graphic Gems I (редактор А. Гласснера), Academic Press, стр. 416–422, 1990.