Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 25
Текст из файла (страница 25)
Интерполирование алгебраическими многочленами 1. Интерполяционная формула Лангранжа. Пусть на отрезке ач-'х(Ь заданы точки хь (с=О, 1,..., и (узлы интерполировании), в которых известны значения функции ((х). Задача интерполирования алгеораичеекими многочленами состоит в том, чтобы построить многочлен 1.„(х) = а, + а,х+... + а„х" (1) степени и, значения которого в заданных точках х„, й= О, 1, ..., л, совпадают со значениями функции ((х) в этих точках. Для любой непрерывной функции ("(х) сформулированная задача имеет едннственное решение.
Действительно, для отыскания коэффициентов а„а„..., а„получаем систему линейных уравнений а,+а,х;+а,х,'.+ ... +а„х',!=((х,), с=О, 1, ..., и, (2) определитель которой (определитель Вандермонда 112, с. 33]) отличен от нуля, если среди точек х„с'=О, 1,..., и, нет совпадаюшнх. Многочлен (.„(х), удовлетворяющий условиям (.„(х,) =((хс), (=О, 1, .... и, (3) называется интерлоляционным многочленом для функции ((х), построенным по узлам (хс)0.
127 значений функции 1(х) в узлах интерполирования. Найдем явное выражение для коэффициентов с„(х). Из условий интерполирования (3) получаем а 'Я сь(хД)(хь) =~(х;), 1=0, 1,, и. ь=о Зги соотношения будут выполнены, если на функции с,(х) нало- жить условия О, (~й, 1, 1 = к, 1 = О, 1, ..., а, которые означают, что каждая из функций с„(х), й=О, 1, ..., и, имеет не менее и нулей на 1а, 5). Поскольку 1.„(х) — многочлен степени и, коэффициенты с,(х) естественно искать также в виде многочленов степени и, а именно в виде с~(х) =1~(х — хр) (х — х~) ° .
° (х хд-~) (х х~~~)..(х х ) ° Из условия с,(х,) =1 находим Х," = (хь — х,)(хь — х,) ... (хь — хь,)(хь — хь„) ... (хз — х„). Таким образом, коэффициенты с,(х) ннтерполяционного многочлепа (4) находятся по формулам Д (х — х;1 сь(х) = П "-;) 1~э (5) Часто коэффициенты с„(х) записывают в другом виде. Введем м огочлен ы(х) степсни и+1: ы (х) = (х-- х,) (х — х,)...(х — х,,) (х — х,) (х — х„+,)...(х — х.') (6) и вычислим его производную в точке х,: м'(х,) = (х,— х,)... (х,— х,,) (х,— х„+,)... (х,— х„), Тогда получим, что сь(х) =— и (х) (х — х ) и' (х„) 1га Решение системы (2) можно записать различным образом.
Наиболее употребительна запись интерполяционного многочлена в форме Лагранжа н в форме Ньютона. Интерполяционная формула Лагранжа позволяет представить многочлен (.„(х) в виде линейной комбинации н 1.„(х) =- 'Я сь (х) ~ (хх) э=а Итак, интерполяу(ионный многочлен Лагранжа имеет вид л 2=2 или, более подробно, Т22 (х — х;) Т., (х) = 'Я и 1(хй). (8) 2=.2 ~ 1 (х — х,) (Фх 2.
Интерполяционная формула Ньютона. Эта формула позволя. ет выразить интерполяционный многочлен („(х) через значеннс 1(х) в одном из узлов и через разделенные разности функции 1(х), построенные по узлам х„х„..., х„, Она является разностным аналогом формулы Тейлора У(х) =Р(хй)+(х — хр)Г(х.)+ '" "' Г(хй) + . Сначала приведем необходимые сведения о разделенных разностях. Пусть в узлах х,~(а, Ь), й=О, 1, ..., п, известны значения функции 1(х). Предположим, что среди точек х„, (г=О, 1, ..., и, нет совпадающих. Разделенными разностями первого порядка называются отношения 1(.,) — 1(;) 1(хих()= ', (,1'=0,1, ..., и, (Ф1.
х( — х, Будем рассматривать разделенные разности, составленные по соседним узлам, т. е. выражения )(хй, х,), 1(х„хй), ..., 1(х„„х„). По этим разделенным разностям первого порядка можно построить разделенные разности второго порядка: 1(х„х,) — 1(хй, хд ('(х„х„х,) = Х2 — Хо 1(22 12) /(х1. 22) ) (х1, х„х,) = Хй — Х, /(хх 1 хх) ~(х 2 х 1) ~(хл-й, хл-д, хл)— ХП Хй 2 Аналогично определяются разделенные разности более высокого порядка. Например, если известны разности я-го порядка 1(хн Ху+1, ..., Х122), 1(х12.1, Хуег, ° ° ., Х11221), то разделенная разность (я+!)-го порядка определяется как 1(хн х;„, ..., хмй, х„й.„) = l (х' х 12 х' 2 1) 1(х> х' 1 хг22) х;,А „— х( 5 А. А.
Сйчйрсхйй, А. В. Гулни При вычислении разделенных разностей принято записывать их в виде таблицы Г (хо) хо Г(хо, хй / (хо, х„хо) ! (х,! х, Г" (х„х,! ~ (х„хо... х„) ! (х,! хо 1(х„„х„, х„) ! (х„„х„) )(х„) хо Разделенная разность л-го порядка следуюпгим образом выражается через значения функции ! (х) в узлах: тоо о( !'(х;, х;„„..., хыо) = '~" '=' П(,—,) ойдо (9) Эту формулу можио доказать методом индукции. Нам потребуется частный случай формулы (9): ! (х,! )(х„хо ..., хо) =",„' ( ! (х; — х~! С =-а.
оФо +~ (х,. — хо) (х; — х,) (х; — х; ) (х; — х; ) (х; — х„! о=а Покажем, что многочлен Р„(х) совпадает с многочленом Лагранжа (8), Рассмотрим наряду с Е„(х) миогочлены Е„(х) =~(х,), !30 Интер)голяционным многочленом Ньютона называется много- член Р„(х) = = ) (хо) + (х — х,) ) (х„ х,) + (х — х,) (х — х,) ( (х„ х„ х,) + ... ... + (х — х,) (х — хо) ... (х — х„,) ) (х„х„..., х„). ( ! ! ) Е,(х), ..., 1.„,(х) и представим 1.„(х) в виде Е„(х) = 1., (х) + '~~~ (Е! (х) — 1.!, (х)).
(! 2) Из условий интерполяции (3) получаем, что Е,,(х,) =Е.,(х„) =~(х,) при а=О, 1, ..., !' — 1 и !'=1, 2, ..., п. Следовательно, разность Ь,(х) — А,,(х) представляет собой алгебраический многочлен степени 1, который обращается в нуль в точках х„х„..., х, „т. е. Е,;(х) — Х.;,(х) =А;(х — х,)(х — х,)...(х — х,,), (13) где А, — числовой коэффициент. Этот коэффициент нзходится из условия У,(х,) †,,(х,) =А;(х, — х,)(х; — х,)...(х, — х~,), откуда, учитывая условие Ь;(х;) =~(х,), получаем А ! -» ! !( ~) — ь!»(»!) (14) (» — х»)...
!»! — х ) Подставим в (14) вместо слагаемого Ь,,(х,) его значение, вычисленное согласно (8), т. е. Е!, (х!) = (х~ — »0) (х! — »>) ... (»~ — х» ,) (х! — хы,) ... (»т — к! ,) = ~ч ', г (х») (»ь — »0) (»» — »,) ... !»» — х» )(»» — х» ,! ... (»» — »~,) х. ) ! !»»! Сопоставляя это выражение с (!0), видим, что А, совпадает с разделенной разностью 1-го порядка: А,=1(х„х„..., х;).
Отсюда и из (12), (13) приходим к интерполяционной формуле Ньютона У.,(х) = = ! (х,) + (х — х,) ! (х„х,) + (х — х„) (х — х,) ! (х„х„х,) +... ... + (х — х,)(х — х,)... (х — х,,))(х„х,, ..., х„), (15) 5* пы Тогда получим ! !»г! (х- — »0) ...(».— I с-1 р(» ! Х Х(,,„) ! =Х ь !», — ха! (хь — »~) ...(»» — »» ,! (»» — »ь ,)...(»» — х- ) (»» — »ь )!»,— х» ! ... (»» — ».
)!»,— »! Подчеркнем еще раз, что формулы (а) и (15) представляют собой различную запись одного и того же многочлена а„+ а,л + а,хз+... + а„х", удовлетворяющего условиям интерполяции (2). Интерпаляционную формулу Ньютона удобнее применять в том случае, когда интерполпруется одна и та же функция )(х), но число узлов интерполяции постепенно увеличивается. Если узлы интерполяции фиксированы и нптерполируется не одна, а несколько функций, то удобнее пользоваться формулой Лагранжа, 3 а м е ч а н и е. При выводе формулы (16) не предполагалось, что узлы хь хь ..., х„расположены и какоч-то определенном порядке. Поэтому роль точки х, а формуле (16) может играть любая из точек хм х„..., х„.
Соотаетстиуюшее множество интерполяпионных формул можно получить из (161 гере- нумераций уэлоа. Например, тот же самый многочлен Е„(х) можно предстаиить и инде 1.„(х) = 1(хп) и- (г — хп) 1(ххи х„) + — (х — хи) (х — х„,) 1(х„, хп а хп,) -1- ... ... +(х — хи)(х — х„,)... (х — хйг(х„, хп „..., л;,). (16) Если хя(х,я.хз<... <х„, то (16) называется формулой интерполирования вперед, а (!61 — формулой интерполирования назад $ 2. Погрешность интерполирования 1.
Остаточный член интерполяцианной формулы. Заменяя функцию!1(х) интерполяционным мпогочленам 1.„(х), мы допускаем погрешность г„(х) =1(х) -1.„(х), которая называется погрешностью интерполирования илн, чта та же самое, остаточным членом интерполяуионнай формулы. Ясно, что в узлах интерполирования эта погрешность равна нулю. Оценим погрешность в любой точке хе=[а, Ь).
Для этого рассмотрим вспамогательнуча функцию ь (5) =1(5) — 1.„(5) — Кь> (5), (1) где зен(а, Ь), К вЂ” постоянная и ю(5) = (5 — х,) (5 — х,)... (5 — л„). (2) Пусть требуется оценить г„(х) в заданной точке х~(а, Ь], не являющейся узлом интерполирования. Выберем постоянную К из условия д(х) =О. Для этого достаточно положить К= 1(х) — 1.и (х) ы (х) Предположим, что 1(5) имеет и+1 непрерывную производную на отрезке а (5 .Ь. Функция у(5) имеет не менее и+2 нулей на этом отрезке, а именно в точках х, х„, й=б, 1, ..., л.
Поэтому производная у'(5) имеет не менее чем и+! нулей на (а, Ь), ди(5)— 132 не менее и нулей н т. д., функция д'"оо(в) по крайней мере один раз обращается в нуль на [а, Ь). Тем самым существует точка 5~[а, Ез!, в которой й'"+о(й) =О. Поскольку ошоп (з) — [(оо-и (з) (п 1 1) 1Е( получаем ы (к) Таким образом доказано, что погрешность интерполирования можно представить в виде Еш'и ($) Е (х) — Е.„(х) = в (х), (3) (и+ 1)! еде фа=[а, Ь[ и в(х) — многочлен, определенный согласно (2), Отсюда следует оценка [Е (х) — Е.„(х) [~~ "" [в (х) [, (4) где М„., = зпр [Е"'+"(х) [. В частности, если Е(х) — алгебрапче.=Го.ь1 ский многочлен степени п, то интерполирование, проведенное по любым точкам х„х„..., х„, осуществляется точно, т.
с. Е.„(х) =— = — Е(х). 3 а меч ание. Наряду с иитерполировзязем применяют и зкстрплолиро. ванпс, т. е. вычисление значений функции Е(к) в тачках хои[а, Ь[ по приближен- ной формуле Е(к) жь (к), где ь„(к) — иятерполяцяаяяый мзагачлен. Одиака погрешность экстрзполираззяия обычно акззызается сушостяензо большей, чем погрешность иятсрполяроязяяя. К этому выводу можио прийти, рассматривая поведение мнагочлеяа в(к) внутри и зие отрезка [а, Ь), Поскольку мпогочлены Лагранжа и Ньютона отличаются толь- ко формой записи, представление погрешности в виде (3) справед- ливо как для формулы Лагранжа, так и для формулы Ньютона.
Однако погрешность интерполирования можно представить в в дру- гом виде. Для этого рассмотрим разделенную разность Е(х, х„х„..., х„)— Е (к) и + (к — ко) (к — «о) ° ° (к — «„) + Е(ко) [ [ Е( л) («о — к) (ко — кз) ... (ко — ко) («„— К) (к„— «о) ... (к„— клоп) имеющую порядок и+1. Отсюда найдем Е (х) Е (хо) (« — к,) (к — ко) ... (к — «„) " +".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
