Том 2 (1160084), страница 27
Текст из файла (страница 27)
Это равносильно уточнению 1-й неизвестной при неизменных остальных. ф 6. Отыскание корней алгебраических уравнений методом выделения множителей Известно, что многочлен 7 (х) = х" + а,х"-' +- ... + а„, х + а„ (1) с действительными коэффициентами может быть представлен в виде прои. ведения многочленов степени не выше двух тоже с лействи- с одним неизвестным Л, что может быть выполнено одним из описанных выше методов. Реализуя этот метод, мы на каждом шаге движемся в направлении быстрейшего убывания функции Ф.
Если начальное приближение выбрано достаточно хорошо и в окрестности искомого решения а нет других минимумов, то этот процесс быстро даст искомое решение с заданной точностью. Если в окрестности к имеются другие минимумы, то при неудачном выборе х1ф процесс сойдется, но не приведет к искомому решению. Применение метода скорейшего спуска на каждом шаге требует выполнения большой вычислительной работы. Поэтому, вместо того чтобы двигаться в направлении градиента Ф (х), можно двигаться из х<ф в направлении какого-либо другого вектора, не касательного к поверхности Ф(х) = Ф(хй).
Проще всего брать векторы в направлении координатных осей. Так, в релаксакиолном методе, дф (д4м) имея начальное приближение х1ф, вычисляют производные —, дху дф (хф1) и если — наибольшая из них, то хп> находят из условия дх~ Ф (хгл л(4) О (62) 163 методы выдвлвния множитвлвй тельными коэффициентами. Линейные множители в этом разложении соответствуют действительным корням уравнения Х(х) = — х" +-а,х"-'+ ...
+-ав гх+ая= 0, (2) а квадратичные — парам комплексно-сопряженных корней. Таким образом, имея способы разложения многочлена на множители, мы сведем задачу отыскания корней уравнения (2) к решению совсем простых уравнений. В связи с этим разработаны методы выделения действительных множителей многочлена Г'(х). При применении методов выделения множителей приходится выполнять многократно деление многочлена на мпогочлен.
т. е. находить частное и остаток. Если делитель имеет первую степень, то это удобно выполнять по схеме Горнера. Пусть требуется найти частное и остаток от деления многочлена 7 (х) = а„х" +-а,х"-' +- . +а„ ,х -+а„ (3) от деления через гг, а част- на многочлен х — г. Обозначим остаток ным пусть будет многочлен а(х) = Ь„х"-'+-Ь,х"-'+ ... +- Ь„,х+- Ь„,. (4) Тогда г'(х) = а(х)(х — г)+гс.
(5) Сравнение коэффициентов при одинаковых степенях х в правой и левой частях тождества (5) дает ао — — Ьо, аи=Ьь — Ьа,г ()а=1, 2, ..., и — 1), а„=ге — Ь„,г, (6) откуда Вычисления удобно располагать по следующей схеме — схеме Гор- нера; ав а, а, а, ... а„, а„(г Ьвг Ь,г Ьзг ... Ь„аг Ь„,г Ьо Ь1 Ьа Ьз ° ° ° Ья-г где Ьз — — ав, а каждое число нижней строки равно сумме двух чисел, стоящих над ним.
Так как из (5) видно, что гс = 7"(г), то схему Горнера удобно применять для отыскания значений многочлена 7(х) при х = г. Для отыскания частного д(х)=Ь, — +Ь, -+ ... +Ь„,х+Ьм в и остатка )г (х) = свх + с, Ь„=аа, Ь„=а„+Ьь,г (й=1. 2, ..., и — 1), )х=а„+Ь„,г. (7) 164 решение ллгевглических и тглнсцендентных гглвнений [гл. 7 от деления многочлена (3) на множитель хз+-рх +д можно исполь- зовать следующую схему: ао а, а, а, ... ап з а„, ап РЬо РЬз — РЬз ° ° ° РЬп-з РЬп-з чЬО ггь1 ° ° ЧЬп-4 ггь — 3 ЧЬп-з Ьо Ьз Ьа Ьз ... Ь, з со с, где последняя строка получается как сумма первых трех строк. Эта схема просто получается из тождества у(х) =(хз+рх+зг)3(х)+Я(х) (8) сравнением коэффициентов при одинаковых степенях х. Это дает ао=Ьо.
аз=Ь|+РЬо, а«=Ь«+РЬ« з+)Ь«з («=2, 3,..., и — 2 ап-з = оо+РЬп-з+ дЬп-з ап = фп-з+ с„ откуда следует: Ьо=ао, Ь,=а, — РЬгп Ь«=а«РЬ«-з — [Ь«-з (Ь= 2, 3, ..., и — 2), со=а -~ — РЬп-з — дЬ з, с, =ап — з)Ьп з, что и реализовано в схеме. Нетрудно сообразить, как будет выглядеть схема для определения коэффициентов частного н остатка при делении многочлена (3) на многочлен х"'+з1,х -'.+ ... + И„, зх +о[ (т ( а). 1. Метод Лина выделения множителей. Метод Лина, или метод предпоследнего остатка, выделения множителя л„,(х) степени т из многочлена у„(х) = х + а,х' -'+ ... + ап,х + а„ (1О) состоит в следующем.
За начальное приближение а;„(х) берется некоторый многочлен степени т д~, з(х) =х +Ь1нх ~+ ... +Ь~~~ зх+Ь~~~ (11) и производится деление у„(х) на лпь з(х) до тех пор, пока в остатке получится многочлен степени т — предпоследний остаток. За следующее приближение апьз(х) берется этот остаток, деленный на коэффициент при хт — приведенный предпоследний остаток, далее процесс повторяется, т. е.
если уже найдено а-е приближение к д„,(х): 3,«(х)=х"+Ь'з'х + +Ь"'- х-[-Ь' ', то азп, «+з(х) определяется как приведенный предпоследний остаток от деления многочлена уп(х) на у, «(х). Процесс продолжают до 165 мвтоды выделвния множитвлвй 6 6) тех пор„пока коэффициенты двух последовательных приближений будут совпадать в пределах заданной точности. Практически приемлемых критериев сходимости этого метода в общем случае нет. Приведем без доказательства один результат, практическая ценность которого невелика.
Если а,, а,,..., а„,— корни выделяемого множителя а„,(х), а Р„(х)=хи-™+сгхя '+ ... +с„т,х+с„,„— частное от деления у„(х) на д„,(х), т. е. у„(х)=д„,(х)Р„,„(х), то сходимость метода Лина будет иметь место в случае, когда рг=! — " м( ') (1= 1, 2, ..., т) (13) с„,„ 1„(х)=х" +а,х"-'+ ... +а„,х+а„= =(х — и! ~)(х" +с1 )х" '+ ... +-с~,!ах)+ба!!(х — и! +О), (14) гле х — а есть й+ 1-е приближение. Из этого тождества имеем: (а+0 Г ( !Ы) б<Ю( !ь> !ььн) у.
(О)= — б!оь!о!ь+О или чГЬ+ ! — ига! У, (чйо) ага+ ! у, (О) откуда „Гь +0 У„ (О) !ь! Уя (О) — У («бп) Это равенство можно рассматривать как итерацию для отыскания корни а уравнения ху„(0) х='т(х)= — у„(0) — у„( ) ' (16) (15) Так как У ОО 9 (")='+" У 0 У„(0) (1 г) по модулю меньше единицы и начальное приближение ач, г(х) выбрано достаточно близко к д„,(х). В случае, если наибольшее из них по модулю есть действительное число, то Ь вЂ” Ьг схо!ь+ 0 Рй дятся к нулю со скоростью геометрической прогрессии со знаменателем, равным модулю этого числа. При практическом применении метода Лина чаще всего выделяют линейные и квадратичные множители, так как только эти множители заранее можно определить достаточно точно и применять процесс Лина для их уточнения.
Но только в случае выделения линейных множителей, соответствующих действительным корням уравнения )'„(х) =О, можно дать простые критерии сходимости метода. Пусть выделяется множитель х — а и х — и — его и-е приблицо жение, тогда имеет место тождество 166 Решение АлГеБРАических и тРАнсцендентных РРАвнений !гл. 7 то при выполнении условия ~14'(а))(1 найдется некоторая окрестность корня х = а, в которой будет иметь место неравенство ! ~(х)~ ( л' ( 1 и итерация (15) будет сходиться, если начальное приближение а( ) взято из этой окрестности. Условие ! е'(а)< ( 1 будет иметь место, если а — наименьший по модулю корень уравнения уа(х) = О, при условии, что все корни уравнения действительны и одного знака.
В самом деле, если в этом случае расположить все корни в порядке возрастания их модулей, т. е. ! а(! ( ! а, < ( ... ( ) аа (. то уа(0) =( — 1)" а,а,... а„; 7„(ИД =(аа — а,) (а, — а,)... (а„— а,) 41Уа ("1) ( '1 ) ( ! Ч1 ) ~ 1 а1 ) ® а1 и так как все отношения — 1(1 =- 2, 3,..., и) положительны и а< меньше единицы, то (19) Пример. Выделить множитель второй степени из многочлена х'+ 7ха -1- 24х'+ 25х — 15.
В качестве начального приближения возьмем многочлен а'4 1 (х) = ха. аз " а -з л -з — Ь, — Ь, — Ь,с, — Ь1са ...— Ь,с„14 — Ь,с„з <В) <В) (4) <В) <В) 1В) ,а) <В <41 (В) <В) (В) (В) йп <В) (В) ()Ч <В) (В) <В) — Ь4 — Ьа — Ь4 с, ...— Ь1 са 4 — Ьа са-4 — Ьз са-з а„, а„ (В) (В) (В) ,!<В) , (В) <Ю .
СЗ ... С„-4 о 4(1 4(4 1 с<) где последняя строка есть сумма первых трех, при этом х"-4 ! -1-с1 х а+ ....+с„зх — предпоследнее частное, а 4, ха-)-4(1 х -)- (В) а-4 (В (В) (В) +4( — предпоследний остаток, приведем результаты вычислений <В) для данного примера. Не приводя промежуточных вычислений, которые сводятся к деле- НИЮ МНОГОЧЛЕНа Уа(Х)=Ха+а,Х" '+ ... +а„,Х+а„иа ТРЕХ- член х + Ь<, )х -1- Ь. до получения предпоследнего остатка, что можно выполнить по схеме: !67 методы выделения множителей 9 б! Приведенное частное Приведенный пред Предпоследний остаток последнии остаток л с,' ' 5(м ри Ри 1 з 5(зз з 1 1 2 1 3 1 29,9991 29,9994 29,9997 1,9999 — 0,9999 1 Последнее частное в общем случае имеет вид и-з 1з> в-з+ + <ц + ро и будет являться приближенным представлением второго множителя, дополняющего искомый множитель д (х) до ув(х).
В нашем примере посл~ 12 шагов имеем: х' (-7хз+ 24х'+-25х — 15 = (х'+- 1,9999х — 0,9999) (х'+ 5,0002х+ 15,0005). Точное разложение имеет вид хз+ 7х'+ 24х' + 25х — 15 = (х'+ 2х — 1) (х' + 5х + 15). Получили хорошее приближение, хотя начальный множитель х' далек от истинного. Если использовать полученное разложение для отыскания корней уравнения хз+ Уха+ 24х' — 15 = О, то получим для корней следующие значения: х, = — 2,4141, х, = 0,4142, хз з = — 2,5001 + 2,95811. Истинные же значения корней с четырьмя верными десятичными знаками: х, = — 2,4142, хз = 0,4142, хз,з = — 2,5000 + 2,9581з'.
2. Метод фридмана. Метод Фридмана выделения множителя а (х) многочлена ув(х) не обладает таким единообРазием, как метод Лина В методе Фридмана, если п,л(х) есть й-е приближение искомого 4 5 7 8 9 10 11 12 1,042 1,5597 1,8024 1,9147 1,9639 1,9849 1,9937 1,9974 1,9989 1,9996 1 9998 — 0,625 — 0,8145 — 0,91 9з — 0,9646 — 0,9850 — 0,9937 — 0,9974 — 0,9989 — 0,9996 — 0,9998 — 0,9999 7 5,957 5,4403 5,1976 5,0853 5,0361 5,0151 5,0063 5,0026 5,0011 5,0002 24 18,4168 16,3293 15,5504 15,2278 15,0946 15,0392 15,0163 15,0067 15,0029 15,0010 15,0005 25 --15 27,7238 15 29,4311 29,7745 29,9053 29,9606 29,9835 29,9933 29,9971 168 гвшвнив ллгввглнчвс«ик н тглнсцвндвнтнык тглвнвннй (гл.
Ч а) а(х) =х — а (ю (20) то в результате деления Гв(х) на а1 а(х) получим: (в) „=х" '+Ь',"'х" Я+ ... +Ьв("ах+Ьв"),+ " „, (21) х — а( ) х — «( ) откуда )а) Г (а)т. Ь(Ы Ги (ч ) Гч (О), гв = у„~а а(а) 1 У (х) — гйв — Ь(") (х — я(")) Ь„а — Иш (22) х (х — ч(Ю) х.ь о (а) з При делении многочлена ув(х), расположенного по возрастаюц(им степеням, на многочлендв(х)=Ь(„") )+.Ь(„") ах+... +Ь(,")х" +х" ' до получения частного первой степени находим следующее частное) которое после деления на коэффициент при х приобретет вид (а+)) авав 1 (ю мк ь+) (х) = х — а = х— (а) (а) а„Ь„) — а„,Ь„), (23) множителя я„,(х), для получения (й + 1)-го приближения поступают СЛЕдуЮщИМ ОбраЗОМ: дЕЛят МНОГОЧЛЕН Г„(Х) На ув Ь(Х) таК жЕ, КаК и в методе Лина, но только до получения последнего остатка; полученное частное располагают по возрастающим степеням х и делят на него многочлен у„(х), расположенный также по возрастающим степеням х, до тек пор, пока в частном получится многочлен степени т; это частное, деленное на коэффициент при х"', и принимают за ум,ь+)(х) О скание каждого приближения по методу Фридмана тре уе более чем в два раза больше операций, чем в методе Лина, но в некоторых случаях метод Фридмана имеет значительно лучшую сходимость, чем метод Лина.
Это можно проиллюстрировать на примере выделения линейного множителя, соответствующего наименьшему по абсолютной величине корню уравнения г'„(х)=0, если это уравнение имеет только действительные корни и одного знака. В самом деле, если искомый линейный множитель имеет вид х — а, а й-е приблигкение его есть 169 методы выделения множителей э 6! откуда, принимая во внимание равенства (22), будем иметь: !а+1) Уя (О) (уя (айо) — Дя (0)1 ас"! у„(ОЯ„(яс'!) -у„(о)) у„'(о) у„(,са>) .с~> ' (24) (25) !Ф'(а)1= 1 — "," <1. у'„(о) (27) Если все корни а,, аа, ..., а„ действительны, одного знака н (28) (1= 2, 3, ..., и), /ас! < ~ас/ то У„' (О) = 1 — (1 + — '+ — '+...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
