Вариационные методы вычисления собственных значений и собственных векторов матриц: теория и численные алгоритмы

Тип работы: Диссертация
Бесплатно: Антиплагиат
Объем: 65 страниц
В избранное:

Казахский национальный университет им. аль-Фараби

УДК 519. 6 На правах рукописи

ЕЛЕУОВ АБДРАХМАН АБУОВИЧ

Вариационные методы вычисления собственных значений и собственных векторов матриц и их численная реализация

01. 01. 07 - вычислительная математика

Диссертация на соискание ученой степени кандидата

физико-математических наук

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

доктор физико-математических наук, академик НАН РК,

профессор Отелбаев М. О.,

кандидат физико-математических наук, доцент Акжалова А. Ж.

Республика Казахстан

Алматы 2007

СОДЕРЖАНИЕ

Введение. . 3

1 Непрерывные варианты вариационных методов вычисления

собственных значений и собствнных векторов

матриц 20

1. 1 Проблемы собственных значений и собственных векторов

матриц . . . 21

1. 2 Вариационный принцип Вебера . . . 22

1. 3 Конструктивное построение минимизирующей

последовательности для положительно определенной

матрицы . . . 23

1. 4 Решение задачи Коши . . . 24

1. 5 Конструктивное определение минимизирующей

последовательности для самосопряженной матрицы . . . 26

1. 6 Численная реализация в случае

самосопряженных матриц . . . 32

2 Численный метод теугольного представления матриц . . . 35

2. 1 Вариационный метод приведения матрицы к треугольному виду . . . 36

2. 2 Применение одного метода приближенного нахождения

собственных чисел к задаче экономики . . . 39

3 Алгоритмы счета собственных чисел и

собственных векторов матриц . . . 43

3. 1 Вычисление собственных чисел (сч) и собственных векторов

(св) самосопряжённых матриц. . . . 46

3. 2 Вычисление собственного вектора соответствующего

известному собственному числу 53

3. 3 Вычисление собственного вектора

и собственного числа . . . 54

3. 4 Численное определение кратности собственного числа

и вычисление присоединённых векторов . . . 61

3. 5 Вычисление всех собственных векторов

и собственных чисел матрицы . . . 63

Заключение . . . 66

Список использованных источников. . 67

Приложение А. Программа приведения произволных матриц к треугольному виду 70

ВВЕДЕНИЕ

Актуальность проблемы. Собственные значения диагональной матрицы указать очень легко. Учитывая, что собственные значения непрерывно зависят от элементов матрицы, естественно задаться вопросом: можно ли сказать что-нибудь полезное о собственных значениях матрицы, внедиагональные элементы которой «малы», по сравнению с элементами главной диагонали. Матрицы этого рода встречаются в приложениях; такими могут быть матрицы больших систем линейных уравнений, к которым приводит численная дискретизация краевых задач для эллиптических уравнений с частными производными. Иногда желательно локализовать собственные значения матрицы в некотором ограниченном множестве, которое можно легко охарактеризовать. К примеру, известно [1], что все собственные значения матрицы A расположены в кругу комплексной плоскости с центром в нуле и радиусом , причем матричную норму, , можно понимать в произвольном смысле. Дальнейшие обобщения этого утверждения приводят к теоремам типа Гершгорина. Другой круг вопросов при нахождении собственных значений матриц связан с теорией возмущений [2] . Предположим, что собственные значения матрицы A ₀ известны точно, но затем A ₀ подвергнута возмущению:

A ₀ → A ₀ +В . Как при этом изменятся собственные значения? Опять же из непрерывной зависимости собственных значений матриц от её элементов, есть основания полагать, что при достаточно малой матрице возмущения В собственные значения не должны изменяться существенно. На этом пути получены точные оценки в зависимости от того, насколько «малы» элементы матрицы возмущения. В реальных задачах для описания отображений приходится, как правило, использовать матрицы, полученные в результате каких-либо измерений или предварительных расчетов. Измерения и расчеты всегда выполняются с некоторыми погрешностями. Если вместо точной матрицы A ₀ мы получили приближенную матрицу A ₀ +В , то точность выполненного измерения или расчета естественно характеризовать безразмерным параметром точности ε, при котором мы можем быть уверены в выполнении оценки .

Возникает вопрос: каким должен быть параметр точности ε, чтобы была обеспечена приемлемая точность в окончательном решении интересующей нас задачи, если в процессе расчета вместо матрицы A ₀ используется её приближение A ₀ +В ? Ответ на этот вопрос в различных задачах различен. В частности, в работах [3-7] введено понятие спектрального портрета матрицы; на его основе оказалось возможным провести более детальный анализ расположения собственных значений матрицы.

