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

Борзых, Алексей Николаевич

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

Борзых, Алексей Николаевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Санкт-Петербург МЕСТО ЗАЩИТЫ

2008 ГОД ЗАЩИТЫ

01.01.07 КОД ВАК РФ

Диссертация по математике на тему «О новых методах решения частичной проблемы собственных значений»

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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

БОРЗЫХ Алексей Николаевич

О НОВЫХ МЕТОДАХ РЕШЕНИЯ ЧАСТИЧНОМ ПРОБЛЕМЫ СОБСТВЕННЫХ ЗНАЧЕНИЙ

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ

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

00345B90G

Санкт-Петербург 2008

003456906

Работа выполнена на кафедре вычислительной математики математико-факультета Санкт-Петербургского государственного

механического университета.

Научный руководитель:

кандидат физико-математических наук, доцент САМОКИШ Борис Андреевич

Официальные оппоненты:

доктор физико-математических наук, профессор ДЕМЬЯНОВИЧ Юрий Казимирович (Санкт-Петербургский государственный университет)

доктор физико-математических наук, профессор ХАЗАНОВ Владимир Борисович (Санкт-Петербургский государственный морской технический университет)

Ведущая организация: Московский государственный

университет им. М. В. Ломоносова

Защита состоится 24 декабря 2008 г. в 13 часов на заседании совета Д 212.232.49 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 199048, Санкт-Петербург, Васильевский остров, 14 линия, д. 29, математико-механический факультет, ауд. 13.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская набережная, д. 7/9.

Автореферат разослан "_"_2008 г.

Ученый секретарь диссертационного совета,

доктор физико-математических наук, профессор А. А. Архипова

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

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

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

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

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

Методы исследования

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

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

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

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

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

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

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

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

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

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

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

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

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

установлены различные зависимости, выявлены наиболее эффективные алгоритмы для каждой конкретной задачи.

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

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

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

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

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

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

Публикации

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

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

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

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

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

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

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

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

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

'1 2 Т| V

2 0 4 1 = 6

4 -к Л к

'1.01 2.02 з.оз4 /Т '6.06^

2.02 0 4 1 = 6.02

^3.03 4 -к ,6-03,

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

д- _ 6.06 + 6.02 + 6.03 _ 6Ш67.

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

. \\Ае - Ле\\

ЗЛесг(А):Л-Л <" „„ ", где е = (\,...,\)т.

1 1 INI

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

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

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

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

Утверждение 1. На каждом шаге алгоритма существует хотя бы одно собственное значение, принадлежащее интервалу \р{А) — d{A), р{А) + d(A)\

где р{А) = -^рХА), = d(A)= d,{Ä) = р,(А)~ р(А).

п I к \п i

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

а в качестве приближенного собственного вектора брать е = (1,..., I)7.

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

В - преобразованная матрица, i и j — номера преобразуемых строк и столбцов.

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

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

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

всех элементов матрицы (т.е. задача ——>тах, где а — угол поворота в

к,т

матрице вращения) имеют одинаковые решения (реализуются одной матрицей вращения).

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

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

Лемма 1. Пусть векторы х, у: |х]| = ¡¡>'||. Пусть в - острый угол между (х V) л

векторами х,у: со$в = - , О<0<—. Тогда существует ортогональная

ИМИ 2

II :1/х = у, |г/-/| = 2-8И1^0

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

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

8ш(/?) < бю! — I • вт(4у5) для V/? е

Л?

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

Лемма 2. Пусть А - симметричная матрица, Л1,...,Л11 - собственные числа А, Х\,...,ХП - соответствующие собственные векторы, с/(А) = £. В утверждении 1 было показано, что на интервале [р(А) — е, р{А) + е\ существует хотя бы одно собственное число А. Пусть £ мало настолько, что на интервале \р(А) — е4п, р(А) + е4п\ существует ровно одно собственное

число Як, и пусть оно простое. Тогда существуют ортогональная и и симметричная А' такие, что

иА11Т =А", с/(А') = 0, \и-1\\<С,Е, С, = .$т(~).

Доказательство основано на рассмотрении матрицы А = А - Д где 0 = <1'щ(с1],...с/, =р,(А)-р(А), ||£>|< 7и ■£ Данная матрица характерна тем, что имеет собственное число р(А) и собственный вектор с = (1,..., 1)г.

Матрица А рассматривается в отношении матрицы А как «возмущенная» матрица. Применение теоремы о возмущении собственного числа и собственного вектора позволяет утверждать, что матрица А имеет собственное число Ят и собственный вектор хт, удовлетворяющие следующим неравенствам: 1)\Лт-р(А)\<Щ\<^-£;

