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

М

8.8

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

О

8.9

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

И

8.10

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

Г

8.11

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

О

8.12

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

И

8.13

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

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

8.14

Д

8.15

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

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

8.16

и

8.17

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

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

Разложение Халецкого

Разложение Хaлецкого — представление симметричной положительно-определённой матрицы A в виде A = LL^T, где L — нижняя треугольная матрица со строго положительными элементами на диагонали. Иногда разложение записывается в эквивалентной форме: A = U^TU, где U = L^T — верхняя треугольная матрица. Разложение Халецкого всегда существует и единственно для любой симметричной положительно-определённой матрицы.

Существует также обобщение этого разложения на случай комплекснозначных матриц. Если A — положительно-определённая эрмитова матрица, то существует разложение , где L — нижняя треугольная матрица с положительными действительными элементами на диагонали, а — эрмитово-сопряжённая к ней матрица.

Алгоритм

Э

8.18

лементы матрицы L можно вычислить, начиная с верхнего левого угла матрицы, по формулам:

Выражение под корнем всегда положительно, если A — действительная положительно-определённая матрица.

Д

8.19

ля комплекснозначных эрмитовых матриц используются формулы:

Приложения

Это разложение может применяться для решения системы линейных уравнений Ax = b, если матрица A симметрична и положительно-определена. Такие матрицы часто возникают, например, при использовании метода наименьших квадратов и численном решении дифференциальных уравнений.

Выполнив разложение A = LL^T, решение x получается последовательным решением двух треугольных систем уравнений: Ly = b и L^Tx = y. Такой способ решения иногда называется методом квадратных корней. По сравнению с более общими методами, такими как метод Гаусса или LU-разложение, он устойчивее численно и требует примерно вдвое меньше арифметических операций.

Разложение Холецкого также применяется в методах Монте-Карло для генерации коррелированных случайных величин. Пусть X — вектор из независимых стандартных нормальных случайных величин, а Σ = LL^T — желаемая ковариационная матрица. Тогда вектор Y = LX будет иметь многомерное нормальное распределение с нулевым математическим ожиданием и ковариационной матрицей Σ.

Контрольные вопросы:

1. Что такое система линейных алгебраических уравнений?

2. Что такое метод Гаусса?

3. Для чего используется метод прогонки?