5.3.4. Доказательство сходимости НСКО-алгоритма

В данном разделе доказывается сходимость НСКО-алгоритма при линейной разделимости заданных классов и корректирующем приращении, удовлетворяющем условию Ключевым моментом обоснования сходимости является доказательство того факта, что вектор ошибки в пределе обращается в . Поскольку из определения алгоритма (5.3.23) следует, что у начального вектора все компоненты положительны и значения этих компонент не уменьшаются, то очевидно, что если при некотором значении имеет место то , т. е. получено решение уравнения (5.3.13).

На основании соотношений (5.3.23) записываем

Поскольку, однако, последнее уравнение можно переписать как

Отсюда следует, что

Используя соотношения , получаем

Из последнего в свою очередь получаем

Запись (5.3.27) можно упростить, введя обозначение

В таком случае (5.3.27) принимает вид

Это уравнение можно существенно упростить. Обратим, прежде всего, внимание на то, что Следовательно,

Матрица симметрическая, значит, . Следовательно, (5.3.29) принимает вид

Так как, однако, , то

Поскольку матрица симметрическая и последний член в (5.3.31) можно представить как

Подстановка этого соотношения в (5.3.31) дает следующее:

Это уравнение позволяет доказать сходимость алгоритма при наличии разделимости заданных классов. Прежде всего, отмечая, что матрица — положительно полуопределенная, получаем Следовательно, при правая часть уравнения (5.3.32) больше или равна нулю. Значит,

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

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

так как все компоненты вектора положительны. Итак,

где обоснованием последнего преобразования является тот факт, что если существует. Условия, при которых такая обратная матрица существует, были рассмотрены в п. 5.3.3.

Если , то Поскольку, однако, должно также выполняться и равенство . Последнее противоречит условию (5.3.34). Следовательно, вектор ошибки при наличии разделимости классов не может быть таким, что все его компоненты неположительны. Это означает, что появление неположительного вектора ошибок является ясным указанием невозможности линейного разделения заданных классов.

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

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

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

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