Алгоритмы и машинно-независимый пакет программ Jinrlinpack решения плохо обусловленных систем линейных алгебраических уравнений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Условные обозначения.

Введение

Цель работы.

Состояние проблемы .7

Достоверность результатов.13

Научная новизна.13

Практическая значимость .13

Структура работы.14

Основные результаты полученные в диссертации 143 Приведены результаты численных экспериментов по вычислению основных численных характеристик решений систем линейных алгебраических уравнений. Приведен также краткий анализ полученных численных результатов, из которого следует, что метод критических компонент является в среднем лучшим по своим качественным показателям из наиболее известных методов, реализованных в пакетах NAG, CERNLIB, LIBJINR, LINA.

-— По теме диссертации опубликованы 10 работ [85-89; 97-99; 103; 110], которые докладовались на научных семинарах: по методам вычислительной и прикладной математики ЛВТА (ЛИТ), по применению вычислительной техники в научных исследованиях JIBTA (ЛИТ) ОИЯИ, а также на международных конференциях: "Численное моделирование и вычисления в физике" (СМСР-96, Дубна, 16-21 сентября 1996 г.), "Актуальные проблемы вычислительной физики" (МТСР-98, Дубна, 15-20 июня 1998 г.), "Актуальные проблемы вычислительной физики" (МТСР-2000, Дубна, 24-30 июля 2000 г.), а также III научной конференции молодых ученых и специалистов (Дубна, 15-19 февраля 1999 г.), на семинаре Института вычислительной математики РАН (Москва, 17 апреля 2001 г.).

В основу диссертации положены лишь некоторые из научных результатов работ [85—89;97—99; 110].

Благодарности 144

Благодарности

Автор выражает благодарность президенту АН РУ академику Юлдашеву Б.С., академику АН РУ Муминову Т.М., директору ЛИТ д.ф.-м.н. профессору Пузынину И.В., заместителю директора ЛИТ к.ф.-м.н. Коренькову В.В., д.ф.-м.н. профессору Жидкову Е.П., а также дирекции ИЯФ АН РУ за предоставление благоприятных условий для работы над диссертацией.

Автор глубоко благодарен своим научным руководителям д.ф.-м.н. профессору Емельяненко Г.А. и к.ф.-м.н. Рахмонову Т.Т. не только за постановку задач и непосредственное участие в совместно выполненных исследованиях, но и за многие уточнения формулировок и основных результатов, а также помощь в компиляции материала в процессе работы над текстом диссертации.

Автор искренне признателен к.ф.-м.н. Сапожникову А.П., к.ф.-м.н. Кочкину В.И. и Сапожниковой Т.Ф. за очень полезные обсуждения результатов работ, вошедших в диссертацию.

Автор благодарит студентку ВМК МГУ Емельяненко М.Г. и аспирантку университета "Дубна" Коновалову Г.Ю. за творческое сотрудничество и техническую помощь на различных этапах работы в ЛИТ ОИЯИ.

1. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. M-JL, Физматгиз, 1963.

2. Голуб Дж. Ван Лоун Ч. Матричные вычисления. М., "Мир", 1999.

3. Малышев А.Н. Введение в вычислительную линейную алгебру (с приложением алгоритмов на ФОРТРАНе). Новосибирск, "Наука", 1991.

4. Уилкинсон Дж., Райнш К. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра. М., "Машиностроение", 1976.

5. Годунов С. К. Решение систем линейных уравнений. Новосибирск, "Наука", 1980.

6. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. М., "Мир", 1980.

7. Воеводин В.В., Кузнецов Ю.А., Матрицы и вычисления. М., "Наука", 1984.

8. Райе Дж. Матричные вычисления и математическое обеспечение. М., "Мир", 1984.

9. Воеводин В.В. Вычислительные основы линейной алгебры. М., "Наука", 1977.

10. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М., "Наука", 1979.

11. Воеводин В.В. Линейная алгебра. М., "Наука", 1980.

12. Морозов В.А. Регулярные методы решения некорректно поставленных задач. М., "Наука", 1987.

13. Икрамов Х.Д. Численные методы для симметричных линейных систем. М., "Наука", 1988.

14. Крылов В.И., Бобков В.Б., Монастырный П.И. Начала теории вычислительных методов. Линейная алгебра и нелинейные уравнения. Минск, Наука и техника, 1985.

