Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант

Компактная схема метода Гаусса для трёхдиагональной матрицы
Последовательный алгоритм
Последовательная сложность	[math]3n-3[/math]
Объём входных данных	[math]3n-2[/math]
Объём выходных данных	[math]3n-2[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]3n-3[/math]
Ширина ярусно-параллельной формы	[math]1[/math]

Основные авторы описания: А.В.Фролов

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Компактная схема метода Гаусса для трёхдиагональной матрицы вычисляет такое [math]LU[/math]-разложение трёхдиагональной матрицы [math]A[/math] на две двухдиагональные, в котором у нижней двухдиагональной матрицы [math]L[/math] на главной диагонали стоят только единицы. При такой фиксации все элементы разложения становятся строго предопределёнными, с точностью до ошибок округления. Компактная схема даёт естественные формулы нахождения остальных элементов получающихся двухдиагональных матриц. Случай для разложения трёхдиагональной матрицы является частным для компактной схемы метода Гаусса общего вида, однако из-за специфики матрицы характеристики алгоритма кардинально меняются по сравнению с компактной схемой для плотных матриц.

1.2 Математическое описание

Формулы метода следующие:

[math] u_{11} = a_{11} \\ u_{i i+1} = a_{i i+1}, \quad i \in [1, n-1] \\ l_{i+1 i} = a_{i+1 i} / u_{i i} , \quad i \in [1, n-1] \\ u_{ii} = a_{ii} - l_{i i-1} u_{i-1 i}, \quad i \in [2, n] \\ [/math]