Геометрические свойства корней полиномов

В математике , одномерный полином степени $п$ с вещественными или комплексными коэффициентами имеет $п$ комплексных корней , если подсчитывают с их кратностей . Они образуют набор из $n$ точек на комплексной плоскости . Эта статья касается геометрии этих точек, то есть информации об их локализации в комплексной плоскости, которая может быть получена из степени и коэффициентов многочлена.

Некоторые из этих геометрических свойств связаны с одним полиномом, например, верхние границы абсолютных значений корней, которые определяют диск, содержащий все корни, или нижние границы расстояния между двумя корнями. Такие оценки широко используются для алгоритмов поиска корней для многочленов, либо для их настройки, либо для вычисления их вычислительной сложности.

Некоторые другие свойства являются вероятностными, например ожидаемое количество действительных корней случайного многочлена степени $n$ с действительными коэффициентами, которое меньше, чем для достаточно большого $n$ . $1+{\frac {2}{\pi }}\ln(n)$

В этой статье рассматриваемый многочлен всегда обозначается

p(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n},

где действительные или комплексные числа и ; таким образом, $n$ - степень многочлена. $a_{0},\dots ,a_{n}$ $a_{n}\neq 0$

Непрерывная зависимость от коэффициентов [ править ]

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

Небольшое изменение коэффициентов может вызвать резкое изменение корней, включая изменение действительного корня на комплексный корень с довольно большой мнимой частью (см . Полином Уилкинсона ). Следствием этого является то, что для классических числовых алгоритмов поиска корней проблема аппроксимации корней с учетом коэффициентов плохо обусловлена .

Спряжение [ править ]

Теорема о комплексно сопряженных корнях утверждает, что если коэффициенты многочлена действительны, то нереальные корни появляются парами вида $(a + ib, a - ib)$ .

Отсюда следует, что корни многочлена с действительными коэффициентами зеркально симметричны относительно действительной оси.

Это может быть расширено до алгебраического сопряжения : корни многочлена с рациональными коэффициентами сопряжены (то есть инвариантны) относительно действия группы Галуа многочлена. Однако эту симметрию редко можно интерпретировать геометрически.

Границы всех корней [ править ]

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

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

Любая верхняя граница абсолютных значений корней обеспечивает соответствующую нижнюю границу. Фактически, если и $U$ - верхняя граница абсолютных значений корней $a_{n}\neq 0,$

a_{0}+a_{1}x+\cdots +a_{n}x^{n},

то $1 / U$ - нижняя граница абсолютных значений

a_{n}+a_{n-1}x+\cdots +a_{0}x^{n},

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

Оценки Лагранжа и Коши [ править ]

Лагранж и Коши были первыми, кто оценил сверху все комплексные корни. ^[1] Оценка Лагранжа равна ^[2]

 $\max \left\{1,\sum _{i=0}^{n-1}\left|{\frac {a_{i}}{a_{n}}}\right|\right\},$

и оценка Коши равна ^[3]

 $1+\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|,\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|\right\}$

Оценка Лагранжа точнее (меньше), чем оценка Коши, только когда 1 больше суммы всех, кроме наибольшего. На практике это относительно редко и объясняет, почему оценка Коши более широко используется, чем оценка Лагранжа. $\left|{\frac {a_{i}}{a_{n}}}\right|$

Обе оценки являются результатом теоремы Гершгорина о круге, примененной к сопутствующей матрице многочлена и ее транспонированию . Их также можно доказать элементарными методами.

Доказательство оценок Лагранжа и Коши.

Если $z$ - корень многочлена и $| z | \geq 1$ имеет

|a_{n}||z^{n}|=\left|\sum _{i=0}^{n-1}a_{i}z^{i}\right|\leq \sum _{i=0}^{n-1}|a_{i}z^{i}|\leq \sum _{i=0}^{n-1}|a_{i}||z|^{n-1}.

При делении на единицу получается $|a_{n}||z|^{n-1},$

|z|\leq \sum _{i=0}^{n-1}{\frac {|a_{i}|}{|a_{n}|}},

что является границей Лагранжа, когда есть хотя бы один корень с абсолютной величиной больше 1. В противном случае 1 является границей корней и не больше границы Лагранжа.

Аналогично, для оценки Коши, если $| z | \geq 1$ ,

|a_{n}||z^{n}|=\left|\sum _{i=0}^{n-1}a_{i}z^{i}\right|\leq \sum _{i=0}^{n-1}|a_{i}z^{i}|\leq \max |a_{i}|\sum _{i=0}^{n-1}|z|^{i}={\frac {|z|^{n}-1}{|z|-1}}\max |a_{i}|\leq {\frac {|z|^{n}}{|z|-1}}\max |a_{i}|.

