Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 64
Текст из файла (страница 64)
)(ля пояснения мгя предположим, что матрица А положительно определена, что не нарушает общности, так как любую симметричную матрицу можно сделать положительно- определенной за счет добавления скалярной матрицы, причем прн таком преобразовании собственные векторы не меняются, а все значения отношения Редея (в частности, все собственные значения) изменяются на постоянное слагаемое. В этом предположении отношение (АХ, Х) 1 Релея р(Х)= ' есть, очевидно, —,, где р †дли вектора, исходящего нз ж начала координат в направлении вектора Х до пересечения с эллнпсоидом (АХ, Х)= — 1. Векторы Х'=Х+аУ лежат в плоскости (двумерном подпространстве), натянутой на векторы Х н У. Эта плоскость пересекает эллипсоид (АХ, Х) = 1 по эллипсу, причем отношение Релея достигает максимума на векторе, направленном по малой оси этого эллипса и минимума на векторе, направленном по большой осп эллипса (см.
рис. 3). Может случиться что вектор У направлен по одной нз осей этого эллипса. Вот именно в этом случае один из корней уравнения (3) обрашается в бесконечность. Наконец, может случиться, что эллипс вырождается в окружность. Рис.
3. Тогда уравнение (3) обращается в тождество, и а может быть взято произвольным. Заметил~ сразу, что если при некоторых Х и У получается не круговое сечение и мы сделаем достаточно малую деформацию векторов Х и У, то направление осей эллипса изменится сколь угодно мало. Неслогкное вычисление дает, что экстремальное значение р' равно где г(=-(Х, Х)(У, У) — (Х, 1')', 3=(АХ, Х)(У, У) — (АХ, У)(Х, У) и а = (АХ, 1)(у, у) — (Ау, у)(Х, у) есть коэффициент при аз в уравнении (3).
Так как сг) О, то из (4) следует, что для получения максимума Р' нужно брать больший корень уравнения (3) при а ) О и меньший корень уравнения при а ( О. Координатный релаксациопный метод заключается в том, что за вектор У на каждом шагу процесса берется один из координатных векторов еп 380 ЧАСТИЧНАЯ ПРОБЛЕА!А СОБСТВЕННЫХ ЗНАЧЕНИЙ [ГЛ. Ч Пусть Х=-(хм ..., х„)'. Введем обозначение Р=АХ=(7», ..., г'„)' р=(АХ, Х) ,7=(Х. Х). (б) Тогда (Х, АУ) = (Х, Ае») = (АХ, е;) = у» (А У, У) = (Аен е») = ан (1", У) =(еь е;) =1 (Х, У) =(Х, е;) =хо (б) Квадратное уравнение для определения а перейдет в уравнение аа [7» — анх»[+ а [р — а»»о[+ рх; — »'Ру = О.
(7) Выбрав соответствующий корень, определим следующее приближение Х' = Х+ ае». (8) Для этого приближения будем иметь »' = АХ' = АХ+ аАе, = Г+ аАО (9) где А; есть»-й столбец матрицы А. Далее р'= (АХ', Хх) =(Р', Х') = р+ 2ау»+ а»а»», 7' = (Х'. Х') = »1 + 2ах»+ а'-'. (10) р — у»х» + аа р' (11) ») — ха (»' которое можно использовать для контроля вычислений.
Максимизация отношения Релея за счет изменения вектора в данном направлении может осуществляться несколько иначе, чем было описано выше. Таким образом, величины р', »1' и компоненты вектора Р', нужные для проведения следующего шага, легко вычисляются. Если на следующем шаге менять у-ю компоненту 7'+1, то в квадратном уравнении нужно заменить а», на а., х» на х', 7» на 7,, »[ на»1' и р на р'.
Выбор номеров изменяемых компонент может осуществляться различно. Простейшей возможностью является ц и к л и ч е с к о е чередование индексов. Ввиду возможного накопления ошибок округления время от времени нужно вычислять величины»1, р и у» (1 =1, 2...,, а) непосредственно по определяющим их формулам. Огметим также соотношение з 61! 881 кооРдинАтнля РелАксАция По существу нам нужно найти максимум отношения Редея — в плоскости Х'= с,Х+ саУ, натянутой на данные век- (АХ', Х') (Х', Х') торы Х и Считая Х' нормированным вектором ((Х', Х)=1), мы придем к задаче об отыскании максимума квадратичной формы (АХ, Х)с,+ 2(АХ, У)с,с +(АУ, У) с, (12) при условии (Х, Х) с»+ 2 (Х, У) сссз+(У, У) с" = 1.
Решая зту задачу методом множителей Лагранжа, мы придем к системе уравнений для определения коэффициентов с, и са [(АХ, Х) — р(Х, Х)[с,+[(АХ, У) — (Х, У) р! с. = О, [(АХ, У) — (Х У) р! с, + [( А«', У) — (У, У) р! са = О, (14) ! (АХ, Х) — (Х, Х)и (АХ, У) — (Л", «')н ~ (АХ, У) — (Х, У) и (АУ, У) — («', «') ц ! =- О. (15) Больший корень этого квадратного уравнения будет давать значение искомого максимума р', коэффициенты же с, и сз определяются нз системы (14) после подстановки в нее вместо и найденного значения р'. Для отношения с, и с, получаем са (АХ, Х) — (Х, Х)Р' (Х, У)Р' — (АХ, У) с, (Х, У)н' — (АХ, У),(АУ, У) — (У, У)н' ' Так как, в конце концов, нормировать вектор Х' нет необходииостя, можно полагать Х' = Х+ ау.
В случае координатной релаксации, когда У=- сь получим в прежних обозначениях, что р.' есть больший корень квадратного уравнения (д — х;) уз — (апс«+р — 2хА) и+ анр — г', =- О (17) Х' = Х+ аео (18) где ди' — р б — хси' ус — хе»' Р' — ан (19) Переход к следующему шагу осуществляется так же, как в прежней схеме. Хорошим контролем является выполнение равенства р'= ~ —,. л откуда следует, что множитель Лагранжа р является корнем квадратного уравнения 382 ЧАСТИЧНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ [ГЛ. у Циклический координатный процесс оказывается сходящимся почги всегда, однако доказательство сходимости мы дадим при не- которых ограничениях. Теорема б1.1. Пусть матрица А симметрична и ее наиболь- шее собственное значение )ч простзе.
Пусть начальный вектор Хо (АХо Хо) выбран тас, что 11 — -' — ) )чи где )г — второе, в сгорядке убы(Хо "о) вопия, собственное значение матрицы А и что 2) — — ' — ) (4Хо Хо) (Х,,'Х„) (Аеи е;)= —:аи при всех 1=-1. 2..., и. При этих условиях последовате,гьные лриб гизкенигг Хь в циклическом координатно.и сгроцессе сходятся ло направ,гению к собственнолгу весстору, отвечаюсцему собственному значению ) .
Доказате.льство. Будем предполагать, что на каждом шзге процесса последовательные приближения нормируются к единичной длине н из двух взаиино противоположных нормированных векторов выбирается один в некоторой фиксированной полусфере. Обозначим через О совокупность векторов длины единица, удовлетворяющих условиям 1) и 2) теоремы и лежащих в выбранной полусфере, Из условия теоремы следует, что начальное приближение принадлежит области О. Все последующие приближения будут также принадлежать области О, ибо по ходу процесса отношение Релея не убывает. Рассмотрим подробнее отдельный шаг циклического координат- ного процесса.
Пусть Х вЂ” некоторый вектор из области О. Обозна- чим через р;(Х) нормированный вектор, взятый в выбранной полу- сфере, на котором достигается максимум (АХ, Х) в подпространстве, натянутом на векторы Х и ер В силу второго условия теоремы (АХ, Х) ) (Аеь е;) и потому вектор рг(Х) определяется однозначно. Из приведенных выше геометрических соображений очевидно, что нелинейный оператор гуг непрерывен в области О, В новых обозначениях процесс может бьжь описан следуюшим образом Х, = гуг(Хо), Х, = гуг (Х,)...,, Х„= ри (Х„,) Х„ьг=-рг(хп),, Хоь З вЂ” — рс.(Х„ч С 1), 0=-1, 2, " и) Через уо, у,, ...
обозначим значения (АХо, Х,), (АХ,, Х,), ... функггионала (АХ, Х). Эти значения удовлетворяют неравенствам уо-(р, (уг (... и ограничены сверху числом с, Следовательно. сушествует 11ш у„= [ь, ь+о РассмотРим последовательность вектоРов Х,, Х,ог, Хг„ог, ... Все векторы этой последовательности находится в области О. В силу ограниченности и замкнутости единичной сферы из этой последовательности можно извлечь сходящуюся последовательность Х„ь ьг. Пусть У есть предел этой последовательности.
Вектор г' находггтся внутри области О, ибо (Аг, )) = — р ) ро ) шах(А,, (Аео е) ). 383 ф 61) кооРлинатнАя РелАксАция В силу непрерывности оператора эз в области О имеем У = та(У) = Иш <р~(Х~А ~~) = !Цп Хяа ьз. Следовательно,(АУ, У)=!!ш(АХ„А,ю Х„а Аз)=р. Но по опреде- "Ф лению оператора эз на векторе У достигается максимум (АЕ, Л) в плоскости, на гянутой на У и ез н этот максимум равен Р = — (АУ, У))(Аеа е,). Следовательно. У =-- У.
Точно так же доказывается, что э,(У) =- !'..., ..., "А (У) == У, о, (У) = У, так что вектор !' оказываешься пеползнжным для всех оперзторов эг (! = 1, 2, ..., Л). Это значит, что зз счет изменения каждой отдельной координаты вектора У отношение Релея не может быть увеличено. Следовательно, все частные производные отношения Релея в точке У равны нулю и, следовательно, У есть собственный вектор. Но, в силу условий 1) и 2) теоремы, это может быть только собственный вектор, соответствующий наибольшему собственному знзчению ), Итак, единственной предельной точкой последовательности Х,, Х„„, Хз„„,, ...
является собственный вектор, отвечающий наибольшему собственному значению. К тому же вектору сходятся и остальные последовательности Хь Х„„, Х,„,,..., а потону и вся последовательность Х,, Хе, ... Теорема доказана. 3 а м е ч а н и е. Условие 2) теоремы не является существенным, ибо оно, вообще говоря, будет выполняться автоматически после провелення первого цикла процесса при любом выборе начального вектора. Если же снять первое ограничение, то, повторяя доказательство, мы получим, что каждая предельная точка последовательности Ха, Хо Х,, ...
является собственным вектором матрицы А. Если допустить, что собственные значения матрицы А различны, то, в силу равенства отношения Релея на всех предельных точках, мы можем заключить, что предельная точка единственна, т. е. последовательность Хз, Х,, ... сходится к некоторому собственному вектору. Одна«о этот собственный вектор не обязан принядлежзть наибольшему собственному значению, что можно проиллюстрировать на следующем примере. Пусть 35 — 22 8 — 22 38 14 8 14 53 /2 ! 2Ъ' Если взять в качестве начального вектора Хе=-!А —, — —, — ),то ~3' 3' 3) ' окажется, что все последовательные приближения будут равны Хз. 384 частичная пговлемл совстванных значений (гл. ч Легко проверить, что Хв есть собственный вектор, отвечающий собственному значению )я=54.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
