Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 24
Текст из файла (страница 24)
Поставим задачу выбрать итерационные параметры т,, а, так, чтобы при любом и=-1, 2, ... была бы минимальной 1~о„~~=,'1гД Обратим внимание на отличие от постановки задачи, возникающей при построении оптимального чебышевского набора итерационных параметров (см. % 6). Там при фиксированном и требовалось найти параметры, минимизирующие 1~г„~~, . Теперь же требуется большее — минимизировать 11г„'~„при каждом и. 121 (36) 122 Параметр т, находится из условия минимума 11о,1~ при заданном векторе о,. Так же, как и в методе скорейшего спуска, получаем " 1(~се, оо) (34) 11 Сов >>~ Отметим, что при таком выборе т, выполняется равенство (Со„о,) = =О, т.
е. векторы о, и о, ортогональны в смысле скалярного про- изведения (и, о),=(Си, о). Далее, рассцотрим погрешность о =-Р,(С)о„ возникающую на й-й итерации, н запишем многочлеп Р,(С) в виде Рх(С) =Е+ "Я а';~~С', >=1 где ам> — числовые коэффициенты, определяемые параметрами а„ ть 1=1, 2,..., й. Тогда ох = о, + '~> а; >С'о„й = 1, 2, >=- > Найдем условия, которым должны удовлетворять коэффициен- ты а(">, минимизирующие >>о„>~'. Из (36) получим и и >>о„>>'= с" а~"~а>л~(С>о,, С>о„) + 2~х~ а ">(о, С'о,)+1>о,!)', (37) и! =1 > =1 т.
е. ',1о„1Р является многочленом второй степени по переменным а>н>, ..., а>„">. Приравнивая к нулю частные производные д~~о.Г/ )да>л>, 1=1, 2,..., л, приходим к системе уравнений л 'У, а';"' (С'о„С>о,) + (С>о„о„) = О, (38) >=1 решение которой а!в, 1=1, 2, ..., п, и обращает в минимум 11о„11'. 6. Выбор итерационных параметров в методе сопряженных гра- диентов. Е[елью дальнейших рассуждений является нахождение па- раметров им т„й=1, 2, ..., и, для которых выполнены условия (38). Заметим прежде всего, что (38) можно записать в виде (С'о„о„) =О, 1'=1, 2, ..., и.
(39) Л ем м а 1. Условия (39) эквивалентны условиям (Со„о.) =О, 1=0, 1, ..., и — 1. (40) Доказательство. Согласно (36) имеем > Со; = Со„-1- '~~ а,'" С> "о„ поэтому I (Соь о„) = (Со„, о„) + ~ч~ а,"~ (С "о„, о„) = >=1 >'-1 =(Сол о ) + '~~'аО>,(С'оо ол). (41) > =й Пусть выполнены условия (39) Тогда, если /+1(и (т. е, 1 <и — 1), то (Сом о„) =О, (С'о„о„) =О, ..., (С'"о„о.) =О. Поэтому из (41) при 1' 'и — ! получим (Соь о„) =О. Итак, условия (40) следуют из (39). Пока>кем, что верно и обратное, т.
е. из (40) следует (39). Доказательство проведем индукцией по числу 11 Условие (40) при 1=0 совпадает с условием (39) при 1'=1. Предположим, что условия (39) выполнены для 1= =1, 2, ..., й, и покажем, что они выполнены и для 1'=й+ 1, где й(п — 1. Из (40) при 1'=и получим, учитывая (36), о = (с;, ~) = ( с, ~- т Й" с"э., ..~ = >=1 л ! = (Со>и о,) +" ,а' ', (С'о„о„). (42) По предположению индукции условия (39) выполнены при = 1, 2„..., /г.
Поэтому нз (42) получил> ал (Сл"о„о.) =О, Посколькуали>~0 (так как Р,(С) — многочлеп степени й), отсюда получаем (С'л'о„о„) =О, т. е. условия (39) выполнены и при 1= =й+1. Лемма 1 доказана. Она потребуется для построения оптимальных итерационных параметров в методе (26). Заметим, что число и в лемме 1 предполагалось фиксированньщ, в то время как при постановке задачи оптимизации мы требовали, чтобы йо„й была минимальной при любом и= 1, 2,... Поэтому оптимальные параметры надо отыскивать не из условий (40) при фиксированном и, а из условий (Со„о„) =О, и=!, 2,..., 1=0, 1,..., и — 1. Если такие параметры будут найдены, то это будет означать, что построена ортогональная (в смысле скалярного произведения (и, о),= (Си, о)) система векторов о„ о„ ..., о„, ...
Поскольку пространство решений системы (1) имеет размерность иг, постро- 123 енная ортогональная система будет содержать пе более т векто- ров. Это означает, что начиная с некоторого и (п(т) погрешности о„ обратятся в нуль, т. е. метод сойдется за конечное число ите- раций. Перейдем к построению итерационных параметроа, для которых выполнены условия (43). Параметры а, и т, найдены согласно (34): а,=1, т,= (С"а* оо) (44) !! Со. Г Пусть параметры ть т„..., г,, а„а„., а, уже выбраны опти- мальным образом. Тогда согласно (43) выполняются условия (Со„о,) =О, г=1, 2, ..., й, 1=0, 1, ..., ! — 1. (45) Построим оптимальные параметры т„„а„э,.
Согласно лемме 1 при и=й+1 должны выполняться услония (Со„о„.„) =О, 1=0, 1, ..., й. (46) Часть из этих условий, а именно условия (46) при 1=0, 1,..., й — 2, следует из (45), Действительно, согласно (29) имеем (о!„„Со;) = аь„(о!„Со;) — аэ„т! „(Соь, Со1) + (1 — а„,,) (ох „Со;). Из (45) при 1=й и 1=й — 1 получим, соответствеюю, (Сол оь) =О, 1=0, 1,, й — 1, (Соь о/,,) =О, 1'=О, 1,, й — 2. Поэтому (о„„„Со,) = — а„.,т„,(Со„, Со!) ., й — 2. что для этих же значений 1' выполняются равенства Запишем уравнение (29) при й=1': !!!!, = а,„, (Š— т„, С) о, + (1 — а,! !) о,, при !'=О, 1, Покажем, (Со„, Со;) =0 124 и найдем отсюда ! Со!' = — ог — !о! „! — (1 — а!ч!) о!' — ).
!'!-! "!.!-! !'.~! Умножая предыдущее соотношение скалярпо па Со, и учитывая симметричность матрицы С, получим (Соь Соь) = ! 1 — (о ' Соь) 1(о ' Сш) ( ! а э ) (о! Соь)) '!ч! /;-!"! !! 1 1 = — (Соь оэ) — ((Со; „„оэ) — (1 — а,,) (Со; „оь)). /~-! '-'!.! !'.! Из (45) при 1=й имеем (Соь ох) =О, (Со„„оь) = О, (Со, „оь) =О, Следовательно (Со1, Со„) =0 при 1=0, 1, ..., я — 2, и согласно (47) имеем (и,+„Сп!) =О, 1=0, 1,..., я — 2. Итак, из всех условий (46) остаются лишь два: (Се!-„ее,) = О, (Сом пьп) =О. (48) (49) Далее, подставляя в (49) значение о,, из (29), получим 0 = а!~ (еы Сти) — а!„,т!~, (Сом Сп!) + (1 — аа~~) (эа „Се!).
Последнее слагаемое в этом тождестве равно нулю, так как согласно (45) при (=я, !'=я — 1 нцесм (оа-ь Сои) =-(Сна ь еь) =0 Таким образом, приходим к тождеству а„,((Сеь о,) — т„„(Се,, Со,) ) =О, из которого находим значение параметра т~+,. (Со!, сь) т!,.1 = ",, Со~(' (51) Обратимся теперь к уравнению (50) и исключим из него выражение (Со„„С1,,).
Из уравнения (29) получим 1 1 Со», = — еь, — — !и! — (1 — а!) и!,-,), (52) а!т! следовательно, 1 1 (Сна, Сп!,) = — (Сом пд,) — — [(Сом е!) — (! — а!) (Сом еэ,)). а!т! Согласно (45) имеем (Сед, е!,) = (ем Се!,) = О, (Сны н!,) = (ем Со!,„) = О. Поэтому (Сом Сэьч) = — — (Сом е!), 1 а(Л Подставляя это выражение в (50), получим а!,т!„, (Сп!, гя) + 1 — аа„=О. ссхт~ (Спь „в„,) !25 Подставляя в (48) значение о„., из (29), получим 0 = а~„(ем Се!,) — аа„„т!„(Сом Со!,) + (1 — а!.ы) (и! „Се!,). Согласно (45) при (=я, )=я — 1 имеем (Сп„„и,) =О, так что предыдущее уравнение принимает вид — а,„,т,ч,(С1„Се,,)-1-(1 — а,,) (Со„ь о!,) =О.
(50) Отсюда приходим к рекуррентной формуле для параметров а„,: '! 1 'д«а«(Сд'«-д, д'«) Формулами (51), (53) задаются выражения для итерацпонных параметров в методе сопряжеш!ых градиентов. Скалярные произведения, входящие в эти выражения, вычисляются в процессе пте. раций. Учитывая, что и о«=А"г«, С=АиВ дАи г«=х« — х, Аг«=Ах« — /=гыВ 'г«=а«, получим Со«=А!ддв«, (Си«, о„) =(шв г«) (Сов Сод) =(Ашв и!!). Поэтому окончательно приходим к следующим формулам для определения итерационных параметров в методе сопряженных градиентов: (в« д«) (Ав«, в«) й=0,1, ..., (54) д«,д 1 (в«, д«) а««д —— 1 — —— т«а«(Ав«, а~«,) /д = 1, 2, ..., а, = 1. (55) !)о„~! =)!х„— х// = йР.
(С),'!))х„— х)~„. Поскольку Р„(С) — многочлен степени п от оператора С, удовлетворяющий условию Р.(0) =Е, выполняется оценка [Р„(С)[)~[т„(С)[=, р,= гР," 1 Р" 5 да )+ уэ где ҄— многочлен Чебышева, наименее уклоняющийся от нуля на [Тв Ы, Т (О) =1. Таким образом, для погрешности метода сопряженных градиентов справедлива оценка ~)х„— хИ -!/.~~х„— х!! . где !/,=2р",/(1 + р,'"). 126 7. Оценка погрешности в методе сопряженных градиентов. Выше отмечалось, что в методе сопряженных градиентов точное решение системы уравнений (1) получается за конечное число итераций, равное порядку системы. Если порядок системы велик, то может оказаться полезной и оценка погрешност!и, Эта оценка не хуже, чем в одношаговом итерационном методе с чебышевским набором параметров.
Действительно, из выражения для погрешности (33) получаем ГЛАВА 3 ИНТЕРПОЛИРОВАНИЕ И ПРИБЛИЖЕНИЕ ФУНКЦИЙ В настоящей главе излагаются вычислительные аспекты некоторых задач теории приближения функций. Задача интерполирования состоит в том, чтобы по значениям функции ((х) в нескольких точках отрезка восстановить ее значения в остальных точках этого отрезка. Разумеется, такая задача допускает сколь угодно много решений. Задача интерполирования возникает, например, в том случае, когда известны результаты измерения у„=~(х„) некоторой физической величины ('(х) в точках х„, й=О, 1, ..., и, и требуется определить ее значения в других точках. Интерполирование используется также при сгущении таблиц, когда вычисление значений ((х) трудоемко.
Иногда возникает необходимость приближенной замены или аппроксимации данной функции другими функциямн, которые легче вычислить. В частности, рассматривается задача о наилучшем приближении в нормированном пространстве (!, когда заданную функцию С"е=(( требуется заменить линейной комбинацией сэ заданных элементов нз Н так, чтобы отклонение Ц вЂ” ср)~ было минимальным. Результаты и методы теории интерполирования и приближения функций нашли широкое применение в численном анализе, например при выводе формул численного дифференцирования и интегрирования, при построении сеточных аналогов задач математической физики. $ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
