2. Квадратичная интерполяция.

( x - x_i2)(x - x_i3) ( x - x_i1)(x - x_i3) ( x - x_i1)(x - x_i2)

у= y_i1 ------------------- + y_i2 ------------------- + y_i3 -------------------;

(x_i1 - x_i2)(x_i1 - x_i3) ( x_i2 - x_i1)(x_i2 - x_i3) ( x_i3 - x_i1)(x_i3 - x_i2)

где

x_i1, x_i2, x_i3 - ближайшие к х узловые точки ( рис. 15 ).

Квадратичная интерполяция осуществляется по трем ближайшим точкам.

Пример.

1. х  [ x₁, x₃ ],

( x - x_i2)(x - x_i3) ( x - x_i1)(x - x_i3) ( x - x_i1)(x - x_i2)

у= y_i1 ------------------- + y_i2 ------------------- + y_i3 -------------------;

(x_i1 - x_i2)(x_i1 - x_i3) ( x_i2 - x_i1)(x_i2 - x_i3) ( x_i3 - x_i1)(x_i3 - x_i2)

2. х  [ x₁, x₃ ],

( x - x_i2)(x - x_i3) ( x - x_i1)(x - x_i3) ( x - x_i1)(x - x_i2)

у= y_i1 ------------------- + y_i2 ------------------- + y_i3 -------------------;

(x_i1 - x_i2)(x_i1 - x_i3) ( x_i2 - x_i1)(x_i2 - x_i3) ( x_i3 - x_i1)(x_i3 - x_i2)

Рис. 15

3 . Интерполирование многочленом степени n-1

Интерполирование многочленом степени n-1 производите по n экспериментальным точкам (рисунок 16). Интерполирование будет осуществляться по формуле (1).

Блок-схема алгоритма представлена на рисунке 17.

Основные обозначения:

x и у - массивы размерностью N;

N - число узловых точек;

x0 - значение х, при котором необходимо найти интерполированное значение функции;

у0 - значение функции, вычисленное в точке х0.

Рис. 16.

3. 3. 2. Форма Ньютона.

Определение. Пусть х₁, х₂, ... , х_N - произвольные точки (узлы), причем x_i x_j при i  j.

Значения y₁, y₂, ... , y_n функции у в узлах называются разделенными разностями нулевого порядка и обозначаются как [x_i], где i=1,N.

Рис.17

[ x₁] = y₁

[ x₂] = y₂

. . . ___

[ x_n] = y_n [ x_i] = y_i i = 1, n .

y(x₂)-y(x₁) y₂-y₁

Число y( x₁ ; x₂) = y( x₂ ; x₁) = ------------- = ------

x₂-x₁ x₂-x₁

называется разделееной разностью первого порядка функции у и обозначается [ x₁ ; x₂ ] = [ x₂ ; x₁ ]. В общем виде

y(x_i)-y(x_i-1) y_i-y_i-1

y ( x_i-1 ; x_i ) = y ( x_i ; x_i-1 ) =------------- = -------

x_i-x_i-1 x_i-x_i-1

___

где i =1, n

Число

1 y₃-y₂ y₂-y₁

y ( x₁ ; x₂ ; x₃ ) = ------- (-------- - -------- )

x₃-x₁ x₃-x₂ x₂-x₁

называются разделенной разностью второго порядка функции у и обозначаются [ x₁ ; x₂ ; x₃ ] . В общем виде

1 y_i-y_i-1 y_i-1-y_i-2

y ( x_i-2 ; x_i-1 ; x_i ) = ------- (--------- - ---------- )

x_i-x_i-2 x_i-x_i-1 x_i-1-x_i-2

___

где i =1, n

Разделенная разность k-го порядка определяется через разделенные разности ( k - 1) -го порядка по рекуррентной формуле ;

y ( x₂ ; x₃ ; x₄ ;… ; x_k+1) - y ( x₁ ; x₂ ; x₃ ;… ; x_k.)

y ( x₁ ; x₂ ;… ; x_k+1) = ---------------------------------------------------

_____ x_k+1 - x₁

k = 1, n-1

или

[ x₂ ; x₃ ; x₄ ;… ; x_k+1] - [ x₁ ; x₂ ; x₃ ;… ; x_k.]

[ x₁ ; x₂ ;… ; x_k+1] = -----------------------------------------------

x_k+1 - x₁

Например , k = 1