Таким образом

|a_{n}|(|z|-1)\leq \max |a_{i}|.

Решение в $| z |$ , можно получить оценку Коши, если существует корень с абсолютным значением больше 1. В противном случае граница также верна, поскольку граница Коши больше 1.

Эти границы не инвариантны при масштабировании. То есть корни многочлена $p (sx)$ являются частным по $s$ корня $p$ , а оценки, данные для корней $p (sx)$ , не являются частным по $s$ границ $p$ . Таким образом, можно получить более точные границы, минимизируя возможные масштабирования. Это дает

 $\min _{s\in \mathbb {R} _{+}}\left(\max \left\{s,\sum _{i=0}^{n-1}\left|{\frac {a_{i}}{a_{n}}}\right|s^{i-n+1}\right\}\right),$

а также

 $\min _{s\in \mathbb {R} _{+}}\left(s+\max _{0\leq i\leq n-1}\left(\left|{\frac {a_{i}}{a_{n}}}\right|s^{i-n+1}\right)\right),$

для оценок Лагранжа и Коши соответственно.

Другая оценка, первоначально данная Лагранжем, но приписываемая Цассенхаусу Дональдом Кнутом , - это ^[4]

 $2\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{1/2},\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|^{1/n}\right\}.$

Эта оценка инвариантна при масштабировании.

Доказательство предыдущей оценки

Пусть $A$ будет наибольшим при $0 \leq$ $i$ $<$ $n$ . Таким образом, есть $\left|{\frac {a_{i}}{a_{n}}}\right|^{\frac {1}{n-i}}$

{\frac {|a_{i}|}{|a_{n}|}}\leq A^{n-i}

для Если $z$ является корнем $p$ , один имеет $0\leq i<n.$

-a_{n}z^{n}=\sum _{i=0}^{n-1}a_{i}z^{i},

и, таким образом, после деления на $a_{n},$

{\begin{aligned}|z|^{n}&\leq \sum _{i=0}^{n-1}A^{n-i}|z|^{i}\\&=A{\frac {|z|^{n}-A^{n}}{|z|-A}}.\end{aligned}}

Как мы хотим доказать $| z | \leq 2 A$ , можно считать, что $| z | > А$ (иначе доказывать нечего). Таким образом

|z|^{n}\leq A{\frac {|z|^{n}}{|z|-A}},

что дает результат, так как $|z|>A.$

Лагранж улучшил эту последнюю оценку до суммы двух наибольших значений (возможно, равных) в последовательности ^[4]

 $\left[\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{1/2},\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|^{1/n}\right].$

Лагранж предоставил также границу ^{[ необходима цитата ]}

 $\sum _{i}\left|{\frac {a_{i}}{a_{i+1}}}\right|,$

где обозначает $i-$ й ненулевой коэффициент, когда члены многочленов отсортированы по возрастанию степеней. $a_{i}$

Использование неравенства Гёльдера [ править ]

Неравенство Гёльдера позволяет распространить оценки Лагранжа и Коши на любую h -норму . $Ч$ -норма последовательности

s=(a_{0},\ldots ,a_{n})

является

\|s\|_{h}=\left(\sum _{i=1}^{n}|a_{i}|^{h}\right)^{1/h},

для любого действительного числа $h \geq 1$ и

\|s\|_{\infty }=\textstyle {\max _{i=1}^{n}}|a_{i}|.

Если с $1 \leq$ $h$ $,$ $k$ $\leq \infty$ и $1 / \infty = 0$ , верхняя граница абсолютных значений корней $p$ равна ${\frac {1}{h}}+{\frac {1}{k}}=1,$

 ${\frac {1}{|a_{n}|}}\left\|(|a_{n}|,\left\|(|a_{n-1}|,\ldots ,|a_{0}|\right)\|_{h}\right)\|_{k}.$

При $k = 1$ и $k = \infty$ получаются оценки Коши и Лагранжа соответственно.

При $h = k = 1/2 справедлива$ оценка

 ${\frac {1}{|a_{n}|}}{\sqrt {|a_{n}|^{2}+|a_{n-1}|^{2}+\cdots +|a_{0}|^{2}}}.$

Это не только граница абсолютных значений корней, но также граница произведения их абсолютных значений больше 1; см. § неравенство Ландау ниже.

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

Пусть $z$ - корень многочлена

p(x)=a^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}.

Параметр

A=\left({\frac {|a_{n-1}|}{|a_{n}|}},\ldots ,{\frac {|a_{1}|}{|a_{n}|}},{\frac {|a_{0}|}{|a_{n}|}}\right),

мы должны доказать, что каждый корень $z$ из $p$ удовлетворяет

