Высокопроизводительные вычисления на кластерах. Беликов Д.А - 105 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

105
6.3 Метод циклической редукции
Рассмотрим систему линейных алгебраических уравнений с
трехдиагональной матрицей следующего вида:
1 1 1 2 1
2 1 2 2 2 3 2
3 2 3 3 3 4 3
1
,
,
,
........................................
........
.
n n n n n
b x c x f
a x b x c x f
a x b x c x f
a x b x f
(6.2)
Системы вида (6.2) образуют очень важный класс линейных ал-
гебраических уравнений. Они часто получаются в результате разно-
стных аппроксимаций дифференциальных краевых задач, а также
при построении кубических сплайнов. Экономичными прямыми
методами решения таких систем на компьютерах с последователь-
ной архитектурой являются специальные варианты метода исклю-
чения Гаусса – метод прогонки и метод циклической редукции.
Идея метода циклической редукции заключается в последова-
тельном исключении из уравнений неизвестных
i
x
сначала с нечет-
ными индексами, а затем с индексами, кратными 2, но не кратными
4, и т.д. Каждый шаг процесса исключения в два раза уменьшает
число неизвестных и уравнений, включающих эти неизвестные. На
последнем шаге остается одно уравнение, из которого можно найти
2
n
. Обратный ход метода состоит в последовательном нахождении
неизвестных
i
x
сначала с номерами i, кратными
/ 4
n
, затем
n
,
/16
n
и т.д.
Рассмотрим систему линейных алгебраических уравнений (6.2),
примем
1 , 2 , 0
q
n n n q
– натуральное число. Выпишем
тройки уравнений системы для
2,4,..., 2
i n
:
1 2 1 1 1 1
1 1
1 1 1 1 2 1
,
,
.
i i i i i i i
i i i i i i i
i i i i i i i
a x b x c x f
a x b x c x f
a x b x c x f
(6.3)
Если установить
0
0
n
x x
, то получим систему уравнений, эк-
вивалентную (6.2), в которую включены дополнительные уравнения
с коэффициентами
0 , 1 , 0
i i i i
a c b f
для
0
i
и
i n
.

Страницы