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