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

• Борзых, Алексей Николаевич
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Борзых, Алексей Николаевич

Используемые обозначения.

Глава 1. Введение.

§1. Классификация задач на собственные числа.

§2. О предмете данной диссертации.

§3. Актуальность задачи.

§4. Обор методов, вычисляющих наибольшее собственное число симметричной матрицы.

§5. Обзор методов, вычисляющих наибольшее сингулярное число несимметричной матрицы.

Глава 2. О новых методах решения частичной проблемы собственных значений.

§1. Идея новых алгоритмов.

§2. О новом методе вычисления наибольшего собственного значения симметричной матрицы.

§3. О новом методе вычисления наибольшего сингулярного значения несимметричной матрицы.

§4. Приближенное решение тригонометрического уравнения.

§5. Оценка сложности одного шага новых методов.

§6. Критерии остановки, обеспечивающие заданную точность.

§7. Прием, позволяющий увеличить сумму элементов матрицы с помощью замен знаков элементов матриц.

§8. Использование матриц отражения вместо матриц вращения.

§9. Техника верхней релаксации.

Глава 3. Результаты численных экспериментов.

§ 1. Проверка сходимости предложенных алгоритмов.

§2. Вычисление наибольшего собственного числа симметричной матрицы.

§3. Вычисление наибольшего сингулярного числа несимметричной матрицы.

Введение диссертации (часть автореферата) на тему «О новых методах решения частичной проблемы собственных значений»