[ x₂ ] - [ x₁] y₂ - y₁

y ( x₁ ; x₂ ) = --------------- = ----------

x₂ -x₁ x₂ - x₁

Лемма. Пусть x₁, x₂, …, x_n произвольные попарно несовподающие узлы, в которых известны значения функции y₁, y₂, …, y_n. Алгебраический многочлен ( n - 1)-й степени

l_n-1(x) = y(x₁) + (x - x₁) y( x₁ ; x₂ ) + (x - x₁)(x - x₂) y( x₁ ; x₂ ; x₃) +

… +(x - x₁)(x - x₂)… (x - x₁)(x - x₂)… (x - x_n-1) y(x₁ ; x₂ ; x₃ ;… ; x_n) (2)

является интерполяционным, т. е.

____

l_n-1(x_i) = y (x_i), i = 1, n.

Так как разделенные разности y(x₁), y(x₁ ; x₂), …, y ( x₁ ; x₂ ;… ; x_n) это вполне определенные числа то функция (2) является многочленом (n-1)-й степени. Многочлен (2) называется интерполяционным многочленом Ньютона для неравных промежутков. Согласно утверждению, существует только один интерполяционный многочлен, интерполяционный многочлен Лагранжа тождественно совпадает с интерполяционным многочленом Ньютона, т,е,

l_n-1(x)  F_n-1(x).

У интерполяционного многочлена Лагранжа видна явная его зависимость от каждого значения функции y_i, где i = 1, n. Это во многих случаях бывает полезно. Однако при изменении n интерполяционный многочлен Лагранжа требуется строить заново. В этом состоит его недостаток, Интерполяционный многочлен Ньютона (2) выражается не через значения функции y, а через ее разделенные разности,

При изменении степени n требуется у интерполяционного многочлена Ньютона требуется добавить или отбросить соответствующие число стандартных слагаемых, Это удобно на практике и ускоряет процесс вычислений, Интерполяционный многочден Ньютона можно записать в виде

_n

l_n-1(x) =  C_i N_i (x) , где

ⁱ⁼¹

___

N_i(x) = (x - x₁)(x - x₂)(x - x₃)… (x - x_i-1) ; i = 2,n ;

N₁(x) = 1 ;

C_i = [ x₁ ; x₂ ;… ; x_i ] ;

___

[ x_i ] = y_i ; i = 1,n ;

1

[ x₁ ; x₂ ;… ; x_i ] = ------- ( [ x₂ ;… ; x_i ] - [ x₁ ;… ; x_i-1]).

x_i-x₁

При вычислениях разделенные разности записываются в виде таблицы 4,

Таблица 4,

xi	[xi]	[xi xi+1]	[xi;xi+1;xi+2]	[xi;xi+1;xi+2;xi+3]	[xi;xi+1;xi+2;xi+3;xi+4]
x1	y(x1)
		y(x1;x2)
x2	y(x2)		y(x1;x2;x3)
		y(x2;x3)		y(x1;x2;x3;x4)
x3	y(x3)		y(x2;x3;x4)		y(x1;x2;x3;x4;x5)
		y(x3;x4)		y(x2;x3;x4;x5)
x4	y(x4)		y(x3;x4;x5)
		y(x4;x5)
x5	y(x5)

Программа использует следующие переменные :

Х0 - аргумент, при котором необходимо вычислить значение функции ;

(N-1) - степень многочлена ;

N - число экспериментальных данных ;

X(N),Y(N) - массивы, i = 1,N.

Замечание :

Разделенные разности помещаются в массив Y.

I,K - параметры циклов ;

L - значение многочленов в точке Х0 ;

P и I1 - рабочие переменные.

Блок-схема алгоритма представлена на рисунке 18,

3. 3. 3. Погрешность интерполяции.

Если функция (x), подлежащая интерполяции, достаточное число дифференцируема, то можно вывести формулу для определения погрешности интерполяции, Оценка максимальной погрешности интерполяции на всем отрезке [ a ; b ] :

M_n

max | (x) - F_n-1(x) |  ---- max | W_n-1(x) | ;

^[a,b] n!

M_n = max | ⁽ⁿ⁾(x) | <  ;

^[a,b]

W_n-1(x) = (x-x₁)(x-x₂)… (x-x_n-1).

Рис. 18

3. 3. 4. Многоинтервальная интерполяция.

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

полинома и значениям его коэффицентов трудно судить о виде зависимости y(x).