15. Бахвалов Н.С. Численные методы. М.: "Наука", 1973.

16. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М., "Мир", 1969.

17. Simon Horst D. Analysis of the symmetric Lanczos algorithm with reorthogonalization methods. Linear Algebra and Appl., 1984, 61, 101131.

18. Aozen Jan Ole. On the reduction of a symmetric martix to tridiagonal form. "BIT" (Sver.), 1971, 11, No 3, 233-242.

19. Tewarson R.P. On the transformation of symmetric sparse matrices to the triple diagonal form. "Int. J. Comput. Math.", 1970, 2, No 3, 247-258.

20. Schwarz H.R. Tridiagonalization of a symmetric band matrix. "Num. Math.", 1968, 12, No 4, 231-241.

21. Martin R.S., Reinsch C., Wilkinson J.H. Householder's tridiagonalization of a symmetric matrix. "Numer. Math.", 1968, 11, No 3, 181-195. Wilkinson J.H. Householder's method for symmetric matrices. "Num. Math.", 1962, 4, No 4, 354-361.

22. Householder Alston S. Generated error in rotational tridiagonalization. J. Assoc. Comput. Machinery, 1958, 5, No 4, 335-338 (РЖМ, 1960, 7007).

23. Зубатенко B.C. Приведение ленточных симметричных матриц к трехдиагональному виду. В сб. "Машины для инж. расчетов. Вып. 5", Киев, 1972, 67-71.

24. Poige С.С. Error analysis of the lanczos algorithm for tridiagonalizing a symmetric matrix. "J. Inst. Math, and Appl.", 1976, 18, No 3, 341349.

25. Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М., "Наука", 1985.

26. Уилкинсон Дж.Х. Алгебраическая проблема собственных значений. М., "Наука", 1970.

27. Емельяненко Г.А., Им Ен Сек. О методах нахождения собственных векторов вещественных трехдиагональных матриц. Препринт ОИЯИ, Р11-88-736, Дубна, 1985.

28. Самарский А.А., Николаев Е.С. Методы решений сеточных уравнений. М. Наука, 1978.

29. Марчук Г.И., Колесов В.Е. Применение численных методов для расчета нейтронных сечений. Атомиздат, М., 1970.

30. Ильин В.П. Численные методы решения задач электрофизики. М., "Наука", 1985.

31. Артемов В.М. и др. Сообщение ОИЯИ, Р10-94-521, Дубна, 1994.

32. Самарский А.А., Гулин А.В. Численные методы. М., "Наука", 1989.

33. Емельяненко Г.А. Методы обращения квазитрехдиагональных и ленточных матриц. Препринт ОИЯИ, Р11-6933, Дубна, 1973.

34. Бурин Е.А. К решению трехдиагональных систем линейных алгебраических уравнений. В сб. "Материалы 1-й Научно-теор. конференции мол. математиков и механиков г. Алма-Аты". Алма-Ата, 1969, 81-85.

35. Rayney J.W. On Comparatively stable tridiagonalization methods. -Numer. Math., 1969. 13. No 4, 316-322.

36. Evans D. J. An algorithm for the solution of certain tridiagonal systems of linear equations. "Comput. J.", 1972, 15, No 4, p. 356359.

37. Боголюбов А.Н., Телегин В.И. Об одном численном методе решения линейных систем уравнений с трехдиагональной матрицей. "ЖВМ и МФ", 1974, 14, No 3, 768-771.

38. Sumec Jozef, Szobo Vendelin. Riesenie systemu linear-nych algebraic Kech rovnic s trojdiagonalnou maticou. "Appl. mat.", 1977, 22, No 6, p. 470-472.

39. Емельяненко Г.А. О свойствах систем линейных уравнений с неособенными трехдиагональными, ленточными и квазитрехдиаго-нальными матрицами. Дубна. Сообщение ОИЯИ, Р11-85-489, 6 е., 1985.

40. Biiytikkoca Edip, Yamaha Ikiho. An approash for the solution of ill-conditioned linear systems by Gaussian elimination "Fen bilimleri derg. Marmara Univ.", 1986, No 3, p. 89-99.

41. Gao daying. A deconvolution-LU method for solving linear equations. "Numer. Math. J. Chin. Univ.", 1987, 9, No 1, p. 30-39 (chin.); (РЖМ, 1988, 1D33).

