Сетевое издание
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

АППАРАТУРНО-ОРИЕНТИРОВАННЫЙ АЛГОРИТМ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ С ВЕРХНЕЙ ТРЕУГОЛЬНОЙ МАТРИЦЕЙ

Бабенко В.Н. 1 Невечеря А.П. 2
1 Краснодарское Высшее Военное Авиационное Училище Лётчиков
2 ФГБОУ ВПО «Кубанский государственный университет»
Для системы линейных уравнений, решаемых в режиме реального времени, применяются систолические структуры. В этой статье предложен метод для решения систем линейных уравнений с верхней треугольной матрицей и систолическая структура для его реализации. В этом методе исходная матрица последовательно трансформируется матрицами локальных вращений и перестановок строк таким образом, что на j-ом шаге все элементы в j-ой строке обращаются в ноль, кроме диагонального элемента. Благодаря этому обеспечивается возможность вычисления j-ой компоненты решения делением j-ой компоненты вектора правой части на диагональный элемент. Соединив вход разработанной систолической структуры с выходом систолической структуры Джентльмена-Кунга, мы получим сквозной конвейер, который будет работать на единой частоте, равной величине обратной значению продолжительности такта. Продолжительность такта обусловлена продолжительностью выполнения машинной операции сложения.
решение систем линейных уравнений
треугольная матрица
локальные преобразования вращения
систолическая структура
процессор
конвейер
тактовая частота
1. Сверхбольшие схемы и современная обработка сигналов. Под ред. С. Гуна, Х. Уайтхауса, Т. Кайлата. – М., Радио и связь, 1989. – 345 с.
2. Бабенко В.Н. Способ вычисления решения систем линейных алгебраических уравнений с треугольной матрицей // Концептуальное проектирование в образовании, технике и технологии: сб. науч. тр. / Волгоградский гос. техн. ун-т. – Волгоград, 1997. – С. 6 – 8.
3. Бабенко В. Н. Способ повышения скорости сходимости процесса аннулирования одной компоненты двумерного вектора преобразованиями псевдовращения // Известия вузов. – Северо-Кавказский регион: Технические науки, 2009. – Спец. выпуск. – С. 33 – 39.
4. Бабенко В. Н. Представление инверсии делителя в мультипликативной форме и ее применение. // Известия вузов. – Северо-Кавказский регион: Технические науки, 2010. – № 6. – С. 33 – 37.
5. Бабенко В. Н. Алгоритм инверсии делителя. // Экологический вестник научных центров Черноморского экологического сотрудничества. – Краснодар: КубГУ, 2013. №4 .Т.1. – С. 19 – 25.
6. Бабенко В. Н. Накопление погрешностей при аппаратурной реализации алгоритма нормировки. // Экологический вестник научных центров Черноморского экологического сотрудничества. – Краснодар: КубГУ, 2014. № 2. – С. 5 – 12.
7. Бабенко В. Н. Точность аппаратурной реализации преобразования вращения вектора. // Экологический вестник научных центров Черноморского экологического сотрудничества. – Краснодар: КубГУ, 2014. № 3. – С. 5 – 14.
8. Пат. 2449354 RU, МПК G 06 F 17/16. Устройство нормировки вектора / Бабенко В. Н.
9. Пат. 2473961 RU, МПК G 06 F 17/16. Устройство нормировки вектора / Бабенко В. Н.
10. Пат. 2475830 RU, МПК G 06 F 17/16. Устройство вращения вектора / Бабенко В. Н.
11. Pat. 2475830 RU, IPC G 06 F 17/16. Ustroystvo vrascheniya vektora [The device rotation vector]. Babenko V.N.

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

