5.6.2. ДОКАЗАТЕЛЬСТВО СХОДИМОСТИ

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

ничено, TD будет показано, что а^ сходится к предельному вектору, лежащему на границе области решений. Поскольку область, в которой  включена в большую область, где а*у>0 при й>0, это означает, что а^ войдет в эту большую область по меньшей мере один раз, в конечном счете оставаясь в этой области при всех к, больших некоторого конечного к^.

Доказательство связано с тем фактом, что если а представляет собой любой вектор, лежащий в области решений, т. е. удовлетворяющий условию   при всех і, то с каждым шагом вектор приближается к вектору а. Данное утверждение сразу же следует из соотношения (28), поскольку

и

так что

Поскольку р изменяется в интервале 0<Ср<;2, из этого вытекает, что Ца^і+і—аІКЦа^—а||. Таким образом, векторы последовательности аі, аг, . . . все более приближаются к а, и в пределе, когда к стремится к бесконечности, величина расстояния Па^ — а|| будет близка к некоторому предельному значению г (а). Отсюда следует, что при стремлении к к бесконечности а^ располагается на поверхности гиперсферы с центром а и радиусом г (а). Поскольку данное утверждение справедливо для любого а, находящегося в области решений, предельное а^ лежит на пересечении гиперсфер, центрами которых являются все возможные векторы решений.

Покажем, что общим пересечением данных гиперсфер является единственная точка, лежащая на границе области решений. Предположим сначала, что существуют по крайней мере две точки а' и а", принадлежащие общему пересечению. Тогда выполняется равенство Ца'—а1|=||а"—a|| для каждого а, находящегося в области решений. Но это означает, что область решений располагается в (d—1)-мерной гиперплоскости, содержащей точки, равноудаленные от а' и а", тогда как известно, что область решений является d-мер- ной. (Точная формулировка такова: если а*уг>0 при і=1, . . . , и, то для любого d-мерного вектора ѵ справедливым будет выражение (а+еѵ) * уг>0 для г=1, . . . , п при условии, что е достаточно мало.) Таким образом, а^ сходится к единственной точке а. Указанная точка, конечно, не находится внутри области решений, ибо тогда после-

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