Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v3(3-4)/presic-281-288.pdf Дата изменения: Fri May 8 19:39:50 2009 Дата индексирования: Mon Oct 1 23:42:37 2012 Кодировка: Windows-1251

m-M исчисление
С.Б. Прешич
Это обзорная статья, относящаяся к монографии [1] (а также и [2] второму дополнительному изданию [1]).

Пусть D = [a1 , b1 ] Ч ... Ч [an , bn ] Rn и f : D - R данная функция. Такую функцию будем называть m-M функцией, если Для любого [1 , 1 ] Ч ... Ч [n , n ] D мы можем эффективно найти пару вещественных чисел m(f )(), M (f )(), так что для них выполняются следующие условия (аксиомы m-M исчисления)

m(f )() f (X ) M (f )() для всех D, X ,
diam0

(1) (2)

lim (M (f )() - m(f )()) = 0, где diam :=

(i - i )2 )1/2 .

Числа m(f )(), M (f )() называем обобщенным минимумом и максимумом функции f , а пару m(f )(), M (f )() называем ее m-M парой. Например, для квадратичной функции k (x) = x2 - x, где D = [a1 , b1 ] и a1 > 0 одну m-M пару можно определить так:
2 m(k )() = 1 - 1 , 2 M (k )() = 1 - 1 .

На самом деле, в этом примере мы использовали тот факт, что функция k разность двух неогибающих функций g и h, где g (x) = x2 , h(x) = x. По этой причине имеем следующие формулы

m(k )() = g (1 ) - h(1 ),

M (k )() = g (1 ) - h(1 ).

Аналогичным образом, учитывая равенство sin(x) = (x + sin(x)) - x, для функции f (x) = sin(x) получим следующие формулы

m(f )() = 1 + sin(1 ) - 1 ,

M (f )() = 1 + sin(1 ) - 1 .

(3)


В [1] (также и в [2]) имеется раздел "m-M Algebra в котором описано, как можно эффективно найти m-M пару для разных классов функций. Один из таких классов состоит из функций, задаваемых выражением, построенным из символов +, ћ, -, 2k+1 , exp, sin, cos, min, max (см. [1, 2, Определение 1.1, Леммы 1.1 - 1.4]). Теперь на одной задаче рассмотрим некоторые общие идеи m-M исчисления. Задача 1. Пусть f : [a, b] - R данная m-M функция. Найти все решения уравнения

f (x) = 0,

где x D = [a, b].

(4)

D произвольный отрезок. Вычислим m(f )(). Если m(f )() > 0, тогда, очевидно, не содержит никакого решения уравнения (4). То же самое имеем и в случае, когда справедливо неравенство M (f )() < 0. Учитывая эти факты введем следующее определение. Определение 1. Отрезок D называется возможным, если выполнено условие m(f )() 0 и 0 M (f )().
Из этого определения и аксиом (1), (2) непосредственно вытекают следующие утверждения. *1. Если f (x) = 0 и x D, тогда возможно. *2. Если f (x) = 0, тогда существует > 0 такое, что все diam() < не являются возможными.

Решение с помощью m-M исчисления. Пусть

xс

Следовательно, в m-M исчислении имеется следующий алгоритм, в котором i, Vi вспомогательные переменные, а K число допустимых шагов алгоритма. Алгоритм 1: Шаг 1. Если D невозможно, переходим к Шагу 3. Иначе, положим i = 1, Vi = D и переходим к Шагу 2. Шаг 2. Множество Vi разобьем на объединение некоторых отрезков 1 , ..., k . Пусть f is(i) означает число всех возможных j . Если f is(i) = 0, переходим к Шагу 3. В противном случае, положим i = i + 1. Если i = K , переходим к Шагу 4, а иначе обозначим через Vi объединение всех возможных j и переходим к Шагу 2. 282


Шаг 3. Алгоритм останавливается с заключением: уравнение (4) не имеет ни одного решения. Шаг 4. Полученные возможные j аппроксимативно определяют "возможные"решения уравнения (4) за число шагов K 1 . Основные характеристики этого алгоритма следующие: Обозначим через S множество всех решений x D уравнения (4). Тогда: 10 . Для всякого i = 1, 2, ... имеем S Vi . 20 . Если a S и a D, тогда на некотором шаге для достаточно большого K отрезок j a станет невозможным. 30 . Если K стремится к бесконечности, то имеем равенство


