Метод прогонки

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Метод прогонки (англ. tridiagonal matrix algorithm) или алгоритм Томаса (англ. Thomas algorithm) используется для решения систем линейных уравнений вида , где  — трёхдиагональная матрица. Представляет собой вариант метода последовательного исключения неизвестных[1]. Метод прогонки был предложен И. М. Гельфандом и О. В. Локуциевским (в 1952 году[2]; опубликовано в 1960[3] и 1962[4] годах), а также независимо другими авторами[5].

Описание метода[править | править код]

Система уравнений равносильна соотношению

Метод прогонки основывается на предположении, что искомые неизвестные связаны рекуррентным соотношением:

где

Используя это соотношение, выразим и через и подставим в уравнение (1):

,

где Fi — правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать

Отсюда следует:

Из первого уравнения получим:

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

Другим способом объяснения существа метода прогонки, более близким к терминологии конечно-разностных методов и объясняющим происхождение его названия, является следующий: преобразуем уравнение (1) к эквивалентному ему уравнению

c надиагональной (наддиагональной) матрицей

.

Вычисления проводятся в два этапа. На первом этапе вычисляются компоненты матрицы и вектора , начиная с до

и

На втором этапе, для вычисляется решение:

Такая схема вычисления объясняет также английский термин этого метода[прояснить] «shuttle»[источник не указан 675 дней].

Для применимости формул метода прогонки достаточно свойства диагонального преобладания у матрицы A.

Пример использования[править | править код]

Трёхдиагональные матрицы, для обращения которых применяется метод простой прогонки, нередко возникают при решении дифференциальных уравнений двух независимых переменных методом конечных разностей. Рассмотрим для примера решение линейного одномерного уравнения теплопроводности:

где — положительная константа (число является коэффициентом температуропроводности) и — функция тепловых источников[6]. Искомая функция задает температуру в точке с координатой в момент времени .

Проведём дискретизацию этого уравнения на равномерной сетке с пространственным шагом и временным . При этом непрерывные функции и заменяются на их дискретные аналоги и , а пространственная и временная производная — на конечные разности:

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

Перенеся известные величины в правую часть, домножив на и сгруппировав коэффициенты, приведём СЛАУ к окончательному виду

Вид матрицы коэффициентов для конечных точек разностной сетки определяется граничными условиями и выводится отдельно. Наличие диагонального преобладания у матрицы коэффициентов гарантирует устойчивость метода прогонки при решении им данной СЛАУ.

Обобщение метода прогонки[править | править код]

А. А. Абрамовым в 1963 году предложен так называемый метод периодической прогонки, который позволяет решать СЛАУ с матрицей, в которой ненулевыми являются все угловые элементы , , , . Для решения СЛАУ на первом шаге рассчитываются коэффициенты прямой прогонки:

Далее выполняется обратная прогонка (справа налево) для получения коэффициентов

Далее вычисляют искомое значение вектора по формулам

Ссылки[править | править код]

Примечания[править | править код]

  1. «Метод прогонки … представляет собой вариант метода последовательного исключения неизвестных» (Самарский, Гулин, с. 45).
  2. «Прогонка, как устойчивый метод решения краевых задач с большим числом параметров, была введена и исследована И. М. Гельфандом и О. В. Локуциевским в 1952 г.» (Федоренко, с. 500).
  3. Березин, Жидков, с. 387, 506 (со ссылкой на неопубликованную рукопись Гельфанда и Локуциевского).
  4. В приложении к книге Годунова и Рябенького.
  5. «Прогонка была „открыта“ И. М. Гельфандом и О. В. Локуциевским в 1952 г. именно как применение алгоритма, изложенного в школьном учебнике алгебры. Их заслугой является установление устойчивости и использование алгоритма при решении сложных задач. Примерно в то же время в связи с аналогичными работами прогонка была предложена другими авторами» (Федоренко, с. 501).
  6. Тихонов А. Н., Самарский А. А. Уравнения математической физики. — гл. III, § 1. — Любое издание.