ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2014, том 54, № 9, с. 1448-1454
УДК 519.658
АЛГОРИТМЫ ПРОЕКТИРОВАНИЯ ТОЧКИ НА ПОВЕРХНОСТЬ УРОВНЯ НЕПРЕРЫВНОЙ НА КОМПАКТЕ ФУНКЦИИ
© 2014 г. Н. К. Арутюнова, А. М. Дуллиев, В. И. Заботин
(420111 Казань, ул. К. Маркса, 10, КНИТУим. А.Н. Туполева (КАИ)) e-mail: arut_natalie@mail.ru, dulliev@yandex.ru, v.zabotin@rambler.ru Поступила в редакцию 10.11.2013 г.
Рассматривается задача нахождения ближайшего к заданной точке решения уравнения f(x) = 0. В отличие от предыдущих работ, посвященных данной проблеме, предлагаются точные алгоритмы при условии непрерывности функции f на компакте, обосновывается их сходимость. Работа алгоритмов иллюстрируется на тестовых примерах. Библ. 8. Табл. 2.
Ключевые слова: s-липшицевость, проектирование точки на поверхность уровня, невыпуклое множество, решение нелинейного уравнения.
DOI: 10.7868/S0044466914090038
ВВЕДЕНИЕ
Пусть C — компакт, расположенный в нормированном пространстве E. В зависимости от строения множества C выделяют различные типы задач проектирования точки на C. Среди наиболее распространенных можно отметить задачи, в которых множество C является выпуклым или же конструируется каким-либо образом из конечного числа заданных выпуклых множеств, например, с помощью операций пересечения множеств, взятия выпуклой оболочки (см., например, [1]—[3]) и т.п. Вместе с тем очевидно, что множество C не всегда удается выразить через выпуклые множества и даже в тех случаях, когда это возможно, поиск проекций на эти выпуклые множества может вызывать серьезные затруднения. Разумеется, задачу проектирования точки на множество С можно попытаться свести к последовательности задач, в каждой из которых множество C аппроксимировано более простым множеством Ck (см. [4]). Однако и здесь нет гарантии, что структура Ck при больших k будет намного проще, чем C. Из невыпуклых множеств, на которые удается спроектировать заданную точку, можно особо выделить множества, определяемые с помощью функциональных ограничений, и, прежде всего, множества вида C = {x е A :f(x) = 0}, где A с E — некоторый выпуклый компакт. Соответствующие методы, как правило, различаются по принадлежности функции f тому или иному классу. Если f является достаточно гладкой, то применимы методы ньютоновского типа (см. [5]); при липшицевости, гёльдеровости или некоторых обобщениях этих свойств функции f возможно использование, например, методов, предложенных в [6], [7]. В настоящей статье рассматриваются два метода решения задачи проектирования на классе s-липшицевых функций. При этом, в отличие от [7], предлагаемые методы являются точными.
Следуя [8], функциюf, определенную на A, будем называть е-липшицевой, если она удовлетворяет условию
Vs > 0 З Де) > 0 Vx, y е A : f (x) - f(y)\ < Де) ||x - y\\ + 6. (1)
Из [8] известно, что е-липшицевыми являются, например, непрерывные на компакте функции, поэтому ниже будем предполагать непрерывность f на множестве A.
Пусть точка a е A такова, что f(a) > 0 и X* = {x е A : f(x) = 0} Ф 0. Через intB и дВ обозначим внутренность и границу множества В соответственно.
Прежде, чем перейти к непосредственному описанию предлагаемых алгоритмов отыскания ближайшего к точке a е A решения уравнения
f (x) = 0, (2)
приведем некоторые вспомогательные результаты.
1. НЕКОТОРЫЕ ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ Всюду далее полагаем, что
ее (0,f(a)). (3)
Ясно, что множество чисел L(s) из (1) не ограничено сверху для каждого фиксированного s из (3). Обозначим это множество через {L(s)}.
Для каждого фиксированного s е (0, /(a)) введем обозначение
/(е) = inf{L(e)}. (4)
Лемма 1. Для любого s е (0, /(a)) имеет место неравенство
/(б) > 0, /(б) е {Z(s>}.
Доказательство. Пусть s е (0,/(a)) таков, что l(s) < 0. Тогда из определения l(s) следует, что для любого 8 > 0 найдется L е {L(s)} такая, что L < l(s) + 8, т.е. l(s) + 8 е {L(s)}, а значит, для всех x, y е A имеет место неравенство
If(x) - f (У) < (/(s) + S)||x - y|| + s. Положим x = a, y е X*. Тогда имеем
f (a) < (/(e) + S)||a - y|| + s. В силу произвольности 8 > 0 получаем
f (a) < /(e) |\a - y|| + e < 6,
что противоречит условию (3).
Из аналогичных рассуждений следует, что
/(е) е {Де».
Для доказательства достаточно зафиксировать точки x0, y0 е A и вновь, как и выше, для произвольного 8 > 0 убедиться в справедливости неравенства
f (xo) - f (Уо) < (/(е) + 8)|xo - Уо\\ + е, после чего остается воспользоваться произвольностью 8 > 0 и точек x0, y0 е A.
Назовем константу L(s) достижимой, если она удовлетворяет условию (1) и найдутся x0, y0 е A, x0 Ф y0 такие, что
|f (xo) - f (Уо) = L(s)|xo - Уо|| + e. (5)
Лемма 2. Оценка l(s) достижима при любом фиксированном s е (0,/(a)). Если L(s) достижима, то L(s) = l(s).
Доказательство. Докажем первую часть леммы от противного. Предположим, что Vx,y е A : 9(x,y) = |f (x) - f(y)\ - /(s)|x - y\\ - e < 0. Тогда, в силу непрерывности 9(x, y) на A x A, имеем
max 9(x, y) < 0.
x,y
Подберем 8 > 0 так, чтобы выполнялись условия 8 < l(s) и
max 9(x, y) < -8diamA.
x,y
Тогда для любых x, y е A имеем
|f(x) - f (y) - W\\x - y\\ - s < -SdiamA < -^|x - y||, т.е. для любых x, y е A получаем
If (x) - f (y)| < (/(6) -5)||x - y + s, откуда следует, что l(s) — 8 е {L(s)}, что противоречит определению l(s). Таким образом, мы доказали, что l(s) есть достижимая константа.
Для обоснования второй части леммы заметим, что если l(s) Ф L(s), то l(s) < L(s), и, в силу (5), имеем
|f (x0) - f(y0) > /(е)||x0 - y0| + S,
чего быть не может.
Отметим некоторые свойства l(s):
1°. /(е) строго возрастает при е, монотонно стремящемся к нулю.
Доказательство. В силу леммы 2, можем предположить, что для некоторого е е (0, /(а)) нашлись точки хЕ, уе е А такие, что хЕ Ф уе и
/(хе) -/Се) = №1 хЕ - уЕ|| + 6.
Пусть е1 < е, тогда
|/(ХЕ) - / У) ^ /(Е1^| ХЕ - У Л + 6Ь
т.е.
(/(6) + /(Е1))|| ХЕ - УЕ\\ <61 -6< 0,
что и требовалось.
2°. Если /(е) ограничена на (0,/(а)) сверху, то/ — липшицева.
Доказательство. Пусть Ь = 8ир{/(е) : е е (0,/(а))}. В силу леммы 1, очевидно, что Ь > 0. Тогда для любого е е (0,/(а)) и любых точек х, у е А имеем
/(х) - /(У)| < Цх - у\\ + 6. В силу произвола е е (0, /(а)) неравенство сохранится:
|/(х) - /(у) < Цх - у|1, ^х, у 6 А,
т.е. / — липшицева.
Таким образом, мы показали, что если / не является е-липшицевой, то
/(б) Т при б ^ 0.
2. ОПИСАНИЕ МЕТОДОВ
2.1. Предлагаемый алгоритм 1 имеет в основе идею, схожую с алгоритмом 2 из [7] (далее, алгоритм З—А), но здесь сходимость к множеству нулей функции достигается путем пересчета на каждой итерации значения параметра s в зависимости от текущего значения функции. Кроме того, использование оценки (4) позволяет на каждой итерации удалиться от начальной точки на максимально возможное расстояние, а также обеспечивает вышеуказанную точность алгоритма.
Предположение. В данном алгоритме в силу свойства 2° будем полагать, что f не является лип-шицевой.
Алгоритм 1
Шаг 0. Задать начальную точку x0 = a е A и значение параметра алгоритма X е (0; 1); установить к := 0.
Шаг 1. Вычислить sk = Xf(xk), соответствующую оценку l(sk) (см. (4)) и величину
= Ä) (1 -х). k l(sk)
Шаг 2. Определить хк + 1, как любую из точек множества
arg min{f (x): x e dKk n A}, (6)
где
Kk = jx :||x - a\\ < j.
Шаг 3. Если f(xk+1) = 0, то хк+1 берется в качестве решения задачи (2). Иначе, принять к := к + 1 и перейти к шагу 1.
2.2. Предлагаемый ниже алгоритм 2 для решения задачи (2) является обобщением метода, рассмотренного в [6], модификация которого — алгоритм З—А — используется в алгоритме 2 в качестве вспомогательной процедуры. Обобщение основано на следующих соображениях. Как следует из предложений 4 и 5 из [7], алгоритм З—А не гарантирует сходимости к множеству нулей функцииf(x). С его помощью можно лишь попасть в некоторую полосу Xe = {х е A : 0 <f(x) < s}. Ясно, что для поиска нуля f(x) достаточно построить последовательность точек из областей XE, полученных уменьшением s до нуля. Это можно осуществить, если каждый раз, начиная с одной и той же начальной точки, находить с помощью алгоритма З—А очередное приближение к Хг.
Но можно поступить иначе: последовательно запускать алгоритм З—А с новой начальной точкой, в качестве которой выбирать найденное приближение на предыдущей итерации. Как будет показано в предложениях 5—6 и продемонстрировано в численных примерах, данный подход обеспечивает сходимость к множеству X*. Более того, предложение 6 показывает, что алгоритм на самом деле позволяет находить проекцию на это множество.
Алгоритм 2
Шаг 0. Выбрать е0 > 0, начальную точку х0 = а е А и задать произвольным образом параметры у, X е (0; 1). Положить у0 := х0, к := 0, т := 0.
Шаг 1. Если/(хк) < ек, то принять ек + 1 := Х/(хк); если ек </(хк) < ек(1 + у), то принять ек + 1 :=Хек. В обоих случаях последовательно установить хк + 1 := хк; ут + 1 := хк, т := т + 1 и перейти к шагу 3. В противном случае перейти к шагу 2.
Шаг 2. Если/(хк) > ек(1 + у), то найти хк + 1 по схеме, предложенной в алгоритме З—А:
Г к 1
„ _ /(■Хк) - 6 к
L(s к )
Kk = jx e E ! ! x - 4 < X Г | ' Gk = Kk ^ A
i=0
Xk+1 = arg min {f (x) : x e dKk n A}. Далее положить sk + 1 := sk и перейти к шагу 3.
Шаг 3. Еслиf(xk + 1 ) = 0 илиf(ym) = 0, то xk+1 или ym соответственно — решение задачи (2). Иначе, установить k := k + 1 и перейти к шагу 1.
3. ОБОСНОВАНИЕ СХОДИМОСТИ МЕТОДОВ 3.1. Вначале рассмотрим вопрос о сходимости алгоритма 1. Предложение 1. Если x e intKk n A, то f(x) > 0.
Доказательство. Аналогично [6], [7] проведем его по индукции. При k = 0 положим y e intK0 n A, тогда
f(y) ^ f(4) - /(s o)|| y - 4 - e о = Го /(sq) - /(s o)|| y - а|| = l(so)(>o -1| У - 41) > 0, поскольку, в силу леммы 1, /(s0) > 0.
Пусть теперь на intKk имеет место f(x) > 0.
1. Если найдется y e dKk n A такое, чтоf(y) = 0, то y можно будет взять в качестве xk + ь но тогда rk + 1 = 0 и, значит, Kk + 1 = Kk, т.е. на intKk + 1 n A имеет место неравенствоf(x) > 0.
2. Если же для любого y e dKk n A имеет место f(y) > 0, то достаточно показать, что f строго положительна на (intKk + 1\Kk) n
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.