Вариационные методы вычисления собственных значений и собственных векторов матриц и их численная реализация
Казахский национальный университет им. аль-Фараби
УДК 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].
Предположим, что собственные значения матрицы A0 известны точно, но затем
A0 подвергнута возмущению:
A0 → A0 +В. Как при этом изменятся собственные значения? Опять же из
непрерывной зависимости собственных значений матриц от её элементов, есть
основания полагать, что при достаточно малой матрице возмущения В
собственные значения не должны изменяться существенно. На этом пути
получены точные оценки в зависимости от того, насколько малы элементы
матрицы возмущения. В реальных задачах для описания отображений приходится,
как правило, использовать матрицы, полученные в результате каких-либо
измерений или предварительных расчетов. Измерения и расчеты всегда
выполняются с некоторыми погрешностями. Если вместо точной матрицы A0 мы
получили приближенную матрицу A0 +В , то точность выполненного измерения
или расчета естественно характеризовать безразмерным параметром точности ε,
при котором мы можем быть уверены в выполнении оценки .
Возникает вопрос: каким должен быть параметр точности ε, чтобы была
обеспечена приемлемая точность в окончательном решении интересующей нас
задачи, если в процессе расчета вместо матрицы A0 используется её
приближение A0 +В ? Ответ на этот вопрос в различных задачах различен. В
частности, в работах [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) и
.
Тогда существуют , такие, что пределы
существуют и
Теорема 2.1.2 Пусть выполнены предположения теоремы 2.1.1 и, кроме того,
жордановы клетки матрицы одномерны. Тогда и есть
треугольная форма матрицы .
В подпункте 2.2 приведено применение метода подпункта 2.1 к
приближенному нахождению нормы прибыли в модели межотраслевого баланса В.
Леонтьева, поскольку норма прибыли интерпретируется как собственное
значение матрицы прямых затрат. Имеются соответствующие иллюстративные
расчеты.
В третьем разделе диссертации разработаны алгоритмы счета собственных
чисел и собственных векторов матриц.
В первых двух подпунктах третеьего раздела приведены конкретные
алгоритмы, вычисляющие собственные вектора и соответствующие собственные
числа самосопряжённой матрицы (см.алгоритмы А1. и А2.). Эти алгоритмы
основаны на дискретизации результатов первого раздела.
В вариационном методе на первом этапе выбирается целевой функционал,
минимум которого представляет собственное значение исходной матрицы. В
случае положительной матрицы этот функционал имеет вид .
Когда самосопряженная матрица, то целевой функционал .
Для произвольных матриц надо уметь выбирать целевой функционал.
Для произвольной матрицы порядка введем функционал
Если вектор есть собственный вектор матрицы , т.е. если
, то, умножая это уравнение скалярно на , получаем, что .
Откуда . Подставим в последнее выражение. Тогда . Поэтому,
из определения функционала сразу вытекает лемма.
Лемма 3.3.1 Если собственный вектор матрицы , то
соответствующее собственное число равно числу и . Если , то
есть собственный вектор матрицы и соответствующее собственное
число равно .
В силу этой леммы вычисление собственного вектора матрицы
эквивалентно нахождению вектора , доставляющего неотрицательному
функционалу .
Выберем малое число , и, если
,
то вектор примем за собственный вектор матрицы , а число
за соответствующее собственное число.
Пусть произвольный единичный вектор. Определим матрицу,
действующую по формуле:
,
где единичная матрица.
Если и единичные векторы, то при прямыми вычислениями
получаем
где
Из этих равенств при малых получаем:
Рассмотрим разность
где .
Отсюда, при малых
(0.10)
где и величина допускает оценку постоянным числом при .
Пусть некоторое приближение к собственному вектору.
Если , возьмём . Тогда из (0.15) вытекает, что
.
Поэтому при малых отрицательных имеем . Выберем
из равенства
.
Число находим по алгоритму (А.4).
Пусть теперь . В случае, когда уравнение имеет же нулевое
решение, то собственное число матрицы . Поэтому по алгоритму
(А.3) (см. подпункт 3.2) находим собственный вектор. Если же уравнение
имеет только нулевое решение, то уравнение имеет решение .
В качестве возьмем
,
где удовлетворяет равенству .
Подставив в (0.10), получаем:
Отсюда вытекает, что, если выбрано малым, и выполнено , то при
имеет место
.
Поэтому
Из вышеприведённых выкладок следует, что вычисления собственного числа и
собственного вектора можно проводить следующим Алгоритмом 5.
Фиксируем малое . Возьмём произвольное и построим
следующим образом:
Обозначим единичная матрица,
.
а) Если , то положим
где выбираем из условия
б) Если же , то берём и построим векторы и числа по
формулам:
Построение продолжим до тех пор, пока не выполнится одно из следующих
условий:
б.1)
б.2)
б.3)
Так как собственное число существует, согласно выкладкам, проведённым выше,
найдется такое , что выполняется одно из этих трёх условий. За целое
число возьмём наименьшее целое, для которого выполнено хотя бы одно
из приведённых, трёх соотношений. Если выполнено условие б.3), то
собственный вектор, а собственное число матрицы . Поэтому
заканчиваем счёт. Если же выполнено условие б.2), то собственное
число матрицы . Собственный вектор найдём по алгоритму (А.3) и
заканчиваем счёт. Если, наконец, выполнено условие б.1), продолжаем
построение , выбрав по формуле:
где выбирается из условия
.
Счёт останавливаем, если . За собственное число берём число , а
за соответствующий собственный вектор . Имеет место теорема.
Теорема 3.3.1 Алгоритм А.5 приближенно вычисляет собственное число и
собственный вектор матрицы .
В подпункте 3.4 приведен численный метод определения кратности
собственного числа и вычисление присоединённых векторов.
1 НЕПРЕРЫВНЫЕ ВАРИАНТЫ ВАРИАЦИОННЫХ МЕТОДОВ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ
И СОБСТВЕННЫХ ВЕКТОРОВ МАТРИЦ
В первом разделе исследуется задача на собственные значения эрмитовых
матриц. Предлагается новый вариационный метод нахождения собственных
значений эрмитовых матриц. Для построения минимизирующей последовательности
необходимо уметь находить решение специальной задачи Коши для системы
обыкновенных дифференциальных уравнений.
1.1 Проблемы собственных значений и собственных векторов матриц
В книге [12] проблема делится на, так называемые, частичную и общую
проблемы собственных значении. К частичной проблеме Н.С.Бахвалов относит
задачу определения максимального или минимального по модулю собственного
значения матрицы, которая возникает, в частности, при решении некоторых
ядерных задач. Здесь приходится решать задачи, эквивалентные задачам
отыскания собственных значений матриц размерности порядка 103-106. При
меньших размерностях матриц для решения этих задач чаще применяют
итерационные методы, а при больших вероятностные. В колебательных системах
иногда требуется определить два максимальных по модулю собственных значений
матрицы, причем меньшее из них обычно достаточно определить с меньшей
точностью. Может возникнуть задача отыскания собственного значения,
наиболее близкого к данному числу. Общая или полная проблема собственных
значений состоит в определении всех собственных значений и всех собственных
векторов матрицы.
Задача определения собственных значений сводится к определению нулей
характеристического многочлена , где единичная матрица,
квадратная матрица размерности . На первый взгляд задача кажется очень
простой. Однако при больших значениях даже раскрытие определителя
связано с громоздкой и утомительной работой. В вычислительной
математике выработано много различных приемов и способов, облегчающих труд
по раскрытию определителя . На следующем этапе надо решать задачу
определения границ нулей характеристического многочлена , а затем
приближенно их находить.
Для матриц произвольного вида задача отделения корней
характеристического многочлена до сих пор в удовлетворительной форме не
решена. Отдельные успехи в этом направлении связаны со специальными
классами матриц. В частности, для эрмитовых матриц имеются довольно
эффективные вариационные методы. Их детальной разработке посвящен настоящий
раздел.
1.2 Вариационный принцип Вебера
В книге [7] показано, что стационарными значениями эрмитовой формы
на сфере являются собственные значения этой формы, и только
они, а стационарными точками ее собственные векторы и только они. Таким
образом, для нахождения собственных значений и собственных векторов
эрмитовой матрицы достаточно находить экстремумы формы при
ограничении . Чтобы избавиться от ограничения , надо изучить
экстремум формы . В книге [7] приведен вариационный принцип Вебера в
следующей формулировке:
Теорема (Вебера) Предположим, что собственные значения эрмитовой
матрицы занумерованы в порядке их неубывания . Если , то
есть минимум формы . Обозначим через вектор, на котором
достигается этот минимум. Следующее собственное значение есть минимум
формы при условии . Обозначим через вектор, на котором
достигается этот условный минимум. Следующее собственное значение
есть минимум формы при условии , . Точно также, при любом
, собственное значение определяется как минимум формы при
ограничениях , , ... , .
Таким образом, главная трудность состоит в конструктивном построении
минимизирующей последовательности, так как теорема Вебера не дает подобного
конструктивного алгоритма.
1.3 Конструктивное построение минимизирующей последовательности для
положительно определенной матрицы
Пусть положительно определенная матрица размерности . Через
обозначим вектор - столбец размерности . Считаем, что нуль не
является собственным значением матрицы. Предположим, что вектор
является дифференцируемой вектор-функцией параметра , причем при
эта кривая проходит через точку . Вычислим производную скалярной
функции
.
Производная дроби равна
Заметим, что величина принимает только действительные значения.
Тогда производная может быть записана в виде
Выберем функцию так, чтобы она удовлетворяла следующему уравнению:
(1.1)
Тогда примет вид
(1.2)
Следовательно, при производная принимает отрицательные
значения, а сама функция, , будет убывающей. Предположим, что
то есть не является собственным вектором матрицы . Тогда
.
Следовательно, функция , в окрестности , будет строго убывающей.
Пусть первый момент, когда обращается в нуль. Возможно
. Через обозначим предел . Указанный предел существует.
Докажем это. Умножим обе части равенства (1.1) скалярно на вектор . В
результате имеем
или
.
Следовательно, при любом справедливо тождество
. (1.3)
Равенство (1.3) представляет сферу в конечномерном пространстве,
которая, как известно, представляет собой компакт. Отсюда вытекает
существование предела . Переходя к пределу при в равенстве
(1.1), имеем
то есть
причем из (3) следует, что . Следовательно, собственный вектор
матрицы . Соответствующие собственное значение равно отношению
.
Как находить другие собственные вектора? Для этого возьмем , так,
чтобы выполнялось условие ортогональности из теоремы Вебера: , .
Пусть решение задачи Коши:
(1.4)
Умножим скалярно обе части уравнения (1.4) на вектор :
. (1.5)
Так как , то равенство (1.5) примет вид
(1.6)
Обозначим через . Выберем ортонормированный базис в конечномерном
пространстве так, чтобы первый элемент базиса был равен . Тогда вектор
разлагается по элементам выбранного базиса следующим образом:
,
Причем
где через многоточие обозначено выражение, не зависящее от . Тогда
уравнение (1.6) запишется в виде
(1.7)
где многоточие обозначает выражение, не зависящее от . Поскольку
при равно нулю и выражения в квадратных скобках из (1.7), не зависит
от , заключаем, что в любой момент времени .
Итак, при верно равенство, то есть , при всех ,
ортогонально собственному вектору . Пусть наименьшее из
(возможно, равное ), для которого вектор , из (1.4), обращается в
нуль. Доказывается, что существует предел , который представляет
собственный вектор матрицы . Этот вектор ортогонален вектору .
Теперь ясно, что надо делать, чтобы находить оставшиеся собственные
вектора. Надо решать задачу Коши (1.4) с начальным условием ,
предварительно выберев его ортогональным к уже найденным собственным
вектором . Этот процесс приводит к решению полной проблемы собственных
значении эрмитовой матрицы. Главная трудность заключается в эффективном
решении задачи Коши (1.4).
Сформулируем основной результат настоящего подпункта
Теорема 1.3.1 Пусть положительная матрица. Рассмотрим решение
задачи Коши
где . Пусть первый нуль величины . Тогда положим .
Построим с помощью рекуррентных соотношений где оператор
определен в предыдущей строке. Тогда ортогональные собственные
векторы матрицы .
1.4 Решение задачи Коши
В предыдущем параграфе мы задачу нахождения собственных векторов свели к
решению начальных задач Коши с теми или иными начальными векторами. Запишем
эту задачу
(1.8)
причем . В принципе, задача (1.8) нелинейная, однако нелинейный член
достаточно специфичен. Обозначим через функционал: . Перепишем
(1.8) в виде
(1.9)
Перепишем (1.9) в виде
сделаем замену
.
(1.10)
Тогда
(1.11)
из соотношения (1.10) имеем:
,
где решение задачи Коши (1.11).
Вспоминая определение функционала , получим уравнение для
определения .
(1.12)
где решение задачи Коши (1.11). Чтобы найти , надо при
каждом фиксированном решать, относительно , интегральное
уравнение (1.12). После определения , надо вычислить предел, при
стремящемся к первому нулю функции , которое обозначено через .
Итак, число представляет собственное значение матрицы .
1.5 Конструктивное определение минимизирующей последовательности для
самосопряженной матрицы
В подпункте 1.3 существенно использовалось то, что является
вещественной величиной. Это условие выполняется, когда положительно
определенная матрица. В то же время, когда является самосопряженной
матрицей, это условие может нарушаться.
Пусть самосопряженная, действительная матрица порядка
действительный вектор столбец порядка .
Предположим, что нуль не является собственным числом матрицы .
Обозначим через
где скалярное произведение в -мерном гильбертовом пространстве,
а норма, согласованная со скалярным произведением.
Если действительнозначная вектор-функция порядка , зависящая
от параметра и непрерывно дифференцируемая по , то будет
непрерывно дифференцируемой по .
Если то
,
Так как самосопряженная матрица, то в общем случае имеем:
Окончательно запишем
Возьмем удовлетворяющим уравнению:
. (1.13)
Это задача Коши. Умножая уравнение (1.13) на скалярно, получим
.
(1.14)
Действительно,
(1.15)
,
то .
Отсюда вытекает, что не зависит от , т.е. является постоянной:
. (1.16)
Подставляя (1.13) в выражение для , получаем, что
.
Действительно
.
Так как нуль не является собственным числом матрицы , поэтому
функция , по , строго убывает до тех пор пока .
Пусть , наименьшее значение для, которого (возможно,
) и
Существование легко вытекает из (1.16) в силу компактности .
Так как , то имеем
Отсюда вытекает соотношение
Следовательно,
Отсюда вытекает, что собственный вектор матрицы .
Следовательно, в силу самосопряженности имеем, что собственный
вектор матрицы . Но тогда, вычислив , получим, что
,
где действительное число.
Таким образом, наименьшее собственное значение матрицы найдено. В
дальнейшем собственный вектор обозначим через .
Возьмем теперь вектор ортогональный к собственному вектору, т.е.
и решим задачу Коши.:
(1.17)
Умножим (1.17) на скалярно
Так как
поэтому
(1.18)
Причем . Рассуждая также, как в подпункте 1.3, из уравнения (1.18),
получаем, что
, для всех .
(1.19)
Теперь найдем . В результате получим, что
Поэтому строго убывает до тех пор пока . Отсюда, аналогично
вышеуказанному получаем, что собственный вектор , где .
Здесь наименьшее из (возможно, равное ), для которого
, из (1.17) обращается в нуль. В силу самосопряженности , вектор
будет также собственным вектором . Тогда, вычислив , найдем
из равенства:
.
Вектор не совпадает с , так как . С другой стороны, .
Это следует из равенства , которое доказывается точно также, как было
доказано соотношение (1.16).
Пусть вычислены собственные векторы и соответствующие собственные
числа , при , матрицы . Возьмем такой, что
; при
Решая задачу Коши:
(1.20)
как и выше, получаем еще один собственный вектор матрицы ,
ортогональный всем и .
Из равенства , предварительно вычислив , найдем следующее
собственное значение .
Таким образом, мы получаем все собственные векторы и все собственные
числа матрицы . Следовательно, мы доказали теорему.
Теорема 1.5.1 Пусть самосопряженная действительная матрица.
Рассмотрим задачу Коши:
где .
Пусть первый нуль величины . Тогда положим
(1.21)
Построим с помощью рекуррентных соотношений.
,
где Т определено равенством (1.21).
Тогда ортогональные собственные векторы матрицы .
Далее числа , при , найдем из соотношений , которые
представляют соответствующие к ним собственные числа.
1.6 Численная реализация в случае самосопряженных матриц
Пусть задана симметрическая матрица c вещественными элементами. -
ый столбец матрицы будем обозначать через . Нормируем столбцы,
то есть вычислим вектор . Ясно, что величина отлична от
нуля, поскольку мы предполагаем, что нуль не является собственным значением
матрицы. Из всех чисел , при , вычислим наименьшее.
Пусть . Рассмотрим задачу Коши для дифференциального уравнения
первого порядка:
(1.22)
Умножим обе части дифференциального уравнения из (1.22) скалярно на
, и в результате имеем
или .
Следовательно, величина не зависит от , то есть равна
единице, поскольку она является таковой в момент . Поэтому в (1.22)
положим . Наша цель: решить задачу Коши (1.22) в интервале , где
первый нуль производной . Как было показано в п. 1.4, значение
, в общем случае, может быть равно бесконечности. Поэтому численное
решение задачи (1.22) возможно только на конечном интервале , при
. В результате при численной реализации предлагаемого в п. 1.5
алгоритма возникают погрешности, связанные с заменой требуемого интервала
на конечный интервал . Такую погрешность будем обозначать .
Другого сорта погрешности , возникают при дискретизации
дифференциальной задачи (1.22). Таким образом, погрешность появляется
при нахождении последовательности из системы:
(1.23)
где .
Заметим, что справедливо равенство
.
Следовательно, длина не меньше единицы. Поэтому можно
нормировать , а и векторы и не могут быть взаимно
ортогональными. Найдем выражение целевого функционала
Если взять , то имеем убывание целевого функционала
.
Итак, при каждом , шаг надо выбирать из условия:
(1.24)
Приведенные расчетные формулы (1.23), (1.24) пригодны, когда ищется
только один собственный вектор. Счет прекращается, когда убывание целевого
функционала становится незначительным.
2 ЧИСЛЕННЫЙ МЕТОД ТРЕУГОЛЬНОГО ПРЕДСТАВЛЕНИЯ МАТРИЦ
Наличие быстро развивающихся мощных современных вычислительных средств
оказывает большое влияние на развитие математики в целом. Особенно
подвержено этому влиянию вычислительная математика. Многие задачи требуют
создания быстро вычисляющих алгоритмов. Например, в задачах, связанных с
реальным использованием военной техники, численные расчеты должны
проводиться за доли секунды. Такие же высокие скорости вычислений, как
правило, требуются в задачах связанных с защитой информации, точнее в
задачах криптографии. Быстрота счета обычно достигается путем кропотливых
исследований и созданием сложных алгоритмов вычислений. На это тратиться
достаточно длительное время квалифицированного специалиста. Иногда у
пользователя возникает необходимость понимания сложного алгоритма, что
также требует много времени и высокой квалификации.
Существует много задач, которые не обязательно решать численно за малые
доли секунды, а достаточно, чтобы численное решение было готово за
определенный промежуток времени, исчисляемый несколькими часами. Для таких
задач, как правило, важнее простота алгоритма, а не быстрота вычислений.
При численном решении таких задач, предпочтительно “переложить” большую
часть работы на быстродействующий компьютер, и тем самым упростить труд
программиста или пользователя.
2.1 Вариационный метод приведения матрицы к треугольному виду
В данном подпункте мы предлагаем один алгоритм одновременного вычисления
всех собственных чисел конечномерных матриц.
Известен метод одновременного вычисления собственных чисел матриц,
изложенный в [13]. Наш алгоритм опирается на вышеуказанный метод,
обеспечивая при этом устойчивость счета, и, кроме всего прочего, отличается
простотой.
Пусть , в дальнейшем, означают квадратные матрицы порядка . В
классе таких матриц введем скалярное произведение
,
где по и ведется суммирование от 1 до . означает
комплексносопряженное число. Норму, соответствующую этому скалярному
произведению, обозначим через , как обычный модуль.
Лемма 2.1.1
Доказательство. Имеем
.
.
Лемма доказана.
Предположим, что обратная матрица и
.
(2.1)
Обозначим через нелинейный оператор, преобразующий матрицу
следующим образом:
при ,
при .
Здесь элементы матрицы .
Введем функционал
(2.2)
Лемма 2.1.2 Пусть удовлетворяет (2.1), ограниченная
обратимая матрица, тогда:
а) если матрица верхне-треугольная матрица, то .
б) если , то матрица есть верхне-треугольная матрица, и
существует треугольное представление .
Лемма очевидна. В силу этой леммы нам достаточно выбрать так,
чтобы функционал (2.2) обращался в нуль. Необходимый ищем в виде
матрицы - функций, зависящей от параметра . Выберем
произвольным образом. Имеем
.
Здесь .
Пользуясь леммой 2.1.1, получаем:
. (2.3)
Выберем , как решение задачи Коши:
(2.4)
При таком выборе из (2.3) имеем
. (2.5)
Отсюда следует, что
,
(2.6)
когда стремится к , минуя множество малой плотности. Более того,
. (2.7)
Поэтому, для достаточно больших , имеем
.
(2.8)
Из (2.5), (2.6) и (2.7) вытекает
Теорема 2.1.1 Пусть решение задачи Коши. Предположим, что
выполнено (2.1) и
.
Тогда существуют , такие, что пределы
существуют и
Доказательство. Существование пределов есть следствие компактности
рассматриваемого множества -мерных матриц. Равенство есть
следствие (2.5).
Теорема 2.1.2 Пусть выполнены предположения теоремы 2.1.1 ... продолжение
Вы можете абсолютно на бесплатной основе полностью просмотреть эту работу через наше приложение.
УДК 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].
Предположим, что собственные значения матрицы A0 известны точно, но затем
A0 подвергнута возмущению:
A0 → A0 +В. Как при этом изменятся собственные значения? Опять же из
непрерывной зависимости собственных значений матриц от её элементов, есть
основания полагать, что при достаточно малой матрице возмущения В
собственные значения не должны изменяться существенно. На этом пути
получены точные оценки в зависимости от того, насколько малы элементы
матрицы возмущения. В реальных задачах для описания отображений приходится,
как правило, использовать матрицы, полученные в результате каких-либо
измерений или предварительных расчетов. Измерения и расчеты всегда
выполняются с некоторыми погрешностями. Если вместо точной матрицы A0 мы
получили приближенную матрицу A0 +В , то точность выполненного измерения
или расчета естественно характеризовать безразмерным параметром точности ε,
при котором мы можем быть уверены в выполнении оценки .
Возникает вопрос: каким должен быть параметр точности ε, чтобы была
обеспечена приемлемая точность в окончательном решении интересующей нас
задачи, если в процессе расчета вместо матрицы A0 используется её
приближение A0 +В ? Ответ на этот вопрос в различных задачах различен. В
частности, в работах [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) и
.
Тогда существуют , такие, что пределы
существуют и
Теорема 2.1.2 Пусть выполнены предположения теоремы 2.1.1 и, кроме того,
жордановы клетки матрицы одномерны. Тогда и есть
треугольная форма матрицы .
В подпункте 2.2 приведено применение метода подпункта 2.1 к
приближенному нахождению нормы прибыли в модели межотраслевого баланса В.
Леонтьева, поскольку норма прибыли интерпретируется как собственное
значение матрицы прямых затрат. Имеются соответствующие иллюстративные
расчеты.
В третьем разделе диссертации разработаны алгоритмы счета собственных
чисел и собственных векторов матриц.
В первых двух подпунктах третеьего раздела приведены конкретные
алгоритмы, вычисляющие собственные вектора и соответствующие собственные
числа самосопряжённой матрицы (см.алгоритмы А1. и А2.). Эти алгоритмы
основаны на дискретизации результатов первого раздела.
В вариационном методе на первом этапе выбирается целевой функционал,
минимум которого представляет собственное значение исходной матрицы. В
случае положительной матрицы этот функционал имеет вид .
Когда самосопряженная матрица, то целевой функционал .
Для произвольных матриц надо уметь выбирать целевой функционал.
Для произвольной матрицы порядка введем функционал
Если вектор есть собственный вектор матрицы , т.е. если
, то, умножая это уравнение скалярно на , получаем, что .
Откуда . Подставим в последнее выражение. Тогда . Поэтому,
из определения функционала сразу вытекает лемма.
Лемма 3.3.1 Если собственный вектор матрицы , то
соответствующее собственное число равно числу и . Если , то
есть собственный вектор матрицы и соответствующее собственное
число равно .
В силу этой леммы вычисление собственного вектора матрицы
эквивалентно нахождению вектора , доставляющего неотрицательному
функционалу .
Выберем малое число , и, если
,
то вектор примем за собственный вектор матрицы , а число
за соответствующее собственное число.
Пусть произвольный единичный вектор. Определим матрицу,
действующую по формуле:
,
где единичная матрица.
Если и единичные векторы, то при прямыми вычислениями
получаем
где
Из этих равенств при малых получаем:
Рассмотрим разность
где .
Отсюда, при малых
(0.10)
где и величина допускает оценку постоянным числом при .
Пусть некоторое приближение к собственному вектору.
Если , возьмём . Тогда из (0.15) вытекает, что
.
Поэтому при малых отрицательных имеем . Выберем
из равенства
.
Число находим по алгоритму (А.4).
Пусть теперь . В случае, когда уравнение имеет же нулевое
решение, то собственное число матрицы . Поэтому по алгоритму
(А.3) (см. подпункт 3.2) находим собственный вектор. Если же уравнение
имеет только нулевое решение, то уравнение имеет решение .
В качестве возьмем
,
где удовлетворяет равенству .
Подставив в (0.10), получаем:
Отсюда вытекает, что, если выбрано малым, и выполнено , то при
имеет место
.
Поэтому
Из вышеприведённых выкладок следует, что вычисления собственного числа и
собственного вектора можно проводить следующим Алгоритмом 5.
Фиксируем малое . Возьмём произвольное и построим
следующим образом:
Обозначим единичная матрица,
.
а) Если , то положим
где выбираем из условия
б) Если же , то берём и построим векторы и числа по
формулам:
Построение продолжим до тех пор, пока не выполнится одно из следующих
условий:
б.1)
б.2)
б.3)
Так как собственное число существует, согласно выкладкам, проведённым выше,
найдется такое , что выполняется одно из этих трёх условий. За целое
число возьмём наименьшее целое, для которого выполнено хотя бы одно
из приведённых, трёх соотношений. Если выполнено условие б.3), то
собственный вектор, а собственное число матрицы . Поэтому
заканчиваем счёт. Если же выполнено условие б.2), то собственное
число матрицы . Собственный вектор найдём по алгоритму (А.3) и
заканчиваем счёт. Если, наконец, выполнено условие б.1), продолжаем
построение , выбрав по формуле:
где выбирается из условия
.
Счёт останавливаем, если . За собственное число берём число , а
за соответствующий собственный вектор . Имеет место теорема.
Теорема 3.3.1 Алгоритм А.5 приближенно вычисляет собственное число и
собственный вектор матрицы .
В подпункте 3.4 приведен численный метод определения кратности
собственного числа и вычисление присоединённых векторов.
1 НЕПРЕРЫВНЫЕ ВАРИАНТЫ ВАРИАЦИОННЫХ МЕТОДОВ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ
И СОБСТВЕННЫХ ВЕКТОРОВ МАТРИЦ
В первом разделе исследуется задача на собственные значения эрмитовых
матриц. Предлагается новый вариационный метод нахождения собственных
значений эрмитовых матриц. Для построения минимизирующей последовательности
необходимо уметь находить решение специальной задачи Коши для системы
обыкновенных дифференциальных уравнений.
1.1 Проблемы собственных значений и собственных векторов матриц
В книге [12] проблема делится на, так называемые, частичную и общую
проблемы собственных значении. К частичной проблеме Н.С.Бахвалов относит
задачу определения максимального или минимального по модулю собственного
значения матрицы, которая возникает, в частности, при решении некоторых
ядерных задач. Здесь приходится решать задачи, эквивалентные задачам
отыскания собственных значений матриц размерности порядка 103-106. При
меньших размерностях матриц для решения этих задач чаще применяют
итерационные методы, а при больших вероятностные. В колебательных системах
иногда требуется определить два максимальных по модулю собственных значений
матрицы, причем меньшее из них обычно достаточно определить с меньшей
точностью. Может возникнуть задача отыскания собственного значения,
наиболее близкого к данному числу. Общая или полная проблема собственных
значений состоит в определении всех собственных значений и всех собственных
векторов матрицы.
Задача определения собственных значений сводится к определению нулей
характеристического многочлена , где единичная матрица,
квадратная матрица размерности . На первый взгляд задача кажется очень
простой. Однако при больших значениях даже раскрытие определителя
связано с громоздкой и утомительной работой. В вычислительной
математике выработано много различных приемов и способов, облегчающих труд
по раскрытию определителя . На следующем этапе надо решать задачу
определения границ нулей характеристического многочлена , а затем
приближенно их находить.
Для матриц произвольного вида задача отделения корней
характеристического многочлена до сих пор в удовлетворительной форме не
решена. Отдельные успехи в этом направлении связаны со специальными
классами матриц. В частности, для эрмитовых матриц имеются довольно
эффективные вариационные методы. Их детальной разработке посвящен настоящий
раздел.
1.2 Вариационный принцип Вебера
В книге [7] показано, что стационарными значениями эрмитовой формы
на сфере являются собственные значения этой формы, и только
они, а стационарными точками ее собственные векторы и только они. Таким
образом, для нахождения собственных значений и собственных векторов
эрмитовой матрицы достаточно находить экстремумы формы при
ограничении . Чтобы избавиться от ограничения , надо изучить
экстремум формы . В книге [7] приведен вариационный принцип Вебера в
следующей формулировке:
Теорема (Вебера) Предположим, что собственные значения эрмитовой
матрицы занумерованы в порядке их неубывания . Если , то
есть минимум формы . Обозначим через вектор, на котором
достигается этот минимум. Следующее собственное значение есть минимум
формы при условии . Обозначим через вектор, на котором
достигается этот условный минимум. Следующее собственное значение
есть минимум формы при условии , . Точно также, при любом
, собственное значение определяется как минимум формы при
ограничениях , , ... , .
Таким образом, главная трудность состоит в конструктивном построении
минимизирующей последовательности, так как теорема Вебера не дает подобного
конструктивного алгоритма.
1.3 Конструктивное построение минимизирующей последовательности для
положительно определенной матрицы
Пусть положительно определенная матрица размерности . Через
обозначим вектор - столбец размерности . Считаем, что нуль не
является собственным значением матрицы. Предположим, что вектор
является дифференцируемой вектор-функцией параметра , причем при
эта кривая проходит через точку . Вычислим производную скалярной
функции
.
Производная дроби равна
Заметим, что величина принимает только действительные значения.
Тогда производная может быть записана в виде
Выберем функцию так, чтобы она удовлетворяла следующему уравнению:
(1.1)
Тогда примет вид
(1.2)
Следовательно, при производная принимает отрицательные
значения, а сама функция, , будет убывающей. Предположим, что
то есть не является собственным вектором матрицы . Тогда
.
Следовательно, функция , в окрестности , будет строго убывающей.
Пусть первый момент, когда обращается в нуль. Возможно
. Через обозначим предел . Указанный предел существует.
Докажем это. Умножим обе части равенства (1.1) скалярно на вектор . В
результате имеем
или
.
Следовательно, при любом справедливо тождество
. (1.3)
Равенство (1.3) представляет сферу в конечномерном пространстве,
которая, как известно, представляет собой компакт. Отсюда вытекает
существование предела . Переходя к пределу при в равенстве
(1.1), имеем
то есть
причем из (3) следует, что . Следовательно, собственный вектор
матрицы . Соответствующие собственное значение равно отношению
.
Как находить другие собственные вектора? Для этого возьмем , так,
чтобы выполнялось условие ортогональности из теоремы Вебера: , .
Пусть решение задачи Коши:
(1.4)
Умножим скалярно обе части уравнения (1.4) на вектор :
. (1.5)
Так как , то равенство (1.5) примет вид
(1.6)
Обозначим через . Выберем ортонормированный базис в конечномерном
пространстве так, чтобы первый элемент базиса был равен . Тогда вектор
разлагается по элементам выбранного базиса следующим образом:
,
Причем
где через многоточие обозначено выражение, не зависящее от . Тогда
уравнение (1.6) запишется в виде
(1.7)
где многоточие обозначает выражение, не зависящее от . Поскольку
при равно нулю и выражения в квадратных скобках из (1.7), не зависит
от , заключаем, что в любой момент времени .
Итак, при верно равенство, то есть , при всех ,
ортогонально собственному вектору . Пусть наименьшее из
(возможно, равное ), для которого вектор , из (1.4), обращается в
нуль. Доказывается, что существует предел , который представляет
собственный вектор матрицы . Этот вектор ортогонален вектору .
Теперь ясно, что надо делать, чтобы находить оставшиеся собственные
вектора. Надо решать задачу Коши (1.4) с начальным условием ,
предварительно выберев его ортогональным к уже найденным собственным
вектором . Этот процесс приводит к решению полной проблемы собственных
значении эрмитовой матрицы. Главная трудность заключается в эффективном
решении задачи Коши (1.4).
Сформулируем основной результат настоящего подпункта
Теорема 1.3.1 Пусть положительная матрица. Рассмотрим решение
задачи Коши
где . Пусть первый нуль величины . Тогда положим .
Построим с помощью рекуррентных соотношений где оператор
определен в предыдущей строке. Тогда ортогональные собственные
векторы матрицы .
1.4 Решение задачи Коши
В предыдущем параграфе мы задачу нахождения собственных векторов свели к
решению начальных задач Коши с теми или иными начальными векторами. Запишем
эту задачу
(1.8)
причем . В принципе, задача (1.8) нелинейная, однако нелинейный член
достаточно специфичен. Обозначим через функционал: . Перепишем
(1.8) в виде
(1.9)
Перепишем (1.9) в виде
сделаем замену
.
(1.10)
Тогда
(1.11)
из соотношения (1.10) имеем:
,
где решение задачи Коши (1.11).
Вспоминая определение функционала , получим уравнение для
определения .
(1.12)
где решение задачи Коши (1.11). Чтобы найти , надо при
каждом фиксированном решать, относительно , интегральное
уравнение (1.12). После определения , надо вычислить предел, при
стремящемся к первому нулю функции , которое обозначено через .
Итак, число представляет собственное значение матрицы .
1.5 Конструктивное определение минимизирующей последовательности для
самосопряженной матрицы
В подпункте 1.3 существенно использовалось то, что является
вещественной величиной. Это условие выполняется, когда положительно
определенная матрица. В то же время, когда является самосопряженной
матрицей, это условие может нарушаться.
Пусть самосопряженная, действительная матрица порядка
действительный вектор столбец порядка .
Предположим, что нуль не является собственным числом матрицы .
Обозначим через
где скалярное произведение в -мерном гильбертовом пространстве,
а норма, согласованная со скалярным произведением.
Если действительнозначная вектор-функция порядка , зависящая
от параметра и непрерывно дифференцируемая по , то будет
непрерывно дифференцируемой по .
Если то
,
Так как самосопряженная матрица, то в общем случае имеем:
Окончательно запишем
Возьмем удовлетворяющим уравнению:
. (1.13)
Это задача Коши. Умножая уравнение (1.13) на скалярно, получим
.
(1.14)
Действительно,
(1.15)
,
то .
Отсюда вытекает, что не зависит от , т.е. является постоянной:
. (1.16)
Подставляя (1.13) в выражение для , получаем, что
.
Действительно
.
Так как нуль не является собственным числом матрицы , поэтому
функция , по , строго убывает до тех пор пока .
Пусть , наименьшее значение для, которого (возможно,
) и
Существование легко вытекает из (1.16) в силу компактности .
Так как , то имеем
Отсюда вытекает соотношение
Следовательно,
Отсюда вытекает, что собственный вектор матрицы .
Следовательно, в силу самосопряженности имеем, что собственный
вектор матрицы . Но тогда, вычислив , получим, что
,
где действительное число.
Таким образом, наименьшее собственное значение матрицы найдено. В
дальнейшем собственный вектор обозначим через .
Возьмем теперь вектор ортогональный к собственному вектору, т.е.
и решим задачу Коши.:
(1.17)
Умножим (1.17) на скалярно
Так как
поэтому
(1.18)
Причем . Рассуждая также, как в подпункте 1.3, из уравнения (1.18),
получаем, что
, для всех .
(1.19)
Теперь найдем . В результате получим, что
Поэтому строго убывает до тех пор пока . Отсюда, аналогично
вышеуказанному получаем, что собственный вектор , где .
Здесь наименьшее из (возможно, равное ), для которого
, из (1.17) обращается в нуль. В силу самосопряженности , вектор
будет также собственным вектором . Тогда, вычислив , найдем
из равенства:
.
Вектор не совпадает с , так как . С другой стороны, .
Это следует из равенства , которое доказывается точно также, как было
доказано соотношение (1.16).
Пусть вычислены собственные векторы и соответствующие собственные
числа , при , матрицы . Возьмем такой, что
; при
Решая задачу Коши:
(1.20)
как и выше, получаем еще один собственный вектор матрицы ,
ортогональный всем и .
Из равенства , предварительно вычислив , найдем следующее
собственное значение .
Таким образом, мы получаем все собственные векторы и все собственные
числа матрицы . Следовательно, мы доказали теорему.
Теорема 1.5.1 Пусть самосопряженная действительная матрица.
Рассмотрим задачу Коши:
где .
Пусть первый нуль величины . Тогда положим
(1.21)
Построим с помощью рекуррентных соотношений.
,
где Т определено равенством (1.21).
Тогда ортогональные собственные векторы матрицы .
Далее числа , при , найдем из соотношений , которые
представляют соответствующие к ним собственные числа.
1.6 Численная реализация в случае самосопряженных матриц
Пусть задана симметрическая матрица c вещественными элементами. -
ый столбец матрицы будем обозначать через . Нормируем столбцы,
то есть вычислим вектор . Ясно, что величина отлична от
нуля, поскольку мы предполагаем, что нуль не является собственным значением
матрицы. Из всех чисел , при , вычислим наименьшее.
Пусть . Рассмотрим задачу Коши для дифференциального уравнения
первого порядка:
(1.22)
Умножим обе части дифференциального уравнения из (1.22) скалярно на
, и в результате имеем
или .
Следовательно, величина не зависит от , то есть равна
единице, поскольку она является таковой в момент . Поэтому в (1.22)
положим . Наша цель: решить задачу Коши (1.22) в интервале , где
первый нуль производной . Как было показано в п. 1.4, значение
, в общем случае, может быть равно бесконечности. Поэтому численное
решение задачи (1.22) возможно только на конечном интервале , при
. В результате при численной реализации предлагаемого в п. 1.5
алгоритма возникают погрешности, связанные с заменой требуемого интервала
на конечный интервал . Такую погрешность будем обозначать .
Другого сорта погрешности , возникают при дискретизации
дифференциальной задачи (1.22). Таким образом, погрешность появляется
при нахождении последовательности из системы:
(1.23)
где .
Заметим, что справедливо равенство
.
Следовательно, длина не меньше единицы. Поэтому можно
нормировать , а и векторы и не могут быть взаимно
ортогональными. Найдем выражение целевого функционала
Если взять , то имеем убывание целевого функционала
.
Итак, при каждом , шаг надо выбирать из условия:
(1.24)
Приведенные расчетные формулы (1.23), (1.24) пригодны, когда ищется
только один собственный вектор. Счет прекращается, когда убывание целевого
функционала становится незначительным.
2 ЧИСЛЕННЫЙ МЕТОД ТРЕУГОЛЬНОГО ПРЕДСТАВЛЕНИЯ МАТРИЦ
Наличие быстро развивающихся мощных современных вычислительных средств
оказывает большое влияние на развитие математики в целом. Особенно
подвержено этому влиянию вычислительная математика. Многие задачи требуют
создания быстро вычисляющих алгоритмов. Например, в задачах, связанных с
реальным использованием военной техники, численные расчеты должны
проводиться за доли секунды. Такие же высокие скорости вычислений, как
правило, требуются в задачах связанных с защитой информации, точнее в
задачах криптографии. Быстрота счета обычно достигается путем кропотливых
исследований и созданием сложных алгоритмов вычислений. На это тратиться
достаточно длительное время квалифицированного специалиста. Иногда у
пользователя возникает необходимость понимания сложного алгоритма, что
также требует много времени и высокой квалификации.
Существует много задач, которые не обязательно решать численно за малые
доли секунды, а достаточно, чтобы численное решение было готово за
определенный промежуток времени, исчисляемый несколькими часами. Для таких
задач, как правило, важнее простота алгоритма, а не быстрота вычислений.
При численном решении таких задач, предпочтительно “переложить” большую
часть работы на быстродействующий компьютер, и тем самым упростить труд
программиста или пользователя.
2.1 Вариационный метод приведения матрицы к треугольному виду
В данном подпункте мы предлагаем один алгоритм одновременного вычисления
всех собственных чисел конечномерных матриц.
Известен метод одновременного вычисления собственных чисел матриц,
изложенный в [13]. Наш алгоритм опирается на вышеуказанный метод,
обеспечивая при этом устойчивость счета, и, кроме всего прочего, отличается
простотой.
Пусть , в дальнейшем, означают квадратные матрицы порядка . В
классе таких матриц введем скалярное произведение
,
где по и ведется суммирование от 1 до . означает
комплексносопряженное число. Норму, соответствующую этому скалярному
произведению, обозначим через , как обычный модуль.
Лемма 2.1.1
Доказательство. Имеем
.
.
Лемма доказана.
Предположим, что обратная матрица и
.
(2.1)
Обозначим через нелинейный оператор, преобразующий матрицу
следующим образом:
при ,
при .
Здесь элементы матрицы .
Введем функционал
(2.2)
Лемма 2.1.2 Пусть удовлетворяет (2.1), ограниченная
обратимая матрица, тогда:
а) если матрица верхне-треугольная матрица, то .
б) если , то матрица есть верхне-треугольная матрица, и
существует треугольное представление .
Лемма очевидна. В силу этой леммы нам достаточно выбрать так,
чтобы функционал (2.2) обращался в нуль. Необходимый ищем в виде
матрицы - функций, зависящей от параметра . Выберем
произвольным образом. Имеем
.
Здесь .
Пользуясь леммой 2.1.1, получаем:
. (2.3)
Выберем , как решение задачи Коши:
(2.4)
При таком выборе из (2.3) имеем
. (2.5)
Отсюда следует, что
,
(2.6)
когда стремится к , минуя множество малой плотности. Более того,
. (2.7)
Поэтому, для достаточно больших , имеем
.
(2.8)
Из (2.5), (2.6) и (2.7) вытекает
Теорема 2.1.1 Пусть решение задачи Коши. Предположим, что
выполнено (2.1) и
.
Тогда существуют , такие, что пределы
существуют и
Доказательство. Существование пределов есть следствие компактности
рассматриваемого множества -мерных матриц. Равенство есть
следствие (2.5).
Теорема 2.1.2 Пусть выполнены предположения теоремы 2.1.1 ... продолжение
Вы можете абсолютно на бесплатной основе полностью просмотреть эту работу через наше приложение.
Похожие работы
Дисциплины
- Информатика
- Банковское дело
- Оценка бизнеса
- Бухгалтерское дело
- Валеология
- География
- Геология, Геофизика, Геодезия
- Религия
- Общая история
- Журналистика
- Таможенное дело
- История Казахстана
- Финансы
- Законодательство и Право, Криминалистика
- Маркетинг
- Культурология
- Медицина
- Менеджмент
- Нефть, Газ
- Искуство, музыка
- Педагогика
- Психология
- Страхование
- Налоги
- Политология
- Сертификация, стандартизация
- Социология, Демография
- Статистика
- Туризм
- Физика
- Философия
- Химия
- Делопроизводсто
- Экология, Охрана природы, Природопользование
- Экономика
- Литература
- Биология
- Мясо, молочно, вино-водочные продукты
- Земельный кадастр, Недвижимость
- Математика, Геометрия
- Государственное управление
- Архивное дело
- Полиграфия
- Горное дело
- Языковедение, Филология
- Исторические личности
- Автоматизация, Техника
- Экономическая география
- Международные отношения
- ОБЖ (Основы безопасности жизнедеятельности), Защита труда