2) I.sin(20)<-г<

D\\ ^

2 minU-Al пш|Л,-ЛГ

lfm 1 lfm

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

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

в е:

Строится А' =UAUT. Показывается, что d(A') = 0. Утверждение 6. Справедливо неравенство

k.m к,т ¿öyjn |

II £

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

IX =2(л -а)5Ш(«) + 2(Й +^)с08(а) + ай + а^ + 2а„со%{2а) +

к,т

+ (^-а„)зт(2а)+

Выполнив замены по формулам Тейлора первого порядка, формируется неравенство >2(р,-Р))а + Я(а), где |Л(ог)|<-|-«2.

к,т к,т

Взяв a = C2(pJ - р,) и учитывая, что d(A)<pj-pl, формируется неравенство >С2(р, -p,f >C2d(A)2.

к,т к,т

Утверждение 7. Пусть U - ортогональная матрица, |[/— /|] = Х- ^ •

Тогда U и UT представляются в виде

U = I + S + P, UT =I-S + PT,

где S - кососшшетричная, ||S| < 2/, Ц/5] < 2%2.

Определяется S = logt/, где логарифм задается рядом по степеням ({/-/):

S = log£/ = log(/ + [/-/)=(t/-/)-^(i/-/)2 +^(t/-/)3 -...

Отмечается, что logt/~' = -logU, из чего следует ST = — S. Оцениваются ||S||, ||/>||.

Утверждение 8. Начиная с некоторого шага алгоритма, имеет место неравенство d(A)2 > С3 • (Л, -р(А)\ С3 = ^г^гц^ц-

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

UAUT = A', d(A') = О, \U-/||<С,£, e = d{A). По утверждению 7 возможно представление:

U-I + S + P, UT=I-S + PT,

И^с,*, И<2(С]£)2,

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

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

А = UTA'U = (/ - S + PT)A\I + S + Р) = А* - SA' + А'S + Рй, где Р0 = -SA'S + PTA'U + UTA'P.

Оценивается норма Ра: |/>||£ 8||л|| • (С,е)2. Показывается, что ~ = ~(рое<е) ^ п' 8|И' (С,£)2.

kjn k,m

Тогда d(Af = ег > С3(Л, - р(А)).

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

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

с/(А)2>С3-(А,-р(Л)).

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

Л, - р(В) _ (л,- р(А))~ (р(В) - р{А)) = х р(В) - р(А) ;} Л,-р(А) Л, - р(А) \~р{А)

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

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

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

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

Утверждение 2. Справедливо неравенство < ||л|, где з(А) = — ^¡Г а().

п 1,1

Утверждение 3. На каждом шаге алгоритма справедлива оценка \э(А)2 - Лг\<2\\А\\А, где Я - одно из сингулярных чисел А, А = тах(Д/?, Ад),

Ар = тах(рк) -тЩрк), Ад = тах(^) - тт(^), = £а,к, = •

Утверждение 4. Существует 5*: —>д*.

Утверждение 5. Справедливо неравенство ¿(/4)-5(Л) > С,Д2, где

преобразования.

Утверждение 6. Имеет место предельное соотношение А (Ак)—)0. Теорема 1. Алгоритм сходится к одному из сингулярных чисел:

А - матрица до преобразования, А - матрица после

Лемма 1. Пусть векторы х, у: ||х| = |у||. Пусть в - острый угол между векторами х,у: соьв = , О<0<—. Тогда существует ортогональная

ИМИ 2

