Том 2 (1160084), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

ПовеРхности У" (х) = сопз< образуют в л-мерном пространстве Й семейство эллипсоидов — 1 с общим центром х*=А К Коэффициенты р<А+1! определяются из системы ~ ~<<»+1<(Ах<<1, хйй)= — (Ау<"+'1, х<й) Ц=1, 2, ..., Л). (30) 1-1 4 51 метод сопРяженных ГРАднентоз Учитывая симметричность матрицы А, преобразуем разность г<х) — 7(х').

Получим: ( (х) — у (х') = (х, Ах) — 2 (К х) — (х*, Ах ) + 2 (К х') = =(х, Ах) — 2(Ах, х')+(Ах*, х")=(х — х', А(х — х*)). (2) Так как А — положительно определенная матрица, то 7'(х) — 7 (х*) ) О, причем знак равенства достигается лишь при х= — х'. Таким образом, задача об отыскании решения уравнения Ах = 5 эквивалентна задаче об отыскании вектора х, обращающего в мимимум функцию /(х), определенную (1). Существует много методов решения последней задачи. Об одном из таких методов мы здесь и расскажем. Берем произвольный начальный вектор х<о). Будем смещаться, начиная с точки, определенной вектором х'о), по нормали к эллипсоилу у(х) =/(х<о)) до тех пор, пока эта нормаль не коснется какого-то эллипсоида семейства у(х) = сопай Получим новую точку. Вектор, проведенный в эту точку, обозначим через х<').

Отыщем этот вектор. Введем обозначение г<о) ~~ — Ах<о) (4) ! — 7(х<о)+ас) ! (5) принимает наибольшее значение при условии (с. с) = сопзй Функцию. стоящую под знаком производной, можно записать в виде T(х<о)+ас)=(х<о)+ас, Ах<о)+аАС) — 2(Ь х<о)+ас) = = аз(с, Ас) — 2а(г<о), с)+)'(х<о)), (6) Таким образом, — ~(х<о) + ас)! = — 2 (гн), с).

до Используя неравенство Буняковского, получим: (г<о), с)а < (г<о). г<о)) (с, с), (7) (8) и покажем, что вектор г<о) имеет направление нормали к эллипсоиду 7(х) =у(х<о)) при х = х<о). действительно, нормальное направлемие будет совпадать с направлением быстрейшего убывания функции 7(х) — направлением градиента. Таким образом, нам надо найти такой вектор с, что З2 гашение систем линейных ллгаввличвских гглвнвний [гл. 6 причем при с=гад имеет место знак равенства. Итак, искомое направление будет определяться вектором г(а>. Найдем теперь такое и, при котором /(х(л>+аг(а>) принимает наименьшее значение.

Используя (6) при с=г(е>, найдем, что искомое и, которое мы обозначим через пз, равно (р(о> г(о>) (г(о) 4г(о>) (9) Итак, х(>) х(о>+ а г(о> (10) х/ -у/х (>>/ Рис. 1. название ме>пода скорейшего спуска. Рассмотрим его несколько позже. В настояшем параграфе будем получать х(а) иначе. Рассмотрим векторное уравнение (Аг(а), х — х('>) = О.

(11) Оно определяет гиперплоскость (п — !)-го измерения. Уравнению (11) удовлетворяет вектор х = х('). Ему удовлетворяет и х*= А Ь. Действительно, (Аг(о) А Ь вЂ” х(г)) = (г(о) Ь А ~(>)) ( (о) и>) (12) где через г(') обозначен вектор г(~) — Ь Ах(>) г(е> ! 4 (л(а) еп)) г(о) и Аг(о) Как и раньше можно показать, что вектор го> имеет направление нормали к зллипсоиду /(х) =/(х('>) (14) На рис, ! показана геометрическая картина нашего построения при п=З. Можно было бы продолжить наш процесс и получить из х('> вектор хсг> так же, как мы получили из х("> вектор х('). Мы пришли бы тогда к методу последовательных приближений, носяшему а 51 мвтод сопгяжвнных гглдивнтов р!') = гп) + рог!о) (!5) Так как вектор Аг!" ортогонален к гиперплоскости, то и ро' должен быть ортогонален к Аг!').

Зто дает (г"), Агю)) 'г'о (г(о, ~г)о)) . (16) Будем теперь отыскивать такое а, что у(хо)+ар(')) принимает наименьшее значение, Так как У(хп) + аРП)) = а'(р') Арй)) — 2)) (гн), рп)) + У (хн)), (17) то искомое значение а, которое мы будем обозначать через ач равно (г ) Р )) ( †)г) -(и) , АР (!8) Итак, х<й = хп) + агрп). (19) На следующем шаге мы перейлем к гиперплоскости (а — 2)-х измерений, определенной уравнениями (11) и (Арп), х — х(о)) = О. В силу ортогональности ро) и г!о) = )) — Ах)а) = г(П вЂ” а,АРП) (21) — 1 получим, что х'=А К принадлежит нашей гиперплоскости ! ынм образом, и эта гиперллоскость будет диаметральной.

Отметя....це слелующие свойства гм): () Ф) ) КВ) — () )Н а,АРО), Г)о)) — О (г(а) г!))) = (гн) — а)Ар))), )"г)) = (г!и — а,АР)н, ргп — Цг(о)) )22) = (гн), рп)) — а,(АР®, рн)) = О, (23) при х = хн), Вектор г! ' касается этого эллипсоида в той же точке. Следовательно, (г)о), г(')) = О Сечение гиперплоскостью (11) эллипсоидов у(х) = с дает диаметральные гиперплоскости (п — 1)-го измерения, проходягцие через точку, определяемую хщ.

