И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 23
Текст из файла (страница 23)
Х11. Вычислить матрицу Зс размера т х с Зс = С1" — с+сс('. ХП1. Составить матрицу Сф размера и х (с + 1), состоящую из матрицы 5с и вектор-столбца ~+с Сц =(Зс!гсю) Х1Ч. Положить с = с + 1 и перейти к шагу Ч. При е = О матрица С„, порождаемая алгоритмом 1', всегда сов- падает с псевдообратной к С„, т. е. Сс' = С+, а алгоритм 1' есть ме- тод Гревилля псевдообращения прямоугольных матриц.
При подходящем (малом) е ) О алгоритм Пс~~' устойчив к малым возмущениям вычислений, а также к возмущениям элементов псев- дообращаемой матрицы С„(метод Гревилля очень чувствителен к ошибкам вычислений). Эта устойчивость имеет место для широко- го класса матриц даже неполного ранга. Определение 1.
Последовательность (х")е м порожденная ал- горитмом 1, сходится сверхлинейно к стационарной точке х' функ- ции 1,(х), если при некотором й, ( оо достигается Рх' = Рх* или при всех й ~» Π— Рх" ~ Рх" и 1пп ~ Р (х"+' — х') ) I ( Р (х'— е-~ аю — х*) 1 = О, где Р— ортопроектор на образ )с (7'„1е (х')) гессиана 7'„1, (х') в точке х'. 4с)й Теорема 1.
Пусть выполняются предположения 0 и следую. щие условия: (до) — последовательность [х»)»-ю, порожденная алгоритмом 1, сходится к стационарной пдочяе хю функции ~ю (х); (о) — при каждом й;::. т матрица А», имеет образ Н (А», ), который содержит образ Н (Ч»,1» (х")) матрицы вторых производ- ных, найденной в точке х"; (од) — при каждом й „в 0 справедливо Р Ф Рх*, где Р— ортонроектор на образ Н (Ч ~ю (х*)) гесснана Ч' 1ю (х') в точке х', (одд) — при каждом й ~ 0 справедливо Н (В»):з Я (Р). Тогда достаточными условиями сверхлинейной скорости входи- мости являются Ит [Р (В»~ — Ч'„1» (х*)) (х'+' — х») 1! [Р(х"-и — х») [ = 0 (з.!0) и выполнение условий в некоторой окрестности пидчки х* [Ч'„,Д,(х»+ т(х+' — х )) Р- РЧ»Д(х» + т(х»+' — х»)) [ < (рд[Р(х»+1 х»)1, О<рд< 00 Ухе[0 Ц.
(2,$01 Если для каждого х»+' имеет место неравенство (2.16) и [ Ч',['ю (х' + т (х»+' — хю)) Р— РЧ'„4» (хю + т (х»+' — х*)) [( <Я[Р(х»+д — х*)$, 0<[)»<оь, Утаи[0, Ц, то (2.15) является и необходимым условием. Теорема Т. Пусть выполняются предположения О, условия (до), (од) теоремы 1, а в некоторой окрктности точки хю выполня- ется неравенство (2.16), Я (А», ) =э Я (Ч' [ю (х»)) и пусть матрица В, на шаге 1Х алгоритма 1 вычивляется по формуле В» (Н», А+», )д'-[- / — Н» А»~ (Н» А»+ )~, где псевдообршцение дд~ означает, ипо оно вздетая алгорипдмом 1' устойчивого псевдообращения Пю о а», удовлетворяющим усюдо> виям идах ( [х» — х! [, [х! — х!-д [) < р»ед»+е; д-ь-е+д„...» !нн е„О, ».ьао (здесь [)„р — некоторые положительиьде постоянные), тогда (х')»" ю сходится сверхлинейно.
109 2. Уотойчввое пеевлообрап«еппе плохо обуоловлепвых матрац Определение 2. Для прямоугольной матрицы С псевдособственнымн числами называют числа Л, такие, что Л~ являются собствен- 2 ными числами матрицы С С. Отношение о = Л „Ф иь где Л,„, т Л и — максимальное и минимальное из ненулевых псевдособственных чисел матрицы С, называют мерой обусловленности матрицы С. Если ч — велико, то говорят, что матрица С плохо обусловлена. Алгоритм 1' неприменим к псевдообращению плохо обусловленных матриц. Ниже приводится модификация алгоритма П~', основанная на последовательном уточнении псевдообращаемой матрицьг, которая позволяет псевдообращать и плохо обусловленные, даже вырожденные матрицы.
Алгоритм 2 служит для псевдообращения матрицы С„размера и м т, состоящей из строк а', 1 = 1, ... ..., а. На выходе алгоритма 2 получается матрица СК которая принимается за псевдообратную к С„. Алгоритм 2 (алгоритм Пм1 (е, б, 1«, р) устойчивого псевдо- обращения плохо обусловленных матриц) Н а ч а л о.
1. Выбрать произвольные константы (параметры алгоритма) з > О, б > О, р > О, р > О (рекомендуется выбрать р (( (( р, 6 — «малоев число). 11. Вычислить )~ а')т. (Норма~ Ь~, вектора Ь = (Ь„..., Ь„) вычисляется по формуле ~~Ь|,= Х,~Ь,~) П1. Если ~ а' Ц ) е, то вычислить матрицу С~~ размера и 1с 1 Сг =(а') (а'(а') ) 1 и перейти к шагу 1Ч; если ~ а' 1««( а, то положить Сг = О, где О— ноль-матрица размера и ~ 1, и перейти к шагу 1Ч.
1Ч. Вычислить матрицу О«размера и х т Ох=)' — С С,. 'в Ч. Вычислить матрицу Я, размера и м и О, = СФ (С~)'. Ч1. Положить 1 1. Основной цикл. ЧП. Если1(п, то перейти к шагу Ч1П; иначе прекратить вычисления. Ч111. Вычислить |)а'+'О, 1„если ) а'+'О, 11«) е, то перейти к шагу ХЧ1 иначе перейти к шагу 1Х. 1Х. Вычислить вектор-столбец г~+' размерности и ~+~ () ( ~+~ т 1 г~-~ ) и.~)т -~ Х.
Вычислить матрицу 5, размера и х 1 5, = С~~" — т'+~а + С~~. 11О Х1. Составить матрицу С!,"! размера т х (1 + 1), состоящую из матрицы Я! и вектор-столбца г!+! Сф! = (3!1г'+'). ХП. Положить б!» ! = 6!. ХП1. Вычислить матрицу 6!».! размера а! х т по фоРмУле д!+! = (/ — г'+'а'+') Я,.
Х1Ч. Положить ! = ! + 1 и перейти к шагу ЧП. ХЧ. Вычислить вектор-столбец г!+! размера и! г'+'*= 6,(а'+') (а'+'6,(а'+') ) '. ХЧ1. Вычислить матрицу 5! размера т х ! 5! = (/ — г!+!а!+!) СР. ХЧ11. Составить матрицу С~~+! размера л! Х (/ + 1), состоящую из матрицы 8! н вектор-столбца г'+' С!~+! (З! ! г!+ ). ХЧП1. Вычислить матрицу О! ! размера л! х и 6!» ! (/ — г'+'а'+') 6,.
Х1Х. Вычислить матрицу 1;!!» ! размера т х т по формуле (/! ! (/ г!+!а!+!) Я (/ !С+!аС+!) + р!+! (!Г+!) ХХ. Вычислить величину 6' ~ (г б!»-! — ганя 6!» ! (, где (г О!е! — след матрицы б!».!1 ганя б!».! — ранг матрицы О!+!. ХХ1. Если 6' ( 6, то положить ! = ! + 1 и перейти к шагу Ч11; иначе перейти к шагу ХХ11. (Шаги ХХП вЂ” ХХХЧ11 алгоритма уточняют полученные выше матрицы Сф!, О!».!, Я~.~! на основании матрицы С,=!). ХХП.
Положить 4о Я!+! ХХП1. Положить / = 1. ХХ1Ч. Вычислить матрицу (С!!)"! размера и! х 1 (С!!)з = (/е! (а!)г (Р зр' -~- аде! (а')г) !. ХХЧ. Положить / О. ХХЧ1. Вычислить вектор-столбец я!+! размера т !Я+! г! (а!+!)г ( — з1!Я + а!».|6!! (а!+!)г) — ! ХХЧП. Вычислить матрицу Щ размера и! х и! 6ю+! (/ — г а!+!) 6! ХХЧП1. Если / О, то перейти к шагу ХХХ1; иначе перейти к шагу ХХ1Х. 111 ХХ1Х. Вычислить матрицу 3/! размера и! х 1 5! = (1 — г+ а + ) (С~!)~".
ХХХ. Составить матрицу (С!~+!)Ф размера пт 14 (1 + 1), состоя!+1 щую из матрицы 3! и вектор-столбца г+ (С!!+!)чь ф1г'+'). ХХХ1. Если 1( !, то положить 1 = 1+ 1 и перейти к шагу ХХЧ1; иначе перейти к шагу ХХХ11. ХХХ11. Вычислить матрицу (С/+!)з' размера пг Х (! + 1) (С',+ ) ь = (р + р-зр-т) (С(+ ) ". ХХХ1П.
Вычислить матрицу 4+! размера пт Х и! /е) = (С' )~((С/ )~) . ХХХ!Ч. Вычислить матрицу 6!~+! размера /и 14 и! а;+ — — 1 — (С+ ) (С ). / ! 4. ХХХУ. Вычислить величину 6"= ! !г б!+! — ганя 6!+! (, / Если 6" ( 6, то перейти к шагу ХХХЧ1; иначе перейти к шагу ХХХЧ11. ХХХЧ1. Положить С!+! = (С!+!)~, б!+! = /г!+!, !1!+! (с/!+!. ! = /+ 1 и перейти к шагу ЧП. ХХХЧ11.
Положить 5+' /е!/+!, 1 /+ 1 и перейти к шагу ХХ1Ч. Библиографические уаиания. При написании параграфа использовались ра. боты 1246, 247, 249!. Дополнительные сведения о псевдообратных матрицах, спа. сабах псевдоабращения матриц, методах псевдообратных операторов можно получить в рабатах !244, 246, 246, 247, 246, 249, 252, 611.
2.7. Методы минимизации вдоль собственных векторов матрицы, близкой к матрице Гессе Задача 1. Найти агйш!п~е(х) для заданной непрерывно гел. диффереицируемой функции ~е: В" -з- 11!. Предположение 1. (г) — минимизируемая функция /е (х) трижды непрерывно дифференцируема.
На й-й итерации приводимых здесь алгоритмов вычисляются векторы /т'", Ь'", ..., /!"', представляющие собой систему, близкую к сопряженной по отношению к матрице вторых производных Ч~,/е (х"), и движение к следующему приближению ха+' осуществляется в направлении зтих векторов.
Шаговые множители вычнс- 112 ляются путем приближенного решения задачи одномерной миними- зации. Основной вариант алгоритма обладает квадратичной, а уско- ренный — кубической скоростью сходимости. 1. О»воевой варвавт Алгорилом 1 Н а ч а л о 1. Выбрать произвольное начальное приближение х' е В". П. Выбрать произвольную систему ортогональных векторов Ь", 1=1, ..., л, (((Ььо)(=1, 1 1, ..., и).
l П1. Выбрать константы ео) О, то > О, ач (О, — (, у ) 1, р>1. 1Ч. Задать последовательности положительных чисел (е»)» ~, '(()»)»», (со»)»», сходящиеся к нулю. Ч. Определить функции Л: В+ х В" х В'-~В', В»В+ х х В" х В"-~ В', 0: В" Х В+ х В+ х В" -э-В', соответственно„ по формулам Л(е, х, Ь) = — е — ' (1»(х-(-еЬ) — 1»(х))1 6(е, х, Ь) 1»(х+ ей(е, х, Ь)Ь) — 1»(х); 8(х, е, т, Ь) = 1,»(х+ ой(е, х, Ь) Ь) — 1,(х), где е Е В+, Е В+, .х Е В"; Ь Е В"; (( Ь 3 = 1. Ч1. Положить Ь 1.
О с н о в н о й ц и к л. УП. Положить хо» = х". ЧП1. Найти симметричную матрицу В» (Н»»), элементы которой ь»»; = ь»»т ь» = —,11 (х»+а»(ь' '+ь" ')) — 1»(х" +альп ')— »о» — 1о(х»+с»»Ф' ')+1 (х»)) (1=1 ..., и; 1=1, ..., и),. здесь Н»» = (Ьь ' Ь'» ' Ь"'»») 1Х. Применяя к симметричной матрице В» (Н» ~) метод враще- ний Якоби для вычисления собственных значений и собственных. векторов (360, с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
