Interested Article - Метод прогонки

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

Описание метода

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

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

где

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

,

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

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

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

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

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

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

.

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

и

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

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

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

Пример использования

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

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

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

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

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

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

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

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

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

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

Ссылки

Примечания

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

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