On a numerical estimation method with a given accuracy of a quantile criterion in the case of a piece-linear loss function and a gaussian probability density

Full Text

Введение. Решение многих практических задач приводит к вычислению значений вероятностных критериев. Наиболее распространенными вероятностными критериями качества технических систем при случайных воздействиях являются функционалы квантили [1] и вероятности. Квантильный критерий может характеризовать точность системы управления при случайных возмущениях [1], гарантированную площадь взлетно-посадочной полосы, на которую летательный аппарат садится с заданной вероятностью в условиях ветровых помех [2] и т.д. Функционал вероятности характеризует обычно вероятность выполнения условий рассматриваемой задачи.

Как установлено в [1], при достаточно общих предположениях методы, пригодные для решения задач нахождения значений вероятностного критерия, могут быть использованы для решения задачи квантильного анализа.

Во многих случаях нахождение значения вероятностного критерия сводится к вычислению многомерного интеграла от плотности вероятности некоторого случайного вектора по заданному множеству, что представляет собой сложную вычислительную задачу [1]. Применение традиционных методов решения этой задачи (см., например, [3–5]), таких, как прямое интегрирование плотности вероятности или метод Монте-Карло, при высоких требованиях к точности получаемого результата приводит к недопустимо большим вычислительным затратам.

Таким образом, нахождение значения вероятностного критерия, а также решение задачи квантильного анализа упирается в разработку численных методов многомерного интегрирования с любой желаемой точностью. Понятно, что размерность n решаемой задачи будет невелика. Автором был проведен численный эксперимент при $n=5$. В случае когда подынтегральная функция является плотностью нормального распределения, множеством интегрирования является многогранник, заданный несколькими линейными ограничениями (количество линейных ограничений в используемом методе не имеет большого значения), приближенное значение интеграла $\tilde{I}=0.785685556863937$ было вычислено с абсолютной погрешностью $\delta =0.000498\dots$ (см. ниже пример 1). Соответственно, относительная погрешность составила 0.0634%. При этом применялся численный метод интегрирования, описанный в работах [6–9], являющийся универсальным в том смысле, что мы можем задавать произвольное количество переменных n и произвольное количество линейных ограничений r, но при этом при больших n время счета может оказаться неприемлемо большим.

Задача многомерного интегрирования с заданной точностью рассматривалась и в других публикациях, в частности в работе [12], в которой предлагаются методы, не обладающие указанным свойством универсальности. Например, случай, когда множеством интегрирования является многогранник, описан в [12] для максимального значения $n=3$, а в случае эллипсоида – для $n=2$. Между тем в [6] (см. табл. 1, 2 из этой работы), приводятся результаты численного эксперимента для эллипсоида при $n=3$ (а сам метод универсален для любого n).

Предлагаемый в этой статье метод решения задачи квантильного анализа основан на применении метода численного многомерного интегрирования, описанного в [6–9], использующего последовательное k-этапное дробление исходного “внешнего” (для заданного подынтегрального множества) куба на кубы, получаемые последовательным делением ребер кубов пополам. Краткое описание этого метода приводится в разд. 1. В разд. 2 представлены основные определения и используемые в настоящей работе обозначения, связанные с функцией квантили. В разд. 3 приводятся некоторые вспомогательные методы и алгоритмы, связанные с рассматриваемым в этой работе кусочно-линейным случаем для целевой функции. В разд. 4 предлагается алгоритм вычисления с заданной точностью функции квантили, основанный на алгоритме вычисления многомерного интеграла с помощью последовательного k-этапного дробления исходного “внешнего” куба. Приводится его обоснование, а также весьма оптимистическая оценка для основного параметра алгоритма – k, т.е. количества этапов дробления, необходимого для достижения требуемой точности вычисления $\epsilon >0$. В зависимости от использования модификации алгоритма интегрирования (см. разд. 1) эта оценка имеет вид $k\le C_1-0.5{\log }_2\epsilon$ (с помощью 1-го наиболее простого метода интегрирования) или $k\le C_2-\left({\log }_2\epsilon \right)/3$ (с помощью 2-го более сложного метода интегрирования), где $C_1\mathrm{,}$ $C_2$ – некоторые константы (которые можно приблизительно оценить уже в самом начале процесса вычислений). Замечательно, что в этих оценках не присутствует число n – размерность задачи. Для получения этих оценок применялось геометрическое неравенство (4.6). В разд. 5 описываются некоторые свойства выпуклых многогранников, необходимые для обоснования этого неравенства.

1. Численный метод многомерного интегрирования с заданной точностью в случае кусочно-линейной функции потерь и гауссовской плотности вероятности. Укажем лишь общие идеи метода, который будем далее называть а л г о р и т м о м 1. Все необходимые детали можно найти в работах [6–9]. Рассматривается задача приближенного вычисления с заданной точностью интеграла:

$I={\int }_X{\phi }_n\left(x\right)dx,$ (1.1)

где ${\phi }_n\left(x\right)={\left(2\pi \right)}^{-n/2}{e}^{-{\left|x\right|}^2/2}$, $\left|x\right|={(x_1^2+\dots +x_n^2)}^{1/2}$,

 $X=\left\{x\in \Pi \left|l_1\right.\left(x\right)\le \mathrm{0,}\dots ,l_r\left(x\right)\le 0\right\},\mathrm{int}X\ne \varnothing ,$

$l_i\left(x\right)=⟨e^i,x⟩+d_i,e^i\in {ℝ}^n,d_i\in ℝ,\left|e^i\right|\ne \mathrm{0,}i=\overline{\mathrm{1,}r},$ (1.2)

$\Pi =\left\{x\in {ℝ}^n\left|a\le x_i\le b,i=\overline{\mathrm{1,}n}\right.\right\},a<b.$ (1.3)

Этот метод использует некоторые идеи метода ветвей и границ, применяемого в алгоритмах дискретной оптимизации (см., например, [10]).

В замечании 2 из [6] говорится о том, что куб $\Pi$ может иметь более общий вид $\Pi =\left\{x\in {ℝ}^n\left|a_i\le x_i\le b_i,i=\overline{\mathrm{1,}n}\right.\right\}$, т.е. являться n-мерным координатным параллелепипедом (будем кубы или параллелепипеды, заданные указанным образом, называть координатными). Однако программная реализация предлагаемого в [6–9] метода оказывается наиболее экономичной (см., например, [6, С. 57]) в случае (1.3). Действительно, в этом случае можно заранее создать одномерный массив Ф(a,b,k) значений функции

$\Phi \left(y\right)=\frac{1}{\sqrt{2\pi }}{\int }_{-\infty }^y{e}^{-t^2/2}dt,$ (1.4)

где $y\in ℝ$, на равномерной сетке $S(a,b,k)=\left\{y\in ℝ\left|y=s_i(a,b,k)\triangleq a+i(b-a)2^{-k},i=\overline{{\mathrm{0,2}}^k}\right.\right\}$ (т.е. $Ф(a,b,k)=\left\{Ф\left(s_i\right(a,b,k\left)\right), i=\overline{0,2^k}\right\}$), и тогда многие вспомогательные задачи интегрирования будут решаться путем выбора соответствующих элементов из этого массива и совершения над ними арифметических действий (умножения, сложения и т.д.).

Алгоритм 1 основан на многоэтапном дроблении куба $\Pi$. Для этого выбирается k – количество этапов дробления. Точность приближенного вычисления интеграла (1.1) непосредственно зависит от величины количества этапов дробления k. Обозначим через $\tilde{I}$ – приближенное значение интеграла (1.1), вычисляемое с помощью алгоритма 1, $\delta$ – достигаемая при выбранном k точность вычисления, при этом после окончания работы алгоритма для приближенного значения интеграла выполняется

$\tilde{I}\le I\le \tilde{I}+\delta \mathrm{.}$ (1.5)

Сначала присваиваем $\tilde{I}=0$, $\delta =0$ и дробим исходный куб $\Pi$ на $2^n$ кубов (делением ребер куба $\Pi$ пополам), которые назовем кубами первого этапа дробления (соответственно, кубы, являющиеся элементами аналогичного дробления кубов первого этапа дробления, назовем кубами второго этапа дробления и т.д.). На каждом этапе $j=\overline{\mathrm{1,}k}$ перебираем кубы Q j-го этапа дробления и проверяем выполнение условия “погружения”:

$Q\subseteq X\mathrm{.}$ (1.6)

Если (1.6) справедливо, то полагаем $\tilde{I}:=\tilde{I}+I_Q$, где

$I_Q={\int }_Q{\phi }_n\left(x\right)dx,$

