Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
Из (6.60) и (6.64) с учетом (6.62) и (6.63) легко получить выражение для А1":
AU) = UAwy,-fQU)/fQm. (6.66)
Исходя из (6.61) и (6.62) можно утверждать, что по крайней мере для ненулевых значений X0 спектры собственных значений матриц GhL совпадают. Т.е. если в спектре матрицы G собственное значение X0 является старшим по модулю, то это же значение будет старшим по модулю в спектре собственных значений матрицы L. И тогда из (6.66) легко установить, что
LAU)=X0AU), (6.67)
т.е. при t оо вектор А(п стремится принимать направление собственного вектора матрицы L, соответствующего ее старшему собственному значению
157
ГЛАВА 5Из (6.65) и (6.66) легко установить, что при t —» °°
Qu+i) = KfQu JawQ0K (6.68)
A0+,) = KfА, J0U^A0K (6.69)
Из основного определения коэффициента корреляции нетрудно убедиться в справедливости
IiklX, к2у) = r(x, >)sgn(Ar, Ar2). (6.70)
Из (6.59), (6.68) и (6.70) с учетом положительности всех /получим
?('+i)=?('> Sgn(X0), (6.71)
АМ = АМ sgnix01 (6.72)
т.е. при / —» оо векторы Qt'1 и Ato сходятся не только по направлению, но и по модулю. Так, если A0 > 0, то имеет место
?('+l)=?('\ (6.73)
Л<'+|,=Л(0, (6.74)
если же <- O1 XO имеют место
?('+l)=-?(0, (6.75)
Л('+|)=-Л(0. (6.76)
Из (6.68) и (6.69) с учетом (6.71) и (6.72) можно заключить также, что при достаточно больших t имеет место
IfifoIMioI=IX0I. (6.77)
Замена в процессе (5.62) операции обычного умножения матриц на их /^-произведение делает этот процесс более корректным, что, естественно, приводит к заметному повышению функциональной эффективности АСДП, по крайней мере, в начальных тактах ее функционирования. Вместе с тем, процесс (6.59) также, как и процесс (5.62), "грешит" забвением при достаточно больших значениях t первоначально сформулированного пользователем запроса, т.е. вектора ?<0). Это приводит к тому, что повышение качества поиска наблюдается лишь в первых нескольких тактах функционирования АСДП, после чего дальнейшее продолжение процесса (6.59) приводит к резкому ухудшению качества поиска. В рассматриваемом смысле представляет интерес Л-аналог
158процесса (5.69), а именно, процесс A(0) = c,?(0)
o(D = crM(0)+o(0) л"> = C*?(l)
?u+n = ст* А{,) + Qm
Отсюда следует
Л<°> = HcCSQw Zeiw
= HcCSQ^fgin Q^ = HrrC7SA^f Q
.(0)
Л
,((I)
(6.78)
Qm = HctCt SAw fAW)+Qw A(l) = HcCSQi^fgw (6.79)
Пользуясь введенными выше обозначениями, получим:
?(,)=Y,(X G"ly,_p)Qm. (6.80) ,,=0
Из (6.61) и (6.62) следуют
HcCSGp = LpHcCS, (6.81)
HctCtLp =GpHctCtS, (6.81а) с учетом которых из (6.79) и (6.80) легко получить:
= Yr X (6.82)
р=0
Из сопоставления (6.80) и (6.64) легко обнаружить, что в отличие от процесса (6.59), в процессе (6.78), благодаря наличию слагаемого Q{{)), вектор Qln зависит от вектора 2<()) при произвольных сколь угодно больших значениях Л
159
ГЛАВА 5Пусть для некоторого значения t = имело место
?('"+1) = ?<4 (6.83) Очевидно, это повлекло бы
л"<>+1) = (6.83а)
и далее
?l'"+/,) = Qi'"'', (6.84)
Л<">+",=Л('", (6.84а)
для любого р = О, 1,2,... Из (6.79) следует, что
?u+i,_?,„=(G/?()/^_1)?(M + ?(0,; (6 85)
Л(,+,) - Л(,) =(LfAU)fQU+[} - 1)Л(,) + HcCSfqM)Q{0\ (6.86)
т.е. соблюдение условия (6.83) повлекло бы:
fQmfA
(1-GZnl41, Д(ч„)б,",)=б(0), (6.87)
(I - ^„„Z^,. M''"' = HcCSf^Qm. (6.88)
Но для того, чтобы существовали Qi'" ' и Ai'"', необходимо и достаточно, чтобы матрицы (I-GZ1ih1Ziw,)) и (1 - Lf {I{)JaW ) были обратимы, т.е. чтобы все собственные значения матриц G vi L удовлетворяли условию:
If(6.89)
При соблюдении же этого условия, введя обозначения
Q = Qi'<)+!>) р = 0,1,2,..., (6.90)
Л = а('"+р) р = 0,1,2,..., (6.91)
получим
Q = O-GZgZJ-1Gw, (6.92)
A=(]-LfQfAy]HcCSfeQi0). (6.93)
Если для всего спектра собственных значений матриц G vi L соблюдено условие
IMZgZ4CI. (6.94)
то матрицы (I-GZ0Z4)"' и O- AZgZ* )"' можно представить в виде
160соответствующих бесконечных сумм, т.е. из (6.92) и (6 93) будем иметь [5]:
Q
( OO Л
X (GfofA)" К /'=O
Q<0), (6.95)
A =
X Шо/л)1'
в
у,,=O
\
(O)
HcCSf0Qw. (6.96)
Таким образом, если процесс (6.79) сходится к паре векторов Q и А, то они могут быть найдены с помощью (6.92) и (6.93). Если к тому же имеет место (6.94), то формулы (6.92) и (6.93) можно переписать в виде (6.95) и (6.96).
Если сравнивать процессы (6.59) и (6.78), то легко обнаружить, что по сравнению с (6.59) процесс (6.78) носит более "консервативный" характер, который обусловлен слагаемым Qw в выражении
?(O = CrM(/-l)+?(0)
Из-за наличия этого слагаемого на каждом этапе отображения вектора А(,_|) на множество терминов фактор "изменчивости", обусловленный слагаемым СТ*А(,~'\ "отягощается", затушевывается присутствием слагаемого ?(()), учитывающего фактор преемственности. От этого недостатка свободен процесс (6.59), где слагаемое Q<()) отсутствует. Но отсутствие Q(0> приводит к тому, что процесс в целом оказывается во власти среды и поэтому после нескольких первых тактов работы полностью "забывает" о векторе Qim и векторы Qin и А(,) принимают собственные направления матриц GwL, т.е. становятся выразителями свойств среды, "забывая" о существовании пользовательского запроса Q({)\