Android-приложение для поиска дешевых авиабилетов: play.google.com
Главная -> Справочник по алгоритмам

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 [25] 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

Точные значения Ht,(x): Но(0,9) =0.523035 и Яо(1,1) = 0,6105787.

Существует ряд специальных видов полинома Р{х) (Ньютона, Эверечта и др.) [4, 5, 7, 18, 24, 30, 38]. Однако следует помнить, что полином Р(х), имеющий P(xi)=y{xi), является всегда единственным. Поэтому при пренебрежении погрешностью вычислений ЭВМ все виды интерполяции должны, давать одинаковый результат. Это характерно для современных ПЭВМ, оперирующих числами с плавающей запятой и имеющих нередко скрытые разряды для повышения точности вычислений.

Интерполяция по методу Эйткена заключается в вычислении у(х) при произвольно расположенных узлах без явного построения интерполяционного полинома. Последнее достигается путем последовательного применения формул линейной интерполяции;

у (x.xt,, х,) =

у {Х, Хп, Хг) =

Xi -Ха

Хг-Хп

у (x,Xo,Xi, Хг) =--

Уп Хп - х

У\ Х-X У(1 Хп-X

Уг Х2-X

1/(х. Хп, Xi) Х-X y(X,Xn.Xi) Х2-Х

Х2 -Х

и т. д. в приведенной ниже программе с М = 2~-6 для ускорения счета интерполяция ведется прямо по приведенным формулам.

Программа 4.5.

iy(1,55)=0,8888683478 (все цифры результата верные).

Интерполяция полиномом Лагранжа при произвольном расположении узлов в общем случае сводится к вычислению y{x) = Ln{x) с помощью интерполяционного полинома,, имеющего вид (рис. 4.2)

, (х-Х)(х-л:2) ... (х-Хп) -" (х„-л;,)(х„-Х2)...(х„-х„) "" (х-Хп)(л:-хе) ... (х-х„) ДХ -Хо)(х1 -Х2) ... (х, -х„)

(х-хо) (х -Xl) (х-x„-i) (х„-Хо) (х„-х,) .. . (x„-Xh-,)

Программа 4.6.

Пример. Используя данные примера к программе 4.5, получим 4/(1,55)=0,888868348.

Интерполяция с одновременным получением коэффициентов полинома

P{x)=anx"+a„ix"~ + ...+a,x + ao

может выполняться с применением интерполяционной формулы Ньютона [4, 24]:

Я„-(х)=41+(х-xi)f(xi; Х2)+

+(х-Х)(х -X2)f(xi; Х2; хзЗ-f (х-xi)(x-Х2).

п- I

... (х-x„ ,)f(xr, Хг; х„) = А,;

где Ае=у\, Ak-f{xu Х2; xt+i) -разделенные разности К-го порядка (К=1, 2,

05 PRINTИНТЕРПОЛЯЦИЯ ТАБЛИЦ С ЧИСЛОМ УЗЛОВ ДО ШЕСТИ 10 INPUT ЧИСЛО УЗЛОВ ДО ШЕСТИ М=М

20 LETB2"=esLETB3=0:LETB4=0sLETB5=e! LETB6=0s LETX3=0!LETX4«=0:LETX5=©

3© INPUT ВВЕДИТЕ XS#V0 X0jV0

40 INPUT ВВЕДИТЕ ХЬVIXI,VI

50 LETBe=V0sl.ETGl=CVl-Ve)*:Xl-X0)5LETBl=Gl

m IF M=2 THEN 210

70 INPUT ВВЕДИТЕ X2,V2XgpV2

80 LETQ2=<V2-V0)(X£-X0)5LETR2=<Q2-G1><X2-X1) 90 LETB2=R2! IF M=3 THEN 210 100 INPUT ВВЕДИТЕ X3,V3X3,y3

110 LET63=«V3-Ve>>tX3-X0)! LETR3=<03-Ql>/<X3-Xi>

