Самарский А.А., Гулин А.В. Численные методы (1989), страница 10

Другие методы исследования сходимости разностных схем излагаются в части П1. 44 7. Метод прогонки. Система уравнений (16) представляет собой частный случай систем линейных алгебраических уравнений Ау=( с трехдиагональной матрицей А= [па), т. е. с матрицей, все элементы которой, не лежащие на главной и двух побочных диагоналях, равны нулю (ая=О при 1)1+1 и 1(1 — 1).

В общем случае системы линейных алгебраических уравнений с трехдиагональной матрицей имеют вид а,у,,— с;у;+6;у;+,— — — [ь 1=1, 2, ..., У вЂ” 1, (41) у,=х,у,+Вь у, =х,у,,+рс. (42) Для численного решения систем с трехдиагональными матрицами применяется метод прогонки, который представляет собой вариант метода последовательного исключения неизвестных. Особенно широкое применение метод прогонки получил при решении систем разностных уравнений, возникающих при аппроксимации краевых задач для дифференциальных уравнений второго порядка. Приведем вывод расчетных формул метода прогонки. Будем искать решение системы (41) в виде У~=аыры+Я+ь 1=0, 1, ..., У вЂ” 1, (43) где аыо ~;+,— неизвестные пока коэффициенты.

Отсюда найдем уМ=.' Гу~!+рГ= ж( Ьмуч.+рт.)+В= =а;агмуг„+(а [)у„+~г), 1=1, 2, ..., У вЂ” 1. Подставляя полученные выражения для уь у,, в уравнение (41), приходим при 1=1, 2,..., У вЂ” 1 к уравнению [а~+, (а;а~ — с,) +ЬД ум, + [ [)„, (а;а,— с,) +аф,+Ц = О. Последнее уравнение будет выполнено, если коэффициенты а~+о ~,+, выбрать такими, чтобы выражения в квадратных скобках обращались в нуль. А именно, достаточно положить агм =, Рг~1= г 1=1 2 °, У вЂ” 1 (44) ь! агрг+ гг с~ — а а~ с.— а аГ Соотношения (44) представляют собой нелинейные разностные уравнения первого порядка. Для их решения необходимо задать начальные значения аь 3,.

Эти начальные значения находим из требования эквивалентности условия (43) при /=О, т. е. условия у,=а,у,'+р„ первому из уравнений (42). Таким образом, получаем а,=хо ~,=по (45) Нахождение коэффициентов а,+ь ~м, по формулам (44), (45) называется прямой прогонкой. После того как прогоночные коэффициенты а, „[3+ь 1=0, 1, ..., У вЂ” 1, найдены, решение системы (41), (42) находится по рекуррентной формуле (43), начиная с 7=У вЂ” 1.

Для начала счета по этой формуле требуется знать у„, которое определяется из уравнений уя= холуя-~+)хь уя-~=ияуп+рп и равно (х,р +р,)/(1 — х,а ). Нахождение у; по формулам У!=ачну;,1+реп, !=У вЂ” 1, У вЂ” 2, ...,О, хгрн + Рг ун = 1 — агин (46) называется обратной прогонкой. Алгоритм решения системы (41), (42), определяемый по формулам (44) — (46), называется методом прогонки.

Применяются и другие варианты метода прогонки (см. [32)). Метод прогонки можно применять, если знаменатели выражений (44), (46) не обращаются в нуль. Покажем, что для возможности применения метода прогонки достаточно потребовать, чтобы коэффициенты системы (41), (42) удовлетворяли условиям аФО, Ь1~0, )с,[) [а;~+[Ь![, 1'=1, 2, ..., У вЂ” 1, (47) ) х, [ <1, [ха[(1 (48) Заметим, что числа а,, Ьь сь х„х, могут быть комплексными. Сначала докажем по индукции, что при условиях (47), (48) модули прогоночных коэффициентов аь 1=1, ..., У вЂ” 1, не превосходят единицы. Согласно (45), (48) имеем [сь,) =1х,) (1.

Предположим, что )и,[<1 ДлЯ некотоРого 1 и Докажем, что [их,[ <1. Из оценок [с, — а а;[ ) [[с;[ — [а,[(а;[[ ) [[с,1 — 1а;[[ и условий (47) получаем [с,— а,а;!) [Ь~[)0, т. е. знаменатели выражений (44) не обращаются в нуль. Более того, [1 — х,сс„[) 1 — [х,) 1сс„[) 1 — [х, [ >О, т. е. не обращается в нуль и знаменатель в выражении для у . К аналогичному выводу можно прийти и в том случае, когда условия (47), (48) заменяются условиями а,=ИО, Ь1ФО, [с;[>[а,[+ [Ь~[, 1=1, 2, ..., У вЂ” 1, (49) [х,~<1, [х,[<1. (50) В этом случае из предположения [а,[ <1 следует )с,— аа,[) [ [с,1 — 1а;) [> [Ь;!, [сс~+,1(1, 46 [ь,1 ~ ау+,1= < 1. 1 сг — а;аг ! Следовательно, [а;[ <1, 1=1, 2, ..., У.

Далее, учитывая второе из условий (48) и только что доказанное неравенство [ия~ < 1, имеем т. е. все прогоночные коэффициенты, начиная со второго, по модулю строго меньше единицы. При этом !! — х,а„~)! — !х,~ (а„~ =» )1 — !а„~ )О. Таким образом при выполнении условий (47), (48) (так же как и условий (49), (50)) система (41) — (42) эквивалентна системе (44) — (46). Поэтому условия (47), (48) (или условия (49), (50)) гарантируют существование и единственность решения системы (41), (42) и возможность нахождения этого решения методом прогонки. Кроме того, доказанные неравенства ~ а, ~ (1, 1= 1, 2, ..., Ф, обеспечивают устойчивость счета по рекуррентным формулам (46).

Последнее означает, что погрешность, внесенная на каком-либо шаге вычислений, не будет возрастать при переходе к следующим шагам. Действительно, пусть в формуле (46) при 1=1,+1 вместо уь„вычислена величина у„+,— — у„+,+Ьь+,. Тогда на следующем шаге вычислений, т. е. при 1=!'„вместо у;,=аа„уь„+р +, получим величину уь=аа+,(уз+,+ба+,)+!)а+, и погрешность окажется равной 61,=уг,— у!.=а~; А.. Отсюда получим, что ~б„~~~а„+,~ ~бь+,~()бь+,~, т.

е. погрешность не возрастает. Отметим, что для разностной краевой задачи (16), записанной в виде У- — 2У+Уь = — "Чь 1=1,2, ...,й( — 1, имеем а,=5,=1, с,=2, х,=х2=-0. Поэтому выполнены условия устойчивости (47), (48) и решение задачи (16) можно отыскивать методом прогонки. ЧАСТЬ П ЧИСЛЕННЫЕ МЕТОДЫ АЛГЕБРЫ И АНАЛИЗА ГЛАВА 1 ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕННЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИИ В главах 1, 2 рассматриваются численные методы решения систем линейных алгебраических уравнений Ах=(, (1) где А — матрица ~иупт, х= (х„х„..., х )' — искомый вектор, )= = Ць ~ь ..., 1 )' — заданный вектоР. ПРедполагаетсЯ, что опРеделитель матрицы А отличен от нуля, так что решение х существует и единственно. Для большинства вычислительных задач характерным является большой порядок матрицы А. Из курса алгебры известно, что систему (1) можно решить по крайней мере двумя способами: либо по формулам Крамера, либо методом последовательного исключения неизвестных (методом Гаусса).

При больших гн первый способ, основанный на вычислении определителей, требует порядка т! арифметических действий, в то время как метод Гаусса — только 0(т') действий. Поэтому метод Гаусса в различных вариантах широко используется при решении на ЭВМ задач линейной алгебры. Методы численного решения системы (1) делятся на две группы: прямые методы и итерационные методы.

В пряИых (или точных) методах решение х системы (1) находится за конечное число арифметических действий. Примером прямого метода является метод Гаусса. Отметим, что вследствие погрешностей округления при решении задач на ЭВМ прямые методы на самом деле не приводят к точному решению системы (1) и называть их точными можно лишь отвлекаясь от погрешностей округления.

Сопоставление различных прямых методов проводится обычно по числу арифметических действий (а еще чаще — по асимптотике при больших и числа арифметических действий), необходимых для получения решения. При прочих равных условиях предпочтение отдается методу с меньшим числом действий. Итерационные методы (их называют также методами последовательных приближений) состоят в том, что решение х системы (1) находится как предел при и — ~-ьо последовательных приближений х'"', где и — номер итерации.

Как правило, за конечное число итераций этот предел не достигается. Обычно задается некоторое ма- 46 5 1. Метод Гаусса численного решения систем линейных алгебраических уравнений 1. Основная идея метода. В ближайших двух главах рассматриваются численные методы решения системы линейных алгебраических уравнений Ах=1, (1) где А — вещественная квадратная матрица порядка т, а 1 — заданный и х — искомый векторы.

Будем предполагать, что определитель матрицы А отличен от нуля. Тогда для каждого вектора Г система (1) имеет единственное решение. Запишем систему (1) в развернутом виде а„х,+а„х,+ ... +а, х а„х,+а„х,+ ... +а,, х,„ (2) агп1х1 + плаха + ... + атпмт = ~т. Метод Гаусса решения системы (2) состоит в последовательном исключении неизвестных х„х„..., х„из этой системы. Предположим, что а„ФО. Поделив йервое уравнение на асч получим х,+с„х,+" +с, х =у„ (3) где 'а с»= —, 1=2, ..., ш, ам Уг =— ад лое число е)0 (точность) и вычисления проводятся до тех пор, пока не будет выполнена оценка ачхоя — х1~ < е. (2) Число итераций а=а(е), которое необходимо провести для получения заданной точности е (т. е.

для выполнения оценки (2)), для многих методов можно найти из теоретических рассмотрений. Качество различных итерационных процессов можно сравнивать по необходимому числу итераций п(е). К решению систем линейных алгебраических уравнений сводится подавляющее большинство задач вычислительной математики. В настоящее время предложено колоссальное количество алгоритмов решения задач линейной алгебры (см. (8, 351), большинство из которых рассчитано на матрицы А специального вида (трехдиаговальные, симметричные, ленточные, большие разреженные матрицы). Прямые методы, которые рассматриваются в гл. 1, не предполагают, что матрица А имеет какой-либо специальный вид. На практике оии применяются для матриц умеренного порядка (порядка ста).

Итерационные методы, рассмотренные в гл. 2, можно применять и для матриц высокого порядка, однако их сходимость не очень быстрая. Более совершенные прямые и итерационные методы, учитывающие структуру матрицы, излагаются в части П1. Рассмотрим теперь оставшиеся уравнения системы (2): а„х,+а(,х,+... +а, х =?„(=2, 3,..., т. (4) 'Умножнм (3) на а„и вычтем полученное уравнение нз ('-го уравнения системы (4), (=2, ..., т. В результате получим следующую систему уравнений: х, + с„х, + ...