S=
i=1

Vi .

(5)

Заметим, что похожие результаты и алгоритмы имеются для систем уравнений (см. [1, 2, Глава 2. System of equations, system of inequalities]). Далее мы приведем некоторые примеры, в которых, грубо говоря, используется Алгоритм 1 (или очень похожий), и на каждом шаге каждый j разбивается пополам. Пример 1. Найти решения уравнения sin x = 1/x, где x [1, 20]. Пусть [a, b] [1, 20] произвольный отрезок. Тогда, используя (3), видим, что для функции f (x) = sin x - 1/x одна m-M пара определена следующим образом

m(f )[a, b] = a + sin a - b - 1/a,

M (f )[a, b] = b + sin b - a - 1/b.

Имеем следующие результаты: f is(i) - число всех возможных j на i-том шаге, где i = 1, 2, ..., 25 изменяется следующим образом
f f f f f is(1) = 1, is(6), is(11), is(16), is(21), f f f f f is(2) = 2, is(7), is(12), is(17), is(22), f f f f f is(3) = 4, is(8), is(13), is(18), is(23), f f f f f is(4) = 8, is(9), is(14), is(19), is(24), f f f f f is(5), is(10), is(15), is(20), is(25).

Как мы видим, с 5-го шага число f is(i) равно около 16. Следовательно, на каждом шаге мы должны рассматривать не больше
Конечно, таким образом полученные "возможные"решения только приближенно соответствуют некоторому действительному решению. В самом деле, с помощью данного алгоритма нельзя найти точные действительные решения.
1

283


чем 16 ћ 2 (то есть 32) подотрезков. На 25-ом шаге мы получим следующие результаты: Данное уравнение имеет 7 решений, описываемых так:

1.11415595 6.4391157 12.6455307 18.9024819



x x x x

1 3 5 7



1.11415821; 2.77260345 x2 2.77260572; 6.4391191; 9.31724286 x4 9.31724399; 12.6455341; 15.6439972 x6 15.6439983; 18.9024853.

Пример 2. Комплексное уравнение относительно z = x + iy
z 8 + (A7 + iB7 ) z 7 + ... + (A0 + iB0 ) = 0,
где A7 , B7 , ..., A0 , B0 данные действительные числа. Все решения находятся в области [-r, r] Ч [-r, r], где

(3)

r = 1 + max (|ai |/|an |) .
0in-1

Несколько уравнений вида (3) решено до 25 шага2 . Число f is(i) было около 15. Например, в случае

A7 A6 A5 A4 A3 A2 A1 A0

= -0.628871968 = 0.655487601 = 0.794467662 = 0.677786328 = -0.623235982 = 0.552867495 = 0.658555102 = 0.934256145

B B B B B B B B

7 6 5 4 3 2 1 0

= -0.90620273 = 0.109498452 = 0.145832495 = 0.862459254 = 0.945879881 = -0.164039785 = 0.618662189 = 0.147878684

получены следующие решения xj + iyj (j = 1, ..., 8):
-0.34072429 -0.89744046 0.38592756 1.11732647 -0.31065032 -0.70770741 0.64331293 0.73882684 x x x x x x x x
1 3 3 4 5 6 7 8



-0.34072414, -0.89744031, 0.38592771, 1.11732662, -0.31065017, -0.70770711, 0.64331308, 0.73882699,

-0.79305351 -0.30877218 -0.95440849 -0.46066165 0.52192032 0.78685761 0.49212873 1.62219122



y1 y2 y3 y4 y5 y6 y7 y8



- - - -

0.79305336; 0.30877203; 0.95440819; 0.46066150; 0.52192062; 0.78685775; 0.49212888; 1.62219137.

Пример 3. Комплексное уравнение относительно z : ez = z .
2

m-M пара определена по формуле (1.21) из [1] (или [2]).

284


В области [-20, 20] Ч [-20, 20] это уравнение имеет 6 решений xj + iy (j = 1, ..., 6) :

j