В частности, для выполнения первого этапа решения систем линейных уравнений, разработана систолическая система (матрица) Джентльмена-Кунга, приводящая матрицу исходной системы к треугольному виду [1]. Для решения системы уравнений с верхней треугольной матрицей (второй этап) используется систолическая структура, реализующая обратный ход метода Гаусса [1]. Вычислительными элементами матрицы Джентльмена-Кунга являются, устройства Cordic, которые осуществляют преобразования вращения. Это обеспечивает вычислительному процессу наибольшую вычислительную устойчивость (преобразования вращения нечувствительны к ошибкам округления), чего нельзя сказать об обратном ходе метода Гаусса. Вычисления здесь ведутся по формуле

.

Выражение  следует читать так: i изменяется от  до 1 с шагом –1. Моделирование и анализ погрешностей обратного хода метода Гаусса для систем с двухдиагональной матрицей можно найти [4, стр. 27]. Вычисление суммы  представляет собой вычисление скалярного произведения i-ой строчки матрицы А на вектор х. Оценку точности вычисления скалярного произведения векторов с обычной точностью, можно найти в [5, стр. 249, (5.16)]

, где (Частичные суммы скалярного произведения продвигаются по систолической структуре, реализующей обратный ход метода Гаусса, от одного вычислительного элемента к другому с обычной точностью).

Погрешности, характеризуемые произведением , относят к эквивалентному возмущению матрицы системы А. Из последних соотношений видно (см. на число (i – 1)), что вычисления обратного хода метода Гаусса обусловлены хуже, чем исходная задача. Следует отметить, что если скалярное произведение вычислять с расширенной точностью, то обратный ход метода Гаусса приобретает устойчивость, в этом случае , [5, стр. 249, (5.16)].

Со своей стороны математики-вычислители стараются разработать новые аппаратурно-ориентированные алгоритмы, отвечающие указанным выше требованиям.

Ниже предлагается метод решения систем линейных уравнений с верхней треугольной матрицей, в котором используются так называемые локальные матрицы вращения (изменяющие только смежные компоненты вектора):

а также локальные матрицы перестановки строк

Последние описывают продвижение обрабатываемых данных по вычислительной структуре (систолической матрице).

Описание метода ортогонального обратного хода

Пусть матрица А системы уравнений  имеет треугольный вид. Составим расширенную систему , введем обозначение  и перейдем к изложению алгоритма.

Предварительный (нулевой) шаг. Вычислим по формуле .

Шаг 1. Подберем пару чисел  такую, чтобы (N – 1)-я компонента N-ого столбца матрицы обратилась ноль. Здесь  – локальное преобразование вращения, определенное парой . При этом матрица примет вид

Употребляемые здесь знаки имеют следующие значения: 0 – обязательно нулевой элемент,  – обязательно ненулевой элемент, # – элемент, значение которого мы не оговариваем. Произведем перестановку N-ой и (N – 1)-ой строк матрицы : , в результате получим

.

Вычислим по формуле .

Шаг 2. Подберем пару чисел  такую, чтобы (N – 2)-я компонента N-ого столбца матрицы  приняла нулевое значение, при этом матрица примет вид.

Произведем перестановку (N – 1)-ой и (N – 2)-ой строк матрицы : , в результате получим

.

Шаг 3. Определим пары чисел   так, чтобы (N – 1)-я компонента (N – 1)-ого столбца и (N – 3)-я компонента N-ого столбца матрицы  приняли нулевое значение, при этом матрица  примет вид

.

Поменяем местами строки N-ю с (N – 1)-ой и (N – 2)-ю с (N – 3)-ой: , в результате получим

Затем вычислим .

Шаг 4. Определим пары чисел   так, чтобы (N – 2)-я компонента (N – 1)-ого столбца и (N – 4)-я компонента N-ого столбца матрицы  приняли нулевое значение, при этом матрица примет вид

.

Поменяем местами строки: (N – 1)-ю с (N – 2)-ой и (N – 3)-я с (N – 4)-я: , в результате получим матрицу

.

