Нахождение минимумов двумерных функций при компенсации областей отрицательности плотности вероятностей

Лёзин И.А. , Лёзина И.В.

НАХОЖДЕНИЕ МИНИМУМОВ ДВУМЕРНЫХ ФУНКЦИЙ ПРИ КОМПЕНСАЦИИ ОБЛАСТЕЙ ОТРИЦАТЕЛЬНОСТИ ПЛОТНОСТИ ВЕРОЯТНОСТЕЙ

В статье рассматривается проблема нахождения экстремумов функций двух переменных, являющихся произведением полинома и положительно определенной функции, через вычисление их производных и решение систем двух полиномиальных уравнений произвольной степени с двумя неизвестными. Для решения системы предлагается подход, основанный на нахождении базиса Грёбнера и нахождения корней системы через решение системы уравнений, составленных полиномами из вычисленного базиса. Базис Грёбнера находится с помощью нового предложенного алгоритма, ускоренного относительно классического алгоритма Бухбергера. Для решения полученных полиномиальных уравнений произвольной степени с одним неизвестным предлагается численный метод Дюрана-Кернера.

При нахождении аппроксимирующих выражений для двумерных функций плотности вероятностей в ортогональных базисах Лежандра, Чебышёва, Лагерра и Эрмита, аппроксимирующее выражение представлено в общем виде следующим образом:

N М

У

п = 0 т=0

где упт - коэффициенты мономов, а Фх (х) Фу ( У ) - некоторые положительно определенные функции.

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

* М ,

/ \ / у

ё (ту) = 22 уПт) х" ут=0

п= 0 т= 0 N М'

(у),

к (ху) = 22 тту) хпут = °-

п=0 т=0

Системы полиномиальных уравнений в общем случае решаются построением базиса Грёбнера из базиса, составленного многочленами рассматриваемой системы, и решением системы уравнений, левые части которых являются многочленами, составляющими базис Грёбнера. Одними из самых широко распространенных методов для построения базиса Грёбнера являются алгоритм Бухбергера и алгоритм Фужера Е5. Однако оба способа при относительной простоте выполняемых преобразований обладают очень высокой операционной сложностью, что затрудняет, а зачастую и делает невозможным из-за слишком высоких требований к операционным ресурсам, вычисление базиса для систем вида (2) высокой степени.

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

Итак, пусть К - поле вещественных чисел, К [х,у] - кольцо многочленов от двух переменных с коэф-

фициентами из К . Рассмотрим некоторый идеал I над кольцом многочленов, в который входят полиномы из системы (2). Множество является базисом идеала I . Зададим лексикографическое упорядоче-

ние мономов в многочленах:

тРхуРу > т4худу т

"У ' Чу)

Используя операции сложения и умножения над многочленами, входящими в базис Н , требуется редуцировать его так, чтобы построить базис Грёбнера идеала I .

Введем понятие S-полинома:

г\ - ЬСМ(У’УЬ ЬСМУ’У) ,

ьт (У) представляет старший терм многочлена У (т, у ) , а ЬСМ (у, у ) равен наименьшему моному, который делится на старшие мономы многочленов Л (т у) и Ъ (X у) • Операцией редуцирования произвольного

полинома Л

, который выражается в виде:

У

і

где а (х,у) є К[х,у] и Уі (х,у)є Н .

Базис Н можно назвать базисом Грёбнера, если для любых двух полиномов Л(X у ) и У ( x, у ) из Н выполняется условие:

$

При заданном лексикографическом упорядочении (3) базис Грёбнера будет составлен парой многочленов, удовлетворяющих условию (6), вида:

М-х Мху

у, ( х, у )=2*П Х)хп+24ту) ут,

п=1 т=0

Му

Уу (т, у ) = 2 к{ту) ут

т=0

Множество решений системы, составленной из полиномов (7), будет соответствовать множеству решений системы (2).

Алгоритм нахождения базиса Грёбнера представлен в виде блок-схемы (Рисунок 1) .

На вход алгоритма редукции подается базис Н идеала I , составленный из множества полиномов системы уравнений (2).

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

Рисунок 1 - Блок-схема алгоритма редукции системы уравнений

Если такой полином найден, то он исключается из базиса и находится остаток г (х, у) от редукции

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

остаток г(х,у) положить равным исходному редуцируемому полиному / (х,у) , то на каждом шаге уменьшения остатка проводится поиск максимального полинома / (х,у) в множестве Н , который может редуцировать остаток г(х,у) , и проводится редукция:

ЬСМ

г

где ЬС (г) - коэффициент перед старшим мономом многочлена г (х,у) .

Редуцирование по формуле (8) следует продолжать до тех пор, пока остаток г(х,у) не станет нереду-цируемым. Когда редуцирование завершено и если остаток г (х, у) не является нулевым полиномом, то он добавляется в базис Н .