2.65319109 x1 2.65319228, -13.94920826 y1 -13.94920731; 2.06227660 x2 2.06227899, -7.58863215 y2 -7.58863020; 0.31813025 x3 0.31813264, -1.33723736 y3 -1.33723497; x4 + iy4 = x3 - iy3 ;
16.

x5 + iy5 = x2 - iy2 ;

x6 + iy6 = x1 - iy1 .

Вычисления проведены до 25-го шага. С 6-го шага f is(i) было около
3

Пример 4. Рассмотрим систему уравнений относительно (x, y , z )
DR ex + x + sin y + cos z = p x3 + esin y - z - ez = q sin(x - z ) + (x + y )5 - x - y - z = r

(p, q , r данные действительные числа). Случай 1: p = 2, q = 0, r = 0, D = [-1, 2] Ч [-2, 1] Ч [-3, 2]. Существует ровно одно решение (x, y , z ) = (0, 0, 0). С 6-ого шага число f is(r) было между 40 и 50. На 24-ом шаге имеем следующий результат

-0.0000152587891 x 0.0000247955322, -0.0000247955322 y 0.0000324249268, -0.00000762939453 z 0.0000114440918.
Случай 2: p = 2, q = 0, r = 0, D = [-5, 5] Ч [1, 5]. Шаг за шагом число f is(r) равно 1, 8, 21, 32, 24, 0. Итак, мы заключаем, что система не имеет решений. Отметим, что в части 4 главы 2 "System of equations, system of inequalities"в [1] обсуждается вопрос о числе f is(i), то есть вопрос конвергенции. В главе 3 "n-Dimensional integrals, innite sums; their m-M pairs"в [1] рассматривается применение m-M исчисления для нахождения nмерного интеграла и суммирования рядов. Пример 5. Найти xy dxdy , где C ond(x, y ) :
C ond(x,y )

0 x 2, 0 y 2,

2 + e ћ (x + y + 2) e

x+1

+e

y +1

.

Решение. Пользуясь на каждом шаге разбиением на 4 (равных)
подотрезка, получим следующие результаты: Шаг 1: 0.0000000000000000 I 0.5625000000000000, 285


Шаг Шаг Шаг Шаг Шаг Шаг Шаг Шаг

2: 3: 4: 5: 6: 7: 8: 9:

0.0278320312500000 0.0950307846069336 0.1179245151579380 0.1239582093403442 0.1255188694198068 0.1259090350460332 0.1259090350460332 0.1259090350460332



I I I I I I I I



0 0 0 0 0 0 0 0

.2424316406250000 .1581497192382812 .1341890022158623 .1281216432544170 .1265613023800256 .1261702301487544 .1259090350460332 .1259090350460332
1 x+2i

, , , , , , , .

В главе 3 в [1] также рассматриваются следующие задачи.

Пример 6. ([1, 2, Пример 3.2.]) Функция f (x) =

Для уравнения f (x) = c, где a x b, a, b, c некоторые константы, имеем следующие результаты. 1) Случай c = 1.5, a = 0, b = 1 : На шаге 20 получим 0.54416 x 0.54417. Числа f is(r) (r = 1, 2, ..., 20) такие:

i=0

.

1, 2, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3, 2, 2, 2, 3, 2, 3, 2, 3.
2) Случай c = 1.5, a = 0.6, b = 1 : Шаг 1: f is(1) = 1; Шаг 2: f is(2) = 1; Шаг 3: f is(3) = 0. Заключение: f (x) = c не имеет решений.

Пример 7. ([1, 2, Пример 3.3]) Функция f (x) =

x

Решено несколько примеров уравнений вида f (x) = c, где a x b и a, b, c константы. До сих пор мы имели дело с понятием m-M пары только для функций. Но как быть в случае такой задачи: Задача 2. Найти x D = [a, b], такое что

0

et 1+t

dt.

(y D) f (x) f (y ),

(6)

где f данная m-M функция. Иными словами, как найти точки x, в которых f достигает минимума. Пусть = [, ] D произвольный отрезок. Основная идея рассуждения следующая: в каком случае в таком не находится ни одного искомого значения x? Обозначим (6) через (x). Это не функция, а формула, условие. Поэтому мы будем определять понятие m-M пары m(), M () так, чтобы импликация

