Введение
В математике алгоритм Лемера — Шура (названный в честь Деррика Генри Лемера и Иссаи Шура) — это алгоритм поиска корней комплексных многочленов, расширяющий идею локализации корней, подобно методу бисекции в одномерном случае, на комплексную плоскость. Он использует критерий Шура — Кона для проверки всё более и более маленьких дисков на наличие или отсутствие корней.
Метод Лемера
Метод Лемерса заключается в следующем. Для заданного комплексного многочлена, с помощью теста Шура — Кона можно найти круговой диск, достаточно большой, чтобы содержать все корни. Затем этот диск можно покрыть набором перекрывающихся меньших дисков, один из которых размещен концентрически, а остальные равномерно распределены по кольцевой области, которую еще предстоит покрыть. Из этого набора, повторно используя тест, можно удалить диски, не содержащие корней. Для каждого из оставшихся дисков эта процедура покрытия и удаления может быть повторена любое количество раз, в результате чего получится набор произвольно малых дисков, которые вместе содержат все корни.
The merits of the method are that it consists of repetition of a single procedure and that all roots are found simultaneously, whether they are real or complex, single, multiple or clustered. Also deflation, i. e. removal of roots already found, is not needed and every test starts with the full precision, original polynomial. And, remarkably, this polynomial has never to be evaluated. However, the smaller the disks become, the more the coefficients of the corresponding 'scaled' polynomials will differ in relative magnitude. This may cause overflow or underflow of computer computations, thus limiting the radii of the disks from below and thereby the precision of the computed roots. To avoid extreme scaling, or just for the sake of efficiency, one may start with testing a number of concentric disks for the number of included roots and thus reduce the region where roots occur to a number of narrow, concentric annuli. Repeating this procedure with another centre and combining the results, the said region becomes the union of intersections of such annuli. Finally, when a small disk is found that contains a single root, that root may be further approximated using other methods, e. g. Newton's method.
Преимущества метода заключаются в том, что он состоит из повторения одной и той же процедуры и в том, что все корни находятся одновременно, независимо от того, являются ли они вещественными или комплексными, простыми, кратными или сгруппированными. Также не требуется дефляция, то есть удаление уже найденных корней, и каждый тест начинается с полной точности, исходного многочлена. И, что примечательно, сам многочлен никогда не вычисляется. Однако, чем меньше становятся диски, тем сильнее различаются по относительной величине коэффициенты соответствующих "масштабированных" многочленов. Это может привести к переполнению или потере значимости при компьютерных вычислениях, тем самым ограничивая радиусы дисков снизу и, следовательно, точность вычисленных корней. Чтобы избежать чрезмерного масштабирования или просто ради повышения эффективности, можно начать с проверки ряда концентрических дисков на количество содержащихся в них корней и, таким образом, сузить область, где находятся корни, до ряда узких концентрических кольцевых областей. Повторив эту процедуру с другим центром и объединив результаты, указанная область станет объединением пересечений таких кольцевых областей. Наконец, когда найден небольшой диск, содержащий единственный корень, этот корень можно дополнительно приблизить, используя другие методы, например, метод Ньютона.
The merits of the method are that it consists of repetition of a single procedure and that all roots are found simultaneously, whether they are real or complex, single, multiple or clustered. Also deflation, i. e. removal of roots already found, is not needed and every test starts with the full precision, original polynomial. And, remarkably, this polynomial has never to be evaluated. However, the smaller the disks become, the more the coefficients of the corresponding 'scaled' polynomials will differ in relative magnitude. This may cause overflow or underflow of computer computations, thus limiting the radii of the disks from below and thereby the precision of the computed roots. To avoid extreme scaling, or just for the sake of efficiency, one may start with testing a number of concentric disks for the number of included roots and thus reduce the region where roots occur to a number of narrow, concentric annuli. Repeating this procedure with another centre and combining the results, the said region becomes the union of intersections of such annuli. Finally, when a small disk is found that contains a single root, that root may be further approximated using other methods, e. g. Newton's method.