42. Vorst Henk A. van. der. Large tridiagonal and block tridiagonal linear systems on vector and parallel computers. "Parallel Comput.", 1987, 5, No 1-2, p. 45-54.

43. You Zhao-yong, Li Lei. The time complexity of tridiagonal Toeplitz systems. "Math, numer. sin.", 1987, 9, No 3, p. 262-265 (chin.).

44. Воеводин А.Ф. Устойчивость метода прогонки для разностьных уравнений. "Динам, сплош. среды" (Новосибирск), 1988, No 84, с. 47-61.

45. Schwanat Н. Cyclic reduction for tridiagonal systems of equations with interval coefficients on vector computers. "SIAM J. Numer. Anal.", 1989, 26, No 3, p. 661-680.

46. Ильин В.П., Кузнецов И.Б., Пинкина Н.А. Исследование устойчивости параллелных алгоритмов решения рекурсивных задач на примере метода прогонки. "Препр. АН СССР. СО. ВЦ", Новосибирск, 1989, No 841, с. 1-18.

47. Пинкина Н.А. Сравнительная анализ ошибок округления решения систем трехточечных уравнений. "Препр. АН СССР. СО. ВЦ", Новосибирск, 1990, No 890, с. 1-27.

48. Kim Hyong Joong, Lee Jang Gyu. A parellel algorithm solving a tridiagonal Teoplitz linear system. "Parallel Comput.", 1990, 13, No 3, p. 289-294.

49. Krechel Arno, Plum Hans-Joachim, Stiiben Klaus. Parallelizatian and vectorization aspects of the solution of tridiagonal linear systems. "Parallel Comput.", 1990, 14, No 1, p. 31-49.

50. Ильин В.П., Пинкина Н.А. Исследование ошибок округления некоторых модификаций метода прогонки. "Моделир. в мех.", 1991, 5, No 1, с. 31-47.

51. Zhao Shuqin. A method to solve the special triple diagonal systems. "Univ. Nat. Sci.", 1990, No 4, p. 10-12 (chin.); (РЖМ, 10D21, 1991).

52. Miiller Silvia М., Scheerer Dieter. A method to parallelize tridiagonal col vers. "Parallel Comput.", 1991, 17, No 2-3, p. 181-188.

53. Brok S.W. Parallel implementation of tridiagonal linear systems on a distributed memory MIMd parallel computer. "Modell. and Simul.: Proc. Eur. Simul. Multiconf.", Nuremberg. June 10-13, 1990. San-Diego (Calif.), 1990, p. 125-130.

54. Hegland Marcus. On the parallel solution of tridiagonal systems by wrap-around partitioning and incomplete LU factorization. "Numer. Math.", 1991, 59, No 5, p. 453-472.

55. Пинкина H.A. Исследование ошибок прямого метода решения на ЭВМ трехдиагональных систем линейных алгебраических уравнений. Нов. подходы к решению диф. ур-й: 3 Всес. конф., Дрогобыч, 17-21 июля, 1991: Тез. докл., М., 1991, с. 40.

56. Bergamaschi L., Bevilacqua P. Symplectic factorizations and parallel iterative algorithms for tridiagonal systems of equations. "Calcolo", 1992, 29, No 3-4, p. 159-191.

57. Остыловский A.H., Пинкина H.A. Применение матричных обозначений при исследовании устойчивости метода прогонки. "Выч. методы и технол. решения задач мат. физ.", РАН. СО. ВЦ. Новосибирск, 1993, с. 157-166.

58. Bevilacqua R., Bozzo Е., Temperanza G., Zellini P. Complexity bounds for solving some tridiagonal systems with preconditioning. "Calcolo", 1993, 30, No 2, p. 127-143.

59. Колотилина Л.Ю., Еремин А.Ю. Разложения Брюа и решение систем линейных уравнений. "Численные анализы и Математическое моделирование", 2 (1987), No 6, 421-436.

60. Молчанов И.Н. Машинные методы решения прикладных задач. Диффиренциальные уравнения. Киев, "Наук, думка", 1988.

61. Wilkinson J.H. Error Analysis of Direct Methods of Matrix Inversion. J. ACM 8, 281-330, 1961.

62. Себер Дж. Линейный регрессионный анализ. М., "Мир", 1980.

