А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 68
Текст из файла (страница 68)
Приведенные в таблице значения для р» хорошо иллюстрируют асимптотическое свойство метода. Видно, что с ростом номера итераций происходит замедление скорости сходимости метода. Точность 4.10 ' была достигнута за 26 итераций, а на увеличение точности еще в 40 раз потребовалось провести дополнительно 23 итерации. Величина р» монотонно возрастает и для й = 26 имеем р +, — р» = 3 10 '. Итерационные параметры т» и т , становятся почти равными. Для сравнения приближенных значений у(" и ф' с точными приведем у, и у,: у, = 18,26556, у, = 232,8036. После выполнения 49 итераций у, было найдено с точностью 0,004У», а у,— с точностью 0,6%. Для ускорения сходимссти метода была применена описанная в п.
1 процедура ускорения. По приближениям у„и ум, найденным по схеме (18), было построено по формулам (6), (9) новое приближение д. Заданная точность е=-10 ' была достигнута. Применение построенного в этом параграфе способа ускорения сходимости двухслойных градиентных методов позволило уменьшить число требуемых итераций для рассматриваемого примера приблизительно в 1,8 раза. ГЛАВА !Х ТРЕУГОЛЬНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ В главе изучаются неявные двухслойные итерационные методы, оператору В в которых соответствуют треугольные матрицы. В 1! рассматривается метод Зейделя, для которого формулируются достаточные условия сходимости. В 1 2 исследуется метод верхней релаксации. Здесь дан выбор атерационного параметра и получена оценка для спектрального радиуса оператора перехода.
В б 3 рассмотрена общая итерационная схема треугольных методов, указан выбор итерационного параметра и доказана сходнмость метода в норме Ол. В 1. Метод Зейделя 1. Итерационная схема метода. В предыдущих главах была изложена общая теория двухслойных и трехслойных итерационных методов, применяемых для нахождения приближенного решения линейного операторного уравнения первого рода Аи=Г. (1) Эта теория указывает выбор итерационных параметров и дает оценку для числа итераций соответствующих методов, причем теория использует минимум информации общего характера относительно операторов итерационной схемы. Отказ от изучения конкретной структуры операторов итерационной схемы позволяет развивать теорию с единой точки зрения и конструировать неявные итерационные методы, оптимальные на классе операторов В.
В общей теории итерационных методов было показано, что эффективность метода существенным образом зависит от выбора оператора В. От выбора оператора В зависят как число итераций, которое нужно выполнить для достижения заданной точности и, так и число арифметических действий, требующихся на реализацию одного итерационного шага. Каждая из этих величин в отдельности не может служить критерием эффективности итерационного метода.
Поясним это утверждение. Пусть операторы А и В самосопряжены и положительно определены в Н. Из теории итерационных методов следует, что если в качестве оператора 0 взять один из операторов А, В или АВ 'А, то число итераций для рассмотренных в гл. И вЂ” И11 итерационных методов (чебышевского, простой итерации, методов вариационного типа и т. д.) опРеделЯетсЯ отношением й = У,!Тю где У, и У,— постоЯнные энеР- гетической эквивалентности операторов А и В: Т,В(А(узВ.
366 Поэтому, если выбрать В= А, то получим максимально возможное значение $=1, и итерационцые методы дадут точное решение уравнения (1) за одну итерацию при любом начальном приближении. Следовательно, указанный выбор оператора В минимизирует число итераций. Однако для реализации этого единственного итерационного шага требуется обратить оператор В, т. е. оператор А. Очевидно, что при этом число арифметических действий будет максимальным. С другой стороны, для явных схем с В = Е требуется минимальное число арифметических действий на одну итерацию, но при этом число итераций становится слишком большим.
Итак, возникает задача оптимального выбора оператора В из условия минимизации общего объема вычислительной работы, которая должна быть-выполнена для получения решения с заданной точностью. Естественно, что в такой общей постановке эта задача не может быть решена.
В настоящее время развитие итерационных методов идет по пути конструирования легко обратимых операторов В, среди которых выбирают операторы с наилучшим отношением у,17,. К легко обратимым или экономичным операторам обычно относят такие операторы, обращение которых осуществляется за число арифметических действий, пропорциональное или почти пропорциональное числу неизвестных. Примерами таких операторов являются операторы, которым соответствуют диагональная, трехдиагональная, треугольные матрицы, а также их произведения. В качестве более сложного примера приведем разностный оператор Лапласа в прямоугольнике, который, как было показано в главе 1Ч, можно обратить прямыми методами с малыми затратами арифметических операций. Следует отметить, что использование в качестве оператора В диагональных операторов позволяет уменьшить число итераций по сравнению со случаем явной итерационной схемы.
Однако асимптотический порядок зависимости числа итераций от числа неизвестных задачи остается таким же, как и для явной схемы. Более перспективным направлением является использование треугольных операторов В. В настоящей главе и главе Х будут рассмотрены универсальные двухслойные неявные итерационные методы, оператору В в которых соответствуют треугольные матрицы (треугольные методы) или произведение треугольных матриц (попеременно-треугольный метод). Рассмотрение этих методов начнем с простейшего — е метода Зейделя. Рассмотрим систему линейных алгебраических уравнений (1) или в развернутом виде ~ а; иу = )о 1 = 1, 2, ..., М.
7=! 367 В данном случае мы имеем дело с уравнением (1), заданным в конечномерном пространстве Н = Нм. Итерационный метод Зейделя в предположении, что диагональные элементы матрицы А =(а; ) отличны от нуля (аа,-ьО), записывается в следующем виде: с М ~~ ~а~ удав+ ~ ану)м=~н 1=1, 2, ..., М, (2) +, ~ где у)м — 1-я компонента итерационного приближения номера я. В качестве начального приближения выбирается произвольный вектор. Определение (я+1)-й итерации начинаем с 1=1: а„у1ын = — ~ а„у,'"'+),. /= 2 Так как ам~О, то отсюда найдем у,'ь"'. Для 1=2 получим М а„у(ын = — а„ум"' — ~ а,~у',~'+ !', 1=з Пусть Уже найдены у,""', у," ", ..., у)ь;".
Тогда ум"' находится нз уравнения С-1 м аау,'" о = — ~ а;,у',"'" — ~~'., аыу';"+ ~н (3) /=1 !=~+1 Из формулы (3) видно, что алгоритм метода Зейделя является чрезвычайно простым. Найденное по формуле (3) значение у,'"~о размещается на месте у',~>. Оценим число арифметических действий, которое требуется для реализации одного итерационного шага.
Если все а~ не равны нулю, то вычисления по формуле (3) требуют М вЂ” 1 опеаций сложения, М вЂ” ! операций умножения и одного деления. оэтому реализация одного итерационного шага осуществляется за 2М' — М арифметических действий. Если в каждой строке матрицы А отлично от нуля лишь т элементов, а именно эта ситуация имеет место для сеточных эллиптических уравнений, то на реализацию итерационного шага потребуется 2глМ вЂ” М действий, т.
е. число действий, пропорциональное числу неизвестных М. Запишем теперь итерационный метод Зейделя (2) в матричной форме. Для этого представим матрицу А в виде суммы диагональной, нижней треугольной и верхней треугольной матриц А=Ы+Е+У, зба где ~о ам о) азз азз о а„ азм азМ о аз, О и=-~~ ' "зз амз ". амм з 01 о ам зм О ~ ам азз о амм Обозначим через уз- — -(у(зз, у.',з', ..., у$) — вектор Ьго итерационного приближения. Пользуясь этими обозначениями, запишем метод Зейделя в виде В""' "'+Ауз=~, ззэз А=О, 1,, УзЕН, находим, что В=йй+Е, т„=!.
Схема (5) неявная, оператор В является треугольной матрицей и, следовательно, несамосопряжен в Н. Мы рассмотрели так называемый точечный или скалярный метод Зейделя, предполагая, что элементы а; матрицы А есть числа. Аналогично строится блочный или векторный метод Зейделя для случая, когда ап есть квадратные матрицы, вообще говоря, различной размерности, а а;, для 1~1 — прямоугольные матрицы. В этом случае уз и ~; есть векторы, размерность которых соответствует размерности матрицы ап. В предположении невырожденности матриц ап блочный метод Зейделя записывается в виде (2) или в каноническом виде (5).
2. Примеры применения метода. Рассмотрим применение метода Зейделя для нахождения приближенного решения разностной задачи Дирихле для уравнения Пуассона и эллиптического уравнения с переменными коэффициентами в прямоугольнике. Пусть на прямоугольной сетке аз = (х;, =(й„)йз) Е 6, О(1< (У„О(1(У„Ь„= 1„(Н„, а= 1, 2), введенной в прямоуголь- 369 (И+Цр„,+ид„=), А=О, 1, ... Приведем эту итерационную схему к каноническому виду двухслойных схем (йР+1,)(Уз+; — Уа)+АУз=~, А=О, 1, ..., УзЕН, (5) Сравнив (5) с каноническим видом нике 6=(О(х„(1„, а=1, 2), требуется найти решение разностной задачи Дирнхле для уравнения Пуассона 2 Лу= ~ у-„, = — <р(х), хЕв, у(х)=д(х), хну, (6) где 7.=(х, ЕГ) — граница сетки в. В данном примере неизвестными являются у(1, 1) =у(х, ) во внутренних узлах сетки. Если упорядочить неизвестные естест- венным образом по строкам сетки в, начиная с нижней строки, то разностная схема (6) может быть записана в виде следующей системы алгебраических уравнений: 1 ..
! .. / 2 2 < — — 2У(< 1 !) 2 У(' 1 1)+( 2 + 2)у(< 1) Ь< !2'1!2!2) У (< 1 1) 2 У (' 1 + 1) — <р (1 !) для 1 — 1 2 ..., Л!2 — 1, 1==1, 2,..., Л<,— 1 н у(х) = д(х) для х Е у. Прн этом неизвестные у(<' — 1, 1) н у(1, ! — 1) предшествуют у(< !) а у(<+ 1, !) н у(2, 1+ 1) следуют за у(1, !). Так как в каждом уравнении связаны не более пяти неизвестных, то в каждой строке матрицы А отличны от нуля не более пяти элементов, Для рассматриваемой системы точечный метод Зейделя будет иметь следующий вид: (' )" з2 + 2 )Уьэ<(<2 1) = 2 Уи;2(< — 1 1)+ 2 У2~«(< ! 1)+ 1 1 2 1 ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