M ()() = (x) = m()()

для x

(7)

была верна. Тогда, естественно, будет возможным в случае, когда условие m()() удовлетворено. 286


Пусть отрезок D разбит на некоторое объединение 1 ...k . Введем следующие обозначения.

m()(i ) := (Y {1 , ..., k } m(f )(i ) M (f )(Y )), M ()(i ) := (Y {1 , ..., k } M (f )(i ) m(f )(Y ),

(8)

где i = 1, ..., k . Тогда не так сложно проверить, что условие (7) выполнено. В связи с этим введем следующее определение. Определение 2. В случае задачи 2 отрезок D называется возможным, если выполнено условие

m()().

(9)

Чтобы решить задачу 2 мы можем воспользоваться алгоритмом, подобным Алгоритму 1. Теперь 1 , ..., k образуют разбиение множества Vi , и квантор (Y ) относится к ним. Очень важно, что в этом случае также справедливо равенство вида (5). Заметим, что в [1, 2] к задачам оптимизации (условной и безусловной) относятся Задача 5.1, Задача 5.2, Задача 5.3. Подчеркнем также, что в [2, Замечание 5.1] описана линейная процедура, с помощью которой можно найти точку локального минимума или седла в случае задачи безусловной оптимизации. Пусть теперь выраж1 , выраж2 обозначают некоторые выражения, построенные из символов действительных чисел, переменных и символов некоторых m-M функций. Далее, обозначим через

F or(<, , , , ѓ, , )
множество всех формул , построенных из формул вида выраж1 < выраж2 , выраж1 выраж2 , логических связок , , ѓ и логических кванторов , присутствующих в виде (x [a, b]), (x [c, d]). Формула

(10)

,

(x [0, 4])(y [3, 5]) y 2 - x2 = z
один из примеров таких формул. Если формула вида (10) не содержит символов <, ѓ, тогда будем говорить, что это позитивная - формула. В главе 4 в [1] "m-M pairs of the rst order formulas; set-theoretical interpretation"для формулы из множества (10) определены m() и M () (см. Определение 4.1), дано общее определение возможных n-мерных промежутков (Определение 4.2), доказана двойная импликация вида (7) 287


([1, 2, 4.4]). Далее, в случае позитивных формул доказано равенство вида (5) (см. [1, 2, Теорема 4.3]). Это самая главная теорема m-M исчисления. В [2, 7. Приложение] дано очень простое доказательство этой теоремы. Грубо говоря, благодаря этой теореме, с помощью алгоритма, похожего на Алгоритм 1 (см. [1, 2, 5.1, 5.2]), можно решить всякую математическую задачу, выраженную некоторой позитивной формулой . Подчеркнем, что с одной стороны к таким задачам принадлежат большинство задач вычислительной математики, интервальной математики, и т.д., а с другой стороны m-M исчисление дает возможность решить многие новые, до сих пор нерешенные задачи. Теперь, для иллюстрации, приведем некоторые примеры из [1] и [2]. Пример 8. (это Пример 5.3) Найти x [1, 2] такое, что справедливо равенство x2 = c, где c константа, про которую известно только, что c [1.69, 1.96]. Основная идея решения. Эта задача логически эквивалентна следующей. Найти x [1, 2] такое, что выполняется следующая формула (c [1.69, 1.96] x2 = c Замечание 1. Эта задача относится к интервальной математике (см. [1, 2, Задача 5.5]). Но она также дает идею, с помощью которой в главе 6 "Finding functions as solutions of a given m-M condition"между прочим, описан метод для нахождения решения дифференциальных уравнений первого порядка. Пример 9. (это [1, 2, Пример 5.1]) Найти
x1 [a1 ,b1 ] x2 [a2 ,b2 ]

min

max f (x1 , x2 ),

где f : [a1 , b1 ] Ч [a2 , b2 ] - R данная m-M функция. Пример 10. Найти z [-7, 25] такое, что выполняется условие

(x [0, 4])(y [3, 5]) y 2 - x2 = z .

Список литературы
[1] Presic S.B. m-M Calculus. Matematiqki Institut. Beograd. 1996. [2] Presic S.B. m-M Calculus. Second revised edition. Matematiqki Institut. Beograd. 1997.

288