Устройство для решения системы ли-нейных алгебраических уравнений

 

О П И С А Н И Е (»)3ll276

ИЗОБРЕТЕН ИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свпд-ву (22) Заявлено 22.09.78 (21) 2665973/18-24 с присоединением заявки № (23) Приоритет (43) Опубликовано 07.03.81. Бюллетень № 9 (45) Дата опубликования описания 07.03.81 (51) М. Кл.з

G 06F 15/324

Государственный комитет

СССР по делам изобретений и открытий (53) УДК 681.14 (088.8) 1 " "« " ЙЬЪйАт (72) Авторы изобретения

)

Л: г т."."6

«, 1" тетмР 1ж! э

Б. И. Хвоин и Н. Д. Челышев (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ

АЛ ГЕБРАИ Ч ЕСК ИХ УРАВ Н Е Н И Й

Изобретение относится к автоматике и вычислительной технике и может найти применение как автономное устройство для решения системы линейных уравнений или в комплексе ЭВМ. 5

Известно устройство для решения системы линейных алгебраических уравнений, содержащее mXn блоков формирования коэффициентов, сумматоры, регистры, цифровые интеграторы, блоки умножения (1). 10

Недостатком известного устройства является значительная сложность структуры.

Наиболее близким по технической сущности к изобретению является устройство, содержащее регистры, и сумматоры прира- 15 щений, блоки памяти коэффициентов, блоки умножения, первые входы которых соединены с выходами блоков приращений, а вторыс — с выходом блока памяти коэффициентов, сумматор, группа входов которого соединена с выходами блоков умножения, блок памяти невязок, коммутатор (2).

Недостаток известного устройства состоит в сложности структуры и быстром росте оборудования при увеличении порядка системы. Это обуславливается тем, что с ростом числа уравнений и неизвестных необходимо увеличить количество сумматоров приращений и блоков умножения для подсчета невязок, так как время вычисления, 30 расходуемое, главным образом, на умножение, растет пропорционально квадрату числа неизвестны:.

Цель изобретения — упрощение устройства и повышение быстродействия, Достигается это тем, что устройство для решения системы линейных уравнений, содержащее блок памяти коэффициентов, олок памяти неизвестных, сумматор, сумматор приращений, блок умножения, первый и второй входы которого соединены соответственно с первымп выходамп блока памяти коэффициентов и блока памяти неизвестны.:, блок управления, первый и второй выходы которого соединены соответственно с входом блока памяти коэффициентов и первым входом блока памяти неизвестных, содержит блок памяти взвешенных координатных приращений, элемент

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

811276

b, b> х>

40 где А= {а2,), Х==.

В= бп хп

EJ =1, ...и

45 является точка пересечения (n — 1) -мерных гиперплоскостей (1) в и-мерном свклидовом пространстве. Для нахождения рсшешгя системы был использован модифицированный метод Гаусса-Зейделя.

5Р

Классический метод Гаусса-Зейдсля состоит в преобразовании системы (2) к виду

Х= АХ+В (3! и решений системы (3) методом последо- 55 вательных итераций

Х =АК - +В, j2= 1,2...и, (4) начиная с некоторого начального прпбли(>(! жения X(I. Основное отличие модифицированного метода Гаусса-Зсйделя более понятно в геометрической интерпретации.

Для подсчета Х; не использовалась явная форма (4) вычисления Х" через остальные (>5 подключены соответственно к вторым входам элемента ИЛИ и блока памяти взвешенных покоординатных приращений, первый, второй и третий выходы которого подключены соответственно к первому входу сумматора прираще2гий и к третьим входам элемента ИЛИ и блока памяти знака, выход которого соединен с управляющими входами сумматора и сумматора приращений, второй вход которого соединен с пер- !(! вым выходом блока памяти неизвестных, второй вход которого соединен с выходом сумматора приращений.

На фиг. 1 представлена блок-схема устройства; на фиг, 2 — схема блока памяти коэффициентов; на фиг. 3 — схема блоков памяти неизвестных и взвешенных покоординатных приращений.

Устройство включает блок управления 1, блок памяти коэффициентов 2, блок памяти неизвестных 3, блок умножения 4, блок

5 памяти взвешенных покоординатных приращений, сумматор приращений б, элемент

ИЛИ 7, сумматор 8, блок 9 памяти знака, выходы устройства 10. Блок памяти коэффициентов содержит первую группу регистров 11, вторую группу регистров 12, п-ю группу регистров 13. Блоки памяти неизвестных и памяти взвешенных покоординапных прира(цений содержат группу регистров 14.

Устройство реализует следующий алгоритм вычисления корней системы.

Решением системы линейных уравнений и 35

; а,,х,.— bl — 0, i=1, ..., n (1)

j=l или в матричной форме АХ— = B, х, персмс(шые. Вместо этого использовалось то свойство и-мерного евклидова пространства, что каждая (n — 1) -мерная гиперплоскость (1) делит его на два пространства.

Гсли теперь в левую часть ypalI»(.HHH гпперплоскости подс авпть координаты т(!яки, лежащей в одном из полупространств, то значение этого выражения будет положительное, а для точки,из другого полупространства — отрицательное.

Ллгоритм точки пересечения гипсрплоскости (1) (корней системы) состоит в следующем.

Ш аг 1. Вычислить знак левой части очередного i-ro уравнения из (1) в достигнутой к данному моменту точке. В начале работы алгоритма на этом шаге вычисляется знак левой части первого уравнения системы в началы(ой точке Y(I. Псрсйтп к шагу 2.

Ш а г 2. С учетом результата шага 1 и знака а;, начинается последовательное изменение х; на величину h с тем, чтобы пересечь (,-ую гиперплоскость, т. е. изменить знак левой части 2-го уравнения. Когда после очередного изменения х, это произойдет, то вернемся к предыдущему значению х; и можем утверждать, что х; отличается от точного значения, вычисленного по формуле (4), меньше, чем h. В целях уменьшения объема вычислений II(. подсчитывается каждый раз значение выражения всей левой части 2-го ypaalleIIIIH, а заранее подсчитыгастся взвешенное приращение а(222; этого в(>2ра>кснпя при пзмсне,(ии х; на величину h. Зто позволило сократить число умножcHHé до 22(н2имума и ускорить подсчет решения. Далее перейти к шагу 3, Ш а г 3. Если по всем координатам происходит изменение знака левой части уравнений гиперплоскостей после первого llpHращения х;, i=1, 2 ... п, то перейти к шагу

5, если не происходит — то к шагу 4.

Ш а г 4. Выбрать следующее (i+1) -ое уравнение из (1) и следующую (i+ 1) -ую координату х;+,. Если (2+1) превысило /2> то следующий номер уравнения и координаты равен 1. Перейти к шагу 1.

Ш аг 5. Изменить всличину приращеш(я координат Й на "/g и величины взвешенных покоординатных приращений а,;h по а((п, q.

Если число изменений h,меньше заданного числа т, то перейти к шагу 1, иначе закончить решение задачи.

Устройство работает следующим образом.

В исходном состоянии сумматор 8 обнулен, в блоке памяти 2 хранятся коэффициенты

cHcT(. III, прп I(. 1 в первой группе регистров !

1 (см. фиг. 2) размещEI!I>I коэффициенты

1-го уравнения, во второй группе 12 коэффициенты второго уравнения и т, д, до и. В первом регистре 2-ой группы хранится коэффициент при первом неизвестном, во втором — прп втором н т. д. Неизвестные х; хранятся в блоке памяти 3 и

811276

6 размещаются в регистрах, начиная с первого порядка, соответствующем их номеру.

Начальное значение всех х; равно h.

Работа устройства по выполнению шага

1 алгоритма решения системы линейных уравнений начинается с передачи 1-го коэ<рфициента и tiepBQH координаты в блок умножения 4, результат умножения через элемент ИЛИ / поступает на сумматор 8 и складывается с его содержанием. l!роизведение ачйь являющееся взвешенным координатным приращением левой части уравнения (1), записывается в блок памяти о. Затем производится сдвиг информации по регистрам в первой группе блока 8 и блоке 3 и процесс повторястся. Запись результата умножения в олок памяти 5 отсутствует. После и сдвигов, у множсний и сложений в сумматор добавляется своооднып член Ь, из блока памяти 2 через элемент ИЛИ. Знак результата сумматора, являющийся знаком левой части уравнения (1), запоминается в блоке 9.

Далее начинается выполнение шага 2.

Для этого взвешенное приращение левой части уравнения (1) из олока памяти 5 поступает на сумматор, а прпращеш;е координат Й из блока памяти о поступает на сумматор приращений. Знак операции, производимой в сумматорах, определяется в олоке 9 с учсточ знаков рсзул;,тата шага

1 и знака агь Если i осле доогвленпя взвешенного приращения знак левой части уравнения пе изменился, то к текущеп координате, поступающей на сучматор приращений с первого регистра блока памяти

3, добавляется приращение h, поступающее из блока памяти 5, результат сучмирования записывается в тот же регистр олока

3. Если знак левой части уравнения (! ) изменился, приращение h не добавляется.

Влок 9 проверяет условие, записанное в шаге 3 алгоритма решения системы уравнений. Если условие не выполняется, то переходим к выполнению шага 4. Оно включает: обнуление сумматора 8 и знака левой части уравнения (1) в блоке 9, перепи ь коэффициентов из гру шы с номером i в i — 1, а из первой группы в n-io, один сдвиг информации по регистрам в блоках памяти неизвестных 3 и памяти взвешенных покоординатных приращений 5, переходим к выполнению шага 1. Есл..i условие шага 3 выполняется, то переходим к шагу 5, при котором происходит умеш— шение прира цений h и а;,.h в блоке памяти

5 путем поразрядного с tat!i a содержпмо o регистров на один ра"ряд вправо. Вся ра5

50 бота спнхронизпруется сигналами блока управления 1 и заканчивается, если число изменений lг больше заданного.

Введение новых блоков и новых конструктивных связей позволило уменьшить количество операций умножения, а следовательно, повысить быстродействие устройства. количество блоков умножения не увеличивается с ростом неизвестных в системе мравнений 1 ормула изобретения

Устройство для решения системы линейных алгебраических уравнений, содержащее блок памяти коэффициентов, блок памяти неизвестных, сумматор, сумматор приращений, блок умножения, первый и второй входы которого соединены соответственно с первыми входами олока памяти коэффициентов и блока памяти нспзвесDHbtx, блокуправленпя, первый и второй выходы которого соединены соответственно с входом блока памяти коэффициентов и первым входом блока памяти неизвестных, о тл и ч а ющее с я тем, что, с целью упрощения устройства и. повышения быстродействия, оно содержппт блок памяти взвешенных коорди натных приращений, элемент ИЛИ и блок taaмяти знака, причем второй выход блока памяти коэффициентов соединен с первым входом элемента ИЛ11, выход которого соедине с входом сумматора, выход которого соединен с первым входом блока памяти знака, второй вход которого соединен с третьим выходом блока управления, четвертый выход которого подклю чен к первому входу олока памяти взвешенных координатных приращений, первый и второй выходы блока умножения подключены соответственно к вторым входам элемента ИЛИ и блока памяти взвешенных покоордипатных приращений, первый, второй и третий выходы которого подключены соответственно к первому входу сумматора приращений и к третьим входам элемента ИЛИ и блока памяти знака, выход которого соединен с управляю цпмп входамп сумматора и сумматора приращений, второй вход которого со дннен с первым выходом блока памяти неизвестных, второй вход которого соединен с выходом сум атора приращений.

Источники информации, принятые во внимание прп экспертизе

1. Лвторское свидетельство СССР

¹ 559241, кл. G 06F 15/32, 1976.

2..5,вторс кое свидетельство СССР

ЛЪ 56! 638 кл. G 061 15/32, 1977 (прототипп) 811276

Фиг. 2

Составитель Н. Палеева

Тсхред Т. Трушкина

Редактор F.. Гончар

Корректоры: Н. Федорова и А. Степанова

Типография, пр, Сапунова, 2

Заказ 742j1 Изд. № 317 Тираж 749 Подписное

H1lO «Поиск» Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ol(-35, Раушская наб.. д. 4/5