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

Союз СоветскикСоциалистическиеРеспублик ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ) Приоритет -Яе -сударственнв 1 й комитетоввта Министров СССРоо делам изобретенийи открытий(72) Авторы изобретени Ленинградский ордена Ленина инс железнодорожного транспорта им.В. Н, Образцова инженеровмика Заявитель РОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ РЕШ СТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕН ИЙ 4) 10 ведена например соеди решению их уравиержит первызователей 1Изоб)тетение относится к области вы числительной техники и может быть использовано при построении устройств для решения систем линейных алгебраических уравнений методом итераций.Известно вероятностное устройство для решения систем линейных алгебраических уравнений, содержащее преобразователи число-вероятность, блоки умножения и сложения, генератор случайных чисел, интеграторы корней. Недостатком этого устройства является низкое быстро действие, связанное с медленной сходимостью процесса итераций, и большая аппаратная сложность 11.Наиболее близким техническим реше кием к данному изобретению является вероятностное устройство для решения систем линейных алгебраических уравнений, содержашее последовательно соединенные первый блок ключей, блок преобразователей число-вероятность, блок умножения, блок сложения, блок интегрирования, вто рой блок ключей, управляющий вход которого соединен с управлякюцим входом первого блока ключей и с. выходом блокауправления, вход которого соединен с выхдом генератора тактовых импульсов и совходом генератора случайных чисел, выход которого подключен к управляющемувходу блока преобразователей число-вероятность и,Недостатком этого устройства такжеявляется низкое быстродействие.Пель изобретения заключается в повышении быстродействия вероятностногоустройства для решения систем линейныхалгебраических уравнений. Для достижения постановленной задачи оно содержитблок задержки, входы которого соединены 15 с выходами блока сложения, а выходисо входами блока умножения соответственно.Блок-схема устройства прифиг. 1. На фиг. 2 приведен 20 пения блоков применительно ксистем линейных алгебраическний третьего порядка.Устройство соде й блок кпюеей 1, блок преобра число-ве633 024 Т.-(+м)1 , (Ъ) зроятность 2, блок умножения 3, блок сложения 4, блок интегрирования 5, второйблок ключей 6, блок управления 7, гене. ратор тактовых импульсов 8, генераторслучайных чисеп 9 блок задержки 10.Выходы первого блока ключей 1 связаны свходами блока преобразователей 2, выходы которого подключены к входам блокаумножения 3. Выходы блока умножения3 соединены с входами блока сложения1 Ф4, выходы которого подключены к входамбпока.интегрирования 5 и блока задержки 10. Выходы блока задержки 10 соединены с входами блока умножения 3, авыходы бпока интегрирования 5 - со вхо Вдами второго блоке ключей 6.Управляющие входы первого и второгоблоков ключей 1 и 6 подкпючены к выходу блока управления 7, вход которогосоединен с выходом генератора тактовых Мимпульсов 8 и со входом генератора случайных чисел 9, а выход генератора случайных чисел 9 подключен к управляющему входу блока преобразователей 2Работает устройство следующим обра- Изом,Если задана система линейных алгебраических уравненийиЕ а, Х, =Ь(т=,гп)где Х -корни системы.д . - постоянные коэффициенты1то при ст,.0 она эквивалентйа приведенной системеЗЮХРЕА; х; (1:,гп) (1)4 4р: - т- -приведенные свободные члены,аЦф т=-цп при тИ- приведенные коэффициейты,Х- корни системы линейных алгебраических уравнений, которая и реализуетсяв схеме прототипа. При этом известныеусловия сходимости итерационного процео 43са (1) должны быть дополнены условиями несовместности;потоков с( дпя кажт 3дого. Физически процесс итераций( 1) е схеме прототипа обеспечиваетсяза счет. связи выходов блока интегрирова ффния с входами блока умножения.За счет этой обратной связи в данномустройстве так же как и в прототипе реализуется процесс поспедоватепьных приближений систем (1) в видеИгде К - номер итерации. По сигнапу из блока управления коэффициенты А; ; передаются на блок преобразователей число-вероятность 2, в котором осуществляется их преобразование в случайные двоичные поспедоватещ ности с математическими ожиданиямиФ равными численным значениям соответст - вующих коэффициентов. Все последовательности из блока преобразователей 2, а также задержанные последовательности с выхода блока сложения 4 непрерывно поступают на входы блока умножения 3.Все и выходных последовательностей блока сложения 4 интегрируются при помощисчетчиков блока интегрирования 5.Каждая новая итерация в устройстве обеспечивается .за счет передачи вектора(к)корней Х из блока сложения 4 на бпок задержки 10 (каждый вход в блоке 10 задерживается на 1 такт) и передачи этого вектора через 1 машинный такт (длитепьность такта задается блоком 8) на входы блока умножения. В результате на выходах блока слежения 4 в соответ-ствии с (2) образуется новый вектор), ) т,е, новое прибпижение корней Х - . Таким образом, дпя получения каждого (по к) нового и точного значения Х трек+) буется лишь один машинный такт, а задача попучения оценки )( с заданной точСг)ностью Е ( " -требуемое число итераций) сводится к накоплению символов 1 последовательности Х( 5 =1,2 в ) эа0+а)1 тр 1 Яп= ) тактов. Здесь 1 р -параметр нормального распределения, Следовательно, общее время решения системы линейных алгебраических уравнений в предлагаемом устройстве составит где- тактовая частота работы устройства.По сигналу из блока управления 7 содержимое счетчиков блока интегрирования 5 при помощи второго блока ключей 6 передается на выход устройства.Время решения Т, определяемое соотношением (3) значительно меньше времет(ни Т расходуемого на ту же операцию в схеме прототипа.Действительно, если по исходному условию процесс последовательных приближений (2) в схеме прототипа сходится за Р итераций и требуемая точность вычисления приближенного значения Х(к ), на каждом шаге равна с, то общее время решения системы линейных алгебраичесТаким образом, дпя получения новогои точного значения корня (т,е, результата каждой последующей итерации) требуется только один машинный такт,Технико-экономический эффект заявляемого устройства закпючвется в резком(10-50 рвз) сокрашении времени дпярешения СЛАУ по методу итераций,633024/ких уравнений Т получим, воспользовавшись соотношением (3)т:(, ),где п -количество тактов, необходимое дпя получения результата с точность С- параметр нормального распределения.Т=т (4)Так как обычно в Ъ 1, то уравнение16 (4) дает время решения большее врвз, чем уравнение (3), справедливое дпя предлагаемого устройства. Обычно итерационный процесс завершается через несколько десятков итераций, т.е. Р = 10-50.33 Это число и определяет выигрыш в быстродействии заявляемого устройства.Физически этот эффект можно объяснить тем, что если в схеме прототипа(кн) каждое новое приближение Хдолжно быть выражено в форме многоразрядного кода (на что требуется 7 п машинных тактов), то в предлагаемом устройстве каж(кодое новое приближение Х образуется в форме вероятности появления бинарного символа и, следовательно, занимает лишь 1 такт машинного времени.Соединения выходов блока задержки 10 с выходами блока умножения 3 уста- з навпиваются в соответствии с уравнением (2). На фиг. 2 показан пример расположения таких соединений применительно к решению систем линейных алгебраических уравнений третьего порядка.33Анализ этой схемы показывает, что выражения дпя последовательных приближений значений корней Х,Х, Х в точности совпадают с видом уравнения ( 2) . Например, для выхода Х схемы получаемФормула иэобретенняВероятностное устройство дпя реве ния систем пннейных алгебраических уравнений, содержашее последовательно соединенные первый блок ключей, блок преобразователей число-вероятность , блок умножения, блок сложения, блок интегрирования, второй блок ключей, управляющий вход которого соединен с управпяющим входом первого блока ключей и с выходом блока управления, вход которого соединен с выходом генератора тактовых нмпульсов и со входом генератора случайных чисел, выход которого подключен к управляющему входу блока преобразователей число-вероятность, о т п и ч а юш е е с я тем, что, с целью повышения быстродействия устройства, оно содержит блок задержки, входы которого соединены с выходами блока сложения, а выходысо входами блока умножения соответственно.Источники информации, принятые вовнимание прн экспертизе;1. Яковлев В. В., Федоров Р. Ф, Стохастические вычислительные машины, Л., "Машиностроение, 1974, с. 322-329.2. Авторское свидетельство СССРРедактор Заказ 6555/39 Тираж 78 ЦНИИПИ Государственного по дедам и 113035, Москва,ЖПодписноеСовета Министр ССС комите бретен35, Рау ий и открытий шская наб., д