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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Общая характеристика работы

Актуальность темы диссертационной работы

Проблема собственных значений в различных ее постановках (полная или частичная, симметричная или несимметричная) является задачей вычислительной математики, интерес к которой не угасает уже много десятилетий. Задачи подобного рода, с одной стороны, достаточно часто возникают в разнообразных инженерных расчетах, приводя к матрицам, как правило, больших размерностей; с другой стороны, имеют кубическую зависимость объема вычислений от размера задачи, что требует существенного времени счета даже на современных быстродействующих ЭВМ. Универсального алгоритма, обеспечивающего эффективное решение задачи в любой ее постановке, не существует. Многие из алгоритмов, существующие ныне, проходили длительный путь от их первоначального «зарождения» до современного вида, возникшего благодаря многократным совершенствованиям и теоретическим исследованиям (например, QR-алгоритм). На основании вышесказанного можно утверждать, что появление любого нового алгоритма, решающего какую-либо постановку проблемы собственных значений, должно вызывать научный интерес.

Цель диссертационной работы

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

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

Достоверность и обоснованность

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

Результаты, выносимые на защиту

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

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

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

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

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

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

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

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

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

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

Практическая ценность

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

Апробация результатов

Основные положения и результаты, включенные в диссертацию, докладывались на конференциях и семинарах Санкт-Петербургского государственного университета, Московского инженерного-физического института (государственного университета), Санкт-Петербургского политехнического университета, Санкт-Петербургского электротехнического университета, на международных конференциях «Математика. Компьютер. Образование».

Публикации

По материалам диссертации опубликовано 13 научных работ, среди них 4 полноценные статьи, 9 - тезисы и краткие статьи. Работа [2] опубликована в журнале, рекомендованном ВАК.

Объем и структура работы

Диссертационная работа состоит из трех глав, заключения, списка публикаций по теме диссертации, списка литературы. Диссертация изложена на 109 листах машинописного текста, включает 30 рисунков, список научных публикаций содержит 13 наименований, список основной литературы - 21 наименование.

Содержание диссертации

алгоритм вычислительный сингулярный матрица

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

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

В § 1 представляется идея новых алгоритмов, заключающаяся в следующем. Пусть для симметричной матрицы требуется решить частичную проблему собственных значений, например вычислить наибольшее собственное число. Предположим, что строковые суммы элементов матрицы взаимно равны. Тогда вектор, состоящий из единиц, будет собственным вектором , а нахождение одного из собственных чисел сводится к вычислению суммы элементов какой-либо из строк. Например:

6 - собственное число.

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

.

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

.

Для оценки близости приближенного значения собственного числа к точному значению собственного числа можно использовать теорему об оценке невязки:

где .

Для приведенного выше примера эта оценка дает: 0.017.

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

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

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

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

,

где

Доказательство утверждения непосредственно следует из теоремы об оценке невязки, если в качестве приближенного собственного числа брать , а в качестве приближенного собственного вектора брать .

Утверждение 2. На каждом шаге алгоритма выполняемое преобразование подобия обеспечивает равенство сумм элементов строк i и j: , где - преобразованная матрица, и - номера преобразуемых строк и столбцов.

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

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

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

Утверждение 4. Сумма всех элементов матрицы в ходе выполнения алгоритма достигает некоторого предельного значения.

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

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

Доказательство леммы основывается на непосредственном построении и изучении матрицы .

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

для .

Доказательство тривиально.

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

Доказательство основано на рассмотрении матрицы где Данная матрица характерна тем, что имеет собственное число и собственный вектор . Матрица рассматривается в отношении матрицы как «возмущенная» матрица. Применение теоремы о возмущении собственного числа и собственного вектора позволяет утверждать, что матрица имеет собственное число и собственный вектор , удовлетворяющие следующим неравенствам:

1) ;

2)

где - угол между векторами и .

Согласно лемме 1 существует ортогональная матрица , переводящая в :

.

Строится . Показывается, что

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

Доказательство основывается на рассмотрении суммы элементов матрицы как функции от :

Выполнив замены по формулам Тейлора первого порядка, формируется неравенство , где .

Взяв и учитывая, что , формируется неравенство .

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

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

Определяется , где логарифм задается рядом по степеням

Отмечается, что , из чего следует .

Оцениваются .

Утверждение 8. Начиная с некоторого шага алгоритма, имеет место неравенство

Согласно лемме 2 существуют ортогональная и симметричная :

,

По утверждению 7 возможно представление:

где - кососимметричная.

Тогда представляется в виде:

где .

Оценивается норма .

Показывается, что .

Тогда .

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

Доказательство основывается на рассмотрении утверждений 6 и 8:

,

.

Из них следует:

,

что доказывает линейную сходимость .

В § 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 графиков на каждом), сформированы практические рекомендации по выбору алгоритма в зависимости от условий задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размещено на Allbest.ru

...