Описание метода прогонки

Метод прогонки представляет собой вариант метода Гаусса, примененный к специальным системам линейных алгебраических уравнений (СЛАУ), и учитывающий ленточную структуру матрицы системы.

Матрица A такая, что ее элементы для всех , называется ленточной.

Пусть имеем, СЛАУ со специальной трехдиагональной формой матрицы, т. е. с матрицей, все элементы которой, не лежащие на главной и двух побочных диагоналях, равны 0 ( при и )

;

, ; (3.1)

,

или в матричной форме: , где - вектор неизвестных; - вектор правых частей; A - квадратная матрица

. (3.2)

Системы вида (3.1) возникают при аппроксимации краевых задач математической физики, описываемых обыкновенными дифференциальными уравнениями второго порядка с постоянными и переменными коэффициентами, а также уравнениями в частных производных. Ставится задача разработать экономичные методы решения задач вида (3.1), число арифметических операций для которых пропорционально числу неизвестных. Таким методом для системы (3.1) является метод прогонки.

Специфика матрицы A системы (3.1) состоит в расположении ненулевых элементов, матрица A - разреженная матрица, из элементов которой ненулевыми являются не более элементов. Это позволяет получить для решения СЛАУ простые расчетные формулы. Будем искать решение (3.1) в виде

, (3.3)

с неопределенными коэффициентами , . Выражение подставим в (3.1)

с учетом (3.3) имеем

.

Это равенство имеет место для любых , если

, .

Отсюда получаем рекуррентные формулы для определения ,

, ; (3.4)

. (3.5)

Коэффициенты , , называются прогоночными.

Если коэффициенты и известны, а также известно то, двигаясь справа налево (от i+1 к i) последовательно, определяем все . Задача нахождения , по формулам (3.4), (3.5) решается слева направо (от i к i+1). Начальные значения прогоночных коэффициентов , можно определить следующим образом. Полагаем в формуле (3.3) , имеем , а из первого уравнения (3.1) , откуда

. (3.6)

Значение определяется следующим образом. Полагаем в формуле (3.3) , имеем , а из последнего уравнения (3.1) , откуда

. (3.7)

Расчетные формулы (3.3) - (3.7) можно получить также из (3.1), если применить метод исключения Гаусса. Прямой ход метода заключается в том, что на первом шаге из всех уравнений системы (3.1) при помощи первого уравнения исключается , затем из преобразованных уравнений для при помощи уравнения, соответствующего , исключается и т.д. В результате получим одно уравнение относительно . На этом прямой ход метода прогонки заканчивается. На обратном ходе для находятся .

Порядок счета в методе прогонки следующий:

- исходя из значений , , вычисленных по формулам (3.6), все остальные коэффициенты , для определяются последовательно по формулам (3.4) и (3.5);

- исходя из значения , рассчитанного по формуле (3.7), все остальные неизвестные , определяются последовательно по формуле (3.3).

Изложенный метод поэтому называется правой прогонкой.

Аналогично выводятся формулы левой прогонки:

, , ; (3.8)

, , ; (3.9)

, , . (3.10)

Здесь находятся последовательно для значений ; ход вычислений - слева направо.

В случае, если необходимо найти только одно неизвестное, например, или группу идущих подряд неизвестных, целесообразно комбинировать правую и левую прогонки. При этом получается метод встречных прогонок.

Получим расчетные формулы метода встречных прогонок. Пусть , по формулам (3.4), (3.5), (3.8), (3.9) найдем прогоночные коэффициенты ; , а также ; . По формулам (3.3) и (3.10) при найдем

откуда определяем

С помощью по формулам (3.3) последовательно находятся с помощью формулы (3.10) последовательно находятся

Формулы метода встречных прогонок имеют вид

для прогоночных коэффициентов и

для определения решения.

Произведем подсчет числа арифметических действий для метода правой прогонки. Анализ формул (3.3)-(3.7) показывает, что общее число арифметических операций есть . Коэффициенты не зависят от правой части СЛАУ (3.1) и определяются только элементами , , матрицы A. Поэтому, если требуется решить серию задач (3.1) с различными правыми частями, то прогоночные коэффициенты вычисляются только для первой серии. Для каждой последующей серии задач определяются только коэффициенты и решение , причем используются ранее найденные .

На решение первой из серии задач расходуется операций, а на решение каждой следующей задачи операций. Число арифметических операций, необходимое для решения СЛАУ (3.1) методом левой прогонки и методом встречных прогонок такое же, т.е. .

Метод правой прогонки будем называть корректным, если при .

Решение находится по рекуррентной формуле (3.3). Эта формула может порождать накопление ошибок округления результатов арифметических операций. Пусть прогоночные коэффициенты и найдены точно, а при вычислении допущена ошибка , т.е. . При вычислениях с помощью формулы (3.3) мы получаем

. (3.11)

Вычитая из (3.11) значение по формуле (3.3) имеем для погрешности с заданным . Отсюда ясно, что если по модулю больше единицы, и если N достаточно велико, то вычисленное значение будет значительно отличаться от искомого решения . В этом случае говорят, что алгоритм прогонки неустойчив.

Определение. Алгоритм прогонки называется устойчивым, если , .

Условия корректности и устойчивости алгоритма правой прогонки определяются следующей теоремой.

Теорема. Пусть коэффициенты системы (3.1) действительны и удовлетворяют условиям:

, ;

, ; (3.12)

, ; (3.13)

причем хотя бы в одном из неравенств (3.12) и (3.13) выполняется строгое неравенство, т.е. матрица A имеет диагональное преобладание. Тогда для алгоритма (3.3)-(3.7) имеют место неравенства: , , , т.е. алгоритм метода правой прогонки корректен и устойчив.

Условия теоремы (3.12) и (3.13) обеспечивают также корректность и устойчивость алгоритмов левой и встречных прогонок. Эти условия сохраняются и для случая системы (3.1) с комплексными коэффициентами , , .

Легко показать, что при выполнении условий теоремы (3.12)-(3.13) система (3.1) имеет единственное решение при любой правой части. Действительно, при проверке легко убедиться в том, что матрица A представляется в виде произведения двух треугольных матриц L и R,

,

где

и . Так как

в силу выполнения условий теоремы система (3.1) имеет единственное решение при любых ее правых частях.

Варианты заданий