Геометрические свойства корней полиномов - Geometrical properties of polynomial roots

О вычислении полиномиальных корней см. Изоляция реального корня и Алгоритм поиска корней § Корни многочленов.

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

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

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

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

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

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

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

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

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

Конъюгация

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

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

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

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

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

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

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

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

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

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

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

Оценки Лагранжа и Коши

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

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

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

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

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

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

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

Если z является корнем многочлена, а |z| ≥ 1 надо ${displaystyle |a_{n}||z^{n}|=left|sum _{i=0}^{n-1}a_{i}z^{i}ight|leq sum _{i=0}^{n-1}|a_{i}z^{i}|leq sum _{i=0}^{n-1}|a_{i}||z|^{n-1}.}$ Деление на ${displaystyle |a_{n}||z|^{n-1},}$ один получает ${displaystyle |z|leq sum _{i=0}^{n-1}{frac {|a_{i}|}{|a_{n}|}},}$ что является границей Лагранжа, когда есть хотя бы один корень с абсолютной величиной больше 1. В противном случае 1 является границей корней и не больше границы Лагранжа. Аналогично, для оценки Коши, если |z| ≥ 1, ${displaystyle |a_{n}||z^{n}|=left|sum _{i=0}^{n-1}a_{i}z^{i}ight|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}|.}$ Таким образом ${displaystyle |a_{n}|(|z|-1)leq max |a_{i}|.}$ Решение в |z|, граница Коши получается, если корень с абсолютным значением больше 1. В противном случае граница также верна, поскольку граница Коши больше 1.

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

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

и

${displaystyle min _{sin mathbb {R} _{+}}left(s+max _{0leq ileq n-1}left(left|{frac {a_{i}}{a_{n}}}ight|s^{i-n+1}ight)ight),}$

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

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

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

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

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

