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

Компактная схема метода Гаусса для трёхдиагональной матрицы
Последовательный алгоритм
Последовательная сложность	[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.6 Последовательная сложность алгоритма

Для разложения трёхдиагональной матрицы порядка n компактной схемой метода Гаусса в последовательном варианте требуется:

• [math]n-1[/math] делений,
• [math]n-1[/math] умножений,
• [math]n-1[/math] сложений (вычитаний).

При классификации по последовательной сложности, таким образом, компактная схема метода Гаусса для разложения трёхдиагональной матрицы в последовательном варианте относится к алгоритмам с линейной сложностью.

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

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

2 Программная реализация алгоритмов

2.1 Особенности реализации последовательного алгоритма

В простейшем варианте алгоритм на Фортране можно записать так:

	DO  I = 1, N-1
		A(I+1,I) = A(I+1,I)/A(I,I)
                A(I+1,I+1) = A(I+1,I+1) - A(I+1,I)*A(I,I+1)
	END DO

Разложение размещается там же, где размещалась исходная матрица. Однако зачастую трёхдиагональную матрицу, естественно, хранят более экономно. Например, если диагонали нумеруются слева направо и каждая хранится в одной строке массива, то получается такая версия:

	DO  I = 1, N-1
		A(1,I) = A(1,I)/A(2,I)
                A(2,I+1) = A(2,I+1) - A(1,I)*A(3,I)
	END DO

в которой также разложение хранится на месте исходных данных.