z\leq \left\|(1,\left\|A\right\|_{h}\right)\|_{k}.

Если неравенство верно; так что можно предположить, что до конца доказательства. $|z|\leq 1,$ $|z|>1$

Записывая уравнение как

-z^{n}={\frac {a_{n-1}}{a_{n}}}z^{n-1}+\cdots +{\frac {a_{1}}{a_{n}}}z+a_{0},

в неравенство Гельдера означает

|z|^{n}\leq \|A\|_{h}\cdot \left\|(z^{n-1},\ldots ,z,1)\right\|_{k}.

Если $k = 1$ , это

|z|^{n}\leq \|A\|_{1}\max \left\{|z|^{n-1},\ldots ,|z|,1\right\}=\|A\|_{1}|z|^{n-1}.

Таким образом

|z|\leq \max\{1,\|A\|_{1}\}.

В случае $1 < k \leq \infty$ формула суммирования геометрической прогрессии дает

|z|^{n}\leq \|A\|_{h}\left(|z|^{k(n-1)}+\cdots +|z|^{k}+1\right)^{\frac {1}{k}}=\|A\|_{h}\left({\frac {|z|^{kn}-1}{|z|^{k}-1}}\right)^{\frac {1}{k}}\leq \|A\|_{h}\left({\frac {|z|^{kn}}{|z|^{k}-1}}\right)^{\frac {1}{k}}.

Таким образом

|z|^{kn}\leq \left(\|A\|_{h}\right)^{k}{\frac {|z|^{kn}}{|z|^{k}-1}},

что упрощает

|z|^{k}\leq 1+\left(\|A\|_{h}\right)^{k}.

Таким образом, во всех случаях

|z|\leq \left\|\left(1,\|A\|_{h}\right)\right\|_{k},

что завершает доказательство.

Другие границы [ править ]

Было дано много других верхних оценок величин всех корней. ^[5]

Связь Фудзивары ^[6]

 $2\,\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{\frac {1}{2}},\ldots ,\left|{\frac {a_{1}}{a_{n}}}\right|^{\frac {1}{n-1}},\left|{\frac {a_{0}}{2a_{n}}}\right|^{\frac {1}{n}}\right\},$

немного улучшает приведенную выше оценку, разделив на два последний аргумент максимума.

Оценка Кодзимы ^[7]^{[ требуется проверка ]}

 $2\,\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n-1}}}\right|,\ldots ,\left|{\frac {a_{0}}{2a_{1}}}\right|\right\},$

где обозначает $i-$ й ненулевой коэффициент, когда члены многочленов отсортированы по возрастанию степеней. Если все коэффициенты отличны от нуля, оценка Фудзивары более точна, поскольку каждый элемент в оценке Фудзивары является средним геометрическим для первых элементов в оценке Кодзимы. $a_{i}$

Сан и Се получили еще одно улучшение оценки Коши. ^[8] Предположим, что многочлен монический с общим членом $a i x i$ . Сан и Се показали, что верхние оценки $1 + d 1$ и $1 + d 2$ могут быть получены из следующих уравнений.

d_{1}={\tfrac {1}{2}}\left((|a_{n-1}|-1)+{\sqrt {(|a_{n-1}|-1)^{2}+4a}}\right),\qquad a=\max\{|a_{i}|\}.

$d 2$ - положительный корень кубического уравнения

Q(x)=x^{3}+(2-|a_{n-1}|)x^{2}+(1-|a_{n-1}|-|a_{n-2}|)x-a,\qquad a=\max\{|a_{i}|\}

Они также отметили, что $d 2 \leq d 1$ .

Неравенство Ландау [ править ]

Предыдущие границы являются верхними границами для каждого корня отдельно. Неравенство Ландау обеспечивает верхнюю границу абсолютных значений произведения корней, имеющих абсолютное значение больше единицы. Это неравенство, обнаруженное в 1905 году Эдмундом Ландау ^[9] , было забыто и открыто заново, по крайней мере, трижды в течение ХХ века. ^[10]^[11]^[12]

Эта оценка произведения корней ненамного превосходит лучшие предыдущие оценки каждого корня в отдельности. ^[13] Позвольте быть корнями $n$ многочлена $p$ . Если $z_{1},\ldots ,z_{n}$

M(p)=|a_{n}|\prod _{j=1}^{n}\max(1,|z_{j}|)

это Малер мера из $р$ , то

M(p)\leq {\sqrt {\sum _{k=0}^{n}|a_{k}|^{2}}}.

Удивительно, но эта граница произведения абсолютных значений корней, превышающих 1, не намного больше, чем лучшие границы одного корня, которые были даны выше для одного корня. Эта оценка даже в точности равна одной из оценок, полученных с помощью неравенства Гёльдера .

