книги / Машинный анализ и моделирование электрических цепей

нью точности, в системе ФАПЧ устанавливаются постоянные разность фаз и выходное напряжение ФД.

Поскольку система ФАПЧ имеет бесконечное множество разнозначных состояний равновесия, различающихся по‘мгно­

венной разности	фаз синхронизируемых колебаний на величину
/2А , V ** 1,2,...	и соответствующих нормированной характери­
стике ФД F ( t p )	, фазовое пространство системы разделяется

на множество областей, топология которых описывается соот­

ношениями вида ( 18). Эти	области	периодически повторяются
с периодом, равным 2J Î	(см . рис.	4 ). Очевидно, что изобра­

жающая точка в общем случае, двигаясь последовательно до оптимальной траектории согласно уравнениям (18) при

.-,п, попадает на оптимальную линию переключения н по ней-;

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

вначало координат.

УДК 62.50

Ф.П.Воробьев, А.М.Мануйлова, А.К.Шевченко, Л.П.Доильницыиа

ПРИНЦИПЫ ПОСТРОЕНИЯ ПРОГРАММЫ МИНИМИЗАЦИИ- В ПРОСТРАНСТВЕ РЕЦЕПТОРОВ

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

121

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

В работе используются к -значные предикаты, т.е. фунт, ции произвольных аргументов, принимающие значения только из множества (0,1,2,..., Л -1 ). Далее рассматриваются преди­ каты вида

