Кіріспе
Математикада, бөлу шеңбері әдісі – полиномды сандық түрде жіктеу және, нәтижесінде, оның кешенді түбірлерін табуға арналған сандық алгоритм. Оны 1982 жылы Арнольд Шёнхаге «Есептеу күрделілігі тұрғысынан алгебраның негізгі теоремасы» деген мақаласында (Техникалық есеп, Тюбинген университетінің математика институты) енгізген. 1998 жылы Виктор Пан осы алгоритмді жаңартылған түрінде ұсынды. 1996 жылы Ксавье Гурдон Magma және PARI/GP компьютерлік алгебра жүйелері үшін оны іске асырды.
Жалпы сипаттама
Бөліну шеңбері әдісінің негізгі идеясы – күрделі талдау әдістерін, атап айтқанда, қалдық теоремасын пайдаланып полиномиалдардың көбейткіштерін құру. Осы әдістер арқылы, бөлшекті тегіс шекарасы бар күрделі жазықтықтың кез келген аймағы үшін берілген полиномияның көбейткішін құруға болады. Көптеген көбейткіштер тривиалды, яғни тұрақты полиномиалдар болады. Тек p(x) түбірлерін қамтитын аймақтар ғана, көптілігін сақтай отырып, дәл сол p(x) түбірлерін өз түбірлері ретінде қамтитын тривиалды емес көбейткіштерге әкеледі. Бұл әдістің сандық жүзеге асыруында күрделі жазықтықтағы D(c,r) (орталығы c, радиусы r) дискілері аймақтар ретінде қолданылады. Диск шеңбері p(x) түбірлерінің жиынын екі бөлікке бөледі, сондықтан әдіс осылай аталды. Берілген дискіге қатысты аналитикалық теорияға сүйене отырып шамамен көбейткіштер есептеледі, содан кейін олар Ньютон әдісімен жақсартылады. Сандық тұрақсыздықтан сақтану үшін, барлық түбірлер диск шеңберінен жеткілікті қашықтықта болуы керек. Жақсы бөліну шеңбері алу үшін, оны үлкен салыстырмалы ені R/r болатын, түбірлері жоқ A(c,r,R) (орталығы c, ішкі радиусы r, сыртқы радиусы R) сақинасына ендіру керек. Осы процесті табылған көбейткіштер үшін қайталап, қажетті дәлдікте полиномияның шамамен көбейткішін аламыз. Көбейткіштер – жақсы оқшауланған нөлдерді көрсететін сызықтық полиномиалдар немесе нөлдердің кластерлерін көрсететін жоғары дәрежелі полиномиалдар болады.
Негізгі сандық байқау
n дәрежелі көптік болсын, оның радиусы 1/2 шеңберінің ішінде k нөлдері және радиусы 2 шеңберінің сыртында қалған n-k нөлдері бар. N=O(k) жеткілікті үлкен болса, N нүктелерді пайдаланып контурлы интегралдарды жуықтау f көбейткішінің жуықтауын береді, қатесі мынадай:
мұнда көпмүшенің нормасы – оның коэффициенттерінің модульдерінің қосындысы. Көпмүшенің нөлдері оның коэффициенттеріне байланысты үздіксіз болғандықтан, N жеткілікті үлкен болса, көпмүшенің нөлдерін f нөлдеріне қалағанша жақын етуге болады. Дегенмен, Ньютон әдісін қолдану арқылы бұл жуықтауды жылдамдатуға болады. p-ді қалдықпен бөлу қалған g көбейткішінің жуықтауын береді. Енді
сонда соңғы екінші реттік мүшені жоққа шығарып, кеңейтілген Евклид алгоритмінің кез келген түрін пайдаланып, жуықталған шамаларды алу үшін шешу керек және. Бұл қадамдар таңдалған дәлдікке сәйкес инкременттер нөлге жететінше қайталанады.
Графикалық итерация
Бұл әдістің маңызды қадамы – күрделі жазықтықта p-нің нөлдері жоқ, ал ішінде p-нің нөлдері сыртындағыдай шамамен бірдей саны бар, 4-ке тең салыстырмалы ені бар сақинаны табу. Мұндай қасиеттері бар кез келген сақинаны полиномды ауыстыру және масштабтау арқылы, нөлдік нүктеден 1/2 және 2 радиустары арасындағы сақинаға түрлендіруге болады. Бірақ, әр полиномда мұндай бөлінетін сақина болмайды. Бұл жағдайды түзету үшін Graeffe итерациясы қолданылады. Ол полиномдар тізбесін есептейді, онда -нің түбірлері бастапқы полиномның p түбірлерінің dyadik қуаттары болып табылады. -ні жұп және тақ бөліктерге бөлу арқылы, келесі полином таза арифметикалық амалдар арқылы алынады, себебі түбірлердің абсолютті модульдерінің қатынасы бірдей қуатпен артады және осылайша шексіздікке ұмтылады. j-ді жеткілікті үлкен етіп таңдағанда, нөлдік нүктеден 4-ке тең салыстырмалы ені бар бөлінетін сақина табылады. Енді -нің шамаменгі факторлануын бастапқы полиномға қайтару керек. Осы мақсатта Ньютон қадамдары мен Паде жуықтамаларының кезектесіп қолданылуы пайдаланылады. Тексеру оңай, келесі теңдік орындалады. Сол жақтағы полиномдар j қадамында белгілі, ал оң жақтағы полиномдар сол жақтағы бөлшектің қуатты қатарға кеңейтуі үшін тиісті дәрежедегі Паде жуықтамалары ретінде алынуы мүмкін.
where the roots of are the th dyadic powers of the roots of the initial polynomial p. By splitting into even and odd parts, the succeeding polynomial is obtained by purely arithmetic operations as The ratios of the absolute moduli of the roots increase by the same power and thus tend to infinity. Choosing j large enough one finally finds a splitting annulus of relative width 4 around the origin. The approximate factorization of is now to be lifted back to the original polynomial. To this end an alternation of Newton steps and Padé approximations is used. It is easy to check that
holds. The polynomials on the left side are known in step j, the polynomials on the right side can be obtained as Padé approximants of the corresponding degrees for the power series expansion of the fraction on the left side.
Жақсы шеңберді табу
Грейффе итерациясын және ең үлкен түбірдің абсолюттік мәнінің кез келген белгілі бағасын пайдаланып, кез келген дәлдіктегі осы абсолюттік мәннің R бағасын табуға болады. Енді p(x) полиномының кез келген түбірінің 0, 2R, −2R, 2Ri, −2Ri бес орталық нүктесіне дейінгі ең үлкен және ең кіші қашықтықтарын есептеп, олардың арасындағы ең үлкен қатынасты таңдаймыз. Осы құрылым арқылы кем дегенде бір орталық үшін кепілдік беруге болады. Мұндай орталық үшін салыстырмалы ені бар түбірсіз аймақ болуы керек. Грейффе итерацияларынан кейін, итерацияланған полиномға сәйкес аймақтың салыстырмалы ені жоғарыда сипатталған бастапқы бөлу үшін қажетті 11 > 4-тен артық болады. Грейффе итерацияларынан кейін, сәйкес аймақтың салыстырмалы ені артық болады, бұл бастапқы бөлуді әлдеқайда жеңілдетуге мүмкіндік береді.
To locate the best root free annulus one uses a consequence of the Rouché theorem: For k = 1, , n − 1 the polynomial equation
u > 0, has, by Descartes' rule of signs zero or two positive roots In the latter case, there are exactly k roots inside the (closed) disk and is a root free (open) annulus.
Ең жақсы түбірсіз аймақты табу үшін Руше теоремасының салдары қолданылады: k = 1, …, n − 1 үшін u > 0 полиномиялық теңдеуі Декарттың белгілер ережесі бойынша нөл немесе екі оң түбірге ие. Соңғы жағдайда, (жабық) диск ішінде дәл k түбір болады және аймақ түбірсіз (ашық) аймақ болады.
To locate the best root free annulus one uses a consequence of the Rouché theorem: For k = 1, , n − 1 the polynomial equation
u > 0, has, by Descartes' rule of signs zero or two positive roots In the latter case, there are exactly k roots inside the (closed) disk and is a root free (open) annulus.