и исключаем куб Q из дальнейшего рассмотрения. В нашем случае с линейными ограничениями проверка условия (1.6) осуществляется точно и достаточно экономично (см. [9. С. 1114–1115]) и в случае (1.6) вычисление интеграла $I_Q$ осуществляется за $O\left(n\right)$ арифметических операций с использованием заготовленного массива Ф(a,b,k) (см. [9, С. 1114]). В противном случае проверяем выполнение условия “отсечения”:

$X\cap \mathrm{int}Q=\varnothing .$ (1.7)

Если (1.7) справедливо, то исключаем куб Q из дальнейшего рассмотрения и переходим к очередному кубу j-го этапа дробления (см. ниже замечание 1); если все кубы j-го этапа дробления исчерпаны, то переходим к очередному кубу Q $(j-1)$-го этапа дробления (пока еще $j-1\ge 1$) и т.д. Если же все кубы первого этапа дробления исчерпаны, то конец работы алгоритма.

Если для очередного куба Q (некоторого j-го этапа дробления) не выполняется ни условие погружения (1.6), ни условие отсечения (1.7), то осуществляем дальнейшее дробление этого куба, а в случае $j=k$ полагаем

$\delta :=\delta +I_Q.$ (1.8)

Нетрудно показать (см. утверждение 1 из [7, С. 45]), что одновременное невыполнение условий погружения (1.6) и отсечения (1.7) для некоторого координатного куба $Q\subseteq \Pi$ равносильно тому, что $\partial X\cap \mathrm{int}Q\ne \varnothing$, где $\partial X$ – граница множества $X$.

После выполнения алгоритма справедливо равенство

$\delta =\sum _{\partial X\cap \mathrm{int}Q\ne \varnothing }{\int }_Q{\phi }_n\left(x\right)dx$ (1.9)

(здесь суммирование осуществляется по всем кубам Q k-го (т.е. последнего) этапа дробления, для которых не выполняется ни условие отсечения, ни условие погружения).

З а м е ч а н и е 1. В [8, 9] трудоемкая проверка условия отсечения (1.7) заменена на достаточное для (1.7) гораздо менее трудоемкое условие (см. условие (3.4) из [9]).

З а м е ч а н и е 2. В приведенном описании алгоритма 1 даны лишь общие идеи и опущены технические детали, позволяющие модифицировать этот алгоритм для уменьшения погрешности $\delta$. Например, в [8, 9] формула присвоения (1.8) уточняется. Для этого вычисляются верхняя и нижняя оценки для величины

$I_{Q\cap X}={\int }_{Q\cap X}{\phi }_n\left(x\right)dx$

