Бабенко - Основы численного анализа (947491), страница 103
Текст из файла (страница 103)
Теперь уже не составляет труда сформулировать экстремальную задачу о выГюре оптимальной стратегии выполнения итераций так, чтобы на т-м шаге выбранная мера погрешности была минимальна. Выбор стратегии —. это, другими словами, выбор величин с,, д., (р — 1,'2, ...,,— 1). Погрешность будем измерять в среднеквадратичной метрике, т.е. примем в качестве меры погрешности величину до = (ью во) ~-.
Учитыг!г е вая формулу (21), можно записать б в виде 1 дг = ~'Б'(1)р' = / Вг(1)да(1) з'=1 0 (22) где дег(Л) -- чистая функция скачков. Формула (22) неудобна в том отно- шении, что нам не известна мера дп. Поэтому можно радикально упро- стить задачу, выбрав в качестве меры погрешности функционал дг = / Я.'(Л'уз(Л)1Л, о (23) ! где р(Л):,[О, 1' — К+ весовая функция [' р(Л)е(Л ( сс. в Будем считать, что матрица А симметрическая, а стало быль, и положительно определенная, поскольку спектр ее лежит на отрезке [т, М).
Без ограничения общности примем, что М вЂ”.. 1: этого можно добиться умножением матрицы А на соответствующую константу. Тем самым в реальных ситуациях и ма ю, и мы будем иметь дело со сравнительно плохо обусловленными матрицами. Пусть ео:, р — компоненты векторов е = ж — с, у = те — с в базисе из собственных векторов матрицы А. Тогда из формулы (19) следует, что "о 5. Итерациоппые методы решения систем линейных уравнений 501 Экстремальная задача. На множестве многочлене степени о, удовлетворяющих условию (20), найти такой, который дает решение экстремальной задачи о~ = / В'-,(Л)р(л)дл -г 1пГ. (24) Эту экстремальную задачу легко решить. Предложение 1. Пусть (р„(Л)) — система ортпогональных много гленов на отрезке [О, Ц с весом Лр(Л). Экстремальный многочлен задачи (24) имеет вид В(л) —..
р,(л) !р,(о), а экстремаатгос. значение интеграла равно (2о) 1 о Пусть (д„(л)) "- система ортонорлгированных мяогочленов на отрез- ке [О, Ц с весам р(Л). Тогда Р г и з-1 р'( ) = с о (л)о (о) ~~4(о)~ р,(о) 1 1 [~' $ лов — [Ело)~ о Доклзатвльство. Если В, = 1 -' азл +... -; а.,Л вЂ” экстремальный многочлен задачи (24), то из условия минимума ддг/да, = О. Это соотношение влечет равенство 1 Х,(Л)Лэр(Л)йл = О, у' = 1, 2, ..., и, о о оэцэ(0) = 1. э=о т.е. многочлен В,(Л) ортогонален к любому многочлену степени не выше о — 1 по мере Лр(Л)дл.
Следовательно, формула (25) доказана. в С другой стороны, В (Л) = 2, о а (Л), причем з=о 502 Глава 3, Теория итераций и методы Решения некоторых задач Поскольку 1 Л2(Л)р(Л)е1Л вЂ”.. Е О2, о з=:е то экстремальная задача сводится к задаче на минимум » о,.- ш( з:-о при условии (26) . По правилам дифференциального исчисления минимум будет при » о, .=- в,(0) ~~ во(0)~, д' =.
О, 1,..., е, з=е а отсюда следуют утверждения леммы. В Э 3 гл. 2, мы уже разбирали свойства ортогональных многочленов. Было установлено, что три последовательных ортогональных многочлена связаны рекуррентным соотношением р,з1(Л) = (໠— с,Л)Р„(Л) — о»Р, 1(Л). Считая, что многочлены р„(Л) удовлетворяют условию (20), получим Р э1(Л) = (1+ А» — с»Л)Р»(Л) — 4 Р»-з(Л). Покажем, что если константы с,, е1, в этой формуле отождествить г, аналогичными константами в формуле (16), то на каждом шаге итерационного процесса многочлен погрешностей будет иметь вид Л (Л) = р (Л). Но это — простое следствие рекуррентной формулы, полученной выше: Р (Л) = Р д(Л) + с (1 — ЛР 1(Л)) + п»(р д(Л) — Р„2(Л)); если в этой формуле перейти к многочленам хе,(Л), .то получим Л.„(Л) = (1- д.
— с,Л)Л,(Л) — д,Я,,(Л), т. е. в точности рекуррептную формулу для многочлепов Р„(Л). Поскольку е1е = О, как мы выше условились, н Ве = 1, то Г»2(Л) = Рз(Л), и, следовательно, Л,(Л) = Р,(Л). Итак, мы построили оптимальный итерационный процесс второго порядка. Выбирая вес тем или иным способом, мы получим различные оптимальные итерационные процессы. 3 а д а ч а 3.
Укажите внд констант с», д» в соотношении (16), которые дают оптимальный итерационный процесс второго порядка, считая, что весовая функция представлена в виде р(Л) = (1 — Л) Ло (о > — 1,,6 > — 1). Связь многочленов, ортогональных с весом Лр(Л). с оптимальными изерационными процессами второго порядка установлена Е, Штифелем. "5 5. Итерационные меллаам решения сватам яинайнмт уравнений 503 4.
Построение оптимального итерационного процесса. Остановиллся на вопросе построения итерационного процесса второго порядка, когда в качестве ллеры погрешности принимается функционал А, = (Ае,. е„)'~и = (А 'т„г„)Из. где и„— погрешность на и-и шаге, а т„невязка. Из формулы (17) непосредственно следует,что тъ = ',1 — АР— л(А)~гс, т.е. многочлен погрешности совпадает с многочленом невязки. Иак и вы- ше, мы получаем экстремальную задачу: д' = (А 'Л„(А)тв, В,(А)ге) — 1пГ, где минимум ищется на множестве многочленов степени и, удовлетворя- ющих условию (20). Но 5,' = ~Л,-'И',-(Л,)лут = / Л-'И=..(Л)1п(Л), з=1 О где д -- компонента вектора те в базисе собственных векторов матрицы А.
Полагая  — 1 -'. алЛ +.... а Л~, из условия минимума функционала 5, получим Л,(Л)Ла" 'с6т(Л) — —. О, л .—... 1, 2, ..., ш Такилл образом, многочлен г5т(Л) —. ортогонвльный многочлен по мере дд(Л). Как и в непрерывном случае, отметим, что три последовательнлях ортогональпых многочлена связаны рекуррептпым соотношением, если степени этих многочлепов ие превосходят числа точек роста меры лЫ(Л), Достаточно рассматривать общую ситуацию, когда все собственные значения различны, поскольку сколь угодно малым возмущениелл матрицы А можно этого добиться.
А отсюда следует, что окончательные выводы справедливы и в случае кратных собственных значений. Поэтому так же, как и раньше, мы устанавливаем, что соотношение (16) можно записать в вице г,, л =- (1 + л1, — с А) 㠄— г1, т, и л =- 1, 2, ..., п — 1.
Поскольку ортогональность многочленов 17„по мере ламп(Л) эквивалентна соотношению (г1 (А)те, й,,„(А)тв) = (т„, та) = О, если и ф р, то коэффициенты с, л1 в последней формуле могут быть найдены из условий ортогопалыюсти вектора т л к векторам т, т, 504 Глава 3, Теорие итераций и методы регаенал некоторых задач Таким образом, мы пришли к итерационному процессу., именуемому методом сонрлонкенных градиенгаов. После конечного числа шагов вектор невязки долгкен обратиться в нуль, так как су.ществует лишь конечное число взаимно ортогопвльпых векторов.
Обычно в методе сопряженных градиентов функционал погрепшости берут в виде гл = (Ах .х„) — 2(а.х,)., учитывая, что единственный минимум функционала (Ах, х) --2(а, х) реализуется на решении уравнения Ах =- а. Но легко видеть, что 1л .— —. б,-— — (А га, а). Существует нескшгько вариантов написания формул метода сопряженных градиентов. Ыы на этих вопросах уже не можем останавливаться, равно как и на вопросах о влиянии погрешностей округления при реализации этого метода. б.
Наилучший скалярный процесс. Формула (21) наводит на мысль, что в качестве меры погрешности можно принять также величину (27) шах Л (Л) .. ЛЕ"т,1 При таком выборе меры погрешности лгы получим следуюшую экстремальную задачу. Экстремальная задача. Уа мнохсества многочленов (гЧ„(Л)) степени не выше и, удовлетворяющих условию (20), найти глакой, который г)аепг региение задачи прах [11,(Л) г 1пП Лейт Ц Предложение 2. Решением поставленной экспгремальной задачгг явллетсл многочлен где Т вЂ” мггогочлен Чебыгиева ггервого рода. ДОказА'гельйтВО.
Допустим, что имеется многочлеп Я„(Л) степени не вылив и, для которого шах [Я,(Л)[ < плах 1,(Л) . Ле т,1 ЛЕ гп.1) Поскольку многочлен г,(Л) на [т, Ц принимает свое максимальное значение с чередующимися знаками в и+1 точках, то многочлен 1,(Л) — Я„(Л) имеет на (т, 1) не менее и корней.
Кроме того, 1„(0) = о„(0) = 1, и, следовательно, гт(Л) = К,(Л), что противоречит исходному предположению. Ц ~ 5. Итерачионные месаоди решения систем яинейних рраонсн™й 305 Из доказанного предложения вытекает, что т .—. 1п1 лпах,В„(Л)! = Т,( — ) ле!т ц ( 1 — лп где нижняя грань берется по многочленам степени не выше и, подчиненным условию (20). Поскольку. многочлены Чебышева либо четные, либо нечетные функции, то т =[Т( )) (28) Построим процесс второго порядка, для которого многочлен потравь ности будет оптимален на каждом шаге, еспи в качестве меры взять функционал (27). Это построение мы произвели выше в счучае функционала погрешности (23). Напомним, что многочлены Чебышева связаны рекуррентной формулой Т„+,(х) = 2хТ,(х) — Т, л(х) (и = 1, 2,...).
Учитывая слазь между многочленами 1, и Т„, ло последней формулы после простых преобразований получаем 1+т, 4т„Л л 1нтл(Л) = (2 оы )1н(Л) — оное л1н л(Л), (29) 1--т 1-т где т = т„,/т„. Поскольку!,(0) = 1 (и = 1, 2,...), то из формулы (29) после подстановки Л = 0 получим 1 -' т 1 — 2 о, 1-о,о, л=0, 1 — т (30) откуда о, = (2 — о„ 1) (31) 4о, г 1+т Ьх =- г -~ (2 и, — 1)Ьх 1 — тп 1 — т (32) эта формула определяет итерационный процесс второго порядка, оптимальнгпй на каждом шаге. Этот процесс является наилучшим скалярным процессом, и поэтому нет необходимости рассматривать скалярные процессы высших порядков: он является также релаксационным процессом, Учитывая формулу (28), подсчитаем тн. Раньше нам встречалась формула Т (с!лсо) = =- с!л и >; полагая с!лес —.
(1+т)/(1 — т), получим. что ы —. !и ((1-,~ от)/(1— —,/т)), и, следовательно, Заменим в соотношении (29) коэффициент — о„о, л на 1 — 2 л,„о„; тогда е! = 2-~-'пзбг . 1, с — ' . Следовательно, 506 Глава д, Теория итаероцай и мгтаоди решешал некоторых задач Из соотношения (21) вытекает неравенство ~хо — ~~2 ~ т,,'хо — ~~ >, откуда следует, что )х,— 62(2( ) ~хо — 6' (33) Сравнивая эту оценку с оценкой (13), в которой нужно положить ЛХ = 1, мы видим сущоствснное увеличение скорости сходимости, Так, если урав- нять погрешности, то для чисел итераций получим соотношение 3 а д а ч и. 4.
Рассмотрим скалярный итерационный процесс второго порядка и выберем в качестве меры погрешности функционал (23). Возьмем у(Л) = (1 — Л) Л", где о ) — 1,,13 ) —.1. Покажите, что для оптимального про- цесса т 1 З 112 . =- ~1В'.(Л)(1 — Л) ЛвдЛ1 о = Г(64- 1) з 1 (2> -~- о д 4- 1)Г(1 о+,3+ 1)Г(1+ д -1- 1) ) )С~- .Г(д'+о —:1) >=О трклзание. В формуле (25) многочлены рь(Л) — многочлены Якоби, приведенные к отрезку (6, 11 Воспользуйтесь формулами (2.3.40), (2.3.45). ЗАмечАнне. Если в формуле (34) положить о =,3 = — 1>2, то 11'2 д„= я/(2(и 1)] . Сравнивая эту величину с константой т, мы видим во что обходится незнание ни>клей границы спектра матрицы А.
5. Докажите, что для метода сопряженных градиентов оценка скорости сходимости Лается неравенством см>с> — 1' где и.= сопс)2А. Для отыскания минимума функции Е: В." -ч В. часто используют метод, называемый методом иаискорейшеео спуска. Существо метода состоит в следующем: строят последовательность х т> =-х -П,йгас1Г(х ) и скаляр т выбирают из условия Г(х — т агас1 Г(х )) — >сп1. ОтКуда р>,с'С>2 —.— Ч>т+ 0(ГП), Н Прн МаЛОМ тл МЫ НабЛЮдаЕМ СущсетВЕННОЕ различие в числе итераций. з 5. Итерационные метаем решения систем яинейнмх уравнений ае07 6. Для функционала Ь(х) =.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
