Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 24
Текст из файла (страница 24)
Из уравнения (29) получим 1 ! Со», = — о»,— — !о» вЂ” (1 — а») о» ) (52) т» а»т» следовательно, (Со», Соь.,) = — (Сом о»,) — — 1(Со», о») — (1 — а») (Со», оь.»)). 1 ! т» а»т» Согласно (45) имеем (Со», оь.,) =(оы Со»») =О, (Сом о»-») =(о», Со»-) =О.
Поэтому 1 (Сом Со»,) = — — (Со»„о»), "»т» Подставляя это выражение в (50), получим а»»т»„„(Со», о ) +1 ар„,=О. а»т» (Со»,, о»,) 126 Следовательно (Соь Со„) =0 при 1=0, 1, ..., !с — 2, и согласно (47) имеем (о„+„Со,)=0, 1=0, 1,..., (с — 2. Итак, из всех условий (46) остаются лишь два: (Со» ь о»+») =О, (Со», о»ы) = О. Подставляя в (48) значение о»», из (29), получим 0 = а»„(оы Со»,) — а»+,т»», (Со», Со»,) + (1 — а»+,) (о»-ь Со»,). Согласно (45) при (=)с, )'=я — 1 имеем (Со, „о,) =О, так что пре- дыдущее уравнение принимает вид — а»,, с».„(Со„, Со,,)+ (1 — а»»,) (Со„„о„,) =О.
(50) Далее, подставляя в (49) значение о„+, из (29), получим 0 = и»ы (о», Со») — и»ыт»„(Со», Со») + (1 — аь.,) (о» „Со»). Последнее слагаемое в этом тождестве равно нулю, так как соглас- но (45) при (=К!=л — 1 имеем (о„ь Со,) = (Со„„о,) = О. Таким образом, приходим к тождеству и»+,[(Со„, о„) — т„,(Со„, Со»)1=0, Отсюда приходим к рекуррентной формуле для параметров а„,: 1 -1 тз аэ (Сээ, оэ,) Формулами (51), (53) задаются выражения для итерационных параметров в методе сопряженных градиентов.
Скалярные произ. ведения, входящие в эти выражения, вычисляются в процессе итераций. Учитывая, что С=АНВ тА'~, гэ=хэ — х, Аг~ =Ахэ — (=гы В ггэ=иб, оэ=А 'гы получим Со„=Ап'гвь (Со„о„) = (гв„г,), (Свм Со,) = (Аиь„гв,). Поэтому окончательно приходим к следующим формулам для определения итерационных параметров в методе сопряженных градиентов: (мм гд) ть.1 = (Авм мь) (54) й= О, 1, й = 1, 2, ..., а, = 1. (55) 7. Оценка погрешности в методе сопряженных градиентов. Выше отмечалось, что в методе сопряженных градиентов точное решение системы уравнений (1) получается за конечное число итераций, равное порядку системы.
Если порядок системы велик, то может оказаться полезной и оценка погрешности. Эта оценка не хуже, чем в одношаговом итерационном методе с чебышевским набором параметров. Действительно, из выражения для погрешности (33) получаем (( о„ (( = ((х„ — х (! ( ~( Р„ (С) (( (( х, — х (! . Поскольку Р„ (С) — м ногочлен степени и от оператора С, удовлетворяющий условию Р. (0)=Е, выполняется оценка ((Р„(С))(~((Т„(С))(= ', р,= "б, 5= — ' 2р" ) уй (+ р,'" (+ Уэ 2 л((1 1 рзл) 12б где ҄— многочлен Чебышева, наименее уклоняющийся от нуля на [Т Т21 Т (О) 1 Таким образом, для погрешности метода сопряженных градиентов справедлива оценка ((х„— х(( (д„((х,— х1(„, ГЛАВА 3 ИНТЕРПОЛИРОВАНИЕ И ПРИБЛИЖЕНИЕ ФУНКЦИИ В настоящей главе излагаются вычислительные аспекты некоторых задач теории приближения функций.
Задача интерполирования состоит в том, чтобы по значениям функции !(х) в нескольких точках отрезка восстановить ее значения в остальных точках этого отрезка. Разумеется, такая задача допускает сколь угодно много решений. Задача интерполирования возникает, например, в том случае, когда известны результаты измерения у„=)(х„) некоторой физической величины !(х) в точках х„, я=О, 1, ..., и, и требуется определить ее значения в других точках.
Интерполирование используется также при сгущении таблиц, когда вычлсление значений Г(х) трудоемко. Иногда возникает необходимость приближенной замены или аппроксимации данной функции другими функциями, которые легче вычислить. В частности, рассматривается задача о наилучшем приближении в нормированном пространстве Н, когда заданную функцию !епН требуется заменить линейной комбинацией ~Р заданных элементов из Н так, чтобы отклонение Ц вЂ” Ц было минимальным. Результаты и методы теории интерполирования и приближения функций нашли широкое применение в численном анализе, например при выводе формул численного дифференцирования и интегрирования, при построении сеточных аналогов задач математической физики.
й 1. Интерполирование алгебраическими многочленами 1. Интерполяционная формула Лангранжа. Пусть на отрезке а(х(Ь заданы точки х„, юг=О, 1, ..., и (узлы интерполирования), в которых известны значения функции Г(х). Задача интерполирования алгебраическими многочленами состоит в том, чтобы построить многочлен Ь,(х) =а,+а,х+...+а„х" степени и, значения которого в заданных точках х„, А= О, 1,..., и, совпадают со значениями функции !(х) в этих точках. Для любой непрерывной функции !" (х) сформулированная задача имеет единственное решение.
Действительно, для отыскания коэффициентов а„а„..., а„получаем систему линейных уравнений а,+а,х;+а,хг+ ... +а„х,"=!(х;), 1= О, 1, ..., п, (2) определитель которой (определитель Вандермонда !!2, с. 33)) отличен от нуля, если среди точек хь 1=0, 1,..., и, нет совпадающих. Многочлен г.„(х), удовлетворяющий условиям Е„(х;)=!'(х,), 1=0, 1, ..., и, (3) называется интерполяционным многочленом для функции !(х), построенным по узлам (х;),". г27 Решение системы (2) можно записать различным образом.
Наиболее употребительна запись интерполяционного многочлена в форме Лагранжа и в форме Ньютона. Интерполяционная формула Лагранжа позволяет представить многочлен Е„(х) в виде линейной комбинации л Е.л(х) =~~ ск(х)('(хл) (4) к=о значений функции 1(х) в узлах интерполирования. Найдем явное выражение для коэффициентов с„(х). Из условий интерполирования (3) получаем л 'Я ск (х1) ~ (хк) = ~ (хс), Е = О, 1., и. Э ти соотношения будут выполнены, если на функции с„(х) наложить условия О, (мй, 1, 1 = й, 1 = О, 1, ..., и, которые означают, что каждая из функциИ с„(х), й=О, 1, ..., и, имеет не менее и нулей на (а, Ь).
Поскольку Е„(х) — многочлен степени и, коэффициенты с„(х) естественно искать также в виде многочленов степени и, а именно в виде сл(х) Хл(х ха) (х х~)...(х хл-~) (х хл+~),(х х ). Из условия с„(х,) =1 находим Хк'=(хк — х,)(хк — х,) ... (хл — хл,)(хл — хк,,) ...
(хл — хл). Таким образом, коэффициенты с„(х) интерполяционного много- члена (4) находятся по формулам П (к — к.) ск(х)= ~ П (кь — к;) 1+к Часто коэффициенты с,(х) записывают в другом виде. Введем мпогочлен в(х) степени и+1: м (х) = (х — х,)(х — х,)...(х — х,,) (х — х„)(х — х„„.,)...(х — х„) (6) и вычислим его производную в точке х,: м (хл) (хл хо)... (хл хк-~) (хл хА+1), (хл хл) . Тогда получим, что ск (х) = (к — кк) лг (кл) 128 Итак, интерполяционный многочлен Лагранжа имеет вид л (х — кх) ьу (хк) или, более подробно, Ц (х — х() ~,,(х) =Я, '! ~(х„). (8) ь=а)1 (х„— к,) !Фк 2.
Интерполяционная формула Ньютона. Эта формула позволяет выразить интерполяционный многочлен („(х) через значение )(х) в одном из узлов и через разделенные разности функции )(х), построенные по узлам х„х„..., х„. Она является разностным аналогом формулы Тейлора )'(х)=~(хь)+(х — хь)('(хь)+ "' )" (х,) + ... Сначала приведем необходимые сведения о разделенных разностях.
Пусть в узлах хье:-[а, Ь), я=О, 1, ..., и, известны значения функции )'(х). Предположим, что среди точек х„, я=О, 1, ... „и, нет совпадающих. Разделенными разностями первого порядка называются отношения Г (х;) — / (х!) ~(хох()= ', 1,/=О, 1, ..., и, (чь). х( — к, Будем рассматривать разделенные разности, составленные по соседним узлам, т. е. выражения 1(х„х!), ((х„х,), ..., 1(х„„х„). По этим разделенным разностям первого порядка можно поглронть разделенные разности второго порядка: Г(к! к!) — Г (ко к!) «! — хо ) (ху, х!) — ((ку, «Д ) (х„х„х,) = кз — х! 1 (к„„к„) — 1 (х„„к„,) у(х к, х„„х„)— Аналогично определяются разделенные разности более высокого порядка. Например, если известны разности я-го порядка ) (Хь ху!.!! ° хых) 1(~у+! «!+2' ' ' ' ! ~у-!к+!) то разделенная разность ()с+1) -го порядка определяется как 1(х!э х(„, ..., х;,м х(,к,!) = Г'(хи о к;„ , ..., х)лкх,) — ( (кр х.+ , ..., к)+к) х! М!! к/ 5 А.
А. самарскиА, А. в. Гуккн Г29 При вычислении разделенных разностей принято записывать их в виде таблицы хо ((хо, кь хо) х, / (хо, к„ ... хо) Г (х , х , х„) кл Разделенная разность Ьго порядка следующим образом выражается через значения функции ((х) в узлах: ( (х;) ((хь х;„„..., х),о) = '~~,, (9) Г( (хо — хо) !мо Эту формулу можно доказать методом индукции. Нам потребуется частный случай формулы (9): г' (к;) ) (», х,, х.) = 5,' о=о П(-;) М=оо 1~о ((О) г (х;) (х; — ко) (к; — хо) °" (х; — к; ) (к; — «го ) ° ° (х; — хь) Интерполяционньоло многочленом Ньютона называется много- член Р„(х) = = ~ (х,) + (х — х,) ~ (х„х,) + (х — х,) (х — хо) 1(х„х„х,) + ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
