Кіріспе
Көпмүшелік бағалау алгоритмі
Математика және информатикада Хорнер әдісі (немесе Хорнер схемасы) – көпмүшелік бағалау алгоритмі. Уильям Джордж Хорнер есімімен аталғанымен, бұл әдіс әлдеқайда көне, өйткені оны Хорнердің өзі Жозеф Луи Лагранжға жатқызған, ал оның тамырларын қытай және парсы математиктерінен бірнеше ғасыр бұрын табуға болады. Компьютерлер енгізілгеннен кейін, бұл алгоритм көпмүшеліктермен тиімді жұмыс істеу үшін маңызды рөл атқарды. Алгоритм Хорнер ережесіне негізделген, онда көпмүше ұялы түрде жазылады:
Бұл n дәрежелі көпмүшелікті бағалау үшін тек көбейту және қосу операцияларын қажет етеді. Бұл ең жақсы нәтиже, себебі n дәрежелі көпмүшеліктердің кейбіреулерін одан аз арифметикалық операциялармен бағалау мүмкін емес. Басқаша айтқанда, Хорнер әдісі 1819 жылы Хорнер сипаттаған көпмүшеліктердің түбірлерін табу әдісін де білдіреді. Бұл Хорнер ережесін қолдану арқылы қолмен есептеуді жеңілдететін Ньютон-Рафсон әдісінің бір түрі. Бұл әдіс 1970 жылға дейін, компьютерлер кеңінен қолданысқа енгенге дейін жиі қолданылды.
Тиімділік
Бір дәрежелі көпмүшенің мономиалды түрін пайдалану арқылы бағалау, егер дәрежелер қайталанған көбейту арқылы есептелсе және әрбір мономиал жеке-жеке бағаланса, ең көп дегенде қосылулар мен көбейтулерді қажет етеді. Итерация арқылы дәрежелерді бағалау арқылы бұл сан қосылулар мен көбейтулерге дейін азайтылуы мүмкін. Егер сандық деректер цифрлар (немесе биттер) түрінде ұсынылса, онда қарапайым алгоритм шамамен : тің биттерінің санынан еселенген санын сақтауды талап етеді, өйткені бағаланған көпмүшенің шамамен шамасын сақтау қажет, сондай-ақ өзінің мәнін де сақтау керек. Керісінше, Хорнер әдісі тек қосылулар мен көбейтулерді қажет етеді, ал оның сақтау талаптары тек : тің биттерінің санынан бірнеше есе көп. Хорнер әдісін көпмүшенің бірінші туындыларын бағалау үшін де қолдануға болады, бұл үшін қосылулар мен көбейтулер қажет. Хорнер әдісі оңтайлы, себебі кез келген алгоритм кез келген көпмүшені бағалау үшін кем дегенде осындай операцияларды қолдануы керек. Александр Островский 1954 жылы қажетті қосылулардың саны ең аз екенін дәлелдеді. Виктор Пан 1966 жылы көбейтулердің саны ең аз екенін дәлелдеді. Дегенмен, егер : матрица болса, Хорнер әдісі оңтайлы емес. Бұл көпмүше мономиалды түрінде бағаланады және бейнелеудің алдын ала шартталуына рұқсат етілмейді деп есептеуді білдіреді, бұл көпмүше тек бір рет бағаланса мағыналы. Бірақ, егер алдын ала шартталуға рұқсат берілсе және көпмүше көп рет бағаланса, онда жылдам алгоритмдер мүмкін болады, олар көпмүшенің бейнелеуін түрлендіруді қамтиды. Жалпы, дәрежелі көпмүше тек +2 көбейту және қосылу арқылы бағаланады.
Жылжымалы нүктемен көбейту мен бөлуді қолдану
Хорнер әдісі - аппараттық көбейтушісіз микробасқарушыда екілік сандарды көбейту және бөлудің жылдам әрі кодты тиімді әдісі. Көбейтілетін екілік сандардың біреуі тривиалды полином түрінде көрсетіледі, онда (жоғарыда аталған белгілерді пайдаланып), және содан кейін x (немесе x-тің белгілі бір дәрежесі) қайта-қайта көбейткіш түрінде шығарылады. Бұл екілік сандар жүйесінде (2-ші негізде) , сондықтан 2-нің дәрежелері қайта-қайта көбейткіш түрінде шығарылады.
Мысал
Мысалы, екі санның (0,15625) және m көбейтіндісін табу үшін:
Басқа қолданбалар
Хорнер әдісі әр түрлі позициялық сандық жүйелерді түрлендіру үшін қолданылуы мүмкін – мұндай жағдайда x сандық жүйенің негізі болып табылады, ал ai коэффициенттері берілген санның x негізіндегі жазылуының цифрлары болып табылады. Сондай-ақ, егер x матрица болса, оны қолдануға болады, бұл жағдайда есептеу тиімділігінің артықшылығы одан да зор. Дегенмен, мұндай жағдайлар үшін одан да жылдам әдістер белгілі.
Көптік түбірді табу
Ұзын бөлу алгоритмін Ньютон әдісімен біріктіре қолдану арқылы полиномның нақты түбірлерін жуықтауға болады. Алгоритм былай жұмыс істейді: нөлдері бар, дәрежесі полином берілгенде, бастапқы шаманы жасаңыз, осылайша . Содан кейін келесі екі қадамды қайталаңыз:
Using Newton's method, find the largest zero of using the guess Using Horner's method, divide out to obtain Return to step 1 but use the polynomial and the initial guess
These two steps are repeated until all real zeros are found for the polynomial. If the approximated zeros are not precise enough, the obtained values can be used as initial guesses for Newton's method but using the full polynomial rather than the reduced polynomials.
1. Ньютон әдісін қолданып, шамадан ең үлкен нөлді табыңыз.
2. Хорнер әдісін қолданып, бөліп алып, полиномды табыңыз.
Using Newton's method, find the largest zero of using the guess Using Horner's method, divide out to obtain Return to step 1 but use the polynomial and the initial guess
These two steps are repeated until all real zeros are found for the polynomial. If the approximated zeros are not precise enough, the obtained values can be used as initial guesses for Newton's method but using the full polynomial rather than the reduced polynomials.
1-қадамға қайта оралыңыз, бірақ полиномды және бастапқы шаманы пайдаланыңыз. Бұл екі қадам полиномның барлық нақты түбірлері табылғанша қайталанады. Егер жуықталған түбірлер жеткілікті дәл болмаса, алынған мәндерді Ньютон әдісі үшін бастапқы шама ретінде пайдалануға болады, бірақ қысқартылған полиномдардың орнына толық полиномды қолдану керек.
Using Newton's method, find the largest zero of using the guess Using Horner's method, divide out to obtain Return to step 1 but use the polynomial and the initial guess
These two steps are repeated until all real zeros are found for the polynomial. If the approximated zeros are not precise enough, the obtained values can be used as initial guesses for Newton's method but using the full polynomial rather than the reduced polynomials.