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

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

двумя корнями (сепаратор корней) уравнения также определение 7.2.10). Этот результат выводится из более общей теоремы Малера и играет важную роль в анализе времени работы не только метода Штурма, но вообще любого метода, используемого для отделения вещественных корней уравнения. [Представляет интерес работа (Mignotte et al., 1979).]

Теорема 7.2.12 (Малер). Если — свободный, от квадратов полином степени от одной переменной с целыми коэффициентами и А — сепаратор его корней, то

Доказательство. Главные инструменты в этом доказательстве — неравенство теоремы 6.3.2 и теорема Адамара об определителях, которая может быть сформулирована следующим образом:

Если элементы , определителя

являются произвольными комплексными числами, то

и равенство имеет место, если и только если

где обозначает комплексно-сопряженное к [Локазательство теоремы Адамара можно найти в книге (Marcus, Mine, 1965), упр. 5, с. 208.]

Для доказательства теоремы пусть — корни уравнения и положим

Тогда из теоремы 6.3.2 работы (Specht, 1949) мы имеем неравенство

где из определения 1.2.6 следует, что

Пусть теперь корни полинома пронумерованы так, что

и пусть

при условии, что при . Хорошо известно, что где — определитель Вандермонда

Более того, положим . Тогда , где

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

Равенство имеет место, если одновременно

и

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

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

или

Таким образом, мы видим, что только в случае где

Теперь пусть фиксированы, . Мы намерены получить границу для методом, аналогичным тому, который мы только что применяли к

Сначала в матрице, соответствующей определителю Вандермонда вычтем столбец из так что новый столбец состоит из элементов

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

Поэтому частное может теперь быть переписано как определитель, в котором столбец состоит из элементов а. остальные столбцов — те же, что и в исходном определителе Разделив теперь снова 1-й, 2-й, столбец матрицы, соответствующей новому определителю, на множители соответственно, мы получаем определитель со значением За исключением столбца, этот определитель совпадает с определителем Его столбец состоит из элементов

если , и элементов

если Поскольку

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

Поскольку сумма в скобках равна что окончательный результат принимает вид

Решая относительно получаем

или

Из разд. 5.2.2 нам известно, что дискриминант полинома равен

и, следовательно, мы можем также написать

или

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

Пример. полинома мы получаем

Это означает, что наименьшее расстояние между любыми двумя

корнями полинома больше, чем 0.0005.