129 LETS3=<R3-R2>(X3-X2>:LETB3=S3t IF M=4 THEN 210

130 IHPUT ВВЕДИТЕ X4,V4X4,V4

140 LETG!4=<V4-V0>/i<X4-X3>!LETR4=<a4-Ql)/<X4-Xl> 150 LETS4>=(R4-R2>.<X4-X2)sLETL4=<S4-S3).<X4-X3) 160 IlETB4=L4! IF M=5 THEN 210 170 IHPCIT ВВЕДИТЕ X5,V5 Х5»У5 180 LET05=<V5-y0>(X5-X0>sLETR5=<Q5-Ql><X5-Xl) 190 LETS5"=(R5-R2)<X5-X2)iLETL5=<S5-S3)<X5-X3> 200 LETB5=<L5-L4><X5-X4) 210 IHPUT ВВЕДИТЕ X=X

220 PRINTy=<:<<<B5iti<:X-X4)+B4)«(X-X3)+B3>a(X-X2>+B2>«<X-Xl)*ei>*<X-X0>+B0 230 60T0 2131 END

Пример. Для контроля этой программы проведем интерполяцию гамма-функции Г(х)=1/(х), заданной М = 6 значениями х, и у1 [36].- хо=1,5; 1/0=0,8862269255; х,= = 1,51; i/i =0,886591685; Х2= 1,525; {/2= =0,8872930231; хз=1,54; г/з = 0,8881776586; Х4=1.54; 1/4=0,889639199; Х5=1,59 и (/5 = =0,8924282141. Тогда для х=1,55 получим

3, .;., га-1) и фо=1;

i i k

ф,= П (х-х,)= I Ф/х--; <К=(-1)* П Г,

Ф*-=7 1 (-1)"+Фи+«

т=1 p=sl

ф,= 1; 1=1, 2.....п-1; fe=l, 2, .... i.



С Mat/ало J i

/ BBoBN, J


ввод xfl),

Вывод y(a:)=B(0}



/ Вывод 7 "7 y(a:)=S I

SS+C*BfJ)

D~X-A(J)

Рис. 4.2. Алгоритм иитерполяции полиномом Лагранжа

IB PRINTИНТЕРПОЛЯЦИЯ ПО ЛАГРАНН1У ДЛЯ N+1 УЗЛОВ ге INPUTВВЕДИТЕ H=N:IiIM А<Ы):ШМ В<Н> Зе FOR 1=0 Т8 H:PRINT13.01.ВВЕДИТЕ XI 40 INPUT A<I>5printBBEfiHTE Vl 50 INPUT B<I>:NEXT I

100 IF B=e THEN PRINT!1.9!V<:X>=B<I>:60T0 60

110 LETC=C*<X-A<n)D!NEXT I

120 LETS=S+C*B(J>:NEXT J

130 PRINT! 1.9!V<X>=S!60T0 бв-.EHD



16 PRINTПОСТРОЕНИЕ ИНТЕРПОЛЯЦИОННОГО ПОЛИНОМА НЫвТОНА

2Э PRIHTH ИНТЕРПОЙЯЦИЯ ПРИ ПРОИЗВОЛЬНО РйСПОЯО»ЕИНЫХ УЗЛАХ

5Й INPUT.ЗАДййТЕ ЧИСЛО УЗЛОВ Н=Н«тМ A<H>i.F<H)*X<N>,V<H>

т FOR 1=1 ТО NsPRINt!2.01ВВЕДИТЕ Х1 , Vl

53 1НР1Я X<1)*V<I>8MEXT I«LETA<1)=18LETF<H>=Y<1>

68 FOR I»l TO N-liLETFa>=08NEXT I

70 PC* K«l TO N-J8Fra? l«l TO H-K

m LETV<n«<va+i>-ya»><xa+K)-xa»8№XT i

Se LETR«18IF K/2-INT«K2)<>0 THEN LETR=-1

108 LETP«18F0R J=l TO KsLETP*P«X<J>iNEXT J •

118 LETA<K+1>=R!«P!IF K»l THEN 170

120 FOR L«l TO K8l.ETl;l=0sFOR M=l TO L

130 LETR-ISIF K.2-INT<K.2)<>0 THEN LETR=-1

140 LETS«e«FOR P»l TO K5LeTS=S+R«<l-X<P))"M!HEXT p

159 LETW«M*<-R>!«A<K+1+M-L>»S8HEXT M

