Файл: Яковлев, В. В. Стохастические вычислительные машины.pdf

Решение системы алгебраических уравнений

« 1 1 - ^ 1 + « 1 2 - ^ 2 ~ Ь - • - + « 1 т Х -т — Ъ ^

вычислительными устройствами аналогового типа возможно раз­ личными методами: итерацией по формуле Зейделя, методом об­ ратной матрицы, приведением системы алгебраических уравнений к системе линейных дифференциальных уравнений, минимиза­ цией и т. д.

Подобные же методы могут быть реализованы средствами сто­ хастической вычислительной техники. В частности, в п. 22 по­ казан способ решения системы уравнений (9.1), заключающийся в нахождении корней характеристического уравнения соответст­ вующей системы дифференциальных уравнений, где решается ди­ намическая задача. При этом система дифференциальных уравне­ ний должна описывать устойчивый процесс, т. е. корни характе­ ристического уравнения системы должны иметь отрицательные вещественные части. Тогда предельные значения (при t -> оо) переменных системы дифференциальных уравнений совпадают с корнями соответствующей системы алгебраических уравнений.

Системы уравнений (9.1) часто решаются на СтВМ в явном виде, когда моделируется решение системы (9.1) относительно неизвестной X t (i = 1, 2, . . ., т):

dj_ d ’

где

« п «12 h « 1 m

Определитель d L получается заменой в определителе d i - го столбца столбцом из свободных членов системы уравнений (правило Кра­ мера).

При небольших т (т ^ 6 ) вычисления значений неизвестных переменных X t систем (9.1) реализуются сравнительно простыми логическими структурами. В таких структурах (рис. 132), как правило, следящие интеграторы образуют выходы схемы и од­ новременно используются в качестве делительных элементов. Несовпадающие коэффициенты, вырабатываемые для управления суммирующими ячейками, должны быть статистически незави­ симы между собой. Элементы задержки осуществляют размноже­ ние и статистическую развязку последовательностей, представля­ ющих входные величины аГг

Рис. 132. Решение системы двух линейных алгебраических уравне­ ний при ОЛС кодировании информации

Обращение матриц. В СтВМ, используемых для решения си­ стем линейных алгебраических уравнений и для реализации не­ которых алгоритмов распознающих автоматов, особое место за­ нимает метод обратной матрицы. Поясним сущность этого метода. Обозначим через

матрицу из коэффициентов системы (9.1), через

h

324

—столбец ее свободных членов и через

Хг

X 2

Х =

X т

— столбец из неизвестных. Тогда система (9.1) может быть запи­ сана в виде матричного уравнения

Если матрица А — неособенная, т. е.

то система (9.1) имеет единственное решение.

Умножая обе части равенства (9.2) на обратную матрицу, по­

Существует много методов обращения матриц: приведением исходной матрицы к произведению треугольных матриц, исполь­ зованием клеточных матриц, приближением Гаусса и т. д.; но лишь немногие из них удобны для реализации на стохастических вычислительных машинах. По-видимому, наилучшей реализуе­ мостью на СтВМ будут обладать те алгоритмы, в которых доми­ нируют операции сложения, умножения и интегрирования и со­ держится минимум операций деления. Рассмотрим два таких алгоритма.

матрица, имеет все собственные числа (нормы) меньше единицы, то существует обратная матрица [26]

Очевидно, что точность вычислений по формуле (9.4) зависит от выбранного к.

3 2 5

Пример. Обратить матрицу

I 0,5 - 0 ,2

Решение задачи начнем с определения матрицы В

Определим нормы матрицы В :

max 2 |o-ij |= max (0,7; 0,9) = 0,9 < 1 , i 1

max 2 |o-ij |= max (0,8; 0,8) = 0,8-<l>

/i

|at{ |2 = У 0,25 + 0,04 + 0,09 + 0,36 « *0 ,8 5 < 1 ,

Если принять точность вычисления коэффициентов матрицы А 1 не выше 3-го знака, то результат

2,86 1,43

2,14 3,57

будет получен после вычисления шестнадцати членов ряда (9.5). Выражение (9.5) включает лишь операции сложения и умноже­ ния и поэтому может быть реализовано при помощи набора вен­ тилей И и ИЛИ, если все коэффициенты atj представлены в виде

бернуллиевских последовательностей.

На рис. 133 показана часть устройства, реализующего зависи­ мость (9.5), а именно: схема для возведения матрицы В в квадрат. Для элементов матрицы В 2 имеем

Для представления всех входных и выходных величин в схеме на рис. 133 использованы ОЛС кодирующие устройства.

В большинстве практических случаев сумма (9.5) медленно сходится к точному результату, а это сказывается на усложнении устройства. С увеличением степени матрицы В пропорционально растет разрядность регистров сдвига, используемых для генери­ рования и статистической развязки к последовательностей а1г Так, для рассматриваемого примера, где потребовалось принять

32 6

к = 15, устройство, реализующее зависимость (9.5), помимо ло­ гических схем включает четыре пятнадцатиразрядных регистра сдвига.

В работе [19] описан другой способ реализации процесса об­ ращения матриц в соответствии с выражением (9.5), основанный на эквивалентных алфавитных преобразованиях вероятностных автоматов.

где А — независимая переменная, называют характеристической матрицей, а ее определитель

det (ХЕ — А) = Am-j- г1Ат~1 -{-. . . -f- гт _хА -\~Гт

называют характеристическим полиномом матрицы А.

Согласно теореме Гамильтона — Кели [41], каждая матрица является корнем своего характеристического многочлена, а потому

А" + М "*-1 + . . . + гт_гА + гтЕ = 0.

Умножая это равенство слева на А"1, получим

Ат-1 4- Г1Ат-2 + . . . + гт^ Е + гтА-' = 0.

3 2 7

(т — 1) включительно, то обратная матрица легко вычисляется

В данном случае необходимо определить только матрицу Л 2,

Заметим, что мы получили результат значительно быстрее, чем при решении той же задачи по методу матричных рядов. При этом требуемое количество оборудования также резко сокращается.

Многие другие задачи линейной алгебры могут быть решены путем реализации соотношения

матрицы; akUj — постоянные коэффициенты.