Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 79
Текст из файла (страница 79)
Таким образом, в случае стабилизации процесса теорема доказана. Обратимся к рассмотрению общего случая, когда (ь ~= О. Введем обозначение (ь< а< 1 ха [' Тогда х„=[х„[(ь<"'и,+ ... +д„")и,), причем д~~)) О. 5 74! опввделение наиволь него сове(венного значения 485 Далее а«=а, (),1 — ра)()1-(-... — а«(˄— „)с(,. (а) (а) С (едовательно, Ла, (л) '=1 ' " ' %2 (а)2 Тзк как р, < 2 « ... .«(... < Л4 =), то 1пп ра существует. а .ь,' Обозначим его через (1. По условию теоремы 1 Г, ( —.— (1« — ра) — + О (й -+ сс).
б(«) 2 (Л вЂ” а)2 О /, что р = Л . Тогда ((п) 1)11') а.ь найдется такое а (!п( Ь) = 1. (1')2 1'-ь ю Покажем, что /=!. Если допустить, что у'> 1, то С другой стороны, имеем 1+1„,(),.--р„,) ~ ~ а(' 1+1,(л.— (.а 1) ) ) „(а-и '= 1„,(л, )) ~ „(-)( (а(а ) та-1(11 11) ибо —, Л ) О, так как та,> О по построению яр„, 1+ 1«(Лу Ра 1) (Р,=Л) (ьм ПолУченное пРотивоРечие показывает, что 7'=1. Итак, мы доказали, что ра-+Л, при й-+ос.
Тем самым установлено, что Ь~ -+1 и так как а1 )О, то б(| -+1. При этом (а) 2 (а) (а) ()()-+О при 1=2, ..., г. Но Поэтому ~' ()( ) ()ч — 1«)2-+О при й — + оо, т, е. ;=1 при всех(=1, 2, ..., г. Если )ч — р+О, то б(а) — «О г однако не может быть при всех ( = 1, 2, ..., г, ибо при й — + со. Этого =О при (ть (2 486 [гл.
чп гааднвнтныв нтвглцнонныа методы Следовательно, т. е. последовательность Х„сходится к (7, по направлению. Теорема 74,2. Если сверх условия теоремы 74Д есе числа 7» ограничены сверху а совокупности, то )опХ» — — П/о где А неко» ьсо торое положительное число. Доказательство. В силу теоремы 74.1 нам надо доказать, что (Х»! — ь Е при й-»со. Но (Х», Х») =(Х Х -1)+ (»,Ь» »Л — ) =(1+'( Л 1)(Х»- Х»-1). Следовательно, (Х», Х»)=(1+Ф,')(1+Т',(';) . (1+уг А,)(Х Х). Бесконечное произведение сходится, ибо га (» сходится (так как он мажорируется сходяшимся »-о рядом Да ь (р»о.г — р»)), а Т» ограничены сверху по условию теоремы.
»=о рассмотрим теперь несколько частных градиентных методов. 1. Т»=7= сопа1 — метод постоянного множителя. В атом случае для возрастания р» на каждом шаге процесса при любом начальном векторе необходимо, как мы видели, выполнение неравенства О( ( Покажем, что при выполнении зтого неравенства выполняются и условия теорем 74.1 и 74.2. Действительно, пусть 0 < ~ ~ 2. Тогда Я(Х») — р(х»-1) 21 — тое» г 1+т'Г» 1 т 2— ~ > ( ~)=Ь)0 ггг - 1+-(жв т»-г й 741 опгвдвлвнив наизольшзго совстввнного значения 487 ибо Га т ( 1, где ! сферическая норма матрицы А.
Действительно, Гз (6а Фь) (Ахь !ь) (АХа АХа) (Хы Х,) (Х„Х„) (Хы Х„) (АХы Хв)т (АХы Аха) ПАХь0Я (~~ ~~~а (ХМ Х„)Я < (Х,, Х,) = ~Х„Р Остальные условия теоремы, очевидно, выполняются. 2. Та —— аы где иа — оптимальный коэффициент й-го шага— метод наискорейшего спуска. В этом случае ", " ' =ам а-г и потому для проверки условий выполнения теоремы 74.1 надо убелиться в ограниченности снизу чисел аы Но мы установили ранее, 1 что яа )~ , так что ограниченность снизу действительно имеет место. Чтобы убелиться, что условие теоремы 74.2 тоже выполнено, нужно докззать ограниченность чисел аа сверху.
Здесь, в отличие от предыдущих оценок, оказывается, что верхняя граница существует, но зависит от начального приближения. Нменно, нетрудно видеть, что все значения аа при достаточно больших )а удовлетворяют условию и яа < л — л Действительно, 1 еа 1» (Хь) И (1ь ) При достаточно большом к, и(Хь) становится сколь угодно близко к Л,, т. е. И(Х„) ) Л,— е, при е ) ().
С другой стороны, (а, ортогонален Х„, и, следовательно, 1а, после нормировки (к единичной длине) подходит сколь угодно близко к подпространству, ортогональному к (7,. В этом подпространстве и(Х) не превосходит ), Поэтому )»((ь,) <( (Ла+ е, при достаточно большом л. Следовательно, при достаточно большом (а 1 1 2 ;< — — < > Л» — » — Л» — » Лт — ).я — 2» Лт — Л» Л вЂ” Л если взять е < 4 . Таким образом, теорема 74.2 оказывается справедливой и для метода наискорейшего спуска.
3 Тв=йаа где иь — оптимальный коэффициент й-го шага, й(р (1 — метод неполного наискорейшего спуска. Для справедливости теоремы 74 А надо доказать. что последовательность (гл. Тн 488 ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ ограничена снизу. Имеем К Р (Хйьт) — Р (Хй) 2~АР ~КР ай гй 1+ айа ГА. 2айР— айР (! — !~а~А) 2 — (!+ Рг~~аС, !+а"Рата 1+а ~а~ 1 — З + В (1 — Р) ай!К + 1+ 'Р'!' 1+ Рай!К 1с =айр 1+(! — 'р) з ..~)~аф. 1+'АР гйа Следовательно, Р (Х„,) — Р (Хй) Л вЂ” сп й Хй. 1= — АХК. 1 Р'сс Имеем Р (Хй„) — Р СХК) Если А положительно-определенная матрица, то Р.
(Хй„) — Р (Х„) —,, >О. й где ! — сферическая норма матрицы А. Очевидно танже, что 1 1 Тй= — ( —. Таким образом, в случае положительно-определенной Рсс матрицы степенной метод является не только сходящимся, но н релаксационным, ибо на каждом шаге происходит увеличение (А(Хк).
В случае произвольной симметричной матрицы этого может не быть иа первых шагах процесса. Однако, если Ас ) — )„, т. е. алгебранчески наибольшим является собственное значение, наибольшее по Справедливость теоремы наискорейшего спуска. 1 1 Р (Хсс) Рсс 74.2 доказывается так же, как и в методе — степенной метод. В этом случае 2 тс, !'й 1 2ий —.11с Р (Хй) + ! (!К) 1,'с Р.- + гйа и (Хй) + !Кз Рй 489 ф 741 р Ж ОСЬ СЧ О 03 3-, 03 ооо ООО о 0 с-СЧ О О О с '00- О О О О о 'О О 'С СЧ 0 с'» х3 СИ \О ообо 3' СЧ С3 4'3 СЧ СОСО О Оооо 3' 3 С'4 СЧ О 0 ОСЧ О О3 !В '3 СО СЧ С 03 СО О С- СЧ О 3 ОО3 СЧ 0 03 00 О СС ОООО 00 3' СЧ С 3 40 С4 03 О Со О со '.о со с оооо 3 4 СО .О со Оооо И О 30 О И 03 ОС3 СО о о» д сСо- Π— Со О О со оооо СО О 00 'О Я 00 О:О, О О 03 О О 3 О О й О 03 4- СО ь 04 С4 О СО Г СБ 3 "00 Осо ЧСС3 о О00 40 О ОЗС4 30 О Со со 00 СЕ .О ОООО 40 03 4' СО ОССИ С о с с СО СО со оооо сО О3 СО 3 со Сс С'4 со с 00 00 С'0 О О со 3 О СО с" 9! 00 О4 оооо 04 ООВ Я СЧ О3 !О С- сО 00 \' сс 3' ОООО О 4 О 3 4О О О 30!04 ОЬ о' о' о о сО 3' С'4 Ж СО О3 3 О О ' 3 О СО С0 ~00 СО 'Ф Оо СО 43 С4 с 3 С'4 В 3 ОООО ~ Я О, оооо О3 ~ ~о ~ !! 43 3 О И О О 3" 2 И И о О О О О 3 О Ио! 0~ О,с О 40 О О О 3 о О ОИРЕДЕЛЕНИЕ НАИБОЛЬШЕГО СОБ О » О Й О О Х О О й О Й ,0 О со 30 о 2 С0 СТБЕННОГО ЗНАЧЕНИЯ 490 (гл.
чп гглдивнтные итзгационные методы модулю, то из факта сходимости по направлению векторов ХВ и У! следует, что й(Х7,)-+),! а р(93)ьл7 и, следовательно, и(Ху,+1) — и (Хе) (1! — 3) + т )~ 732 Л +7 Во=О 99231126, 1о.=О 71392752, так что = — 0.67750609. ) 3.3403917+ О. 99231126 Приведем также значения а = 0.60271425, а1 = 0.51669127, ав = 0,59837767, а4 = 0.51670397. ТабяиЦа 4771'. 17 Определение наименьшего собственного значения методом наискорейшего спуска АХ„ х, Х, -2 ШВ37В2 — О. 2691 368 1.0828515 1.5917026 -2.0012022 — 0.1776640 1.ОИ8913 1. 599 1528 1.0000 О ВЫΠ— ОЛЗЗΠ— 0.7928 1АОВО 0.78278286 Овб!В 0 59478902 !.В1Ш -ОЛЗИ4536 1.2604 - 0.11213780 — 1.
2783558 — 1.0296919 1. 59! 4454 О.ГМВвз! 0.77798313 0.767!9557 0.25391984 0.59252ЬП ОЛА 0.20 оло огш 4.9388 — 0.18.10 2.39172706 0.91393373 2.7965 1.090952 64 1.5281 ьвзавн ~ 0.24226089 0.88773917 0.24227723 начиная с некоторого места. Таким образом, и в этом случае степенной метод сохраняет релаксационный характер, начиная с некоторого шага процесса. В табл. Ъг!!.9 определяется наибольшее собственное значение матрицы (4) 9 51 градиентным методом с постоянным 7, в табл. Ч1!.10 методом наискорейшего спуска. В табл.
57!!. 11 для той же матрицы определяется наименьшее собственное значение. В последней строке таблиц записываются значения й(Х). На каждом шаге процесса в табл. !7!!. 1О оптимальный коэффициент находится по формуле (6). Для первого шага имеем 9 74! опввдзлвнив нлизольшего созстввнного значения 491 На каждом шаге процесса в табл. Ч!!. 11 оптимальный коэффициент ий находится по формуле 17). Для первого шага имеем ео = 0 99231126 1о = 0 71392752 — — 2.0674390. $г 3.84039> 7 — 0.99281126 Сравнение табл. Ч!!. 9 и Ч!!. 10 показывает, что в данном примере метод постоянного множителя с 7 =-0.6 сходится лишь немного медленнее, чем метод наискорейшего сп>"ска.
Объем же вычислений для одного шага метода постоянного множителя вдвое меньше, чем в методе наискорейшего спуска. Вопрос о выборе значения постоянного множителя пока не исследован. Для положительно-определенной матрицы во всяком случае 2 в качестве 7 может быть взято число не превосходящее —. >! А >>, ' Вычисления, проведенные для матрицы !4) 2 51 при 7 =- 0.5, т= 0.4, 7=0.3 и 7 =0.25, показывают, что с уменьшением 7 сходимость процесса замедляется. Применение неполного наискорейшего спуска при р = 0.8 и р = 0.9 в рассматриваемом примере оказалось не целесообразным, так как сходимость процесса не улучшилась.
Возвратимся теперь снова к методу постоянного множителя, причем будем считать на этот раз, что 1 0(7 ( —. Отметим следующее важное свойство последовательных приближений. Лемма. Если в методе постоянного множителя М вЂ” т (й) и 0 ( р ( 1, то ! пп — '„- = 0 при ! ( /. Здесь агй>, а!»>, ..., а!й> коэффициенты в разложении приближения Х» по собственным векторам У,, ..., У„, содержащимся в инвариантном подпространстве Рз, порожденном начальным приближением. Доказательство.
Пусть Ха=а»)У,+аа! >У + ... +а! У,. Тогда Ха=а, У,+а, У,+ ... +а„У„, !») !») !й) причем а =!1+ т 0 — рй-т)1 а* (й) 1й-г> 492 [гл чп гглдиентпые итевлционные методы Отсюда следует, что ае ) О, ибо 1+[(Л( — ра,) = 1+р — — -' — -' ) О. (а) Л( — (чьОбозначим 6,=1+Т(Л,— Л)=1+~ ' Очевидно, в силу выбора р О(о„о„( ... (о (2,=1, (а) „(, -2 оп Позтому (а-1) (а) (а->) ,(,( а(а) а(а ~) а а( 2 Так как (а-+Л,, то а(а) Ь "'„„<Е( —,'+ ) (Д) [2,). ау а( ) Выбирая 2 так, что — +2(1, получим, что — ' -+О при )()'. а(а) В атом „суженном" методе постоянного множителя интересным является и поведение последовательности Ва.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
