Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 54
Текст из файла (страница 54)
Последующее приближение юлучается нз предыдущего смещением в направлении, протиеоположзом градиенту функции Р(х). Каждое гледугощсо приближегие ищштЯ виде хэю = ха — Е„Огас(Р(хп). Приведенное описание нг определяет алгоритм однозначно, посколькУ зичега не сказано о выборе параметра дя. Например, его можно апре !взять пз условия минимума величины (г) Р (х' — д„ Итадр(х")). 3 этом снучае рассматриваемый меюд называют мсгпадом наискорейшего уидиенпгиага спуска или просто менюдом наискорейшего сарска. З 8. Мевж наискорейшего гралиевтиого спуска и т1 х»+ = х» — 26»(Ах' — Ь).
Обозначим 2б„через Ь„т.е. положим хк' ' = х — 13»(Ах» — Ь). (3) Пусть уг(Ь») = Р(хкы). Вспоминая». что А = Ат, вычислим уУ(дг„). Имеем 1с[21») = Р(х ) — 2сь„(Ах — Ь, Ахв — Ь) -~- (А(Ах" — Ь), Ах — Ь)лу„— — (Ахв — Ь, Ах» — Ь)) = О, откуда (Ах" — Ь, Ахв — Ь) (А(А .-ь),А --ь)' На риг..
6.8.1 ггэображены последовательные приближения меиуга нанскорейгпего спуска и линии уровня функции Р. Итерационный процесс (3), [4) пвзггва~от маслодел~ паосксрееюсго спуске решения рассматриваемой системы линейных уравнений, Пусть собственные значения матрицы А расположены иа [д, М], г.
о. Ял с [д, М]. [4) Теорема. Пуясблвгюсвоя метода ив»- скорейшего спуска удоелсгллоря»вв солю»шпаною Рнс. В.ВА Рь[х ) < ( — — ) Ро(х ), Ро[х) = (А(х — Х), х — Х). (6) (,М+ р,) Доказопюяьюлео. Прн у" =х произведем одну итерацию оптимального цаношагового итерационного процесс:а у = у — (Аук — Ь). „+1 „ 2 М+р Погрешности итераций г" = уа — Х связаны соотношением (6) г"лг = [ Š— А) г". Для функции Р(х) = (Ах, х) — 2(Ь, х), соответствующей системе линейных уравнений с матрицей А = Ат > О, задача нахождения мияимума решастсв в явном виде.
В этом конкретном случае Взад Р = 2(Ах — Ь) 292 Глава 6. Численные метели влыбры Пусть еь.... -ортонормированнвя система собственнык векторов матрицы А: Ае2 = Лгее (еь е ) = е,". Пгкзюльку р < Л, < М, то при всех г выпелнюотся соотношения М вЂ” р 2 и — „.
<1 — Л;< М+р Мтр * М+р 2 М вЂ” р М+р Лй рр 1— и, таким образом, (7] Пусть г" = А,'сге,. Справедливы сеотг2ошения (Аг", гл) = ф:,Л,е,. ~ с,е,) = ~Л,сч 2Л, М+ р) т2 М -~- р) С учетом (7) получаем ЬГ л 2 ('ЯХ вЂ” Р' ,г г,мчр7' можно получить неравенство ()х- Х((2. ' )(х Х((2. -'Л,М+ру' 1 р Хотя на каждом шаге метода наискорейшего спуска уменьшение величины гЪ(х) заведомо не меньше, чем у итерационного процесса (6), Поскольку ге(у") = (Аг", гл], то зю означает, что 2 2 Ло(у" ) < ( ) йе(у ) = ( ) Ра(х").
Приближоние у "г можно записать в виде (1) у"+ = х" — о бгас1К(х"), и — — (М+ р) Так как на х +г достигается минимум г'(х) среди всгз приближений вщга (1), то Г(хэтг) < Р(у"+~). Опявда следует оценка М+ р) а поэтому и справедливость утверждения теоремы. Аналогично (7.9) 293 48. Мепщ нанскорейглего градиентного спуска »гы получили примерна одинаковые оценки скорости сходиыости. Однако есть принципиальное различие в этих методах. Длл наппсанпл пшгг»щпангшго пр»щссса (6) тргбуегася г»нФармацпл а грзннцаг: спектора р, 34. В случае гшшгх)а (3), (4), гапкой информации не шребрешсл.
Отметим также то важное обстовтельства, что метод наискорейшего спуска «вляется нелпнебным итерационным методом; параметры метода ца каждом шаге выбираннз;я в зависимости от полученного приближения. У метала наискорейшего снугыл (3), (4), од»гака, есть глелующнй недостаток по сравнению с простейшим нраш«гпм (6). При нахождения кгзкдого следующего прнблнлсения ан зребуог не одной, а двух трудоемких операций умважеаня матрицы на еекюр. Двукра н га у» ноя»ения матрицы на «г.кзор ри каждой итерации можно избежать шюлуюшил» обрюом Обозна щи я" = Ахн — Ь н перепишом (3) в виде х"г = х" — Аяп". (8) Вектор кж и юывает»я егхшарап г»связка Умно»кая (8) »лева яа А и вычизая Ь, пшгучвм (0) Формулу (4) дяя определения »3„мож»»а записать в виде (н", шя) (Аш'", и )' (10) В процессе итерации:юном ннаются ыигоры х", я"' н на каждом шаге паследоаатгльно вычисляка»я Аа", Ае, хэ "', »ч"з'. В исходном иегодг наискорейшего гпу«ка (3), (4) погрешность нг шыо итерации раваосильна жпмущгнию назым»»ага приближения и, полз»альку процеш сходягцнйся, ш влияние дол»кно нме»ь тенденцию к затуханию.
В»ггерапианном процеша (8)-(10) пако»пенне вы гислитгльной погрешности носит более сложный характер. Ввдачн 1. Получить оценку скорости сходимооги метсда наискорейшего спуска ((ха — Х((з < (1 - р)34)е((х' — 30)(з. Реальный выбор игерационнап» процесса должен производиться с учетом имеющейся информации а гралице спектра, объеме и структуре па»сити ЭВМ. Например, при решении сеточных уравнений, аппроксимирующих дифференциальные уравнения в частных про»швадных, иногда цц)ч' па следующему пути. Рассматривая задачу на более крупной сотке, пРоводят вспомогательную работу по всаможно более тачноыу опреде. нению значений д и М, соответствующих более мелкой сат»ш, а затем нрименякж оптимальный линейный итерационный процшх.
Глава 6. '1вглениые лгегады алгебры Обратим внимание на интересное обстоятельство. Из пюмегрической картины итераций метода Зеуслеля видно, что скорость схолимости мета. ла не меняется при умвожглии уравнений системы на мнолсители и гмменении масштабов по координатным оглы, равносильном замене зз = й,уг Иначе обстоит дело в случае мезгща наискорейшею глусю1. Пусть, например, А = Š— единичная матрица.
Тогда Р(х) = (Ах, х) — 2(Ь, х) = ) хз — 2) 6;аз .=.1 =1 и метод наискарейп1его спуска сходится за одну итервлню (доказать!). Произведем замену ьшсштвбав х, = Црч г, > О. Матрица системы А в данном случае будет диагональной с злемгзг1ами на диагонали, равными йь Тогда мипимизиругтся функционал Р(у) =. (Ау, у) — 2(Ь, у) = ~ 11р~ — 2) б,уг -1 =1 При болыпом рвзбрглп 11 линияыи уровня функции Е' будут сильно вытянутые зллипсоиды и скорость гходимости метода наискорейшего спуска будет очень медленной. 2 9.
Метод сопряженных градиентов Метод сопряженных градиентов предназначен для решения систем ли- нейных алгебраических уравнений Ах= Ь с симметричной положительно определенной матрицей А. Предположим, что мы имеем некоторое начальное приближение х . е Обозначим черш гв = А(хо — Х) невязку начального приближения; здесь Х вЂ” точное решение системы (1). Поставим слевующую задачу — -пестро" ить мноючлен Р (Л) степени и, удовжтеоряюво1й условию,Р„(0) = 1, такой, что значение функционала Р(х") = [Ах", х") — 2[Ь, хв), где х находится из соотношения гв = Р„(А)ге, (2) будет минимальным. Тв,к как Р(у) = (Ау, у) — 2(Ь, у) = ()у — Х((л — ((Х((л = ((Ау — Ь(),1, — ()Х((л, то данная задача может быть переформулирована гледукяцим образом. ТРебУетса найти Рв(Л), Р (й) = 1 таыэй, .1то ноРма невизки ((г" ((Л-~ бУДет минимальной. В 9.
Метод сопряженных градяентов Покажем, что зта задача всегда разрепчима единственным обри!ем. Пу я ч Р (Л) = г с11 )Л", ге~ ! = 1 и ге = ) г,ее (3) ь=-е 1=1 где г, ф О, 1 = 1,..., д, а е, собствепнь1е векторы А, соответствующие раялнчпмм собственным значениям А. Предо!веление !3) всегда возможно, так квк матрица А симметрична и невырождона. Вектор г" имеет вид !!! =а / *=.! Лг=е / *=1 Ль=с и )г ))з, = (А 'г', г") = ) чч ) ~ с1")ЛГ 1~) () с!2!Л"; Ль=!! / ),г=о Мы ищем минимум щоп! выражезчия относительно коэффициентов счщ~. Прираеюивая чаопчые проязвсднью нули>, получим = 2) ч' г." Лчг,Л! '1 = 2(г", А' 'г ) =О, 1=-1,..., и. ЩЕ ),1=Е Таким образом, в ючке минимума должны выполняться равенства (г", А'гс) = О, 1 = О,..., и — 1.
(4) Пусть и р о — 1. Из курса линейной алгебры известно, по векторы ге, Аго .. Ач — 1ге образуют линейно нщааисимую систему !пространною Крылова). действительно, допустим противное. Тогда существуют постоянные се,..., с 1, не 1жвные нулчо одновременно, такие, что ч-1 Е с;Ачг =-О. Подставляя вместо ге его разложение из (3), получим 'с Ч1 Ч 1 Ч ч — 1 ч ч /ч-1 В" =В'К =ВтВ;1;с=К;.~х.е)= *=.е ,=Е 1=1 ч=в 1=1 1=1 ч=о Глава б.
Численные мегалы алгебры Таким образом, так как г и О, то должны выполняться равенства (5) т. е. к<оффициенты с; должны удовлщворять системе уравнений (5) Определитель матрицы системы (5) <овпадавт с определителем Вандермоцца и отличен от нуля, поскольку все Л различны по првдполол«ь нию. Отскда <э<сдует, что равенсгва (5) могут выполняться только при се = ° -. = с < = О. Таким образом, векторы го, Лгэ,..., Аг <г действительно образу<от линейно независимую систему. Мно<ичлен Р„(Л) имеет и неизвестных коэффициентов (Р„(О) = 1); тэк как сисгю<а линейных юптбраических уравнений (4) невырождена, то коэффициенты с„", й = 1,..., и находятся из эее однозначно.
Это означжн; что поставленная задача всегпа имеет единственное решение. Посла нахождения коэффициентов с<, й = 1,, и, значоние ха из (О (2) накопится <ледующим обркюь<. Из<о<и А 'гв =х" — Х =Р„(А)(хэ — Х) ='> с")Л"( в — Х) = ь=е = ) с(в)А"(хо Х) +хо Х = хо Х 4-) с(")Л<-<(Ахо Ь) ь=-< ь=! откуда <шедует х" =х" + ) с(,")Аь '(Ах — Ь).
л=< Обсаначим через бь линейную оболочку векторов гв, Агв,..., А"г". Из построения видно, что г< = Р (Л)г" б Ог, 1 < й. Покажем, что гв, г,..., г" образуют базис в Ью Доказательство проведем индукпией по и. Для и = О утверждение очевидно, Предположим, что для и = й векторы г", г<,..., г" образуют базис в бь (и, как следствие, явля<отса линейно независимыми). Покажем, что сис<ема ге, г<,..., г"+< также линейно независима.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
