Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 38
Текст из файла (страница 38)
$4. Итерационные методы для систем нелинейных уравнений 1. Общие понятия. Рассмотрим систему нелинейных уравнений ~,(хп х„..., х )=О, 7,(хо хм ..., х~) =О, (1) 7 (х„х„..., х„,) =О, х= (х„ х„ ..., х ) ~Н, т Е(х) =(~,(х), ),(х), ..., ( (х)) и запишем (1) в виде операторного уравнения Г(х) =О, (2) где г": Н- Н вЂ” отображение, нелинейное, вообще говоря, из Н в Н. 207 где !и 1=1, 2, ..., и,— функции вещественных переменных х„... ..., х . В дальнейшем систему (!) будем рассматривать как опе- раторное уравнение в некотором линейном пространстве Н раз- мерности гп. Обозначим Многие одношаговые итерационные методы для решения системы (2) можно записать в виде Взы ю +Р(хз) =О, й=О, 1, ..., х задан, (3) „зю „з где я — номер итерации, а з з т х = (хо хз ° ° ° »м) ~ ть+г — числовые параметры, В,+,— матрица тКт, имеющая обратную.
Если Р— линейный оператор, то (3) совпадает с канонической формой одношагового итерационного метода (см. $ ! гл. 2), т. е. в виде (3) можно записать любой одношаговый метод дли лвнейной системы уравнений. В случае нелинейной системы (1) возможны методы, содержащие новую итерацию хь+' нелинейно, и тем самым не представимые в виде (3). Однако мы по-прежнему будем называть канонической формой запись итерационного метода в виде (3). Для нахождения х"+' по известному х' из уравнения (3) необходимо решить систему линейных алгебраических уравнений В,,х"" = д (х'), (4) где д(х') =В„„,х' — т,,Р(х"). Метод (3) называется явным, если В„+,— — Е для всех я=О, 1,..., и неявным — в противном случае.
Метод (3) называется стационарным, если В и т не зависят от номера итерации й. Систему линейных уравнений (4) можно решать либо прямым, либо итерационным методом. В последнем случае итерации, приводящие к решению системы (4), называются внутренними итерациями, а итерации (3) — внешними итерациями. 2.
Сходимость стационарного метода. Остановимся кратко на вопросе о сходимости метода (3). Предположим, что метод (3)— стационарный, т. е. В и т не зависят от й. Тогда уравнение (3) можно переписать в виде х" +' = 5 (хь) а исходное уравнение (2) — в виде х=5(х), (6) 208 где 5(х) =х — тВ-'Р(х). Будем считать, что Н вЂ” конечномерное линейное нормированное пространство, т. е.
что определен функционал ))х)(, удовлетворяющий всем аксиомам нормы. Точка х.веН, для которой 5(х ) =х, называется неподвижной точкой оператора 5. Очевидно, что точка х. является решением операторного уравнения (2) тогда и только тогда, когда она является неподвижной точкой оператора 5. Таким образом, отыскакие корней уравнения (2) эквивалентно отысканию неподвижных точек оператора 5.
Говорят, что 5 является сжимающим оператором на множестве Кс=.Н с коэффициентом сжатия д, если существует число дев (О, 1) такое, что дли любых х', х"ееК выполняется неравенство ))5(») — 5( ")1( ц()х — "(1. Теперь мы в состоянии сформулировать теорему, которая называется принципом сжимающих отображений и содержит условия сходимости метода простой итерации х'+'=5 (х") (7) и конечномерном линейном нормированном пространстве Н.
Она является многомерным аналогом теоремы 1 из $2. Т е о р е м а 1. Пусть оператор 5 определен на множестве Е7,(а) = (хенН: 1!х — а~1<») и является сжимающим оператором на этом множестве с коэффициентом сжатия о, причем ~~5(а) — аИ<(1 — д)», 0<у<1. (8) Тогда в (7„(а) оператор 5 имеет единственную неподвижную точку х. и итерационный метод (7) сходится к х„при любом х'ен енК(а). Для погрешности справедливы оценки 1х" — х.1< у''1 хь — х, 1, (9) ~хх — х.~< 15(хь) — х'1.
ч (10) ) — д Доказательство теоремы 1 можно найти в [42). 3. Примеры итерационных методов. П р и м е р 1. Метод релаксации представляет собой частный случай метода (3), когда В„~,=Е, т,+,— — т. Это стационарный итерационный метод, который можно записать в виде х'+'=5 (х"), где 5(х) =х — тР(х). Метод сходится, если ~~5'(х,) 9 <1. В данном случае 5'(х) = =Š— тР'(х) и д/, (х) дх, д)ь (х) дх, д(1 (х) д)1 (х) дх, дх д»..(х) д~.
(х) дх, дх Р'(х) = д) (х) д( (х) дхь дх д( (х) дх, 209 Пр имер 2. Метод Пикара. Пусть Р(х) представляется в виде Р(х) =Ах+6(х), где А — матрица гпХгп. Тогда итерации можно определить следующим образом: Ах'+'+6(х") =О. Итерационный метод можно переписать в виде А (х"' — х")+г (хй) =О, т. е. в канонической форме (3) с В,й,=А, т,й,=!. Можно и здесь ввести итерационный параметр и рассматривать более общий метод А + г (хй) = О. т П р им е р 3. Метод Ньютона для системы уравнений (!) стро- ится следующим образом.
Пусть приближение х"=(х„х„..., х ) уже известно. Выпий й й г шем разложение функции ~;(х„х„..., х„) по формуле Тейлора в точке х', й й й дй (лй) ~~ (хы хй, ..., хщ) = ~; (хь хм ..., хщ) + (хд — х~) + дх, +(х,— х,) + ... +(х — х„) ' +0()х — х")й), д(, (хй) дН (хй) дхй дх и отбросим величины второго порядка малости. Тогда система (!) заменится системой уравнений дН(й) 'Я (х; — х1) ' +Н(хй) =О, (=1, 2,, т, (!2) дх. /=1 1 линейной относительно приращений х,— хй, 1=1, 2, ..., и. Решение х= (х„х„..., х„)' системы (!2) примем за следующее приближение и обозначим через хй =(хй й ... хй )т.
Таким образом, итерационный метод Ньютона для (1) определяется системой уравнений '~'„(х>" — х)) ' +(~(хй)=О, (=1, 2, ..., и, (13) дх. 1=1 1 из которой последовательно, начиная с заданного х' = (х„ ...,х ), 0 й т находятся векторы х', й=1, 2,... Систему (!3) можно записать в векторном виде г"'(хй) (х"+' — хй)+Е(хй) =О, юг=О, 1, ..., х' задан, (14) где матрица г'(х) определена согласно (11). Таким образом, метод Ньютона имеет канонический вид (3), где В,й, = г"'(х"), т,й, =!. Для реализации метода Ньютона необходимо существование матриц (Г'(х"))-', обратных Е'(хй). По поводу сходимости метода Ньютона для систем уравнений можно сказать то же, что и в слу- 210 чае одного уравнения, а именно, метод имеет квадратичную сходи. масть, если начальное приближение выбрано достаточно хорошо.
Приведем без доказательства одну из теорем о сходимости метода Ньютона. Пусть Еы — множество т-мерных вещественных векторов с нормой !!х!1= ,г ы тя Я хт~ ,!!А!! — норма матрицы А, подчиненнаи данной норме вектора. т=т Обозначим П,(хо) =(хщЕчц Цх — хо!)<т) и предположим, что в шаре П,(хо) функции Н(х), т=1, 2, ..., т, непрерывно дифференцируемы. Те о р ем а 2. Предположил, что в П,(хо) матрица Р'(х) удовлетворяет условию Дипшица с постоянной Е, т. е. !! Р'(х') — Р'(хт) )! < И!х' — хЧ для любых х', хттмП,(хо).
Пусть е 0,(хо) матрица (Р'(х))-' существует, причем элементы ее непрерывны и !! (Р'(х) )-Ч <М. Если начальное приближение хо таково, что !1Р(хо) !1~(ц и МЧл) ц= <1, 2 причем Локазательство теоремы 2 можно найти в [42[. П р и м е р 4. Модифицированный метод Ньютона имеет вид Р'(х') (хеы — х")+Р(х") =О (15) и обладает линейной сходимостью. Упрощение в численной реализации по сравнению с обычным методом Ньютона состоит в том, что матрицу Р'(х) надо обращать не на каждан итерации, а лишь один раз. Возможно циклическое применение модифицированного метода Ньютона, когда Р'(х) обращается через определенное число итераций. П р и мер 5.
Метод Ньютона с параметром имеет вид Р'(х") + Р(хь) =О. т (16) Мт) ~~~ дз~-т < т, ь=о то система уравнений (2) имеет решение х.омП,(хо), к которому сходится метод Ньютона (14), Оценка погрешности дается неравенством , аь-т [! х — х, [! < Мт)— 1 — до Рассмотренные до сих пор методы являлись линейными отно- сительно новой итерации х'+'. Возможны и нелинейные методы, ког- 211 да для вычисления х'+' приходится решать нелинейные системы уравнений.
Приведем примеры таких методов. П р и м е р 6. Нелинейный метод Якоби для системы (1) имеет вид й й й йл! й й> !й! (х! х>,, х>->> х> х>й! ... > х>>) О> ! =1, 2,..., ги. (17) Здесь для отыскания х'й' необходимо решить лй независимых скалярных уравнений. Для решения скалярного уравнения можно применить какой-либо из итерационных методов, рассмотренных в $ 1, причем не обязательно применять один и тот же метод для всех уравнений. П р имер 7. Нелинейный метод Эейделя состоит в последовательном решении уравнений й+! йй! й+! й !"с(х! > хй, ..., хс, хсй>, ..., х>1) =0 й+! > й +)(х>, ..., х; „уо хы„..., х„>) =О, (19) й=1,2,..., т. Здесь индексом в обозначен номер внутренней итерации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
