В математике теорема Будана - это теорема для ограничения количества действительных корней многочлена в интервале и вычисления четности этого числа. Он был опубликован в 1807 году Франсуа Буданом де Буаслореном .
Подобная теорема была независимо опубликована Джозефом Фурье в 1820 году. Каждая из этих теорем является следствием другой. Утверждение Фурье чаще встречается в литературе XIX века и упоминается как теорема Фурье , Будана – Фурье , Фурье – Будана и даже теорема Будана.
Оригинальная формулировка Будана используется в быстрых современных алгоритмах для выделения действительных корней многочленов.
Вариант знака
Позволять - конечная последовательность действительных чисел. Изменение знака или знака изменения в последовательности является пара индексов я < J таким образом, чтои либо j = i + 1, либодля всех k таких, что i < k < j .
Другими словами, изменение знака происходит в последовательности в каждом месте смены знаков при игнорировании нулей.
Для изучения действительных корней полинома можно использовать количество вариаций знака нескольких последовательностей. Для теоремы Будана это последовательность коэффициентов. Для теоремы Будана – Фурье это последовательность значений последовательных производных в точке. Для теоремы Штурма это последовательность значений в точке последовательности Штурма .
Правило знаков Декарта
Все результаты, описанные в этой статье, основаны на правиле знаков Декарта.
Если p ( x ) - одномерный многочлен с действительными коэффициентами, обозначим через # + ( p ) количество его положительных вещественных корней, считая их кратностью, [1] и через v ( p ) количество изменений знака в последовательность его коэффициентов. Правило знаков Декарта утверждает, что
- v ( p ) - # + ( p ) - неотрицательное четное число.
В частности, если v ( p ) ≤ 1 , то # + ( p ) = v ( p ) .
Заявление Будана
Для одномерного многочлена p ( x ) с действительными коэффициентами обозначим через # ( ℓ , r ] ( p ) количество действительных корней, подсчитанное с учетом их кратностей, [1] из p в полуоткрытом интервале ( ℓ , г ] (с л < г действительные числа). Обозначим также об ч ( р ) числа вариаций знака в последовательности коэффициентов полинома р ч ( х ) = р ( х + ч ) . в частности , , то v ( p ) = v 0 ( p ) в обозначениях предыдущего раздела.
Теорема Будана такова:
- является неотрицательным четным числом.
В виде неотрицательно, это означает
Это обобщение правила знаков Декарта, так как, если выбрать достаточно большое r , оно будет больше, чем все действительные корни p , и все коэффициенты положительны, то есть Таким образом а также что делает правило знаков Декарта частным случаем теоремы Будана.
Что касается правила знаков Декарта, если надо Это означает, что если у одного есть «тест с нулевым корнем» и «тест с одним корнем».
Примеры
1. Учитывая многочлен и открытый интервал , надо
Таким образом, а теорема Будана утверждает, что многочлен имеет либо два, либо ноль действительных корня в открытом интервале
2. С тем же полиномом надо
Таким образом, а теорема Будана утверждает, что многочлен не имеет реального корня в открытом интервале Это пример использования теоремы Будана в качестве критерия нулевого корня.
Заявление Фурье
Теорема Фурье о полиномиальных действительных корнях , также называемая теоремой Фурье – Будана или теоремой Будана – Фурье (иногда просто теоремой Будана ), в точности совпадает с теоремой Будана, за исключением того, что для h = l и r последовательность коэффициентов при p ( x + h ) заменяется последовательностью производных p в h .
Каждая теорема является следствием другой. Это следует из разложения Тейлора
полинома p в точке h , откуда следует, что коэффициент при x i в p ( x + h ) является частным отпользователя i ! , положительное число. Таким образом, последовательности, рассматриваемые в теореме Фурье и в теореме Будана, имеют одинаковое количество вариаций знака.
Эта сильная связь между двумя теоремами может объяснить спор о приоритетах, который произошел в 19 веке, и использование нескольких названий для одной и той же теоремы. В современном использовании для компьютерных вычислений теорема Будана обычно предпочтительнее, поскольку последовательности имеют гораздо большие коэффициенты в теореме Фурье, чем в теореме Будана, из-за факторного фактора.
Доказательство
Поскольку каждая теорема является следствием другой, достаточно доказать теорему Фурье.
Таким образом, рассмотрим многочлен p ( x ) и интервал ( l , r ] . Когда значение x увеличивается от l до r , количество изменений знака в последовательности производных p может измениться только тогда, когда значение x проходит через корень p или одну из его производных.
Обозначим через f либо многочлен p, либо любую его производную. Для любого корня h кратности m из f этот многочлен хорошо аппроксимируется вблизи h формулойдля некоторой постоянной a . Более того, для i = 1, ..., m его i- я производная аппроксимируется формулойОтсюда следует, что в последовательности, образованной f и ее m первыми производными, есть m вариаций знака для x < h и ноль для x ≥ h .
Это показывает, что когда x увеличивается и проходит через корень из p кратности m , то количество изменений знака в последовательности производной уменьшается на m .
Теперь, для i > 0 , пусть h будет корнем i- й производнойиз p , который не является корнемСледует рассмотреть два случая. Если кратность m корня h четная, то а также сохранять постоянный знак, когда x проходит через h . Это означает, что количество знаков вариации в последовательности производных уменьшается на четное число m . С другой стороны, если m нечетное,меняет знак на h , в то время какне. Таким образом, существует m + 1 вариаций знака. Таким образом, когда x проходит через h , количество вариаций знака уменьшается либо на m, либо на m + 1 , которые в каждом случае являются неотрицательными четными числами.
История
Проблему подсчета и нахождения действительных корней многочлена начали систематически изучать только в начале 19 века.
В 1807 году Франсуа Будан де Буаслорен открыл метод распространения правила знаков Декарта, действительного для интервала (0, + ∞), на любой интервал. [2]
Жозеф Фурье опубликовал аналогичную теорему в 1820 году [3], над которой работал более двадцати лет. [4]
Из-за схожести двух теорем возник спор о приоритете [5] [6], несмотря на то, что эти две теоремы были открыты независимо. [4] В 19 веке в учебниках по теории уравнений использовались в основном формулировка и доказательство Фурье .
Использование в 19 веке
Теоремы Будана и Фурье вскоре стали иметь большое значение, хотя они не решают полностью проблему подсчета числа действительных корней многочлена в интервале. Эта проблема была полностью решена в 1827 году Штурмом .
Хотя теорема Штурма не основана на правиле знаков Декарта , теоремы Штурма и Фурье связаны не только использованием количества вариаций знака в последовательности чисел, но и аналогичным подходом к проблеме. Сам Штурм признал, что вдохновлялся методами Фурье: [7] «C'est en m'appuyant sur les Principes qu'il a posés, et en imitant ses démonstrations, que j'ai Trouvé les nouveaux théorèmes que je vais énoncer. » , Что переводится как « Опираясь на изложенные им принципы и имитируя его доказательства, я нашел новые теоремы, которые собираюсь представить. »
По этой причине в XIX веке теоремы Фурье и Штурма вместе появлялись почти во всех книгах по теории уравнений.
Фурье и Будан оставили открытой проблему уменьшения размера интервалов, в которых ищутся корни, таким образом, чтобы, в конечном итоге, разница между количеством вариаций знака была не больше единицы, что позволяло удостоверять, что конечные интервалы содержат не более одного корня. каждый. Эта проблема была решена в 1834 году Александром Джозефом Хидульфом Винсентом. [8] Грубо говоря, теорема Винсента состоит в использовании цепных дробей для замены линейных преобразований переменной Буданом преобразованиями Мёбиуса .
Теорема Будана, Фурье и Винсента канула в лету в конце 19 века. Последний автор, упоминавший эти теоремы до второй половины 20 века, Джозеф Альфред Серре . [9] Они были снова введены в 1976 году Коллинзом и Акритасом для обеспечения в компьютерной алгебре эффективного алгоритма выделения действительных корней на компьютерах. [10]
Смотрите также
Рекомендации
- ^ a b Это означает, что корень кратности m считается m корнем.
- ^ Будан, Франсуа Д. (1807). Nouvelle méthode pour la résolution of équations numériques . Париж: Курсье.
- ^ Фурье, Жан Батист Жозеф (1820). "Sur l'usage du teorème de Descartes dans la recherche des limit des racines" . Bulletin des Sciences, par la Société Philomatique de Paris : 156–165.
- ^ а б Араго, Франсуа (1859 г.), Биографии выдающихся ученых , Бостон: Тикнор и Филдс (английский перевод), стр. 383
- ^ Акритас, Алькивиадис Г. (1981). «О споре Будана – Фурье». Бюллетень ACM SIGSAM . 15 (1): 8–10. DOI : 10.1145 / 1089242.1089243 .
- ^ Акритас, Алкивиадис Г. (1982). «Размышления о паре теорем Будана и Фурье». Математический журнал . 55 (5): 292–298. DOI : 10.2307 / 2690097 . JSTOR 2690097 .
- ^ Hourya, Benis-Sinaceur (1988). "Deux moment dans l'histoire du Théorème d'algèbre de Ch. F. Sturm" . Revue d'histoire des Sciences . 41 (2): 108.
- ^ Винсент, Александр Джозеф Хидульф (1834). "Mémoire sur la résolution des équations numériques" . Mémoires de la Société Royale des Sciences, de l 'Agriculture et des Arts, Лилль : 1–34.
- ^ Серре, Джозеф А. (1877). Cours d'algèbre supérieure. Фолиант я . Готье-Виллар. С. 363–368.
- ^ Коллинз, GE ; Акритас, AG (1976). Выделение полиномиального действительного корня с использованием правила знаков Декарта . Труды симпозиума ACM 1976 г. по символическим и алгебраическим вычислениям. С. 272–275.
Внешние ссылки
О'Коннор, Джон Дж .; Робертсон, Эдмунд Ф. , "Budan de Boislaurent" , архив истории математики MacTutor , Сент-Эндрюсский университет