Эта оценка также полезна для оценки коэффициентов делителя многочлена с целыми коэффициентами: ^[14] если

q=\sum _{k=0}^{m}b_{k}x^{k}

является делителем числа $p$ , то

|b_{m}|\leq |a_{n}|,

и, по формулам Виета ,

{\frac {|b_{i}|}{|b_{m}|}}\leq {\binom {m}{i}}{\frac {M(p)}{|a_{n}|}},

для $i = 0, ..., m$ , где - биномиальный коэффициент . Таким образом ${\binom {m}{i}}$

|b_{i}|\leq {\binom {m}{i}}M(p)\leq {\binom {m}{i}}{\sqrt {\sum _{k=0}^{n}|a_{k}|^{2}}},

а также

\sum _{i=0}^{m}|b_{k}|\leq 2^{m}M(p)\leq 2^{m}{\sqrt {\sum _{k=0}^{n}|a_{k}|^{2}}}.

Диски, содержащие некоторые корни [ править ]

Из теоремы Руше [ править ]

Теорема Руше позволяет определять круги с центром в нуле, содержащие заданное количество корней. Точнее, если существует положительное действительное число $R$ и целое число $0 \leq k \leq n$ такие, что

|a_{k}|R^{k}>|a_{0}|+\cdots +|a_{k-1}|R^{k-1}+|a_{k+1}|R^{k+1}+\cdots +|a_{n}|R^{n},

то есть ровно $к$ корней, с учетом кратности, по абсолютной величине меньше , чем $R$ .

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

Если тогда $|z|=R,$

{\begin{aligned}|a_{0}&+\cdots +a_{k-1}z^{k-1}+a_{k+1}z^{k+1}+\cdots +a_{n}z^{n}|\\&\leq |a_{0}|+\cdots +|a_{k-1}|R^{k-1}+|a_{k+1}|R^{k+1}+\cdots +|a_{n}|R^{n}\\&\leq |a_{k}|R^{k}\leq |a_{k}z^{k}|.\end{aligned}}

По теореме Руше это прямо означает, что и имеют такое же количество корней с абсолютными значениями, меньшими $R$ , с учетом кратностей. Поскольку это число равно $k$ , результат доказан. $p(z)$ $z^{k}$

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

h_{k}(x)=|a_{0}|+\cdots +|a_{k-1}|x^{k-1}-|a_{k}|x^{k}+|a_{k+1}|x^{k+1}+\cdots +|a_{n}|x^{n}.

принимает отрицательное значение для некоторого положительного действительного значения $x$ .

В оставшейся части раздела предположим, что $a 0 \neq 0$ . Если это не так, ноль является корнем, и локализацию других корней можно изучить, разделив многочлен на степень неопределенности, чтобы получить многочлен с ненулевым постоянным членом.

Для $к = 0$ и $к = п$ , Теорема Декарта показывает , что многочлен имеет ровно один положительный действительный корень. Если и являются этими корнями, приведенный выше результат показывает, что все корни проверяют $R_{0}$ $R_{n}$

R_{0}\leq |z|\leq R_{1}.

Эти неравенства применимы и к, и эти оценки оптимальны для многочленов с заданной последовательностью модулей их коэффициентов. Таким образом, они точнее всех оценок, приведенных в предыдущих разделах. $h_{0}$ $h_{n},$

Для $0 < k < n$ правило знаков Декарта подразумевает, что либо имеет два положительных действительных корня, которые не являются кратными, либо неотрицательны для каждого положительного значения $x$ . Таким образом, приведенный выше результат применим только в первом случае. Если эти два корня, из приведенного выше результата следует, что $h_{k}(x)$ $R_{k,1}<R_{k,2}$

|z|\leq R_{k,1}

для $k$ корней из $p$ , и что

|z|\geq R_{k,2}

для $n - k$ других корней.

Вместо того , чтобы вычисления в явном виде , и она , как правило , достаточно , чтобы вычислить значение такое , что (обязательно ). Они обладают свойством разделять корни в терминах их абсолютных значений: если при $h$ $<$ $k$ оба и существуют, существует ровно $k$ $-$ $h$ корней $z$ таких, что $R_{k,1}$ $R_{k,2},$ $R_{k}$ $h_{k}(R_{k})<0$ $R_{k,1}<R_{k}<R_{k,2}$ $R_{k}$ $R_{h}$ $R_{k}$ $R_{h}<|z|<R_{k}.$

