Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 66
Текст из файла (страница 66)
Положим В=А — Ао, р =),— )„. Тогда имеют место соотно- шения ( (р Е В) Х Хо) = 0 (Š— й(рŠ— В) )Х= Хо (10) (1 1) Действительно, (рŠ— В) Х (ЛŠ— А) Х вЂ” ()~Š— Ао) Х = (Ао — )чЕ) Х, так что ((ОŠ— В)Х, Хо)=(Х, (Ао — )оЕ)Ло)=-О. Далее, (Е й(1АЕ В)) Х=Х й(Ао — )ЧЕ)Х= Х А = Хо. При малых !(о( и ((В~! правую часть равенства (12) можно разложить в ряд. Ограничиваясь членами второго порядка и принимая во внимание, что йХо=О, получим приближенную формулу Х Хо — йВХо+ йВйВХо — рзйзВХо, (13) которая вместе с (10) дает (ВХм Хо) — (йВХо, ВХо)+(ВйВХо йВЛ;) 1Х !!о+ 11 йХ 1! Для применения изложенного к задаче об уточнении отдельного собственного значения симметричной матрицы воспользуемся приемом .ложного возмущения', также предложенного М.
К. Гавуриным'). Пусть для симметричной матрицы А известен приближенный нормированный собственный вектор Хо и приближенное собственное значение )о — — (АХо, Х,). Построим матрицу / Ао = А — Хог гЛо где г = АХо — )еХо. Ясно, что Ао симметрична, и легко проверяется, что для нее вектор Хо является собственным вектором, принадле- жащим собственному значению ) . ' А) М.
К. Г аз урн н. Успехи матем. наук, 1957, 12, № 1, 173 — 175. Если матрица Š— й(рŠ— В) невырожденная (что будет иметь место, например, если ~ р) и ()В,/ достаточно малы), то формула (11) эквивалентна формуле Х= (Е й(рЕ В) ) Хо. (! 2) 9 62) гточнвния отдельного совстввнного значения 391 Приближенные формулы (13) и (14) превращаются в (15) Х Хз — гсг — айаг (Йг, г) 1+ 11)7г1~"- ' (16) Уточнив по формулам (15) и (16) собственный вектор и собственное значение, можно повторять процесс до получения требуемой точности. Векторы )сг и й'г находятся соответственно нз систем линейных уравнений (17) (А — ), Е)Л =г (к„Х) =0 (А,— ),Е)г=)7г (К, Х,)=0.
(18) Так как ! Аз — )чС ) =.О, одно из а первых уравнений в системах (17) и (18) может быть отброшено и использовано лишь для контроля. Если в формуле (15) отбросить член (ь)саг второго порядка малости, то отпадает необходимость в решении второй системы. Отметим, что метод может применяться, начиная с довольно грубых приближений для Х,. На описанный здесь прием реализации метода возмущений обратил внимание авторов Л.
А Руховец. Для матрицы (4) в 51 имеем ), 0.24226071, Х=(0.718846, 0.095699, — 0.387435, — 0.569207)'. Исходя из приближения Х„ = (О.?04361, 0.176090, — 0.440225, — 0.528271)', полученного нормированием вектора (0.8, 0.2, — 0.5, — 0.6)', и ) = (АХ, Х ) = 0.248992, получим, после однократного применения формул (15) и (16) и нормирования, Х, = (0.718839, 0.0957 17, — 0.387445, — 0.569206)', )ч = 0.24226072. При проведении итерационного процесса посредством и-кратного повторного применения формул (15) и (16), быстрота сходимости имеет порядок ф", если же пользоваться упрощенной формулой (15) с отброшенным членом р)7зг, то быстрота сходимостн будет иметь порядок 9з .
Здесь д = зВ 11г11 ~ — 21г11 где г невязка начального приближения, т расстояние от уточняемого собственного значения до ближайшего соседнего. Эти оценки нам сообщены М. К. Гавуриным. ГЛАВА Ч! МЕТОД МИНИМАЛЬНЫХ ИТЕРАЦИЙ И ДРУГИЕ МЕТОДЫ, ОСНОВАННЫЕ НА ИДЕЕ ОРТОГОНАЛИЗАЦИИ Методы, которые будут описаны в этой и следующей главах, применимы к решению системы линейных уравнений и к решению проблемы собственных значений — полной (гл.
Ч1) н частичной (гл. Ч!1). Хотя исторически некоторые методы, описанные в гл. Ч1! (в частности, метод наискорейшего спуска), появились ранее методов гл. Ч!, мы излагаем сначала эти последние, ибо появление их позволило упростить и развить дальше первые. Несмотря на то, что методы гл. Ч1 являются точными, а методы гл. Ч11 итерационными, их вычислительные схемы по существу имеют один рисунок. й 63. Метод минимальных итераций 1.
Построение базисных векторов в невырожденном случае. Пусть матрица А симметрична. Метод минимальных итераций' ) для решения полной проблемы собственных значений есть не что иное, как метод ортогоналиаации последовательных итераций некоторого начального вектора (6 50). Однако мы изложим его независимо от результатов 6 50, ввиду возникновения многих важных особенностей метода, наличие которых позволяет обобщить метод и расширить область его применения.
Будем в этом пункте предполагать, что симметричная матрица А имеет попарно различные собственные значения )ч, )а ..., Х„. Пусть Оы (Уз...., ((„сэответствующие им собственные векторы, которые мы будем считать нормированными. Выберем некоторый начальный вемтор Х. Он может быть единственным образом представлен в виде Х=а,(У,+аз()з+ ... + а„()„. Будем далее пока предполагать. что все коэффициенты а! чь О. Тогда система векторов Х, АЛа, ..., А" 'Х будет линейно-независимой.
т) Л а и ц о ш (2). 393 9 631 метод минимальных итвглций Теорема б3.1. Если векторы Х, АХ, ..., А" 'Х линейно-независильы и векторы Рв, Р,, ..., Р„, полУчены из них пРи помощи процесса ортогонализации, то зти векторы определяется по трехчленным рекурренпьным формулам р<,=Арь — иьрь — ~ьрь ь (1=1, 2, ..., п — 2) (2) Ро=Х Рь = Арв в.орв где иь = — ' (ь'= О, 1,..., и — 2) (Арь, Рь) (Рь Рь) (Арир-.) (Ри Арь-ь) (Рирь) (, 1 2 „2) (Рь-» Рь-ь) (Рь ы Рь-<) (Рь-ь Рь-ь) (3) Доказательство. Пусть Х, АХ, ..., А Х линейно-независимы, и векторы р, р„, ..., р„, получены из них процессом ортогонализации.
Тогда рь= А'Х+с<НА' 'Х+ ... +сь<ОХ. О~сюда следует, что вектор рьч, — Ар, принадлежит подпространству, натянутому на векторы Х, АХ, ..., А<Х, или, что то же самое, надпространству. натянутому на векторы рш р,, ..., Ро Итак, вектор р,е, выражается через предшествующие по формуле Р =А.о — <<ор — .. — (ньр ьеь ь ь' ь ''' О 0' где (ь<ьь, ..., .1<'> некоторые числа.
Из соотношений ортогональности вектора рье, к предшествующим векторам получим Рь РЬ) (Рз Рз) <ь) ( Рь Р ) (Рь Рь) (АРь, Рь,) (Рь, АРь д) (Рь-ь Рь-ь) (Рь-ь Рь-ь) Палее, (Рь Арь-ь) = (Рь' Рь + "ь-ьрь-ь + рь-ьрь-г) = (Рь Рь) (ч) и, следовательно, Но при /=О, 1, ..., 1 — 2 имеют место равенства (Арь, рь)=О, ибо (Аро рз)=(ро Ар)), а вектор Ар) есть линейная комбинация векторов РВ~ь, ру...., ре, каждый из которых ортогонален к вектору рь при у' (1 — 2. Следовательно, ненулевыми остаются только два козффициента 394 (гл, ч» метод минимальных итяг»щий где р»(О=»»+ ... некоторый полипом степени д Полиномы р»(() могут вычисляться параллельно с вычислением векторов р» по формулам р».
1 О) (( а») р» (~) н»р»-1(т) в которых коэффициенты а, и р» имеют прежние значения. Заметим, что вектор р„= Ар„,— а -»Ря-» — рн-»Ря-г Р -н Ря-») н яг " »' Р" '), будет ортогонален к и (А , ) (Р (Ря-о Ря-») " ' (Рп-э Ри-я)' векторам р, р,, ..., р„, и, следовательно, вектор р„равен нулю, Соответственно, полинол» р„(() = (г — а„»)р„» (г) — ря-»р -я (т) совпадает с характеристическим полиномом.
Тем самым получен удобный и простой алгорифм для вычисления коэффициентов характеристического полинома. Трехчленность рекуррентных соотношений, связывающих векторы р» и полиномы Р»(1), была уже нами установлена двумя способами, только что и выше в 9 50. Осветим это обстоятельство еще с одной точки зрения. Из равенства (5) и разложения р,= а»У»+а (»а+ ... +а У„ следует, что р, =а,р»(Л,) У»+а,р»(1 ) У,+ ... +а„р»().„) У„. Отсюда, принимая во внимание условие ) У»! = 1, получим (ррр») = а',р (Л,)р»(Л )+ ...
+ а~ар (Л„)р»(Л ) = О. Последнее равенство эквивалентно равенству / р,(ОР»(т) (Р(»)=О. Здесь весовая функция интеграла Стилтьеса определена следующим образом Р (() = 0 ш<»<Л, р(()= ая Л <~<Л, р (Г) = ая+ ая Л, <~ <Ла (7) Р(7) = а +-аа+ ... + а' Л < 7 < М, где и и М,— границы спектра матрицы А (рис. 4). Из последней формулы для р» следует, что (»» ) О. Для положительно-определенной матрицы положительными будут и коэффициенты ан Очевидно, что векторы р» представляются в виде р»=Р,(А) Х= р»(А)рз (1= 1, ..., л — 1), 395 й бЗ) метод минимАльных итеглцнй Условие (7) определяет ортогональную по интегральному весу Р (с) систему полиномов рг(1). Но из теории ортогональных полиномов известно '), что зти полиномы связаны трехчленными рекуррентными соотношениями.
Отметим ряд свойств векторов рр, ..., о„ , и полиномов рр(1), Рг(О , Р - ((), Р И) г а, л„. л„ ы м л, л, Рис. 4. Теорема 63.3. Корни лолиномов р„(г), ..., ррЯ вещественны и разделяются, Действительно, в силу соотношений (6) и положительности коэффициентов ~г последовательность полиномов р„(1), р„,(г), ..., рр(г) есть последовательность Штурма с положительными старшимн козффнциентами. Теорема 63.3.
Векторы рр, ..., р;, образуют ортогональный базис надпространства Ро натянутого на векторы Х, АХ, ..., А' 'Х. Доказательство. Векторы рр, ..., о;, принадлежат подпространству Рп линейно-независимы и ортогональны. Следующая теорема описывает свойства векторов ро дающее право называть их минимальными итерациями. Именно это свойства было положено в основу построения системы векторов р,, ..., р„, Ланцошем (2), автором первой публикации, посвященной методу минимальных итераций.
Теорема 63.4, Среди всех векторов вида л = АгХ+ У, где УДАРЬ вектор пг имеет наименьшую длину. Действительно, Р,=-А'Х+ Ур, где Ур некоторый определенный вектор из Ро и, следовательно, 2=р;-+ У вЂ” Ур. Но )Л(г=(Л Е) =(Рг+1 Ур Рг+ У У ) =~Р')г+!У )о~в г) И. П. Натансон. Конструктивная теория функций, 1949, ч. 11, гл. !Ч.
мвтод минимальных итвегций [гл ю 396 нбо (рн )' — Го) О. Таким образом, [2[г> [р;[г и знак равенства возможен, только если 1' — )'о О, т. е. Л=р,. Теорема 63.6. Оператор с матриией А имеет в базисе ро, р,, ..., р„, трехдиагональную матрицу Якоби ао 1 1 а (9) о 1 а о-! Действительно, Аро =агро+.Рг Арг = Ргро+агрг+Рг Аро-г = йо-гр~-г+ ао-гро-г+ Ра-г Ар„, = ~„,р„г+ а„,р„ т. е. координаты векторов Аро, Ар,,..., Ар„, в базисе ро, ро..., р„, совпадзют со столбцами матрицы Х Положительность чисел р; уже отмечалась. Тем самым теорема доказана.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