Булем теперь проводить наши рассуждения лишь в этой гиперплоскости. Нормаль к эллипсоиду, получающемуся в сечении Г"(х)=у(х(н) гнперплоскостью (11), можно получить, проектируя г(') на гиперплоскость. Обозначим эту ) роекцию через р<') и булем разыскивагь ее в виде 34 гашении систвм линвйных алгввгаичвских.явавнаний !гл. 6 Проекцию нормального к эллипсоиду 7'(х) = 7(х<а)) при х=х<з) вектора г<з) на гиперплоскость — вектор р<Я) — будем разыскивать в виде рй) — г<з) < а р<г) (24) Нужно потребовать ортогональность р<з) к Аг<е) и Арш.

Но (р<з' Аг<о)) (г<я) + ~ р<п Аг<е)) (г<а) Ар<я)) (г<я), г<о) г<))) — <) "о <25) Условие ортогональности ра) и Ар<о записывается так: (26) Гр"), Ар<')) Теперь, как и ранее, отыскиваем значение а, для которого 7(х<з)-<-ар<а)) принимает наименьшее значение. Это значение а, которое мы обозначим через а,, будет равно () Р) )<а)) ае <27) Гр"'. Ар<а)) Поэтому вектор х<з) будет представляться в виде х<а) = х<з) .+ аер<я). (28) р<е) ).<е) ().<а) р<ю) (р <") А <")) (ЗО) х<"+') = х<") .+ а„р<а), г<~+о = г<") — ааАР<ь), (31) (32) (г < + ", Ар <" ') (ЗЗ) (р<~), Ар<а)) Р<а+)) .<ьч.)) + ЗьР<а) (34) Отметим следующие свойства членов этик последовательностей.

В силу самого построения будем иметь: (р«), Ар<)))=(Ар«), р<)))=0 при (чь г'. (35) Так же продолжаем и дальше. Получим последовательность векторов (х<л)), (г<">), (р<Ы), которые определятся рекуррентно следующим образом: (29) 35 мвтол сопгяженных ГРАливнтов 51 далее, при ()у получим; (г((), рЫГ) = () ((-)) — с< Ар((-г) р0))— = (гп <), р0)) — о( (рби Ар((-<)) (36) Правая часть последнего равенства равна нулю при (=у'+1 в силу опрелеления я( ).

При с')/-4-1 она будет равна (г((-г), р0)), т, е, индекс у г<" понизился на единицу. Повторяя рассуждения достаточное количество раз, мы прилем в конце концов к случаю, когда индекс у г будет на елиницу больше инлекса у р. Слеловательно, при ()у (г<(), р<Л) = О. (37) Наконец, рассмотрим (г((), г())) при ( Ф/.

Пусть, для определенности с ) у. Тогда (г< ), г())) = (г<'), ро) — ~,,р<~-')) = (г®, р())) — ~,, (г('>. р(~-))) = О. (38) ) (а) с(а~~(о~.+ с(а)Аг(о) + + с<за)АагТе) о 1 (39) Это свойство очевидно, если вспомнить ход процесса ортогоналиаацин, как он определен выше. 2. Вектор г<" +') ортогонален к наименьшему линейному многообразию, содержащему векторы г(е).

г<'), ..., г(е). Действительно, если г<а+') = О, то утверждение тривиально. Вели же г("+') чь О, то и каждый из векторов г('), г('), ..., г(а) не Р~~~н нулю. Совокупность последних векторов образует базис наимен 'ныпего линейного многообразия, содержащего векторы г(е), Аг(е), е е ° ° " А"г(е). Вектор г(а+'), будучи ортогональным ко всем Так как в и-мерном пространстве не может быть более и взаимно ортогональных векторов, то на некотором шаге <е (и мы получим гн') = О, При атом х(Ю= А 'о.

Таким образом, на некотором шаге мы придем к точному решению системы. Такой способ получения решения будем называть методом сопряженных градиентов, Методу сопряженных градиентов можно дать простую алгебраическую трактовку. Будем таким же способом, как зто делалось Ранее, ортогонализировать систему векторов гй), Агю),..., Ааг(е)..., Полученные при атом векторы г(е), г<')...

Характеристики

Список файлов книги