Том 2 (1160084), страница 22
Текст из файла (страница 22)
е. мы найдем р и соз~р, а следовательно н х,, и ха. Далее, а~И Р ~хз", доз ~ Р хз +2Р '" хз сов~>, хам,, (59) ф 4. Итерационные методы решения алгебраических и трансцендентных уравнений Для решения алгебраических и трансцендентных уравнений вида 7(х) = 0 разработано много различных итерационных мегодов. Сущность этих методов заключается в следующем.
Пусть известна доста точно малая область, в которой содержится единственный корень х =а уравнения 7'(х) = О. Остальные корни находятся так же, как и в предыдущих случаях, по формулам (55). Можно рассмотреть аналогично случаи, когда кратные или комплексные корни имеют промежуточные модули, Наличие комплексных корней и их место обнаруживаются так же, как и в методе Лобачевского. Видоизменение Лемера метода Лобачевского имеет несомненные преимущества по сравнению с обычным методом Лобачевского, так как при его применении не приходится извлекать корней высоких степеней. а также при наличии различных корней с одинаковыми модулями нет необходимости разьединять зти корни, рассматривая уравнение Р(х — Ь)=О и применяя к нему повторно метод Лобачевского. 129 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ В этой области выбирается точка хз — начальное приближение корня, — достаточно близкая к искомому корню х=а, и с помо.цью некоторого рекуррентного соотношения (2) х„=~рв(хы х,, ..., х„,) строится последовательность точек х,, хз, ..., х„, ..., сходящаяся к х = а.
Сходимость последовательности обеспечивается соответствующим выбором функции у„и начального приближения хв. Выбирая различными способами функцию ~ра, которая зависит от /(х) и в общем случае от номера (г, можно получить различные итерационные методы. Чаше всего по функции 1(х) строят функцию р(х) такую, что искомый корень х=а уравнения (1) является и корнем уравнения х = 9 (х), и затем строят последовательность 1х„) с помощью соотношения х„=а(х„,) (а=1, 2, ...), (4) исходя из некоторого начального приближения хв. В этом случае функция у не зависит оз номера й, и методы такого типа мы будем называть стационарными. Ниже мы исследуем ряд стационарных и нестационарных методов. 1.
Принцип сжатых отображений и его применение к доказательству сходимости итерационных методов. Для исследования сходимости итерационных методов, а также для доказательства существования корня уравнения широко применяется принцип сжатых отображений, который мы сформулируем и докажем в общем виде и в форме, удобной для наших целей. Пусть )с — некоторое метрическое пространство, а Ах — некоторый оператор, определенный на этом пространстве. Будем говорить, что этот опер тор осуществляет вжатое отображение )с в себя, если существует такое положительное число а, меньшее единицы, что для любых двух элеменгов х, у~ )с имеет место неравенсзво (5) р(Ах, Ау) ...ар(х, у), т.
е. оператор А сближает элементы. Теорема (1гринцип сжатых отображений). Если )с — полное .Иетрическое пространство, а оператор Ах осуществляет сжатое отображение )с в себя, то существует одна и только одна неподвижная точна этого отображения, т. е. уравнение Ах=х 130 вешании ьлгввгьичвскик и твьнсцандвнтных эвьвнений [гл. 7 имеет одно и только одно решение.
Решение этого уравнении может быть получено как предел последовательности хв —— Ахь ()е=-1, 2, ...1, (7) где х„— проиэвольныд элемент из )с. Доказательство. Пусть хв — произвольный элемент из гч. Образуем последовательность (7) и докажем, что она является фундаментальной последовательностью.
В самом деле, если и) т, то в(х„, х )=р(Ах„,, Ах,) <ар(х„,, хт,), р(х„,, х,„,) <ар(х„,, хм,). р (х„„,ч „х,) < ар (х„, х,). Следовательно, р(х„, х ) <а р(х„, х ). Но р(х„„, хв)~<р(хв. х,)+р(х,, хч) [- ... -]-р(х„,, х„) < 1 <р(хь, х,)[1+а-[-а'+ ... +а" '] < — р(хь, х,). Таким образом, дм р(х„, х ) < — р(х,, х,), что и доказывает фундаментальность последовательности [х„], так как при достаточно большом т и любом и ) т правая часть последнего неравенства может быть сделана меньше любого заданного положительного числа, Из полноты пространства Я следует существование элемента к~ Я, к которому сходится последовательность [х„], т.
е. х= 1нп х„. Далее, так как р(Ах„, Ах) <ар(х„, х) н р(х„, х)-+О при и-+ со, то 1ип Ах„=Ах. Но Ах„=х„+,-+ х. п -ь оэ Следовательно, х= Ах. Для доказательства единственности допустим, что существуют два неподвижных элемента х и у, т. е. х=Ах, у=Ау, р(х, у) ФО. Но оператор Ах осуществляет сжатое отображение, поэтому р (Ах, Ау) = р (х, у) < ар (х, у), что невозможно, так как О < а < 1. 131 итеоьционнъш методы Решения Приведем еще одну теорему, которая уточняет доказанный выше принцип сжатых отображений.
Те о р е и а. Лусть в полном м трическом пространстве гч| или на его часа|и, содержащей окрестность Я элемента уо: о =- (р (х, уо) «( г], определен оператор Ах. Лусть для любых х убей р (Ах, Ау) ( ар (х, у) (5') и р(Ауо, уо) ((1 — а) г, (5") где а — некоторое 4иксированное положительное число, меньшее единица. Тогда в 3 существует одно и только одно решение уравненик (6), которое может быть получено как предел последовательности (7), где хо — произвольный элемент из 5. Эта теорема непосредственно следует из принципа сжатых отображений, так как если хЕ 5, то р(Ах, уо)«(р(Ах, Ауо) +р(Ауо, уо) «(ар(х, у„)+-(1 — а) г«(г.
т. е. Ах~Я. Это означает, что оператор Ах осуществляет отображение 5 в себя. Из (5') следует, что это отображение сжатое. Совокупность всех элементов о с тем же самым понятием расстояния р(х, у) можно рассматривать как полное метрическое пространство, так как если !у„) — любая фундаментальная последовательность элементов нз 5, то она сходится в Й, т.
е. существует элемент у~ Й такой. что у= 1ппу. Но р(у„, у,) (г, отсюда П|п р(у„, у,) =р( П|п у„. у)= р(у. у>) (г, т, е. у~ 5. Теперь уже утверждение теоремы прямо следует из принципа сжатых отображений. Рассмотрим применение этого принципа к исследованию сходимости итерационного метода решения уравнения х= о(х) (3) при некоторых ограничениях на функцию р(х). Предположим, что уравнение (3) имеет корень х=а и в круге Й ( ( х — а) ( г) функция |р (х) удовлетворяет условию Липшица ! р(х') — р(х") ! (К1х' — х" ) (3) для любых точек х', х'~ !ч.
Теорема. Каково бы ни было хо~)7, последовательное по хь=р(хь-г) (Ф=1 2 3 ) 132 евшвиие ллгеввличвских и тглисцяидвитиых звлвияиий (гл. 7 сходится к и, если только ог(х) в круге Й удовлетворяет условию Пипшиаа с кокстантой К( 1, причем скорость сходимости характеризуется неравенством (х„— а( < К" )хо — а(, Доказательство. Совокупность точек круга )с, если определить расстояние между точками х и у соотношением р(х, у)= = ~х — у1, образует полное метрическое пространство.
Если х~ )с, то у=о(х) также принадлежит )ч, ибо р (у, а) = (у — а ( = ( со (х) — ср (сс) ! ( К ( х — а ! < г. Отображение, определяемое функцией р(х), есть сжатое отображе- иие сс в себя, так как для любых х, у~ )с р1ср(х), г(у)1=! р(х) — о(у)! (К)х — у(=Кр(х, у) и К(1. Поэтому по принципу сжатых отображений в )2 существует одна и только одна неподвижная точка, ио эта точка х=а. Эту точку можно получить как предел последовательности хь —— р (хг,) (lг = 1, 2, ...) при любом хо~И.
Используя условие Лившица (8), имеем: ( х„— сс ( = ( со (х„,) — р (а) ( «( К ( х„, — а ( . т. е. (х„— а(~(К) х„, — а(~(Кч~ х„г — сс( ( ... (К" (хо — а!. Таким образом, (х„( сходится к а со скоростью геометрической прогрессии со знаменателем К, В доказанной теореме мы предполагали существование корня уравнения (3). Принцип сжатых отображений может быть использовав и для доказательства существоваиия корня. Теорема.
Если функция р(х) в некотором круге)с () х — хо( ( г( удовлетворяет условию Липш ииа (8) с константой К ( 1 и в точке хо имеет место неравенство ~ хо — чг (хо) ! < (1 — К) г, (10) то в )с уравнение (3) имеет единственный корень х= а, который может быть найден нак предел последовательности уь = у (ул с) (к = 1, 2, ...), где уо — любая точка из круга )с. Доказательство. Пусть х~ )ч.
Тогда ( о (х) — хо ( = ~ ср (х) — ср (хо) + р (хо) — хо ( ( «((Т(х) — ~(хо) ~+ ~ сР(хо) хо(«(К(х хо(+(1 — К) г < г, $ 41 !33 итвглциоииые методы гашения т. е. функция ~р(х) осуществляет отображение Я в себя. Это — сжа- тое отображение, так как для любых х, у~Я р (<р (х), ч (у) ) = ! р (х) — ср (у) ! ( К ) у — х ~ = Кр (х, у). ! р'(х)! ( К ( 1. (1 1) Если производная э'(х) непрерывна, то из условия !р'(а)! ( К( 1 следует выполнение этого неравенства в некоторой окрестности корня х=а, и для отыскания этого корня можно применить метод итераций, выбирая начальное приближеиие хз из этой окрестности.
Скорость сходимости будет тем больше, чем меньше К. Введем понятие порядки итерации (4) для решения уравиеиия (3). Будем говорить, что итерация (4) имеет порядок т, если р'(а) =ри(а) = ... =ср! -'1(а) =О, ф"'1(а) +О. (12) Если р(х) имеет в окрестности корня т непрерывных производных, то по формуле Тейлора р (х) — а = (х — а) и' (а) + р" (а) + В случае итерации порядка т имеем: р (х) — а =, р!"'> ($), откуда (хк 1 — а) ха — а= а ' ф"'>($а).
т! (13) Обозначая через Мт максимум модуля ф'и)(х) в некоторой фикси- роваииой окрестности корня х=а, получим неравенство (14) Следовательно, имеет место принцип сжатых отображений. из которого прямо следует теорема. Мы требовали от функции р(х) выполнения условия Липшица с константой К ( 1 в некоторой окрестности корня х = а уравиеиия (3). Чаще всего функция р(х) имеет производные, и условие Липшица с константой К( 1 будет иметь место, если в некоторой окрестности корня х=а функция р(х) имеет производную э'(х), по модулю меньшую некоторого числа, меньшего едииицы, т.
е. 134 Решение АВГеБРАических и тРАнсцендентных РРАвнений [гл. 7 из которого следует: Г+тет*ч- ... +т 1 ха — и ! ( !! — ) ~ хе т — ! А !' АГ~ и — ! ть ! т!) ~х,— ) т — ! к = ~ —.", ~ . — ~) -' ~ . — ~ ть+!-Зте-Г! (15) Таким образом, если )хе — а( ( 1 и — ~! хе — а! = т ( 1, то ~т т! т — 1 А ~ХА — а~ (т (16) что дает очень быструю сходимость хе к а. Для случая, когда р 1х) — действительная функция переменного х и х= а — действительный корень уравнения (3), метод итерации (4) имеет хорошую геометрическую интерпретацию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
