Теорема Будана

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

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

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

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

Позволять $c_{0},c_{1},c_{2},\ldots c_{k}$ быть конечной последовательностью действительных чисел. Изменение знака или смена знака в последовательности — это пара индексов $i < j$ такая, что $c_{i}c_{j}<0,$ и либо $j = i + 1$ , либо $c_{k}=0$ для всех $k$ таких, что $i < k < j$ .

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

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

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

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

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

v (p) - # + (p)

— неотрицательное четное целое число.

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

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

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

Теорема Будана заключается в следующем:

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

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

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

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

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

Примеры

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

{\begin{aligned}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{aligned}}.

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

2. С тем же полиномом $p(x)=x^{3}-7x+7$ у одного есть

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

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

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

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

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

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

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

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

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

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

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

Позволять $n$ быть степенью $f$ , так что $f,f',...,f^{(n-1)}$ являются непостоянными полиномами, $f^{(n)}$ является ненулевой константой, и $f^{(n+1)},...$ все тождественно равны нулю.

В качестве функции $t,$ вариант знака $v_{t}(f)$ может изменяться только в корне хотя бы одного из $f,f',...,f^{(n-1)}.$

Если $v_{t}(f)$ варьируется в $t=r$ , то для некоторых $k$ , $f^{(k)}(x)$ имеет корень в $t$ , и каждый из $f,f',...,f^{(k-1)}$ не имеет корня в $t$ .

Если $k=0$ , затем $f(x)=(x-r)^{s}p(x-r)$ для некоторых $s\geq 1$ и некоторый полином $p$ это удовлетворяет $p(0)\neq 0$ . Явно вычисляя $f,f',...,f^{(n)}$ в $r$ и $r-\epsilon$ для маленького $\epsilon$ , у нас есть $v_{r}(f)=v_{r-\epsilon }(f)-s-2s',\quad \exists s'\geq 0.$

В этом уравнении член $-s$ происходит из-за признаков $f,f',...,f^{(s)}$ изменение с $(-1)^{s}\operatorname {sign} (p(0)),(-1)^{s-1}\operatorname {sign} (p(0)),...,-\operatorname {sign} (p(0)),\operatorname {sign} (p(0))$ к $0,0,...,0,\operatorname {sign} (p(0))$ . Термин $-2s',\quad \exists s'\geq 0$ Это связано с тем, что знаки высших производных могут стать равными нулю.

Если $k\geq 1$ , то, поскольку некоторые производные обнуляются при $r$ , но оба $f^{(k-1)}(x)$ и $f^{(n)}(x)$ остаются ненулевыми, мы теряем только четное количество смен знака:

$v_{r}(f)=v_{r-\epsilon }(f)-2s',\quad \exists s'\geq 0$

Если $v_{t}(f)$ варьируется в $t=l$ , то рассуждая аналогично, находим, что для обоих случаев можно взять небольшую $\epsilon$ такой, что $v_{l+\epsilon }(f)=v_{l}(f)$ .

История

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

В 1807 году Франсуа Будан де Буалоран открыл метод распространения правила знаков Декарта , действующего для интервала $(0, +\infty)$ , на любой интервал. ^{[ 2 ]}

Жозеф Фурье опубликовал аналогичную теорему в 1820 году. ^{[ 3 ]} над которым он работал более двадцати лет. ^{[ 4 ]}

Из-за сходства между двумя теоремами возник спор о приоритетах: ^{[ 5 ]}^{[ 6 ]} несмотря на то, что обе теоремы были открыты независимо. ^{[ 4 ]} Обычно именно формулировка и доказательство Фурье использовались в XIX веке в учебниках по теории уравнений .

Использование в 19 веке

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

Хотя теорема Штурма не основана на правиле знаков Декарта , теоремы Штурма и Фурье родственны не только использованием числа вариаций знака последовательности чисел, но и схожим подходом к проблеме. Сам Штурм признал, что его вдохновили методы Фурье: ^{[ 7 ]} «Опираясь на изложенные им принципы и подражая его доказательствам, я нашел новые теоремы, которые собираюсь сформулировать. » что переводится как «Опираясь на изложенные им принципы и подражая его доказательствам, я нашел новые теоремы, которые собираюсь представить». »

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

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

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

См. также

Ссылки

^ Jump up to: ^а ^б Это означает, что корень кратности $m$ считается $m$ корней.
^ Будан, Франсуа Д. (1807). Новый метод решения численных уравнений . Париж: Курьер.
^ Фурье, Жан Батист Жозеф (1820). «Об использовании теоремы Декарта при поиске пределов корней» . Бюллетень наук Парижского филоматического общества : 156–165.
^ Jump up to: ^а ^б Араго, Франсуа (1859), Биографии выдающихся ученых , Бостон: Тикнор и Филдс (английский перевод), стр. 383
^ Акритас, Алкивиадис Г. (1981). «О споре Будана и Фурье» . Бюллетень ACM SIGSAM . 15 (1): 8–10. дои : 10.1145/1089242.1089243 . S2CID 6086015 .
^ Акритас, Алкивиадис Г. (1982). «Размышления о паре теорем Будана и Фурье». Журнал «Математика» . 55 (5): 292–298. дои : 10.2307/2690097 . JSTOR 2690097 .
^ Бенис-Синасер, Хурия (1988). «Два момента в истории алгебраической теоремы Ч. Ф. Штурма» (PDF) . Журнал истории науки . 41 (2): 99–132 (с. 108). дои : 10.3406/rhs.1988.4093 . S2CID 201270382 .
^ Винсент, Александр Жозеф Хидульф (1834). «Память при решении числовых уравнений» . Мемуары Королевского общества наук, сельского хозяйства и искусств Лилля : 1–34.
^ Серре, Джозеф А. (1877). Высший курс алгебры. Том I. Готье-Виллар. стр. 363–368.
^ Коллинз, Джорджия ; Акритас, АГ (1976). Полиномиальная изоляция действительного корня с использованием правила знаков Декарта . Материалы симпозиума ACM 1976 года по символьным и алгебраическим вычислениям. стр. 272–275. дои : 10.1145/800205.806346 .

Внешние ссылки

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

[mult-1] Jump up to: ^а ^б Это означает, что корень кратности $m$ считается $m$ корней.

[nmethode-2] Будан, Франсуа Д. (1807). Новый метод решения численных уравнений . Париж: Курьер.

[Fourier-3] Фурье, Жан Батист Жозеф (1820). «Об использовании теоремы Декарта при поиске пределов корней» . Бюллетень наук Парижского филоматического общества : 156–165.

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

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

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

[Sturm-7] Бенис-Синасер, Хурия (1988). «Два момента в истории алгебраической теоремы Ч. Ф. Штурма» (PDF) . Журнал истории науки . 41 (2): 99–132 (с. 108). дои : 10.3406/rhs.1988.4093 . S2CID 201270382 .

[paper_1834-8] Винсент, Александр Жозеф Хидульф (1834). «Память при решении числовых уравнений» . Мемуары Королевского общества наук, сельского хозяйства и искусств Лилля : 1–34.

[Serret-9] Серре, Джозеф А. (1877). Высший курс алгебры. Том I. Готье-Виллар. стр. 363–368.

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]