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

1481794Изобретение относится к вычислительной технике и может быть использовано для решения систем линейных алгебраических уравнений.Цель изобретения - повышение быст 5 родействия, достигаемое за счет параллельного вычисления для каждой итерации произведения коэффициентовнеизвестных на значения самих неизвестных при использовании итерационального. метода Зейделямн ф м Ю-(а также за счет ускорения итерационального процесса за счет исключения из дальнейших вычислений неизвестных, найденных с требуемой точностью и переходе на .(К+1)-й итерации к нахождению п-й неизвестной, если (и)-е неизвестные найдены в предыдущих К-х итерациях.На чертеже представлена схема устройства.Устройство содержит первый 1 и второй 2 блоки памяти, первый и второй счетчики 3 и 4, дешифратор 5,первый и второй КБ-триггеры 6 и 7,сумматор 8, блок 9 вычитания, блок 10 сравнения, и блоков 11 -11" умножения, и регистров 12-12 , первый,втонрой и третий элементы ИЛИ 13-15,эле" мент НЕ 16, первый, второй и третий элементы И 17-19, первую 20 -20", вторую 21" -21", третью 22 -22", чет вертую 23 -23" группы элементов И, вход 24 запуска устройства, вход 25 коэффициентов и правых частей системы уравнений устройства, вход 26 значения точности решения системы урав нений устройства, выход 27 результата решения устройства.Устройство работает следуннцим образом.Нулевое приближение. Так как блок 45 9 вычитания установлен в состоянии 000, а на второй вход блока 10 сравнения подано значение Ь а, то на выходе блока 10 вырабатывается высокий потенциал, который через элементы ИЛИ 15 и 13 подается на первый вход элемента И 17, разрешая прохождение перепада потенциалов с прямого выхода триггера 6, возникающего при поступлении на его вход Я управляющего сигнала, на счетный вход счетчика 3, одновременно триггер устанавливается в единичное состояние. Так как в блаке 1 памяти (ЗУ 1) информация записана во все ячейки 1, то по адресу 0001 из нее считывается "1" и разрешит через элемент И 18 прохождение кода 0001 на адресный вход блока 2 памяти (ЗУ 2) и вход дешифратора 5. Из ЗУ 2 по адресу 0001, что соответствует выбору коэффициентов первого уравнения системы линейных алгебраических уравнений, считываются и подаются значения , на первый вход сумматора 8. На другие (2,; ,и+1) входы сумматора подаются значения 0000, так как в блоках 11 -11 умножения коэффициенты Ы; умножаются на код 0000, Таким образом, на выходе сумматора имеем хо = , + Е Ф;1 0 =Это значение через элемент И 19 переписывается в регистр 12 , Аналогичным образом проводятся итерации 2. п.После и-й интерации в региистрах 12 -12 записываются соответствующие значения начальных прибли"е йоПервое приближение. Из ЗУ 2 последовательно выбираются коэффициенты соответствующих уравнений СЛАУ и поданы соответственно: ; - на первый вход сумматора 8, с 11 - на первый вход соответствующего блока 1 ум" ножения, в котором производится перемножение значений этих коэффициентов на значения нулевых приближенийю;1 х";, Эти значения суммируются в сумматоре 8 и подаются на первый вход блока 9 вычитания, на второй его вход подается значение нулевого приближения 1-й неизвестной х из;1 соответствующего регистра 12 через соответствующий элемент И 22 и элемент ИЛИ 14, Выбор соответствующего регистра 12" осуществляет дешифратор 15 путем возбуждения соответствующей выходной шины. Таким образом, в блоке 9 вычитания определяется разность между значениями 1 неизвестной СЛАУ нулевого и первого приближений.Далее, если эта разность меньше или равна допустимой ошибке, то по адресу 1 в ЗУ 1 записывается "0", одновременно значение 1-й неизвестной первого приближения переписывается в соответствующий 1-й регистр, а так" же записывается "1" в счетчик 4. Аналогично проводят п итераций ви ,результате чего в регистрах 12 -12 записываются значения неизвестных первого приближения.5 1481 794Подобным образом производят второе, третье и т.д. приближения. Окончание работы происходит при достижении счетчиком 4 состояния и,Повышение быстродействия работы5устройства достигается за счет исключения из дальнейших вычислений значений неизвестных, вычисленных припредыдущих приближениях, так чтоесли 1-я неизвестная вычислена с заидданной точностью (т,е. х - х, сЬ Ь,), то в соответствующую 1-юячейку ЗУ 1 записывается "О". Тогдана следующем приближении при считывании по адресу 1 из ЗУ 1 на выходеЗУ 1 появляется "О" означающий, чтопо адресу 1 из ЗУ 2 информация не выбрана. Одновременно после прохождения через элемент НЕ этот сигнал изменяет состояние счетчика 4 на "1",т,е. производится ускоренный переходк следующей (1+1)-й итерации.При достижении счетчиком 4 состояния и на его выходе вырабатывается 25сигнал, устанавливающий первый триггер в нулевое состояние и разрешающий выдачу содержимых регистров12 -12" через элементы И 23 -23 навыходе 27 устройства.30 Формула изобретения Устройство для решения систем линейных алгебраических уравнений, содержащее первый и второй блоки памяти, первый и второй счетчики, первый и второй триггеры,. сумматор, и бло" ков умножения, где и - порядок системы линейных алгебраических уравнений, и регистров, первый, второй и третий элементы ИЛИ и первую группу из и элементов И, о т л и ч а ю щ е.е с я тем, что, с целью увеличения быстродействия, оно содержит первый, второй и третий элементы И, элемент НЕ, вторую, третью и четвертую группы по и элементов И каждая, дешифратор, блок вйчитания и блок сравнения, при этом вход запуска устройства, вход коэффициентов и правых частей уравнений устройства, вход значения точности решения системы уравнений устройства подключены соответственно к информационному входу первого триггера, к информационному входу первого блока памяти и к первому входу блока сравнения, выход первдго триггера подключен к первому входу первого элемента И, выход которого объединен через элемент монтажное ИЛИ с выходом переноса первого счетчика и подключен к счетномувходу первого счетчика и к информационному входу второго триггера, инверсный выход которого подключен кпервым входам элементов с первого пои-й И первой группы, выходы которыхподключены соответственно к информационным входам регистров с первогопо и-й, выходы которых подключенысоответственно к первым входам элементов И с первого по и-й второйгруппы, вторые входы которых подключены к прямому выходу второго триггера, выход 1-го (д = 1и) элемента И второй группы подключен к первым входам -го элемента И третьейи четвертой групп и к первому входу-го блока умножения, выход которогоподключен к д-му информационномувходу сумматора, информационный выход первого счетчика подключен к адресному входу второго блока памятии к первому входу второго элемента И,выход которого подключен к адресномувходу первого блока памяти и к входу дешифратора, выходы с первого по и-й которого подключены соответственно к вторым входам элементов И с первого по и-й первой группы и соответственно к вторым входам элементов И с первого по и-й третьей группы, выходы которых подключены к входам первого элемента ИЛИ, выход которого подключен к первому входу блока вычитания, выход которого подключен к второму входу блока сравнения, первый и второй выходы которого объединены через элемент МОНТАЖНОЕ ИЛИ и подключены к первому входу второго элемента ИЛИ и к счетному входу второго счетчика, выход перепол-45нения которого подключен к вторым входам элементов И четвертой группы и к инвертированному информационному входу второго блока памяти,вы" ход которого подключен к второму входу второго элемента И и к входу элемента НЕ, выход которого подклю" чен к первому входу третьего элемента ИЛИ, выход которого подключен к второму входу первого элемента И, выход второго элемента И подключен к входу дешифратора и к адресному входу первого блока памяти, выходы с первого по и-й которого подключе"1481 794 Составитель В. СмирновТехред М.Ходанич КорректорВ. Гирняк Редактор В. Данко Заказ 2692/51 Тираж 669 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 ны соответственно к вторымвходам блоков умножения с первого по п-й, (и+1)-й выход первого блока памяти подключен к (и+1)-му входу суммато 5 ра, выход которого подключен к второму входу блока вычитания и к первому входу третьего элемента И, выход которого подключен к третьим входам элементов И первой группы,тре; тий выход блока сравнения подключен к второму входу второго элемента ИЛИ, выход которого подключен к второму входу третьего элемента И, квходу установки в "О" второго триггера и к второму входу третьего элемента ИЛИ, выход переполнения второго счетчика подключен к входу установки в "0" первого триггера, к вторым входам элементов И четвертойгруппы, выходы которых подключены квьходам результата решения устройства.