Корн Г.А., Корн Т.М. - Справочник по математике для ученых и инженеров (947387), страница 151
Текст из файла (страница 151)
20.2-2, с), Сходимосгь этих и излагаемых ниже другнл мета«аз итерации зависит ат выбора . ачальиого приближения, Начальное првблнжеияе чожет быть получено илн из прел««- рительиого исследования, или нз квадратичной интерполяции функции 1(г), яли металвмя п, 20.2.б, При отсутствии такой информации ияотда можае выбирать в на~естве начального приближения нуль нлн палас действительное чясло. Н случве иомплеисныг корней применит«в схема Горнера для номпленснаго аргумента, если толька 1(г) есть многочлен с действвтельиымн наэффициентами; при зтоья в качестве начального орнближеиия важна испытать такое число а + Ф, которое минимизирует величины 1 А; и 1 Э ! в Указанной схеме.
Как толька найДен аДнн ив коРией «а, можно РазДелить многочлсн 1(г) на (г — га) и затем в качестве начальнага приближения для следующего корня можно выбиРать га или г (1.1. с), Для камплексвыг норис(я методы Мюллера и Бэрстоу упрощают вычисления и обеспечивают более быструю с«адимость, чем метод Ньютона, есля корне блн«нн друг н другу, 657 20,2-5. Таблица 20*'.1 л, ар 012! — ! где Е[11= "' 0 а, (20,2-20Ь) 0[21 0 ,И л[7-Ч ,П вЂ” !1 — (!-21 Е[!! 1 0[2! 1 ( =-~) Е[1 1 Е[2! 1 Е[а 11 4-л Иш !4[а!лл ! чз (20.2-21а) (20.2-23) В В[ 1=0, ! со (20.2-24) для каждого ! по фор- 2, ..., л), (20.2-210) (20.2-22) 666 ГЛ. 20. ЧИСЛЕННЬЩ МЕТОДЫ И КОНЕс!НЫЕ РАЗНОСТИ 20.2-0.
(Ц Метод Мюллера. Вместо линейной интерполяаии метода секущих здесь применяется квадратичная интерполяция, что приводит к итераш!и вида 2[1+')=г['! — (г[П вЂ” г[! '!) ' Нйп ВЬ (20ЕР20а) ) В! )+)! ВЧ вЂ” 4А!Су л,.=й,)7 — йу(1+О,) ),;+О!)7 2, В,.=(20 + 1) )у — (1+Ой)2'[,,+Ч!!7 м С;=(1+0!) (Л 1;=[(г[г)), )[ля начала решения можно положить 2[01= — 1, г['1=1, 2[21=0 (с=ил — ал,-(-ал 2+ ..„(,=ал-( ал,+ал,+..., уа=ал. Метод Мюллера распространяется также н на нсалгебранческне уравнения. (с) М е т о д Б э р с т о у.
Пусть многочлен (16) содержит квадратный множитель гз — иг — о, определя!ощив два различных простых корня уравнения (18), и пусть известны достаточно хорошие начальные приближения и щ! и о[0! для и и о. Тогда последовательность лучших приближений, сходящихся к и п о, дается формулами Ь[!!4[1! — Ь[1! с[!! П !.1! [П л гл-3 л — !гл-2 ( '- )' —— л — 2) л — 1 л-3 Ь[!1 г[!! — Ь[!!с[!! П.! !! [П л — 1гл — 1 л сл — 2 — с[ ! г[!1 1' — 2) с» — 1гл — 3 ! где величины Ь['1, с[1! вычисляются последовательно а ' а мулам Ь['! а +и[!!Ь[1! +0[1!Ь[!! с'„"=Ь['!+и[(!сл[1' !+о[!1с[!1, Ь[1! =Ь[П =с[11, =сИ = О. Этот метод более удобен для многочленов четной степени.
20.2-5. Специальные методы решения алгебраических уравнений. (а) Алгоритм разделенных разностей. Этот метод, обобщающий классический метод Бернулли, может давать пркблнх!ения ко всем корням алгебраического уравнения (18) за один цикл расчета Ов применяется така!е для получения на~!алы!ых приближений в н!ерационпых методах. Вычисления располага!от по схеме табл. 20.2-1, где [)[а! С![0! ( (В[ь! БГ01 ) !х1 20.2 ЧИСЛЕННОЕ РЕШЕНИЕ УРЛВ!!ЕНИН Таблица алгоритма разделенных разностей Вычисления становятся невозможными, если !2[ ! илн Е[а! обращается 1-1- 1 в нуль. Тем нс менее, метод разделенных разностей эффективен во многих частных случаях.
Например, если все л корней г,, г,, ..., г„уравнения (18) положительны илн если все корни являются простыми с различными ненулевыми абсолютнымн величинами, то для каждого й имеем так что каждый стллбей таблицы 20.2-1 дает приближение к корто. Вообн!е, пусть ' г, 1= ' г 1зв...га! г„~ ) О. Если алгоритм разделенных разностей не отказывает, аю формула (23) дает каждый корень гл, который ога!ичас!лся ло абго ион!ной селичине от соседних с лил! в указинной аьние последовательности, а фоомула (24) остается справедливой при ) га,' ) 1 гам 1. Это помогает укааать корни с равньгап абсолютными величинами, наяриыер, сопряженные ко!!плекспые корни. (Ь) Метод Греффе — Лобачевского.
Если дано алгебраическое уравнение с дсйствительпычн коэффициентами 7 (г) = — И (г — гл) =— гл+ а,гл т-(-...-1- ал= О, 2=1 то сначала находят нозффнцненты а!" многочлена л 1 (г) 1'( — г) == ( — 1)л Ц (гз — 21) — ( — 1)л (г )л + а" ,(гз)л ! + ... + а„". 0=-1 зол-в. 659 С помощью таблицы ! П) ', г !')ь' при )-ъсо. ай)  — 2 1 О ... О 0 (20.2-28) о о ... о — — в — е я- ''' т 1 1 — а и о(!) и- 2 о(!) а(!) в(!) и — ! (20.
2-27) х!'" !)=х())+ А(!)Р(()1 ! о(1 )2льг 1 прн 1- со. в(!) й-г (20.2.25) ! а()) — )г)ю при 1'- со, РО) ва-1 ;.56 Гл. 20. численные методы и конечные РАЕИОсти 20 2.0. Повторяя этот процесс, получают последовательао коэффициенты и,") много.
членов и ( — 1)" П (г ( — гд)) — н( — 1)" (гз()"+а(!) (г ')" 1+...+О()), а 1 При возрастании 1 столбцы в расчетных таблицах оказываются одного из трех типов: 1) В некоторых столбцах удвоенные произведения становятся пренебрежимо малыми, так что последовательные записи в этих столбцах становятся квадратами с одинаковыми знакамн (провилькав столбцы): если последовательные записи имеют одинаковые анаки, а их абсолютные значения оказываются разными определенной доле квадрата предыдущего аначеяия, то мы имеем чнстикно провильнав столбца.
2) Записи столбцов могут иметь чередующиеся знаки (колеблющиеся столбца). 3) Некоторые столбцы могут не обладать указанной выше правильностью. Каждая пора правильнах столбцов (нопример, й и й — г), разделенная г — 1 непроеильнами столбцами, соответствует г корням г с ровными моду. лами такими, что Эти г корней все либо действительны, либо чисто мнимы, если г — 1 разделяющих столбцов частично правильны, В частности) 1. Дза соседних правильных столбца (например, й и й — 1) определяют простой действительный корене г такой, что 20.2.
ЧИСЛЕННОЕ РЕШЕНИЕ УРАНИЕНИЙ 2 Два правильных столбпа (й н й — 2), разделенные одняч колебл !Оп столбпо оцрслеЛ т пару ' ростах ко„.лс „„ сопряженных корнеи г таких что На практике сначала находят действительные корни н чисто мнимые; знаки определяют подстановкой илн с помощью п. !.6-0. Затем упроц(ают уравнение делением на выделенные множители. (с) Метр и ч и ы й метод, Корни алгебрам юского уравнения (!8) и-й степени с а» =- ! ме>кпб вычнслять кмс собственные»печения (и Х к).матрицы однпч ~гс методов, апис»нных в п. 20Л-5 к песне о (а!Меток Ге яе е. Мего Гя я Р Р .. к яряерь (4 н д й свнтевь«ых не веа) све нтся ся новьтевьному вычнсленн:о йоэФэи»(и«нтск мкогочленев н, и) = =й,, Г == к (и-!.
с,), ... пе схеме Горнерв, где с„с..., вы — д „с, выбнцеютсяи тьк, чтобы умейьшнт м стеткев, сля удается получить г (О) ж О, то искомый корень приблнженно ревев с -Ь с .(-... + с, ср 20.2-6. С 12.5-6, 20.2-2 и 20.2-3). истемы уравкений и экстремальные задачи (см. также пп. 11.1-1, (а) Постановка задачи. Итерадионные методы. За ача решения системы и уравненнй адача 7((х>, х,, ..., х„) = 0 (( = 1, 2, ..., и) с и неизвестными х, х, ..., Р х„..., х„эквивалентна задаче минимизации функции е Р(х„х„..., х„) = ~~ !)((хн х„..., хн),' (20.2-26) (=! нлв какой-либо другой возрастаю!дей функции от абсолютных величаи ; '7! ~ мин*.мума (или максимума) функции и переменных и сама по себе имеет большое практическое значение.
ля решеввя этой задачи итсроцискке!ми методоми начинают с .(О) произвольных значений х( 1 (! = 1, 2, ..., и) и строят последовательные прпближе- ния ((=1, 2, ..., и; 1=0, 1, 2, ...), (20,2-29) ко)орые сходится к некоторому решению х; при !' оз. Различные методы Отличаются выбором «направления» /-го шага, т.
е. выбо оц; И (П . (/] р Отношений Р1 ' Р2 " . Ря' . Лет но шаго определяется зьа«1енпеч и Раь!Ртра Х мвпичи нрчюшим величин> р (х(! т ') х()-Ь '1 !/ !)) а ь !П 1 Ьз °" Х„ как бт ); 171 ,унклню от Х . оту фупкцию обычно аппрокснмнруют ее тейлорозскги разложением пли интерполяционсам многочленом по трем — пят б " зн ч ((1, значениям Х . Последний метод применим длл оп.ап пкия гоах и ппп л1.йлич1(О виданной фУнкЦии г' (хы хт,... т хя), эа.2-2, 660 ГЛ. ВК ЧИСЛЕННЫЕ МЕТОДЫ И КОНЕЧНЫЕ РЛЭНОСТИ 20.2 сн(СЛЕННОЕ РЕШЕНИЕ УРЛВНЕИИИ 20.2-7. Градиентные методы.
(а) Метод н а и с к о р е й ш е г о спуска. Выбирают и 1 1= —,с 1/1= — дГ,'дх где все производные вычисляются при хс=хс, и умеаьш 1/1, ают величин ' шага у л[/1 мере приближения к минимуму функции Г (рис. 20.2-1). по м для аналитическнх функций р н малых значенвй [с тейлоровск р ' ое азло)кение р (й[/1) позволяет выбрать оптимальнуо величину шага ~ (-~-.'-;)' я а Л=-)а=с ([ =О, 1, 2, " ), (20 2 30) где все производные вычиелшатся при х!=х['1.
Параболическая интерполяция функции Р [а(/!) может оказаться более удобной. Ь) Спуск с вычислением ноординат градиента. Часто вычисление координат вектора градиента дГПдха, необходимых для метода наискорейшего спуска, оказывается невозможным или непрактичным. Тогда указаийые производные заменяют разностными отношениями й Р/Дхй, получаемыми путем по поочередного изменения только одного переменного хз. Так кзк при этом на каждый шаг расчета в направлении градиента затрачивает Схацямасть таких исеряциаияык метацая ~акта ыасяпа уста . т ааяягь с аамащща теа- ремьс а ся яыающеы ющеы отображения и !2 б-б; аря *та» ясяаиае ре[ авиа рассматривается как ааслаР с ЯаРыай )с к! + т! 1-,, + кя ииа 1 «1 1-1-, к ! -1-...
+ ' ха ) (Щ Изменение на кавсдом шаге только одного пере- и е н н о г о. На каждом шаге изменяют только одно из хп лабо циклически, либо так, чтобы уменьшить наибольшую по людулю певязку (см. также (с) Методы п о и с к а. Чисто случайный попок состоит в отборе наи- большего (или наименьшего) из значенив г" (х(, х,, ..., х„) для некоторого количества случайно выбранных точек (х,, хз, ..., х„); он применяется, глав- ным образом, при оты б, отыскании начальных приближений для итерационных мето- . В тсдг случайных еозлсущенийначинают с некоторой точки (х„хз, ..., к„) и вводят множество случайных возмущений всех неизвестных для получения большего (или меньшего) значения нсследуемой функции Е.
Рассчитанная при этом точка дает следуюизсе приближение, и поиск продол- . П м методе, в отличие от метода чисто случайного поиска, можно . Мета сл чайных использовать свойство непрерывности исследуемой функции, .", етод у возмущений часто прнмеияегся в тех случаях, когда градиентные методы отказ т нэ-за таких особенностей многомерной области, как екрсбгы», «ущельям зывают нэ-за ак «плоскогорья» и кратные экстремумы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
