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

О П И С А Н И Е (и)ВИ 276ИЗОБРЕТЕН ИЯ Союз Советских Социалистических) 2665973/18 з06 Г 15/32 с присоединением аявки М Государственный комитет ссср по делам изобретений и открытий(53) У 3,81. Бюллетень Мя описания 07.03.8 1,14 88,8 Авторыизобретен Ф 2 ййА т.". Челыше Б. И, Хвои 1 Заявител 4) УСТРОЙ ВО ДЛЯ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХГЕБРАИЧЕСКИХ УРАВНЕНИЙ Изобретение относится к автоматике и вычислительной технике и может найти применение как автономное устройство для решения системы линейных уравнений или в комплексе ЭВМ. 5Известно устройство для решения системы линейных алгебраических уравнений, содержащее тХп блоков формирования коэффициентов, сумматоры, регистры, цифровые интеграторы, блоки умножения 11. 1 ОНедостатком известного устройства является значительная сложность структуры.Наиболее близким по технической сущности к изобретению является устройство, содержащее регистры, и сумматоры прира щений, блоки памяти коэффициентов, блоки умножения, первые входы которых соединены с выходами блоков приращений, а вторыс - с выходом блока памяти коэффициентов, сумматор, группа входов которого соединена с выходами блоков умножения, блок памяти иевязок, коммутатор 2.Недостаток известного устройства состоит в сложности структуры и быстром росте оборудования при увеличении порядка системы. Это обуславливается тем, что с ростом числа уравнений и неизвестных необходимо увеличить количество сумматоров приращений и блоков умножения для подсчета невязок, так как время вычисления, 30 расходуемое, главным ооразом, на жение, растет пропорционально квадр у числа неизвестных.Цель изобретения - упрощение устройства и повышение быстродействия,Достигается это тем, что устройство для решения системы линейных уравнений, содержащее блок памяти коэффициентов, олок памяти неизвестных, сумматор, сумматор приращении, блок умножения, первый и второи входы которого соединены соответственно с первыми выходами блока памяти коэффициентов и блока памяти неизвестных, блок управления, первый и второй выходы которого соединены соответственно с входом блока памяти коэффициентов и первым входом блока памяти неизвестных, содержит блок памяти взвешенных координатньх приращений, элемент ИЛИ и блок памяти знака, причем второй выход блока памяти коэффициентов соединен с первым входом элемента ИЛИ, выход которого соединен с входом сумматора, выход которого соединен с первым входом блока памяти знака, второй вход которого соединен с третьим выходом блока управления, четвертый выход которого подключен к первому входу блока памяти взвешенных покоординатиых приращений, первый и второй выходы блока умноженияподключены соответственно к вторым входам элемента ИЛИ и блока памяти взвешенных покоординатных приращений, первый, второй и третий выходы которогоподключены соответственно к первому входу сумматора приращеггий и к третьим входам элемента ИЛИ и блока памяти знака,выход которого соединен с управляющимивходами сумматора и сумматора приращений, второй вход которого соединен с пер- )Овым выходом блока памяти неизвестных,второй вход которого соединен с выходомсумматора приращений.На фиг, 1 представлена блок-схема устройства; на фиг, 2 - схема блока памяти 5коэффициентов; на фиг. 3 - схема блоковпамяти неизвестных и взвешенных покоординатных приращений.Устройство включает блок управления 1,блок памяти коэффициентов 2, блок памяти неизвестных 3, блок умножения 4, блок5 памяти взвешенных покоординатных приращений, сумматор приращений б, элементИЛИ 7, сумматор 8, блок 9 памяти знака,выходы устройства 10. Блок памяти коэффициентов содержит первую группу регистров 11, вторую группу регистров 12,и-ю группу регистров 13, Блоки памяти неизвестных и памяти взвешенных покоординапных прирагцений содержат группу регистров 14,Устройство реализует следующий алгоритм вычисления корней системы,Решением системы линейных уравненийи 35а, х,. - Ьг=О, г=1, , и (1)=1или в матричной форме АХ=В,х,40 где А= (аг Х:=. В= б хгюу=1, и45 является точка пересечения (и - 1) -мерных гиперплоскостей (1) в и-мерном свклидовом пространстве. Для нахождения рсшешгя системы был использован модифицированный метод Гаусса-Зейделя.50Классический метод Гаусса-Зейдсля состоит в преобразовании системы (2) к видуХ= АХ+В (3) и решений системы (3) методом цоследо вательцых итераций Х = АК- г + В, А =. 1,2 иг, (4) начиная с некоторого начального прцбли 00 жения Хо. Основное отличие модифицированного метода Гаусса-Зсйделя более понятно в геометрической интерпретации. Для подсчета Х; не использовалась явная форма (4) вычисления Х" через остальные 05 церсмсгшые. Вместо этого использовалось то свойство и-мерного евклидова пространства, что каждая (и - 1) -мерная гиперплоскость (1) делит его на два пространства, Гсли теперь в левую часть уравнения гццерплоскости подставить координаты точки, лежащей в одном из цолупрострацств, то значение этого выражения будет положительное, а для точки,из другого полу- пространства - отрицательное.Ллгоритм точки пересечения гипсрплоскости (1) (корней системы) состоит в следующем.Шаг 1. Вычислить знак левой части очередного г-го уравнения изв достигнутой к данному моменту точке. В начале работы алгоритма ца этом шаге вычисляется знак левой части первого уравнения сцстемы в начальной точке хгг. Псрсйтц к шагу 2.Ш аг 2, С учетом результата шагаи знака а;, начинается последовательное изменение х; на величину Й с тем, чтобы пересечь г-ую гиперплоскость, т, е, изменить знак левой части г-го уравнения, Когда после очередного изменения х, это произойдет, то вернемся к предыдущему значению х; и можем утверждать, что х; отличается от точного значения, вычисленного цо формуле (4), мсцьше, чем Й. В целях уменьшения объема вычислений цс подсчитывается каждый раз значение выражения всей левой части г-го уравнения, а заранее подсчитывается взвешенное приращение аЙ; этого выражения при цзмсцении х; ца величину Й. Зто позволило сократить число умножений до минимума и ускорить подсчет решения. Далее перейти к шагу 3,Ш а г 3. Если по всем координатам происходит изменение знака левой части уравнений гиперплоскостей после первого приращения х;, г=1, 2и, то перейти к шагу 5, если це происходит - то к шагу 4.Ш а г 4. Выбрать следующее (г+1) -ое уравнение из (1) и следующую (г+1)-ую координату хгьг. Если (г+1) превысило Й, то следующий номер уравнсшгя и координаты равен 1. Перейти к шагу .Ш а г 5. Изменить всличину приращешгя координат Й на "/ и величины взвешенных покоординатных приращений а,;Й по а",. Если число изменений Й меньше заданного числа т, то перейти к шагу 1, иначе закончить решение задачи.Устройство работает следующим образом. В исходном состоянии сумматор 8 обнулен, в блоке памяти 2 хранятся коэффициенты системы, причем в первой группе регистров 1 (см. фиг, 2) размегггегы коэффициенты 1-го уравнения, во второй группе 12 коэффицисггты Второго уравнегия и т, д, до и. В первом регистре г-ой группы храццтся коэффициент цри первом неизвестном, во втором - прц втором н т. д. Неизвестные х; хранятся в блоке памяти 3 иразмещаются в регистрах, начиная с первого порядка, соответствующем их номеру. Начальное значение всех х; равно Й.Работа устройства по выполнению шага 1 алгоритма решения системы линейных уравнений начинается с передачи 1-го коэрфициента и первой координаты в блок умножения 4, результат умножения через элемент ИЛИ / поступает на сумматор 8 и складывается с его содержанием. 11 роизведение адЙь являющееся взвешенным координатным приращением левой части уравнения (1), записывается в блок памяти о. Затем производится сдвиг информации по регистрам в первой группе Олока 8 и блоке 3 и процесс повторяется. Запись результата умножения в олок памяти 5 отсутствует. После и сдвигов, умножений и сложений в сумматор дооав,1 яется своооднып член Ь, из блока памяти 2 через элемент ИЛИ. Знак результата сумматора, являющийся знаком левой части уравнения (1), запоминается в блоке 9,Далее начинается выполнение шага 2, Для этого взвешенное приращение левой части уравнения (1) из олока памяти 5 поступает на сумматор, а прпращеш;е координат Й из блока памяти о поступает на сумматор приращешй. Знак операции, производимой в сумматорах, определяется в олоке 9 с учетом знаков результата шага 1 и знака а. Если после доогвления взвешенного приращешгя знак левой части уравнения пе изменился, то к текущеп координате, поступающей на сумматор приращений с первого регистра блока памяти 3, добавляется приращение Й, поступающее из блока памяти 5, результат суммирования записывается в тот же регистр олока 3, Если знак левой части уравнения (1) изменился, приращение Й не добавляется. Влок 9 проверяет условие, записанное в шаге 3 алгоритма решения системы уравнений. Если условие не выполняется, то переходим к выполнению шага 4. Оно включает: обнуление сумматора 8 и знака левой части уравнения (1) в блоке 9, перепис ь коэффициентов из гру шы с номером с в с - 1, а из первой группы в п-ю, один сдвиг информации по регистрам в блоках памяти неизвестных 3 и памяти взвешенных покоординатных приращений 5, переходим к выполнению шага 1. Если условие шага 3 выполняется, то переходим к шагу 5, при котором происходит уменьшение прирагцений Й и а;Й в блоке памяти 5 путем поразрядного сдв 1 гга содержимого регистров на один разряд вправо. Вся ра 5 1 О 15 20 30 05 40 45 50 бота спнхронизпруется сигналами блока управления 1 и заканчивается, если число изменений Й больше заданного.Введение новых блоков и новых конструктивных связей позволило уменьшить количество операций умножения, а следовательно, повысить быстродействие устройства. Количество блоков умножения не увеличивается с ростом неизвестных в системеравнений Формула изобретенияУстройство для решения системы линейных алгебраических уравнений, содержащее блок памяти коэффициентов, блок памяти неизвестных, сумматор, сумматор приращений, блок умножения, первый и второй входы которого соединены соответственно с первыми входами олока памяти коэффициентов и блока памяти неизвестных, блокуправленпя, первый и второй выходы которого соединены соответственно с входом блока памяти коэффициентов и первым входом блока памяти неизвестных, о тл и ч а ющее с я тем, что, с целью упрощения устройства и повышения быстродействия, оно содержппг блок памяти взвешенных координатпых приращений, элемент ИЛИ и блок памяти знака, причем второй выход блока памяти коэффициентов соединен с первым входом элемента ИЛИ, выход которого соединен с входом сумматора, выход которого соединен с первым входом блока памяти знака, второй вход которого соединен с третьим ияходом блока управления, четвертый выход которого подключен к первому входу олока памяти взвешенных координатных приращений, первый и второй выходы блока умножения подключены соответственно к вторым входам элемента ИЛИ и блока памяти взвешенных покоордипатных приращений, первый, второй и третий выходы которого подключены соответственно к первому входу сумматора приращений и к третьим входам элемента ИЛИ и блока памяти знака, выход которого соединен с управляю.цпмп входамп сумматора и сумматора прпращеппй, второй вход которого со дннен с первым выходом блока памяти неизвестных, второй вход которого соединен с выходом сум атора приращений.Источники информации,принятые во внимание при экспертизе 1. Лвторское свидетельство СССР М 559241, кл, 6 06 Г 15/32, 1976.2,вторское свидетельство СССР Ло 56 638, кл. 6 06 Г 15/32, 1977 (протот 11 п) .811276 Составитель Н. Палеева Тсхред Т, Трушкина Редактор Г. Гончар Корректоры: Н. федороваи А, Степанова Типография, пр, Сапунова, 2 Заказ 742/1 Изд.317 Тираж 749 ПодписноеН 1 зО Поиск Государственного комитета СССР по делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5