Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 69
Текст из файла (страница 69)
При нахождении граничных условий для р;Еьи СЛЕдуЕт ПпетуиатЬ таК жЕ, КаК И В СЛуЧаЕ СХЕМЫ (12), (13), т. Е. ВЫраЗИтЬ УЕГ'г нз уравнений (24) или (25) через у,".,Ег, р,"; и доопределить у,"ети на границе с помощью полученного выражения. ГЛАВА 5 ПРЯМЫЕ И ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИЙ $1. Модельная задача 1. Введение.
Как мы уже видели, аппроксимация дифференциальных уравнений разностными приводит к системам линейных алгебраических уравнений Ад=-(, (() которые нецелесообразно, а чаще всего и невозможно решать стан- дартными вычислгпельными методами линейной алгебры. 378 В этой схеме каждое из уравнений в отдельности не аппроксимирует исходное уравнение (!), однако имеет место суммарная аппроксимация 0(тч-ат).Действительно, в данном случае — -(- Лги,".зи = 0,5 + Ьти (х,Е, Е„) +0(т+ат)=0(1), в единичном квадрате б(0(хь х2(1) с границей Г.
Введем в 6 квадратную сетку с шагом й, т, е. множество точек Й1, = (хп = (х~1~, ха)), где хю =16, х<"=)й, 1, )=1, 2,..., А', 11%=1. Пусть, как обычно, 1 2 Е21 — МНОжсетВО ВНУтРЕНННХ ТОЧЕК И т2 — МНОжЕСтВО ГРаНИЧНЫХ тО- чек сетки й,. Заменим исходную дифференциальную задачу разностной за- дачей У2,2Ы1 + УХьвп) Хн1гл ГЕМ (2) уи=-о, Х21еБ („ которую будем рассматривать как модельную при изучении мето- 379 Если исходной задачей является краевая задача для обыкновенного дифференциального уравнения, то соответствующую разностную схему можно решить с помощью метода прогонки (см.
п, 7 2 4 ч. 1). В многомерном случае не свшестичет столь же удобного и экономичного способа решения разностных уравнений, как метод прогонки. Поэтому возникает необходимость в развитии методов, специально предназначенных для решения многомерных разаостных краевых задач. Мы будем рассматривать здесь лишь двумерные разностные задачи.
Как и в общем случае систем линейных уравнений, методы решения разностных задач разделяются на прямые и итерационные, Итерационные методы являются более простыми, чем прямые, и в меньшей степени используют структуру матрицы. По этой причине для решения двумерных разностных уравнений первоначально использовались исключительно итерационные методы.
Однако в случае разностных задач сходимость таких, например, методов, как метод простой итерации, Зейделя, верхней релаксации, весьма медленная. В настоящее время интенсивно развиваются и прямые методы решения двумерных разностных уравнений.
Они применимы, как правило, к уравнениям с разделяющимися переменными, когда область изменения независимых переменных — прямоугольник. Наконец, следует отметить все возрастающее значение неявных итерационных методов, в которых решение на новой итерации находится тем или иным прямым методом. Хотя такие методы алгоритмически сложнее, чем явные, их несомненным преимуществом является существенно более быстрая сходимость. 2.
Модельная задача. Методы решения двумерных разностных краевых задач мы будем иллюстрировать в дальнейшем на следующем простом примере. Рассмотрим задачу Дирихле для уравнения Пуассона д2и дзи — + — = — 1(х), х = (х„х,) = б, дх2 дк2 1 2 и(х) =О, х= (х„х,) ~Г дов решения сеточных уравнений. Подробнее задачу (2) можно записать в виде системы у;; — 2у; + уг, ! угп„— 2у;1+ уг; (3) Ьв пв ун=ул=О, ур,=Див=О, 1', 1=1 На этом примере хорошо видны характерные особенности систем уравнений, возникающих при аппроксимации многомерных задач математической физики.
Матрицы таких систем характеризуются высоким порядком, сильной разреженностью (т. е. преобладанием нулевых элементов) и большим разбросом собственных чисел. Действительно, порядок системы 2 совпадает с числом то- () б чек сетки орв и равен (гьг — 1) '. Даже при й=0,1 имеем (йг — 1)'= =81, т. е. матрица системы (2) — — ~- . „. вк рР В Р.ВНВР о г ." з л в ' порядка. На более типичной сетРис.
!4. Однамернвя нумерации дву- ке, когда шаг й=0,01, порядок мерного мяссивв системы равен примерно 10 000. Сильная разреженность видна из того, что каждое уравнение системы (3) содержит не более пяти отличных от нуля коэффициентов. Тем самым отношение числа ненулевых элементов данной матрицы к общему числу ее элементов не превосходит б/(йг — 1)'= 0(й').
Собственные числа матрицы, отвечающей системе (2), найдены в 5 2 гл. 3. Для иас существенно сейчас, что отношение наименьшего собственного числа Тв к наибольшему собственному числу Т, равно т,, па г = — = !йв— тх 2 Отношение й является величиной второго порядка малости при й -О, а именно $ = + 0(й'). (4) 4 Следствием малости величины й является плохая обуслонленность системы (2).
Ло этой же причине явные итерационные методы для системы (2) сходятся медленно. Чтобы зкпнсвть систему двумерных ркзностных уравнений в матричном пи° кр-г де (1), надо провести псренумсрэцию двумерного массива индексов (1, 1)г; в одномерный массив, Это можно сделать различными способкми. Сопоставим, нвпрнмер, индексу (1, 1) двумерного мэссивя индекс Д одномерного мэсснвя по правилу 12=(йр — 1) (1 — 1) е1 (см.
рис. 14). При этом, если 1 н 1 меняются в пределах от 1 до ДР— 1, то я меняется от 1 до (Л/ — 1)2. В результате указанной пе- ззв реиумерации система уравнений (3) запишется в аиде у „— 4уь+ уь „у и,!+ Уь»!и,! — г'ь (5) Уравнения (5) определены для л=(йà — 1)(ь — 1)+й й /=2, 3, ..., 5» — 2. уь-ьн-и — 4уь+уьч~= — Ц», у= (й» вЂ” !) (й) — 2) +1 (1=!у — 1, Уь-~х-и+у»-; — 4у»+у»+~= — а»1», Й= (!У вЂ” !)(йà — 2) зл!' (1=Л' — 1, (=2, 3,, !У вЂ” 2), Уь-ьх — о+у» — ~ — 4У»= — й»(», й= (Ч вЂ” 1)» ((=Ж вЂ” 1, ! йг — 1) Матрица системы (5) для случая )ь»=5 условно изображена на рис, 15, где крестиками отмечены ненулевые элементы. Заметим, что при решении системы (3) иет необходимости записывать ее в виде (5), мы привели такую запись лишь для того, чтобы еше раз продемонстрировать разреженность матрины и ее ленточную структуру.
3. Применение методов Якоби и Зейделя. Запишем разностное урав- нение Пуассона (2) в операторной форме (1), где оператор А опреде- лен следующим образом: ххх х х х х х х х х х х (6) до=О, хьс=у». В дальнейшем будем рассматривать для зтого уравнения одношаговые итерационные методы, записанные в каноническом виде (см, 3 1 гл. 2»!. П), В "" " +Ау„= !". (7) тл»ь ххх х! (х -! хмхх х х х! х Рис. 15. Структура матрицы си- стемы (5) для йг=5 Начнем с наиболее простых методов — Якоби н Зейделя. Покажем, что зти методы сходятся, однако их скорость сходимостн невысока.
При остальных значениях гс учитывая нулевые граничные условия, получим сле- луюшие уравнения: — 4у~+утч-ух= — й»(ь х=1 (ь=! ! — !) у»-» — 4у +уь„,+ульи,= йь(„ а=2, 3, ..., йà — 2 (»=1, 1=2, 3, „, й( — 2) ух-ь — 4ун-~+уыи-и= — Ьь(» и й й» вЂ” ! (1= ! ' — й) У»-(и-о — 4У»+уьчл+у»их о= — а(ь, й=(йг — 1)(! 1).» 1 (ь=2, 3,, Лг — 2, 1=1), — 4У»+Уь-~+У» — <и — и+у»мх — и= — )ь»1», й= (йг — 1)ь' (1=2, 3... йà — 2, )=йг — 1), !), Метод Якоби для системы (3) записывается в виде У~;"= — (У'-ь)+У' у+Ус!- +Уь! +и/у)* х!/Е= <ем 4 (8) у,",=-О, хо Е=ум Здесь у,",.— значение решения в точке хосни, на и-й итерации. В дан- ном случае метод Якоби совпадает с методом простой итерации при оптимальном значении итерационного параметра.
Действительно, метод простой итерации (у„„,— у„)/т+Ау„=/ для системы (!) в случае А'=А>О обладает наибольшей скоростью сходимости, если т=т,=2/(б+/!), где б„б — наименьшее и наибольшее собственные числа матрицы А (см. $ 6 гл. 2 ч. 11). Для разностного оператора Лапласа имеем (см. ф 2 гл. 3) 8 . ела 8 епя 6= — з)пе —, Л= — соз' —, и~ 2 ае 2 следовательно, т.=й'/4. При этом значении параметра метод про- стой итерации н случае модельной задачи (2) принимает вид ри ру а а у',.',. = О„ху е= уь.
Последнее уравнение, как нетрудно видеть, совпадает с уравнением (8). Скорость сходимости метода (8) как метода простой итерации с оптимальным параметром определяется числом р = —, 5 — = ! =†8 !+а д 2лЛ = !а— а Число итераций п,(е), необходимых для достижения заданной точности е, раино п,(е) =!и — 1п — =1п — !п!! +— е/ р е/ ~ ! — $ иеае ! и1!Р При й — ~-О имеем $= —, !и — =25= —, так что 4 р 2 и (е) = па' (9) Следовательно, метод Якоби требует 0(п-') итераций для достижения заданной точности.
Это очень медленная сходимость. В настоящее время применяются методы, требующие 0(й-') и даже О(!ой ') итераций для достижения той же точности. С этими методами мы познакомимся в 8 2, 3, 4, 882 Рассмотрим метод Зейделя для системы (3). В общем случае (см. $1 гл. 2 ч. 11) метод Зейделя строится таким образом, чтобы в уравнении с номером ) неизвестные, имеющие индекс больший, чем г', вычислялись бы по значениям на п-й итерации. Реализация метода Зейделя для системы (3) приводит к следующему итерационному методу: чы 2 чьт ~ ч ч+т 2,лтт ~,л УГ гз УП + Умгу У).)-т О~у + кд!ы Из аа — х)! гш ши ) ~ — э (10) (12) у",." = О, кн ~ уи.
Хотя метод Зейделя является неявным, нахождение значений д",." на новой итерации не представляет труда, поскольку оно сводится к обращению треугольной матрицы. Здесь нужно лишь правильно установить последовательность проведения вычислений. Сначала из уравнения (10), используя известные граничные значения у'+) = 0 и уч+' =О, находят у"". Зная ул", можно найти у""' аг га 11 зз )з и т. д. Таким образом, неизвестные у!ч) вычисляются в следую)/ щем порядке изменения индексов: (1, 1), (1, 2), ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
