Устройство для решения систем линйныхалгебраических уравнений
.ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
Союз Советских
Социалистических
Республик
К АВТОРСКОМУ СВ ЕТВЛЬСТВУ (63) Дополнительное к авт. свид-ву (22) Заявлено 161178 (21) 2684069/18-24 (51)М. КЛ З
G: 06 F 15/324 с присоединением заявки Ио .\
Государственный комитет
СССР по делам изобретений и открытий (23) Приоритет )лубликовано 2,304.81.Бюллетень ЙЯ 15 (5$) УД3(6 81.325..5 (088 . 8) Дата опубликования описания 23. 04 . 81
Л . I . Козлов
1 ена Ленина институт кибернетики АН Украинской CCP — Ф (72) Автор изобретения (71) 3 а яв итель
Орд (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ
АЛГЕБРАИЧЕСКИХ УРАВНЕНИЯ г
Изобретение относится к вычислительной технике и может быть использо-.;, вано при построении специализиро-- ванных и проблемно-ориентированных .вычислительных машин и комплексов.
ИзвестнО устройство для моделирования обыкновенных дифференциальных. уравнений", .содержащее цифровой блок, аналоговые запоминающие устройства, два суммирующих усилителя с цифровыми управляемыми сопротивлениями во входиих цепях. .9то устройство используют для решения систем линейных алгебраических уравнений (СЛАУ), когорые, предварительно преобразуются в эквивалентную. систему линейных дифференциальных уравнений (Ц
Недостаткааж этого,устройства является низкая точность решения
СЛАУ, обусловленная. ограниченной точностью аналоговых: блоков, и большое время..рещеиия задач из-за большой.инерционности интеграторов., необходимой для обеспечения устойчивости процесса решения.
Известно устройство для решения
СЛАУ, содержащее группы сумматоров приращений, регистров приращений ! и сумматор, группу входов которого соединена с выходами. соответствующих
2 регистров приращения, входы которых соединены со входами сумматоров приращения, выходы которых соединены с выходами устройства (2).
Недостатками этого устройства являются большой объем оборудования, поскольку при решении СЛАУ и-го порядка в устройстве используется п +и .„ злов умножения приращений, и интеграторов и и сумматоров на и+1 входах, большое время решения иэ-эа инерционности, вносимой интег- раторами, и трудность автоматизации ввода в устройство коэФфициентов рейз шаемой системы из-эа наличия большого количества узлов умножения, автома,тизация ввода информации в которые существенно усложняет блок управяеийя устройства.
20 Наиболее близким по техничесиой сущносюи к предлагаемому,изобретению является устройство, содержащее группы сумматоров приращений, регистров приращений неизвестных н блоков.уи25 ножения приращений, сумматор, группа входов которого соединена с выходами ,блоков умножения приращений, выход сувеаатора через блок памяти неэязок, соединен со своим входом и через блок
ЗО.умножения невязок - с первым входом
824217 коммутатора, выходы которого соединены со входами регистра приращений.неизвестных и входами сумматоров приращений, выходы которых соединены с выходами устройства, выходы. блока управления соединены со вторыми вхО- 5 дами коммутатора и. блока памяти невя-, зок, а также со входом блока памяти коэффициентов, выходы которого соединены со вторыми входами блоков умножения приращений и вторым входом блока умножения невязок, устройство работает следующим образом.
В исхвдном состоянии коэффициенты а„- системы управлений и 15 à..Ъ =Ъ.; (! )
j=" .." — 1",n ° записаны в блоке памяти коэффициентов, а значения свободных членов Ь содержатся с блоке памяти невязок.,ф Начальные значения неизвестны х„(ЮЬ
=О заносятся в сумматоры приращений.
Каждая К-ая итерация вычислений состоит из циклов по числу строк решаемой системы уравнений (1). В
i--ом цикле осуществляется выдача коэффициентов a„ (j=l,n) из блока памяти коэффициентов на вторые входы блоков умножения приращений, на пер- вые входы которых поступают приращения неизвестных А xj i-ой невяэки Е, которое запоминается в блоке памяти невязок, и пос- 4Q тунает на второй вход блока умножения невязок, на первый вход которогс с выхода блока памяти коэффициентов подается значение Н„, определяющее абсолютную величину приращения неизвестной ах)", знак. которого соответствует знаку невяэки Е) . По к .лученное на выходе блока умножения Сз невязок значение приращения неизвестного х » подается через коммута 1 5Î тор 8 на вход )»го регистра прираще- ний 1, где запоминается, и на вход i-га сумматора приращения 2, в ко.тором форьируется поЛное значение искомой неизвестной х; (В рассматриваемом. устройстве реа.. лизуется одна из модификаций метода простой итерации, который сходится в том случае, если коэффициенты матрицы решаемой СЛОУ удовлетворяют сле- бО дующим условиям ) ай> ф„И+ ), т.е. диагональные коэффициенты по абсолютной величине больше суммы моду-, лей всех остальных коэффициентов s строке или в столбце Г31 .. 65 Однако имеется широкий класс важных научно-.технических задач, которые сводятся к СЛОУ с матрицей коэффициентов, не удовлетворяющие йриведенным ограйичениям. Такие задачи.не возможно решить с.помощью известного устройства. Цель изобретения - расширение. функциональных возможыоотей за счет обеспечения решения класса задач, не удовлетворяющих условию, когда диагональные коэффйциенты по абсолютной величине не болыае суммы модулей всех -остальных коэффициентов в строке или столбце. Поставленная цель достигается тем, что в устройство, содержащее сумМато ры приращений, регистры приращений неизвестных, блоки умножения приращений, сумматор, группа входов которого соединена с выходами блоков умножения приращений, выход:сумматора.через блок памяти невязок соединен со своим входом и через блок умноже,ния невязок. — подключен ко.входу коммутатора, выходы которого соединены соответственно со входами регистров приращений неизвестных и с входами сумматоров приращений, вйходы которых являются выходами устройства, управляющиЕ входы коммутатора и блока памяти невязок соединены соответственно с первым и вторым. выходами блока управления, третий выход которого соединен с. входом блока памяти коэффициентов, выход которого подключен к первым входам блоков умножения приращений и к входу блока умножения невязок, введены переключатели и регистры приращений невязок, входы которых соединены соответственно с выходами коммутатора,,информационные входы каждого "переключателя соединены с выходами соответствующих регистров приращений неизвестн х и приращений неиязок, управляющий вход каждого переключателя соединен с четвертым выходом блока управления, а выход ." подклкиен ко второму входу соответствукпцего блока умножения приращений ° На чертеже представлена схема предлагаемого устройства. Устройство содержит регистры 1 приращений неизвестных, регистры 2 приращений иевязок, сумматоры 3 приращений, переключатели 4, блоки 5, умножения приращений, блок 6 умножения невязок, сумматор. 7, блок 8 памяти невязок, коммутатор 9, блок 10 памяти коэффициентов, блок 11 управления и выходы 12 устройства. Устройство работает следующим образом. В исходном состоянии коэффициенты решаемой системы уравнений записаны в блоке 10 памяти коэффициентов, а значения свободных членов содержатся в.йище З памяти невязок. 824217 ное значение искомой неизвестной и выдается на выходы 12 устройства. Обычно функция формирования приращения Н „ (Е „." ) выбирается такой, чтобы упростить устройство и повысить его быстродействие.,Так, например,. если выбрать Н„ (Е,. )= 2 "(в=1-р), где р — разрядность. представления чисел в устройстве), то блоки умножения приращений значительно упрощаются 10 и цревращаются в группы элементов И, через которые, в.зависимости от знаков соответствующих невязок, передаются коэффициенты а;> на входы сложения или вычитания сумматора 7. Однако для некоторых специальных классов задач приращения ах ." и, (к) hy выбираются двух- и более разрядными, что несколько усложняет блоки 5 умножения приращений и снижает бы. стродействие устройства. Формула изобретения Начальные значения искомых неизвест- ных х1(0)=0 заносятся в сумматор 3 приращений. Каждая итерация вычислений состоит из числа циклов, в два раза больших числа строк решаемой СЛАУ . В 1-том цикле первой группы циклов (i= 1„n) осуществляется выдача коэффициентов из блока 10 памяти коэффициентов на входы блоков 5 умножения .приращений, на другие входы ко- торых через переключатели 4 поступают приращения неизвестных с регистров 1 приращений неизвестных. Резупьтаты произведений с выходов блоков 5 умножения приращений поступают на входы сумматора 7, на другой вход которого подается значение i-той невязки на предыдущей ите. рации E„. с выхода блока 8 памяти (- ) невязок. На выходе сумматора 7 формируется новое значение i-той невяэки, которое запоминается в блоке 8 памяти невязок и поступает на вход блока 6 умножения невязок, на другой вход которого с выхода блока 10 памяти коэффициентов подается значение Н;, определяющее абсолютную величину приращения Фзевязки у("), знак которого равен знаку соответствующей невязки Е; . В зависимости от . к) значения шага приращения, в блоке 6 умножения невяэок производится формирование одноразрядного или несколькоразрядного приращения д,у(1к1 . Значение шага приращения зависит от класса решаемых устройством задач и от реализуемого в устройстве метода решения.СЛАУ. Полученное на выходе блока 6 умножения невязок значение приращение невязки подается через коммутатор 9 на вход i-ro регистра 2 приращений невязок, где оно запоминается. Аналогично в i+1 цикле формируется приращение невязки Ьу„+„<") В и+i цикле второй группы циклов (i=-1,n) осуществляется выдача коэф". фициентов иэ блока 10 памяти коэффициентов на входы блоков 5 умножения приращений, на другие входы которых через переключатели 4 поступают приращения невязок с регистров 2 приращений невяэок. Результаты произведений с выходов --тых блоков 5 умножения приращений поступают на входы сумматора 7, на выходе которого фомируется значение +1-ой невяэки которое поступает на вход блока б ум; ножения невязок. На другой вход блока 6 умножения невяэок . подается значение шага приращения, в соответствии с которым производится формирование приращения неизвестной, которое подается через коммутатор 9 на вход i-го регистра 1 приращений неизвестных> где оно запоминается, и на вход i-го сумматора 3 приращений, в котором формируется пол25 Устройство для решения систем линейных алгебраических уравнений, содержащее сумматор я приращений, регистры приращений неизвестных,.блоки умножения приращений, сумматор, входы которого соединены соответственно с выходами блоков умножения приращений, вь-:од сумматора через блок памяти невязок соединен со своим входом и через блок умножения невязок — подключен ко входу коммутатора, выходы которого соединены соответственно со входами регистров приращений неизвестных и с входами сумматоров приращений, выходы которых являются выходами устройства, управляющие входы коммутатора и блока памяти невяэок соединены соответственно с первым и вторым выходами блока управления, третий выход которого соединен со входом блока памяти коэффициентов, выход которого подклю,чен к первым входам блоков умножения приращений и к входу блока умно1жения невяэок 1 о т л и ч а ю щ е е с я тем, что, с целью расширения ,класса решаемых задач, в него введе ны переключатели и регистры приращений невязок, входы которых соедине,ны соответственно с выходами коммутатора, информационные входы каждого переключателя соединены с выходами соответствующих регистров приращений неизвестных и приращений невязок, управляющий вход каждого переключателя соединен с четвертым выходом блока уиравления, а выход — подключен ко второму входу соответствующего блока умножения приращений. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР Р 307404, кл. 6 Об F 5/32, 1969. 824217 Сос т.авитель Редактор Н. Рогулич Уекред ."@ .Савка, Корректор М. Демчик Юю ° ЬюВВююВВФВ Ф Я Заказ 2126/72 Тнуаж!745 Подписное ВйййПИ Государотвейиого комитета СССР по делам изобретеиий и открытий 113035, Москва, В-35, Раушская иаб ., д.,4/5 Филиал ППП "Патент", r. егоyag„ ya. Проектная, 4 2. Майоров Ф. В. Электронные цифyOSh39 интегрирующие машины. М., "Маза из", 1962, с. 86-88. 3. Авторское свидетельство СССР Р 564638, кл. G 06 F 15/32, 1972 (прототип).