Инд. авторы:	Шокин Ю.И.
Заглавие:	Об интервальных задачах, интервальных алгоритмах и их трудоемкости
Библ. ссылка:	Шокин Ю.И. Об интервальных задачах, интервальных алгоритмах и их трудоемкости // Вычислительные технологии. - 1996. - Т.1. - № 1. - С.98-115. - ISSN 1560-7534. - EISSN 2313-691X.
Внешние системы:	РИНЦ: 13009723;
Реферат:	rus: В этой методологической работе предлагается формализация понятия интервальной (локализационной) задачи и с позиций трудоёмкости обсуждаются общие свойства интервальных задач и алгоритмов их решения. Концепция последовательно гарантирующего алгоритма, недавно предложенная как разумный компромисс между требованиями гарантированности интервального результата и получения его за практически приемлемое время, распространяется на общие интервальные (локализационные) задачи.
Издано:	1996
Физ. характеристика:	с.98-115
Цитирование:	1. АЛЕФЕЛЬД Г., ХЕРЦБЕРГЕР Ю. Введение в интервальные вычисления. Мир, М., 1987. 2. ВОЩИНИН А. П., СОТИРОВ Г. Р. Оптимизация в условиях неопределённости. МЭИ-Техника, М. - София, 1990. 3. ГЭРИ М., ДЖОНСОН Д. Вычислительные машины, и труднорешаемые задачи. Мир, М., 1982. 4. ДОБРОНЕЦ Б. С, ШАЙДУРОВ В. В. Двусторонние численные методы. Наука, Новосибирск, 1990. 5. КАЛМЫКОВ С. А., ШОКИН Ю. И., ЮЛДАШЕВ 3. X. Методы интервального анализа. Наука, Новосибирск, 1986. 6. КУРОШ А. Г. Лекции по общей алгебре. Наука, М., 1973. 7. ЛАКЕЕВ А. В., НОСКОВ С. И. Описание множества решений линейного уравнения с интервально заданными оператором и правой частью. Докл. Академии наук, 330, №4, 1993, 430-433. 8. ЛАКЕЕВ А. В., НОСКОВ С. И. О множестве решений линейного уравнения с интервально заданными оператором и правой частью. Сиб. матем. журн., 35, 1994, 1074-1084. 9. СУХАРЕВ А. Г. Минимаксные алгоритмы в задачах численного анализа. Наука, М., 1989. 10. Философский Энциклопедический Словарь. Сов. Энциклопедия, М., 1983. 11. ЧЕРНОУСЬКО Ф. Л. Оценивание фазового состояния динамических систем. Наука, М., 1988. 12. ЯКОВЛЕВ А. Г. Машинная арифметика мультиинтервалов. Вопросы, кибернетики. Научн. совет по компл. проблеме "Кибернетика"АН СССР, вып. 125, 1986, 66-81. 13. ЯКОВЛЕВ А. Г. Локусы и локализационные вычисления. В "Интервальная математика: Тез. конф., Саратов, 23-25 мая 1989 г.", Саратов, 1989, 54-56. 14. ADAMS E. Enclosure methods and scientific computations. In "IMACS'1988 Proceedings: 12th World Congress on Scientific Computation", July 18-22, 1988, Paris, France, R. Vichnevetsky, P. Borne and J. Vignes, eds., 1, XVII-XXVI. 15. AUBIN J.-P., FRANKOWSKA H. Set-valued Analysis. Birkhauser, Boston, 1990. 16. BELTRAN M., CASTILLO G, KREINOVICH V. Algorithms that still produce a solution (maybe not optimal) even when interrupted: Shary's idea justified. Reliable Computing, 3, 1997, в печати. 17. DEAN Т. L., BODDY M. An analysis of time dependent planning. In "Proceedings of AAAI-88 Conference", St. Paul, 1988, 49-54. 18. DOBRONETS B. S. On some two-sided methods for solving systems of ordinary differential equations. Interval Computations, 1, №3, 1992, 6-21. 19. FlLIPPOV A. F. Ellipsoidal estimates for a solution of a system of differential equations. Ibid, 2, №4, 1992, 6-17. 20. KELLING В., OELSCHLÄGEL D. Zur Losung von linearen Toleranzproblemen. Wiss. Zeitschrift TH Leuna-Merseburg, 33, №1, 1991, 121-131. 21. KLATTE P., ULLRICH Ch. Complex sector arithmetic. Computing, 24, 1980, 139-148. 22. KOLACZ H. On the optimality of inclusion algorithms. In "Interval Mathematics 1985", Lecture Notes in Computer Science, 212, K. Nickel, ed., Springer Verlag, New York, 1986, 67-80. 23. KREINOVICH V., LAKEYEV A. V., NOSKOV S. I. Optimal solution of interval linear systems is intractable (NP-hard). Interval Computations, 1, 1993, 6-14. 24. KREINOVICH V., LAKEYEV A. V., NOSKOV S. I. Approximate linear algebra is intractable. Linear Algebra Apppl., 232, 1996, 45-54. 25. KREINOVICH V., LAKEYEV A. V., ROHN J. Computational complexity of interval algebraic problems: Some are feasible and some are computationally intractable - A survey. In "Scientific Computing and Validated Numerics", G. Alefeld, A. Frommer and B. Lang, eds., Akademie Verlag, Berlin, 1996, 293-306. 26. KUPRIYANOVA L. Inner estimation of the united solution set of interval linear algebraic system. Reliable Computing, 1, №1, 1995, 15-31. 27. LAKEYEV A. V. Linear algebraic equation in Kaucher arithmetic. In "Reliable Computing 1995", Supplement, Extended Abstracts of APIC'95: Int. Workshop on Applications of Interval Computations, El Paso, TX, February 23-25, 1995, 130-133. 28. LAKEYEV A. V. On the computational complexity of the solution of linear systems with moduli. Reliable Computing, 2, №2, 1996, 125-131. 29. LAVEUVE S. E. Definition einer Kahan-Arithmetic und ihre Implementierung. In "Interval Mathematics", Lecture Notes in Computer Science, 29, K. Nickel, ed., Springer Verlag, New York, 1975, 236-245. 30. MOORE R. E. Interval Analysis. Englewood Cliffs, Prentice Hall, 1966. 31. MOORE R. E. Bounding sets in function spaces with application to nonlinear operator equations. SIAM Review, 20, 1978, 492-512. 32. MOORE R. E. Methods and Applications of Interval Analysis. SIAM, Philadelphia, 1979. 33. MOORE R. E. A survey of interval methods for differential equations. In "Proceedings of 23rd Conference on Decision and Control", Las Vegas, NV, December 1984, 1529-1535. 34. NEUMAIER A. Tolerance analysis with interval arithmetic. Freiburger Intervall, Berichte, 86/9, 1986, 5-19. 35. NEUMAIER A. Interval Methods for Systems of Equations. Cambridge University Press, Cambridge, 1990. 36. NICKEL K. Stability and convergence of monotonic algorithms. J. Math. Anal. Appl, 54, №1, 1976, 157-172. 37. NICKEL K. Interval-analysis. In "The State of the Art in Numerical Analisis: Proc. of the Conference on the State of Art in Numerical Analysis", Univ. of York, April 12th-15th, 1976, D. Jacobs, ed., Univ. of York, 1977, 193-225. 38. NICKEL K. Die Uberschatzung des Wertebereichs einer Funktion in der Intervallrechnung mit Anwendungen auf linearer Gleichungssystemen. Computing, 18, 1977 15-36. 39. NICKEL K. Using interval methods for the numerical solution of ODE's. ZAMM, 66, №11, 1986, 513-523. 40. NUDING E. Intervallrechnung und Wirklichkeit. In "Interval Mathematics", Lecture Notes in Computer Science, 29, K. Nickel, ed., Springer Verlag, Berlin, 1975, 263-269. 41. NUDING E. Schrankentreue Algorithmen. Beitrage zur Numerische Mathematik, 11, 1983, 115-137. 42. OETTLI W. On the solution set of a linear system with inaccurate coefficiets. SIAM J. Numer. Anal, 2, 1965, 115-118. 43. POLJAK S., ROHN J. Checking robust nonsingularity is NP-hard. Math. of Control, Signals & Systems, 6, 1993, 99-105. 44. PETKOVIC M. S., MITROVIC Z. M., PETKOVIC L. B. Arithmetic of circular rings. In "Interval Mathematics 1985", Lecture Notes in Computer Science, 212, K. Nickel, ed., Springer Verlag, New York, 1986, 133-142. 45. RATSCHEK H. Optimal approximations in interval analysis. In "Interval Mathematics 1980", K. Nickel, ed., Academic Press, New York, 1980, 181-202. 46. RATSCHEK H. Interval Mathematics. Contribution to "Enciclopedia of Computer Science and Technology", A.G.Holzman, A. Kent and J.G. Williams, eds., published by Marcel Dekker Inc., New York, in Freiburger Intervall-Berichte, 7, 1987, 1-44. 47. RICHMAN P. L. Computing a submterval of the image. J. of the ACM, 21, 1974, 454-458. 48. ROHN J. Systems of linear interval equations. Linear Algebra Appl, 126, 1989, 39-78. 49. ROHN J. NP-hardness results for linear algebraic problems with interval data. In "Topics in Validated Computations", J. Herzberger, ed., North-Holland, Amsterdam, 1994, 463-471. 50. ROHN J., KREINOVICH V. Computing exact componentwise bounds on solutions of linear system is NP-hard. SIAM J. Matr. Anal. Appl, 16, 1995, 415-420. 51. RUMP S. M., KAUCHER E. Small bounds for the solution of systems of linear equations. Computing Suppl, 2, 1980, 157-164. 52. RUMP S. M. Solving algebraic problems with hign accuracy. In "A New Approach to Scientific Computations", U. Kulish and W. L. Miranker, eds., Academic Press, New York, 1983, 27-49. 53. RUMP S. M. Solution of linear and nonlinear algebraic problems with sharp guaranteed bounds. Computing Suppl, 5, 1984, 147-168. 54. SHARY S. P. A new class of algorithms for optimal solution of interval linear systems. Interval Computations, 2, №4, 1992, 11-22. 55. SHARY S. P. Solving the linear interval tolerance problem. Mathematics and Computers in Simulation, 39, 1995, 53-85. 56. SHARY S. P. On optimal solution of interval linear equations. SIAM J. Numer. Anal., 32, 1995, 610-630. 57. SHARY S. P. Algebraic approach to the interval linear static identification, tolerance and control problems, or One more application of Kaucher arithmetic. Reliable Computing, 2, №2, 1996, 3-33. 58. SHARY S. P. A new approach to the analysis of static systems under interval uncertainty. In "Scientific Computing and Validated Numerics", G. Alefeld, A. Frommer and B. Lang, eds., Akademie Verlag, Berlin, 1996, 118-132. 114 59. SHARY S. P. Algebraic solutions to interval linear equations and their applications. In "Numerical Methods and Error Bounds", G. Alefeld and J. Herzberger, eds., Akademie Verlag, Berlin, 1996, 224-233. 60. SHARY S. P. Algebraic approach in the "outer problem" for interval linear equations. Reliable Computing, 3, №2, 1997, в печати. 61. Verbitskii V. I., Gorban' A. N., Utyubaev G. Sh., Shokin Yu. I. The Moore effect in interval spaces. Soviet Math. Dokl., 39, 1989, 8-11.