WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 ||

В §3 предлагается использовать идею уравнивания строковых (столбцевых) сумм для вычисления наибольшего сингулярного числа несимметричной матрицы. Строится алгоритм, основанный на последовательных умножениях текущей матрицы на ортогональные матрицы двумерного вращения: при умножении слева – изменяются две строки, при умножении справа – два столбца (как известно, сингулярные числа при данных преобразованиях остаются без изменений). В пределе формируется матрица с равными строковыми и столбцевыми суммами, сингулярное число которой известно.

Доказательство сходимости основывается на доказательстве следующих утверждений.

Утверждение 1. Преобразования не меняют сингулярных чисел.

Утверждение 2. Справедливо неравенство, где.

Утверждение 3. На каждом шаге алгоритма справедлива оценка где – одно из сингулярных чисел,,,.

Утверждение 4. Существует.

Утверждение 5. Справедливо неравенство, где, – матрица до преобразования, – матрица после преобразования.

Утверждение 6. Имеет место предельное соотношение.

Теорема 1. Алгоритм сходится к одному из сингулярных чисел:

.

Лемма 1. Пусть векторы Пусть – острый угол между векторами : Тогда существует ортогональная.

Утверждение 7. Справедливо неравенство при.

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

где

где

.

Утверждение 9. Пусть – сингулярные числа. Пусть (по теореме 1). Начиная с некоторого шага алгоритма, матрица имеет левый сингулярный вектор и правый сингулярный вектор, удовлетворяющие условиям:

где,.

Утверждение 10. Пусть - ортогональная матрица, Тогда и представляются в виде:

где – кососимметричная,

Утверждение 11. Начиная с некоторого шага алгоритма где, – точное значение одного из сингулярных числа.

Теорема 2. Алгоритм имеет линейную скорость сходимости.

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

Третья глава посвящается результатам численных экспериментов.

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

  1. Степенной метод.
  2. Приведение матрицы к трехдиагональной форме с последующим применением какого-либо другого метода.
  3. Покоординатная релаксация отношения Релея с циклическим перебором координат.
  4. Покоординатная релаксация отношения Релея с выбором координат наискорейшего спуска.
  5. Градиентная релаксация отношения Релея.
  6. Алгоритм, предложенный в диссертации.
  7. Алгоритм, предложенной в диссертации, который предваряется заменами знаков элементов матрицы.

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

Выполняются следующие эксперименты.

  1. Проведение тестовых экспериментов при фиксированной относительной точности вычислений ( и ), но на разных размерах задачи, варьируемых от 10 до 100, от 100 до 1000.
  2. Проведение тестовых экспериментов при фиксированном размере задачи (, и ), но для разных, варьируемых от до.
  3. Проведение экспериментов при фиксированном размере задачи (), фиксированной относительной точности вычислений (), но на матрицах с различной близостью старших собственных значений, определяемой величиной и варьируемой от до («плохие матрицы») и от до 0.9 («хорошие матрицы»).
  4. Проведение экспериментов при фиксированном размере задачи (, ), фиксированной относительной точности вычислений (), но с различным коэффициентом верхней релаксации, варьируемом от 1.0 до 1.9.

Результаты экспериментов оформлены в виде 13 рисунков (по 7 графиков на каждом), сформированы практические рекомендации по выбору алгоритма в зависимости от условий задачи.

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

  1. Степенной метод, примененный к матрице без явного умножения на.
  2. Степенной метод, примененный к матрице с явным умножением на.
  3. Покоординатная релаксация отношения Релея с циклическим перебором координат.
  4. Покоординатная релаксация отношения Релея с выбором координат наискорейшего спуска.
  5. Градиентная релаксация отношения Релея.
  6. Алгоритм, предложенный в диссертации.
  7. Алгоритм, предложенной в диссертации, который предваряется заменами знаков элементов матрицы.
  8. Алгоритм, предложенный в диссертации, но использующий матрицы отражения вместо матриц вращения.
  9. Приведение матрицы к двухдиагональной форме с последующим применением какого-либо другого метода.
  10. Приведение матрицы к трехдиагональной форме с последующим применением какого-либо другого метода.

Порядок проведения экспериментов аналогичен случаю, когда исследовались алгоритмы вычисления наибольшего собственного числа.

Для сингулярной задачи результаты экспериментов также оформлены в виде 13 рисунков (по 10 графиков на каждом), сформированы практические рекомендации по выбору алгоритма в зависимости от условий задачи.

Список публикаций

  1. Борзых А. Н. О сходимости одного оптимизационного алгоритма вычисления наибольшего собственного значения симметричной матрицы // Записки научных семинаров ПОМИ. Численные методы и вопросы организации вычислений. Т. 346. СПб., 2007. С. 5-20.
  2. Борзых А. Н. Об одном оптимизационном алгоритме, вычисляющем наибольшее сингулярное число вещественной матрицы // Вестн. С-Петерб. ун-та. Серия «Математика. Механика. Астрономия». СПб., 2008. С. 56-67.
  3. Борзых А. Н. Новый алгоритм быстрого решения частичной проблемы собственных значений // Известия СПбГЭТУ «ЛЭТИ». Серия Информатика, управление и компьютерные технологии. Вып. 1. 2004. C. 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.
Pages:     | 1 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»