63. Емельяненко Г.А. Препринт ОИЯИ, Р11-85-488, Дубна, 1985.

64. Емельяненко Г.А., Рахмонов Т.Т. Сообщение ОИЯИ, Р11-93-249, Дубна, 1993.

65. Емельяненко Г.А. Блочно-трехдиагональные матрицы и методы численного решения спектральных задач. Автореферат докторекой диссертации. ВЦ СО АН СССР. Новосибирск 1992; ОИЯИ 1192-4. Дубна 1992.

66. Emel'yanenko G.A., Rakhmonov Т.Т., Dushanov Б.В. JINR preprint, Ell-96-105, Dubna, 1996.

67. Emel'yanenko G.A., Rakhmonov T.T., Dushanov E.B. JINR preprint, Ell-96-106, Dubna, 1996.

68. Emel'yanenko G.A., Rakhmonov T.T., Dushanov E.B. JINR preprint, Ell-96-107, Dubna, 1996.

69. Emel'yanenko G.A., Emelianenko M.G., Rakhmonov T.T., Dushanov E.B., Konovalova G.Yu. JINR preprint, Ell-98-302, Dubna, 1998.

70. Душанов Э.Б., Емельяненко М.Г., Коновалова Г.Ю. Препринт ОИЯИ, Р11-2000-163, Дубна, 2000.

71. Емельяненко Г.А., Рахмонов Т.Т. Препринт ОИЯИ, Р11-87-533, Дубна, 1987.

72. Емельяненко Г.А. Рахмонов Т.Т. Препринт ОИЯИ, Р11-89-203, Дубна, 1989.

73. Емельяненко Г.А., Рахмонов Т.Т. Препринт ОИЯИ, Р11-93-248, Дубна, 1993.

74. Емельяненко Г.А. Рахмонов Т.Т. Сообщение ОИЯИ, Р11-93-250, Дубна, 1993.

75. Емельяненко Г.А., Рахмонов Т.Т. Препринт ОИЯИ, Р11-93-265, Дубна, 1993.

76. Емельяненко Г.А., Рахмонов Т.Т. Препринт ОИЯИ, Р11-93-266, Дубна, 1993.

77. Ланкастер П. Теория матриц. М., "Наука", 1973.

78. Международная Конференция МТСР-98, Дубна, 15-20 июня 1998 г.

79. Труды III научной Конференции молодых ученых и специалистов. Дубна, 15-19 февраля 1999 г.

80. Труды Международной Конференции МТСР-2000, Дубна, 24-30 июля 2000 г.1. Список литературы 152

81. Фаддеева В.Н., Колотилина Л.Ю. Вычислительные методы линейной алгебры: Набор матриц для тестирования, ч.1, 2, 3 (Материалы по мат. обеспечению ЭВМ), Ленинград, 1982.

82. Федорова Р. Н., Широкова А. И. Библиотека программ на ФОРТРАНе. т. VI-VII. Описание программ. Дубна, 1990.

83. CERNLIB — CERN Program Library (Short Writeups). Application Software Group. Computing and Networks Division. CERN, Geneva, Switzerland (May, 1993).

84. Новости ОИЯИ (JINR News). Информационный бюллетень ОИЯИ: 3, 1996, стр. 12; 1, 2001, стр. 7-8.

85. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. I. М., "Наука", 1969.

86. Майерс Г. Архитектура современных ЭВМ. М., "Мир", 1985.

87. Трифонов Н.П., Громыко В.И. Программирование на автокоде ЕС ЭВМ. М., "Наука", 1985.

88. Криницкий Н.А., Миронов Г.А., Фролов Г.Д. Программирование и алгоритмические языки. М., "Наука", 1979.

89. Белецки Я. Фортран 77. М., "Высшая школа", 1991.

90. Емельяненко Г.А., Рахмонов Т.Т. Препринт ОИЯИ, Р11-88-598, Дубна, 1988.

91. Емельяненко Г.А., Душанов Э.Б., Емельяненко М.Г., Рахмонов Т.Т., Сапожников А.П. Сообщение ОИЯИ, Р11-2000-287, Дубна, 2000.

92. Виницкий С.И., Пузынин И.В., Чулуунбаатар О. Препринт ОИЯИ, Р11-2001-61, Дубна, 2001.