Теорема Буданса - Budans theorem

В математике Теорема Будана это теорема для ограничения числа действительных корней многочлена в интервале и вычисления паритет этого числа. Он был опубликован в 1807 г. Франсуа Будан де Буасларан.

Аналогичная теорема была опубликована независимо Жозеф Фурье в 1820 году. Каждая из этих теорем является следствием другой. Утверждение Фурье чаще встречается в литературе XIX века и именуется Фурье, Будан – Фурье, Фурье – Будан, и даже теорема Будана

Оригинальная формулировка Будана используется в быстрых современных алгоритмах для изоляция реального корня многочленов.

Вариант знака

Позволять ${ Displaystyle c_ {0}, c_ {1}, c_ {2}, ldots c_ {k}}$ - конечная последовательность действительных чисел. А изменение знака или же изменение знака в последовательности пара индексов $я < j$ такой, что ${ displaystyle c_ {i} c_ {j} <0,}$ и либо $j = я + 1$ или же ${ displaystyle c_ {k} = 0}$ для всех $k$ такой, что $я < k < j$ .

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

Для изучения действительных корней полинома можно использовать количество вариаций знака нескольких последовательностей. Для теоремы Будана это последовательность коэффициентов. Для Теорема Будана – Фурье., это последовательность значений последовательных производных в точке. За Теорема Штурма это последовательность значений в точке Последовательность Штурма.

Правило знаков Декарта

Все результаты, описанные в этой статье, основаны на правиле знаков Декарта.

Если $п (Икс)$ это одномерный многочлен с действительными коэффициентами обозначим через $# + (п)$ количество его положительных действительных корней, считая с их кратностью,^[1] и по $v (п)$ количество вариаций знака в последовательности его коэффициентов. Декарт Правило знаков утверждает, что

v (п) - # + (п)

является неотрицательным четным числом.

В частности, если $v (п) \leq 1$ , то есть $# + (п) = v (п)$ .

Заявление Будана

Учитывая одномерный многочлен $п (Икс)$ с действительными коэффициентами обозначим через $# (ℓ, р] (п)$ количество реальных корней, считая с их кратностью,^[1] из $п$ в полуоткрытый интервал $(ℓ, р]$ (с $ℓ < р$ действительные числа). Обозначим также через $v час (п)$ количество изменений знака в последовательности коэффициентов полинома $п час (Икс) = п (Икс + час)$ . В частности, есть $v (п) = v 0 (п)$ с обозначениями предыдущего раздела.

Теорема Будана такова:

