Теорема Декарта
Теоре́ма Дека́рта о зна́ках (или пра́вило зна́ков Дека́рта) — теорема в алгебре, утверждающая, что число положительных вещественных корней многочлена с вещественными коэффициентами равно числу перемен знаков в ряду его коэффициентов или на чётное число меньше этого числа. Корни считаются с учётом их кратности; нулевые коэффициенты при подсчёте числа перемен знаков игнорируются[1].
Формально, если — число положительных вещественных корней многочлена , а — число перемен знаков в последовательности его ненулевых коэффициентов, то: , где — некоторое целое неотрицательное число ()[2].
Аналогично, рассматривая многочлен , можно с помощью этой же теоремы найти число отрицательных вещественных корней , так как положительные корни в точности соответствуют отрицательным корням .
В качестве примера рассмотрим многочлен . Ряд его коэффициентов: . Перемены знака происходят дважды: с на и с на . Следовательно, . Согласно теореме Декарта, этот многочлен имеет либо 2, либо 0 положительных вещественных корней. Действительно, разложив его на множители: , мы видим, что корни равны . Положительных корней два (корень кратности 2), что в точности совпадает с предсказанием теоремы.
Общие сведения
| Теорема Декарта о знаках | |
|---|---|
| лат. Regula signorum Cartesii | |
| Область использования |
алгебра теория многочленов вычислительная математика |
| Дата появления | 1637 |
История
Правило знаков было впервые сформулировано Рене Декартом в 1637 году в его фундаментальном труде «Геометрия», который был опубликован как приложение к «Рассуждению о методе». Декарт описал правило, однако не привёл его строгого математического доказательства, ограничившись лишь эмпирическим обоснованием и примерами[3][4].
Первое известное строгое доказательство этого правила было дано Исааком Ньютоном в его работе «Универсальная арифметика» (Arithmetica Universalis), опубликованной в 1707 году (хотя сама работа была написана ранее). Доказательство Ньютона опиралось на анализ знаков коэффициентов при делении многочлена на двучлен[5][6].
Важно отметить, что в 1799 году Карл Фридрих Гаусс опубликовал первое полное доказательство основной теоремы алгебры, что создало теоретическую базу для дальнейшего развития методов анализа корней многочленов, включая обобщения правила Декарта[7].
В дальнейшем правило Декарта привлекало внимание многих выдающихся математиков:
- Леонард Эйлер в 1760-х годах дал альтернативное доказательство правила, основанное на разложении многочлена на линейные и квадратичные множители[8].
- Жозеф Луи Лагранж в 1768 году предложил более строгую формулировку и уточнил условия применимости[9].
- В XIX веке правило было существенно обобщено и углублено:
- В 1807—1820 годах Шарль Будан и Жозеф Фурье независимо друг от друга доказали теорему, обобщающую правило Декарта для определения числа корней на произвольном отрезке (см. Теорема Будана — Фурье).
- В 1829 году Жак Штурм предложил алгоритм (цепочка Штурма), позволяющий находить точное число вещественных корней на отрезке[10].
- Огюстен Коши и Карл Якоби в середине XIX века внесли вклад в строгое обоснование правил подсчёта корней.
- В XX веке правило знаков было обобщено на бесконечные степенные ряды в работах Георга Полиа и Годфри Харди.
Связь с теорией матриц
Теорема Декарта тесно связана с задачами линейной алгебры и теории матриц:
- Характеристические многочлены. Для характеристического многочлена симметрической (или эрмитовой) матрицы все корни вещественны, поэтому теорема Декарта даёт точное число положительных и отрицательных собственных значений. Это используется, в частности, в законе инерции Сильвестра[11].
- Неотрицательные матрицы. В теории Перрона — Фробениуса правило знаков помогает анализировать спектральный радиус неотрицательных матриц и оценивать число положительных собственных значений.
- Матрицы с знакопеременными элементами. В теории графов правило знаков применяется к характеристическим многочленам матриц смежности двудольных графов, коэффициенты которых обладают специальной знакопеременной структурой.
- Оценка числа положительных собственных значений. Для произвольной вещественной матрицы теорема Декарта даёт верхнюю оценку числа положительных собственных значений через знаки коэффициентов характеристического многочлена.
Вычислительные аспекты
В современной вычислительной математике правило знаков Декарта лежит в основе нескольких эффективных алгоритмов:
- Алгоритм Винсента — Акмана — Коллинза. Разработанный в 1834 году А. Ж. Винсентом и усовершенствованный в XX веке, этот алгоритм использует правило знаков в комбинации с дробно-линейными преобразованиями Мёбиуса для отделения вещественных корней. Алгоритм реализован в современных системах компьютерной алгебры: Maple, Mathematica, SymPy, SageMath.
- Метод бисекции с правилом знаков. Простейший алгоритм отделения корней: на каждом шаге отрезок делится пополам, и правило знаков применяется к каждому подотрезку. Если на подотрезке , корней там нет; если , там ровно один корень.
- Сравнение с методом Штурма. Алгоритмы на основе правила знаков (особенно алгоритм Винсента) часто превосходят классический метод Штурма по вычислительной эффективности для многочленов высокой степени, так как требуют меньшего числа арифметических операций.
- Сложность. Для многочлена степени с целыми коэффициентами битовой длины алгоритм на основе правила знаков имеет сложность , что сопоставимо с лучшими известными алгоритмами[12].
Обобщения
Правило знаков Декарта имеет несколько важных обобщений:
Теорема Будана — Фурье
Теорема Будана — Фурье обобщает правило Декарта на произвольный отрезок . Число вещественных корней многочлена на равно , где — число перемен знаков в последовательности , а — целое число. При эта теорема сводится к классическому правилу Декарта[13].
Обобщение Лагерра
Эдмон Лагерр в 1883 году предложил обобщение, учитывающее не только перемены знаков, но и «пропуски» в последовательности коэффициентов, что даёт более точные оценки в ряде случаев.
Обобщение на степенные ряды
В работах Г. Полиа и Г. Харди правило знаков было распространено на сходящиеся степенные ряды: если ряд сходится и имеет конечное число перемен знаков в последовательности коэффициентов, то число его положительных вещественных нулей не превосходит этого числа[14].
Точность оценки (Обратная теорема)
Правило Декарта даёт наилучшую возможную оценку числа корней, которую нельзя улучшить, не привлекая дополнительной информации об абсолютных величинах коэффициентов. В математике известна «обратная теорема» к правилу Декарта (в строгом виде доказанная для общего случая Д. Грабинером в 1999 году[15]): для любой последовательности знаков коэффициентов и любого целого числа вида (), всегда существует математически сконструированный многочлен с такой последовательностью знаков, имеющий ровно положительных вещественных корней.
Ограничения теоремы и показательные примеры
Важно понимать, что теорема Декарта даёт лишь оценку сверху и оценку по модулю 2, но не всегда определяет точное число корней. Рассмотрим показательные примеры:
- Пример 1: точное попадание. Для имеем , и действительно три положительных корня: 1, 2, 3.
- Пример 2: теорема даёт лишь оценку. Для имеем . Теорема утверждает, что положительных корней либо 2, либо 0. На самом деле корней нет вовсе (дискриминант квадратного трёхчлена отрицателен). Теорема не позволяет отличить этот случай от случая с двумя корнями.
- Пример 3: отсутствие корней при ненулевом . Для имеем , и теорема корректно предсказывает отсутствие положительных корней.
- Пример 4: комплексные корни не учитываются. Для имеем , теорема говорит об отсутствии положительных корней — что верно, хотя комплексные корни существуют.
- Пример 5: кратные корни. Для имеем , и теорема корректно предсказывает 4 положительных корня (с учётом кратности).
Из примера 2 видно, что разность может быть ненулевой, что соответствует наличию комплексно-сопряжённых пар корней.
Отличие от критерия Сильвестра
Следует отличать теорему Декарта о знаках от другого, совершенно иного правила — критерия Сильвестра для квадратичных форм. Критерий Сильвестра утверждает, что квадратичная форма положительно определена тогда и только тогда, когда все главные миноры её матрицы положительны. Несмотря на схожее название, эти два правила относятся к разным разделам математики и не имеют прямой связи[16].
Доказательство
Доказательство
Обозначим через число положительных вещественных корней многочлена , а через число перемен знака в последовательности его ненулевых коэффициентов. Очевидно, что эти значения не изменятся, если умножить многочлен на , поэтому можно считать, что старший коэффициент положителен, не уменьшая общности. Кроме того, если является корнем многочлена кратности , можно разделить на ; значения и от этого, очевидно, также не изменятся. Вследствие этого можно считать, что не является корнем многочлена, то есть свободный член отличен от нуля.
Докажем последовательно несколько лемм:
Лемма 1
Доказательство: Пусть — свободный член . Тогда . Так как по условию старший член положителен, мы можем утверждать, что при достаточно больших . Если двигаться по числовой прямой от нуля вправо, то при прохождении корня многочлена кратности знак изменяется на противоположный, если нечётно, и сохраняется, если чётно (то есть значение умножается на ).
Следовательно, количество положительных корней с учётом кратности чётно, если , и нечётно, если . Данный факт определяется исключительно знаком свободного члена . Также очевидно, что так как старший коэффициент многочлена положителен, чётность числа перемен знака зависит от того, должен ли знак в конце последовательности (у старшего коэффициента) совпадать со знаком в начале (у свободного члена). Таким образом, и имеют одинаковую чётность. Лемма доказана.
Лемма 2
Доказательство: По теореме Ролля между любыми двумя различными положительными корнями многочлена лежит хотя бы один положительный корень его производной . Кроме того, каждый корень кратности многочлена является корнем кратности его производной. Отсюда получаем, что , что эквивалентно требуемому неравенству.
Лемма 3
Доказательство: Это утверждение, известное как лемма Ролля для знаков коэффициентов, не является тривиальным, но фундаментально для доказательства. Интуитивно оно означает, что дифференцирование «сглаживает» осцилляции многочлена. Строгое доказательство опирается на анализ знаков коэффициентов: если в последовательности коэффициентов была перемена знака, то при переходе к коэффициентам производной (которые равны ) эта перемена знака либо сохраняется, либо «поглощается» соседними коэффициентами, но новые перемены знака при этом не возникают. Следовательно, количество перемен знака не может увеличиться.
Утверждение
Число отрицательных корней многочлена равно числу положительных корней многочлена , где .
Лемма 4
Доказательство: Коэффициенты многочлена получаются из коэффициентов многочлена попеременным умножением на . Если предположить, что все коэффициенты многочлена отличны от нуля, то на том месте, где в их ряду была перемена знака, в ряду коэффициентов многочлена перемены знака не будет, и наоборот — где не было у , обязательно будет у . Поскольку всего пар соседних коэффициентов , сумма чисел перемен знаков в этих многочленах в точности равна . При замене некоторых коэффициентов нулями (и их последующем исключении из ряда) количество перемен знаков в сумме не может увеличиться. Следовательно, в общем случае имеем: . Лемма доказана.
Доказательство теоремы
Докажем неравенство индукцией по . База индукции: при , . Шаг индукции: Пусть . Тогда . Пользуясь леммами 2 и 3 и предположением индукции, что , получаем: . Однако строгое равенство невозможно ввиду леммы 1 (так как и должны иметь одинаковую чётность). А так как и являются целыми числами, мы имеем: .
Если же все корни многочлена вещественны, то общее число корней равно . В силу доказанного неравенства для и , а также леммы 4, имеем: . Отсюда следует, что все неравенства превращаются в равенства: и , из чего и следует теорема в общем случае (с точностью до вычитания чётного числа )[1].
Применение
Правило знаков Декарта находит широкое применение как в теоретической, так и в прикладной математике.
Быстрая оценка числа корней без вычислений. Теорема позволяет мгновенно определить максимальное количество положительных или отрицательных корней, а также доказать их отсутствие. Например, если все коэффициенты многочлена положительны (), то положительных вещественных корней у него нет.
Критерий вещественности всех корней. Если для многочлена степени выполняется равенство , то это является необходимым и достаточным условием того, что все корни многочлена являются вещественными. В этом случае теорема Декарта даёт не просто оценку, а точное число положительных и отрицательных корней.
Локализация корней и вычислительная математика. В комбинации с теоремой Будана-Фурье правило Декарта используется в алгоритмах отделения вещественных корней (например, в методе Штурма или в современных алгоритмах компьютерной алгебры).
Теория управления и устойчивость. В инженерных задачах (например, при анализе устойчивости линейных систем) правило знаков используется для быстрой проверки: если в характеристическом многочлене системы есть пропуски коэффициентов или «неправильные» знаки, система гарантированно неустойчива (имеет корни с положительной вещественной частью). Наглядной иллюстрацией перечисленных выше свойств служат следующие типовые задачи. Они демонстрируют, как именно правило знаков позволяет быстро анализировать структуру корней многочлена, избегая громоздких алгебраических вычислений:
Задача 1. Определить число положительных корней уравнения . Решение. Ряд коэффициентов: . Исключая нули, получаем последовательность . Число перемен знака: . Следовательно, положительных корней либо 3, либо 1.
Задача 2. Доказать, что уравнение не имеет положительных вещественных корней. Решение. Все коэффициенты положительны, поэтому . По теореме Декарта положительных корней нет (что напрямую иллюстрирует первый пункт применения).
Задача 3. Исследовать число отрицательных корней многочлена . Решение. Составим . Все коэффициенты положительны, . Следовательно, отрицательных корней нет.
Примечания
- ↑ 1 2 Кострикин А. И. Введение в алгебру. — М.: Физматлит, 1977. С. 286—287.
- ↑ Прасолов В. В. Многочлены. — М.: МЦНМО, 2001. C. 39.
- ↑ Вилейтнер Г. История математики от Декарта до середины XIX столетия. — М.: ГИФМЛ, 1960. — С. 38.
- ↑ Горелов М. А. Простые задачи оптимизации. Правило Декарта. — М.: Вычислительный центр РАН, 2009. — С. 4, 17.
- ↑ Синкевич Г. И. Отделение корней алгебраического уравнения в XVII и XVIII веке. Метод каскадов Мишеля Ролля и метод многоугольника Исаака Ньютона // Математическое моделирование, численные методы и комплексы программ. — СПб.: СПбГАСУ, 2014. — Вып. 20. — С. 22 — 38.
- ↑ Вилейтнер Г. История математики от Декарта до середины XIX столетия. — М.: ГИФМЛ, 1960. — С. 42—43.
- ↑ Вилейтнер Г. История математики от Декарта до середины XIX столетия. — М.: ГИФМЛ, 1960. — С. 42.
- ↑ Михалкин Е. Н. 2021. Гипергеометрическая интерпретация формулы Декарта — Эйлера // Прикладная математика & Физика. 53(3): 230—234. DOI 10.52575/2687-0959-2021-53-3-230-234.
- ↑ Вилейтнер Г. История математики от Декарта до середины XIX столетия. — М.: ГИФМЛ, 1960. — С. 42.
- ↑ Шафаревич И. Р. О решении уравнений высших степеней [Текст] : (Метод Штурма). — Москва : Гостехиздат, 1954. — 24 с.
- ↑ Гантмахер Ф. Р. Теория матриц. — М.: Физматлит, 2010. — 560 с.
- ↑ Basu S., Pollack R., Roy M.-F. Algorithms in Real Algebraic Geometry. — 2nd ed. — Springer, 2006. — 662 p.
- ↑ Prenov B. B. On an analog of Descartes' rule of signs and the Budan-Fourier theorem for entire functions // Журнал СФУ. Математика и физика. 2018. № 3. С. 317—321.
- ↑ Полиа Г., Сёге Г. Задачи и теоремы из анализа. — Т. 2. — М.: Наука, 1978. С. 46-63.
- ↑ Grabiner, David J. (1999). “Descartes' Rule of Signs: Another Construction”. The American Mathematical Monthly. 106 (10): 854—856. DOI:10.2307/2589619.
- ↑ Ким Г. Д., Крицков Л. В. Алгебра и аналитическая геометрия: теоремы и задачи. T. 2 (2). — Москва: Зерцало, 2003. — С. 150, 152—153. — ISBN 5-94373-077-X.
Литература
- Вилейтнер Г. История математики от Декарта до середины XIX столетия. — М.: ГИФМЛ, 1960. — 468 с.
- Винберг Э. Б. Курс алгебры. — 2-е изд., испр. и доп.. — М.: МЦНМО, 2017. — 592 с. — ISBN 978-5-4439-1087-1.
- Горелов М. А. Простые задачи оптимизации. Правило Декарта и мажоризация. — М.: Вычислительный центр им. А. А. Дородницына РАН, 2011. — 64 с.
- Кострикин А. И. Введение в алгебру. — М.: Физматлит, 1977. — 496 с.
- Курош А. Г. Курс высшей алгебры. — 9-е изд.. — М.: Наука, 1968. — 432 с.
- Михалкин Е. Н. Гипергеометрическая интерпретация формулы Декарта — Эйлера // Прикладная математика & Физика. — 2021. — Т. 53, № 3. — С. 230–234. — doi:10.52575/2687-0959-2021-53-3-230-234.
- Прасолов В. В. Многочлены. — 2-е изд., стер.. — М.: МЦНМО, 2001. — 335 с. — ISBN 5-900916-73-1.
- Синкевич Г. И. Отделение корней алгебраического уравнения в XVII и XVIII веке. Метод каскадов Мишеля Ролля и метод многоугольника Исаака Ньютона // Математическое моделирование, численные методы и комплексы программ. — СПб.: СПбГАСУ, 2014. — Вып. 20. — С. 22–38.
- Шафаревич И. Р. О решении уравнений высших степеней (Метод Штурма). — М.: Гостехиздат, 1954. — 24 с.
- Basu S., Pollack R., Roy M.-F. Algorithms in Real Algebraic Geometry (англ.). — 2nd ed.. — Berlin: Springer, 2006. — 662 p. — ISBN 978-3-540-33098-1.