А.А. Самарский - Введение в численные методы (1113832), страница 19
Текст из файла (страница 19)
Для числа итераций я=и(е) верны оценки (11) и (12). Чтобы убедиться в этом, достаточно свестн задачу (22) к эквивалентной задаче для явной схемы + Схь = О, й = О, 1, ..., х,:=- В"'и ю (25) та+ где х„=Вг"шн С =В "АВ "' — самосопряженный положительный оператор с границами спектра (, и (,; Т ~ ~Ъ (26) В самом деле, так как В = В* > О, то существует В" = (В"')* > О, Действуя оператором В " на ураане- 12о гл. пт. ггппкнпс ьлгквгьичгскпх гглвнкнии пнс (22), получаем (25) для х„=Во'иь Обратный ход рассуждений очевиден.
Остается доказать эквцвалептность неравенств (23) п (26). Рассмотрпм функционал /= ((А — "(В)у, р) = — (Ау, р) — 7(Ву, р) = = (АВ 'п(В"-"у), В-'"-(В'"у)) — 7(Во-'), Вп') ) = = (Сх, х) — 7(х, х) = ((С вЂ” тВ)х, х), где х В'пу. Так как р (а значпт, и х) — произвольный вектор пз Л, то пз равопства У=((Л вЂ” 7В)у, у) ИС вЂ” 7К)х, х) (27) следует, что операторы Л вЂ” 7В и С вЂ” 7В имеют одпнаковые знаки.
Если, например, Л вЂ” 7,В -=-О, то прп равенство (27) дает С вЂ” т,Е ~ 0 н т. д. Для явной схемы имеем оценку 1х„з < д„зх,1. Подставляя сюда х„= В"'и„= В-"'г„г„= Л р, — (", получаем оценку (24). Для методов Зсйдсля и верхней релаксации В те В*, и потому нельзя воспользоваться чебытиевскпм набором параметров. и б. Попеременно-треугольный метод 1. Попеременно-треугольный метод. Будем рассматривать неявную итерационную схему В "+' " — ', Ау„=), я=0,1,... (1) тл.
д Если оператор В представляет собой пропзведгние конечного числа экономичных операторов, то он также экономичен. Так„ экономичным является оператор В = В,Вп равный произведению треугольных операторов В, и Вз. Рассмотрим так называемый попеременно-трерзольяый метод — метод (1), для которого оператор В имеет впд В = (В+ юЛ,)В '(Рл+ юЛ,), (2) где Ю тле>0, В~=Ли Л,-)-Лт=-Л, Л=Л" >О, ы > 0 — параметр.
Покажем, что оператор В является саыосопряженным и положительным, т. е. схема (1) с оператором (2) принадлежит исходному семейству схем (2) пз з 3 и можно пользоваться всеми полученными ранее результатамп об- ф х попквкмкнно-тгвутольный метОд изей теории. В самом деле, (Ву, о) ((Р+ езН,)Р '(Р+ ыЛ,)у, о) = = ((Р+ езЛ,)у, Р '(Р+ юН,)о) = =.
(у, (Р+ юЛ,)Р '(Р+ юН,)о), а значит, (Ву, и) (у, Ви), т, е. В=В*. Далее, находим (Ву, у)=((Р+сеЛх) у, Р ' (Р + еэЛа) у)=)(Р+ыНт)у !/ — т)0, т. е. В = Ве ) О, Оператору Л соответствует матрица В = (гс). В качестве матриц К, п Нз можно взять нижнюю и верхнюю треугольные матрицы, т. с. г„-1, .'9 гч= гц, О, ) гп12, ги = О, 1=1, 1(1 1~ (' Лт = (г;.), 1=1, 1)1, 1(й Л, = (ги), Если Л вЂ” симметричная матрица, гл = г„, то Н, н Л, взаимно сопряжены, Нх Лм В качестве Р= Ы;,) возьмем диагональную матрицу. Тогда Р+ юЛ, — нижняя треугольная, а Р+ езЛ~ — верхняя треугольная матрица.
Таким образом, процесс итераций сводится к попеременному обращению нижней и верхней треугольных матриц (отсюда и название метода). В самом деле, для казкдон итерации надо решать урав- нение Ву„, = (Р+ юН,)Р '(Р+ юЛ,)уз~, =Г,. (3) Обозначая Р '(Р+ езЛ,)у~+~ = у, „получаем (Р+ ял!)ум+ РА (Р+ иЛ2)ум! Ру " 1 1'=О, (, ... (4) Замечая, что (Н,у, у) = (Л,у, у) = (Лу, у)/2, находим ((Р + сВ ) у у) - (Ру у) + ю (Лту: у) =- - ~(и + ~ ~ у, у1~= ((Р+,) у, у)-. О, тек кан Р)0, ю>0 и Л)0.
ГЛ. П1. РЕ>ПЕНИЕ АЛГЕБРАИЧЕСКИХ УРАВНЕНИИ Отсюда следует существованпе обратных операторов (Р+ ь>й,) ', (Р+ ь>й,) ', т. е. разре>пнмость задач (4). 2. Выбор параметра е>. Чтобы пользоваться общей теорией, надо сначала найти параметры (< и у„ входящие в неравенства у,й(А ( ц>В, поторые в силу ограниченности н положительности операторов А и В всегда выполнены. Начном с определения параметра ь> ) О.
Л е и м а. Пусть оператор В определяется по формуле (2), эде В:=В,, В,+В,=й, В=В*=.О и В удовлетворяет условия.и В)бРЬ>ОВ~Рйэ(4 ВЛ)Ю(6) Тогда справедлива оценка о о о б о 1 У>в~В<У,В, У,= е, У,=, . (У) 1 —,- о>б + 0,25ь>" бЛ 2ь> о От>гашение с = (>(ь>)>>ц,(ь>) ил<еет наибольшее эномение при ь> = е> = 2/)'6Л; при это.>< 21/Ч б о 1+ (/»' Л' 2(1- .
'(>'т~) 4 1/>> Д о н а з а т с л ь с т в о. Неравенства (б) означают, что 4 ( для всех у~ П. После преобразовавпй й= (Р+ <эй,)Р '(Р+ е>й,) = =Р— ь>(й, +В,)+ ю'П,Р-'Во+ 2ь>(й, +В,)- = (Р— <ой>)Р '(Р— <вй,) + 2ь>й получаем (йу, у) (Р ' (Р— ь>й,) у, (Р— е>й,) у) + 2ь> (Ву, у) 1(Р— ь>йэ) у~~,' 1+ 2<>(йу, у) о2е>(йу, у), 5 Ь. ПОПЕРЕМЕННО-ТРЕУоОЛЬНЫИ МЕтол 123 так что В: 2аВ, нлн В( — В, уз=,—, о 1 Получим теперь оценку дл» В сверху.
Учитывая (6), найдем га П+аП+аВП В ~~ В ь ~+ 4 ( +а ' 4 ) а 64~ Л,)),В, 7',=6(1+ 6-(- 4 ) Число итерацпй, необходимое для решения уравнения Ву = /, зависит от отношения 4(а) = (,/то = 2аб(1+ аб+ а'6Л/4) '. о Выберем а пз условия максимума $(а). Приравнивая нуо лю производную $'(а) = 26(1 — а'6Л/4)(1+ аб+ а'6Л/4) ', о о о паходпм а = а = 2/1'6Л; при атом 4" (а) (О. Подставляя о о о это значение а в фоРмУлы дл» 1о 1» $(а), полУчаем фоР- мулу (9). Лемма доказана. 3. Скорость сходимости. Т е о р е и а, Пусть оператор А = Аь ) 0 представлен, в виде суна»ел А = Ат+ Ла Л, =- А1, и выполнены условия А) 6П, Л1П 'Л ( — Л, 6~0, Л) О. (10) Тогда для попеременно-треугольного метода (1) с В = (П+ аЛ,)П '(П+ аЛ.), П = Пв ) О, (11) с параллетром а =2/УБЛ и чебьпиевснигз наборолз параметров то 2 то=, .
ро= — т, + тг ' $ =. — ' — — ) ", (12) тг 4 —:-1/Ч где б 6 6 о 2 (1 -'- (/Ч) 4 (/1) (13) 124 ГЛ. Н1, РЕШЕНИЕ АЛГЕВРАИЧЕСКПХ УРАВНЕНИИ достато'гно п(е) итераций: п, (е) » (п (е) ( ггв (е) Р 1, и, (е) ( 1и —, /(2 У2 1 ц); (14) при этом выполнена оценка ~1~-~ ~ е)) Ау~ 1))в-Р (15) Д о к а з а т е л ь с т в о. Воспользуемся предыдущей леммой, полагая Л = А, 1г, = А „)гг = А:, а также оценкой (24) из 4 4: Муь Лв- ( г )) Аув Л и г — „ ни =- .„' Рг 1, 'УГ иг — 2ггг —;- п;„г А ггв - = О, ил.= О.
(16) Пусть Н Й вЂ” пространство сеточных функций, заданных во внутренних узлах г =- 1„2,..., Дг — 1 сетки ым введем скалярное произведение (у, и) =- ~э уггг)г. Оператор Ау= — у -х является самосоиряженным н положительно определенным: А)ЬЕ, 6 = —,япт — ', 4 ., па А ,(тнг числа итераций и = и(е) и у 3 была получена оценка п„(е) --н(г) (п„(е)+ 1, где и„(е)((п —,/(2г )IЦ). Подставляя сюда с = 21'ц г(1+ Ут)), получим (15). 4. Пример применения попеременно-треугольного згетода.
Рассыотрпм модельную задачу $ Е ПОПЕРЕМЕННО. ТРЕУГОЛЬНЫЙ МЕТОД 125 Введем операторы Ру = у (Р = Е) н е- А,у= Лгу = — ' у,1 Е1 й й Итерации (у,)1= уч(1) находятся по формулам (Š—;.Л,)(у,-)й„= у,+." -' ~ -:.:Г„((), й !1«1 1ее (1 ) ) ~ йей (1) У1.,1(1) =- й, 1Е (Š— ' е1Ле) Уй, (1)— 1Е , (1) — ', (У1,, (1 + )) — У111(1)) . Уй~-1(')1 окончательно имеем ывй (1+ 1)+ й че (1) уй, () =" ы —,'- й 1 = )ч' — 1, д1 — 2, ..., 2, 1. У,„,(О) = О, У1.1(Д.) = О, Формулы подобного типа называют форэ1ула.чи бегу1уего счета, Из равенства у-„1„, = ух,1 следует, что Л1 =- Л. В самом деле, так нак 121 — иа + йа-„1=- йг„-,, то И вЂ” 1 1 %1 1=1 Е-1 Е-1 ,~„у1о;, = й ~„у, ' =- (у, Л111), 1=1 (Л,у, 1) ~'„у„,ь, 1 е = У,1:-,, + ~~У Г;1 — = т.
е. Ат =- Ае. Значения у,,(1) находятся последовательно при двпькенип слева направо (от 1 — 1 н (), а учч,(1) — справа палево (от 1+1 к 1); при этом учитываются краевые условия 1ве гл. пх гвшвних ллгввгаичкских тглэнкнин откуда следует Л = 4//т!. Таккм образом, 6 ., сл э-ь ~/- — эь г !) = — = зй!э —,ж —, ц= — '. ', 2 4 ) ц/'(1+ У )=2 у' = ° К )/Х= )~М! гак что и, (е) )п —, 1 2 2 )!яа Если е = 10 ', то зто дает и,(з) - 3/!'!!. Результат таков: п„(е) = 10 при Ь = 1/10 (У = 10), я,(.з) =30 прп В=1/100 (%=100).
11апомним, что при У = 100 надо сделать 20000 !итераций по методу простой итерации и 340 итераций по явной чебышевской схеме. Таким образом, поперемепно-треугольный метод оказался лучшим среди тех методов, которые мы изучали. э 6. Вариационно-итерационные методы 1. Метод минимальных невяэок. До сих пор при изучении итерационных методов мы всюду предполагали, что постоянные т, и т,— границы спектра оператора Л в Н илп в Н вЂ” известны.
Что делать, если такой информации нет! В этом случае можно применять методы, пе испольаующие в явном виде параметры т, и (ь Зто методы вариацнонного типа. Здесь мы рассмотрим методы минимальных невязок, скорейшего спуска и сопряженных градиентоз, Вычислим постоянную (А Л,у, у) = (Л„у, А,у) = л-! 1 ч э = — э,4 (У*,) ь < — 'Х й(у- )'=- !=.! й = — ',,')'„(!-„,.)э й~ ~=2 л — ! 1 ь' !ь а В. зхэихционно итГРхционныГ метОды в27 Начнем с метода юинплальных невязов для явной схемы уаав — ив + Ауз =- /, й .=- О,!, ° °, для всех у еи Н.
'ва в (4) Для певязкп г, = Лув —,( имеем однородное уравнение -1-Ага.— -- О, lа =- 0,1, ° ° °, г, = Луа ~ (2) вэв Параметр тва, будем выбирать нз условия минимума иевязки г„+, по норме: ,'„'гвав11а =. !а га — та+,Ага(1а = =-. 1(гв "Г' — 2та,(гю Ага) —;. тва, 11Аг„'1а = а(;(тв„в). Продифференцнруем это выражение по т„„приравняем производную ар (т,в,) нулю: ар'(т„ю) = — 2(г„Лг,) + 2т„„11Агв'1а = О и найдем Прп этом значения т„.„вторая производная ар (т„,) положительна и, следовательно, достпгаетсЯ ппп ~)гва, 1(ь твав До сих пор мы пе предполагалп, что А — самосопряженный оператор.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