Позволять А быть самым большим ${displaystyle left|{frac {a_{i}}{a_{n}}}ight|^{frac {1}{n-i}}}$ за 0 ≤ я < п. Таким образом, есть ${displaystyle {frac {|a_{i}|}{|a_{n}|}}leq A^{n-i}}$ за ${displaystyle 0leq i<n.}$Если z это корень п, надо ${displaystyle -a_{n}z^{n}=sum _{i=0}^{n-1}a_{i}z^{i},}$ и, таким образом, после деления на ${displaystyle a_{n},}$ ${displaystyle {egin{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| ≤ 2А, можно предположить, что |z| > А (иначе доказывать нечего). ${displaystyle |z|^{n}leq A{frac {|z|^{n}}{|z|-A}},}$ что дает результат, так как ${displaystyle |z|>A.}$

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

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

Лагранж дал также оценку^{[нужна цитата ]}

${displaystyle sum _{i}left|{frac {a_{i}}{a_{i+1}}}ight|,}$

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

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

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

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

является

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

для любого реального числа час ≥ 1, и

${displaystyle |s|_{infty }= extstyle {max _{i=1}^{n}}|a_{i}|.}$

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

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

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

За час = k = 1/2, есть граница

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

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

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

Позволять z быть корнем многочлена ${displaystyle p(x)=a^{n}+a_{n-1}x^{n-1}+cdots +a_{1}x+a_{0}.}$ Параметр ${displaystyle A=left({frac {|a_{n-1}|}{|a_{n}|}},ldots ,{frac {|a_{1}|}{|a_{n}|}},{frac {|a_{0}|}{|a_{n}|}}ight),}$ мы должны доказать, что каждый корень z из п удовлетворяет ${displaystyle zleq left|(1,left|Aight|_{h}ight)|_{k}.}$ Если ${displaystyle |z|leq 1,}$ неравенство верно; так что можно предположить ${displaystyle |z|>1}$ для оставшейся части доказательства. Записывая уравнение как ${displaystyle -z^{n}={frac {a_{n-1}}{a_{n}}}z^{n-1}+cdots +{frac {a_{1}}{a_{n}}}z+a_{0},}$ то Неравенство Гёльдера подразумевает ${displaystyle |z|^{n}leq |A|_{h}cdot left|(z^{n-1},ldots ,z,1)ight|_{k}.}$ Если k = 1, это ${displaystyle |z|^{n}leq |A|_{1}max left{|z|^{n-1},ldots ,|z|,1ight}=|A|_{1}|z|^{n-1}.}$ Таким образом ${displaystyle |z|leq max{1,|A|_{1}}.}$ В случае 1 < k ≤ ∞, формула суммирования для a геометрическая прогрессия, дает ${displaystyle |z|^{n}leq |A|_{h}left(|z|^{k(n-1)}+cdots +|z|^{k}+1ight)^{frac {1}{k}}=|A|_{h}left({frac {|z|^{kn}-1}{|z|^{k}-1}}ight)^{frac {1}{k}}leq |A|_{h}left({frac {|z|^{kn}}{|z|^{k}-1}}ight)^{frac {1}{k}}.}$ Таким образом ${displaystyle |z|^{kn}leq left(|A|_{h}ight)^{k}{frac {|z|^{kn}}{|z|^{k}-1}},}$ что упрощает ${displaystyle |z|^{k}leq 1+left(|A|_{h}ight)^{k}.}$ Таким образом, во всех случаях ${displaystyle |z|leq left|left(1,|A|_{h}ight)ight|_{k},}$ что завершает доказательство.

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

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

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

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

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

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

${displaystyle 2,max left{left|{frac {a_{n-1}}{a_{n}}}ight|,left|{frac {a_{n-2}}{a_{n-1}}}ight|,ldots ,left|{frac {a_{0}}{2a_{1}}}ight|ight},}$

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

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

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

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

${displaystyle 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 г. Эдмунд Ландау^[9] была забыта и открыта заново по крайней мере три раза в течение 20 века.^[10][11][12]

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

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

это Мера Малера из п,тогда

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

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

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

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

является делителем п, тогда

${displaystyle |b_{m}|leq |a_{n}|,}$

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

${displaystyle {frac {|b_{i}|}{|b_{m}|}}leq {inom {m}{i}}{frac {M(p)}{|a_{n}|}},}$

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

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

и

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

Диски, содержащие корни

Из теоремы Руше

Теорема Руше позволяет определять диски с нулевым центром и заданным количеством корней. Точнее, если есть положительное действительное число р и целое число 0 ≤ k ≤ п такой, что

${displaystyle |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 корни, пересчитанные с кратностью, по модулю меньше чем р.

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

Если ${displaystyle |z|=R,}$ тогда ${displaystyle {egin{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}}}$ По теореме Руше это непосредственно означает, что ${displaystyle p(z)}$ и ${displaystyle z^{k}}$ имеют одинаковое количество корней абсолютных значений меньше, чем р, считая с кратностями. Поскольку это число k, результат доказан.

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

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

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

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

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

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

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

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

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

за k корни п, и это

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

для п – k другие корни.

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

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

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

Из теоремы Гершгорина о круге

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

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

Границы настоящих корней

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

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

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

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

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

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

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

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

${displaystyle p(x)=sum _{i=0}^{n}a_{i}x^{i}}$.

Фактически, если B такая граница, для всех Икс > B, надоп(Икс) ≥ q(Икс) > 0.

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

${displaystyle 1+{ extstyle max _{i=0}^{n-1}}{frac {-a_{i}}{a_{n}}}}$

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

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

${displaystyle 2,{max _{a_{i}a_{n}<0}}left({frac {-a_{i}}{a_{n}}}ight)^{frac {1}{n-i}}.}$

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

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

Многочлены с действительными корнями

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

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

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

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

${displaystyle -3.8118<-{frac {5}{4}}-{frac {3}{4}}{sqrt {frac {35}{3}}}leq xleq -{frac {5}{4}}+{frac {3}{4}}{sqrt {frac {35}{3}}}<1.3118.}$

Отделение корней

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

${displaystyle operatorname {sep} (p)=min{|alpha -eta |;;;alpha eq eta { ext{ and }}p(alpha )=p(eta )=0}}$

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

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

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

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

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

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

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

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

куда s это кусочек размер п, то есть сумма битового размера его коэффициентов.

Теорема Гаусса – Лукаса

Основная статья: Теорема Гаусса – Лукаса

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

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

Связанный результат Неравенство Бернштейна. Он утверждает, что для полинома п степени п с производной П' у нас есть

${displaystyle max _{|z|leq 1}{ig |}P'(z){ig |}leq nmax _{|z|leq 1}{ig |}P(z){ig |}.}$

Статистическое распределение корней

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

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

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

куда

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

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

Настоящие корни

Для больших п, средняя плотность реальных корней вблизи Икс асимптотически

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

если ${displaystyle x^{2}-1eq 0,}$и

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

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

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

куда C - константа, примерно равная 0.6257358072.^[22]

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

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

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

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

Примечания

1. Херст, Холли П.; Мейси, Уэйд Т. (1997). «Ограничение корней многочленов». Математический журнал колледжа. 28 (4): 292–295. JSTOR  2687152.
2. Лагранж J – L (1798) Traité de la résolution des équations numériques. Париж.
3. Коши Огюстен-Луи (1829). Математические упражнения. Uvres 2 (9) стр.122
4. Яп 2000, §VI.2
5. Марден, М. (1966). Геометрия многочленов. Амер. Математика. Soc. ISBN  0-8218-1503-2.
6. Фудзивара, М. (1916). "Über die obere Schranke des Absoluten Betrages der Wurzeln einer algebraischen Gleichung". Математический журнал Тохоку. Первая серия. 10: 167–171.
7. Кодзима, Т. (1917). «О пределах корней алгебраического уравнения». Математический журнал Тохоку. Первая серия. 11: 119–127.
8. Sun, Y.J .; Се, Дж. Г. (1996). «Замечание о круговой границе полиномиальных нулей». IEEE Trans Circuits Syst. я. 43 (6): 476–478. Дои:10.1109/81.503258.
9. Э. Ландо, Sur quelques th & or & mes de M. Petrovic relatifs aux zéros des fonctions analytiques, Бык. Сот. Математика. Франция 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, A. W .; Вигклас, П. С. (2008). «Повышение эффективности метода непрерывных дробей с использованием новых оценок положительных корней» (PDF). Нелинейный анализ: моделирование и управление. 13: 265–279. Архивировано из оригинал (PDF) на 2013-12-24. Получено 2019-03-10.
16. Штефэнеску, Д. Границы вещественных корней и приложения к ортогональным многочленам. В: В.Г. Ганжа, Э.У. Майр и Е.В. Ворожцов (редакторы): Материалы 10-го Международного семинара по компьютерной алгебре в научных вычислениях, CASC 2007, стр. 377-391, Бонн, Германия, 16-20 сентября 2007 г. LNCS 4770, Springer Verlag, Берлин, Гейдельберг.
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. Дои:10.1006 / jsco.2001.0481.
20. Кац, М. (1943). «О среднем числе действительных корней случайного алгебраического уравнения». Бюллетень Американского математического общества. 49 (4): 314–320. Дои:10.1090 / S0002-9904-1943-07912-8.
21. Кац, М. (1948). «О среднем числе действительных корней случайного алгебраического уравнения (II)». Труды Лондонского математического общества. Вторая серия. 50 (1): 390–408. Дои:10,1112 / плмс / с2-50.5.390.
22. Эдельман, Алан; Костлан, Эрик (1995). «Сколько истинных нулей случайного многочлена?» (PDF). Бюллетень Американского математического общества. 32 (1): 1–37. Дои:10.1090 / S0273-0979-1995-00571-9.

Рекомендации

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

внешняя ссылка

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