Для вычисления можно использовать , что является выпуклой функцией (ее вторая производная положительна). Таким образом, существует тогда и только тогда, когда он отрицателен в своем единственном минимуме. Для вычисления этого минимума можно использовать любой метод оптимизации или, в качестве альтернативы, метод Ньютона для вычисления единственного положительного нуля производной функции (он быстро сходится, поскольку производная является монотонной функцией ). $R_{k},$ ${\frac {h(x)}{x^{k}}}$ $R_{k}$ ${\frac {h(x)}{x^{k}}}$ ${\frac {h(x)}{x^{k}}}$

Можно увеличить количество существующих , применяя операцию возведения в квадрат корня итерации Данделина – Греффе . Если корни имеют различные абсолютные значения, можно в конечном итоге полностью разделить корни с точки зрения их абсолютных значений, то есть вычислить $n$ $+ 1$ положительных чисел , так что существует ровно один корень с абсолютным значением в открытом интервале для $k$ $= 1, ..,$ $п$ . $R_{k}$ $R_{0}<R_{1}<\dots <R_{n}$ $(R_{k-1},R_{k}),$

Из теоремы Гершгорина о круге [ править ]

Теорема Гершгорина о круге применяет сопутствующую матрицу полинома на основе, связанной с интерполяцией Лагранжа, дает диски с центрами в точках интерполяции, каждый из которых содержит корень полинома; подробности см. в методе Дюрана – Кернера § Включение корня через окружности Гершгорина .

Если точки интерполяции близки к корням корней многочлена, радиусы дисков малы, и это ключевой компонент метода Дюрана – Кернера для вычисления корней многочлена.

Границы настоящих корней [ править ]

Для многочленов с действительными коэффициентами часто бывает полезно ограничить только действительные корни. Достаточно ограничить положительные корни, так как отрицательные корни $p (x)$ являются положительными корнями $p (- x)$ .

Ясно, что каждая оценка всех корней применима также и к действительным корням. Но в некоторых случаях полезны более жесткие границы реальных корней. Например, эффективность метода непрерывных дробей для выделения действительных корней сильно зависит от точности оценки положительных корней. Это привело к установлению новых границ, более жестких, чем общие границы всех корней. Эти границы обычно выражаются не только через абсолютные значения коэффициентов, но и через их знаки.

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

Границы положительных реальных корней [ править ]

Чтобы дать оценку положительных корней, можно предположить без ограничения общности, поскольку изменение знаков всех коэффициентов не меняет корни. $a_{n}>0$

Каждая верхняя граница положительных корней

q(x)=a_{n}x^{n}+\sum _{i=0}^{n-1}\min(0,a_{i})x^{i}

также является оценкой действительных нулей

p(x)=\sum _{i=0}^{n}a_{i}x^{i}

.

Фактически, если $B$ является такой границей, для всех $x > B$ выполняется $p (x) \geq q (x)> 0$ .

Применительно к оценке Коши это дает верхнюю оценку

1+{\textstyle \max _{i=0}^{n-1}}{\frac {-a_{i}}{a_{n}}}

для действительных корней многочлена с действительными коэффициентами. Если эта граница не больше, чем1 , это означает, что все ненулевые коэффициенты имеют один и тот же знак и что положительного корня нет.

Аналогично, другая верхняя граница положительных корней равна

2\,{\max _{a_{i}a_{n}<0}}\left({\frac {-a_{i}}{a_{n}}}\right)^{\frac {1}{n-i}}.

Если все ненулевые коэффициенты имеют один и тот же знак, положительного корня нет, и максимум должен быть определен как нулевой.

Другие оценки были недавно разработаны, в основном из-за необходимости метода непрерывных дробей для выделения действительного корня . ^[15]^[16]

Многочлены, все корни которых действительны [ править ]

Если все корни полинома действительны, Лагер доказал следующие нижние и верхние границы корней, используя то, что сейчас называется неравенством Самуэльсона . ^[17]

Позвольте быть многочлен со всеми действительными корнями. Тогда его корни находятся в интервале с концами $\sum _{k=0}^{n}a_{k}x^{k}$

-{\frac {a_{n-1}}{na_{n}}}\pm {\frac {n-1}{na_{n}}}{\sqrt {a_{n-1}^{2}-{\frac {2n}{n-1}}a_{n}a_{n-2}}}.

Например, корни полинома удовлетворяют $x^{4}+5x^{3}+5x^{2}-5x-6=(x+3)(x+2)(x+1)(x-1)$

-3.8118<-{\frac {5}{4}}-{\frac {3}{4}}{\sqrt {\frac {35}{3}}}\leq x\leq -{\frac {5}{4}}+{\frac {3}{4}}{\sqrt {\frac {35}{3}}}<1.3118.

Разделение корней [ править ]

Корень разделения многочлена является минимальным расстоянием между двумя корнями, то есть минимальное значение абсолютных значений разности двух корней:

