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

Выражение для у{х) есть интерполяционная формула Лаграцжа для трех ординат, применяемая для каждого частичного интервала.

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

у{х)=уо+{х-а)(41 -1/2 -3f/o)/2/z при х-<а, у{х)==у„+(х - Ь) (Зг/„ -f 1/„ 2 - 4t/„-., )/2/г при xfc.

Сплайн-интврполяция есть специальный вид многоинтервальной интерполяции, при котором интерполируюш.ий полином обеспечивает не только равенство у{х) значениям yi в узлах, но и непрерывность заданного числа первых производных на границах частичных интервалов. В обш.ем случае сплайн задается глобальным способом, т. е. с использованием всех узлов при любом их расположении (см. § П5.П Приложения 5). Ниже рассматривается задание кубичекого сплайна локальным способом, которое реализуется сравнительно просто и требует суш.е-ственно меньшего объема памяти ЭВМ, чем при глобальном способе задания.

Кубический сплайн, заданный локально,- это интерполируюш.ая функция в виде полинома третьей степени, вычисляемая по формулам (6),

1 = Ы{{х-а)/к1

(х...-л:)-(2(л:-х.)+

(x-x,f(2(x,+ ,-x)+/z) ft-

{x,+ t-xf(x - Xi)

(Х -(х- -Х,-ц)

--р-

где nii и mi+1 - первые производные у(х). Производные локального сплайна могут задаваться двумя способами.

Способ 1. Производные т, и т,+ , вычисляются с помощью формул численного дифференцирования по трем точкам:

т,=((/, +i - i/, i)/2ft для i = l, 2, .... п-1, то=(4f/, -1/2 - 3f/o)/2A для i"=О,

m„=(3f/„+f/„ 2-4i/„ i)/2/i для i = n.

Способ удобен тем, что для задания сплайна требуется вводить лишь ординаты I/, (значения mi вычисляются программой). Для уменьшения времени многократных вычислений у(х) желательно предварительно вычислить массив т,- и хранить его в памяти ЭВМ.

Способ 2. Значения mi (вычисленные отдельно или полученные из графика как наклоны его в узлах) задаются непосредственно в виде массива т,-.

Задание асимптотического поведения у{х) за пределами отрезка [а, Ь] осуществляется так же, как и при многоинтервальной квадратичной интерполяции. У рассмотренного локально заданного сплайна непрерывны лишь нулевая и первая производные (у глобально заданных кубических сплайнов не--прерывна также и вторая производная). Кусочно-линейная и многоинтервальная квадратичная интерполяция рассматриваются как дефектные сплайны, у которых обеспечивается непрерывность только нулевой производной. Все эти виды интерполяции реализуются программой 4.8. После задания нужного вида интерполяции вычисления у{х) выполняются подпрограммами: кусочно-линейная интерполяция - экстраполяция со строки 1000, квадратичная - со строки 2000 и кубическая со строки 3000. Эти подпрограммы могут использоваться для задания (аппроксимации) нелинейных зависимостей у{х) в дополнительных . программах, вписываемых пользователем в программу 4.8.

Программа 4.8.

le printаппроксимация?интерполяция и экстраполяция 20 printсплайнами при локальном их задании Зв шритвведите начальное значение К0=а 40 inputвведите ШАГ н=н

50 ШРиТвведите номер последнего узла N=H!eim V<N> 60 FOR 1=0 то Nsprint 13>e!введите Vl 70 input V<I>!HEXT I

80 ШРиТВВЕДИТЕ порядок, ъг am з полиномаp •.

Э0 IF Р=2 THEN 130

100 IF p=3 THEN 150

lie 1нрутвведите X=X!60sub 1000

120 pr1nt!F1.9!V<X>=W!&0T0 110

130 inputвведите X=X!60sub 2069

140 priht!F1.9!V<X)=b.l!&0tq 130

150 prшtзaдaйte код O-DV-DX HE задаетсяsDIM M<N> 160 inputзадайте код l-DSVDX задаетсяК 170 if к=0 THEN 200

18Й for 1=0 TO H!priht!3.0«введите DV-txI

190 input M<I>".NEXT I!goto 230

208 letm<0)=<4*V<l>-Vf2>-3*V<0>)-2-H

210 LETM<N>=<3iiiVtN>+V«:H-2>-4stV<N~t>>-.-H

220 for 1=1 TO n-liLETM<n=<V<I+l>-Va~l)>-2-H!hext I

230 1НРитвведите х=х5605ув ЗвВО



24e PRIHT!Fi.9!V<X>=Ut60T0 238

leee REMВЫЧИСЛЕНИЕ V<X>=W ПРИ СТЕПЕНИ ПОЛИНОМА 1

1816 IF X<=A THEH 1050

1820 LETB=A+H*NiIF X>=B THEH 1060

1830 LETI=IHT< <X-A>-H)tLETU=V< I >

1048 LETW=U+<V<I+l>-V<I>)!ii<X-I«H-A>HtRETURN