Отметим также, что методы, основанные на раскрытии характеристического определителя и затем нахождении его нулей, очень трудоемки и применяются при нахождении характеристических многочленов для матриц невысоких размерностей [8-9] . Степенной метод не требует раскрытия характеристического определителя, но его эффективность сильно зависит от “удачного” или “неудачного” выбора начального вектора. Этот метод может не дать нужного собственного значения или даже вообще не иметь смысла, то есть может не существовать предельного вектора [10] . Метод вращения и его модификации требуют большого количества матричных операций, поэтому также не удовлетворяют требованиям пользователей [11, с. 125] .

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

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

- разработан непрерывный вариант вариационного метода нахождения собственных векторов и собственных матриц самосопряженных матриц;

- разработан непрерывный вариант вариационного метода вычисления собственных векторов и собственных значений матриц, произвольных матриц;

- обоснован вариационный метод приведения матриц к треугольному виду;

- исследован дискретный вариант вариационного метода приближенного нахождения собственных векторов и собственных значений матриц;

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

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

Задачи исследования. Обосновать идеологию построения целевого функционала, экстремумы которого совпали с собственными значениями матриц. Построить минимизирующую последовательность целевого функционала. Разработать конкретные расчетные формулы минимизирующей последовательности, которые обладали бы свойством устойчивости.

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

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

Положения, выносимые на защиту:

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

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

Апробация работы.

Основные результаты диссертации докладывались и обсуждались на следующих семинарах:

- научный семинар «Вычислительные и информационные технологии», г. Алматы, НИИ ММ при КазНУ им. аль-Фараби, руководимом академиком НИА РК, д. ф. -м. н., профессором Н. Т. Данаевым. Секретарь семинара д. ф. -м. н., профессор, К. К. Шакенов.

- научный семинар «Функциональный анализ и дифференциальные уравнения», руководимом академиком НАН РК, д. ф. -м. н., профессором Т. Ш. Кальменовым; ЦФМИ МОН РК, г. Алматы.

- научный семинар «Методы математического моделирования», г. Астана, ЕНУ им. Л. Н. Гумилева, руководимом академиком НАН РК, д. ф. -м. н., профессором М. О. Отелбаевым;

- научный семинар «Обратные задачи математической физики», г. Алматы, КазНПУ им. Абая, руководимом академиком РА ИО, д. п. н., профессором Е. Ы. Бидайбековым;

- научный семинар «Исследование по дифференциальнным уравнениям и по математическому анализу», г. Алматы, под руководством д. ф. -м. н., профессора М. О. Орынбасарова и к. ф. -м. н., профессора Ж. А. Токибетова

а также на конференциях:

- 10-ой Международной межвузовской конференции по математике и механике. КазНУ им Аль-Фараби. Алматы, 2004.

- V Казахстанско-Российской Международной научно-практической конференции «Математическое моделирование научно-технологических и экологических проблем в нефтегазодобывающей промышленности». Атырау, 2005.

- Международной научной конференции «Проблемы теоретической и прикладной механики». КазНУ им Аль-Фараби. Алматы, 2006.

- II-Международной научно-техническая конференции «Математическое моделирование информационных технологий в образовании и науке». КазНПУ им Абая. Алматы, 2003 г.

- “Вычислительные и информационные технологии в науке, технике и образовании”. КазНУ им Аль-Фараби. Алматы - Новосибирск, 2004.

- 11-ой Международной межвузовской конференции по математике и механике. ЕНУ им Л. Гумилева. Астана, 2006.

Публикации по теме диссертации. Основные результаты по теме диссертации опубликованы в 8 научных работах. В совмесных работах Отелбаеву М. О. принадлежат подстановки задач и руководство работой.

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

Сначала кратко опишем содержание разделов диссертации.

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

В третьем разделе диссертационной работы приведен целевой функционал , который пригоден для произвольных матриц . Глобальный минимум указанного функционала достигается на собственном векторе матрицы . К сожалению, методика, разработанная в первом разделе, не может быть применена к целевому функционалу . Поэтому в третьем разделе, в подразделе 3. 3, разработан специальный дискретный вариант вариационного метода, основанного на целевом функционале и пригодного для произвольных матриц. Отметим, что во втором разделе приведен вариационный метод сведения произвольной матрицы к треугольному виду. Далее зная треугольный вид матрицы, можно указать собственные значения матрицы. Таким образом, второй раздел также посвящен приближенному вычислению собственных значений произвольных матриц.

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

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

Производная скалярной функции

может быть записана в виде

Выбирая функцию так, чтобы она удовлетворяла следующему уравнению:

, (0. 1)

получим соотношение для производной

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

то есть не является собственным вектором матрицы . Тогда

Следовательно, функция, , в окрестности будет строго убывающей.