Перед добавлением остатка в базис требуется провести корректировку коэффициентов для г(х,у) . В кольце К[х,у] необходимо найти такие многочлены а (х,у) , аЛ/(х,у) , а г(х,у) и акг (х,у) , чтобы можно было представить полиномы 8(х,у) и к(х,у) в базисе Н + {г} :

8 (x, у) = 2 ag,  (x, у) /< (x, у)+ag, г (x, у)г (x, у),

'

к (x, у) = 2 ак, < (у) /1 (у)+ак г (у)г (у ) I

Если решение системы (9) не находится, это значит, что при вычислениях в значениях коэффициентов остатка накопилась методическая погрешность, вызванная способом представления вещественных чисел в памяти ЭВМ. Так как уже имеющиеся в базисе полиномы имеют правильные значения коэффициентов, в таком

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

Сначала определяются значения коэффициентов для полиномов а / (х,у) и ан у (х,у) . Затем вычисляются разности:

гв (л, у) = ё (л, у) - Е ав, і (лУ) ^ (лУ)= ав, г (лУ)г (лУ)’

гн

і

Если разности представляют собой нулевые полиномы, то одну или несколько базисных функций /

добавляется в базис Н , и алгоритм редуцирования базиса идет на очередную итерацию.

По второй ветви алгоритм редуцирования базиса развивается, если в базисе Н не найден полином, который может быть редуцирован. В таком случае набор базисных функций должен быть расширен для продолжения редукции. Из всех возможных пар полиномов базиса /(л, у) и / (л, У) , для которых не выполняется условие (6), нужно найти пару с минимальным ьсм (/і, ^ ) .

Если такая пара найдена, то редуцированный остаток Б-полинома этой пары включается в базис Н , предварительно пройдя корректировку коэффициентов, как это было описано ранее.

Если же такой пары многочленов в базисе Н нет, то этот базис полностью редуцирован и является базисом Грёбнера.

Таким образом, алгоритм на выходе вернет базис, составленный из пары многочленов (7). Теперь для решения исходной системы нужно вычислить все корни у. полиномиального уравнения одной переменной

/ (л,у) = 0 вида (11), подставить по очереди эти значения в многочлен /л (л,у) , превращая его в полином

одной переменной, и рассчитать соответствующие корни хг- • уравнения

Мх’Уі)=°

Е = 0

т=0

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

Согласно теореме Абеля-Руффини, уравнение вида (11) при степени Муу >4 неразрешимо в радикалах, то есть для такого уравнения невозможно указать закрытую формулу для решений, содержащую только

арифметические операции и корни произвольной степени. Полином произвольного вида степени 5 , применяя преобразования Чирнхауса, можно привести к нормальной форме Бринга-Жерара в терминах разрешимых полиномиальных уравнений, при этом используются полиномиальные преобразования, включающие выражения в корнях не выше четвёртой степени. Эта процедура порождает лишние решения, но если отсечь их численными методами, то получим выражение для корней уравнения пятой степени через квадратные, кубические корни и радикалы Бринга. Однако для многочленов более высоких степеней не существует аналитических способов определения всех корней.

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

Для этого необходимо представить полином из уравнения (11) в нормированном виде:

г/ \ Мт ^Муу-1 щ-\ 4 ^

/

к

кМуу кМуу

Полином вида (12) имеет А/ комплексных корней ут , поэтому может быть представлен как произведение:

Муу

1{У) = ШУ-Ут)

т=1

Для запуска алгоритма необходимо задать начальные комплексные значения корней уравнения, например:

Уш)=

Уточнение корней уравнения на очередном шаге к проводится по следующей формуле:

/

пМы,)п М1-")

у(к) _ у(к !)-----------------------------;---------/-----------------

Ут Ут , М ^ 1

I=1 I=т+1

Когда требуемая точность будет достигнута, алгоритм следует остановить и отбросить все комплексные корни, оставив только вещественные значения у( . Эти значения по очереди подставляются в уравне-

/л (л У ) = 0 :

Мл Млу

+ о

Эти уравнения, как правило, являются линейными, поэтому не составляет труда найти соответствующие корни х- . Таким образом, мы получаем набор точек {ху,^} , подозрительных на экстремум. Их дальнейший анализ позволяет определить, в каких точках функция (1) принимает отрицательные значения.

Литература

1. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. В 3 т. Т. I / Пред. и прим. А.А. Флоринского. - 8-е изд. - М.: ФИЗМАТЛИТ, 2003.

2. Buchberger B. Grobner Bases: an Algorithmic Method in Polynomial Ideal Theory. In Recent

trends in multidimensional system theory, Reidel, Ed. Bose, 1985.

3. Durand, E. "Equations du type F(x) = 0: Racines d'un polynome". Solutions numeriques des equations algebriques, vol. 1. 1960.

4. Faugere, J.-C. (July 2002). "A new efficient algorithm for computing Grobner bases without reduction to zero (F5)". Proceedings of the 2002 international symposium on Symbolic and algebraic computation (ISSAC) (ACM Press).