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

Геометрия расположения корней полинома

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

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

Некоторые другие свойства являются вероятностными, например, ожидаемое число действительных корней случайного многочлена степени n с действительными коэффициентами, которое меньше, чем при достаточно большом n . ${\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}\neq 0}$ ${\displaystyle n}$

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

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

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

Спряжение

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

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

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

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

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

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

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

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

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

${\displaystyle 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 больше суммы всех , кроме наибольшего. Это встречается на практике относительно редко и объясняет, почему граница Коши используется шире, чем граница Лагранжа. ${\displaystyle \left|{\frac {a_{i}}{a_{n}}}\right|}$

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

является

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

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

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

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

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

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

При h = k = 2 имеет место ограничение

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

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

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

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

Связанный Фудзиварой ^[6]

${\displaystyle 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] [ требуется проверка ]}

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

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

${\displaystyle d_{1}={\tfrac {1}{2}}\left((|a_{n-1}|-1)+{\sqrt {(|a_{n-1}|-1)^{2}+4a}}\right),\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] Пусть — n корней многочлена p . Если ${\displaystyle z_{1},\ldots ,z_{n}}$

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

является мерой Малера p , тогда

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

${\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 корней, подсчитанных с учетом кратности , имеющих абсолютное значение меньше R.

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

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

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

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

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

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

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

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

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

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

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

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

Вместо явного вычисления и обычно достаточно вычислить значение, такое что (обязательно ). Они обладают свойством разделения корней с точки зрения их абсолютных значений: если для h < k существуют и , то существует ровно k – h корней z таких, что ${\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}}$ ${\displaystyle R_{h}}$ ${\displaystyle R_{k}}$ ${\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}}}}$

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

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

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

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

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

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

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

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

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

Чтобы дать оценку положительным корням, можно без потери общности предположить, что изменение знаков всех коэффициентов не приводит к изменению корней. ${\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 является такой границей, то для всех x > B имеем p ( x ) ≥ q ( x ) > 0 .

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

${\displaystyle 1+{\textstyle \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}}}\right)^{\frac {1}{n-i}}.}$

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

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

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

Если все корни многочлена действительны, Лагерр доказал следующие нижние и верхние границы корней, используя то, что сейчас называется неравенством Самуэльсона . ^[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 x\leq -{\frac {5}{4}}+{\frac {3}{4}}{\sqrt {\frac {35}{3}}}<1.3118.}$

Разделение корней

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

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

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

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

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

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

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

где дискриминант, и ${\displaystyle \Delta (p)}$ ${\displaystyle \textstyle \|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 — это разрядность p , то есть сумма разрядностей его коэффициентов.

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

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

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

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

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

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

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

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

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

где

${\displaystyle {\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 асимптотически равна

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

если и ${\displaystyle x^{2}-1\neq 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,625 735 8072 . ^[23]

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

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

Геометрия кратных корней

Многочлен можно записать в виде ${\displaystyle p}$

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

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

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

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

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

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

Примечания

1. Hirst, Holly P.; Macey, Wade T. (1997). «Ограничение корней многочленов». The College Mathematics Journal . 28 (4): 292–295. doi :10.1080/07468342.1997.11973878. JSTOR  2687152.
2. Лагранж J – L (1798) Traité de la resolution des équations numériques. Париж.
3. Коши Огюстен-Луи (1829). Математические упражнения . Увр 2 (9) с.122
4. Яп 2000, §VI.2
5. Марден, М. (1966). Геометрия многочленов . Amer. Math. Soc. ISBN 0-8218-1503-2.
6. Фудзивара, М. (1916). «Über die obere Schranke des Absoluten Betrages der Wurzeln einer алгебраишен Gleichung». Математический журнал Тохоку . Первая серия. 10 : 167–171.
7. Кодзима, Т. (1917). «О пределах корней алгебраического уравнения». Tohoku Mathematical Journal . Первая серия. 11 : 119–127.
8. Sun, YJ; Hsieh, JG (1996). «Заметка о круговой границе полиномиальных нулей». IEEE Trans Circuits Syst. I. 43 ( 6): 476–478. doi :10.1109/81.503258.
9. Э. Ландо, Sur quelques th&or&mes de M. Petrovic relatifs aux zéros des functions Analytiques, Bull. Сот. Математика. Франция 33 (1905), 251–261.
10. М. Миньотт. Неравенство о множителях многочленов, Math. Comp. 28 (1974). 1153-1157.
11. В. Шпехт, Abschätzungen der Wurzeln алгебраишер Gleichungen, Math. З. 52 (1949). 310-321.
12. Ж. Винсенте Гонсалвес, L'inégalité de W. Specht. унив. Лиссабон Ревиста Фак. Ци А. Ци. Мат. 1 (195О), 167-171.
13. Миньотт, Морис (1983). «Некоторые полезные границы». Компьютерная алгебра: символические и алгебраические вычисления . Вена: Springer. С. 259–263. ISBN 0-387-81776-X.
14. Миньотт, М. (1988). Неравенство о неприводимых множителях целочисленных многочленов. Журнал теории чисел , 30(2), 156-166.
15. Акритас, Алкивиадис Г.; Стржебонский, А. В.; Вигклас, П. С. (2008). «Улучшение производительности метода непрерывных дробей с использованием новых границ положительных корней». Нелинейный анализ: моделирование и управление . 13 (3): 265–279. doi : 10.15388/NA.2008.13.3.14557 .
16. Штефанеску, Д. Границы для действительных корней и приложения к ортогональным многочленам . В: В. Г. Ганжа, Э. В. Майр и Е. В. Ворожцов (редакторы): Труды 10-го Международного семинара по компьютерной алгебре в научных вычислениях, CASC 2007, стр. 377 – 391, Бонн, Германия, 16-20 сентября 2007 г. LNCS 4770, Springer Verlag, Берлин, Гейдельберг.
17. Лагерр Э (1880). «Sur une метод для получения приближения к алгебраическим уравнениям, которые toutes ses racines réelles». Новые анналы математики . 2. 19 : 161–172, 193–202. Архивировано из оригинала 15 июля 2014 г. Проверено 3 сентября 2013 г..
18. Миньотт, Морис (1982). Некоторые полезные границы (PDF) . Springer. стр. 262.
19. Яп 2000, § VI.7, Предложение 29
20. Коллинз, Джордж Э. (2001). "Минимальное разделение корней полиномов" (PDF) . Журнал символических вычислений . 32 (5): 467–473. doi : 10.1006/jsco.2001.0481 .
21. Кац, М. (1943). «О среднем числе действительных корней случайного алгебраического уравнения». Бюллетень Американского математического общества . 49 (4): 314–320. doi : 10.1090/S0002-9904-1943-07912-8 .
22. Кац, М. (1948). «О среднем числе действительных корней случайного алгебраического уравнения (II)». Труды Лондонского математического общества . Вторая серия. 50 (1): 390–408. doi :10.1112/plms/s2-50.5.390.
23. Эдельман, Алан; Костлан, Эрик (1995). "Сколько нулей случайного многочлена являются действительными?" (PDF) . Бюллетень Американского математического общества . 32 (1): 1–37. doi : 10.1090/S0273-0979-1995-00571-9 .
24. Кахан, В. (1972). «Сохранение слияния ограничивает плохое состояние». Технический отчет 6, Компьютерные науки, Калифорнийский университет .

Ссылки

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

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

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