Пусть первый момент, когда производная обращается в нуль. Возможно, . Через обозначим предел . Указанный предел существует. Переходя к пределу при в равенстве (0. 1) имеем

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

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

Пусть решение задачи Коши:

(0. 2)

Доказывается, что при верно равенство: , то есть при всех ортогонально собственному вектору . Пусть наименьшее из (возможно, равное ), для которого вектор из (0. 2) обращается в нуль. Доказывается, что существует предел , который представляет собственный вектор матрицы . Этот вектор ортогонален вектору . Теперь ясно, что небходимо для нахождения собственного вектора. Надо решать задачу Коши (0. 2) с начальным условием , который ортогонален уже найденным собственным вектором . Этот процесс приводит к решению полной проблемы собственных значении эрмитовой матрицы. Главная трудность заключается в эффективном решении задачи Коши (0. 2) .

Сформулируем основной результат подпункта 1. 3.

Теорема 1. 3. 1 Пусть положительная матрица. Рассмотрим решение задачи Коши:

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

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

Пусть самосопряженная действительная матрица порядка действительный вектор - столбец порядка .

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

Обозначим через:

где скалярное произведение в -мерном гильбертовом пространстве, а норма, согласованная со скалярным произведением.

Если действительнозначная вектор-функция порядка , зависящая от параметра и непрерывно дифференцируемая по , то будет непрерывно дифференцируемой по .

Дифференцирование по приводит к формуле:

Возьмем вектор удовлетворяющий задаче Коши для системы обыкновенных дифференциальных уравнений:

. (0. 3)

Подставляя (0. 3) в выражение для получаем, что

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

Существование легко вытекает из компактности . Так как , то имеем соотношение:

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

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

и решим задачу Коши:

(0. 4)

Отсюда, аналогично вышеуказанному получаем, что собственный вектор , где . Здесь наименьшее из (возможно, равное ), для которого из (0. 4) обращается в нуль. В силу самосопряженности , вектор будет также собственным вектором . Тогда, вычислив , найдем из равенства:

Вектор не совпадает с , так как . С другой стороны, .

Пусть вычислены собственные векторы и соответствующие собственные числа , при матрицы .

Возьмем такой, что

; при .

Решая задачу Коши:

(0. 5)

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

Из равенства , предварительно вычислив , найдем следующее собственное значение .

Таким образом, мы получаем все собственные векторы и все собственные числа матрицы . Сформулируем полученный результат.

Теорема 1. 5. 1 Пусть самосопряженная действительная матрица. Рассмотрим задачу Коши:

где .

Пусть первый нуль величины . Тогда положим

(0. 6)

Построим с помощью рекуррентных соотношений.

где Т определено равенством (0. 6) .

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

На основе теоремы 1. 5. 1 в подпункте 1. 6. предложены численные алгоритмы счета собственных векторов и собственных значений самосопряженных матриц.

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

Пусть в далее означают квадратные матрицы порядка . В классе таких матриц введем скалярное произведение по формуле:

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

Лемма 2. 1. 1

Предположим, что обратная матрица и

. (0. 7)

Обозначим через нелинейный оператор, преобразующий матрицу следующим образом:

при ,

при .

Здесь элементы матрицы .

Введем функционал:

(0. 8)

Лемма 2. 1. 2 Пусть удовлетворяет условию (0. 7), а ограниченная обратимая матрица, тогда:

а) если матрица верхне-треугольная матрица, то .

б) если , то матрица есть верхне-треугольная матрица и есть треугольное представление .

В силу этой леммы нам достаточно выбрать так, чтобы функционал (0. 8) обращался в нуль. Необходимый ищем в виде матрицы - функций, зависящей от параметра . Выберем произвольным образом. Имеем

Здесь .

Пользуясь леммой 2. 1. 1, получаем:

. (0. 9)

Выберем , как решение задачи Коши:

При таком выборе, из (0. 9) имеем

Сформулируем доказанные утверждения в виде теорем.

Теорема 2. 1. 1 Пусть решение задачи Коши. Предположим, что выполнено (0. 7) и

Equation. 3 .

Тогда существуют , такие, что пределы

существуют и

Теорема 2. 1. 2 Пусть выполнены предположения теоремы 2. 1. 1 и, кроме того, жордановы клетки матрицы одномерны. Тогда и есть треугольная форма матрицы .

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

В третьем разделе диссертации разработаны алгоритмы счета собственных чисел и собственных векторов матриц.

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

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

Когда самосопряженная матрица, то целевой функционал .

Для произвольных матриц надо уметь выбирать целевой функционал.

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

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

Лемма 3. 3. 1 Если собственный вектор матрицы , то соответствующее собственное число равно числу и . Если , то есть собственный вектор матрицы и соответствующее собственное число равно .