Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 82
Текст из файла (страница 82)
Л,) Л, то р<Ю(Л,))р(л1(Л.) для 1 = 1, 2, ..., в и, следовательно, М(")) М(")) О. Таким образом, Это неравенство выполняется при всех )г н находится в противоречии с предельным соотношением а1 1 1 — -ь О. 1л) 'у Поэтому неравенство у 1 невозможно. Теорема доказана. 3 а м е ч а н и е. Если процесс наискорейшего спуска вести по формулам (Р; Ре ! то вектор Хл», — Х„ будет ортогонзлен к вектору Хл. В этом случае последовательность векторов Хь будет сходиться к (I, (а не только сходиться по направлению). Этот факт, доказанный Карушем [1), легко вытекает из оценок быстроты сходимости процесса. Теорема 76.2. В в-шаговом методе наискорейшего спуска, при достаточно больших )г, имеет место неравенство Л вЂ” рл <(1+ )()ь( — рь).
Здесь 1,1 есть наименьшее отклонение от нуля в точках сово- купности Лг, ..., Л„полиномов Р,(Г) в-й степени, нормирован- ных условие.ч Р, ()ч) = 1. доказательство. Пусть Ф, (Г) — полинам, реализующий наи- меньшее уклонение от нуля на совокупности точек Ла ..., ).„при нормировке Ф,(Л,) = 1, )(опустим, что построено приближение Хь.
Наряду со следующим приближением Хь„рассмотрим вектор Х„»,=Ф,(А)Хл. Через рл, р,, р „, обозначим соответствующие значения функционала р(Х). Ясно, что 1»в»г )' (ьь»г так как Рл», есть максимУм )ь(Х) в подпРостРанстве Рнль»г), а и„ есть одно из значений р(Х) в том же подпространстве. 506 1гл. Рп ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЪ| Сравним теперь Л, — рй , и Л, — )12. Пусть Хй = а1 )У1 + а~з )Уз+ ...
+ аг( Уг разложение вектора Хй по собственным векторам, содержашимся з инвариантном подпространстве, порожденным вектором Хе. Тогда Хй~,=аРУ,+Ф21Л2)аз"~172+ ... +Ф,.(Л )а~"~У„. Далее (АХй, Х(,.) Л1 (2 Л1 (Х Хй) Л а(1")2+ Л а(1)2+ ... + Л„а(й~"' 1,(й)2 ~ (1)2 1 1 (й)2 таз (Л вЂ” Л„) а(й) ' + ... + (Л вЂ” Л„) а(г~) (й) 2 + а((» 2 + + а(й) 2 1 2 Таким же образом (Л вЂ” Л,) Ф-,'(Л ) а~~~ 2+ .. + (»., — Л,) Ф,(л ) а~~~ а(й) 2 „. Ф' (Л ) а(й( 2 1 ( Фа (Л ) а(й) 2 Так как (Фй(Л()( ((Э, при 1'=2, ..., г, то (л,— ла)а(зй(2+ ... - (л,— л„)а(й)' 1 Поэтому Л вЂ” а а(12+ ...
+а() 1 й-~-1,.а (Мз '2 й(й)2' ! Рй а, 1 где , (й) 2 а(й) 2 1 а( )2+ .. +а(,)2 Таким образом. (12+1 '1 — ~й 1 й (й)2 (й)2 где ай — — „. В силу теоремы 76.1, Ь1 -й1 при (з-+со, так ь(й)2 что ай станет меньше з при достаточно больших Д, и потому Л вЂ” «йй, (Я~~(1+2)(Л вЂ” р,й) при 72) Фз. 9 7б) г-шлговый метод нлискогвйшвго спускА 507 Полученные оценки показывают, что быстрота сходимости последовательности р„к Л, не меньше, чем быстрота сходимости геометрической прогрессии со знаменателем ()',(1+а).
Ясно, что !;1, не превосходит уклонения от нуля полинома, наименее уклоняющегося от нуля на промежутке (Л,, Л,) прн прежней нормировке в точке 1 = Л,. Это наименьшее уклонение равно как известно Е,— 7.00 (г+ « - — !)" +( — )"- — !)' при 2Лт — !ч — Л„ Применение двухшагового метода наискорейшего спуска к матрице (4) 9 51 при Х=(0.34, 0.20, 0.90, 0:75)' дает р(м ! 8300504 р!и = 2.3227312 р.м~ = 2.3227487. При этом Х, =(1.000, 0.799, 0.752, 0.887)' Х = (1.0000, 0,793!. 0.7479, 0.8867)'. Таким образом, применение двух шагов оказывается здесь достаточным для получения первого собственного значения с высокой точностью. Соответствуюший же ему собственный вектор определяется со значительно меньшей точностью.
ГЛЛВЛ УН1 ИТЕРАЦИОННЫЕ МЕТОДЫ ДЛЯ РЕШЕНИЯ ПОЛНОЙ ПРОБЛЕМЫ СОБСТВЕННЫХ ЗНАЧЕНИЙ Итерационные методы решения полной проблемы собственных значений появились в самое последнее время. Естественно, что они значительно более трудоемки, чем итерационные методы решения частичной проблемы. Как правило, их практическое осуществление даже для матриц не очень высокого порядка, требует применения быстродействующих вычислительных машин. Однако несомненным их преимуществом перед точными методами (гл. 1Ч) является возможность вычисления всех собственных значений, минуя вычисления характеристического полинома. Как уже отмечалось выше, ошибки округления в коэффициентах характеристического полинома могут сильно влиять на точность вычисления его корней.
5 77. Алгорифм деления и вычитания ллгорифм (Рутисхаузер 121), к описанию которого мы переходим, является надстройкой над биортогональным алгорифмом. Этот алгорифм позволяет определять собственные значения матрицы А как пределы последовательностей чисел. которые строятся рекуррентно по несложным формулам. Начальными данными алгорифма служат коэффициенты ра и еа двучленной формы биортогонального алгорифма. Прежде всего мы изложим теорию метода в простейшем случае, предполагая матрицу А, для которой строится алгорифм, положительно-определенной.
Алгорифм основан на свойствах нескольких бесконечных послеДовательностей вектоРов Р1гь), лежащих в Циклическом инваРиантном подпространстве, порожденном начальным вектором Х,. Это дает право при изложении теории метода считать все собственные значения матрицы А попарно различными и все компоненты в разложении начального вектора Хз по собственным векторам, отличными от нуля. При фиксированном и векторы р1га1, 1= 0, 1, ..., и — 1, строятся посредством Аь-ортогоналиаации последовательности векторов Ха, 509 ф 77) Алгоеием деления и ВычитАния АХЧ... „Аи 'Хе. При всех и будет р<"> =Х, р<.">=р<1>(А)Хе, где р<<А>(1)=Г<-+ ... полиномы степени <. Покажем, что векторы р)в> связаны простыми рекуррентными соотношениями Ар<. '> — р — р< '>р (4= П 2, ..., и) р<А>.— р<>1+1> =- 2<в+1>р<44~1> (4 = П 2 л >) (>) (Прн < = п считаем р<„"> = 0).
Действительно, вектор Ар<У ",'> — р<1> ПРиналлежит подпространству Р<4>, натянутому на векторы Хе, АХ„, ..., А' Х„, н А"-ортогонален к векторам Хе, АХ,, ..., А< ЯХе. В силу единственности нормированного вектора, удовлетворяюшего этим условиям, вектор А)><!"',1> — р<,."> лишь численным множителем отличается от вектора р<1>,. Лналогично, вектор р<,"> — р<41 '> принадлежит подпространству Р<4>, А -ортогонален к Х,, АХ,, ..., А Х, и, следовательно, лишь 1-1 4-2 численным множителем отличается от вектора р<А41>. Между пол нномами р<1> (Г), очевидно, тоже выполняются соотно- шения 4,<1 >(г <У>(г),<11+1> (в> (г) р<11>(Г) р<)4- >(Г) е<вч-1>р<14-1>(() (2) Выведем теперь зависимость между числами р<,."> и 2<41>.
С этой целью перейдем к трехчленным соотношениям, связывающнм век- ТОРЫ Р<1>н Р<,">, Р<В>,. ТаКИЕ СООТНОШЕНИЯ МОЖНО ПОСтРОИтЬ ДВУМЯ способами. Во-первых, исключая из соотношений Ар<1'1> — р<1> = р("Ф'>р<"> 1 1 ! 1 Ар<А+1> р<в> р<в4-1>р<1> 4-1 1 4 — 1 4 — 1' Ар<1'> — Ар<А+1> = а<"+1>АР<1+1> 1 1 1 1-1 векторы Ар<,.""> и Ар<,"'„'>, получим р<" > + (о<<В< 1>+ р<4<4 1>) р<1'> — Ар<В>+ р<<В < 1>2<А+1>р<4<> = О.
(3) Во-вторых, исключая из соотношений Ар<А> р<а-1> р<А>р<в-1> 1.>- 1 $4 р<ь-1> р<В> с<А> р<А> 14-1 4+1 44-1 4 р<" — '> — р<<А> = е<Ь>р<А> 1 4 векторы >2<9-1> и р<А-1>, получим 4+1 4 р<Р> + (2<9> + р<41>) р<<Ь> — Ар<1>+ а<<в>р<">р<">1 — — О.' (4) 510 итеРационные метОды для Решения потной пРОБлемы [Гл. ч!и Сравнивая трехчленные соотношения (3) и (4), заключаем, что , )ь+1>+ р(ьь1) й)!) +р<ь) 4 1 си1 Р1 огнь')рф"> = о(ь)р<ь).
(5) 1 1-1 ! 1 Последние соотношения позволяют последовательно строить числа р!Ь+1), о)>Ы '> в порядке р<Ь"!), о)ЬЬ1), р<" '>,..., р!Ь+!), о)Ь ~1), ры-"> ! ' с О ' 1 ' 1 ''''' и-2' и — 1''И вЂ” 1! как только числа р'12), о!2) уже построены. Вычислительными формулами алгорифма (схема деления и вычитания — Ясг) являются, при н)~1, р!Ри!)=о)ь) +рф) — а~.'+'> (1=0, 1, ..., п — 1) Ф !!1 4 Ф )ь) (1) (6) о)ь+1)= . (1=1, 2, ..., п — 1).
)Ь-!-1) с-1 При этом надлежит считать о)Ю = о)ь) =О. Начальная строка алгорифма ры>, с)1), ..., о)1), рн) О ' 1 ' ' И-Н Ри-1 определяется коэффициентами двучленных формул метода минимальных итераций или получается из коэффициентов а! и р! трехчленных формул этого метода в виде р!') = а, оы) = — рн) = а, — о(!).
о (7) Р," , Лля вычисления собственных значений матрицы (на инвариантном надпространство, порожденном вектором Х,) нужно составить только последовательность чисел р(ь), о)ь>. Векторы же р(ь) строить нет необходимости, так что их введение нужно только для пояснения теории метода. Именно, верна следуюшая теорема. Теорема 77.1. Пусть А положительно-определенная матрица, Хо данный вектор, )ч ) Л ) ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
