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

Подсчет действительных корней многочлена в интервале

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

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

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

Изменение знака

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

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

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

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

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

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

v ( p ) – # ₊ ( p ) – неотрицательное четное целое число.

В частности, если v ( p ) ≤ 1 , то имеем # ₊ ( p ) = v ( p ) .

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

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

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

${\displaystyle v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}}$— неотрицательное четное целое число.

Так как это неотрицательно, это подразумевает ${\displaystyle \#_{(\ell ,r]}}$ ${\displaystyle v_{\ell }(p)\geq v_{r}(p).}$

Это обобщение правила знаков Декарта, поскольку, если выбрать 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 p(x)=x^{3}-7x+7,}$ ${\displaystyle (0,2)}$

${\displaystyle {\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}}.}$

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

2. С тем же полиномом имеем ${\displaystyle p(x)=x^{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).}$

утверждение Фурье

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История

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

В 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]

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

• Свойства корней полинома
• Алгоритм поиска корня

Ссылки

1. Это означает, что корень кратности m считается как m корней.
2. Будан, Франсуа Д. (1807). Новый метод для решения числовых уравнений. Париж: Курьер.
3. Фурье, Жан Батист Жозеф (1820). «Sur l'usage du theorème de Descartes dans la recherche des limites de racines». Бюллетень наук, Парижское философское общество : 156–165.
4. Араго, Франсуа (1859), Биографии выдающихся ученых, Бостон: Тикнор и Филдс (английский перевод), стр. 383
5. Акритас, Алкивиадис Г. (1981). «О споре Будана и Фурье». Бюллетень ACM SIGSAM . 15 (1): 8–10. дои : 10.1145/1089242.1089243 . S2CID  6086015.
6. Акритас, Алкивиадис Г. (1982). «Размышления о паре теорем Будана и Фурье». Mathematics Magazine . 55 (5): 292–298. doi :10.2307/2690097. JSTOR  2690097.
7. Бенис-Синасер, Хурия (1988). «Два момента в истории теории алгебры Штурма» (PDF) . Revue d'Histoire des Sciences . 41 (2): 99–132 (с. 108). дои : 10.3406/rhs.1988.4093. S2CID  201270382.
8. Винсент, Александр Жозеф Хидульф (1834). «Мемуар о разрешении числовых уравнений». Мемуары Королевского общества наук, сельского хозяйства и искусств, Лилль : 1–34.
9. Серрет, Джозеф А. (1877). Высший курс алгебры. Том I. Готье-Виллар. стр. 363–368.
10. Коллинз, GE ; Акритас, AG (1976). Изоляция действительных корней полиномов с использованием правила знаков Декарта. Труды симпозиума ACM 1976 года по символическим и алгебраическим вычислениям. С. 272–275. doi : 10.1145/800205.806346 .

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

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