Беклемишев - Дополнительные главы линейной алгебры (947281), страница 38
Текст из файла (страница 38)
Характеристическое уравнение матрицы Р можно преобразовать следующим образом; с(е1(Р -ЛЕ) де1 (0+ вЕ)-1 1)е([(! — в) 0 — вУ вЂ” Л (0+ вЕ)!. Отсюда видно, что характеристические числа матрицы Р совпадают с корнями уравнения бе1 ((1 — в) 0 — вУ вЂ” Л(0+ вЕ)')= О. (1О) Введем в уравнении (10) вместо переменной Л переменную $> связанную с Л соотношением Л= —. 5+1 4 — 1' $4.
ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ 169 Легко видеть, что условие ! )с ! ( ! равносильно условию 1се $ ( О, а уравнение (10) перейдет в с)е! 1 — соАс — (2 — со) Р + со (У вЂ” 1.)1= О. (11) Мы получили П р е д л о ж е н и е 5, ссс!етод верхней релаксации сходится тогда и только тогда, когда весцественные части всех корней уравнения (11) отрицате,сьны. Это позволяет получить следующее достаточное условие.
П р е д л о ж е н и е 6. Для сходимосссги метода верхней релаксации достаспочно, чтобьс матрица А была симметричной и полоохсстельно определенной и чтобы со Е (О, 2). Для доказательства напишем уравнение (11) для симметричной матрицы А и рассмотрим корень ьо этого уравнения. Для Ео существует (вообще говоря, комплексный) ненулевой столбец х такой, что ( — соА 54 — (2 — со) Р т со (У вЂ” Е)) х = О, и потому соь хгАх (2 со) хгРх + сохт (У /) х 0 (12) Матрица У вЂ” й кососимметрична, и для нее мы имеем хг (У вЂ” /.) х = ( — хг ((/ — й) х) г = — х' (У вЂ” Е) х = — х' (У вЂ” Х) х.
Поэтому последний член в равенстве (12) имеет нулевую вещественную часть. Ассалогично доказывается, что ххгАх и хгРх вещественны. Кроме того, если А положительно определена, то все ее диагональные элементы положительны, и квадратичная форма хгРх также положительна определена. Приравнивая нулю весцественную часть (12), имеем и — 2х Рх -г ссе $„= — = со хг Ах (13) Если со ~ (О, 2), то (со — 2)/ы ( О. Отсюда следует, что ссе ео ( О. Предложение доказано. Предложение 4 следует отсюда как частный случай прн ас = 1.
Формула (12) позволяет высказать некоторые соображения о выборе параметра со в случае симметричной положительно определенной матрицы А. Предположим, что корни (11) вещественны, и перепишем (13) в виде ео — — — ар, где а = (2 — со)/со, а р = = (хгРх)/(хтАх). Значению А= 0 соответствует значение $ = = — 1, Мы должны выбрать а таким образом, чтобы $ было возможно ближе к — 1. Оценим р. Для этого можно воспользоваться результатом 9 2 гл. 1, согласно которому р заключено между минимальным и максимальным корнями уравнения бе! (Р— )сА) = О. Обозначим эти корни соответственно р, и р,. Тогда все корни уравнения (11) заключены между — ар, и — ар,. Для того чтобы приблизить эти ГЛ. ПЬ ВВЕДЕНИЕ В ЧИСЛЕННЫЕ МЕТОДЫ границы к — 1, мы должны так выбрать а, чтобы наибольшее из чисел 11 — ар, 1 н 11 — ар, ~ было минимальным. Это равносильно тому, чтобы минимальным было наибольшее из чисел )а — р,' 1 и ~ а — р,' ~. Последнее будет достигнуто, если а— середина отрезка (р,', р,'1.
Такой выбор а не является наилучшим, но дает приемлемые результаты. В общем виде задача о нахождении наилучшего а решена, но решение достаточно сложно, и мы не будем на нем останавливаться. й 5. Вычисление собственных векторов и собственных значений 1. Вводные замечания. В этом параграфе мы рассмотрим задачу нахождения ненулевых решении системы уравнений Ах=Хх, которые, допуская некоторую вольность речи, будем называть собственными векторами матрицы А. Различаются две постановки этой задачи: нахождение всех характеристических чисел и соответствующих собственных векторов называется полной проблел"ой собственных значений, а нахождение одного или немногих из ннх носит назнание чостичной проблелны собственных зночений. Понятно, что проблема собственных значений, как полная, так н частичная, намного сложнее, чем рассмотренная выше задача решения системы линейных уравнений.
Среди большого числа алгоритмов, предназначенных для ее решения, нет такого, который можно было бы рекомендовать во всех случаях, хотя некоторые из алгоритмов и выделяются своей эффективностью среди остальных. Некоторые алгоритмы особенно эффективны в специальных случаях, например специально приспособлены к симметричным пли к ленточным матрицам.
Все имеющиеся методы решения проблемы собственных значений могут быть разделены на две большие группы: прямые методы, основанные на решении характеристического уравнения, и итерационные методы. В прямых методах важным этапом является нахождение коэффициентов характеристического многочлена, так как их вычисление на основе общих формул, прямо следующих из определения, требует осуществления очень большого числа арифметических операций. Вычисления, проделываемые для нахождения характеристического многочлена, обычно могут быть использованы для нахождения собственных векторов, Результат, получаемый прямыми методами, является в принципе приближенным (т.
е. даже если не говорить об ошибках округления), так как корни характеистического многочлена могут быть найдены только приближенно. не будем излагать здесь прямых методов решения проблемы собственных значений. О них можно прочесть в книгах Гантмахера 181, Д. К. Фаддеева и В. Н. Фаддеевой (351. $ К ВЫЧИСЛЕНИЕ СОБСТВЕННЫХ ВЕКТОРОВ 171 Типичным итерационным методом является метод вращений, или метод Якоби.
Исходная симметричная матрица А подвергается последовательно ряду преобразований вращения, рассмотренных нами в 2 3 при построении !',1»1-разложения. Однако, в отличие от ДР-разложения, па каждом шагу преобразование производится по формуле А'»"'=Т ' А'"!Т »+ !».,1, где А по — матрица, полученная после Й-го шага, а Т»+т — матрица вращения.
По этой формуле в общем случае невозможно за конечное ч«ело шагов привести матрицу к такому виду, для которого характсркст;шсск«е числа устанавливалпсь бы непосредственно. Очередное (й--1)-е вращение выбирается так, чтобы обратить в «уль наиссльш«й по модулю внедиагональный элемент матриц«! А""' илп, если это затруднительно, любой элемент, превосходящий некоторое заданное число. В других вариантах уменьшается сумма квадратов внед1ягональных элементов и:и вообще какая- либо норма матр:шы Л!"', получаемой из А!»! заменой диагональных элс:!е»поз на О. В результате после достаточного числа К шагсв матрица А!"! Оказывается близкой к д !«гол!Ельной и имеет Ге же характеристиче ск«е числа, что и А.
Диагональные элементы А!"! принимаются за прп!Ки!»кс!и!Ые значения характерисп ческпх чисел, а столбцы матрицы Т = Т, ... Т,— за приближенные собственные векторы. Иа методе вращений Гюлее подробно останавливаться мы не будем, Замети.!, что этот метод„как и другие итерационные методы, ввиду большой трудоемкости получил распространение только после появления электронных вычислительных ли«ппн, однако он является одним из наиболее эффективных методов для симметричных матриц.
2. Степенной л!етод. Эгот метод приланлется для решения частичной проблемы собственных значеюш. В простейшем варианте (ярялсй сте!!виной метод без сдвигов), нашная с произвольного векторах„строится последовательность векторов х„х„... по форл!улам Ах»=у;,», х»„— — а»'ь«у»»„ причем положительный множитель а»!, выбирается так, чтобы 1! х»», !! = 1. Очевидно, что эта же последовательность может быть задана формулой р»х» — — А»х», (2) где р» —— а!...а».
Каким из выражений (1) или (2) следует пользоваться — вопроо зкономии числа арифметических операций. Как правило, используется формула (1), так как, скажем, для получения хэ по формуле (2) нужно умножить матрицу А на столбец п + 1 раз, а для получения по формуле (1) — всего 2 раза. Однако дпя больших Гл, и!. введение В численные методы степеней, вычисляя А», АО, А', ... последовательным возведением в квадрат, можно получить результат по формуле (2) за меньшее число операций. Допустим, что среди характеристических чисел матрицы А есть вещественное число Л„по модулю превосходящее остальные.
При этом условии мы можем доказать, что построенная последовательность сходится. С этой целью напишем спектральное разложение АО по формуле (!5) З 3 гл. 11. Мы получим О!! 0»»г»= ~ ~.', (Л1)™4!хо. 1=1)=! Здесь числа т! — кратности корней Л, в»1иннмальном многочлене, а Лп — постоянные матрицы, называемые компонентными матрицами. Разделим обе части равенства на я"-1Л1. Тогда О! 7»ХО =,У~ ~ т»1)А1)ХО. (4) 1=1!=1 Здесь 7„.= РОЯ-! +1Л, ", а коэффициенты тмт, выполнив диффеРенцирование, мы можем записать следующим образом: »(ь )) ... (» )+2)(лПО-/+! Ь' -'Л)-' (,Л ) ! 1 Л! При ~.— '~(1 очевидно, что тмт -1- О при й — 1- со.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
