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

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

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

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

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

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

где

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

,

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

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

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

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

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

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

.

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

и

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

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

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

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

Пусть дано уравнение :

Обозначим этот оператор за L.

Можно добавить новую переменную t и добавить на неё уравнение.

Тогда

И разностная схема будет

где h, dt - шаги по сетке. решая её при больших конечных t мы получим решение начального уранения. Этот метод называется методом инвариантного погружения.

Ссылки[править | править вики-текст]

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

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