1050 LETU=V<0>+<X~A>«<V<1>-V<0>>-HSRETURH

1068 LETU«V<N>+<X-B>«<V<N)-V<N-l)3-HtRETURH

2008 РЕМВЬНИСЛЕНИЕ V<X>=W ПРИ СТЕПЕНИ ПОЛИНОМА 2

2010 IF X<=A THEN 2060

2920 LETB=A+M«H!IF X>=B THEN 2076

2030 LETI=l+2«INT<<X-A>-2-H>!LETP=<X-A~I«H>rH

2040 LETU=P«<P-l>«V<I-l)-2+<Hf>!iiP)!iiV<I>

2058 LETU=U+P»i<P+l >i«V< I+l V2!RETURN

2860 LETU=V<0>+<X-A>«<4»V<l>-V<2>-3«V<8»2-HrRETURH

2070 LETW=V<H>+<X-B>«<3«V<N>+V<N-2>4«Y<N-1>)2H!RETURH

3000 REMВЫЧИСЛЕНИЕ V<X>=W ПРИ СТЕПЕНИ ПОЛИНОМА 3

3010 IF X<=A THEN 3080

3028 LETB=A+Hi«Ht IF X>=B THEN 3890

3038 LETI=INT<<X-A)/H>:LETB=A+H«I

3040 LETC=B+H!LETD=X-CtLETE=X-B

3858 LETW=D«D«<E+E+H)«V< I >+E!i!E«<H-I)-I»«V<I+1 >

3860 LETW=W-H+Di»D)«E»M<I)

3070 LETW=<W+E«E«D«M< 1+1 > >-H-Ht RETURN

3080 LETU=V<0>+<X-A)«M<8>!RETURN

3098 LETW*=V<N>+<X-B>«M<N>!RETURN:END

Пример. Провести интерполяцию (an- влияние на ход у{х) по всей кривой, что

проксимацию) /V-образиой вольт-ампёрной качественно неверно описывает физические

характеристики туннельного диода, заданной явления, лежащие в основе нелинейности

в виде интерполируемой функции.

х,и, В

(у, = 1, мА

Задаем ло = 0. /г = 0,1 и й = 8. Введя ординаты у. для кусочно-линейной интерполяции - экстраполяции, будем иметь (/(0,1)---10, (/(-0,1)==-10, {/(0,05)=5, j/(0,8)= = 13 и т. д. Для многоинтервальнои квадратичной интерполяции - экстраполяции :0,1)=10, {/(-0,1)=-18, 1/(0,25)=2,8125, Т)=21 и т. д. Для кубической сплайн-интерполяции н экстраполяции i/(0,l)=10; {/(0,25) = 2.65625, j/(-0,l)=-18, (/(1)= =21 и т. д.

Из этого примера видно, что для задания сплайна, аппроксимирующего некоторую зависимость ух,), достаточно задать лишь определенное число ее ординат f/,. Массив значений t/,- сохраняется в памяти ЭВМ и в любой момент может быть использован для восстановления вида аппроксимируемой зависимости, например, для вывода по точкам ее графика.

Достоинством локально заданных сплайнов является описание свойств зависимости yi (Xi) иа каждом частичном интервале независимо от ее свойств на других интервалах. Подобное поведение нередко встречается R.3 практике, например, восходя-ш.ие туннельная и диффузионная ветви Л-образной вольт-амперной характеристики туннельного диода обусловлены совершенно различными физическими явлениями. Отметим, что у обычной полиномиальной аппроксимации этого свойства нет и изменение у[х) вблизи какого-либо узла оказывает

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

Интерполяция функции двух переменных X к у по трем точкам (см. рис. 4.3, а) выполняется по формулам

fix, y) = (l-p - q)foo + pfto + qfm,

где p=(x-xa)lh и д-(у-уо)/1. Здесь А - шаг изменения х, а I - шаг изменения у. Несколько лучшие результаты дает интерполяция по четырем точкам (рис. 4.3, б):

fix, {/)=(1 -р)(.1-д) foo + p(! -9) /,0 + + Р). f 01+pqf п.

Ошибка при этом пропорциональна Н..

При интерполяции по шести точкам (рис. 4,3, в)

p{p - 2q + l)

-- -f„-pgf

погрешность пропорциональна h.



(0,1)

(o,i)*(i,i)

(0,1)»(1,1)

(1,0)

(0,0)

(1,0)

(0,0)

(1,0)

(-1,0) 0

(0-1)

а о о

Рис. 4.3. Расположение равноотстоящих узлов при интерполяции функции, двух переменных по 3(a),

4(6) и 7(e) точкам

Программа 4.9.

18 PRIИТИНТЕРПОЛЯЦИЯ ФУНКЦИИ ДВУХ ПЕРЕМЕННЫХ .

SO PR1NTF<X/v) ПО 3,4 и 6 ТОЧКАМ

Зе INPUT-ЗАДАЙТЕ ШАГ X Н=Н

40 INPUTЗАДАЙТЕ ШАГ Y L=L

50 INPUTЗАДАЙТЕ ЧИСЛО ТОЧЕК 3,4 ИЛИ 6 N=N

60 IF N=4 THEN 90

70 IF N=6 THEN 100

80 ШРиТВВЕДИТЕ F08,Fle,F01 А,В,С!60Т0 НО

90 1ИРиТЕВЕДИТЕ F00,Fiei,F01,Fll А,В,С,г1!60Т0 110

100 INPUTBBEAHTE F0-1,F-10,F00,FIO,FObFl 1 A,B,C,B,E,I

110 INPUTВВЕДИТЕ ЗНАЧЕНИЯ X0,V0 X0,V0

1S0 INPUTBBEAHTE X,v X,v

130 LETP=<X~X0)-H!LETQ=(:v-V0>-L:IF N=4 THEN 160

140 IF N=6 THEN 170

150 LETF=a-P-Q)*A+P*B+D*C!60T0 19©

