Инд. авторы:	Шарый С.П.
Заглавие:	Оптимальное внешнее оценивание множеств решений интервальных систем уравнений. Часть 1
Библ. ссылка:	Шарый С.П. Оптимальное внешнее оценивание множеств решений интервальных систем уравнений. Часть 1 // Вычислительные технологии. - 2002. - Т.7. - № 6. - С.90-113. - ISSN 1560-7534. - EISSN 2313-691X.
Внешние системы:	РИНЦ: 13024936;
Реферат:	eng: A new class of adaptive and sequentially guaranteeing parameter partitioning methods (PPS-methods) for computing optimal (exact) component-wise bounds of the solution sets to interval linear systems of equations is presented. A possible generalization of the new technique to the general nonlinear case is considered. The results of numerical calculations and the comparison to other known approaches for solving the given problem are presented. rus: Представлен новый класс адаптивных и последовательно гарантированных PPS методы для точного решения интервальных систем линейных уравнений.
Издано:	2002
Физ. характеристика:	с.90-113
Цитирование:	1. Шарый С. П. Алгебраический подход к анализу линейных статических систем с интервальной неопределенностью // Изв. РАН. Теория и системы управления. 1997. № 3. С. 51-61. 2. Шарый СП. Новый подход к анализу статических систем с интервальной неопределенностью в данных // Вычисл. технологии. 1997. Т. 2, № 1. C. 84-102. 3. Шарый СП. Внешнее оценивание обобщенных множеств решений интервальных линейных систем // Вычисл. технологии. 1999. Т. 4, № 4. С. 82-110. 4. Shary S. P. Algebraic solutions to interval linear equations and their applications // Numerical Methods and Error Bounds / G. Alefeld, J. Herzberger (Eds). Berlin: Akad. Verlag, 1996. P. 224-233. 5. Shary S. P. Interval Gauss-Seidel method for generalized solution sets to interval linear systems // MISC'99 - Workshop on Applications of Interval Analysis to Systems and Control, Girona, Spain, Feb. 24-26, 1999. Girona: Univ. de Girona, 1999. P. 51-65. 6. Shary S. P. Outer estimation of generalized solution sets to interval linear systems // Reliable Computing. 1999. Vol. 5. P. 323-335. 7. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987. 8. Добронец Б. С, Шайдуров В. В. Двусторонние численные методы. Новосибирск: Наука, 1990. 9. Калмыков С. А., Шокин Ю. И., Юлдашев З. Х. Методы интервального анализа. Новосибирск: Наука, 1986. 10. Шарый С. П. Алгебраический подход во "внешней задаче" для интервальных линейных систем // Вычисл. технологии. 1998. Т. 3, № 2. С. 67-114. 11. Barth W., Nuding E. Optimale Losung von Intervallgleichungssystemen // Computing. 1974. Vol. 12. P. 117-125. 12. Beeck H. Uber die Struktur und Absch¨atzungen der Losungsmenge von linearen Gleichungssystemen mit Intervallkoeffizienten // Computing. 1972. Vol. 10. P. 231-244. 13. Cope J., Rust B. Bounds on solutions of linear systems with inaccurate data // SIAM J. Numer. Analysis. 1979. Vol. 16, № 6. P. 950-963. 14. Garloff J. Block methods for the solution of linear equations // SIAM J. Matrix Analysis Appl. 1990. Vol. 11. P. 89-106. 15. Gay D. M. Solving interval linear equations // SIAM J. Numer. Analysis. 1982. Vol. 19, № 4. P. 858-870. 16. Hansen E. Bounding the solution of interval linear equations // SIAM J. Numer. Analysis. 1992. Vol. 29, № 5. P. 1493-1503. 17. Hansen E. Global Optimization Using Interval Analysis. N.Y.: Marcel Dekker, 1992. 18. Hartfiel D.J. Concerning the solution set of Ax = b where P ≤ A ≤ Q and p ≤ b ≤ q // Numer. Mathematik. 1980. Vol. 35, № 3. P. 355-359. 19. Jansson C. Calculation of exact bounds for the solution sets of linear interval systems // Linear Algebra Appl. 1997. Vol. 251. P. 321-340. 20. Kearfott R. B. Rigorous Global Search: Continuous Problems. Dordrecht: Kluwer, 1996. 21. Kolev L. V. Interval Methods for Circuit Analysis. Singapore: World Sci. 1993. 22. Madsen K., Toft O. A parallel method for linear interval equations // Interval Computations. 1994. № 3. P. 81-105. 23. Moore R. E. Methods and Applications of Interval Analysis. SIAM, Philadelphia, 1979. 24. Neumaier A. Linear interval equations // Interval Mathematics 1985/ K. Nickel (Ed.) N. Y.: Springer Verlag, 1986. P. 109- 120. (Lecture Notes in Computer Science; Vol. 212). 25. Neumaier A. Interval Methods for Systems of Equations. Cambridge: Cambridge Univ. Press, 1990. 26. Neumaier A. A simple derivation of Hansen-Bliek-Rohn-Ning-Kearfott enclosure for linear interval equations // Reliable Computing. 1999. Vol. 5, № 2. P. 131 - 136. 27. Nickel K. Die Uberschatzung des Wertebereiches einer Funktion in der Intervallrechnung mit Anwendungen auf lineare Gleichungssysteme // Computing. 1977. Vol. 18. P. 15-36. 28. Ning S., Kearfott R. B. A comparison of some methods for solving linear interval equations // SIAM J. Numer. Analysis. 1997. Vol. 34, № 4. P. 1289-1305. 29. Oettli W. On the solution set of a linear system with inaccurate coefficients // SIAM J. Numer. Analysis. 1965. Vol. 2, № 1. P. 115-118. 30. Oettli W., Prager W. Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides // Numer. Mathematik. 1964. Vol. 6. P. 405 - 409. 31. Rohn J. Systems of linear interval equations // Linear Algebra Appl. 1989. Vol. 126. P. 39-78. 32. Rohn J. Cheap and tight bounds: the recent result by E. Hansen can be made more efficient // Interval Computations. 1993. № 4. P. 13-21. 33. Rump S. M. Solution of linear and nonlinear algebraic problems with sharp guaranteed bounds // Computing Suppl. 1984. Vol. 5. P. 147-168. 34. Rump S. M. Verification methods for dense and sparce systems of equations // Topics in Validated Numerics / J. Herzberger (Ed.). Amsterdam: Elsevier, 1994. P. 63-135. 35. Shary S. P. On optimal solution of interval linear equations // SIAM J. Numer. Analysis. 1995. Vol. 32, № 2. P. 610-630. 36. Shary S. P. Algebraic approach in the "outer problem" for interval linear equations // Reliable Computing. 1997. Vol. 3, № 2. P. 103-135. 37. Kolacz H. On the optimality of inclusion algorithms // Interval Mathematics 1985 / K. Nickel (Ed.) N.Y.: Springer Verlag, 1986. P. 67-80. (Lecture Notes in Computer Science; Vol. 212). 38. Ratschek H. Optimal approximations in interval analysis // Interval Mathematics 1980/ K. Nickel (Ed.). N.Y.: Acad. Press, 1980. P. 181-202. 39. Nuding E. Intervallrechnung und Wirklichkeit // Interval Mathematics / K. Nickel (Ed.) Berlin: Springer Verlag, 1975. P. 263-269. (Lecture Notes in Computer Science; vol. 29). 40. Nickel K. Interval-Analysis // The state of the art in numerical analysis: Proc. of the Conf. on the State of Art in Numerical Analysis, Univ. of York, April 12th-15th, 1976 / D. Jacobs (Ed.). York: Univ. of York, 1977. P. 193-225. 41. Nuding E. Schrankentreue Algorithmen // Beitrage zur Numer. Mathematik. 1983. Vol. 11. P. 115-137. 42. Гаганов А. А. О сложности вычисления интервала значений полинома от многих переменных // Кибернетика. 1985. № 4. С. 6-8. 43. Лакеев А. В., Носков С. И. Описание множества решений линейного уравнения с интервально заданными оператором и правой частью // Докл. РАН. 1993. Т. 330, № 4. С. 430-433. 44. Лакеев А. В., Носков С. И. О множестве решений линейного уравнения с интервально заданными оператором и правой частью // Сиб. мат. журнал. 1994. Т. 35, № 5. С. 1074-1084. 45. Heindl G., Kreinovich V., Lakeyev A. Solving linear interval systems is NP-hard even if we exclude overflow and underflow // Reliable Computing. 1998. Vol. 4. P. 383-388. 46. Kreinovich V., Lakeyev A. V., Noskov S. I. Optimal solution of interval linear systems is intractable (NP-hard) // Interval Computations. 1993. № 1. P. 6-14. 47. Kreinovich V., Lakeyev A. V., Noskov S. I. Approximate linear algebra is intractable // Linear Algebra Appl. 1996. Vol. 232. P. 45-54. 48. Kreinovich V., Lakeyev A., Rohn J., Kahl P. Computational Complexity and Feasibility of Data Processing and Interval Computations. Dordrecht: Kluwer, 1997. 49. Lakeyev A. V. Linear algebraic equations in Kaucher arithmetic // Reliable Computing, 1995, Supplement (Extended Abstracts of APIC'95: International Workshop on Applications of Interval Computations, El Paso, TX, Febr. 23-25, 1995). P. 130-133. 50. Lakeyev A. V. On the computational complexity of the solution of linear systems with moduli // Reliable Computing. 1996. Vol. 2, № 2. P. 125-131. 51. Poljak S., Rohn J. Checking robust nonsingularity is NP-hard // Math. of Control, Signals & Systems. 1993. Vol. 6. P. 99-105. 52. Rohn J. NP-hardness results for linear algebraic problems with interval data // Topics in Validated Numerics / J. Herzberger (Ed.). Amsterdam: North-Holland, 1994. P. 463- 471. 53. Rohn J., Kreinovich V. Computing exact componentwise bounds on solutions of linear system is NP-hard // SIAM J. Matrix Analysis Appl. 1995. Vol. 16. P. 415-420. 54. Coxson G., de Marco C. The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix // Math. of Control, Signals and Systems. 1995. Vol. 7. P. 279-291. 55. Coxson G. E. Computing exact bounds on elements of an inverse interval matrix is NP-hard // Reliable Computing. 1999. Vol. 5. P. 137- 142. 56. Jansson C. An NP-hardness result for nonlinear systems // Reliable Computing. 1998. Vol. 4. P. 345 - 350. 57. Лакеев А. В. Вычислительная сложность оценивания обобщенных множеств решений интервальных линейных систем // Методы оптимизации и их приложения: Тр. XI Междунар. Байкальской школы-семинара. Иркутск, Байкал, 5-12 июля 1998 г. Cекция 4. Иркутск: ИСЭМ, 1998. С. 115-118. 58. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 59. Сухарев А. Г. Минимаксные алгоритмы в задачах численного анализа. М.: Наука, 1989. 60. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. 61. Панков П. С. Алгоритм доказательного поиска экстремума с использованием миноранты по области // Изв. АН Киргиз. ССР. 1979. № 6. C. 12, 13. 62. Панков П. С. Алгоритмы доказательства устойчивых утверждений и глобальной оптимизации в ограниченной области. Фрунзе, 1984. 13 с. Деп. в ВИНИТИ, № 5250-84Деп. 63. Asaithambi N. S., Shen Zuhe, Moore R. E. On computing the range of values // Computing. 1982. Vol. 28, № 3. P. 225-237. 64. Ratschek H., Rokne J. New Computer Methods for Global Optimization. Chichester, N. Y.: Ellis Horwood, Halsted Press, 1988. 65. Шарый С. П. Новый класс алгоритмов для оптимального решения интервальных линейных систем // Актуальные проблемы прикладной математики: Тр. конф. Саратов, 20-22 мая 1991. Саратов, 1991. С. 113-119. 66. Shary S. P. A new class of algorithms for optimal solution of interval linear systems // Interval Computations. 1992. № 2(4). P. 18-29. 67. Шарый СП. Оптимальное внешнее оценивание множеств решений интервальных систем уравнений. Часть 2 // Вычисл. технологии. 2003. (В печати). 68. Apostolatos N., Kulisch U. Grundzuge einer Intervallrechnung fur Matrizen und einige Anwendungen // Electron. Rechenanl. 1968. B. 10. S. 73-83. 69. Gay D. M. Computing perturbation bounds for nonlinear algebraic equations // SIAM J. Numer. Analysis. 1983. Vol. 20. P. 638-651. 70. Gregory R.T, Karney D.L. A Collection of Matrices for Testing Computational Algorithms. N. Y.: Wiley Interscience, John Wiley, 1969. 71. Neumaier A. Rigorous sensitivity analysis for parameter-dependent systems of equations // J. Math. Analysis Appl. 1989. Vol. 144. P. 16-25. 72. Rump S. M., Kaucher E. Small bounds for the solution of systems of linear equations // Computing Suppl. 1980. Vol. 2. P. 157-164. 73. Schwandt H. Iterative methods for systems of equations with interval coefficients and linear form // Computing. 1987. Vol. 38, № 2. P. 143-161. 74. Schwandt H. Cyclic reduction for tridiagonal systems of equations with interval coefficients on vector computer // SIAM J. Numer. Analysis. 1989. Vol. 26, № 3. P. 661-680. 75. Shary S. P. Optimal solution of interval linear algebraic systems. Pt I // Interval Computations. 1991. Vol. 1, № 2. P. 7-30.