Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 30
Текст из файла (страница 30)
(4) О а Пусть задана конечная система линейно независимых элементов фьеиН, й=0, 1,..., и. В данном случае задача о наилучшем приближении состоит в том, чтобы для заданного элемента 1еиН найти обобщенный многочлен ф=софо +сьфь+ ° ° + с ф для которого отклонение !1Р— Йн =Ч вЂ” ф, Р— ф)йи (6) является минимальным среди всех обобщенных многочленов вида ф=еьфь+ Сьфь+... + Сафа 2. Сведение к алгебраической задаче о минимуме квадратичного функционала.
Покажем, что сформулированная задача имеет единственное решение. Перепишем равенство (6) в виде ь Ю Ц~ — фей= 'Я сьев(фь, ф~)н — 2 ~ сь(~, фь)н+[7$$й (7) Пусть А= [аь,) — матрица с элементами а„,= (ф„, ф ) „, й, 1=0, 1,..., и (8) 1вт и с, 1 — векторы, с=(с., с„..., с„)*, )=()„)ь...,7„)', где )»= (1, »р») „, »=О, 1,..., и.
Обозначая через л (и, о) = ~ и»о» скалярные произведения векторов и и о, можно записать тожде- ство (7) в виде !/~ — »р~й=(Ас, с) — 2(), с)+Яю Отсюда видно, что задача о нахождении наилучшего приближения в гнльбертовом пространстве Н сводится к минимизации функционала г" (с) = (Ас, с) —.2 (1, с), (10) определенного на множестве вещественных (и+1)-мерных векторов. Отметим основные свойства матрицы А.
Прежде всего, А— симметричная матрица, поскольку а,»=(»рв»р»)я (»р»,ц»»)я=а»» Кроме того, А — положительно определенная матрица. Докажем последнее свойство, исходя из тождества (7). Прн ~=0 из (7) получим »» Я (Ас, с) =~»р)(й = ~ са»рь»0 г=»» и для любого вектора с. Предположим, что (Ау,у) 0 для некоторого у=(у„у„..., у )'. Тогда для обобщенного многочлена ч=у.ф.+у в+".+у.ч.
н имеем 1»р'1й =(Ау,у)=0, следовательно, »р= '5', уг»рг=О. Отсюда в силу линейной независимости элементов»р„»р„..., »р„получим, что у,=у,=...=у„=О. Таким образом, (Ас, с))0 для всех счьО, т. е. А — положительно определенная матрица. Заметим, что положительно определенными являются и матрицы всех угловых миноров А. Следующая теорема сводит проблему минимизации квадратичного функционала (10) к решению некоторой системы линейных алгебраических уравнений. Теорема 1. Пусть А — симметричная положительно определенная матрица и 1 — заданный вектор.
Тогда функционал (10) имеет единственную точку минимума с. Вектор с удовлетворяет системе уравнений Ас = 7'. (11) 158 т. е Р (с + о) = Р (с) + 2 (Ас — 1, о) + (Ао, о). (12) Предположим, что с является решением системы (1!). Тогда из (12) получим Р(с+ о) =Р(с) + (Ао, о). В силу положительной определенности матрицы А отсюда следует неравенство Р(с+о) )Р(с) для любого ненулевого вектора о. Это и означает, что с — точка минимума функционала Р(с).
Докажем необходимость условия (11). Надо показать, что если с — точка минимума функционала (10), то выполнено уравнение (11). Для этого воспользуемся тождеством (12), в котором положим о=Лу, где Л вЂ” действительное число и у — произвольный вектор. Тогда получим Р (с+ Лу) = Р (с) + 2Л (Ас — ~, у) + У (Ау, у).
Рассмотрим выражение в правой части этого тождества как функцию Л и обозначим д (Л) = Лз (Ау, у) + 2Л (Ас — ), у) + Р (с). Поскольку с — точка минимума функционала Р(с), при любых у н Л выполняется неравенство Р(с+Лу) >Р(с), т. е. д(Л) >д(0). Таким образом, Л=О является точкой минимума д(Л) и, следовательно, у'(0) =О. Отсюда получаем, что у'(0) = 2(Ас — ~, у) =0 и в силу произвольности вектора у приходим и выводу, что Ас — 1= =О. Теорема 1 доказана.
3. Следствия. Более подробно систему (11) можно записать в виде ,'," „с~ (<рм ~~)н = (~. ада, й = О, 1, ..., а. (13) Таким образом, элемент наилучшего приближения в пространстве Н имеет вид (5), где коэффициенты с„ lг=О, 1,..., н, отыскиваются 159 Д о к а з а т е л ь с т во. Заметим прежде всего, что система (11) имеет единственное решение, поскольку А — положительно определенная матрица. Остается доказать, что вектор с минимизирует функционал (10) тогда и только тогда, когда он является решением системы (11). Докажем сначала достаточность. Для любых векторов о и с имеем Р (с+ о) = (А (с+ о), с + о) — 2 $ с + о) = =(Ас, с) — 2(1, с)+ 2(Ас, о) — 2(1, о)+ (Ао, о), из системы (13).
Из сказанного выше ясно, что алгоритм построе- ния элемента наилучшего приближения в гильбертовом простран- стве состоит в следующем: 1) вычисление элементов аи —— («р», «р ) н, й, 1=0, 1,..., и, матри- цы А; 2) вычисление правых частей (1, «р»), й=О, 1,..., п; 3) решение системы (13); » 4) вычисление суммы«р= 'Я с»«р». Как правило, каждый из этапов этого алгоритма осуществля- ется приближенно, с помощью численных методов. Например, и случае пространства Ь» необходимо уметь вычислять интегралы ь (~р», ~)ы = ') «р» (х) ) (х) «1х, » что можно сделать, вообще говоря, лишь приближенно.
Оценим теперь отклонение Ц вЂ «»1~„, которое получается в ре- зультате использования наилучшего приближения в гильбертовом пространстве. Докажем сначала, что справедлива Л е м м а 1. Если «р — элемент наилучшего приближения э Н, то (1 — «р, «р)н =О, (14) т. е. погрешность (-«р ортогональна элементу наилучшего прибли- жения. Доказательство.
Из (11) имеем (Ас,с) (1,с). Как по- казано ранее, (Ас, с) =1«р1ю Далее, а «л (~, с) = ~~ с»(1, «1«»)н = ( ), '~~~~ с»«р » ~= (~ «р)н. »=о »=о /и Таким образом, приходим к тождеству («' 'р)н =1фьй, совпадающему с (14). С л ед с т в и е. Если «р — элемент наилучшего приближения в Н, то 1!Р— йй=!УЬ вЂ” 1 р!!й. (15) Доказательство следует из тождества М вЂ” 'рй=)Я вЂ” 2Ь р)н+ЮР и равенства (14). Наиболее часто среднеквадратичные приближения использу ются в том случае, когда система («р»)» ортонормирована, т. с. (р., р) =~ ' «О, 1«-ь1, »60 Тогда система (13) решается в явном виде, с,= (1, сра) „, А=О, 1,..., н, (16) а погрешность приближения определяется формулой и (7 ср(й =(~(й '~~ с»а. (! 7) Числа с„определенные согласно (16), называются коэффициентами Фурье элемента )енН по ортонормированной системе (ср»)» „а обобщенный многочлен а ср= 'Я с»ср» »=а называется многочленом Фурье.
ГЛАВА 4 ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ И ДИФФЕРЕНЦИРОВАНИЕ 5 1. Примеры формул численного интегрирования 1. Введение. В настоящем параграфе рассматриваются способы приближенного вычисления определенных интегралов 1 = ~ 1(х) йх, а основанные на замене интеграла конечной суммой и 1. =;5', с4 (х»), (2) »=а где с,— числовые коэффициенты и х,— точки отрезка (а, Ь), й =О, 1,..., и. Приближенное равенство ь а ~)(х)йх= ',~ с»)(х») и »=а называется квадратурной формулой, а сумма вида (2) — квадратурной суммой. Точки х„называются узлами квадратурной формулы, а числа с,— коэффициентами квадратурной формулы. Разность Ч', = ~ ) (х) ах — '~', с»)'(х») и »=а называется погрешностью квадратурной формульь Погрешность зависит как от расположения узлов, так и от выбора коэффициентов.
Ь А. А. Самарский, А. В. Гулиа 16$ При оценке погрешности в приводимых ниже примерах функция 1(х) предполагается достаточно гладкой. Введем на [а, Ь] равномерную сетку с шагом Ь, т. е. множество точек от«=(хг=а+И,(=0, 1,..., У, Иг(=Ь вЂ” а), и представим интеграл (1) в виде суммы интегралов по частичным отрезкам: ь н хг $ ~ (х) йх = ~ч' ~ ~ (х) Нх. (3) О г=т«; д Для построения формулы численного интегрирования на всем отрезке [а, Ь] достаточно построить квадратурную формулу для интеграла ] 1(х) ах (4) Рис.
о. Геометрический смысл фо, мулы прямоугольников которая называется формулой прямоугольников на частичном отрезке [х, о хт]. Погрешность метода (5) определяется величиной хг фг= ~ 1«(х)йх — )(х у)й, х~ т которую легко оценить с помощью формулы Тейлора. Действительно, запишем фг в виде ~ (у(х) — у(хг и))йх (6) «г т и воспользуемся разложением 1(х) =У" (хг И)+ (х — х~ И) ~'(х. И) + ' И )" (Ьг), 162 «г-т на частичном отрезке [х, „ х,] и воспользоваться свойством (3). 2. Формула прямоугольников. Егх) Заменим интеграл (4) выражением [(х, ь) Ь, где хг ь=х,— 0,5 Ь. Геометрически такая замена означает, что площадь криволи~с' нейной трапеции АВСР заменяется площадью прямоугольника АВС'Р' (см.
рнс. 5). Тогда полу- Ю чнм формулу А Ю 1 л; х ~ хг .х [ гг (х) йх 1 (хг-и) Ь, (5) где ~< — — ~,(х)ен(х, ох,). Тогда из (6) получим «~ 7'" (~~) Их. «~-д Обозначая М,л = шах ~Г'(х) ~, оценим ~, следующим обра- «~1«а-~ «с3 зом: «1 Г (х — х1 И)» «в 1Ф~<М»л ) 11х= — М»л. 2 24 Таким образом, для погрешности формулы прямоугольников на частичном отрезке справедлива оценка «» ~ф1~~ — М, ь 24 (7) т. е. формула имеет погрешность 0(й') при й-з-О.
Заметим, что оценка (7) является неулучшаемой, т. е. существует функция 1(х), для которой (7) выполняется со знаком равенства. Действительно, для 1(х) = (х — х, «)* имеем М,л=2, 1(х, ь) = Ои «1 «в «х 7(х)ах — 1(ху у)й= — = — М«л. !2 24 «1-1 Суммируя равенства (5) по 1 от 1 до У, получим составную формулу прямоугольников ь Я ~~(х)йх= '~ 1(х; м)й. (8) а 1=» Погрешность этой формулы б У Ч'=~~(х)Нх — ',~" ~(х~ и) й » ю-~ равна сумме погрешностей по всем частичным отрезкам, У И «Ф « р=;~ ф =,'Е ~ '","" )" (~') (' Г=~ с=~ „. ~-1 Отсюда, обозначаяМ,= шах ~~"(х) ~, получим «ы1».ь1 (9) т.
е. погрешность формулы прямоугольников на всем отрезке есть величина 0 (й*). 6» 163 В этом случае говорят, что квадратурная формула имеет второй порядок точности. Замечание. Возможны формулы прямоугольников и при ином расположении узлов, например такие формулы: ь М ь М ) )(х)ох= Я ь)(х~ )„) 1(х)их= ~ь', Л)(хг). а г=з а 1=1 Однако из-за нарушения симметрии погрешность таких формул является величиной 0(Н). 3. Формула трапеций. На частичном отрезке эта формула имеет вид 'г (! О) хг-х и получается путем замены подынтегральной функции ((х) интерполяционным многочленом первой степени, построенным по узлам х, „хь т. е. функцией 1 1, г(х) = — ((х — хг,)1(хг) — (х — хг)1(хг,)), и Для оценки погрешности достаточно вспомнить (см. п, 1 $2 гл.
3), что 1(х) — Е, г(х) = ' ' ' 1" (ьг(х)). Отсюда получим хг / (хг,) + у (х;) фг= ~ ~(х)г(х — ' ' ' й= 2 х; х хг х; = ~ Д(х) — Еыг(х))йх= ~ ' ' ' )" (г.;(х))ах 2 «пы и, следовательно, (фг! ~< —" !2 (11) Оценка (11) неулучшаема, так как в ней достигается равенство, например, для 1(х) = (х — х,) '. Составная формула трапеций имеет вид ь и у (хг) + / (хг,) 2 г=х =й(03)о+~а+ ° +Ь- +ОДн), (12) где ),=1(х,), 1=0, 1,..., У, йУ = Ь вЂ” а. 144 Погрешность этой формулы оценивается следующим образом: [Ч")( ~ М„М,= шах [1"."(х)[.
12 хяиьь1 Таким образом, формула трапеций имеет, так же как и форму- ла прямоугольников, второй порядок точности, Ч" = 0(Ь'), но ее по- грешность оценивается величиной в два раза большей (см. (9)). 4. Формула Симпсона. При аппроксимации интеграла (4) заме- ним функцию [(х) параболой, проходящей через точки (хь [(х,)), )=ь — 1, 1 — 0,5, ь, т. е. представим приближенно 1(х) в виде 1(х) - "Еь,(х), хен[х, ь хД, где Е,;(х) — интерполяционный многочлен Лагранжа второй сте- пени, 2 Еьл(х) = — ((х — хь-и) (х — хь) ~ь-~— Ль — 2 (х — хь,) (х — хь) )"..
и + (х — хь) (х — хь «) Ц. (13) Проводя интегрирование, получим жь Еь ь(х)йх= а ф, +45 и+~ь), й=хь — хь,. 6 хь Таким образом, приходим к приближенному равенству «ь ~ (х) йх = — Щ, + 4~; и + [ь), 6 (14) которое называется формулой Симпсона или формулой парабол. На всем отрезке [а, Ь) формула Симпсона имеет вид ь )(х)йх= ',~~ — (1ь,+4~д и+~;)= а 6 й ь 1 л = — Уь+[ьь+2Чь+~ь-ь- ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