{ displaystyle v _ { ell} (p) -v_ {r} (p) - #_ {( ell, r]}}

является неотрицательным четным числом.

В качестве ${ displaystyle #_ {( ell, r]}}$ неотрицательно, это означает ${ displaystyle v _ { ell} (p) geq v_ {r} (p).}$

Это обобщение правила знаков Декарта, как если бы кто-то выбрал $р$ достаточно большой, он больше всех реальных корней $п$ , а все коэффициенты при ${ displaystyle p_ {r} (x)}$ положительные, то есть ${ displaystyle v_ {r} (p) = 0.}$ Таким образом ${ displaystyle v_ {0} (p) = v_ {0} (p) -v_ {r} (p),}$ и ${ displaystyle #_ {+} = #_ {(0, r)},}$ что делает правило знаков Декарта частным случаем теоремы Будана.

Что касается правила знаков Декарта, если ${ displaystyle v _ { ell} (p) -v_ {r} (p) leq 1,}$ надо ${ displaystyle #_ {( ell, r]} = v _ { ell} (p) -v_ {r} (p).}$ Это означает, что если ${ displaystyle v _ { ell} (p) -v_ {r} (p) leq 1}$ у одного есть «тест с нулевым корнем» и «тест с одним корнем».

Примеры

1. Учитывая многочлен ${ Displaystyle р (х) = х ^ {3} -7x + 7,}$ и открытый интервал ${ displaystyle (0,2)}$ , надо

{ displaystyle { begin {align} p (x + 0) & = p (x) = x ^ {3} -7x + 7 p (x + 2) & = (x + 2) ^ {3} -7 (x + 2) + 7 = x ^ {3} + 6x ^ {2} + 5x + 1 end {align}}.}

Таким образом, ${ displaystyle v_ {0} (p) -v_ {2} (p) = 2-0 = 2,}$ а теорема Будана утверждает, что многочлен ${ displaystyle p (x)}$ имеет два или ноль действительных корня в открытом интервале ${ displaystyle (0,2).}$

2. С тем же полиномом ${ Displaystyle р (х) = х ^ {3} -7x + 7}$ надо

{ Displaystyle p (x + 1) = (x + 1) ^ {3} -7 (x + 1) + 7 = x ^ {3} + 3x ^ {2} -4x + 1.}

Таким образом, ${ displaystyle v_ {0} (p) -v_ {1} (p) = 2-2 = 0,}$ а теорема Будана утверждает, что многочлен ${ displaystyle p (x)}$ не имеет реального корня в открытом интервале ${ displaystyle (0,1).}$ Это пример использования теоремы Будана в качестве критерия нулевого корня.

Заявление Фурье

Теорема Фурье о полиномиальных действительных корнях, также называемый Теорема Фурье – Будана или же Теорема Будана – Фурье. (иногда просто Теорема Будана) в точности совпадает с теоремой Будана, за исключением того, что для $час = л$ и $р$ , последовательность коэффициентов при $п (Икс + час)$ заменяется последовательностью производных от $п$ в $час$ .

Каждая теорема является следствием другой. Это результат Расширение Тейлора

{ displaystyle p (x) = sum _ {i = 0} ^ { deg p} { frac {p ^ {(i)} (h)} {i!}} (x-h) ^ {i}}

полинома $п$ в $час$ , откуда следует, что коэффициент при $Икс я$ в $п (Икс + час)$ является частным от ${ Displaystyle p ^ {(я)} (ч)}$ к $я!$ , положительное число. Таким образом, последовательности, рассматриваемые в теореме Фурье и в теореме Будана, имеют одинаковое количество вариаций знака.

Эта сильная связь между двумя теоремами может объяснить противоречие приоритетов, которое произошло в 19 веке, и использование нескольких названий для одной и той же теоремы. В современном использовании для компьютерных вычислений теорема Будана обычно предпочтительнее, поскольку последовательности имеют гораздо большие коэффициенты в теореме Фурье, чем в теореме Будана, из-за факторного фактора.

Доказательство

Поскольку каждая теорема является следствием другой, достаточно доказать теорему Фурье.

Итак, рассмотрим многочлен $п (Икс)$ , и интервал $(л, р]$ . Когда значение $Икс$ увеличивается с $л$ к $р$ , количество изменений знака в последовательности производных $п$ может измениться только тогда, когда значение $Икс$ пройти через корень $п$ или одна из его производных.

Обозначим через $ж$ либо многочлен $п$ или любые его производные. Для любого рута $час$ множественности $м$ из $ж$ , этот многочлен хорошо аппроксимируется вблизи $час$ к ${ Displaystyle а (х-ч) ^ {м}}$ для некоторой постоянной $а$ . Более того, для $я = 1, ..., м$ , это $я$ -я производная аппроксимируется ${ displaystyle textstyle a (x-h) ^ {m-i} prod _ {j = 1} ^ {i} (m-j + 1).}$ Отсюда следует, что в последовательности, образованной $ж$ и это $м$ первые производные, есть $м$ варианты знаков для $Икс < час$ и ноль для $Икс \geq час$ .

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

Теперь для $я > 0$ , позволять $час$ быть корнем $я$ th производная ${ displaystyle f = p ^ {(i)}}$ из $п$ , который не является корнем ${ displaystyle p ^ {(i-1)}.}$ Следует рассмотреть два случая. Если кратность $м$ корня $час$ четно, тогда ${ displaystyle f = p ^ {(i)}}$ и ${ Displaystyle p ^ {(я-1)}}$ держать постоянный знак, когда $Икс$ пройти через $час$ . Это означает, что количество знаков вариации в последовательности производных уменьшается на четное число $м$ . С другой стороны, если $м$ странно, ${ displaystyle f = p ^ {(i)}}$ изменения знака на $час$ , пока ${ Displaystyle p ^ {(я-1)}}$ не. Таким образом $м + 1$ вариации знаков. Таким образом, когда $Икс$ пройти через $час$ , количество вариаций знака уменьшается либо $м$ или же $м + 1$ , которые в каждом случае являются неотрицательными четными числами.

История

Проблему подсчета и нахождения действительных корней многочлена начали систематически изучать только в начале 19 века.

В 1807 г. Франсуа Будан де Буасларан открыл способ расширения Правило знаков Декарта - действительно для интервала $(0, +\infty)$ - на любой интервал.^[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. » что переводится в «Опираясь на изложенные им принципы и копируя его доказательства, я нашел новые теоремы, которые собираюсь представить. »

По этой причине в 19 веке теоремы Фурье и Штурма вместе появлялись почти во всех книгах по теории уравнений.

Фурье и Будан оставили открытой проблему уменьшения размера интервалов, в которых ищутся корни, таким образом, чтобы, в конечном итоге, разница между числом вариаций знака была не более единицы, что позволяло удостоверить, что конечные интервалы содержат не более одного корня. каждый. Эта проблема была решена в 1834 году Александром Джозефом Хидульфом Винсентом.^[8] Грубо говоря, Теорема Винсента состоит из использования непрерывные дроби для замены линейных преобразований переменной Будана на Преобразования Мебиуса.

Теорема Будана, Фурье и Винсента канула в лету в конце 19 века. Последний автор, упоминавший эти теоремы до второй половины ХХ века Джозеф Альфред Серре.^[9] Они были снова введены в 1976 году Коллинзом и Акритасом для предоставления в компьютерная алгебра, эффективный алгоритм выделения реальных корней на компьютерах.^[10]

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

внешняя ссылка

О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., "Будан-де-Буасларан", Архив истории математики MacTutor, Сент-Эндрюсский университет.

[mult-1] а ^б Это означает, что корень множественности $м$ считается как $м$ корни.

[nmethode-2] Будан, Франсуа Д. (1807). Nouvelle méthode pour la résolution des équations numériques. Париж: Курсье.

[Fourier-3] Фурье, Жан Батист Жозеф (1820). "Sur l'usage du théorème de Descartes dans la recherche des limit des racines". Bulletin des Sciences, par la Société Philomatique de Paris: 156–165.

[arago-4] а ^б Араго, Франсуа (1859), Биографии выдающихся ученых, Бостон: Ticknor and Fields (английский перевод), стр. 383

[BF-5] Акритас, Алкивиадис Г. (1981). «О споре Будана – Фурье». Бюллетень ACM SIGSAM. 15 (1): 8–10. Дои:10.1145/1089242.1089243.

[Reflections-6] Акритас, Алкивиадис Г. (1982). «Размышления о паре теорем Будана и Фурье». Математический журнал. 55 (5): 292–298. Дои:10.2307/2690097. JSTOR 2690097.

[Sturm-7] 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.

[paper_1834-8] Винсент, Александр Джозеф Хидульф (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.

[Serret-9] Серре, Джозеф А. (1877). Cours d'algèbre supérieure. Том I. Готье-Виллар. С. 363–368.

[10] Коллинз, Г. Э.; Акритас, А. Г. (1976). Изоляция полиномиального действительного корня с использованием правила знаков Декарта. Материалы симпозиума ACM 1976 г. по символическим и алгебраическим вычислениям. С. 272–275.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]