[/ :С/х = у, ||£/-/|| = 2-би^0

Утверждение 7. Справедливо неравенство в<$т2в при ве [0, —].

Утверждение 8. Пусть (1*,г*,Хт) - собственная тройка А'. Пусть А = А' — Р, <||Л||. Пусть Л1,...,Лп - сингулярные числа А. Тогда у матрицы А имеется собственная тройка (1,г,Лт), удовлетворяющая следующим условиям:

^sm2вl<g(A), где -йт\1в2< g(A), где вг-/.(г,г'),

а(А,Лт) со(А,Лт) = тт\Л? -Л1\.

1*т I 1

Утверждение 9. Пусть Л, - сингулярные числа А. Пусть —'~>°° >Лк (по теореме 1). Начиная с некоторого шага алгоритма, матрица А имеет левый сингулярный вектор I и правый сингулярный вектор г, удовлетворяющие условиям:

¿(/,е)<С2 Д, Дг,е)<С2 Д,

где С2 = 6"^ , ю(А,Лк) = тт\Л, -ЛкI. со(А,Лк) к 1 ' 41

Утверждение 10. Пусть и - ортогональная матрица, ||С/-/|| =

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

и = I + Б + Р,

иТ =1-8 + РТ,

где Б-кососимметричная, ||5||<2^, Ц/5! < 2;^2.

Утверждение 11. Начиная с некоторого шага алгоритма Д2(Л)^С3(н»,-я(Л)), где С3 = бС^ЦлЦ, м>1 - точное значение одного из сингулярных числа А.

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

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

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

В §1 эмпирически проверяется линейная скорость сходимости предложенных в диссертации алгоритмов.

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

1) Степенной метод.

2) Приведение матрицы к трехдиагональной форме с последующим применением какого-либо другого метода.

3) Покоординатная релаксация отношения Релея с циклическим перебором координат.

4) Покоординатная релаксация отношения Релея с выбором координат наискорейшего спуска.

5) Градиентная релаксация отношения Релея.

6) Алгоритм, предложенный в диссертации.

7) Алгоритм, предложенной в диссертации, который предваряется заменами знаков элементов матрицы.

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

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

1) Проведение тестовых экспериментов при фиксированной относительной точности вычислений (е = 10~3 и £ = 10~5), но на разных размерах задачи, варьируемых от 10 до 100, от 100 до 1000.

2) Проведение тестовых экспериментов при фиксированном размере задачи (п = 100, п = 1000 и п = 5000), но для разных е, варьируемых от 10~' до Ю'7.

3) Проведение экспериментов при фиксированном размере задачи (и = 100), фиксированной относительной точности вычислений (£ = 10~7), но на матрицах с различной близостью старших собственных

значений, определяемой величиной й = 1--у- и варьируемой от 10"5 до

Ю-1 («плохие матрицы») и от 0.1 до 0.9 («хорошие матрицы»).

4) Проведение экспериментов при фиксированном размере задачи (и = 100, и = 1000), фиксированной относительной точности вычислений (е = 10~3), но с различным коэффициентом верхней релаксации, варьируемом от 1.0 до 1.9.

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

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

1) Степенной метод, примененный к матрице ААТ без явного умножения А на Ат.

2) Степенной метод, примененный к матрице ААТ с явным умножением А на Ат.

3) Покоординатная релаксация отношения Релея с циклическим перебором координат.

4) Покоординатная релаксация отношения Релея с выбором координат наискорейшего спуска.

5) Градиентная релаксация отношения Релея.

6) Алгоритм, предложенный в диссертации.

7) Алгоритм, предложенной в диссертации, который предваряется заменами знаков элементов матрицы.

8) Алгоритм, предложенный в диссертации, но использующий матрицы отражения вместо матриц вращения.

9) Приведение матрицы к двухдиагональной форме с последующим применением какого-либо другого метода.

10) Приведение матрицы к трехдиагональной форме с последующим применением какого-либо другого метода.

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

исследовались алгоритмы вычисления наибольшего собственного числа.

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

виде 13 рисунков (по 10 графиков на каждом), сформированы практические

рекомендации по выбору алгоритма в зависимости от условий задачи.

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

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

2. Борзых А. Н. Об одном оптимизационном алгоритме, вычисляющем наибольшее сингулярное число вещественной матрицы // Вестн. С-Петерб. ун-та. Серия «Математика. Механика. Астрономия». СПб., 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.

Подписано к печати 11.11.08. Формат 60x84 % . Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Заказ 4321

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел,: (812) 428-4043, 428-6919

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Борзых, Алексей Николаевич

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

Глава 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. Построена наиболее оптимальная реализация предложенных алгоритмов, обеспечивающая в вычислительном процессе минимальное количество арифметических операций на каждом шаге.

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

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

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

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

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

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

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

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.