160 LETF= a-P)* a-Q)жа+Р* <1-Q)*B+Q* fl-P)жС+РжОжЩ:60T0 190 170 LETF=Q*<:e-l>*AS+P*<P-l)*B>S+<l+P*6-P»!P~Q!kq>*C 180 LETF=F+P*<P-S*Q+l>*riS+e«i;Q-2s«P+l)!ke>S+P*Q«I 190 PRINTF<X,V)=F!60T0 ISOsEND

Контрольные примеры, поляция функции последействия

Интер-

заданной таблично.

1. Интерполяция по трем точкам. Задано: п = 3; А=0,3; 1=0.1; х„ = 0,4; уо = 0; /оо=2,5; foi =2,456 и f,o= 1,429. Получим f(0,7; 0,05)= = 1,407; Я0,4; 0,05)=2,478 и т. д.

2. Интерполяция по четырем точкам. Задано: п=4, /г = 0,3; Z=0,1; хо = 0,4; f/o = 0; foo = 2,5; f,o=l,429; f6i=2,456 и Ь, = 1,4. Получим f(0,7; 0,05)= 1,4145; f(0,5; 0,08) = = 2,1118 и т. д.

3. Интерполяция по щести точкам. Задано: п=6, ft=0,3; /=0,1; х-о=0,7; t/o = 0,05; fo-i = 1,429; / ,„ = 2,487; foo= 1,419, /,о = = 0,995; foi = l,4; ,=0,981. Получим f(0,4; 0)=2,502; f(0,5; 0,03) = 2,065857778.

Многоинтервалышя квадратичная интерполяция - аппроксимация функции двух переменных может использоваться, когда необходимо интерполировать или аппроксимировать таблично или графически заданные функции двух переменных. Такая интерполяция - аппроксимация удобна, например, для вычисления токов по заданным напряжениям у приборов с графически определенным семейством вольт-амперных характеристик (биполярных и полевых транзисто-

ров, тиристоров и т. д.). Алгоритм интерполяции - аппроксимации следующий.

1. Функция f{x, у) задается в виде матрицы F{I, J), где / - номер строки таблицы (или кривой графика), / - номер столбца (или точки на кривой). При нумерации / и / с О имеем 0</<Л-1 и 0</<М -1, где N - число строк (кривых), М - число столбцов (точек на каждой кривой). Кроме того, задаются прираш.ения (щаги) Ax = /f= =const и Af/ = Z=const и начальные значения хп = а и 1/0 = fc.

2. Для каждого значения х к у вычисляются :

/ = int ({x~a)/h), если i=0, то берем /= 1, I=int{{y - b)/l), если 1=0, то берем 1=1, p = (x-a~Jh), Q={y-b-l[).

3. Для каждого / = /-1, /, /+1 (в правой части / соответствует вычисленному в п. 2) вычисляется значение

Z = P(P-!)f(/, /-l)/2-f(!-PV(/, J) + -ЬР(Р+!) /=(/,/-fI)/2. Эти значения присваиваются переменным С, D и Е. Таким образом, обеспечивается тройная квадратичная интерполяция по переменной х.

4. Выполняется квадратичная интерполяция по переменной у:

Z = Q[Q-l)C/2+(,l-Q)D + Q{Q +1) Е/2. Считаем F(x, y)=Z.



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.013
Яндекс.Метрика