Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Сандық талдауда Бейрстоу әдісі – кез келген дәрежедегі нақты көпмүшенің түбірлерін табуға арналған тиімді алгоритм. Алгоритм алғаш рет 1920 жылы Леонард Бейрстоудың "Қолданбалы аэродинамика" кітабының қосымшасында жарияланды. Алгоритм нақты арифметиканы ғана қолдана отырып, кешенді жұп түбірлерді табады. Басқа алгоритмдер туралы мәліметтер үшін түбір табу алгоритміне қараңыз.
In numerical analysis, Bairstow's method is an efficient algorithm for finding the roots of a real polynomial of arbitrary degree. The algorithm first appeared in the appendix of the 1920 book Applied Aerodynamics by Leonard Bairstow. The algorithm finds the roots in complex conjugate pairs using only real arithmetic. See root finding algorithm for other algorithms.
Өнер көрсету
Бейрстоу алгоритмі Ньютон әдісінің жергілікті квадраттық конвергенциясын мұра етеді, бірақ 1-ден жоғары сандық квадраттық факторлар болған жағдайда, сол факторға қатысты конвергенция сызықтық болады. Полиномиалдың тақ дәрежесі және тек бір нақты түбірі болған кезде ерекше тұрақсыздық байқалады. Бұл нақты түбірде кіші мәнді квадраттық факторлар шексіздікке ұмтылады. Суреттер t > 0 жоғарғы жартысы жазықтықтағы нүктелерді жұптар түрінде көрсетеді, олар түбірлері бар сызықтық факторларға сәйкес келеді, яғни t < 0 төменгі жартысы жазықтықтағы нүктелер түбірлері бар квадраттық факторларға сәйкес келеді, яғни , сондықтан әдетте нүктелер Бейрстоу итерациясының соңғы нүктесіне сәйкес түспен боялады, ал қара нүктелер дивергентті мінез-құлықты көрсетеді. Бірінші сурет жалғыз нақты түбір жағдайын көрсетеді. Екінші сурет конвергенция жылдамдығын төмендету есебінен қосымша нақты түбірді енгізу арқылы дивергентті мінез-құлықты түзетуге болатынын көрсетеді. Сонымен қатар, тақ дәрежелі полиномиалдар үшін Ньютон әдісі және/немесе аралықты тарылту әдісін қолданып, алдымен нақты түбірді табуға болады, содан кейін дефляциядан кейін жақсырақ мінез-құлыққа ие жұп дәрежелі полиномиал қалдырылады. Үшінші сурет жоғарыдағы мысалға сәйкес келеді.
Bairstow's algorithm inherits the local quadratic convergence of Newton's method, except in the case of quadratic factors of multiplicity higher than 1, when convergence to that factor is linear. A particular kind of instability is observed when the polynomial has odd degree and only one real root. Quadratic factors that have a small value at this real root tend to diverge to infinity. The images represent pairs Points in the upper half plane t > 0 correspond to a linear factor with roots , that is Points in the lower half plane t < 0 correspond to quadratic factors with roots , that is, , so in general Points are colored according to the final point of the Bairstow iteration, black points indicate divergent behavior. The first image is a demonstration of the single real root case. The second indicates that one can remedy the divergent behavior by introducing an additional real root, at the cost of slowing down the speed of convergence. One can also in the case of odd degree polynomials first find a real root using Newton's method and/or an interval shrinking method, so that after deflation a better behaved even degree polynomial remains. The third image corresponds to the example above.