Алгоритм Лемера – Шура

В математике алгоритм Лемера-Шура (названный в честь Деррика Генри Лемера и Иссаи Шура ) представляет собой алгоритм поиска корней для комплексных многочленов , расширяющий идею включения корней, как в одномерном методе деления пополам , на комплексную плоскость. Он использует тест Шура-Кона для проверки дисков все меньшего размера на наличие или отсутствие корней.

Алгоритм Шура-Кона

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

Для комплексного многочлена $p$ степени ​ $n$ его обратный сопряженный полином $p^{*}$ определяется $p^{*}(z)=z^{n}{\overline {p({\bar {z}}^{-1})}}$ и его преобразование Шура $Tp$ к

$Tp={\overline {p(0)}}p-{\overline {p^{*}(0)}}p^{*},$

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

Итак, если $p(z)=a_{n}z^{n}+\cdots +a_{1}z+a_{0}$ с $a_{n}\neq 0$, затем $p^{*}(z)={\bar {a}}_{0}z^{n}+{\bar {a}}_{1}z^{n-1}+\cdots +{\bar {a}}_{n}$, с удалением ведущих нулевых членов , если таковые имеются. Коэффициенты ​ ​ $Tp$ поэтому может быть непосредственно выражено в $p$ и, поскольку один или несколько старших коэффициентов сокращаются, $Tp$ имеет более низкую степень, чем $p$. Корни $p$, $p^{*}$, и $Tp$ связаны следующим образом.

Лемма

Позволять $p$ быть комплексным полиномом и $\delta =(Tp)(0)$.

• Корни $p^{*}$, включая их кратности , являются образами при инверсии в единичном круге ненулевых корней $p$.
• Если $\delta \neq 0$, затем $p,\,p^{*}$, и $Tp$ общие корни на единичном круге, включая их кратности.
• Если $\delta >0$, затем $p$ и $Tp$ имеют одинаковое количество корней внутри единичного круга.
• Если $\delta <0$, затем $p^{*}$ и $Tp$ имеют одинаковое количество корней внутри единичного круга.

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

Для $z\neq 0$ у нас есть $p^{*}(z)=z^{n}{\overline {p(z/|z|^{2})}}$ и, в частности, $|p^{*}(z)|=|p(z)|$ для $|z|=1$. Также $\delta \neq 0$ подразумевает $|p(0)|\neq |p^{*}(0)|$. Из этого и приведенных выше определений следуют первые два утверждения. Два других утверждения являются следствием теоремы Руше, примененной на единичной окружности к функциям ${\overline {p(0)}}p(z)/r(z)$ и $-{\overline {p^{*}(0)}}p^{*}(z)/r(z)$ , где $r$ многочлен, имеющий своими корнями корни $p$ на единичном круге с теми же кратностями. □

Для более доступного представления леммы позволять $n_{p}^{-},n_{p}^{0}$, и $n_{p}^{+}$ обозначают количество корней $p$ внутри, на и вне единичного круга соответственно и аналогично для $Tp$. Более того, пусть $d$ быть разницей в степени $p$ и $Tp$. Тогда из леммы следует, что $(n_{p}^{-},\;n_{p}^{0},\;n_{p}^{+})=(n_{Tp}^{-},\;n_{Tp}^{0},\;n_{Tp}^{+}+d)$ если $\delta >0$ и $(n_{p}^{-},\;n_{p}^{0},\;n_{p}^{+})=(n_{Tp}^{+}+d,\;n_{Tp}^{0},\;n_{Tp}^{-})$ если $\delta <0$ (обратите внимание на обмен $^{+}$ и $^{-}$).

Теперь рассмотрим последовательность полиномов $T^{k}p$ $(k=0,1,\ldots )$, где $T^{0}p=p$ и $T^{k+1}p=T(T^{k}p)$. Применение вышеизложенного к каждой паре последовательных членов этой последовательности дает следующий результат.

Теорема [тест Шура-Кона]

Позволять $p$ быть комплексным многочленом с $Tp\neq 0$ и пусть $K$ быть наименьшим числом таким, что $T^{K+1}p=0$. Более того, пусть $\delta _{k}=(T^{k}p)(0)$ для $k=1,\ldots ,K$ и $d_{k}=\deg T^{k}p$ для $k=0,\ldots ,K$.

• Все корни $p$ лежат внутри единичного круга тогда и только тогда, когда

$\delta _{1}<0$, $\delta _{k}>0$ для $k=2,\ldots ,K$, и $d_{K}=0$.

• Все корни $p$ лежат вне единичного круга тогда и только тогда, когда

$\delta _{k}>0$ для $k=1,\ldots ,K$ и $d_{K}=0$.

• Если $d_{K}=0$ и если $\delta _{k}<0$ для $k=k_{0},k_{1}\ldots k_{m}$ (в порядке возрастания) и $\delta _{k}>0$ иначе, тогда $p$ не имеет корней на единичной окружности и число корней $p$ внутри единичного круга находится

$\sum _{i=0}^{m}(-1)^{i}d_{k_{i}-1}$.

В более общем смысле распределение корней многочлена $p$ относительно произвольного круга на комплексной плоскости, скажем, с центром $c$ и радиус $\rho$, можно найти, применив тест Шура-Кона к «сдвинутому и масштабированному» полиному $q$ определяется $q(z)=p(c+\rho \,z)$.

Однако не каждый масштабный коэффициент допускается, поскольку тест Шура-Кона можно применить к полиному. $q$ только если не выполняется ни одно из следующих равенств: $T^{k}q(0)=0$ для некоторых $k=1,\ldots K$ или $T^{K+1}q=0$ пока $d_{K}>0$. Теперь коэффициенты многочленов $T^{k}q$ являются полиномами в $\rho$ и указанные равенства приводят к полиномиальным уравнениям для $\rho$, которые поэтому справедливы только для конечного числа значений $\rho$. Таким образом, всегда можно найти подходящий масштабный коэффициент, даже сколь угодно близкий к $1$.

метод Лемера

Метод Лемерса заключается в следующем. Для данного комплексного многочлена $p$, с помощью теста Шура-Кона можно найти круглый диск, достаточно большой, чтобы вместить все корни $p$. Затем этот диск можно покрыть набором перекрывающихся дисков меньшего размера, один из которых расположен концентрически, а остальные равномерно распределены по еще не покрытому кольцу. Из этого набора, используя тест еще раз, были обнаружены диски, не содержащие корня $p$ можно удалить. С каждым из оставшихся дисков эту процедуру закрытия и удаления можно повторить сколько угодно раз, в результате чего получится набор сколь угодно малых дисков, которые вместе содержат все корни $p$.

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

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