§1. Классификация задач на собственные числа Перечислим некоторые возможные постановки проблемы собственных значений. 1) Полная проблема собственных значений. Заключается в задаче поиска всех собственных чисел заданной матрицы. В некоторых случаях вычисление также и собственных векторов. 2) Частичная проблема собственных значений. Заключается в вычислении некоторого подмножества собственных чисел, а также, возможно, требуется соответствующих им собственных векторов. Этим подмножеством может быть: а) к наибольших (наименьших) собственных чисел; б) собственные значения, принадлежащие заданному интервалу. С другой стороны, при решении проблемы собственных значений все матрицы разбиваются на два класса, существенно различающих по свойствам: эрмитовы матрицы (в вещественном случае симметричные) и неэрмитовы (в вещественном случае нессиметричные). По этому признаку выделяют симметричную проблему собственных значений и несимметричную. Каждый из этих классов в свою очередь может быть разбит на подклассы. При этом удобно выделять в подклассы матрицы, для которых развиты какиенибудь специальные методы или имеются эффективные модификации методов, применяемых в общем случае. Отдельной задачей, представляющей существенный интерес для различных инженерных расчетов, выделяют проблему собственных значений для матрицы АА (или А А), то есть задачу вычисления сингулярных чисел (возможно, и сингулярных векторов). Для задач подобного рода имеется отдельная группа алгоритмов.Для задач средних размеров, матрицы которых могут быть целиком размещены в оперативной памяти, используются обычно численные методы, основанные на итерационном приведении исходной матрицы А общего вида с помощью преобразований подобия к матрице В специального вида (например, диагонального или треугольного), для которой проблема собственных значений решается достаточно просто. В целях экономии памяти для некоторых матриц (симметричных, ленточных, симметричных) может быть использована компактная форма хранения. Для задач больших размеров, матрицы которых, как правило, являются разреженными, обеспечивающих возможно как использование хранение специальных данных в памяти, методов, так и компактное оптимальную по сложности реализацию алгоритма (см., например, [12]). Наибольший интерес представляют следующие типы матриц: вещественные симметричные, вещественные несимметричные, разреженные, симметричные трехдиагональные, почти треугольные). Классификации матриц и видов решаемых задач представлены на рис. 1 и 2. матрицы Хессенберга (несимметричные Виды матриц А Симметричная Несимметричная т, Плотная Плотная "W Разреженная >w Разреженная Трехдиагональная e H T O шая) г Почти треугольная Симметричная проблема собственных значений Несимметричная проблема собственных значений Рис. 1.Виды задач Искать все собств. числа Искать собств. векторы Не искать собств. векторы Искать несколько собств. чисел Искать собств. векторы Не искать собств. векторы Полная проблема собственных значений Частичная проблема собственных значений Рис. 2.§2. О предмете данной диссертации Предметом данной диссертации являются новые алгоритмы: 1) Алгоритм, вычисляющий наибольшее собственное число симметричной вещественной матрицы; 2) Алгоритм, вычисляющий наибольшее сингулярное число несимметричной вещественной матрицы. Идея алгоритмов представлена в §1 главы 2. Вычислительные схемы и доказательства сходимости предложенных алгоритмов даны в §2 и §3 главы 2. Параграфы 4, 5 и 6 дают необходимую программной реализации предложенных информацию для эффективной алгоритмов. Параграфы 7, 8, 9 описывают возможные модификации предложенных алгоритмов.

Заключение диссертации по теме «Вычислительная математика», Борзых, Алексей Николаевич

Заключение

В диссертации получены следующие научные результаты.

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

2. Линейная сходимость предложенных алгоритмов теоретически доказана, эмпирически проверена.

3. Установлена связь между предложенными алгоритмами и методом релаксации отношения Релея.

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

5. Установлены оптимальные критерии, позволяющие останавливать вычислительный процесс при достижении заданной точности.

6. Предлагаются некоторые модификации, позволяющие ускорить сходимость (в частности, применение техники верхней релаксации).

7. Построена вычислительная схема, позволяющая применять матрицы отражения вместо матриц вращения.

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

Публикации по теме диссертации

1. Борзых А. Н. О сходимости одного оптимизационного алгоритма вычисления наибольшего собственного значения симметричной матрицы // Записки научных семинаров ПОМИ. Численные методы и вопросы организации вычислений. Т. 346. СПб., 2007. С. 5-20.

2. Борзых А. Н. Об одном оптимизационном алгоритме, вычисляющем наибольшее син1улярное число вещественной матрицы // Вестн. С-Петерб. ун-та. Серия «Математика. Механика. Астрономия». СПб., 2008. С. 56-67.

3. Борзых А. Н. Новый алгоритм быстрого решения частичной проблемы собственных значений // Известия СПбГЭТУ «ЛЭТИ». Серия Информатика, управление и компьютерные технологии. Вып. 1. 2004. С. 27-36.

4. Борзых А. Н. Эффективный подход к решению на ЭВМ частичной проблемы собственных значений // Материалы семинаров политехнического симпозиума. Май-июнь 2004 г. Изд-во СПбГПУ. 2004. С. 28-29.

5. Борзых А. Н. Эффективный подход к решению на ЭВМ частичной проблемы собственных значений // Девятая Санкт-Петербургская ассамблея молодых ученых и специалистов. Изд-во СПбГУ. 2004. С. 18.

6. Борзых А. Н. Оптимизация алгоритмов вычисления собственных чисел симметричной матрицы // Математика. Компьютер. Образование. Тезисы. Вып. №12. М.; Ижевск: РХД, 2005. С. 86.

7. Борзых А. Н. Анализ динамики сходимости различных методов решения частичной проблемы собственных значений // Научная сессия МИФИ-2005: Сборник научных трудов. Т. 12. Изд-во МИФИ. 2005. С. 173-174.

8. Борзых А. Н. Оценка спектрального радиуса трехдиагональной матрицы // Материалы семинаров политехнического симпозиума. Июнь 2005 г. Изд-во СПбГПУ. 2005. С. 9-13.

9. Борзых А. Н. Оценка спектрального радиуса плотной симметричной матрицы // Труды политехнического симпозиума. Апрель — декабрь 2004 г. Изд-во СПбГПУ. 2005. С. 53-54.

10.Борзых А. Н. Вычислительная сложность методов расчета максимального собственного значения симметричной матрицы // Известия СПбГЭТУ «ЛЭТИ». Сер. Информатика, управление и компьютерные технологии. 2005. Вып. 1/2005. С. 48-56.

11 .Борзых А. Н. Исследование и анализ методов расчета собственных значений симметричных матриц // Десятая Санкт-Петербургская ассамблея молодых ученых и специалистов. Изд-во СПбГУ. 2005. С. 14.

12. Борзых А. Н. Эффективная локализация собственных значений симметричных матриц высокого порядка // Научная сессия МИФИ-2006. Сборник научных трудов. Т. 7. Изд-во МИФИ. 2006. С. 159-160.

13. Борзых А. Н. Об одном алгоритме вычисления максимального собственного значения симметричной матрицы // Математика. Компьютер. Образование. Тезисы. Вып. №15. М.; Ижевск: РХД, 2008. С. 50.

Список литературы диссертационного исследования кандидат физико-математических наук Борзых, Алексей Николаевич, 2008 год

1. Вазов В., Форсайт. Дж. Разностные методы решения дифференциальных уравнений в частных производных. М.: Изд-во иностранной литературы, 1963.

2. Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1988.

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

4. Голуб Дж., Ван Лоун Ч. Матричные вычисления / Дж. Голуб, Ч. Ван Лоун; под ред. В. В. Воеводина; пер. с англ. М.: Мир, 1999.

5. Деммель Дж. Вычислительная линейная алгебра / пер. с англ. X. Д. Икрамова. М.: Мир, 2001.

6. Измаилов А. Ф., Солодов М. В. Численные методы оптимизации. М.: ФИЗМАТЛИТ, 2003.

7. Икрамов X. Д. Несимметричная проблема собственных значений. М.: Наука, 1991.

8. Ланкастер П. Теория матриц / Пер. с англ. С. П. Демушкина. М.: Наука, 1982.

9. Марчук Г. И. Методы вычислительной математики. М.: Наука, 1989.

10. Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. М.: Наука, 1987.

11. Парлетт Б. Симметричная проблема собственных значений / Пер. с англ. X. Д. Икрамова, Ю. А. Кузнецова. М.: Мир, 1983.

12. Тьюарсон Р. Разреженные матрицы / пер. с англ. Э. М. Пейсаховича; под ред. X. Д. Икрамова. М: Мир, 1977.

13. Уилкинсон Дж. X. Алгебраическая проблема собственных значений / Пер. с англ. В. В. Воеводина, В. Н. Фаддеевой. М.: Наука, 1970.

14. Уоткинс Д. С. Основы матричных вычислений / Д. Уоткинс; пер. с англ. М.: Бином, 2006.

15. Фаддеев Д. К., Фадцеева В. Н. Вычислительные методы линейной алгебры. СПб: Лань, 2002.

16. Хейгеман Л., Янг Д. Прикладные итерационные методы / Пер. с англ. А. Ю. Еремина, И. Е. Капорина; Под ред. Ю. А. Кузнецова. М.: Мир, 1986.

17. Bauer F. L., Fike С. Т. Norms and exclusion theorems // Numerische Math. 2. 1960, pp. 137-141.

18. Davis Ch., Kahan W. M. Some new bounds on perturbation of subspaces. Bull. Amer. Math. Soc. Vol. 75, Number 4, 1969, pp. 863-868.

19. Davis Ch., Kahan W. M. The rotation of eigenvectors by a perturbation. 1П, SIAM J. Numer. Anal. Vol. 7, No. 1, March 1970, pp. 1-46.

20. Householder A. S., Unitary Triangularization of a Nonsymmetric Matrix, Journal ACM, 5 (4), 1958, pp. 339-342.

21. Luo Z. Q., Tseng P. On the convergence of the coordinate descent method for convex differentiable minimization // Journal of Optimization Theory and Applications. Vol. 72, No. 1, January 1992, pp. 7-35.