где л*£ Jiff-				S " F W .
Пусть G	-	область определения предиката				у =- F ( х ) ■
Тогда множество			G	можно разбить на к непересекающихся
подмножеств	Gf		( i = 0,J,2,...,k -I ) в соответствии			с правилом
х е Gf , вели		у	=?	F (x ) = i	(é=*û,J,...,k'f ?. Некоторые из
этих подмножеств			пустые.
Используя		к -значные			предикаты и функции	к -значной

логики, строим более сложные предикаты в пространстве ре­

цепторов	Rn . Если Fi	(Xf , Х2 , ~ , х ц ) -предикаты	( /W,
a	<P(Sj,}/z » •••’	9т } ~ ФУ1®1” ” 1 л-значной	логики,
то
Ф ( Xj ,'Х2 f ' ‘>Xfl) ~		V [ F t (Xj f “tXjf), Fg(Xf f - ,X

также является предикатом.

Для классификации объекта строим решающее правило, устанавливающее принадлежность произвольно взятой точки

(объекта) рассматриваемому подпространству	R n ( т 4 Tl).
Это правило записывается в виде предиката	P =*F(Xj,..., Хд),

принимающего значение истинности, если объект принадлежит R щ , и значение ложности в противном случае. Решающее правило ищется в виде совершенной дизъюнктивной нормальной

формы булевой функции F ( P j , Р% »**.> )* которую можно ми­ нимизировать, исходя из ее логической структуры или с помо­ щью теории графов. Поскольку процесс построения характери­ стик из элементарных операторрв в пространстве R^ аналоги­ чен движению по некоторому дереву, то перебор рецепторов

можно сократить отсечениём некоторых ветвей (без полного просмотра всех их ответвлений). Для этого находят промежу­ точные критерии отбора относительно информативных характе­ ристик, основанных на упорядочении всех характеристик объек­ та в соответствии с уменьшением показателя эффективности Щ

Определяем показатель эффективности #?--й характери­ стики

< P i = * b j + P < *> ï+ t< P Î,

где to - оценка вершины по сводному фактору условий измере­ ния (вес вершины); со - оценка параметра по фактору чувств вительности к появлению дефектов и информативности (оценка вершины по информативности); - оценка параметра по фак­ тору разделительной способности дефектов при измерении дан­ ной характеристики; * - нормированные значения соответст­ вующих оценок (например, to * = to /tomax » где а , ft, { - коэффициенты значимости указанных факторов в задачё распо­ знавания; си + fi Коэффициенты a ,f l, $ подбираем эмпирически проигрыванием рабочей модели на ЭВМ).

Методика упорядочения характеристик разработана на ба­ зе граф-модели объекта с учетом показателя эффективности Щ Вес ребра представляет собой оценку тесноты связи между двумя вершинами по парной корреляции. Вес вершины опреде­

ляется по Шеннону [\ J

ш

= 2 f i (X j,X t),

J=1 . * w

где ж - количество вершин, из которых достижима рассма­ триваемая вершина лу в рабочей граф-модели. Все расстоя­ ния между начальной вершиной лу и любой другой (достижи­ мой) вершиной должны соответствовать условию

		f i * Р к р
Здесь fixp -	критическое (пороговое) значение расстояния,
определяющее основной критерий минимизации
f i ( * j		= ( fthp *fimix> ~ fi(X jt*j*'
Для вершины	йГ/	•

где Г max - общее число распознаваемых классов; г - числп

1 2 3

классов, из комплекса первоначально нарушенных характеристик которых постижима вершина X;

Множество всевозможных реализаций алгоритма предел ляется в виде логической функции, последовательному прохо­ ждению дуг пути которой соответствует конъюнктивная связь, а параллельному - дизъюнктивная. В процессе синтеза алго­ ритма на базе графов равные подпути совмещаются, а нерав­ ные присоединяются введением дополнительных вершин граф» т.е. путем расширения графа. Назначение дополнительных вер. шин - разветвление алгоритма в соответствии со спецификой решения \задач. При направленном Обучении, когда решающее правило вырабатывается индивидуально для каждого объекта, базисной системой функций является конъюнкция признаков, соответствующих распознаваемому объекту.

Отличительная особенность этого .алгоритма заключается в применении метода перебора конъюнкций совместно с проце­ дурой предикатного описания объектов в пространстве рецелеров. Используя метод предикатного описания [ 2 J, можно весь ма эффективно осуществить аппроксимацию заданными поверх­ ностями границ областей, соответствующих распознаваемым

классам	объектов.
Рассмотрим операторное описание программы минимиза­
ции пространства		признаков.
Логическая схема программы имеет вид
W W	* Г h	( 7 > E,< S)P 7 PaP g £ ,„ (7 >£ „ lS ) A I0 A „ ,
7P12 f/3 ( tS)£pf (M )Pjf Pfg Pu Efg			(fS)A20 A2f A22
ft25	^	28 ft27 ft£6 '

Здесь П0 - оператор ввода программы; Pj - устанавли­ вает по специальному индексу требуемый класс заболеваний, соответственно которому оператор 32 производит перенос чи­ сел из определенной части операторной, памяти машины в стандартные ячейки; У^ - оператор чтения с магнитной лен­ ты нужной информации.

При одной реализации этого оператора о магнитной лен­ ты в оперативную память ЭВМ считывается информация об одном классе заболеваний. А^ определяет вид эталонной ма­ трицы, элементы которой - значения признаков для каждого

124

конкретного заболевания. Если матрица бинарная, то работает

оператор	который является оператором обращения к под­
программе	Р у

Подпрограмма Ру вычисляет количество совпавших при­ знаков f î ' = îî - f i ( S j , S f ) при сравнении объектов; f i С•S/, расстояние Хемминга между строками s ; и 5*.. Затем вычис­ ляется S $ ) ( к - постоянная величина, требующая оптимального выбора), которое описывается подпрограммой

Pg . Оператор

Рд

выделяет

/ -й

признак из

общего

набора

признаков.

. Операторы

о б р е т е н и я .^

и

£

вычисляют

f i - f t *

Gд-р (Sj ,sj. )

без /-го признака;

sjf$t —

строки матрицы, из которой удалей столбец.

J

*

Число голрсов,

поданных

у-строкЬй за

/

объектов, оп­

ределяется

по формуле

/у (к )

~

(2 )

Оператор

AJ0

вычисляет

удельное

число голосов,

подан­

ных / -строкой

за

/

объектов

О (к )

/

у г

к

(sj '

( 3)

I

I

J lj

Оператор

А^

определяет информационный вес призна­

ков по формуле из работы £Ъ]х

Р ( 0 ~ ~

2

2 ^ iÇGn-fl ( sf

( sj

? 3t

$ •

(4 )

При произвольной матрице начинает работать оператор Р%- Оператор Pjy проверяет условие

		H/j	- C f f !	< à .	(5 )
Если условие (5 ) выполняется, то с помощью оператора
Gfs (15) происходит		переход к подпрограмме			PJJ , определяю­
щей число признаков,		для которых условие (5 ) выполнилось.
Затем работает	оператор		Е ц	(10), осуществляющий переход
к подпрограмме	P J6				л - f i t s ' s	)
Подпрограмма		Pjg	вычисляет значение		2 P 1 J*	t f
где п - f i (Sj, S f ) -		общее число признаков,			удовлетворяющих
условию

		/*)• “ * > / <		cf
Оператор Pjy выделяет из общего набора признаков i-\
Признак, затэм при реализации			операторов		/■,-_( 15) и
(1 0 ) происходит обращение и подпрограммам						0PJS и	Pfg , 1
торые вычисляют	н	-*/>( $ } ,	)	и 2 Л'Ф	3}> si	)	соответ
ценно без включения		/ что признака.
Оператор Àpç		определяет	удельное число			голосов произ.
вольной матрицы	у

Оператор Agf вычисляет информационные веса по форму­

ле

Р(о=т

*j=tt*ti i

Операторы A gi > A2f осуществляют перевод получении результатов цз двоичной системы счисления в десятичную. Операторы П^з , П27 - выводят результаты на печать,* формирует команды для определения информационного веса следующих признаков| Рщ выделяет признаки с наибольшими информационными весами; /^останавливает работу программы,

3 исследованных практических задачах оптимальный на­ бор признаков включал менее половины признаков.первоначаль­ ного списка» Соответствующие программы реализованы на ЭЕМ ‘'М-222*' дли сложных динамических систем.

Литература

1. Медицинская информационная система / Под ред. Н.М.Амо­ сова. , А,А.Подова, - Киев: Наук.думка, 1975. - 506 с.

2.Рвачёр В.Л. Методы алгебры логики в математической фи­ зике, - Киёв: Наук.думка, 1974. - 258 с.

3.Журавлев Ю.И. Локальщлй алгоритм вычисления информа­ ции, - Кибернетика, 1066, № 1. с, 12-10.

УДК 518.61

В.П.Толмачев

ОБ ОДНОМ АЛГОРИТМЕ ПОСТРОЕНИЯ ИТЕРАЦИОННЫХ СХЕМ РЕШЕНИЯ КРАЕВЫХ ЗАДАЧ

В связи с развитием гибридных вычислительных систем, использующих АВМ и ЦВМ, необходимо усовершенствовать методические приемы решения краевых задач с учетом основ­ ного преимущества АВМ, заключающегося в быстродействии решения уравнения Пуассона при достаточно сложных гранич­ ных условиях [ \ ] . Общий методический прием сведения реше­ ния исходных дифференциальных уравнений достаточно общего вида к интегрированию уравнений, реализуемых на конкретном аналоговом устройстве, получил название квазианалогового моделирования [ 2 ] .

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

ласа, а в последующих -	уравнение Пуассона f Z j .
Рассмотрим дифференциальный оператор вида
^	U y s , U j f i U x > U О )

для которого в соответствии с его типом решается краевая

задача. Используя данные о начальных и граничных условиях для (1) и физические особенности рассматриваемого процесса, можно априори получить максимальное (минимальное) значе­ ние решения^ В качестве нормы, характеризующей решение, выбираем среднеарифметическое значение функции U для рас­ сматриваемой области решения в некоторой дискретной систе­ ме точек.

Представим итерационную схему интегрирования (1 ) в ви­

де

(I)Г(-Г) (('-/)

L U - A U + LU,

( 2 )

где L - лапласиан. В первом приближении решается уравнение Лапласа

а )

LU а0,

в последующих итерациях -	уравнение Пуассона
со d -o	{‘ -и
LU =AU + LU , i > J ,		(4)

гла индекс ( è- 1 ) означает, что величина'слагаемых извест­ на ИЗ предыдущей итерации. Для интегрирования (2 ) удобно использовать гибридные вычислительные средства (ГВ С ), включающие аналоговые и цифровые вычислительные машины [ \ ] . При этом интегрирование оператора L в уравнении (2) достигается использованием аналоговой части ГВС, а числен­ ное дифференцирование и вычисление алгебраических соотноше­

ний - в соответствии с операторами А , L	; сходимость
вычислений обеспечивается ЦВМ. Управление	сходимостью

итерационного процесса достигается использованием двусто­ ронних оценок решения, которые рассматриваются ниже.

Если уравнение (| ) эллиптическое, его граничные усло­ вия при интегрировании (3 ) и (4 ) используются без измене­ ния. При параболическом типе уравнения ( 1 ) ( коэффициент при % равен нулю) в качестве условий на границе выбираются начальные и граничные условия, а на оставшейся части грани­ цы полагается ЛЛ- = О . Такое граничное условие характерно для многих асимптотически протекающих физических процессов, Его можно использовать в качестве первого приближения в итерационных граничных условиях типа (10К (11). Целесооб­ разность применения граничного условия объясняется также тем, что значения решения Внутри рассматриваемой об­ ласти и на границе при проведении вычислительного процесса (4 ) корректируются от итерации к итерации. Аналогичное ус­ ловие ставится при решении (3 ), если уравнение (1 ) гипербо­ лическое.

Проинтегрировав уравнение (3 ), получаем приближенное решение уравнения ( 1 ), которое не зависит от типа рассматриэаемого исходного уравнения и учитывает только его началь­ ные и граничные условия. Норма такого решения определяете)! неравенством

йгмг <'	< V/nàx ‘	^
После подстановки решения уравнения (3 )		в правую, часть
уравнения (4 ) и i итерирования	его норма решения в эависи-
' X2 Q

мости от конкретных начальных и граничных условий изменя­ ется в сторону максимума либо минимума. Допустим, что нор­ ма решения изменилась в сторону U щцх Тогда искомое решение находится в интервале

Uj < 11иск < Umax •

Рассмотрим более подробно процесс получения искомого реше­ ния, Вычислим правую^часть (4) с ‘учетом решения уравнения

(3) и обозначим ее ( х , у ) . После решения уравнения

(2)п)

LU	« (f	(7 )
может возникнуть ситуация,	А л	Такое условие
	когда Ü2 > и тах

соответствует нарушению физического смысла рассматривае­ мой задачи и приводит к расходимости итерационного процес­ са (2). Поэтому для обеспечения сходимости вычислительного процесса вместо соотношения (7 ) целесообразно использовать соотношение

		(2)	а> а )	(8)
		L U	- * < ? ,
значение коэОДициеита		у в котором выбирается таким,		чтобы
после решения ( 8 )	выполнялось неравенство U2 < $ т х , Такой
выбор коэффициента	Ф	обеспечивает сходимость вычислитель­

ного процесса, т.е. сжимаемость дифференциального оператора Л 7 . Полученное значение у ф является верхней границей изменения правой части ( 2 ) при последующих итерациях, а ве­

личина cpifsm соответствующая искомому решению,	находит­
ся в интервале
/ у 9 ! > ! Ч и с т !? ° ‘	(9)

Сходимость вычислений в интервале (9 ) обеспечивается одним из многочисленных способов построения итерационной процедуры вычислений /"57, Искомое решение определяется следующим условием: разница значений норм решения двух по­ следовательных итераций должна быть меньше некоторой за­ данной величины, определяющей точность вычислений. Следует отметить, что от итерации к итерации значение V изменяется И определяет скорость сходимости вычислений.

Приведенный подход к управлению сходимостью процесса

решения не связан с анализом собственных значений матриц. Это не позволяет, заблаговременно выбрать наилучшую страте­ гию изменения коэффициента у и предполагает использование для его определения информации о решении, получаемом в каж­ дой итерации, т.е. используются апостериорные оценки реше­ ния [ А ] .

Подобны й характер вычислений предпочтителен при реше­ нии однотипных задач, так как позволяет накопить опыт о значениях У в каждой итерации и использовать его для уве­ личения скорости получения решения. При отсутствии такого опыта выбирают соответствующий алгоритм изменения у ко­ торый обеспечивает монотонное стремление решения от перво­ го приближения (решения уравнения (3 )) к-искомому. Реали­ зация итерационного способа ( 2 ) особенно удобна при диалоге оператор - машина, когда информация о. решении выводится на дисплей, с помощью которого можно следить за изменени­ ем, сходимости вычислений и вводить ускоряющие ее значения параметра У в ЦВМ.

После интегрирования (4 ) полученное решение является для уравнений эллиптического типа окончательным, а для урав­ нений параболического и гиперболического типов необходима корректировка граничного условия для участка границы, соот­ ветствующего рассматриваемому моменту времени. Для урав­ нений параболического типа вместо условия ^ - = 0 использу­ ется итерационное граничное условие, которыьг является исход­

ное	уравнение	( 1)	следующего вида:
		» )					( 10)
	ÉJL		(i 4)/ д 2й		dü
	*9
а для уравнений гиперболического типа
	£ . Н №			, S L , É L , в ,ч ) м ,			( и )
	ау	/	ч л г		ал ' а/	у/
где	В, Л - операторы,			получаемые		после разделения	( 1)' отно­
сительно производных					, 4 ^	соответственно.	Сходимость

итерационного процесса обеспечивается также введением в пра­ вую часть уравнений ( 10), ( 11) определенного коэффициента, с помощью которого достигается соответствующее управление сходимостью вычислений. Следует отметить, что после коррек­ тировки граничных условий решение изменится и потребуется