Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях

Подождите немного. Документ загружается.

требует большого количества вычислений интервальных расширений (того или иного вида)

функции к f(x

, x

, ... x

). Сколбоу предположил метод, позволяющий существенно сократить

объем вычислений. В качестве интервального расширения используется центрированная

форма дающая наименьшую нижнюю границу для

. Области различной величины,

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

вычисленные на этих областях, возрастают. Если дальнейшее подразбиение конкретной

области дает новые нижние границы, превосходящие нижние границы на каких-то других

областях из списка, то только тогда эти области далее подразбиваются, на них вычисляется

и список переупорядочивается. Процедура продолжается до тех пор, пока разность между

двумя последовательными нижними границами не станет меньше заданной величины.

Поясним сказанное на примере функции одной переменной. При

р=8

возможна следующая

ситуация (рис.3.1).

Рис 3.1.

В обозначениях имеем . Следующий шаг включает

азбиение и вычисление соответствующих значений интервальной

функции. Эти значения вносятся в список в нужном порядке,a , которое теперь не

нужно, отбрасывается. Предположим, что . Это дает возможности:

1) тогда продолжаем процесс при

р=32

;

2) .

Во втором случае необходимо разбить , вычислить соответствующие значения функции,

а результаты упорядочить. Действия по этой схеме продолжаются до тех пор, пока не

получится наименьшая нижняя граница, соответствующая

р=16

. Итерации прекращаются

тогда, когда разность между двумя последовательными нижними границами и , не

станет меньше ,

— заданное число.

Для получения верхней границы процесс повторяется с -

вместо

. Данный метод можно

использовать не обязательно с рациональными

, только в этом случае вместо

центрированной формы надо взять какой-либо другой тип интервального расширения,

нап

име

MV-

Применение обобщенной интервальной арифметики

Получение границ для

⎯

f(X)

с помощью обобщенной интервальной арифметики

проиллюстрируем на нескольких простых примерах.

Пример 3.5.

Рассмотрим функцию

f(x

)=(x

)/(x

), X

=[l, 2], X

=[5, 10]

. Интервалы

представим в виде

=3/2+

=[-1/2, 1/2], X

=15/2+

=[-5/2, 5/2].

Положим

= Х

, X

=Х

-X

Тогда

⎯

f(Х

) Х

/Х

. Учитывая правила арифметических

действий над обобщенными интервалами, будем последовательно иметь

= 9 +

, X

= -

6 +

и, наконец,

= -9/6 +

[-5/6, -5/18]+

[1/18, 1/6]. После сведения к интервалам,

т.е. заменяя

на [1/2, -1/2],

- на [-5/2, 5/2], найдем X

= [-7/3, -2/3]

[-2.334, -0.6666]. Тот

же результат получил Мур с помощью центрированной формы. MV-форма в этом случае

приводит к более широкому интервалу [-67/18, 13/18]. Прямое вычисление Х

в обычной

интервальной арифметике дает интервал [-4, -2/3]. Точное множество значений

⎯

f(Х

, X

) = l+2/(Х

/ X

-l) = l+2/([l/10, 2/5]-1) = 1 + 2/[-9/10, -6/10] =

= 1 + [-20/6, -20/9] = [-7/3, -11/9] [-2.334, -1.222].

Пример 3.6.

Возьмем

f(x)=-(1+x+x

)/(1+x+2x

), x ∈

X= [-0.001, 0.003].

Вычисляя (1+X + Х

)/(1+Х+2Х

) с помощью обычной интервальной арифметики (с

точностью до (6знаков), получим интервал [0.995994, 1.00402]. Обобщенная интервальная

арифметика дает [0.999991, 1.0001]+

[-0.00200503, -0.00198498], и после сведения к

интервалу [0.999986, 1.00001] объединенное расширенно

(

⎯

∈

[0.999991, 0.999999]. Таким образом, результат, полученный с помощью обобщенной

интервальной арифметики, заметно точнее результата применения обычной интервальной

арифметики.

Обобщенная интервальная арифметика может быть полезна при решении многих задач.

Заметим, однако, что при широких исходных интервалах она зачастую дает интервалы шире,

чем, к примеру, центрированная форма. При очень узких или вырожденных интервалах, по-

видимому, лучше использовать обычную интервальную арифметику, поскольку обобщенная

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

Вычисления с помощью нестандартной арифметики

Арифметикой с нестандартными операциями можно эффективно пользоваться для

вычисления объединенных pacширений функции, удовлетворяющих определенным условиям

монотонности.

Пусть

∈

)

, функция

x) определена при

∈

. Обозначим через

М(D)

множество всех

монотонных на

функций. Если

∈

M(D)

, то

объединенное расширение

⎯

f(X)

легко вычисляется:

⎯

Будем говорить, что (f, g)

∈

M(D) удовлетворяют условию монотонности M

, если функции f,

g одновременно обе возрастают или обе убывают. Пара f, g удовлетворяет условию M

, если

одна из функций f, g возрастает, а другая — убывает. Будем, по определению, полагать А

В = A - (-В), A, B

∈

(R).

