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

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

1.3 Вычислительное ядро алгоритма

Как видно из формул, n-1 раз повторяется одна и та же последовательность трёх операций: деление, умножение, вычитание.

1.4 Макроструктура алгоритма

В качестве макровершины можно взять последовательность трёх операций: деление, умножение, вычитание. Эти макровершины выполняются в алгоритме n-1 раз.

1.5 Описание схемы реализации последовательного алгоритма

В схеме учтено, что ряд выходных данных вычислять не нужно - они совпадают с входными. В частности,

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

В начале процесса [math]i = 1[/math]

1. Вычисляется [math]l_{i+1 i} = a_{i+1 i} / u_{i i}[/math]

[math]i[/math] увеличивается на 1

2. Вычисляется [math]u_{ii} = a_{ii} - l_{i i-1} u_{i-1 i}[/math]

Если [math]i = n[/math], то конец, иначе возврат к п.1.

1.7 Информационный граф

Граф алгоритма без отображения входных и выходных данных. / - деление, * - умножение, - - вычитание.