Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 78
Текст из файла (страница 78)
тв ~ Т» (тв) где Т,(т) =-сова агссозт — полипом Чебышева. Известно в), что Т, (т)— ( +Т" — 1)" +( — ~' - — 1)" Поэтому Б частности, М вЂ” и (М вЂ” т)в М+т ' в (М+т)в+4тМ (М вЂ” т)т (М+ т) ((М+ т)в+ 2тМ! ' (19) Легко видеть, что в 1 > б, > ~7 (, > ~г (., > (20) г) В.Л. Гончаров. Теория интериолироваяяя и приближения функций, ГТТИ, 1934, стр.
281. в) В. Л. Гончаров. Там же, стр. 27, оценку (16), если среди полиномов указанного вида выберем полипом Фв(1) таким, что Яв= гпах<1>в()ч) будет наименьшим. Эта наилучшая оценка, конечно, зависит от Л,, ..., ):,„, Для класса матриц, собственные значения которых заключены в промежутке (т, М) можно дать оценку, зависящую от чисел т и М, наилучшую для этого класса в целом. Для этого в качестве полннома Фв(1) следует взять полипом, наименее отклоняющийся от нуля в промежутке (и, М) и нормированный так, что Ф,(0) = 1.
М вЂ” т М+и Линейной заменой Г.=, т — мы сведем задачу к пог 2 строению полинома, наименее отклоняющегося от нуля в промев<утке — 1~т.(1 н принимающего в точке М+т значение !. РешеМ вЂ” и ние последней задачи ') дается полиномои $73) з-шлговыя гглдивнтныа мвтоды нлискогвйшвго спхскл 479 3 — соэ 211 — М1 — т Т.в ( Т.ю если а — ' ' ) М1 — т 1+ соэ Далее, с„монотонно возрастая, стремится при построенному для промежутка (т, М,).
Можно подсчитать, что для двухшагового метода спуска а-+со к Т,, наискорейшего М,— т Л1+ т Т"2 если М, ( М1+ и+в и ' Л1 — М1 Для произвольного з соответствующие оценки получаются при помощи полиномов, изучавшнхся Е. И. Золотаревым '), и оказываются громоздкими. Б. А. Самокишем (!) предложена приближенная формула 1 М1+и 1 Г е — а 1 — ап1 йв(т, а) == —,Г1п' + о-в 2~ 1+аи а — а 11 т+ Ггттэ 1 а а+ !л аа 1 1) Е.
И. Золотарев. Приложение эллиптических функций к вопросу о функциях, наименее н наиболее отклоняющихся от нуля. (Полн. собр. сочв вып. 2). Последние неравенства означают, что при достаточно большом АГ' Г Ав1 результат применения ~ — 11 шагов з-шагового процесса дает лучшее М", приближение, чем ! 1 шагов г — 1-шагового процесса. ~х — 11 Заметим, что в приведенных рассуждениях мы не использовали результатов Л. В. Канторовича об оценке функции ошибок в одно- шаговом методе наискорейшего спуска, и потому равенство М вЂ” т Е =— М+и дает другой вывод оценки (10) 2 70.
Можно дать и другие, более точные оценки для быстроты схо- димости г-шагового метода наискорейшего спуска, если иметь более точную информацию о расположении собственных значений матрицы А. Так, в работе Б. А. Самокиша (1! рассматривается ситуация, когда известно наибольшее собственное значение Л, н известен проме- жуток (т, М,), в котором расположены все остальные собственные значения. В этом случае в качестве фв(Г) можно взять полинам наименее уклоняю1цийся от нуля на множестве, состоящем из точки Л, и про- межутка (и, М,).
Обозначим отклонение от нуля выбранного поли- нома чеРез 1'.в. Тогда 480 [гл. чн гвлдивнтныв итввлционные методы 5 74. Определение алгебраически наибольшего собственного значения симметричной матрицы и принадлежащего ему собственного вектора градиентными методами Экстремальная теория собственных значений позволяет применить релаксацнонные градиентные методы и к определению крайних собственных значений (т. е. алгебраически наибольшего ь, и алгебраически наименьшего лл) снммегриччоя матрицы А, так же как и принадлежащих им собственных векторов. Действительно, ) (АХ, Х) (Х, Х) (АХ, Х) д — И1п ( причем собственными векторами, принадлежащими этим собственным значениям, будут векторы, реализующие экстремум.
Таким образом задача отыскания )., или )„связывается с задачей максимизации или минимизации функционала р. (Х) = — - — '— (АХ, Х) (Х, Х) Ввиду полной аналогии теории мы рассмотрим вопрос об отыскании алгебраически наибольшего собственного значения н принадлежащего ему собственного вектора. Как было выяснено в З 14, градиентом функционала р (Х) будет 2 2 вектор — — (АХ вЂ” й(Х) Х) =- "=, где (Х,Х) (Х,Х)- с = АХ вЂ” и (Х) Х. Направление градиента совпадает с направлением вектора $, так как (Х, Х) > О.
Если Х не является каким-либо собственным векторолг матрицы А, то (еьО. Во всем дальнейшем, говоря о градиенте функционалз р(Х), чы будем подразумевать под этим вектор Е Пусть Х,— произвольный вектор, не являющийся собственным вектором матрицы А. Пусть (2) Х, =Хв+Т(. Из свойств градиента следует, что при достаточно малом по модулю Т справедливы неравенства (ь(Л;) > 1ь(Хв) при Т > 0 и Р(Х~) ( ( н(Хв) при Т ( О. Выясним подробнее, как ведет себя равность р(Х,) — р(Хв) при изменении Т по всей вещественной оси. 3 74) опгадвлзнив нливольшего совственного знлчвния 481 Имеем (АХ,, Х,)=(е1Ха, Ха)+ 21(АХа $а)+Тв(А=а За)= =(АХа Ха)+27((а (а)+Т'(Аеа -а).
ибо (.4 Ха, (а) = ((а -'-а). Далее (Хг Хг) =(Ха Ха)+'Т (-"а а) ибо (Ха Еа) = О. Таким образом, Ха) + 27 (Еа, Еа) + те (Аба, Еа) Р (Хг) = р (Ха+ Т )а) = (А Ха (Ха, Ха)+ тв(-'"а Еа) , (Ха) + 2тсав + 1 "Се,' ((е) 1+ )аГа где (еа еа) (Ха, Ха) ' Поэтому И (Ха) + 2тса -1- "Ге И ба) — И (Ха) — 1'Га И (Ха) р(Х,) — р(Х,) =- ' '+ тв'а (3) 21га т гае (и (ха) и (еа)) 21 — тваа в — (4) 1+1 Го 1+ т"ае где 31 звв, аы. д. К. Фввдеев в В, Н. Фаддееве га = — Р (Ха) р (еа). (5) Из равенства (4) ясно, что р.(Х,) =)е(Ха) при Т =0 и при Т = —.
ве КРоме того, Ясно, что Р(Х,) — Р(Ха) есть непРеРывнан фУнкпиа от Т при всех вешественных Т, включая Т = со, так как 1(а [и(Х,)— т.в-. — р (Ха)) = 1пп (р (Х~) — р (Ха)) = — я, . Отметим, что р (Хг)— ва р(Ха) = — — за еше в одной точке, именно при Т.—.= — —,. Таким 2сае образом, график р(Х,) — р(Х„), в зависимости от знака аа, имеет вид„ изображенный на рис. 9, 10, 11. Из графиков видно, что неравенство р (Х,) — р (Ха) ) 0 выполняется в области 0 « , †, если з ) О. в области Т ) О„ 2 2 если аа = О, и в области Т > 0 или Т < — , если за < О. аа 482 [гл. Тп ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ Покажем, что для данной матрицы А можно указать такой промежуток изменения (, в котором Р(Х,) — Р(Хе) ) О независимо от выбора Х,, т. е.
независимо от величины ге. Именно таким промежут- 2 ном является О ( у С вЂ” . действительно, при зе ( О, и(Х,)— — Р (Ха) ) О при любом положительном (, если же з„) О, то Р(Х,) — Р(Ха) ) О, при О (", <, ибо — = . ь 2 2 2 лл — ж гм и(-'оа) Р (1е) 2 >л|— Ряс. 9. Рис.
10. Рис. 11. Найдем теперь значения параметра у, при которых Р(Х,) — и(Хе) будет принимать экстремальные значения. Из приведенных графиков ясно, что максимум лежит направо, минимум — налево. Производная от Р(Х) — Р(Хе) по ( (с точностью до положительного множителя) будет (2 — 2узо) (1+ уча) — 2)(е'(2'( — )'еа) = — 2'('Го 21'е+ 2 и по~ому критические значения и и а параметра ( определяются из квадратного уравнения (Г';+таз — 1=О. 9 74! опгедвление нливольшвго совстввнного знлчвния 488 Положительный корень этого уравнения — го + Г' го + 4!о 2 реализует максимум, отрицательный корень — ао У гоо+ 4го 2 ао г (о 1 ао + 4!о 'о (7) реализует минимум.
При этом г 2оо оо го 1+ гогог 1+ 1 — 'оао Р (Хо+ ао-о) 1' (Хо) = "ого. (8) (9) Отметим два свойства корня а,. 1 "о= Н (Хг) — !г ($о) М вЂ” пг ' )~ —. (10) Действительно, Р (Хг) и ((о) = 1' (Хо+ ао о) 1" ("го) + Р (Хо) Р 6о) = ао(о+ ло = — „ г 1 на основании уравнения для а,. 2. аоао = Р (Хо+ ао1о) — и (Хо) «( М вЂ” т. (11) Коэффициент ао будем называть оптимальным коэффициентом.
рассмотрим теперь следующую группу итерационных процессов, которые естественно назвать градиентными. Пусть Хо некоторый начальный вектор, отличный от нулевого. Построим последовательность векторов Х»='Х»-г+ 7»-А-г (я= ! 2 ) г — =АХ вЂ” г р -гХ вЂ” ° (! 2) где (1 3) р», —— р.(Х»,), а 7„, некоторое положительное число, выбираемое так, чтобы во всяком случае р„было бы меньше, чем о»,. Отметим, что если Х», ~= О, то и Х» ~ О. Действительно, (Х» Х») = (Х вЂ” + 1» - о — Х» - + 7» - 1» - ) = =(Х„„, Х )+уз»,(1~- (»- ) ) О. ') Хеетинс и К аруш [1], 31* Таким образом, описанный процесс продолжим неограниченно.
Две следующие теоремы') дают достаточные условия сходимостн градиентных методов, ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ [гл. Тп Теорема 74.Т. Если на всех шагах градиентного процесса <А(ХА+г) — 1*(ХА)~~8 Х Х (о) О) (сь. сь) (Хл А) то последовательность й(Х„) сходится к наибольшему собствен- ному значению матрицы А в анвариантном подпространстее, порожденном вектором Хо, а последовательность гекторов 'Хь сходится по направлению к соответствующему собственному вектору.
Локозательстео. Пусть </о ..., и, — нормированные собствен- ные векторы, образующие базис циклического подпространства Рг, порожденного век~ором Х,, )ч ) )и) ... ) <.„— соответствующие им собственные значения. Пусть Х,=а( и,+ ... +а(<и, Тогда (теорема 11.8) а, ~- О, ..., а„чь О, Без нарушения общности (ю <т можно считать, что а, ) О. (ю Ясно, что все векторы Х,, ..., Х,, содержатся в подпространстве Ре и потоку ха=а,ни,,— ...
+а„и„ Гч ~ Ро Покажем, что а(о)О. Имеем ((О , — (Х„, и,) =(Хв о и,)+ Т„,Е„Ы и,) —. (ю =(ХЬ, (У,)+<Ь,(с<Ха г--ра,х,, и,) =- =(Х„,, и,)+<н,)ч(ХА, и) — Тл (Р,,(Хн, и,)= = [1+.<ь- Оч — гь- )[(хь — и ) = = [1+ (ь-((А< — рь-г)[ а(ь —.— [1+ )ь, (А~ — рь-1)[ . [1+ то()ч — ро)[ а< 1) О ибо все множители последнего прот(введения положительны. Отметим прежде всего, что процесс может стабилизироваться, если на каком-либо шагу окажется, что сь=О. В этом случае вектор Хь будет собственным векторои матрицы А и так как (Х„, и,) =- (й) =а, ) О, то этот собственный вектор буде~ пропорционален и,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