\operatorname {sep} (p)=\min\{|\alpha -\beta |\;;\;\alpha \neq \beta {\text{ and }}p(\alpha )=p(\beta )=0\}

Разделение корня является фундаментальным параметром вычислительной сложности из алгоритмов корневых ознакомительные для полиномов. Фактически, разделение корней определяет точность представления чисел, которая необходима для уверенности в различении разных корней. Кроме того, для изоляции реального корня он позволяет ограничить количество делений интервала, необходимых для изоляции всех корней.

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

Для полиномов без квадратов с целыми коэффициентами дискриминант является целым числом и, следовательно, имеет абсолютное значение не ниже, чем 1 . Это позволяет получить нижние границы для разделения корней, которые не зависят от дискриминанта.

Граница разделения Миньотта составляет ^[18]^[19]

\operatorname {sep} (p)>{\frac {{\sqrt {3}}\Delta (p)}{n^{n/2+1}(\|p\|_{2})^{n-1}}},

где - дискриминант, а $\Delta (p)$ $\textstyle \|p\|_{2}={\sqrt {a_{0}^{2}+a_{1}^{2}+\dots +a_{n}^{2}}}.$

Для многочлена без квадратов с целыми коэффициентами отсюда следует

\operatorname {sep} (p)>{\frac {\sqrt {3}}{n^{n/2+1}(\|p\|_{2})^{n-1}}}>{\frac {1}{2^{2s^{2}}}},

где $s$ - размер бит $p$ , то есть сумма разряда его коэффициентов.

Теорема Гаусса – Лукаса [ править ]

Теорема Гаусса – Лукаса утверждает, что выпуклая оболочка корней многочлена содержит корни производной многочлена.

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

Связанный результат - неравенство Бернштейна . Он утверждает, что для многочлена P степени n с производной P ′ имеем

\max _{|z|\leq 1}{\big |}P'(z){\big |}\leq n\max _{|z|\leq 1}{\big |}P(z){\big |}.

Статистическое распределение корней [ править ]

Если коэффициенты $a i$ случайного многочлена независимо и одинаково распределены со средним значением, равным нулю, наиболее сложные корни находятся на единичной окружности или близко к ней. В частности, действительные корни в большинстве своем расположены около $\pm 1$ , и, более того, их ожидаемое число в значительной степени меньше натурального логарифма степени.

Если коэффициенты гауссово распределение со средним значением нуль и дисперсией из сг затем средней плотности действительных корней дается формулой Каца ^[20]^[21]

m(x)={\frac {\sqrt {A(x)C(x)-B(x)^{2}}}{\pi A(x)}}

где

{\begin{aligned}A(x)&=\sigma \sum _{i=0}^{2n-1}x^{i}=\sigma {\frac {x^{2n}-1}{x-1}},\\B(x)&={\frac {1}{2}}{\frac {d}{dx}}A(x),\\C(x)&={\frac {1}{4}}{\frac {d^{2}}{dx^{2}}}A(x)+{\frac {1}{4x}}{\frac {d}{dx}}A(x).\end{aligned}}

Когда коэффициенты распределены по Гауссу с ненулевым средним и дисперсией σ , известна аналогичная, но более сложная формула. ^{[ необходима цитата ]}

Настоящие корни [ править ]

При больших $n$ средняя плотность вещественных корней около $x$ асимптотически равна

m(x)={\frac {1}{\pi |1-x^{2}|}}

если и $x^{2}-1\neq 0,$

m(\pm 1)={\frac {1}{\pi }}{\sqrt {\frac {n^{2}-1}{12}}}

Отсюда следует, что ожидаемое количество действительных корней составляет, используя нотацию большого O

N_{n}={\frac {2}{\pi }}\ln n+C+{\frac {2}{\pi n}}+O(n^{-2})

где $C$ - постоянная, примерно равная0,625 735 8072 . ^[22]

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

Кац, Эрдеш и другие показали, что эти результаты нечувствительны к распределению коэффициентов, если они независимы и имеют одинаковое распределение с нулевым средним. Однако, если дисперсия $i-$ го коэффициента равна ожидаемому количеству действительных корней, будет ^[22] ${\binom {n}{i}},$ ${\sqrt {n}}.$

См. Также [ править ]

Правило знаков Декарта - Связь между количеством положительных корней многочлена и знаками его коэффициентов
Теорема Мардена - Геометрическая связь между нулями кубического многочлена и его производной
Тождества Ньютона - отношения между степенными суммами и элементарными симметричными функциями
Квадратичная функция # Верхняя граница величины корней
Изоляция действительного корня - методы поиска действительных корней многочлена
Поиск корней многочленов - Алгоритмы нахождения нулей многочленов
Многочлен без квадратов - многочлен без повторяющегося корня
Формулы Виета - отношения между коэффициентами и корнями многочлена

