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

СОЮЗ СО 8 ЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 4 1191 6 Е 1/02, 15/32 ЕТ СССР И ОТКРЫТ ИСА ВТОРСКО ВИДЕТЕЛЬСТкров рг И.М, Програмк вычислительнроение, 1972.дифференциальныпер. под ред. ашин. к а- асвидетельство С С 06 Р 15/32,свидетельство С С 06 Р 15/32,ТВО ДЛЯ РЕШЕНИЯ КИХ УРАВНЕНИЙСР973.СР976,ИСТЕМ ГОСУДАРСТВЕННЫЙ КОМ ПО ДЕЛАМ ИЗОБРЕТЕНИ(56) Витенб ние аналого М.: Машинос Цифровые лизаторы./С на Б.Я. 196 Авторско У 682902, к Авторско Е 71 ОО 44, к(57) Изобретение относится к области цифровой вычислительной техникии может быть использовано в специализированньк устройствах, предназначенных для решения систем линейных алгебраических уравнений, Цельизобретения - повьппение скорости вычислений. Указанная цель достигается тем, что устройство содержит регистровые блоки коэффициентов матрицы коррекции, умножители, группысумматоров, регистровый блок памятикоэффициентов уравнений, регистрыневязки, триггер, сумматоры экстраполированньк значений, счетчик, дешифратор, элементы И. Устройствореализует решение методом приближений с одновременной коррекцией матрицы экстраполяции. 1 ил.Изобретение относится к пифровойвычислительной технике и может бытьиспользовано в специализированныхустройствах, предназначенных длярешения систем линейных алгебраических уравнений.Цель изобретения - повьшение скорости вычислений,На чертеже изображена функциональная схема предлагаемого устройства (для упрощения показана реали-,зация лишь одного (первого) уравнения из множества алгебраическихуравнений),Устройство содержит регистровыеблоки 1 коэффициентов матрицы коррекции с первой по п-ю, группы 2 -2 ц умножителей, первую 3, вторую 4,третью 5, четвертую 6 группы сумматоров, с (и+1)-й по 2 и-ю группы 7 -71 умножителей с (2 п+1)-й по 3 и-югруппы 8, -8 умножителей, регистровый блок 9 памяти коэффициентов уравнений, регистр 10 невязки, григгер11, сумматор 12 экстраполированныхзначении, счетчик 13, дешифратор 14и первые 15 и вторые 16 элементы И.Устройство работает следующим образом,Время работы разбито на циклы.Каждый цикл содержит п тактов, Один такт равен времени прохокдения одного разряда, число разрядов равно ш. Начало цикла в виде сигнала поступает с внешнего входа устройства на счетчик 13 и триггер 11, В результате в счетчике формируется номер шага (в данном случае один шаг), а триггер 11 перебрасывается в "1" состояния и на выходе элемента И 5 формируется приращение длиной ш разрядов, Приращение, начиная с младших разрядов, поступает на умножитель 71, на остальные умножигели приращения поступают с выходов в других ячеек,.Так как произведегие имеет 2 ш разрядов, то ш старших разрядов формируется во втором цикле. Начиная с первого разряда второго никла, величина с выхода сумматора 5 поступает на умнокитель 2 па выходы остальных умножителей поступает информация с выходов сумматора 5 других ячеек. Получаемые на выходах умножителей 2 (1=1,п) произведения складываются на сумматоре 3, Полученная величина затем складываетсярассогласованием, хранящимся в регистре 10, Так как сумма произведений на выходе сумматора 3 имеет 2 шразрядов, то и регистр 1 О имеет 2 тразрядов, поэтому ш младших разрядов рассогласования, получающиесяво 2-м цикле, не участвуют в формировании приращений. Это достигаетсятем, что по сигналу начала второгоцикла триггер 11 перебрасывается в"О" и закрывает элемент И 15. Одновременно с умножителями 7) в первомпикле начинают работать умножители8 (1=1,п). Множимые поступают с выходов регистров 9 ц=1 и), множители хранятся в регистрах умножителей, которые заносятся туда из регистров 1,1. Полученные произведенияскладываются на сумматоре 6. Во втором цикле, когда на входы сумматора6 поступают старшие ш разрядов произведений, открывается второй элементИ 16 сигналом с дешифратора 14 и поступает на вход сумматора 6 число,равное 1. По этому же сигналу разрешается запись з регистр 1, величины,получаемой на выходе сумматора 6,Затем все повторяется, за исключением того, что число, равное 1, не добавляется к сумме произведений,формируемой на выходе сумматора 6. Навыходе дешифратора 14 формируютсясигналы, управляющие записью в регистры 11 в следующей последовательЧерез2 п циклов счетчик 13 переполняет 35ся. Сам он переходит в нулевое состояние, а на выходе переноса появляется сигнал . По сигналу содержимоерегистров 11 перезаписывается в ре 1 3истры умнокителей 7 и 8 , Это допускается, так как через 2 п цикловво всех регистрах 1,; сформированынужные величины элементов матрицы Ф. На выходе сумматора 5 формирует 5ся приращение неизвестной величины,которое поступает на накопитель 12,где складывается с предыдущим зна:ением искомой величины, Если текущее значение искомой переменной обозначить через Х , значение, полу. ктчаемое на выходе сумматора 5 через, к+1где 1=1и, ч Х - приращение, получаемое на выходе элемента И 15 в текущем шаге, Ф - элементы матрицы Ф, являющейся некоторым приближением обратной матрицы. На выходе сумматора 3 формируется величинаэ(к 11 Полученная величина складывается с содержимым регистра 10, который хранит текущее рассогласованиек+1Рассогласование Б используется .для формирования нового приращенияК 1 2Этот процесс описывается системой уравнений; кк Вк 1 В УХк Рк а 9 л к чХ =Р,Б ) - чХ = ч Х =ччХо . кгде Р (Б ) - функция выделения шЯразрядов с 0 по ш в переменной Б,Х= ХХ - вектор неизвестных, - матрица коэффициентов исходной системы уравнений,аа,аип Фц,ФФ,вспомогательная матрица. в =в,в= 1 ьь ,ь,1 Ф=А +А ,Е-,Л),=Е-А. Значения коэффициентов, хранимых в первом столбце, поступаютна схемы умножения устройства, реализующего первое уравнение, второгостолбца - второго уравнения и т.д.Соответственно на вторые выходыумножителей поступают значения строкматрицы Ф, т,е,векторсвободных членов.За начальное приближение выбирают Ф=Е+(Е-А),Ф в этом случае равно: У =Ф и (1=1,и)1Полученные произведения суммируются на сумматоре иК+15 Ф = Ф й +1,и . -ц 11Во втором шаге изменяется расположение информации в блоке 9, второй столбец передвигается на местопервого, третий - второго и т.д.и первый на место п-го,Во втором шаге формируется5=Этот процесс продолжается и шагов,что позволяет определить все коэффициенты строки матрицы Ф:где 1=1,и1,.1, если Х=Ов 0, если )Х)0Соответственно, во втором устройстве формируетсяигде 1=(2,1)п - означает, что 7 принимает последовательно значения 2,3,,и,1.ЗОНа первом шаге происходит корректировка сначала элементов основнойдиагонали, во втором шаге - ближайшей боковой и первого элемента (и)строки, в третьем - следующей боковойдиагонали и первого элемента (и)-йстроки элемента и т,д т.е, еслиОФ =Е+ (Е-А), тоФ =Е+ (Е-А)+ (Е-А)э.40 Ф Е+ (Е-А)+ (Е-А) + (Е-А)Ф =Е+ (Е - А)+ + (Е-А)Формула изобретенияУстройство для решения системалгебраических уравнений, содержащее с первой по и-ю группы из и умножителей, и накапливающих сумматоров экстраполированных значений, первую и вторую группы из и сумматоров, и резисторов невязки, первые информационные входы умножителей с первой по и-ю групп являются входами записи значений коэффициентов уравнений уст ройства, выходы 1.-х умножителей3 12 которого подключен к первому информационному входу 1-го сумматора второй группы, выход которого подключен к входу -го регистра невязки, выход которого подключен к второму информационному входу -го сумматора второй группы, отличающее с я тем, что, с целью повыщения скорости вычислений, оно содержитс (и+ +1)-ю по Зп группы по и умножителей, третью и четвертую группы по и сумматоров, п регистровых блоков памяти коэффициентов матрицы коррекции,регистровый блок памяти коэффициентов уравНений, первую и вторую группы элементов И, п триггеров, дещифратор и счетчик, информационные выходы х-го регистрового блока памяти коэффициентов матрицы коррекции подключены к первым информационным входам 1-х умножителей с (и+1)-й по 2 п-ю групп и к первым информационным входам 1-х умножителей с (2 п+1)-й по 2 п-ю групп, выходы -х умчожителей групп с (и+1)-ю по 2 п-ю подключены к информационным входам 1.-го сумматора третьей группы, выход которого подключен.к второму информационному входу 1-го умножителя -й группы и к информационному входу соответствующего -го накапливающего сумматора экстраполированных значений, выход х-го сумматора второй группы подключен к первому входу 2 б 427 Ь1.-го элемента И первой группы, второй вход которой подключен к выходу-го триггера, вход сигнала началацикла подключен к информационным входам триггеров и счетчика, выход сигнала переполнения которого подключен к управляющим входам умножителейс (и+1)-ю по Зп-ю групп, информационные .выходы счетчика подключены к О входам дешифратора, 1-й выход которого подключен к соответствующим управляющим входам -го регистровогоблока памяти коэффициентов матрицыкоррекции и к первым .входам 1-го 5 элемента И второй группы, второйвход которого подключен к входу управления режимом коррекции устройства, выход -го элемента И второйгруппы подключен к управляющему вхо ду 1-го сумматора четвертой группы,информационные входы которого подключены к выходам -х умножителейгрупп с (2 п+1) -ю по Зп-ю, а выходк информационным входам -го регист рового блока памяти коэффициентовматрицы коррекции, выход -го элемента И первой группы подключен квторым информационным входам 1-х умножителей групп с (и+1)-ю по 2 п-юи к информационным выходам устройства, второй информационный вход 1-гоумножителя подключен к -м выходамрегистрового блока памяти коэффициентов уравнений.,Пожо каз 2133/ Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектн 47 Тираж 671ВНИИПИ Государствепо делам изобрет 13035, Москва, Ж,Подписноеного комитета СССРний и открытийаушская наб д, 4/5