А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 27
Текст из файла (страница 27)
Следующий алгоритм дает решение этой задачи путем последовательного обращения множителей в (36): »/» = ср, С, »,и, = »/, -„! = 1, 2, ., 2»-», причем т/=и,»- . Этот алгоритм мы будем использовать для обращения матриц С'» ". Опишем теперь второй алгоритм метода полной редукции. Прямой ход метода реализуется на основании (34) следующим образом: 1) Задаются значения для ф'. /7)»'= Р~, /=1, 2, ..., У вЂ” 1.
2) Первый шаг для /»=1 осуществляется отдельно по формулам, учитывающим начальные данные р,'"= — О. Решаются уравнения для р,'о и вычисляются ф': С/а/~п = /!)" /7')=2Я>+/7)о)д-(-/7)о', /=2 4 6 У вЂ” 2 (37) 3) Для каждого фиксированного я=2, 3, ..., и — 1 вычисляются и запоминаются векторы т/)м=д» "+р'.,',/,+р'»,,", „ /=2", 2.2», 3 2", ..., У вЂ” 2". (38) Затем при фиксированном !=1, 2, 3, ..., 2* ' для каждого /=2», 2 2», 3 2», ..., У вЂ” 2» решаются уравнения С, и'и = е"-» с,»-» / — / (39) 141 с одной и той же матрицей, но разными правыми частями. В результате будут найдены векторы и,' ' (в формулах (34) этим векторам соответствуют 5,'~ ").
Векторы р)м и ф' вычисляются по формулам з(м з<~~-0 1 пр"- ) ! ! 1 7,'" = 4)" + 75':,".—. + й,'",,~'-. (40) 1=2", 2 2ь, 3 2», ..., У вЂ” 2ь. Обратный ход метода реализуется согласно (35): 1) Задаются значения для )~, и Ум'. У,=- Г„);~= Ел. 2) Для каждого фиксированного lг=п, и — 1, ..., 2 вычисляются и запоминаются векторы ~>(а) 79-0 1 у'. ь, ( ъз 1=2ь-', 3 2"-', 5 2" ', ..., У вЂ” 2ь '. (4 411 Затем при фиксированном 1 — — 1, 2, ..., 2"-' для каждого 1=2ь ', 3 2ь ~, 5.2ь ', ..., У вЂ” 2ь ' решаются уравнения Ф'д = п)~ ~~. ьь-1 1 В результате находятся векторы и' ~ (в (35) им соответствуют векторы Ф)~ ").
Далее вычисляется У по формуле К =р(."- 0+ и<.'-" ч, 1 = — 2" ', 3.2ь ', 5 2ь ', ..., й( — 2" >. (43) 3) Последний шаг обратного хода для й = 1 осуществляется решением уравнения Ср~ — — ~у)н+ ~1,+ Уп„)'=1, 3, 5, ..., й( — 1. (44) (42) Замечание к алгоритму. Все вновь определяемые по формулам (37) и (40) векторы р~м размещаются на месте р,'/'-ь. Все векторы п)ь в формулах (38), (39), (41), (42), вновь определяемые по формулам (37), (40) векторы дчч, а также решение х" из (43) н (44) размещаются на месте ф '. Следовательно, этот алгоритм требует память ЭВМ в 1,5 раза больше, чем число неизвестных в задаче. Уменьшение объема вычислительной работы в данном алгоритме по сравнению с первым алгоритмом основано на том, что при решении серий задач (39) и (42) для различных 1 с одинаковыми матрицами С, ь, полный объем работы затрачивается при решении лишь первой задачи из серии, а при решении каждой последующей задачи потребуется уже значительно меньше арифметических действий.
Приведем число действий для второго алгоритма, обозначая, как и раньше через д — число действий, затрачиваемых на решение уравнения вида (39) или (42) при заданной правой части, а через о — число действий для решения того же уравнения, но с другой правой частью (д(д). 142 Количество действий, затрачиваемых на реализацию прямого кода, равно Я» =~~~ (ОМ( — 1)+ ~д+д( — — 2)12» ') — ЗМ( — — !) = »=! = 0,5дУп -1- (0,5д — 1,5д+ 4,5М) 74 — 6Мп — (4 — 2п+ ЗМ), а обратного хода д, = ~~~' (ЗМ вЂ” + [д + ( — — 1) д1 2»-'~ —— »=1 = 0,5уй7п+(у — у 1-2,5М) л1 — д+и — ЗМ.
Общее число действий для второго алгоритма равно Я=Я,+О»= = д7»' 1ои» У+ (1,5д — 2,5д+ 7М) 7т' — 6Мп — 2о+ Зг1 — ОМ. (45) Из оценки (45) следует, что если д=О(М), то д=О(М) и О =О (МУ 1од, Ж), причем здесь коэффициент при главном члене МЖ!од»У меньше, чем в оценке (29), так как д( д. Кратко остановимся еще на одной особенности второго алгоритма. Если в первом алгоритме обращение матриц С'» " осуществлялось обращением множителей С, „, и последующим суммированием результатов, то во втором алгоритме пооисходит последовательное обращение множителей и результат получается после обращения последнего множителя.
С точки зрения реального вычислительного процесса, который учитывает погрешности округления, порядок обращения множителей С, „, во втором алгоритме является существенным. С аналогичной ситуацией мы встретимся в главе т'1 при изучении чебышевского итерационного метода. Можно рекомендовать следующий порядок обращения матриц С, „,. Матрице С'» " поставим в соответствие вектор 9,»- размерности 2» ', компонентами которого являются целые числа от 1 до 2» '. Пусть 8»»-1 = (8»»-1 (1), 81»-1 (2), ..., 8»»-ъ (2»»)) т. е. 1-й элемент вектора 9»»- обозначен через 9»»- (1).
Число 8,»- (1) определяет очередь обращения матрицы С, »,. Вектор 8»»- строится рекуррентно. Пусть О,— — (2, 1). Тогда процесс удвоения размерности вектора описывается следуюцими формулами: О, = (8,„ (41 — 3) = О (21 в 1), 8»„ (41 — 2) = О (21 в 1) + т, О,, (41 — 1) = 9„ (21) + т, 9, (41) = 8„ (21), 4=1, 2, ..., т12), т=2, 4, 8, ... 143 Пример: 6„=(2, 10, 14, 6, 8, 16, 12, 4, 3, 11, 15, 7, 6, !3, 9, 1) и, следовательно, матрица С, „будет обращаться шестнадцатой, а матрица С„„— седьмой.
$ 3. Примеры применения метода 1. Разностная задача Дирихле для уравнения Пуассона в прямоугольнике. Рассмотрим применение построенного выше метода полной редукции к нахождению решения разностной задачи Дирихле для уравнения Пуассона в прямоугольнике. Как было показано ранее, разностная задача у„-„+у-„„= — ф(х), хЕсо, у(х)=д(х), хЕу, заданная на прямоугольной сетке в=(х, =(1Ь„)й,), 0<1<М, 0<1<37, Ь,М=1„Ь,У=1,), записывается в виде первой краевой задачи для векторных трехточечных уравнений — г,,+Ср' — рт~, = )гт, 1 <1'< й1 — 1, 1 о — ~м ~м= РФ Здесь У~ —— (у(1, 1), у(2, 1), ..., у(М вЂ” 1, 1)), 0(1<0, — вектор неизвестных, компонентами которого являются значе- ния сеточной функции у(1, 1) на 1-й строке сетки, Р =(Ь,'ф(1, 1), Ь',ф(2, 1), ..., Ь',ф(М вЂ” 2, 1), й,'ф(М вЂ” 1, 1)), 1<1<йод — 1, т" =- (д (1, 1), д (2, 1), ..., д (М вЂ” 1, 1)), 1 = О, У, где ф(1, 1)=ф(1, 1)+ — ', д(О, 1), 1 ф(М вЂ” 1, 1) =ф(М вЂ” 1, 1)+ — ', а(М, 1).
й,' Квадратная матрица С соответствует разностному оператору Л, где Лу=2у — й,'у„-„, Ь„<х,<1,— Ь„ у=О, х,=О, 1„ так что СК =(Лу(1, 1), Лу(2, 1), ..., Лу(М вЂ” 1, 1)). Задача (1) может быть решена любым из двух приведенных выше алгоритмов метода полной редукции. Основным этапом этих алгоритмов является решение уравнений вида 144 1<1<М вЂ” 1, (3) где 7(1) = 11 — 1-я компонента вектора о'.
Расписывая разностную производную о„-, по точкам, запишем (3) в виде обычного трех- точечного разностного уравнения для скалярных неизвестных о(1) =об — ог,+ао1 — о,+,—— Ь70 1<1<М вЂ” 1, (4) о,=ом =О, где а=2 ~1+Ь (1 — соз (21 — 1)я~1 а1~ 2" ) ! 6~2 д, Ь= —. Задача (4) является специальным случаем трехточечных краевых задач, методы реше- ния которых были изучены в главе 11. Было показано, что эффективным методом решения задач вида (4) является метод прогонки.
Приведем расчетные формулы метода прогонки для задачи (4): а,~, = 1/(а — а;), р1+1 = (Ь71 + р ) а1+1 Ог = а1+1О1+г+ Р1н1 1=1,2, ..., М вЂ” 1, а,=О, 1=1, 2, ..., М вЂ” 1, (1,=0, (=М вЂ” 1, М вЂ” 2, ..., 1, ом=О Из этих формул следует, что задача (4), следовательно, и уравнение (2), при заданных а и Ь могут быть решены с затратой д=7(М вЂ” 1) действий.
Для решения уравнения (2) с другой правой частью Г прогоночные коэффициенты а1 пересчитывать не нужно, и поэтому дополнительное число действий д равно д= 5(М вЂ” 1). Эти действия будут затрачены на вычисление ()! и на нахождение решения о,. Отметим, что метод прогонки для (4) будет численно устойчив, так как достаточное условие устойчивости метода к ошибкам округления, имеющее в данном случае вид а)2, выполнено. 14$ с заданной правой частью г"'. Здесь У вЂ” вектор неизвестных, К=(о(1), о(2), ..., о(М вЂ” 1)) размерности М вЂ” 1 (для упрощения записи индекс у У и т' опущен).
Напомним, что число действий, затрачиваемых на решение задачи (1) по первому алгоритму, определяется числом действий д, требуемых для решения уравнения (2) (см. (29) п. 3 2 2), а по второму алгоритму — в основном числом дополнительных действий д, которое требуется затратить на решение уравнения (2), но с другой правой частью (см. (45) п. 4 3 2). Для рассматриваемого примера приведем способ решения уравнения (2) и оценим д и д.
Из определения матрицы С следует, что решение уравнения (2) эквивалентно нахождению решения следующей разностной задачи: 2(1 — соз ) о — Ь,'о- =7(1), (21 — 1) яч 2а ) х,х, о(0) =о(М)=0, 2 (! — соз (2! — !) М ).— Л;.— =1, 2а ) ~ х,а, Ьа (2! — 1) ат 2(е 2 ~1+ — х — соз ~ о — — о ь, 2а ) Й, ья (2( — 1) м 2ь~ 2 (1+ — х — соз ~~ о-1- — '- о- = ~, ь~ +~ ) ь 1((<М вЂ” 1, !'=О, Эта задача в обычной трехточечной форме имеет вид 1:.1(М вЂ” 1, —,,+ —;,=ЬР;, "о = хР~+ р~ ом =хавм-~+р„ (5) где а+2а,х, ' ' а+2а,х~, ' ! ' а+2а,х ~ ' р~ а-(-2Ь х+, ° а а и Ь определены выше.
Так кака>2 и хь,)О, то 0<х,<! и 0<х,<1, и метод прогонки решения задачи (5) будет также устойчив, а алгоритмы метода полной редукции и в этом случае будут требовать О (МЛ( 1од, Л() арифметических действий. 2. Разностная задача Дирихле повышенного порядка точности. В п. 4 2 1 разностная задача Дирихле для уравнения Пуассона 146 Подставляя д в оценку (29) п.
3 2 2 для числа действий первого алгоритма, получим, удерживая главные члены, (',)<" ж ж9,5МЛ!1оя, Л( — 8МЛ(. Для второго алгоритма из оценки (45) п. 4 2 2 получим следующую оценку для числа действий: ()"'ж 5МЛ(1оя, )т'+ 5МЛ(. Итак, для каждого из рассмотренных алгоритмов число действий метода полной редукции, применяемого для решения разностной задачи Дирихле для уравнения Пуассона в прямоугольнике, есть величина порядка О (МЛ( 1од,Л(), причем для второго алгоритма требуется меньше арифметических действий.
Например, для М=Л(=64 получим (~"'ж 1,4Яе> и для М=Л(=128 соответственно (,"го-1,469'м. Мы не будем приводить расчетные формулы для алгоритмов решения указанной разностной задачи, так как на векторном уровне они подробно описаны в 2 2. В п. 2 2 ! были приведены примеры других разностных краевых задач, которые сводятся к задаче (1). Они отличаются от рассмотренной задачи Дирнхле типом краевых условий на сторонах прямоугольника при х, =-0 и х, = 1„ что приводит к различным матрицам С.
Так для задачи (10) †(12) п. 2 2 1 с краевыми условиями третьего или второго рода при х, = О, 1, уравнение (2) эквивалентно разностной задаче повышенного порядка точности Ь',+ Ь.,' у(х)=д(х), хну была сведена к первой краевой задаче для неприведенного трехточечного векторного уравнения — ВУ +АУ вЂ” ВУ'.,»=/о', 1(/(Л( — 1, »о=»о Квадратные матрицы В и А размерности (М вЂ” 1)х(М вЂ” 1) соответствуют разностным операторам Л, и Л, где 12+),о и у=О для х, =О и х,= 1,.
Было показано, что если выполнено условие /о,()~26„то уравнения (6) приводятся к стандартному виду — 17,+С~ — 1)„=Ф, 1</<Л1 — 1, 1 о Фоо У'о Фл (7) где С=В-'А, Ф =В 'Г7, 1(/(Л( — 1 и Ф = Г для 1=0, ЛГ. Кроме того, было отмечено, что матрицы А и В перестановочны. Для решения (7) используем первый алгоритм метода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