Заметки [ править ]

^ Херст, Холли П .; Мейси, Уэйд Т. (1997). «Ограничение корней многочленов». Журнал математики колледжа . 28 (4): 292–295. JSTOR 2687152 .
↑ Lagrange J – L (1798) Traité de la résolution des équations numériques. Париж.
^ Коши Огюстен-Луи (1829). Математические упражнения . Uvres 2 (9) стр.122
^ a b Яп 2000 , §VI.2
^ Марден, М. (1966). Геометрия многочленов . Амер. Математика. Soc. ISBN 0-8218-1503-2.
Перейти ↑ Fujiwara, M. (1916). "Uber die obere Schranke des Absoluten Betrages der Wurzeln einer algebraischen Gleichung" . Математический журнал Тохоку . Первая серия. 10 : 167–171.
↑ Кодзима, Т. (1917). «О пределах корней алгебраического уравнения» . Математический журнал Тохоку . Первая серия. 11 : 119–127.
^ Вс, YJ; Се, JG (1996). «Замечание о круговой границе полиномиальных нулей». IEEE Trans Circuits Syst. Я . 43 (6): 476–478. DOI : 10.1109 / 81.503258 .
^ Э. Ландо, Sur quelques th & or & mes de M. Petrovic relatifs aux zéros des fonctions analytiques, Bull. Сот. Математика. France 33 (1905), 251-261.
^ М. Миньотт. Неравенство о множителях многочленов, Матем. Комп. 28 (1974). 1153-1157.
^ W. Specht, Abschätzungen der Wurzeln algebraischer Gleichungen, Math. З. 52 (1949). 310-321.
↑ J. Vincente Gonçalves, L'inégalité de W. Specht. Univ. Lisboa Revista Fac. Ci A. Ci. Мат. 1 (195O), 167-171.
^ Миньотт, Морис (1983). «Некоторые полезные границы» . Компьютерная алгебра: символьные и алгебраические вычисления . Вена: Springer. С. 259–263. ISBN 0-387-81776-X.
^ Миньотт, М. (1988). Неравенство о неприводимых множителях целочисленных многочленов. Журнал теории чисел , 30 (2), 156-166.
^ Akritas, Alkiviadis G .; Strzeboński, AW; Вигклас, ПС (2008). «Повышение эффективности метода непрерывных дробей с использованием новых оценок положительных корней» (PDF) . Нелинейный анализ: моделирование и управление . 13 : 265–279. Архивировано из оригинального (PDF) 24 декабря 2013 года . Проверено 10 марта 2019 .
^ Штефэнеску, Д. Границы вещественных корней и приложения к ортогональным многочленам . В: В.Г. Ганжа, Э.У. Майр и Е.В. Ворожцов (редакторы): Материалы 10-го Международного семинара по компьютерной алгебре в научных вычислениях, CASC 2007, стр. 377-391, Бонн, Германия, 16-20 сентября 2007 г. LNCS 4770, Springer Verlag, Берлин, Гейдельберг.
Перейти ↑ Laguerre E (1880). "Sur une méthode pour obtenir par приближении les racines d'une équation algébrique qui a toutes ses racines réelles" . Nouvelles Annales de Mathématiques . 2. 19 : 161–172, 193–202..
^ Яп 2000 , § VI.7, предложение 29
^ Коллинз, Джордж Э. (2001). «Полиномиальное минимальное разделение корней» (PDF) . Журнал символических вычислений . 32 : 467–473. DOI : 10,1006 / jsco.2001.0481 .
^ Кац, М. (1943). «О среднем числе действительных корней случайного алгебраического уравнения» . Бюллетень Американского математического общества . 49 (4): 314–320. DOI : 10.1090 / S0002-9904-1943-07912-8 .
^ Кац, М. (1948). «О среднем числе действительных корней случайного алгебраического уравнения (II)». Труды Лондонского математического общества . Вторая серия. 50 (1): 390–408. DOI : 10.1112 / ПНИЛИ / s2-50.5.390 .
^ a b Эдельман, Алан; Костлан, Эрик (1995). «Сколько истинных нулей случайного многочлена?» (PDF) . Бюллетень Американского математического общества . 32 (1): 1–37. DOI : 10.1090 / S0273-0979-1995-00571-9 .

Ссылки [ править ]

Рахман, QI; Шмайссер, Г. (2002). Аналитическая теория многочленов . Монографии Лондонского математического общества. Новая серия. 26 . Оксфорд: Издательство Оксфордского университета . ISBN 0-19-853493-0. Zbl 1072.30006 .
Яп, Чи-Кенг (2000). Фундаментальные проблемы алгоритмической алгебры (PDF) . Издательство Оксфордского университета . ISBN 978-0195125160..

