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

Информацию о вычислении корней полинома см. в разделе «Алгоритмы поиска корня полинома» .

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

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

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

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

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

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

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

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

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

Спряжение

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

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

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

Границы всех корней

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

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

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

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

тогда 1/ U — нижняя граница модулей корней

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

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

Границы Лагранжа и Коши

Лагранж и Коши были первыми, кто определил верхние границы для всех комплексных корней. Граница Лагранжа равна

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

и граница Коши равна

$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|$ но самый большой. На практике это встречается относительно редко и объясняет, почему граница Коши используется более широко, чем граница Лагранжа.

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

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

If z is a root of the polynomial, and |z| ≥ 1 one has $|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}.$ Dividing by $|a_{n}||z|^{n-1},$ one gets $|z|\leq \sum _{i=0}^{n-1}{\frac {|a_{i}|}{|a_{n}|}},$ which is Lagrange's bound when there is at least one root of absolute value larger than 1. Otherwise, 1 is a bound on the roots, and is not larger than Lagrange's bound. Similarly, for Cauchy's bound, one has, if |z| ≥ 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}|.$ Thus $|a_{n}|(|z|-1)\leq \max |a_{i}|.$ Solving in |z|, one gets Cauchy's bound if there is a root of absolute value larger than 1. Otherwise the bound is also correct, as Cauchy's bound is larger than 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),$

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

Другая граница, первоначально данная Лагранжем, но приписываемая Зассенхаузу Дональдом Кнутом , такова:

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

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

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

Let A be the largest $\left|{\frac {a_{i}}{a_{n}}}\right|^{\frac {1}{n-i}}$ for 0 ≤ i < n. Thus one has ${\frac {|a_{i}|}{|a_{n}|}}\leq A^{n-i}$ for $0\leq i<n.$ If z is a root of p, one has $-a_{n}z^{n}=\sum _{i=0}^{n-1}a_{i}z^{i},$ and thus, after dividing by $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}}$ As we want to prove |z| ≤ 2A, we may suppose that |z| > A (otherwise there is nothing to prove). Thus $|z|^{n}\leq A{\frac {|z|^{n}}{|z|-A}},$ which gives the result, since $|z|>A.$

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

$\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|,$

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

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

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

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

является

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

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

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

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

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

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

Для h = k = 2 существует граница

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

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

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

Let z be a root of the polynomial $p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}.$ Setting $A=\left({\frac {|a_{n-1}|}{|a_{n}|}},\ldots ,{\frac {|a_{1}|}{|a_{n}|}},{\frac {|a_{0}|}{|a_{n}|}}\right),$ we have to prove that every root z of p satisfies $z\leq \left\|(1,\left\|A\right\|_{h}\right)\|_{k}.$ If $|z|\leq 1,$ the inequality is true; so, one may suppose $|z|>1$ for the remainder of the proof. Writing the equation as $-z^{n}={\frac {a_{n-1}}{a_{n}}}z^{n-1}+\cdots +{\frac {a_{1}}{a_{n}}}z+{\frac {a_{0}}{a_{n}}},$ Hölder's inequality implies $|z|^{n}\leq \|A\|_{h}\cdot \left\|(z^{n-1},\ldots ,z,1)\right\|_{k}.$ If k = ∞, this is $|z|^{n}\leq \|A\|_{1}\max \left\{|z|^{n-1},\ldots ,|z|,1\right\}=\|A\|_{1}|z|^{n-1}.$ Thus $|z|\leq \max\{1,\|A\|_{1}\}.$ In the case 1 ≤ k < ∞, the summation formula for a geometric progression, gives $|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}}.$ Thus $|z|^{kn}\leq \left(\|A\|_{h}\right)^{k}{\frac {|z|^{kn}}{|z|^{k}-1}},$ which simplifies to $|z|^{k}\leq 1+\left(\|A\|_{h}\right)^{k}.$ Thus, in all cases $|z|\leq \left\|\left(1,\|A\|_{h}\right)\right\|_{k},$ which finishes the proof.

Другие границы

Было дано множество других верхних оценок величин всех корней.

Фудзивара связан

$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\},$

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

Граница Кодзимы равна

$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\},$

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

Сунь и Се получили еще одно улучшение оценки Коши. Предположим, что полином является моническим с общим членом a _i x ^я . Сунь и Се показали, что верхние границы 1 + d ₁ и 1 + d ₂ могут быть получены из следующих уравнений.

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

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

$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 ₂ ≤ d ₁ .

Неравенство Ландау

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

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

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

— Малера p , мера затем

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

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

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

$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 ≤ k ≤ 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},$

тогда имеется ровно k корней, считая с кратностью, по модулю меньше R .

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

If $|z|=R,$ then ${\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}}$ By Rouché's theorem, this implies directly that $p(z)$ and $z^{k}$ have the same number of roots of absolute values less than R, counted with multiplicities. As this number is k, the result is proved.

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

$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 . Если это не так, ноль является корнем, и локализацию других корней можно изучить путем деления многочлена на степень неопределенного, получая многочлен с ненулевым постоянным членом.

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

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

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

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

$|z|\leq R_{k,1}$

для k корней числа p и что

$|z|\geq R_{k,2}$

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

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

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

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

Из теоремы

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

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

Границы действительных корней

Для многочленов с действительными коэффициентами часто бывает полезно ограничить только действительные корни. Достаточно ограничить положительные корни, поскольку отрицательные корни 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 ) ≥ 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}}.$

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

Недавно были разработаны и другие оценки, в основном для метода цепных дробей для изоляции вещественных корней .

все корни которых

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

Позволять $\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 . Это позволяет получить нижние границы разделения корней, независимые от дискриминанта.

Граница разделения Миньотта равна

$\operatorname {sep} (p)>{\frac {\sqrt {3|\Delta (p)|}}{n^{(n+1)/2}(\|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 случайного многочлена независимо и одинаково распределены со средним значением, равным нулю, наиболее сложные корни находятся на единичной окружности или близко к ней. В частности, действительные корни большей частью расположены вблизи ±1 , причем их ожидаемое число в значительной степени меньше натурального логарифма степени.

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

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

где

${\begin{aligned}A(x)&=\sigma \sum _{i=0}^{n-1}x^{2i}=\sigma {\frac {x^{2n}-1}{x^{2}-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}}}$

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

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

где C равная 0,6257358072 — константа , . примерно

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

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

Геометрия множественных корней

Полином $p$ можно записать в виде

$p(x)=a(x-z_{1})^{m_{1}}\cdots (x-z_{k})^{m_{k}}$

с разными корнями $z_{1},\ldots ,z_{k}$ и соответствующие кратности $m_{1},\ldots ,m_{k}$. корень $z_{j}$ является простым корнем , если $m_{j}=1$ или кратный корень , если $m_{j}\geq 2$. Простые корни липшицевы по коэффициентам, а кратные корни — нет. Другими словами, простые корни имеют ограниченную чувствительность, но кратные корни бесконечно чувствительны, если коэффициенты изменяются произвольно. В результате большинство алгоритмов поиска корней страдают от существенной потери точности при множественных корнях при численных вычислениях.

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

Это геометрическое свойство кратных корней имеет решающее значение при численном вычислении кратных корней .

См. также

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

Ссылки

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

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

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