Теорема 3.3.

Если f, g таковы, что h = f + g

∈

М (D), то при всех X

∈

Если f, g таковы, что h = f - g

∈

M(D), то

Если f и g таковы, что

, h = f

•

∈

M(D), то

Здесь А B = A : (1/B). Если f и g таковы, что

| ∈

M(D), g(x) 0, x

∈D и

h = f/g

∈

M(D),

то для любого X

∈

⎯

Доказательство утверждении теоремы легко получается с использованием монотонности

фигурирующих в ней функций. Рассмотрим примеры ее применения.

Пример 3.7.

Вычислить

⎯

h(Х), где h(x)=x

+ x, x

∈

R. Объединенным расширением функции

(x)=x является

⎯

f(X)=X. Если 0 является не принадлежит Х, то для g(x)=x

⎯

g(X)=X

•

X=X

. Функция h(x)

=x+x

монотонна на всяком интервале Х таком, что —1/2 не принадлежит X. Таким образом,

объединенное расширение

⎯

h(X) монист быть вычислено с помощью теоремы 1 для любого

X, не содержащего точек -1/2 и 0, и мы имеем

⎯

Пример 3.8.

Для h(x) = x - x

применение теоремы 3.3 дает

Пример 3.9.

Для функции е

={е

∈

Х} при Х 0 можно записать

1 + X/1! + Х

/2! + ...

Рассмотрим Х 0. Ряд Тейлора для e

запишем в следующем виде:

= х + 1 + x

/3! + x

/2! + x

/5! + x

/4! + x

/7! + ...

Все частичные суммы этого ряда монотонно возрастают при х

∈

(- , 0]. Применяя теорему

3.3, получим для Х 0

Если .

3.1.4. Интервальные векторы и матрицы

Пусть R

- множество всех n-мерных векторов a=(a

,...,a

), a

∈

R, i= . Через I(R

)

обозначим множество всех n-мерных интервальных векторов, т. е. множество упорядоченных

интервалов A=(A

,...,A

), A

∈

I(R

), i= . Аналогично и I( ) есть

соответственно множество всех вещественных и интервальных матриц размера . Так же

как и интервальные числа, будем обозначать интервальные векторы и матрицы прописными

буквами.

Если a

∈

(соответственно ), A

∈

I(R

) (соответственно I( )), то запись a

∈

означает a

∈

i= (соответственноa

∈

ij,

i= , j= ). Точно так же для элементов I(R

I( ) соотношение A B понимается в смысле покомпонентного включения.

Будем считать, что пересечение для интервальных векторов пусто, если

хотя бы для одного i. В противном случае .

Для A=(A

,...,A

), по определению, полагаем

, (3.19)

m(A)=(m(A

), ..., m(A

)).

(3.20)

Далее, норма интервального вектора A есть

, (3.21)

асстояние межд

векто

ами A и B

. (3.22)

Для A

I( ) будем обозначать через m(A) матрицу с элементами m(A

), i,j= ,

, а в качестве нормы используем

. (3.23)

Легко видеть, что если A, B

∈

I(R

) или I( ), то из AB вытекает,.

Если a

∈

, то операторы Pr

определяются равенствами Pr

a=a

, i= .

Система линейных алгебраических уравнений с интервальными коэффициентами

Рассмотрим систему линейных алгебраических уравнений вида

(3.24)

где S

∈

I( ), F

∈

I(R

). Уравнение (3.24) понимается в следующем смысле: требуется найти

множество

∈

S, f

∈

F}.

Обозначим еще ,

i= .

Множество решений может иметь весьма

замысловатую структуру. Например, Хансен показал, что при

изображается на плоскости (u

, u

) в виде невыпуклого восьмиугольника (рис.3.2).

Понятно, что нахождение и точное описание таких множеств в случае n, больших двух,

чрезвычайно затруднительно и вряд ли целесообразно.

В рамках интервального исчисления можно поставить задачу нахождения интервального

вектора U=(U

,...,U

) такого, что , i= .

Оптимальным интервальным

ешением

назовем такой интервальный вектор , компоненты которого удовлетворяют

условиям

i= ,

где inf и su

бе

ру

тся по всем возможным

ешениям , i= .

Рис. 3.2.

Для отыскания интервалов Ui, i= ,применяются как прямые, так и итерационные методы.

Прямые интервальные методы часто представляют собой непосредственное перенесение на

интервальный случай обычных (вещественных) прямых методов. Рассмотрим их применение

на примере метода Гаусса.

3.1.5. Решение систем алгебраических уравнений с интервальными

коэффициентами методом Гаусса

Для системы линейных алгебраических уравнений

su=f (3.25)

с вещественными коэффициентами метод Гаусса можно описать как преобразование

исходной матрицы s к матрице треугольного вида: и

соответствующее преобразование правых частей . При этом

, ,

где

(3.26)

Вообще при и имеют вид

Переход от к , i n-1, осуществляется по формулам

(3.27)

Здесь выписаны только те элементы матрицы и компоненты вектора, которые меняются при

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

(3.28)