и вместо $I_Q$ к $\delta$ прибавляется разность между верхней и нижней оценками. Одновременно с этим нижняя оценка прибавляется к $\tilde{I}$. В [8, 9] приведены две модификации для приближенного вычисления $I_{Q\cap X}$ с разными порядками точности. Пусть $\tau =T/2^{k+1}$, где $T=b-a$ – длина ребер куба $\Pi$, т.е. $\tau$ – половина длины ребер кубов k-го (последнего) этапа дробления куба $\Pi$. В первой модификации для результирующего значения $\delta$ выполняется $\delta =O\left({\tau }^2\right)$при $\tau \to 0+$ (метод второго порядка точности), а во второй гораздо более сложной модификации $\delta =O\left({\tau }^3\right)$ при $\tau \to 0+$ (метод третьего порядка точности). Первая модификация была реализована на компьютере (см. ниже пример 1, из которого видно, что при увеличении k на единицу (соответственно, при уменьшении $\tau$ в 2 раза) $\delta$ уменьшается приблизительно в 4 раза.

З а м е ч а н и е 3. Для уменьшения времени работы алгоритма возможно распараллеливание. Например, всякий раз при дроблении любого куба $\left(k-1\right)$-го этапа дробления на кубы k-го этапа дробления можно параллельно решать $2^n$ подзадач (для каждого куба Q k-го этапа дробления) проверки выполнения условий (1.6), (1.7) и в случае невыполнения этих условий – вычисления верхней и нижней оценок для $I_{Q\cap X}$ (см. замечание 2). Можно провести распараллеливание по-другому принципу: параллельно вычислять значения интегралов $I_{Q\cap X}$ для $2^n$ кубов Q первого этапа дробления с последующим сложением результатов, т.е. приближенных значений интегралов. Используя равенство (1.9), нетрудно показать, что при этом сумма погрешностей при вычислении интегралов $I_{Q\cap X}$ даст точную погрешность в случае вычисления без распараллеливания всего интеграла I. Такие распараллеливания могут значительно уменьшить общее время счета.

З а м е ч а н и е 4. Поскольку множество  ограничено, то, решая соответствующие задачи линейного программирования (ЗЛП), можно определить $a_i=\min \left\{x_i\left|x\in \Pi ,l_j\left(x\right)\le \mathrm{0,}j=\overline{\mathrm{1,}r}\right.\right\}$, $b_i=\max \left\{x_i\left|x\in \Pi ,l_j\left(x\right)\le \mathrm{0,}j=\overline{\mathrm{1,}r}\right.\right\}$, $i=\overline{\mathrm{1,}n}$ и тем самым сузить куб $\Pi$ до параллелепипеда ${\Pi }_0=\left\{x\in {ℝ}^n\left|a_i\le x_i\le b_i,i=\overline{\mathrm{1,}n}\right.\right\}$, где $a\le a_i$, $b_i\le b$, $i=\overline{\mathrm{1,}n},$ и при этом $X\subseteq {\Pi }_0\subseteq \Pi$, откуда $X=X\cap {\Pi }_0=\left\{x\in {\Pi }_0\left|l_j\left(x\right)\le \mathrm{0,}j=\overline{\mathrm{1,}r}\right.\right\}$. Более того, можно считать, что числа $a_i$, $b_i$ являются узлами сетки $S(a,b,k)$ (наиболее близкими к точным их значениям), поскольку при любых ${\tilde{a}}_i\in \left[a,a_i\right]$, ${\tilde{b}}_i\in \left[b_i\mathrm{,}b\right]$, $i=\overline{\mathrm{1,}n}$, очевидно, снова выполняется $X\subseteq {\tilde{\Pi }}_0\subseteq \Pi$, где ${\tilde{\Pi }}_0=\left\{x\in {ℝ}^n\left|{\tilde{a}}_i\le x_i\le {\tilde{b}}_i,i=\overline{\mathrm{1,}n}\right.\right\}$, откуда $X=X\cap {\tilde{\Pi }}_0=\left\{x\in {\tilde{\Pi }}_0\left|l_j\left(x\right)\le \mathrm{0,}j=\overline{\mathrm{1,}r}\right.\right\}$. Тогда, следуя [8], алгоритм 1 можно модифицировать следующим образом. Снова последовательно дробим куб $\Pi$. Но теперь для каждого текущего куба  перед проверкой условий (1.6), (1.7) проверяем выполнение условия ${\Pi }_0\cap \mathrm{int}Q=\varnothing$ (осуществляется за $O\left(n\right)$ арифметических операций). Если это условие верно, то исключим Q из дальнейшего рассмотрения и перейдем к анализу очередного куба. В противном случае действуем согласно алгоритму 1. Такая модификация позволит за незначительное время отсечь “лишние” области в кубе $\Pi$ по сравнению с параллелепипедом ${\Pi }_0$. Кроме того, условие погружения (1.6) можно теперь ослабить, заменив его на $Q\cap {\Pi }_0\subseteq X$ (проверяется аналогично (1.6)), в случае выполнения которого присваиваем $\tilde{I}:=\tilde{I}+I_{Q\cap {\Pi }_0}$, где

$I_{Q\cap {\Pi }_0}={\int }_{Q\cap {\Pi }_0}{\phi }_n\left(x\right)dx.$

При этом $Q\cap {\Pi }_0$ – координатный параллелепипед, координаты вершин которого являются элементами сетки S(a,b,k). Но тогда значение интеграла $I_{Q\cap {\Pi }_0}$ легко вычисляется, используя элементы массива Ф(a,b,k). Аналогичным образом можно ослабить и условие отсечения, заменяя в нем Q на $Q\cap {\Pi }_0$.

З а м е ч а н и е 5. Отметим, что процесс нахождения величины $\tilde{I}$, удовлетворяющей (1.5) для заданного $\delta >0$, является, вообще говоря, многошаговым. Нам редко удастся сразу “угадать” требуемое количество этапов дробления k. Начинаем с некоторого $k=k_0\ge 2$, а затем увеличиваем значение k до достижения (1.5) для заданного $\delta$. При этом следует отметить три момента. Во-первых, при увеличении k на 1 можно снова использовать Ф(a,b,k), поскольку $S\left(a\mathrm{,}b\mathrm{,}k\right)\subset S(a\mathrm{,}b\mathrm{,}k+1)$, $Ф(a,b,k)\subset Ф(a,b,k + 1)$ (в Ф(a,b,k + 1) помимо элементов из Ф(a,b,k) войдут значения функции $\Phi \left(y\right)$ в серединах отрезков, соединяющих каждые из двух последовательных членов из S(a,b,k)). Во-вторых, применив алгоритм 1 при некотором начальном $k=k_0\ge 2$, можно в процессе работы этого алгоритма определять для всякого куба Q (любого этапа дробления), для которого было выполнено условие погружения (1.6), а также для всех кубов последнего k-го этапа дробления, для которых не было выполнено условие отсечения (1.7) (объединение указанных кубов покрывает $X$), минимальный номер $j_{\min }\left(k_0\right)\in \left\{\overline{{\mathrm{1,2}}^{k_0}+1}\right\}$ и максимальный номер $j_{\max }\left(k_0\right)\in \left\{\overline{{\mathrm{1,2}}^{k_0}+1}\right\}$ элементов сетки $S(a,b,k)$, являющихся координатами вершин этих кубов. Обозначим $\tilde{a}\left(k_0\right)=s_{j_{\min }\left(k_0\right)}(a,b,k_0)$, $\tilde{b}\left(k_0\right)=s_{j_{\max }\left(k_0\right)}(a,b,k_0)$. Тогда выполняется включение $X\subseteq \tilde{\Pi }\left(k_0\right)=\left\{x\in {ℝ}^n\left|\tilde{a}\left(k_0\right)\le x_i\le \tilde{b}\left(k_0\right),i=\overline{\mathrm{1,}n}\right.\right\}.$ Таким образом, в случае применения алгоритма 1 для $k=k_0+1$ можно теперь в качестве куба $\Pi$ взять куб $\tilde{\Pi }\left(k_0\right)$ (при этом $\tilde{\Pi }\left(k_0\right)\subseteq \Pi$). Более того, следуя замечанию 4, можно в процессе работы алгоритма 1 для тех же кубов определять по каждой координате $x_i$ минимальный $j_{\min }^{\left(i\right)}\left(k_0\right)\in \left\{\overline{{\mathrm{1,2}}^{k_0}+1}\right\}$ и максимальный $j_{\max }^{\left(i\right)}\left(k_0\right)\in \left\{\overline{{\mathrm{1,2}}^{k_0}+1}\right\}$ номера элементов сетки S(a,b,k), являющихся координатами вершин этих кубов. Обозначим ${\tilde{a}}_i\left(k_0\right)=s_{j_{\min }^{\left(i\right)}\left(k_0\right)}(a,b,k_0)$, ${\tilde{b}}_i\left(k_0\right)=s_{j_{\max }^{\left(i\right)}\left(k_0\right)}(a,b,k_0)$, $i=\overline{\mathrm{1,}n}$. Тогда верно включение $X\subseteq {\tilde{\Pi }}_0\left(k_0\right)=\left\{x\in {ℝ}^n\left|{\tilde{a}}_i\left(k_0\right)\le x_i\le {\tilde{b}}_i\left(k_0\right),i=\overline{\mathrm{1,}n}\right.\right\}$. Таким образом, при выполнении алгоритма 1 при $k\ge k_0+1$ можем теперь применить модификацию этого алгоритма в соответствии с замечанием 4 (минуя необходимость дополнительного решения указанных в этом замечании ЗЛП). В-третьих, может также возникнуть следующая ситуация, которую поясним на примере. Предположим, что $k_0=6$ и соответственно в сетке S(a,b,k₀) содержится $2^{k_0}+1=65$ элементов. Пусть в результате работы алгоритма 1 при $k=k_0=6$ оказалось, что $j_{\min }\left(k_0\right)=11$, $j_{\max }\left(k_0\right)=26$, т.е. имеем, $26-11+1=16$ “активных” членов сетки S(a,b,k₀). Это указывает на то, что полученные значения $\tilde{I}$, $\delta$ в результате применения алгоритма 1 при количестве этапов дробления $k=k_0=6$ к рассматриваемой задаче с использованием куба $\Pi$, удовлетворяющего (1.3), дают одинаковый результат, если бы вместо куба $\Pi$ применялся куб $\tilde{\Pi }=\left\{x\in {ℝ}^n\left|s_{11}(a,b,k_0)\le x_i\le s_{27}(a,b,k_0),i=\overline{\mathrm{1,}n}\right.\right\}$ (здесь $27=11+2^4$, 4 – минимальный показатель степени l, при котором $11+2^l\ge 26$), при количестве этапов дробления $k={\tilde{k}}_0=4$ (вместо $k=k_0=6$). В связи с этим в этом примере можно для дальнейшего уменьшения $\delta$использовать алгоритм 1, применяя $\tilde{\Pi }$ вместо $\Pi$ при количестве этапов дробления ${\tilde{k}}_0+1=5$вместо $k_0+1=7$, что может дать существенное сокращение объема вычислений. Здесь используется простое утверждение, заключающееся в том, что значения величин $\tilde{I}, \delta$, однозначно определяются множеством кубов последнего этапа дробления, для которых либо верно условие погружения (в том числе, в случае его выполнения для некоторого куба меньшего этапа дробления, в котором он содержится), либо в случае одновременного невыполнения ни условия погружения, ни условия отсечения. В приведенном примере в обоих рассматриваемых случаях множества этих кубов совпадают (несмотря на отличие в максимальном количестве этапов дробления в каждом из этих случаев).

П р и м е р 1. Автором была составлена программа для вычисления интеграла I вида (1.1) для случая, когда $X$ – многогранник, реализующая метод второго порядка точности. Рассматривался пример, когда $n=5$,

$X=\{x\in \Pi |x_1+x_2-x_3-x_4-x_5-7\le \mathrm{0,}2x_1-x_2+2x_3-x_4+2x_5-8\le \mathrm{0,}$

$\begin{array}{c}{x}_1-x_2+2x_3-x_4+2x_5-9\le \mathrm{0,}2x_1+x_2-x_3+x_4-x_5-7\le 0\},\\ \Pi =\{x\in R^5|-2\le x_i\le \mathrm{2,}i=\overline{\mathrm{1,5}}\},\end{array}$

т.е. при $r=4.$ Результаты вычислений величин $\tilde{I},\tilde{I}+\delta ,\delta ,$ удовлетворяющих (1.5), приведены в табл. 1 при различных $k=\mathrm{4,5,6.}$ Из этой таблицы видно, что погрешность $\delta$ уменьшается примерно в 4 раза при каждом увеличении k на 1.

Таблица 1

2. Функция квантили. Пусть

$F\left(t\right)=P_t=P\left(\Psi \left(\xi \right)\le t\right)=\underset{\Psi \left(x\right)\le t}{}f\left(x\right)dx,$

где $t\in ℝ$, $\text{{}x\in {ℝ}^n\text{|\hspace{0.33em}}\Psi x\le t\ne \varnothing$, $\Psi \left(x\right)$ – целевая функция, например кусочно-линейная (как всюду в этой статье), квадратичная (как в статье [8]) или возможны другие случаи, $f\left(x\right)$ – плотность вероятности вектора случайных факторов $\xi$, а следовательно $\forall x\in {ℝ}^n$, $fx\ge 0$. В этой статье всюду в дальнейшем $f\left(x\right)={\phi }_n\left(x\right)$.

Обозначим $X\left(t\right)=\{x\in {ℝ}^n|\Psi \left(x\right)\le t\}$. Функцией квантили (quantile function) называется функция

$q\left(\alpha \right)=\inf \left\{t\right|P_t\ge \alpha \}=\inf \left\{t\left|{\int }_{\Psi \left(x\right)\le t}f\left(x\right)dx\ge \alpha \right.\right\}=\inf \left\{t\left|{\int }_{X\left(t\right)}f\left(x\right)dx\right.\ge \alpha \right\}.$

В сделанных обозначениях

$F\left(t\right)={\int }_{X\left(t\right)}f\left(x\right)dx.$

Тогда $q\left(\alpha \right)=\inf \left\{t\left|F\left(t\right)\ge \alpha \right.\right\}$, где $\alpha \in \left(\mathrm{0,}1\right)$ – заданная доверительная вероятность. Предполагается, что $F\left(t\right)$ – непрерывная функция при всех $t\in ℝ$, таких, что $X\left(t\right)\ne \varnothing$ (в рассматриваемом кусочно-линейном случае с ограниченными множествами $X\left(t\right),t\in ℝ$ это условие очевидным образом выполняется). В любом случае $\forall t_0\in ℝ\mathrm{,}$ такого, что $X\left(t_0\right)\ne \varnothing$, для любых $t,t^{\text{'}}\ge t_0$ справедливо $t^{\text{'}}\ge t\Rightarrow X\left(t^{\text{'}}\right)\supseteq X\left(t\right)\Rightarrow F\left(t^{\text{'}}\right)\ge F\left(t\right)$.

Таким образом, в рассматриваемом случае функция $F\left(t\right)$ монотонно не убывает и непрерывна при $t\ge t_0$ (где $t_0$ – любое число, такое, что $X\left(t_0\right)\ne \varnothing$), а следовательно, в случае, если

$\exists t_1,{\overline{t}}_1\in ℝ:t_1<{\overline{t}}_1,X\left({\overline{t}}_1\right)\ne \varnothing ,F\left(t_1\right)<\alpha ,F\left({\overline{t}}_1\right)\ge \alpha ,$ (2.1)

верно

$q\left(\alpha \right)=\inf \left\{t\left|F\left(t\right)\ge \alpha \right.\right\}=\min \left\{t\in \left[t_1,{\overline{t}}_1\right]\left|F\left(t\right)=\alpha \right.\right\}$ (2.2)

(здесь и далее знак $\min$ перед некоторым множеством действительных чисел означает минимальный элемент в нем и соответственно $\inf$ – точную нижнюю грань на этом множестве).

3. Кусочно-линейный случай. В настоящей работе исследуется случай, когда

$\Psi \left(x\right)=\max \left\{l_1\left(x\right),\dots ,l_r\left(x\right)\right\}$ (где $l_1\left(x\right),\dots ,l_r\left(x\right)$ удовлетворяют (1.2)). Для произвольного измеримого (по Лебегу) множества $Y\subseteq {ℝ}^n$ будем его меру обозначать через $\mu \left(Y\right)$. Пусть для некоторого $t_0\in ℝ$ $X\left(t_0\right)=\{x\in {ℝ}^n|\Psi \left(x\right)\le t_0\}$ – ограниченное непустое множество. Тогда (см. теорему 17, С. 177 из [11]) $\forall t\in ℝ$ $X\left(t\right)$ – ограниченное множество и $\exists t_1\in ℝ:t_1=\min \Psi \left(X\left(t_0\right)\right)=\min \Psi \left({ℝ}^n\right)$, поскольку $X\left(t_0\right)$ – компакт. При этом, очевидно, $\mathrm{int}X\left(t_1\right)=\varnothing \Rightarrow \mu \left(X\left(t_1\right)\right)=0$, откуда $F\left(t_1\right)=0<\alpha$, а следовательно, $q\left(\alpha \right)=\inf \left\{t\left|F\left(t\right)\ge \alpha \right.\right\}>t_1$, т.е. величина $t_1$ дает нижнюю границу для $q\left(\alpha \right)$ и может быть найдена, решая задачу линейного программирования:

$v\to \min \left(=t_1\right),l_i\left(x\right)\le v,i=\overline{\mathrm{1,}r},x\in {ℝ}^n,v\in ℝ$ (3.1)

(в (3.1) и ниже в аналогичных случаях выражение $v\to \min \left(=t_1\right)$ означает, что в рассматриваемой задаче ищется значение минимума функции  при указанных ограничениях и при этом в скобках дается обозначение для искомого значения минимума).

Заметим, что в кусочно-линейном случае с ограниченным множеством $X\left(t_1\right)$ функция $F\left(t\right)$непрерывна и монотонно возрастает. Это следует из рассмотрения монотонно возрастающей непрерывной функции $\mu \left(X\left(t\right)\right)$ (нетрудно даже показать, что она удовлетворяет условию Липшица).

Опишем также метод определения верхней границы для $q\left(\alpha \right)$. Пусть имеется программа вычисления функции $\Phi \left(y\right)$, где $y\in ℝ$, по формуле (1.4). Рассмотрим задачу поиска $b\in ℝ$:

$b>\mathrm{0,}\beta \left(b\right)={\left(2\pi \right)}^{-1/2}\underset{-b}{\overset{b}{}}{e}^{-t^2/2}dt=\Phi \left(b\right)-\Phi \left(-b\right)={\alpha }^{1/n}.$ (3.2)

Пусть ${\Pi }_0=\{x\in {ℝ}^n|-b\le x_i\le b,i=\overline{\mathrm{1,}n}\}$. Тогда

${\int }_{{\Pi }_0}{\phi }_n\left(x\right)dx=\prod _{i=1}^n\left[\Phi \right(b)-\Phi (-b\left)\right]=\alpha .$

Поскольку функция $\beta \left(y\right)$ является монотонно возрастающей всюду на ${ℝ}_{\ge }=\{t\in ℝ|t\ge 0\}$, то величину $\beta \left(b\right)$, удовлетворяющую (3.2), можно определить со сколь угодной точностью $\sigma >0$, т.е. вычислить $b_{\sigma }\in ℝ:b\le b_{\sigma }\le b+\sigma$. При этом $\beta \left(b_{\sigma }\right)\ge {\alpha }^{1/n}$. Пусть ${\Pi }_{\sigma }=\{x\in {ℝ}^n|-b_{\sigma }\le x_i\le b_{\sigma },i=\overline{\mathrm{1,}n}\}$, где $\sigma >0$ – произвольное небольшое число (например, $\sigma =0.01$). Тогда

$\underset{{\Pi }_{\sigma }}{}{\phi }_n\left(x\right)dx=\underset{i=1}{\overset{n}{}}\left[\Phi \left(b_{\sigma }\right)-\Phi \left(-b_{\sigma }\right)\right]={\left[\beta \right(b_{\sigma }\left)\right]}^n\ge \alpha .$

Рассмотрим для каждого $i=\overline{\mathrm{1,}r}$ задачу

$l_i\left(x\right)=⟨e^i,x⟩+d_i\to \max (={\gamma }_i),x\in {\Pi }_{\sigma }.$

Каждая из этих задач решается точно за $O\left(n\right)$ арифметических операций (см. аналогичную задачу в [9, С. 1113]). Тогда для величины ${\overline{t}}_1=\max \{{\gamma }_1,\dots ,{\gamma }_r\}$ выполняется $X\left({\overline{t}}_1\right)=\left\{x\in {ℝ}^n\left|\Psi \left(x\right)\le {\overline{t}}_1\right.\right\}\supseteq {\Pi }_{\sigma }$, а следовательно,

$F\left({\overline{t}}_1\right)=\underset{X\left({\overline{t}}_1\right)}{}{\phi }_n\left(x\right)dx\ge \underset{{\Pi }_{\sigma }}{}{\phi }_n\left(x\right)dx\ge \alpha ,$

т.е. величина ${\overline{t}}_1$ является верхней оценкой для $q\left(a\right)$. Таким образом,

$t_1<q\left(\alpha \right)\le {\overline{t}}_1.$ (3.3)

Кроме того, для работы алгоритма многомерного интегрирования функции ${\phi }_n\left(x\right)$ на многогранниках $X\left(t\right)$, где $t\in \left(t_1\mathrm{,}{\overline{t}}_1\right]\mathrm{,}$ понадобится (см. разд. 2) куб $\Pi$ вида (1.3), такой, что $X\left({\overline{t}}_1\right)\subseteq \Pi$. Для нахождения чисел $a$, b из (1.3) достаточно решить $2n$ задач линейного программирования

$x_i\to \max \left(={\eta }_i\right),x\in X\left({\overline{t}}_1\right),$ (3.4)

$x_i\to \min \left(={\nu }_i\right),x\in X\left({\overline{t}}_1\right),$ (3.5)

а затем положить $a=\min \{{\nu }_1,\dots ,{\nu }_n\}$, $b=\max \{{\eta }_1,\dots ,{\eta }_n\}$.

З а м е ч а н и е 6. В процессе работы приводимого ниже алгоритма 2 величина $q\left(\alpha \right)$ будет оценена сверху и снизу гораздо более точно, чем в (3.3), и тогда мы можем уточнить величины a, b заменяя в (3.4), (3.5) величину ${\overline{t}}_1$ на новую гораздо более точную оценку сверху величины $q\left(\alpha \right)$. Такие уточнения можно производить периодически (см. далее замечание 7).

4. Численный метод нахождения с заданной точностью $q\left(\alpha \right)$. Опишем алгоритм 2 нахождения с заданной точностью $\epsilon >0$ величины $q\left(\alpha \right)$, основанный на использовании алгоритма 1. Шаги алгоритма 2 вполне очевидны (в частности, сходны с соответствующим алгоритмом в [12]) и не претендуют на новизну. Для автора важным было показать возможность применения в этом алгоритме универсального (относительно размерности n) алгоритма 1 и тем самым придать алгоритму 2 ту же универсальность. В разд. 3 величина $q\left(\alpha \right)$ была уже оценена сверху и снизу (см. неравенства (3.3)). Кроме того, в разд. 3 был описан алгоритм нахождения куба $\Pi$ вида (1.3) такого, что $\forall t\in \left(t_1,{\overline{t}}_1\right]X\left(t\right)\subseteq \Pi$, а следовательно, $\forall t\in \left(t_1,{\overline{t}}_1\right]X\left(t\right)=\left\{x\in {ℝ}^n\left|\Psi \left(x\right)\le t\right.\right\}=\left\{x\in \Pi \left|\Psi \left(x\right)\le t\right.\right\}$. Но тогда $\forall t\in \left(t_1\mathrm{,}{\overline{t}}_1\right]$ ($t>t_1$, чтобы $\mathrm{int}X\left(t\right)\ne \varnothing$) интеграл

$F\left(t\right)={\int }_{X\left(t\right)}{\phi }_n\left(x\right)dx$

является интегралом вида (1.1)–(1.3), и мы можем применить к нему алгоритм 1, описанный в разд. 1, который позволяет вычислять значение этого интеграла с любой желаемой точностью $\delta =\delta \left(k\right)>0$ (задавая необходимое количество  последовательных дроблений куба $\Pi$). Используя алгоритм 1, $\forall t\in \left(t_1\mathrm{,}{\overline{t}}_1\right]$при любом выбранном значении $k\ge 2$ вместо точного значения интеграла $F\left(t\right)$ находим числа $F_{\delta }\left(t\right)$, $\delta =\delta \left(k\right)>0$, такие, что (см. далее замечание 7)

$F_{\delta }\left(t\right)\le F\left(t\right)\le F_{\delta }\left(t\right)+\delta .$ (4.1)

Заметим, что в рассматриваемом нами кусочно-линейном случае с ограниченными множествами $X\left(t\right)$, где $t\ge t_1$, функция  непрерывна и монотонно возрастает при $t\ge t_1$, а следовательно, существует единственное число $q\left(\alpha \right)>t_1: F\left(q\left(\alpha \right)\right)=\alpha$. Нам понадобятся следующие простые утверждения, непосредственно следующие из определения $q\left(\alpha \right)$.

У т в е р ж д е н и е 1. Пусть выполняется (4.1). Тогда в случае $F_{\delta }\left(t\right)<\alpha -\delta$ (откуда в силу (4.1) $F\left(t\right)<\alpha$) справедливо $t<q\left(\alpha \right)$.

Д о к а з а т е л ь с т в о. Предположим, что $t\ge q\left(\alpha \right)$. Из монотонности F следует, что $F\left(t\right)\ge F\left(q\right(\alpha \left)\right)=\alpha$, а это противоречит тому, что $F\left(t\right)<\alpha$. Утверждение 1 доказано.

У т в е р ж д е н и е 2. Пусть верно (4.1). Тогда в случае $F_{\delta }\left(t\right)\ge \alpha$ справедливо $q\left(\alpha \right)\le t$.

Д о к а з а т е л ь с т в о. Используя (4.1), получаем $F\left(t\right)\ge F_{\delta }\left(t\right)\ge \alpha =F\left(q\right(\alpha \left)\right)$, откуда в силу монотонности  имеем $q\left(\alpha \right)\le t$ Утверждение 2 доказано.

А л г о р и т м 2 (нахождения с заданной точностью $\epsilon >0$ величины $q\left(\alpha \right)$).

Ш а г 1. Пусть $t_1\mathrm{,}{\overline{t}}_1$ — найденные ранее величины, удовлетворяющие (3.3), $i=1$, $k=k_0\ge 2$, k — количество этапов дробления куба $\Pi$, от которого зависит величина $\delta$ из (4.1), $k_0$ — начальное значение этой величины. Тогда справедливы неравенства

$t_i<q\left(\alpha \right)\le {\overline{t}}_i.$ (4.2)

Ш а г 2. Проверяем выполнение неравенства $t_i-{\overline{t}}_i\le 2\epsilon$. Если оно верно, то в силу (4.2) имеем: $\left|q\left(\alpha \right)-(t_i+{\overline{t}}_i)/2\right|\le \epsilon$, т.е. задача решена и в качестве приближенного значения $q\left(\alpha \right)$ берем $(t_i+{\overline{t}}_i)/2$. В противном случае переходим к шагу 3.

Ш а г 3. Находим числа ${t^{\text{'}}}_i$, ${{t^{\text{'}}}^{\text{'}}}_i$ методом “золотого сечения” (см. ниже замечание 8):

${t^{\text{'}}}_i=t_i+\left(3-\sqrt{5}\right)\left({\overline{t}}_i-t_i\right)/2\simeq t_i+0.382\left({\overline{t}}_i-t_i\right),$

${{t^{\text{'}}}^{\text{'}}}_i=t_i+\left(\sqrt{5}-1\right)\left({\overline{t}}_i-t_i\right)/2\simeq t_i+0.618\left({\overline{t}}_i-t_i\right).$

Ш а г 4. Используя алгоритм 1, определяем числа $F_{{\delta }_1}\left({t^{\text{'}}}_i\right)$,$F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)$,${\delta }_1={\delta }_1\left(k\right)>0$, ${\delta }_2={\delta }_2\left(k\right)>\mathrm{0,}$ такие, что $F_{{\delta }_1}\left({t^{\text{'}}}_i\right)\le F\left({t^{\text{'}}}_i\right)\le F_{{\delta }_1}\left({t^{\text{'}}}_i\right)+{\delta }_1$, $F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)\le F\left({{t^{\text{'}}}^{\text{'}}}_i\right)\le F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)+{\delta }_2$. Если $F_{{\delta }_1}\left({t^{\text{'}}}_i\right)<\alpha -{\delta }_1$, то в силу утверждения 1 ${t^{\text{'}}}_i<q\left(\alpha \right)$. Тогда полагаем $t_{i+1}={t^{\text{'}}}_i$, ${\overline{t}}_{i+1}={\overline{t}}_i$, присваиваем $i:=i+1$, переходим к шагу 2 и при этом сохраняется (4.2).

Если $F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)\ge \alpha$, то в силу утверждения 2 $q\left(\alpha \right)\le {{t^{\text{'}}}^{\text{'}}}_i$. Тогда полагаем $t_{i+1}=t_i$, ${\overline{t}}_{i+1}={{t^{\text{'}}}^{\text{'}}}_i,$ присваиваем $i:=i+1$, переходим к шагу 2 и при этом сохраняется (4.2).

Ш а г 5. К шагу 5 переходим только в случае

$F_{{\delta }_1}\left({t^{\text{'}}}_i\right)\ge \alpha -{\delta }_1,F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)<\alpha .$ (4.3)

Увеличиваем число этапов дробления куба $\Pi$ на 1, т.е. присваиваем $k:=k+1$ и переходим к шагу 4.

О б о с н о в а н и е а л г о р и т м а 2. Покажем, что работа алгоритма 2 закончится через конечное число шагов.

Предположим противное, т.е. пусть при работе алгоритма 2 совершается бесконечное число шагов. Заметим, что после каждого присвоения (на шаге 4) $i:=i+1$ переходим к шагу 2 с новым набором величин $t_i$, ${\overline{t}}_i$ и при этом ${\overline{t}}_i-t_i=0.5\left(\sqrt{5}-1\right)\left({\overline{t}}_{i-1}-t_{i-1}\right)$, где $0.5\left(\sqrt{5}-1\right)=\mathrm{0.618...}<1$, а следовательно, при достаточно большом i будет справедливо ${\overline{t}}_i-t_i={\left[0.5\left(\sqrt{5}-1\right)\right]}^{i-1}\left({\overline{t}}_1-t_1\right)\le 2\epsilon$, что приведет к остановке алгоритма на шаге 2, а это противоречит бесконечности выполнения шагов алгоритма. Таким образом, для некоторого фиксированного i будет происходить бесконечное число переходов: шаг 4 $\mapsto$ шаг 5 $\mapsto$ шаг 4 $\mapsto$ шаг 5 $\mapsto$ ⋅⋅⋅ $\mapsto$ шаг 4 $\mapsto$ шаг 5 $\mapsto$ ⋅⋅⋅, т.е. бесконечное увеличение количества этапов дробления k при вычислении интегралов: $F\left({t^{\text{'}}}_i\right)={\int }_{X\left({t^{\text{'}}}_i\right)}{\phi }_n\left(x\right)dx$, $F\left({{t^{\text{'}}}^{\text{'}}}_i\right)={\int }_{X\left({{t^{\text{'}}}^{\text{'}}}_i\right)}{\phi }_n\left(x\right)dx$,

где ${t^{\text{'}}}_i=t_i+0.5\left(3-\sqrt{5}\right)({\overline{t}}_i-t_i)$, ${{t^{\text{'}}}^{\text{'}}}_i=t_i+0.5\left(\sqrt{5}-1\right)({\overline{t}}_i-t_i)$. При этом ${t^{\text{'}}}_i\ge t_1+0.5\left(3-\sqrt{5}\right){\left[0.5\left(\sqrt{5}-1\right)\right]}^{i-1}$ $\left({\overline{t}}_1-t_1\right)>t_1$, а следовательно, $\mathrm{int}X\left({t^{\text{'}}}_i\right)\ne \varnothing$, $\mathrm{int}X\left({t^{\text{'}\text{'}}}_i\right)\ne \varnothing$.

Таким образом, выполнены все условия, необходимые для применения алгоритма 1 и при увеличении k — количества этапов дробления куба $\Pi$ величины ${\delta }_1={\delta }_1\left(k\right)$, ${\delta }_2={\delta }_2\left(k\right)$ стремятся к 0 (см. далее замечание 7). Из (4.3), используя (4.1), для фиксированного i имеем $\alpha -{\delta }_1\le F_{{\delta }_1}\left({t^{\text{'}}}_i\right)\le F\left({t^{\text{'}}}_i\right)$, $F\left({{t^{\text{'}}}^{\text{'}}}_i\right)\le F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)+{\delta }_2<\alpha +{\delta }_2$, и при этом в силу монотонности $F\left(t\right)$справедливо $F\left({t^{\text{'}}}_i\right)<F\left({{t^{\text{'}}}^{\text{'}}}_i\right)$ (поскольку ${t^{\text{'}}}_i<{{t^{\text{'}}}^{\text{'}}}_i$), а следовательно,

$F\left({{t^{\text{'}}}^{\text{'}}}_i\right)-F\left({t^{\text{'}}}_i\right)<{\delta }_1\left(k\right)+{\delta }_2\left(k\right).$ (4.4)

Заметим, что в левой части неравенства (4.4) находится постоянная положительная величина, а выражение справа стремится к 0 при $k\to \infty$. Полученное противоречие и завершает обоснование алгоритма 2.

Таким образом, установлена принципиальная возможность вычисления с заданной точностью $\epsilon >0$ значения $q\left(\alpha \right)$. Получим также в рассматриваемом кусочно-линейном случае некоторые оценки. Обозначим через ${\epsilon }_i=\left({\overline{t}}_i-t_i\right)/2$ переменную величину, меняющуюся в процессе работы алгоритма 2. Поскольку в силу (4.2) $t_i<q\left(\alpha \right)\le {\overline{t}}_i$, то $\left|q\left(\alpha \right)-0.5\left({\overline{t}}_i+t_i\right)\right|\le 0.5\left({\overline{t}}_i-t_i\right)={\epsilon }_i$, т.е. величину ${\epsilon }_i$ можно рассматривать как достигнутую при текущем значении параметра i точность вычисления $q\left(\alpha \right)$. Цель дальнейшего рассуждения — получение неравенства, показывающего, что между величиной ${\epsilon }_i$ и величиной ${\delta }_1\left(k\right)+{\delta }_2\left(k\right)$ из условия (4.4), являющегося следствием неравенств (4.3), выполняющихся на шаге 5, можно установить “линейную” зависимость так, что для некоторой константы $C>0$ справедливо

${\epsilon }_i\le C\left({\delta }_1\left(k\right)+{\delta }_2\left(k\right)\right).$ (4.5)

Из этого неравенства, в частности, следует, что на шаге 5 не может выполняться ${\delta }_1\left(k\right)+{\delta }_2\left(k\right)\le \epsilon /C$, поскольку в этом случае ${\epsilon }_i\le \epsilon$ и на шаге 2 должна была произойти остановка по условию ${\overline{t}}_i-t_i=2{\epsilon }_i\le 2\epsilon$. Таким образом, оценка (4.5) накладывает ограничение на максимальное количество этапов дробления k (более подробно об этом говорится в замечании 7, приведенном ниже).

Для установления справедливости указанного условия (4.5) потребуется геометрическое неравенство, обоснование которого приводится в разд. 5. Чтобы его сформулировать, потребуются некоторые обозначения. При любом $t\ge t_1$ множество $X\left(t\right)=\left\{x\in {ℝ}^n\left|\Psi \left(x\right)\le t\right.\right\}$является выпуклым ограниченным и многогранным (кратко — многогранником). В случае $t>t_1$имеем $\mathrm{int}X\left(t\right)\ne \varnothing$, т.е. множество $X\left(t\right)$ является многогранником размерности n и мы можем ввести в рассмотрение поверхность множества $X\left(t\right)$, т.е. его границу, которая является объединением граней размерности $n-1$ многогранника $X\left(t\right)$. Кроме того, в этом случае можно говорить о площади поверхности $X\left(t\right)$ как сумме площадей граней размерности $n-1$многогранника $X\left(t\right)$ (площадь каждой грани $\Gamma$ размерности $n-1$ многогранника $X\left(t\right)$ понимается как мера Лебега ${\mu }_{n-1}\left(\Gamma \right)$, рассматриваемая в плоскости размерности $n-1$, включающей в себя $\Gamma$; этой плоскостью будет аффинная оболочка множества $\Gamma$). Обозначим через $S\left(t\right)$ площадь поверхности многогранника $X\left(t\right)$, где $t>t_1$. Пусть $E=\max \left\{\left|e^1\right|\mathrm{,...,}\left|e^r\right|\right\}>0$, $t^{\text{'}}\ge t>t_1$. Тогда (см. ниже утверждение 21) справедливо геометрическое неравенство

$\mu \left(X\left(t^{\text{'}}\right)\right)-\mu \left(X\left(t\right)\right)\ge E^{-1}S\left(t\right)\left(t^{\text{'}}-t\right),$ (4.6)

откуда

$F\left(t^{\text{'}}\right)-F\left(t\right)={\int }_{X\left(t^{\text{'}}\right)\backslash X\left(t\right)}{\phi }_n\left(x\right)dx\ge \min {\phi }_n\left(X\right(t^{\text{'}}\left)\right)\left[\mu \left(X\left(t^{\text{'}}\right)\right)-\mu \left(X\left(t\right)\right)\right]\ge$

$\ge E^{-1}\min {\phi }_n\left(X\right(t^{\text{'}}\left)\right)S\left(t\right)\left(t^{\text{'}}-t\right).$

Пусть теперь

$\Delta >\mathrm{0,}{\overline{t}}_1\ge t^{\text{'}}\ge t\ge t_1+\Delta ,L=E^{-1}\min {\phi }_n\left(X\right({\overline{t}}_1\left)\right)\cdot \underset{t\in \left[t_1+\Delta ,{\overline{t}}_1\right]}{}S\left(t\right).$  (4.7)

Тогда

$F\left(t^{\text{'}}\right)-F\left(t\right)\ge L\left(t^{\text{'}}-t\right).$ (4.8)

Заметим, что в формуле, определяющей постоянную L, присутствует неопределенный параметр $\Delta >0$. Он легко находится в результате совершения нескольких шагов алгоритма 2 без проверки справедливости условия остановки алгоритма ${\overline{t}}_i-t_i\le 2\epsilon$. Поскольку $q\left(\alpha \right)>t_1$ и при обосновании алгоритма 2 была по существу доказана сходимость $t_i$, ${\overline{t}}_i$ к $q\left(\alpha \right)$ в процессе его выполнения, то после конечного числа шагов алгоритма при некотором $i_0\ge 2$ обязательно верно $t_1<t_{i_0}<q\left(\alpha \right)$, и тогда при $i\ge i_0$ будет справедливо $t_i\ge t_1+\Delta$, где $\Delta =t_{i_0}-t_1$. Таким образом, можно для простоты обозначений предполагать, что уже при $i=2$ верно

$t_2=t_1+\Delta <q\left(\alpha \right)\le {\overline{t}}_2\le {\overline{t}}_1,\Delta >0.$ (4.9)

В этом случае, если мы находимся на шаге 5 при некотором $i\ge 2$, то справедливы неравенства (4.3), а следовательно, и (4.4), откуда, используя выполнение (4.8) в случае (4.7), имеем

${\delta }_1\left(k\right)+{\delta }_2\left(k\right)>F\left({{t^{\text{'}}}^{\text{'}}}_i\right)-F\left({t^{\text{'}}}_i\right)\ge L\left({{t^{\text{'}}}^{\text{'}}}_i-{t^{\text{'}}}_i\right)=\left(\sqrt{5}-2\right)L\left({\overline{t}}_i-t_i\right),$ (4.10)

т.е. на шаге 5 при $i\ge 2$ верно

${\epsilon }_i=0.5\left({\overline{t}}_i-t_i\right)<{\left[L\left(\sqrt{5}-2\right)\right]}^{-1}\left({\delta }_1\left(k\right)+{\delta }_2\left(k\right)\right)=\left(\sqrt{5}+2\right)L^{-1}\left({\delta }_1\left(k\right)+{\delta }_2\left(k\right)\right),$

и тем самым обосновано существование величины $C=\left(\sqrt{5}+2\right)L^{-1}$ из условия (4.5). Кроме того, необходимо обосновать, что

$L=E^{-1}\min {\phi }_n\left(X\right({\overline{t}}_1\left)\right)\cdot \underset{t\in \left[t_1+\Delta ,{\overline{t}}_1\right]}{}S\left(t\right)>0.$

Выполнение $\min {\phi }_n\left(X\right({\overline{t}}_1\left)\right)>0$ очевидно. Осталось доказать, что

$\underset{t\in \left[t_1+\Delta ,{\overline{t}}_1\right]}{inf}S\left(t\right)>0.$

Заметим, что функция $\mu \left(X\right(t\left)\right)$ монотонно возрастает и при этом ${\mu }_0=\mu \left(X\right(t_1+\Delta \left)\right)>0$, поскольку в силу $\Delta >0$ верно $\mathrm{int}X(t_1+\Delta )\ne \varnothing$. Пусть $S_0$ — площадь поверхности n-мерного шара объема ${\mu }_0$. Тогда $\forall t\ge t_1+\Delta$ $\mu \left(X\right(t\left)\right)\ge {\mu }_0=\mu \left(X(t_1+\Delta )\right)$, а следовательно, $\forall t\ge t_1+\Delta$ $S\left(t\right)\ge S_0$, откуда

$\underset{t\in \left[t_1+\Delta ,{\overline{t}}_1\right]}{inf}S\left(t\right)\ge S_0>0.$

З а м е ч а н и е 7. Как уже отмечалось, мы находимся в условиях применения алгоритма 1, и при этом возможны по крайней мере две модификации, предложенные в [8, 9]. В одной из них (1-я модификация) для величины $\delta$ из условия (5.1) выполняется $\delta =O\left({\tau }^2\right)$ при $\tau \to 0+$, а в другой (более сложной 2-й модификации) $\delta =O\left({\tau }^3\right)$ при $\tau \to 0+$, где $\tau =T/2^{k+1},$ $T=b-a$ — длина ребер куба $\Pi$, т.е. $\tau$ — половина длины ребер кубов k-го (т.е. последнего) этапа дробления куба $\Pi$, k — параметр алгоритма 2. Более того, можно показать, что в случае выполнения условий (4.9) найдутся константы ${\overline{C}}_1,{\overline{C}}_2>0$ (общие для всей работы алгоритма 2), такие, что при $i\ge 2$ для величин ${\delta }_1\mathrm{,}{\delta }_2$, вычисляемых на шаге 4 алгоритма 2, в случае 1-й модификации будет верно ${\delta }_1\mathrm{,}{\delta }_2\le {\overline{C}}_1{\tau }^2\mathrm{,}$ а в случае 2-й модификации — ${\delta }_1\mathrm{,}{\delta }_2\le {\overline{C}}_2{\tau }^3$. Следствием этих условий, а также неравенства (4.5) является условие ${\epsilon }_i=O\left({\tau }^2\right)$ (для 1-й модификации) и ${\epsilon }_i=O\left({\tau }^3\right)$ (для 2-й модификации) при $\tau \to 0+$. Условие ${\epsilon }_i=O\left({\tau }^2\right)$ при $\tau \to 0+$говорит о том, что при увеличении k на 1 (см. $k:=k+1$ на шаге 5) величина $\tau =T/2^{k+1},$уменьшается в 2 раза и можно ожидать, что величина ${\epsilon }_i$ уменьшится в 4 раза (в рассмотренных автором примерах такая зависимость, как правило, наблюдается). Соответственно, в случае 2-й модификации при увеличении k на 1 можно ожидать уменьшение величины ${\epsilon }_i$ в 8 раз.

Используя эти соображения, можно при решении практической задачи сделать предварительные расчеты для некоторого $k=k_0$ и по достигнутой для этого случая величине ${\epsilon }_i={\epsilon }_i\left(k_0\right)$ спрогнозировать количество этапов $k=k\left(\epsilon \right)$, необходимых для вычисления с заданной точностью $\epsilon$ значения $q\left(\alpha \right)$. Затем, как уже отмечалось ранее, можно заранее создать одномерный массив Ф(a,b,k) значений функции $\Phi \left(y\right)$, удовлетворяющей равенству (1.4), на равномерной сетке $S(a,b,k)=\left\{y\in ℝ\left|y=s_i(a,b,k)\triangleq a+i(b-a)2^{-k},i=\overline{{\mathrm{0,2}}^k}\right.\right\}$, которые можно использовать при решении всех вспомогательных задач интегрирования, возникающих в процессе выполнения алгоритма 2. Это дает значительное снижение вычислительных затрат.

Кроме того, действуя, согласно замечанию 5, можно при каждом вычислении величины $F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)$ для всяких текущих i, k находить минимальный и максимальный номера используемых узлов сетки S(a,b,k). Тогда в первом же случае присвоения на шаге 4 алгоритма 2 ${\overline{t}}_{i+1}={{t^{\text{'}}}^{\text{'}}}_i$ (при выполнении $F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)\ge \alpha$) можно теперь уточнить границы внешнего куба $\Pi$, используемого при решении дальнейших задач интегрирования, заменяя его на более узкий $\tilde{\Pi }=\left\{x\in {ℝ}^n\left|\tilde{a}\le x_i\le \tilde{b},i=\overline{\mathrm{1,}n}\right.\right\}$, где $\tilde{a}$, $\tilde{b}$ — элементы сетки S(a,b,k), определяемые по указанным номерам (см. замечание 5). Кроме того, как показано в замечании 5, при замене внешнего куба $\Pi$ на $\tilde{\Pi }$ может появиться возможность для уменьшения текущего (а следовательно, и последующих) количества этапов дробления k для нового внешнего куба $\tilde{\Pi }$.

Более того, следуя замечанию 4, можно при каждом вычислении величины $F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)$ для всяких текущих i, k определять по каждой координате $x_i$ минимальный $j_{\min }^{\left(i\right)}\left(k\right)\in \left\{\overline{{\mathrm{1,2}}^k+1}\right\}$ и максимальный $j_{\max }^{\left(i\right)}\left(k\right)\in \left\{\overline{{\mathrm{1,2}}^k+1}\right\}$ номера элементов сетки S(a,b,k), являющихся координатами вершин этих кубов. Обозначим  ${\tilde{a}}_i\left(k\right)=s_{j_{\min }^{\left(i\right)}\left(k\right)}(a,b,k),$ ${\tilde{b}}_i\left(k\right)=s_{j_{\max }^{\left(i\right)}\left(k\right)}(a,b,k)$, $i=\overline{\mathrm{1,}n}$. Тогда в первом же случае присвоения на шаге 4 алгоритма 2 ${\overline{t}}_{i+1}={{t^{\text{'}}}^{\text{'}}}_i$ (при выполнении $F_{{\delta }_2}\left({{t^{\text{'}}}^{\text{'}}}_i\right)\ge \alpha$) происходит включение $X\subseteq {\tilde{\Pi }}_0\left(k\right)=\left\{x\in {ℝ}^n\left|{\tilde{a}}_i\left(k\right)\le x_i\le {\tilde{b}}_i\left(k\right),i=\overline{\mathrm{1,}n}\right.\right\}$. Таким образом, при решении дальнейших задач интегрирования с помощью алгоритма 1 можем теперь применять модификацию этого алгоритма в соответствии с замечанием 4 (минуя необходимость дополнительного решения указанных в этом замечании ЗЛП).

Приведем также следующие “оптимистические” оценки для количества этапов дробления k. В случае 1-й модификации неравенства (4.5), ${\delta }_1\mathrm{,}{\delta }_2\le {\overline{C}}_1{\tau }^2$, а также равенство $\tau =T/2^{k+1}$ приводят к неравенству ${\epsilon }_i\le {C^{\text{'}}}_1{2}^{-2k}$, где ${C^{\text{'}}}_1>0$ — некоторое число, т.е. найдется число $C_1>0$, для которого верно $k\le C_1-0.5{\log }_2{\epsilon }_i$. Соответственно, в случае 2-й модификации аналогичным образом получаем, что для некоторого числа $C_2>0$ выполняется $k\le C_2-\left({\log }_2{\epsilon }_i\right)/3$. Отметим, что в этих оценках не присутствует число n — размерность задачи (тем не менее, от n зависит общее число кубов на каждом этапе дробления, которое очевидным образом влияет на время решения задачи).

З а м е ч а н и е 8. Как известно (см., например, [11, С. 19]), золотым сечением отрезка $\left[t_i\mathrm{,}{\overline{t}}_i\right]$ называется деление его (с помощью любой из точек ${t^{\text{'}}}_i$,$t_i^{\text{'}\text{'}}$) на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Замечательно здесь то, что ${t^{\text{'}}}_i$ в свою очередь производит золотое сечение отрезка $\left[t_i,t_i^{\text{'}\text{'}}\right]$. Аналогично точка $t_i^{\text{'}\text{'}}$ производит золотое сечение отрезка $\left[{t^{\text{'}}}_i,{\overline{t}}_i\right]$. Используя указанное, можно получить экономию в вычислениях.

З а м е ч а н и е 9. Чтобы расширить множество задач, к которым может быть применен алгоритм 2, перечислим все условия, которые потребовались для его обоснования. Это прежде всего строгая монотонность $F\left(t\right)$, которая применялась на втором этапе обоснования при рассмотрении (4.4). Кроме того, использовалась применимость алгоритма 1 для вычисления интегралов $F\left(t\right)$ с точностью $\delta >0$, т.е. возможность вычисления чисел $F_{\delta }\left(t\right), \delta \mathrm{,}$ удовлетворяющих (4.1). При любом фиксированном $t\in (t_1,{\overline{t}}_1]$ с увеличением k (параметр алгоритма 1) величина $\delta =\delta \left(k\right)$ в условии (4.1) должна стремиться к нулю (это также использовалось на втором этапе обоснования при рассмотрении (4.4)). В работе [9] (см. также [6, С. 53]) показано, что если $X=\left\{x\in \Pi \left|l_1\left(x\right)\le \mathrm{0,}\dots ,l_r\left(x\right)\le 0\right.\right\},$ $\Psi \left(x\right)=\max \left\{l_1\left(x\right),\dots ,l_r\left(x\right)\right\}$, где $\Pi$ удовлетворяет (1.3), $l_1\left(x\right),\dots ,l_r\left(x\right)$ — определенные и измеримые на $\Pi$ функции, то в случае $\mu \left(\left\{x\in \Pi \left|\Psi \left(x\right)=0\right.\right\}\right)=0$ при применении алгоритма 1 к вычислению

$F={\int }_X{\phi }_n\left(x\right)dx$

верно $\delta =\delta \left(k\right)\to 0$ при $k\to \infty$. В связи с этим потребуется выполнение условия $\mu \left(\left\{x\in \Pi \left|\Psi \left(x\right)=t\right.\right\}\right)=0$ при $t\in t_1\mathrm{,}{\overline{t}}_1$. Соответственно для существования и возможности определения границ $a\mathrm{,}b$ куба $\Pi$ понадобится ограниченность множеств $X\left(t\right)=\left\{x\in {ℝ}^n\left|\Psi \left(x\right)\le t\right.\right\}$ при $t\in t_1\mathrm{,}{\overline{t}}_1$. Перечисленные условия являются справедливыми для широкого круга задач. Кроме того, для работы алгоритма 2 необходимы “стартовые” значения $t_1$, ${\overline{t}}_1$, такие, что $t_1<q\left(\alpha \right)\le {\overline{t}}_1$. Как правило они находятся “простым подбором” (в результате вычисления значений $F_{\delta }\left(t\right)$ на сетке значений t при достаточно малом $\delta >0$).

П р и м е р 2. Рассматривался случай с $n=3$, $r=4$, $X\left(t\right)=\left\{x\in \Pi \left|\Psi \left(x\right)\le t\right.\right\}$, $\Psi \left(x\right)=$ $=\max \left\{l_1\left(x\right),l_2\left(x\right),l_3\left(x\right),l_4\left(x\right)\right\}$, $l_1\left(x\right)=x_1+x_2+x_3-9$, $l_2\left(x\right)=-x_1-2x_2-x_3-8$, $l_3\left(x\right)=x_1+3x_2-$$-4x_3-10$, $l_4\left(x\right)=-x_1-2x_2+3x_3-9$, $\Pi =\{x\in {ℝ}^n|-10\le x_i\le \mathrm{10,}i=\overline{\mathrm{1,3}}\}$. Величина $q\left(\alpha \right)$вычислялась для $\alpha =0.9$. Была задана точность $\epsilon =0.001$. Начальное значение $k=5$. Был использован метод интегрирования второго порядка точности. Составлена табл. 2 текущих значений величин k, i, ${\epsilon }_i=0.5\left({\overline{t}}_i-t_i\right)$, $0.5\left({\overline{t}}_i+t_i\right)$ на шаге 5 алгоритма 2. Именно на этом шаге происходит увеличение количества этапов дробления k. Поэтому представляет интерес достигнутое минимальное значение величины ${\epsilon }_i=0.5\left({\overline{t}}_i-t_i\right)$ (текущая точность вычисления $q\left(\alpha \right)$ для текущего значения k). Как и было предсказано теоретически, в последнем столбце устанавливается значение 4 (поскольку был использован метод интегрирования второго порядка точности). Алгоритм закончил работу при $i=20$, $k=\mathrm{12,}$ ${\epsilon }_i=0.5\left({\overline{t}}_i-t_i\right)=0.000695261517342338$, $q\left(\alpha \right)=q\left(0.9\right)\simeq 0.5\left({\overline{t}}_i+t_i\right)=-\mathrm{2.09240354796087.}$

Таблица 2

5. Некоторые свойства выпуклых многогранников. Целью этого раздела является получение геометрического неравенства (4.6), позволяющего в свою очередь получить неравенство (4.5), устанавливающее линейный характер зависимости между вычисляемой на шаге 2 алгоритма 2 величиной ${\epsilon }_i=({\overline{t}}_i-t_i)/2$ (точность достигнутого приближения $({\overline{t}}_i+t_i)/2$ к искомому значению $q\left(\alpha \right)$) и суммарной погрешностью ${\delta }_1\left(k\right)+{\delta }_2\left(k\right)$ вычисления интегралов на шаге 2. Расчет этих интегралов дает основной вклад в трудоемкость алгоритма 2, которая определяется максимальным значением параметра k — количества этапов дробления “внешнего” куба $\Pi$, необходимого для вычисления этих интегралов. На основании оценки (4.5) в замечании 7 приведены весьма “оптимистические” оценки для величины k в зависимости от ${\epsilon }_i$, не зависящие от размерности задачи n.

Нам понадобятся некоторые вспомогательные утверждения. Пусть $x^0\in {ℝ}^n$, $\delta >0$. Обозначим $B^{\left(n\right)}(x^0,\delta )=\{x\in {ℝ}^n|\left|x-x^0\right|\le \delta \}$ — шар радиуса $\delta$ с центром в точке $x^0$. Кроме того, для произвольного множества $U\subseteq {ℝ}^n$ считаем, что $\partial U=\overline{U}\backslash \mathrm{int}U$ — граница $U$.

Утверждение 3. Допустим, что $X\left(t\right)=\{x\in {ℝ}^n|\Psi \left(x\right)\le t\}$, $X=X\left(0\right)\ne \varnothing$, $\Psi \left(x\right)=\max \left\{l_1\right(x),\dots ,l_r(x\left)\right\}$ и $l_i\left(x\right)$ удовлетворяют условиям (1.2). Тогда при любом $t>0$множество $X\left(t\right)$ содержит каждую точку $x^0\in X$ вместе с шаром $B^{\left(n\right)}(x^0,E^{-1}t)$, где $E=\max \left\{\left|e^1\right|,\dots ,\left|e^r\right|\right\}>0$.

Д о к а з а т е л ь с т в о. Из условия $x^0\in X$ следует, что $\max \left\{⟨e^i,x^0⟩+d_i|i=\overline{\mathrm{1,}r}\right\}\le 0.$ Пусть $x\in {ℝ}^n$, $\left|x-x^0\right|\le E^{-1}t$. Докажем, что $x\in X\left(t\right)$. Действительно,

$\underset{i=\overline{\mathrm{1,}r}}{max}\left\{⟨e^i,x⟩+d_i\right\}=\underset{i=\overline{\mathrm{1,}r}}{max}\left\{⟨e^i,x^0+(x-x^0)⟩+d_i\right\}=\underset{i=\overline{\mathrm{1,}r}}{max}\left\{⟨e^i,x^0⟩+d_i+⟨e^i,x-x^0⟩\right\}=$

$\begin{array}{c}\le \underset{i=\overline{\mathrm{1,}r}}{max}\left\{⟨e^i,x^0⟩+d_i+\left|e^i\right|\cdot \left|x-x^0\right|\right\}\le \underset{i=\overline{\mathrm{1,}r}}{max}\left\{⟨e^i,x^0⟩+d_i+E^{-1}\left|e^i\right|t\right\}\le \\ \underset{i=\overline{\mathrm{1,}r}}{\le \max }\left\{⟨e^i,x^0⟩+d_i+t\right\}\le \underset{i=\overline{\mathrm{1,}r}}{max}\left\{⟨e^i,x^0⟩+d_i\right\}+t\le t\Rightarrow x\in X\left(t\right).\end{array}$