Алгоритм Лемера–Шура
Алгоритм поиска корня

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

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

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

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

Т п = п ( 0 ) ¯ п − п ∗ ( 0 ) ¯ п ∗ , {\displaystyle Tp={\overline {p(0)}}p-{\overline {p^{*}(0)}}p^{*},}

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

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

Лемма

Пусть — комплексный многочлен и . п {\displaystyle p} δ = ( Т п ) ( 0 ) {\displaystyle \delta =(Tp)(0)}

  • Корни , включая их кратности , являются образами при инверсии в единичной окружности ненулевых корней . п ∗ {\displaystyle p^{*}} п {\displaystyle p}
  • Если , то и имеют общие корни на единичной окружности, включая их кратности. δ ≠ 0 {\displaystyle \delta \neq 0} п , п ∗ {\displaystyle п,\,п^{*}} Т п {\displaystyle Тп}
  • Если , то и имеют одинаковое число корней внутри единичной окружности. δ > 0 {\displaystyle \дельта >0} п {\displaystyle p} Т п {\displaystyle Тп}
  • Если , то и имеют одинаковое число корней внутри единичной окружности. δ < 0 {\displaystyle \дельта <0} п ∗ {\displaystyle p^{*}} Т п {\displaystyle Тп}
Доказательство

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

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

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

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

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

  • Все корни лежат внутри единичной окружности тогда и только тогда, когда p {\displaystyle p}

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

  • Все корни лежат вне единичной окружности тогда и только тогда, когда p {\displaystyle p}

δ k > 0 {\displaystyle \delta _{k}>0} для и . k = 1 , … , K {\displaystyle k=1,\ldots ,K} d K = 0 {\displaystyle d_{K}=0}

  • Если и если для (в порядке возрастания) и в противном случае, то не имеет корней на единичной окружности и число корней внутри единичной окружности равно d K = 0 {\displaystyle d_{K}=0} δ k < 0 {\displaystyle \delta _{k}<0} k = k 0 , k 1 … k m {\displaystyle k=k_{0},k_{1}\ldots k_{m}} δ k > 0 {\displaystyle \delta _{k}>0} p {\displaystyle p} p {\displaystyle p}
∑ i = 0 m ( − 1 ) i d k i − 1 {\displaystyle \sum _{i=0}^{m}(-1)^{i}d_{k_{i}-1}} .

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

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

Метод Лемера

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

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

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

Ссылки

  1. ^ Кон, А (1922). «Uber die Anzahl der Wurzeln einer алгебраишен Gleichung in einem Kreise». Математика. З.​ 14 : 110–148. дои : 10.1007/BF01215894. hdl : 10338.dmlcz/102550 . S2CID  123129925.
  2. ^ ab Henrici, Peter (1988). Прикладной и вычислительный комплексный анализ. Том I: Ряды степеней — интегрирование — конформное отображение — расположение нулей (Перепечатка оригинала, опубл. 1974 г. John Wiley \& Sons Ltd., Мягкая обложка). Нью-Йорк и т. д.: John Wiley. стр. xv + 682. ISBN 0-471-60841-6.
  3. ^ Марден, Моррис (1949). Геометрия нулей полинома комплексной переменной . Математические обзоры. № 3. Нью-Йорк: Американское математическое общество (AMS). стр. 148.
  4. ^ Шур, I (1917). «Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind». Журнал для королевы и математики . 1917 (147): 205–232. дои : 10.1515/crll.1917.147.205. S2CID  199546483.
  5. ^ Лемер, Д. Х. (1961). «Машинный метод решения полиномиальных уравнений». Журнал Ассоциации вычислительной техники . 8 (2): 151–162. doi : 10.1145/321062.321064 . S2CID  17667943.
  6. ^ Стюарт, GWIII (1969). «О методе Лемера для нахождения нулей многочлена». Math. Comput . 23 (108): 829–835. doi :10.2307/2004970. JSTOR  2004970.
  7. ^ Loewenthal, Dan (1993). «Улучшение метода обнаружения корней Лемера-Шура». J. Comput. Phys . 109 (2): 164–168. Bibcode :1993JCoPh.109..164L. doi :10.1006/jcph.1993.1209.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Lehmer–Schur_algorithm&oldid=1249934629"