Samarskij A.A. Vvedenie v chislennye metody (ru)(400dpi)(T) (969542), страница 19
Текст из файла (страница 19)
Покажем, что оператор В является саыосопряженным и положительным, т. е. схема (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(ь твав До сих пор мы пе предполагалп, что А — самосопряженный оператор.
Если же А = Аа ) О, то верны оценки ~!гв (((ра~!гв(~, 1(Лу„— )) =рЦЛуа — й (4) 2 Где гм п тв — точные границы спектра оператора А, В самом деле, так как прп значения т, 1 согласно (3) норма 11г,,11 минимальна, то прп любом татаа, она должна возрастать, поэтому 11гв+ 11 = 11гв тв ЛГР 11гв таАг„11 К 11Е т АР11г 11", С другой сторонвз, язвестно, что 11Š— таА11 = ра при т, = 2Пу, + аа). Отсюда и следует, что '1г„+,11 ~ р,11г,'11. 1зз Гл пь Гвюлннв хлгввохнчкскнх углвнвпнн Таням образом, метод минимальных певязок сходится с тон ьке скоростью, что и метод простой итерация (еслп в методе простой птсрацпп пспользулгтся точные значения 7,п бо), В случае неявного метода певязок, нлп летоба поправок, вместо (1) получаем уравнение для поправки: В»+» +Лир»=оо »=0,1, т» ю» гг 1» ~со Е (Ауо 7)1 (б) где т,+, определяется по формуле ( пг»,;,) (В 'Ам», Ай») (6) (о- — — О, 1, Вместо (4) получаем оценку ~~АУ» — 71в-» ~~ро(ЛУо — Лв-» 2.
Метод скорейшего спуска. Лвный гзетод скорейиоего спуска отличается от метода мпннмальных невязок то»о.- ко формулой для т»ю: (г,, г,) т»о»=-- ~,, А==0,1, (Агю г») ' (7) (Лг»оп г»+») = (А㻠— т»»»А гю 㻠— т»»»Лг») = = (㻠— т»отЛгю 㻠— т»»,г») = (гто г»)— — 2т»о»(г», г») + т»о, (Лг„г„). Дпфференцпруя (гав.,()»о по т,, п прправпивая пропзводную нулю, получим (7). Далее, имеем (! г»о»(л = "„(Š— т»+,А) г»)(", (1(Š— тЛ) г»((»г ( ~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