Ш LETA<K-L+l>=WLirCXT L

170 FOR J=H to H-K STEP -1

180 L£TF<J>=F<J)+A<J-H+K+l)!i(Y<i>sNEXT JINEXT К

1Э0 PRlHTKOWHUHEHTbl СТЕПЕННОГО МНОГОЧЛЕНА

280 FOR I«l TO H8PRIHT»2.0>AH-I!F1.9!»F(l>sHEXT I

210 INPOTBBE&HTE ЗНАЧЕНИЕ X=X8LETS=F<i>8FOR I«l TO H-1

220 LETS=S!i(X4P<I+l>iNEXT I

230 PRINT!F1.9!V<X>=S8&0T0 2ie8END

Пример. Пусть надо построить интерполяционный полином для янтеграла вероят-

ности у{х) =Ф„(х) = (1/) \ехр {-/)dt,

заданного пятью узлами i/i (2,2) =0,4860966; У2(2,3) =0,4892759; Уз{2А) =0,4918025;

4(2,5) =0,4937903 и 1/5(2.6) =0,4953388. Введя эти значения, найдем: ао=-0,1706447; а, =0,805165666; 02=-0,3712775; аз = =0,07783333333 ищ= -0,0625. Далее можно вычислить у{х) для заданного х (в том числе и в узлах интерполяции).

Экстраполяция - получение значений у[х) прк X, не принадлежащем отрезку [х:о, х„] или [xi, x„+i],- также осуществляется по описанным выше программам, но с существенно большей погрешностью. Для гладких у{х) экстраполяция целесообразна при х, выходящих за указанные пределы не более чем на /г/2.

Обратная интерполяция - процесс нахождения значений х по заданным значениям у. Она может выполняться по любой программе интерполяции с произвольно расположенными узлами. При этом вместо значений Xi вводятся значения yi, а вместо у - значения л.

Многоинтервальная интерполяция заключается в интерполяции у,{х, в ряде частичных интервалов (ограниченных двумя узлами или группой узлов) отдельными полиномами невысокой степени.. Такая интерполяция может применяться при широком общем отрезке [а, Ь], когда обычная интерполяция полиномом высокой степени дает большую погрешность и ведет к большому времени вычислений. Заметим также, что по виду полинома и значениям его коэффициентов трудно судить о виде зависимости у{х).

Многоинтервальная кусочно-линейная интерполяция при равномерном расположении узлов сводится к заданию начального значения хо=а, шага k (расстояния между ухпамн), номера п последнего, узла и (п+!)

ординат I/O, 1/, уп, после чего вычисление у{х) при заданном х выполняется по формулам

i = int((x-a)/ft),

, У{х)=№+(№ +1 -М) {X - т -a)/h.

На примере многоинтервальной кусочно-линейной интерполяции отчетливо видны общие свойства многоинтервальнои интерполяции: степень интерполирующего полинома (в данном случае 1) не зависит от числа узлов; с ростом последнего погрешность интерполяции монотонно стремится к нулю; для любого интервала вычисление у[х) производится по одним и тем же относительно простым (из-за малой степени полинома) формулам, поэтому время вычислений у[х) при заданных х мало; массив i/,- несет наглядную информацию о виде зависимости у(х).

Задание асимптотического поведения у{х) при х<хс,=а н x>b=a-\-nh заключается в линейной экстраполяции, т. е. вычислении у{х) за пределами отрезка [а, 6] по формулам

y[x)=yii-\-{x-a)(yi-yo)/h при х<а, у(х)=уп+(х-Ь){у„-у„-,)/П при х>6.

Такое задание не всегда строго, но позволяет избежать грубых искажений асимптотического поведения экстраполирующей функции у[х) за пределами отрезка [а, Ь], которые нередко наблюдаются при обычной полиномиальной экстраполяции.

Многоинтврвальная квадратичная интерполяция заключается в задании четного числа парных интервалов (п - четное число) с вычислением фс) при заданном х по формулам (хо = а)

i=int((x-a)/2ft)-fl, p=(x-a-ih)

,(.)£(,. ,+(, p)„.+P(P+JJ



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 [25] 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78



0.0108
Яндекс.Метрика