Кіріспе
Математикада Лехмер-Шур алгоритмі (Деррик Генри Лехмер және Иссаи Шурдың есімдерімен аталады) — кешенді полиномдар үшін түбірлерді табу алгоритмі. Бұл алгоритм бір өлшемді екіге бөлу әдісіндегідей түбірлерді қоршау идеясын кешенді жазықтыққа кеңейтеді. Ол түбірлердің болуын немесе болмауын анықтау үшін Шур-Кон тестін пайдаланып, күшін жоғалтпай кішірейтілген дисктерді тексереді.
Лемер әдісі
Лемердің әдісі былай шартталған. Берілген күрделі көпмүше үшін, Шур-Кон тесті арқылы барлық түбірлерін қамтитын жеткілікті үлкен шеңбер тәрізді диск табылады. Бұдан кейін бұл диск, жабылатын кішірек дисктер жиынтығымен жабылады, олардың біреуі концентрлі орналасқан, ал қалғандары жабылмаған сақинаға тең бөлінеді. Осы жиынтықтан, тестті қайталап, көпмүшенің түбірін қамтымайтын дисктерді алып тастауға болады. Әрбір қалған диск үшін осы жабу және алып тастау процедурасын кез келген рет қайталауға болады, нәтижесінде барлық түбірлерін қамтитын, кез келген кішкентай дисктер жиынтығы пайда болады.
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.