Открыть главное меню

Метод прогонки (англ. 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).