5.9.2, ДОКАЗАТЕЛЬСТВО СХОДИМОСТИ

Покажем теперь, что если выборки линейно разделяемы и 0<р < <1, то процедура Хо — Кашьяпа будет давать вектор решения за конечное число шагов. Чтобы сделать алгоритм конечным, следовало бы добавить правило остановки, по которому процесс коррекций прекратится сразу же, как будет найден вектор решения. Однако более удобно считать процесс коррекций непрерывным и показать, что вектор ошибки е* либо становится нулевым при некотором конечном k, либо сходится к нулевому при k-*-oo.

Очевидно, что либо е*=0 при некотором к, скажем при k^,, либо в последовательности е*, . . . не содержится нулевых векторов. В первом случае, как только нулевой вектор получен, ни один из векторов а^, или е^ больше не изменяется и Kaft=b*>0 для всех k^kn. Таким образом, при получении нулевого вектора ошибки алгоритм автоматически останавливается, и мы имеем вектор решения.

Предположим теперь, что никогда не станет нулевым при конечном к. Чтобы показать, что тем не менее должно сходиться к нулю, сначала поставим вопрос, возможно ли получение с неположительными компонентами. Указанное обстоятельство должно быть наиболее нежелательным, поскольку требуется, чтобы выполнялось условие Faft^bfe, и поскольку е* должно быть нулевым, чтобы прекратилось дальнейшее изменение а^, Ь^ или е^. К счастью, данная ситуация может никогда не возникнуть, если выборки линейно разделяемы. Доказательство просто и основано на том факте, что если К*Уа^=К*Ьй, то У‘е*=0. Однако в случае линейно разделяемых выборок существуют такие а и 6>0, что справедливо соотношение

Таким образом,

и поскольку все компоненты вектора Ь положительны, то либо 6^= =0, либо по крайней мере одна из компонент должна быть положительна. Поскольку случай е^=0 исключен, из этого следует, что

может не быть нулем при конечном к.

Для доказательства того, что вектор ошибки всегда сходится к нулю, используется тот факт, что матрица УУ+ симметрична, положительно полуопределена и удовлетворяет соотношению

Хотя эти результаты справедливы и в общем случае, для простоты рассмотрим их только для невырожденной матрицы У*У. В этом случае УУі= У (У‘У)-1У‘, и симметричность очевидна. Поскольку матрица Y^Y является положительно определенной, то сущест-

вует матрица  таким образом, Ь*У (У*У)~‘ У*Ь>0 при лю

бом Ь, и матрица УУ+ является по крайней мере положительно по- луопределенной. Итак, соотношение (66) вытекает из следующего:

Чтобы показать, что должно сходиться к нулю, исключим из (63)—(65) и получим следующее выражение:

Затем, используя (62), получим рекуррентную формулу так что

Как второй, так и третий члены значительно упрощаются. Поскольку е*У=0, второй член представляется в виде

ненулевые компоненты вектора t% являются положительными компонентами вектора е^. Поскольку матрица УК+ симметрична и равна произведению (УУ+)‘ (УК+), третий член упростится до следующего выражения:

Таким образом,

Поскольку предполагается, что вектор ненулевой и матрица УУ+ является положительной полуопределенной, то||еь||'*>||е*+іІР, если 0<р<1. Таким образом, последовательность ||еі|Р, ЦегІР, . . • будет монотонно убывающей и должна сходиться к некоторому предельному значению ||е|р. Однако в случае рассматриваемой сходимости должно сходиться к нулю, так что все положительные компоненты ел должны сходиться к нулю. И поскольку е*Ь= =0 для всех k, отсюда следует, что все компоненты вектора должны сходиться к нулю. Таким образом, при условии, что Ос <р<1 и выборки линейно разделяемы, а* будет сходиться к вектору решения при k, стремящемся к бесконечности.

Если на каждом шаге проверяются знаки компонент вектора Уа^ и алгоритм останавливается при условии, что они положительны,

то фактически получаем разделяющий вектор в случае конечного числа шагов. Это следует из тогофак^а, что Yau=bk+^h и что компоненты вектора никогда не убывают. Таким образом, если fcmin является наименьшей компонентой вектора Ьі и если сходится к нулю, то вектор должен попасть в гиперсферу ||eft||=bmin после конечного числа шагов, при котором Уа^^О. Хотя в целях упрощения доказательства условия остановки были исключены, указанное условие должно всегда применяться на практике.