Шаг i (i = 5, N – 1). Подберем пары чисел  где , такие, чтобы элементы  матрицы  приняли нулевое значение (здесь  – целая часть частного от деления (i + 1) на 2), при этом матрица , если i нечетно, примет вид

Осуществим перестановку строк: , в результате получим матрицу

 Отсюда видно, что .

Если i четно, то матрица  примет вид

 

Осуществим перестановку строк: , в результате получим матрицу

 

Шаг i (i = N, 2(N – 1) – 1). Подберем пары чисел  где ,,, такие, чтобы элементы  матрицы  приняли нулевое значение (здесь  – целая часть частного от деления (i+1) на 2), при этом матрица , если i нечетно, примет вид

Осуществим перестановку строк:  в результате получим матрицу

Отсюда видно, что .

Если i четно, то матрица  примет вид

Осуществим перестановку строк: , в результате получим матрицу

Замечание 1. Применение формулы  основано на том факте, что при нечетном i в N-ой строке все элементы расширенной матрицы за исключением  и, возможно,  равны нулю (матрица А невырождена).

Замечание 2. Более наглядный и простой вывод формул без указания перестановок строк дан в [2].

Перейдем к упрощенному описанию систолической структуры, реализующей предложенный метод, и вычислительных элементов (ВЭ), входящих в ее состав. Эта структура состоит из ВЭ трех типов.

Первый ВЭ. Он имеет один вход, два выхода и внутренний регистр (ВР) для хранения вычисленного результата (обозначение ). Будем предполагать, что на регистре имеется вычисленный результат – у, а на его вход поступает число х (х,у – компоненты двумерного вектора , тогда функционирование ВЭ можно описать следующим образом: на первый и второй выходы поступают c и s, на ВР – у, где с,s и у определяются соотношениями , , .

Второй ВЭ. Он имеет три входа, один выход и внутренний регистр (ВР) для хранения вычисленного результата (обозначение ). Будем предполагать, что на регистре имеется вычисленный результат – v, а на его первый вход поступает число u, на второй и третий – с и s (u,v – компоненты двумерного вектора , тогда функционирование ВЭ можно описать следующим образом: на выход поступает u на ВР – v, где u и v определяются соотношениями , .

Третий ВЭ. Он имеет два входа и один выход (обозначение ). На входы ВР поступают два числа: у и а, соответственно. На выход .

Более подробное описание работы представленных ВЭ можно найти в [3–10].

Ниже на рис. 1 представлена систолическая структура, реализующая, описанный выше метод.

Рис. 1. Систолическая структура ортогонального обратного хода

Обсуждение результатов

После выполнения первого этапа система уравнений с верхней треугольной матрицей поступает на систолическую структуру, реализующую процедуру обратного хода (число обусловленности матрицы не вычисляется). Такой подход к решению системы уравнений может быть принятым, если априори известно, что решаемая система принадлежит классу невырожденных задач, а ее обусловленность позволяет получить приемлемое по точности решение.

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

Очевидно, если выход систолической системы Джентльмена-Кунга [1] соединить с входом представленной систолической структуры, то мы получим сквозной единый конвейер, работающий на частоте , где  – продолжительность операции сложения на сумматоре.

Рецензенты:

Лебедев К.А., д.ф.-м.н., профессор кафедры вычислительной математики и информатики ФГБОУ ВПО «Кубанский государственный университет», г. Краснодар;

Уртенов М.А.Х., д.ф.-м.н., профессор, заведующий кафедрой прикладной математики ФГБОУ ВПО «Кубанский государственный университет», г. Краснодар.


Библиографическая ссылка

Бабенко В.Н., Невечеря А.П. АППАРАТУРНО-ОРИЕНТИРОВАННЫЙ АЛГОРИТМ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ С ВЕРХНЕЙ ТРЕУГОЛЬНОЙ МАТРИЦЕЙ // Современные проблемы науки и образования. – 2014. – № 6. ;
URL: https://science-education.ru/ru/article/view?id=16966 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674