Построение единой программной среды для решения задач глобальной оптимизации (стр. 9 из 9)

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

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

Литература

1. Iwaarden R. Van, An Improved Unconstrained Global Optimization Algorithm, PhD thesis, Department of Mathematics, University of Colorado at Denver, 1996. URL http://ww.cs.hope.edu/~rvaniwaa/phd.ps.gz.

2. Moore R. E., Interval analysis. New York, Prentice-Hall, 1966.

3. Glassner A., Space subdivision for fast ray tracing. // IEEE Computer Graphics & Application, 1994.

4. IEEE Standard for Binary Floating-Point Arithmetic. ANSI/IEEE Std 754-1985, IEEE, New York, 1985.

5. Comba J.L.D., Stolfi J., Affine arithmetic and its applications to computer graphics, in Proceedings of VI SIBGRAPI (Brazilian Symposium on Computer Graphics and Image Processing), 1993, pp. 9-18. URL http://dcc.unicamp.br/~stolfi/.

6. Figueiredo L.H. DE, Surface intersection using affine arithmetic, in Proceedings of Graphics Interface '96, May 1996, pp. 168-175. URL ftp://csg.uwaterloo.ca/pub/lhf/gi96.ps.gz.

7. Figueiredo L.H. DE, Stolfi J., Adaptive enumeration of implicit surfaces with affine arithmetic, Computer Graphics Forum, 15 (1996), pp. 287-296.

8. Figueiredo L.H. DE, Stolfi J., Iwaarden R. Van, Branch-and-bounds methods for unconstrained global optimization with affine arithmetic.

9. Farouki R., Rajan V., Algorithms for polynomials in Bernstein form, Computer Aided Geometric Design, 5 (1988), pp. 1-26.

10. Gill P.E., Murray W., Wright H., Practical Optimization, Academic Press, San Diego, CA, 1981.

11. Hansen E., A generalized interval arithmetic, in Interval Mathematics, K. Nickel, ed., no. 29 in Lecture Notes in Computer Science, Springer Verlag, 1975, pp. 7-8

12. Назаренко Т.И., Марченко Л.В., Введение в интервальные методы вычислительной математики, 1982

13. Калмыков С.А., Шокин Ю.И., Юлдашев З.Х., Методы интервального анализа, 1986

14. Шокин Ю.И., Интервальный анализ, 1981

15. Кнут Д., Искусство программирования для ЭВМ, Т.1, 1976

16. Коллатц Л., Крабс В., Теория приближений. Чебышевские приближения и их приложения, Москва “Наука” 1978

Приложение
Примеры оценивания диапазонов функций

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

Рис. 1. , ¦(¦(x)) оценивается на отрезке [-1,1] c шагом 0.0125 в интервальной арифметике.

Рис. 2.

, ¦(¦(x)) оценивается на отрезке [-1,1] c шагом 0.0125 в аффинной арифметике.

Рис. 3. , ¦(¦(x)) оценивается на отрезке [-1,1.2] c шагом 0.0126 в интервальной арифметике.

Рис. 4. , ¦(¦(x)) оценивается на отрезке [-1,1.2] c шагом 0.0126 в аффинной арифметике.