Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 48
Текст из файла (страница 48)
Кроме того, в силу симметричности матри. цы собственные значения являются хорошообусловленньзми.Вследующем разделе мы будем рассматривать задачу вычисления собственных значений для несимметричных матриц. В этом случае возможная плохая обусловленность собственных значений представляет серьезную проблему. Дополнительные замечания и ссылки б.2 Идея вычисления собственных значений симметричной матрицы с помощью первоначального приведения матрицы к трехдвэгонэльному виду была предложена в начале 1950-х годов Гивснсом, который использовал элементарные матрицы вращения, обнуляюшке по одному внсцивгонэлъному элементу.
Впоследствии Хаусхолдср заметил, что число арифметических операций можно сократить примерно вдвое, если ислользовазь ортогокэльные матрицы вида 16.2.3). Гивенс также разработал идею использования классических последовательностей Штурма для вычисления собственных значений трсхднагонзльной матрицы. Огромный вклад в понимание поведения этих методов при расчстэх на ЭВМ внес Уилкинсон; подробное обсуждение этих методов, включая анализ ошибок округления, можно найти в его классической книге 184].
Изложение с более теоретических позиций имеется в книге ]91], а обзор последних результатов содержится в книге ]5б]. Превосходные программы, реэлизуюшке методы Хаусхолдерв в метод половинного деленая, а также излагаемый в следующем разделе ]2Я-алгоритм, имеются в пакете ЕирасФ (см. 19, 73] ). Ранее уже упоминалось, что если матрица В невырождена, то обобщенная проблема собственных значений Ах= ЛВх может быть сведена к стандартной проблеме В 'Ах= Лх.
Однако даже если матрицы А и В симметричны, произведение В 'А не обязано быть симметричным. Если матрица В является, кроме того, положительно определенной, то можно претпложить другой вариант сведения, основанный на разложении Холецкого В '=ЕЕ . Тогда с помощью замены переменных у =Ьгх обобщенная проблема сводится к стандартной е 'А(е ') гу = лу с симметричной матрицей козффициентов.
Такое сведение часто оказывается удобным способом решения задачи, особенно если разложение В легко осуществляется. В качестве альтернативы мы в дополнительных замечаниях к следующему разделу упоминаем ДЕ-алгоритм, который непосредственно применим к обобщенной проблеме. УПРАЖНЕНИЯ б. 2 6.2.1. Пусть  — невырожденная матрица с собственными значениями Л,,... ..., Л„и соответствующими собственными векторамн т,,...,т „: а) покажите, что матрица В ' имеет собственные значения л, ',..., Л,,' и собственные векторы ч,,..., т„; б) покажите, что матрица  — л(, где и — скалярная величина, имеет собственные значения Л, — и;..., л„— л и собственные векторы т,,..., т„.
6.2.2. По методу Хаусхолдера приведите к трехдиагональной форме матрицу 2 1 1 А= 1 2 1 1 1 2 6.2З. Составьте програзаму, приводюцую произвольную вещественную симметричную матрицу размера л х л к трехдиагональной форме по методу Хаусхолдера. 6.2.4. Пусп Р =1 — лжм~, где ю — вектор, такой, что в ю = 1. Покажите, что Т Т матрица Р будет ортогональной в том и только том случае, если в = 2. 6 2.5. Для матрицы 2 — 1 0 В= — 1 2 — 1 0 — 1 2 выпишите полииомы р! нз (6.2.6) и убедитесь, что они обладают свойствами (6.2.7)— (6.2.9) . 6 2 6 Используя карманный калькулятор, с помощью последовательности Штурма определите приближенные собственные значения матрицы из упражнения 6.2.5.
Продолжайте вычисления до тех пор, 'пока все три собственных значения не окажутся заключенными в интервалы, длина которых меньше 0,01. 6.2.7. Для матрицы из упражнения 6.2.5 найдите приближенные собственные векторы, которые соответствуют приближенным собственным значениям, вычисленным в упражнении 6.2.6. 6.3. ДМ.ч(лгоритм Теперь перейдем к проблеме вычисления собственных значений для несимметричных матриц.
Это намного более трудная. задача, чем в случае симметричных матриц, и хорошие методы ее решения оказываются значительно сложнее методов, изложенных в предыдущем разделе. Еще более существенным является то, что собственные значения несимметричной матрицы могут быть очень плохо обусловленньпчщ.
Покажем зто на простом примере. Пусть А и 8 — следующие матрицы размера л Х и: О 1 0 1 2 (6.3.1) А = (6.3,6) О е О Ясно, что матрица А имеет и-кратное нулевое собственное значение, а собственные значения матрицы В удовлетворяют характеристическому уравнению Л" — е = О,так что !Л~!=1е! ~, 1=1,...,п. (6.3.2) Предположим, например, что и= 100 и е = 10 '~~.
Тогда ! Лр! = 10 ', т.е. изменение одного элемента матрицы вызвало в 10аа раз большее изменение собственных значений. Отметим, что это тот же самый пример, который мы испольэовали в разделе 4.2 для демонстрации возможной плохой обусловленности корней полинома, только переформулированный как задача на собственные значения. Эта возможность плохой обусловленности собственных значений не позволяет рассчитывать, что найдется такой метод, который будет точно вычислять собственные значения для всех несимметричных матриц.
Если задана матрица А, то в очень хорошем случае можно надеяться, что метод будет давать достаточно точные собственные значения для матриц вида А + Е, где элементы матрицы К в каком-то смысле малы. Если все же вычисленные собственные значения будут заметно отличаться от точных, то это объясняется плохой обусловленностью этих собственных значений.
Теперь рассмотрим два тесно связанных между собой метода — ЛЯ- и ДЯ-алгоритмы. Пусть нам задана матрица А, С помощью алгоритма гауссова исключения разложим ее в произведение А =ЕК (6.3.3) где Š— нижняя треугольная матрица с единицами на главной диагонали, а Я вЂ” верхняя треугольная матрица, Отметим, что мы здесь предполагаем воэможность представления матрицы А в виде произведения верхней н нижней треугольных матриц; кюс мы видели в гл, 3, это имеет место не всегда.
Введем теперь новую матрицу А ~, изменив порядок множителей А ий,т.е. А, =ВА. (6.3.4) Так как Е является нижней треугольной матрицей с единицами на главной диагонали, то она невырождена, и мы можем написать А =ЬВ =С(ЯЬ)А ' =ЬА,А ', (6.3,5) Отсюда видно, что А и А ~ подобны и, следовательно, имеют одинаковые собственные значения. (См. упражнение 6.3.1, где сформулирован более общий результат.) Предположим, далее, что матрипу А, можно разложить в произведение нижней треугольной матрицы Х ~ и верхней треугольной матрицы Я, . Введем новую матрицу Аа, поменяв порядок сомножителей: А~ =А~Я~, Аа =.К~Ус.
И' снова матрица Ат подобна'А1. Мы можем продолжить этот процесс. факторизации и перестановки сомножителей, получая последовательность матриц, Ау =ЕкЯк, Ак+1 =ЯкАк, й=1,2,... (6.3.7) Все матрицы А к подобны и, следовательно, имеют те же собственные значения, что и исходная матрица А. Имеет место следующая теорема, доказательство которой выходит за рамки настоящей книги. Т е о р е м а 6.3.1.
Предположим следующее: 1) может быть выполнен ЬЯ-алгоритм (6.3.7); 2) все собственные значения К,,...,Х„различны по абсолютной величине и ! Х, ! >...> ! Х„1; 3) если А = РРР '., где Ю вЂ” диагональная матрица из собственных значений матрицы А, то матрицы Р и Р ' допускают Е Ьразлоясение. Тогда матрицы Ак в (6.3.7) сходятся к треугольной матрице Х, ь... ь 1~1 - ° ° (6.3.8) 1~и — 1 Х„ где звездочкой обозначены элементы, в общем случае отличные от нуля.
Обратите внимание, что условие 2) исключает не только кратные собственные значения, но в случае, если матрица А вещественная, то и невещественные собственные значения. Два других предположения тоже весьма ограничительны и трудны для проверки. Хотя некоторые из этих ограничений можно обойти, мы, вместо этого, сейчас обратимся к другому методу, близкому к изложенному. Основная идея 1гЯ-алгоритма та же, что и в ЬЯ-алгоритме, но в нем используется разложение в произведение ортогональной матрицы и верхней треугольной матрицы: исходя из матрицы Аь =А и осуществляя поочередно факторизацию и перестановку сомножителей, мы получаем последовательность матриц Ак =ЬЯк, Ак+1 =ЯвОк (63.9) й= 0,1,...
где каждая иэ матриц Дк является ортогональной. (Мы предполагаем, что матрица А вещественна; в случае невещественной матрицы А матрицы !гк были бы унитарными.) Мы сейчас покажем, что (гЯ-разложение очень легко осуществляется с помощью преобразования Хаусхолдера, описанного в предыдущем разделе, Пусть вектор ~ч1 выбран так, что т и1 =д(а1, — з, аа1,...,а„,), л зы( 2' а2 )1/2 (6.3.101 д =[2з (з — а )] Тогда, как легко проверить (упражнение 6.3.3), (6.3.11) А121=(1 — 2м,ю~~)А = где,.
как обычно, звездочкой обозначены элементы, в общем случае от. личные от нуля. Выберем далее вектор юг так, что н э=~( Х а;) /=2 л л л л л ~чг =Р(О*агг — ~. азг . а~г) р = [2э(э — агг)1 где крышечкой помечены элементы матрицы А ~~1. Тогда лежащие ниже главной диагонали элементы двух первых столбцов матрицы (1— 2вгм>г~)А121 обратятся в нуль. Продолжая этот процесс с помощью векторов и«, „имеющих нули в первых 1 — 1 позициях, получим (1 — 2и„, и „1)... (1 — 2гчгюг )(1 — 2в,в~ )А =Я, (6.3.12) где Я вЂ” верхняя треугольная матрица.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