Сплайн - интерполяция.

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

Определение. Пусть отрезок [ a ; b ] разбит на ( N-1 ) равных частичных отрезков

[ x_i, x_i+1 ], где

x_i = a + ( i-1 ) h , i = 1, 2.,…, N-1, x_N = b ; x₁ = a ;

h = ( b - a ) / ( N-1 ).

Сплайном называется функция, которая вместе с несколькими производными непрерывна на всем заданном отрезке [ x_i ; x_i+1 ] в отдельности является некоторым алгебраическим многочленом.

Максимальная по всем частичным отрезкам степень многочленов называется степенью сплайна, а разность между степенью сплайна и порядком наивысшей непрерывной на [ a, b] производной - дефектом сплайна,

Например, непрерывная кусочно - линейная функция ( рисунок 19 ) ( ломаная ) является сплайном первой степени с дефектом, равном единице, т.к. непрерывна только сама функция ( нулевая производная ), а первая производная уже разрывна.

На практике наиболее широкое применение получили сплайны третьей степени, имеющие на [ a, b ] непрерывную, по крайней мере , первую производную.

Эти сплайны называются кубическими и обозначаются через S₃(x). Величина mi = S’₃(x_i) называется наклоном сплайна в точке ( узле ) x_i. В общем случае сплайн задается глобальным способом, т.е. с использованием всех узлов при любом их расположении. Рассмотрим кубический сплайн, заданный локальным способом. Это задание реализуется сравнительно просто и требует существенно меньшего объема памяти ЭВМ, чем при глобальном способе задания.

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

i = int (( b-a ) / h ) ;

h = ( b-a ) / ( N-1) ;

(x_i+1-x)²(2(x-x_i)+h) (x-x_i)²(2(x_i+1-x)+h)

S₃(x)= ----------------------- y_i + ----------------------- y_i+1 +

h³ h³

(x_i+1-x)²(x-x_i) (x-x_i)²(x-x_i+1)

+ ----------------- m_i + ---------------- m_i+1 ,

h² h²

где m_i , m_i+1 --первые производные S₃(x).

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

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

m_i=(y_i+1-y_i-1)/2h , i=2 , ... , n-1 ;

m_i=(4y₂-y₃-3y₁)/2h , i=1 ;

m_n=(3y_n+y_n-2-4y_n-1)/2h , i=n .

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

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

Блок-схема алгоритма представлена на рисунке 20.

Примечание. Вввод данных и вывод результата осуществить с соответствующими коментариями.

Например:

а) 20 PRINT “ВВЕДИТЕ ЗНАЧЕНИЕ Х , ПРИ КОТОРОМ ВЫЧИСЛЯЕТСЯ”

30 PRINT “ИНТЕРПОЛЯЦИОННОЕ ЗНАЧЕНИЕ Y”

40 INPUT X0

50 PRINT “ВВЕДИТЕ КООРДИНАТЫ БЛИЖАЙШИХ УЗЛОВЫХ ТОЧЕК”

60 INPUT X(1) , Y(1) , X(2) , Y(2)

. . .

б) 100 “ИНТЕРПОЛЯЦИОННОЕ ЗНАЧЕНИЕ ФУНКЦИИ В ТОЧКЕ”; Х0

110 “РАВНО “; Y0 ; “КОД ОШИБКИ L=”; L

. . .

Рис. 20

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Волков Е.А. Численные методы: Учеб. пособие для вузов.-.: Наука, 1987. - 248с.

2. Уолш Б. Программирование на Бейсике. - М.: Радио и связь, 1988. - 336 с.

3. Гринчишин Я.Т., Ефимов В.И., Ломакович А.Н. Алгоритмы и программы на Бейсике. - М.: Просвещение, 1988. - 160 с.

4. Дьяконов В.П. Справочник по алгоритмам и программам на языке Бейсик для персональных ЭВМ. - М.: Наука,1987. - 240 с.

5. Светозарова Г.И., Мельников А.А., Козловский А.В. Практикум по программированию на языке Бейсик. - М.: Наука, 1988. - 368 с.

6. Сергованцев В.Т., Смирнов С.М. Сборник задач по вычислительной технике в инженерных и экономических расчетах. - М.:Финансы и статистика, 1985. - 160с.

7. Бронштейн И.Н., Семендяев К.А. Справочник по математике. - М.: Наука, 1986. - 544 с.

56