Понятно, что для возможности приведения вычислений до конца по формулам (3.26), (3.27)

необходимо, чтобы s

0, Этого всегда можно добиться, когда det s 0,

пе

еставляя, если надо, столбцы пол

чаемых мат

иц

(

и пе

ен

ме

овывая соответств

ющим

образом переменные).

Вернемся теперь к системе (3.24) линейных алгебраических уравнений с интервальными

коэффициентами. В этом случае уже нельзя говорить об исключении неизвестных, так как,

A/A 0 при

(A)>0. Однако по аналогии с вещественным случаем можно преобразовать S к

треугольному виду по формулам (3.26), (3.27), заменяя в них

вещественные коэффициенты интервалами, а вещественные арифметические операции -

интервально - арифметическими:

(3.29)

(3.30)

После этого вычисляем интервалы

(3.31)

Формулы (3.29) - (3.31) дают интервальный вариант метода Гаусса.

Из основной теоремы 3.1 интервальной арифметики непосредственно вытекает

справедливость следующего утверждения :

Теорема 3.4.

Пусть интервалы U

, i= определены формулами (3.29) - (3.31) (то есть в

форм

лах (3.29) - (3.31) не встречается деление на интервал, содержащий н

ль). Тогда для

юбых s

∈

S, f

∈

F решение

системы (7) существует, единственно и

ругими словами, det s 0

∀

∈

S и

Таким образом, если мы можем с помощью (машинной) интервальной арифметики провести

до конца вычисления (на ЭВМ) методом Гаусса, то можно утверждать, что то же самое

справедливо для любой вещественной системы, коэффициенты и правые части которой лежат

в соответствующих интервалах.

В связи со сказанным возникает интересный вопрос. Пусть det s 0

∀

∈

S. Всегда ли можно в

таком случае провести до конца вычисления интервальным методом Гаусса? Ответ

отрицательный. Рассмотрим соответствующий пример.

Пример 3.10

(Райхмана [109]). Рассмотрим интервальную матрицу

Проводя вычисления интервальным методом Гаусса, последовательно получим

Если - (единственный) корень уравнения (1-x

)

-x

=0 из интервала (0,1), то

при x

<1 имеем 0

∈

[1-

/(1-

), 1+

/(1-

)] и мы не можем закончить вычисления

методом Гаусса.

Возьмем

=0,62> и покажем, что для любой матрицы s

∈

S(0,62) dets 0. Матрица

имеет вид

(x, y, z, u, v, w)

∈

D = [0, 0.62] [0, 0.62] [0, 0.62] [0, 0.62] [0, 0.62] [0, 0.62]

и ее оп

еделитель det s = 1 + wx

+ uvz + wz - ux -

v = f

(

, z, u, v, w

)

. Выполняя

несложные, но громоздкие выкладки, нетрудно найти f(x, y, z, u, v, w) >0 при всех (x, y, z, u,

v,w)

∈

D. Итак, изложенный пример показывает, что при переходе от обычного метода Гаусса

к интервальной версии свойства его, вообще говоря, ухудшаются. Результаты проведенных

некоторыми авторами экспериментальных расчетов на ЭВМ также показали, что ширина

вычисляемых интервалов может довольно быстро расти для систем с хорошо

обусловленными матрицами. Тем не менее в случае систем с матрицами некоторых

специальных видов метода Гаусса может дать (и дает) хорошие результаты. Одним из важных

классов таких матриц являются M-матрицы.

Напомним, что вещественная матрица a = (a

)

∈

называется

М-матрицей

, если a

0 для

всех ij и выполнено одно из эквивалентных условий:

1) det a 0 и a

-1

2) a

>0, i= , и спектральный радиус матрицы e-d

-1

a меньше единицы (здесь e=(

) -

единичная матрица, d - диагональная матрица с элементами d

- символ

Кронекера);

3) все собственные значения матрицы a имеют положительные вещественные части;

4) для каждого вектора x такого, что ax 0, имеем x 0.

Следствие.

Если существует М - матрица b такая, что a b, то a- M-матрица.

Интервальная матрица A называется M - матрицей, если M - матрицей является всякая

вещественная матрица a

∈

Теорема 3.5.

Пусть S - интервальная M-матрица, F - неотрицательный интервальный

вектор, то есть f0 для всех f

∈

F. Тогда интервальный вектор можно получить с помощью

интервального метода Гаусса, и он является оптимальным интервальным решением

системы (3.24).

3.1.6. Интервально-аналитический метод прогонки

Рассмотрим метод прогонки для систем с трехдиагональными интервальными матрицами.

Пусть о коэффициентах аi, bi, ci и правых частях fi системы

известно лишь, что они принадлежат заданным интервалам :

∈

Ai, i =1, n;

∈

Bi, i = 0, n;

b0 c0 0 0 0 ....................................0 u0 f0

a1 b1 c1 0 0 ..................................0 u1 f1

0 a2 b2 c2 0 ..................................0 * u2 = f2 =

......................................................... ... ..

0 .......................... 0 an-1 bn-1 cn-1 un-1 fn-1

0 .......................................0 0 an bn un fn