Внешние ссылки [ править ]

Красота корней , визуализация распределения всех корней всех многочленов со степенью и целыми коэффициентами в некотором диапазоне.

[Hirst1997-1] Херст, Холли П .; Мейси, Уэйд Т. (1997). «Ограничение корней многочленов». Журнал математики колледжа . 28 (4): 292–295. JSTOR 2687152 .

[2] Lagrange J – L (1798) Traité de la résolution des équations numériques. Париж.

[Cauchy1829-3] Коши Огюстен-Луи (1829). Математические упражнения . Uvres 2 (9) стр.122

[yap145-4] Яп 2000 , §VI.2

[5] Марден, М. (1966). Геометрия многочленов . Амер. Математика. Soc. ISBN 0-8218-1503-2.

[Fujiwara1916-6] Перейти ↑ Fujiwara, M. (1916). "Uber die obere Schranke des Absoluten Betrages der Wurzeln einer algebraischen Gleichung" . Математический журнал Тохоку . Первая серия. 10 : 167–171.

[Kojima1917-7] Кодзима, Т. (1917). «О пределах корней алгебраического уравнения» . Математический журнал Тохоку . Первая серия. 11 : 119–127.

[Sun1996-8] Вс, YJ; Се, JG (1996). «Замечание о круговой границе полиномиальных нулей». IEEE Trans Circuits Syst. Я . 43 (6): 476–478. DOI : 10.1109 / 81.503258 .

[9] Э. Ландо, Sur quelques th & or & mes de M. Petrovic relatifs aux zéros des fonctions analytiques, Bull. Сот. Математика. France 33 (1905), 251-261.

[10] М. Миньотт. Неравенство о множителях многочленов, Матем. Комп. 28 (1974). 1153-1157.

[11] W. Specht, Abschätzungen der Wurzeln algebraischer Gleichungen, Math. З. 52 (1949). 310-321.

[12] J. Vincente Gonçalves, L'inégalité de W. Specht. Univ. Lisboa Revista Fac. Ci A. Ci. Мат. 1 (195O), 167-171.

[13] Миньотт, Морис (1983). «Некоторые полезные границы» . Компьютерная алгебра: символьные и алгебраические вычисления . Вена: Springer. С. 259–263. ISBN 0-387-81776-X.

[14] Миньотт, М. (1988). Неравенство о неприводимых множителях целочисленных многочленов. Журнал теории чисел , 30 (2), 156-166.

[15] Akritas, Alkiviadis G .; Strzeboński, AW; Вигклас, ПС (2008). «Повышение эффективности метода непрерывных дробей с использованием новых оценок положительных корней» (PDF) . Нелинейный анализ: моделирование и управление . 13 : 265–279. Архивировано из оригинального (PDF) 24 декабря 2013 года . Проверено 10 марта 2019 .

[16] Штефэнеску, Д. Границы вещественных корней и приложения к ортогональным многочленам . В: В.Г. Ганжа, Э.У. Майр и Е.В. Ворожцов (редакторы): Материалы 10-го Международного семинара по компьютерной алгебре в научных вычислениях, CASC 2007, стр. 377-391, Бонн, Германия, 16-20 сентября 2007 г. LNCS 4770, Springer Verlag, Берлин, Гейдельберг.

[Laguerre1880-17] Перейти ↑ Laguerre E (1880). "Sur une méthode pour obtenir par приближении les racines d'une équation algébrique qui a toutes ses racines réelles" . Nouvelles Annales de Mathématiques . 2. 19 : 161–172, 193–202..

[18] Яп 2000 , § VI.7, предложение 29

[19] Коллинз, Джордж Э. (2001). «Полиномиальное минимальное разделение корней» (PDF) . Журнал символических вычислений . 32 : 467–473. DOI : 10,1006 / jsco.2001.0481 .

[Kac1943-20] Кац, М. (1943). «О среднем числе действительных корней случайного алгебраического уравнения» . Бюллетень Американского математического общества . 49 (4): 314–320. DOI : 10.1090 / S0002-9904-1943-07912-8 .

[Kac1948-21] Кац, М. (1948). «О среднем числе действительных корней случайного алгебраического уравнения (II)». Труды Лондонского математического общества . Вторая серия. 50 (1): 390–408. DOI : 10.1112 / ПНИЛИ / s2-50.5.390 .

[ek-22] Эдельман, Алан; Костлан, Эрик (1995). «Сколько истинных нулей случайного многочлена?» (PDF) . Бюллетень Американского математического общества . 32 (1): 1–37. DOI : 10.1090 / S0273-0979-1995-00571-9 .