А.А. Самарский - Теория разностных схем (1989) (1160092), страница 87
Текст из файла (страница 87)
> )'2'1 — 1, 1 = 1, 2,..., )УА — 1, где коэффициент Фурье с„ зависит от х, й,. После подстановки выражения И5) в уравнение ИЗ) получим Ю;1 Лу = Л,у+ Л,у =- ~ [рАЦЬ2) Л,св(АЬ,)+ са(й,)ЛА)ААЦЬА)) = А=1 И2 = —,'2~ РА(й ) рА(уЬ,), (16) А 1 где <РА(1Ь,) — коэффициент Фурье функции <Р(х): КА-1 <РА (й1) = Х <Р (й12 )ЬА) )АА ()ЬА) ЬА. З 1 Учитывая И4), а также ортогональность функций 12„получим ив Иб) для определения с„задачу л,с„— ЬАсА = — <РА, ь, ( х, < 1, — ь„с„(0) = с„(1,) = О, И7) где Ь = 1, 2, ..., )2'2 — 1.
Отсюда видно, что с„(й,) как функция х, = й, для каждого Ь находится методом прогонки. Всего надо )2'2 — 1 раэ испольвовать алгоритм прогонки. Зная с„(й,), по формуле И5) находим решение задачи ИЗ). Вычисление коэффициентов Фурье 2РА и нахождение решения у» может быть выполнено по одним и тем же формулам.
Здесь общим является вычисление сумм вида К-1 ив= )' ввв1п —, у'= 1,2,...,Л1 — 1. Ал) 1-1 Для втого используется специальный алгоритм быстрого преобраэования Фурье (на его описании мы не имеем воэможности останавливаться), который позволяет вычислять все укаванные 522 ГЛ. Х. МЕТОДЫ РВШКНИЯ СКТОЧНЫХ УРАВНННИй суммы за д = 2%1оялУ арифметических операций (дт' 2") вместо 0()уд) при обычном способе суммирования и тем самым найти решение разностной задачи Дирихле (2) в прямоугольнике за О(№№ 1он, №) арифметических операций. Метод декомпозиции можно применять в комбинации с мето- дом разделения переменных. В частности, метод разделения пе- ременных можно применить для решения. укороченной системы (6) (получающейся после исключения неиавестных с нечетны- ми у). Тогда аадача (2) может быть решена за 0'= 2№№1ой,№ арифметических действий, что в два раза меньше, чем требуется при решении задачи (2) методом разделения переменных.
4. Метод матричной прогонки. Система уравнений (3) является част- ным случаем задачи — Адуд-~ +СдТд — Вдув+~ = Рд, 1 1, 2, ..., Ф вЂ” 1, (18) Сэуэ- Влу~ = Рл, — А»Т»-д+ С»Т» = Р», где Тд и 'Рд — векторы размености Мь Сд — квадратная матрица размер- ности Мд Х Мд, Ад — нрэыоугояьная маэрица размерности Мд Х Мд ь а Вд — прямоугольная матрица размерности Мд Х Мд+ь Решение задачи ищется (по аналогии с и. 5 1 2 гл. 1) в виде Тд = ддд+ дул+в + Рдд д, 1 = Лд — 1, Лд — 2, ..., 1, О, где ад — прямоугольная вдатрица размерности Мд д Х Мь а рд — вектор раз- мерности Мд д.
Из (18) и (19) по аналогии со случаем обычной прогонки по- лучаем рекуррентные формулы для определения ад, рд а+ =(С вЂ” Аа) В;, -д а =С дВ, 1=1,2,...,Л' — 1, о е (11 д —— (С вЂ” А;а ) д(Р -) А;() ), Р =С др, !=1,2,.',Лд — 1,Лд, э с' Т = (С вЂ” А ) (Алй „+, Р,) = () Т =а)+дТ+д+())лд, 1= дт — 1,Л' — 2,,1,0. Метод матричной прогонки устойчнв по отношению к случайной ошиб- ке, т. е.
1адб ( 1, ) = 1, 2, ..., Лд, если выполнены условия ~ Со дВ 1~(1, $ Сл~Ая$$(1, $$С. ~А.$$+ $С. дВ $$(1, 1 (,У (Лд — 1, причем хотя бы для одного из этих условий должно выполняться строгое неравенство. Для интересующего лас частного случая (3) имеем Ад = =Вд=Е, Сд=С ДлЯ'1(1(ЛД вЂ” 1, а Вл=А»=0, Сл — — С»=Е. ФОР- мулы матричной прогонки упрощаются: ад+в=(С вЂ” ад)-, а~=О, 1=1,2, ...,Лдл — 1, ())+~ = ад ы(Р, + () ), 81 = Рл, 1 = 1, 2, °, Лдд —.1, Тд — — а)~дТ)лд+())лд, Тл = Ря, ) = Лдэ — 1, ...,2,1. Векторы Хд и рд имеют размерность Лдд — 1, ад и С вЂ” квадратные мат- рицы раэмерностдд (Лд1 — 1) Х (Лд~ — 1), а достаточное условие устойчиво- сти только одно, илдеет вид 1С Ч! ( 0,5; оно выполнено, так как С) 2Е.
з 2. ДВУХСЛОИНЫЕ ИТЕРАЦИОННЫЕ СХЕМЫ 523 Подсчитаем число действий для определения решения задачи (2) методом матричной прогонки. Так как все матрицы а~ являются полными (хотя С вЂ” трехдоагональная матрица), то для вычисления аьы по заданному а» требуется 0(ят) арифметических операций, а длн вычисления всех ая ) = », 2, ..., )У„и»ЯОО(Лд~Х )опеР»Ций. Далее, Дла опРеДелениЯ Ды, по заданному р; падо 0 (Рз») операций, а для определения всех векторов р) надо 0 (ФР ) операций. Столько же действий надо для вычисления всех Хь Общий объем работы 0 = 0(л~з~.х )операций.
Если решается серия задач, то а» не надо пересчитывать, и при ранении второго и слцдующих вариантов требуется 0 (Хз)У,) нрац й. й 2. Двухслойные итерационные схемы 1. Двухслойные итерационные схемы. Постановка задачи. Пусть требуется решить уравнение первого рода Аи (1) где А: Н- Н вЂ” линейный оператор в конечномерном (размерности )Ч) вещественном пространстве Н со скалярным проиаведением (,) и нормой!1у!! = 1(у, у). Будем предполагать, что А =А*>О, ужН вЂ” любой вектор.
Остановимся сначала на общей характеристике итерационного метода (схемы). Итерационный метод позволяет, отправляясь от некоторого начального приближения уешН, последовательно находить приближенные решения уравнения (1): у„у», ..., у», у,+„..., называемые итерауплми; здесь Й вЂ” номер итерации. Значение у,+, выражается через известные предыдущие итерации у„у„о ... Если при вычислении у,+, используется только предыдущая итерация у„то говорят, что итерационный метод (схема) является одношаговым, а если используются две предыдущие итерации, то метод итераций назьгвают двухшаговым. Мы убедимся в том, что нти методы, по аналогии с гл.
Ч1, естественно называть двухслойным и соответственно трехслойным. Ниже будет показано, что одношаговый итерационный метод по форме совпадает с двухслойной схемой, рассмотренной в гл. Ч1. Любой линейный одношаговый итерационный метод для нахо>кдения приближенного решения уравнения (1) может быть записан в виде В„у»+, — — С»у»'+,и"», й = О, 1, 2, ..., (2) где В» и С» — линейные операторы из Н в Н, зависящие, вообще говоря, от номера итерации й, и"»евН вЂ” заданная функция й, у» — й-я итерация, причем существует В» '.
524 ГЛ. Х. МЕТОДЫ РЕШЕНИЯ СЕТОЧНЫХ РРАВНЕНИй Естественно требовать, чтобы не зависящее от й точное решение и уравнения (1) тождественно удовлетворяло уравнению (2): („— С„) и = Г"». Это воз»южно только при условии (В, — С»)А-'/ В». Отсюда следует, что 1) существует обратный оператор („— С„)-', 2) ) = А(В» — С»)-'Р».
Всегда можно полонсить т»+»(В» — С») =-4 )Р» = Рт»+», й= 0,1,2, ° » где т»+, ) 0 — числовой параметр. В результате получим каноническую форму двухслойной итерационной схемы В» " ' +Ау»=~, й=0,1,2, ... (3) т»+ Прй й = 0 задается произвольное начальное приближение (нулевая итерация) у, »и В. Так как существует обратный оператор В„', то из (3) следует у»+1 у» т»+»В» (Ау» 1)1 (4) ъ-» у»+» = у» — т»+»»'» г» = у» — т»+Ф'Й где т„ =Ау» — / — невязка,ш» = В» Г» — поправка. ' Если итерация у„ известна, то у,+, находится из уравнения (4). Зная у,, последовательно определим у„ у„ ... Очевидно, что итерационный метод имеет смысл, если он сходится, т. е. !!у„— и!! .
0 при й -». а». (5) Обычно задают некоторую погрешность з ) 0 (относительную погрешность !!у„— и!!Л!у, — и!!), с которой надо найти приближенное решение задачи (1). Вычисления прекращают, если выполнено условие !!У» — и!! ~ з!1у» — и!!. (6) Это условие неудобно для практической проверки, так как и— неизвестный вектор, и может быть заменено требованием !!Ау» — ~!! < с!!Ау» — )'!! (7) для невязки г, = Ау„— ~ = Ау, — Ап, которая может быть вычислена непосредственно.
В общем случае вместо (6) пишут неравенство 1у» — и!!в < а!!у, — и!!», (8) где Р =Р* ) 0 — некоторый Оператор. Полагая, например, Р = А', получим из (8) неравенство (7). 6 2. двтхслойньге итеРАционные схемы 525 Напишем уравнение для погрешности г„= у, — н. Так как Ан ),то Вд ""' д +Агд= О, й= 0,1,2,..., задано гдееН. (9) та+1 Если В,=В не зависит от й, то поправка и1„=В 'гд также удовлетворяет однородному уравнению В д+1 " +Аи1д= О. тд+1 В самом деле, из (4) следует у„+, — уд = — тд+,В-'г„— тд+,иъд. Действуя на обе части этого равенства оператором А и учиты- вая, что Ау„+, — Ауд = (Ауд+, — )) — (Ау„— )) = гд+, — г„, г,+, — г„= В(В 'г„+, — В г,) = В(и>„+, — иод), получаем однородное уравнение для иод.
Из (9) видно, что -1~ 22.11 —— Яд+1гд, 82+, — — Š— тд+1Вд А, где Яд+1 — оператор перехода со слоя й на слой й+1. Исключая гд, гд-~, ..., г„имеем при й п — 1 г„= Т„ан Т„8„8„1... Я1Я„ где ҄— разрешающий оператор схемы (9). Отсюда находим !!г„1„!!Т„г !!д ( !!Т„!!д)г1!!ш или !!г„!1„( д„!!г,!!ю Д„!!Т„!1„. Условие окончания итераций выполнено, если д„< в. Таким образом, для выяснения вопроса о сходимости итераций надо оценить норму разрешающего оператора Т„. Схема (3) имеет точную аппроксимацию на решении и уравнения Аи ) при любых операторах (В,) и любых параметрах (тд+1).
Однако величина д„зависит от (В„) и (тд+,). Поэтому В, и т,+, следует выбирать так, чтобы минимизировать норму !!Т„!!а д„разрешающего оператора Т схемы (3). Кроме того, при выборе В„естественно стремиться к минимуму арифметических действий, нужных для определения у,+, при заданном у, нз уравнения Вдуд+~ = А'ь Ед В1Уд тд+1(АУд ~). В этом и состоит основная задача теории итерационных методов. Из предыдущего ясно, что любой итерационный процесс (3) можно формально трактовать как двухслойную схему для реше- 520 ул.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
