Оценка погрешности вычисления производных на основе варьируемой кусочно-полиномиальной аппроксимации функции

поиску локально экстремальных элементов последовательности. На основе схемы программируется локализация одновременно всех экстремумов входной последовательности при произвольно

заданных радиусах окрестности локализации.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Вирт, Н. Алгоритмы и структуры данных. - М.: Мир, 1989. - 360 с.

2. Заика, И.В. Разработка и исследование схем оптимизации на основе алгоритмов сортировки с приложением к идентификации экстремумов решений дифференциальных уравнений: автореф. дис.... канд. техн. наук / И.В. Заика - Таганрог: ТРТУ, 2007. - 19 с.

3. Маркушевич, А.И., Маркушевич, Л.А. Введение в теорию аналитических функций. - М.: Просвещение, 1997. - 320 с.

4. Ромм, Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. I // Кибернетика и системный анализ. - 2007. - № 1. - С. 165 - 183.

5. Ромм, Я.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ. - 1994. - № 5. - С. 3 - 23.

6. Ромм, Я.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. - 1995. - № 4. - С. 13 - 37.

7. Ромм, Я.Е., Заика, И.В., Лабинцева, А.А. Безусловная оптимизация на основе сортировки с приложением к компьютерному анализу устойчивости систем управления // Известия вузов. Северо-Кавказский регион. Технические науки. Серия «Управление, вычислительная техника и информатика». - 2008. - № 6. - С. 11 - 17.

8. Ромм, Я.Е., Заика, И.В., Лабинцева, А.А. Безусловная численная оптимизация при вариации параметров. I / ТГПИ. - Таганрог, 2008. - 31 с. Деп. в ВИНИТИ 04.03.2008, № 193-В2008.

9. Ромм, Я.Е., Заика, И.В., Лабинцева, А.А. Безусловная численная оптимизация при вариации параметров. II / ТГПИ. - Таганрог, 2008. - 44 с. Деп. в ВИНИТИ 04.03.2008 № 194-В2008.

УДК 681. 3.06

С.С. Выпряжкина

ОЦЕНКА ПОГРЕШНОСТИ ВЫЧИСЛЕНИЯ ПРОИЗВОДНЫХ НА ОСНОВЕ ВАРЬИРУЕМОЙ КУСОЧНО-ПОЛИНОМИАЛЬНОЙ АППРОКСИМАЦИИ ФУНКЦИИ

Аннотация. Произведена оценка погрешности вычисления кусочно-полиномиальной аппроксимации функций и производных на основе интерполяционного полинома Ньютона для произвольно заданной границы погрешности. Показана сходимость кусочно-полиномиально интерполированных производных к производным кусочно-полиномиально интерполируемой функции. Дана оценка скорости сходимости.

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

S.S. Vypryazhkina

THE ESTIMATION OF ERROR OF CALCULATION OF DERIVATIVES ON BASIS

THE VARIED PIECEWISE-POLYNOMINALAPPROXIMATION OF FUNCTION

Absrtact. The estimation of error of calculation of piecewise-polynominal approximation of functions and derivatives is made on the basis of the Newton's interpolation polynomial for the arbitrarily set border of error. Convergence of thepiecewise-polynominal interpolated derivatives is shown to the derivatives of thepiecewise-polynominalinterpolated function. The estimation of speed of convergence is given.

Key words, piecewise-polynominalapproximation of functions, piece interpolation, piece-interpolation approaching of derivatives

Аппроксимация действительной функции y = f (x) от одной действительной переменной на произвольном отрезке [ а, Р ] выполняется следующим образом [1 - 3]. Выбирается система подынтервалов равной длины, объединение которых покрывает [ а, Р ]:

р-1

[а, Р] = и [х 1 , хм],

i=0

> к

для определенности полагается Р = 2 , к е {0, 1, ...}. Пусть априори задана граница Б абсолютной погрешности аппроксимации данной функции. При каждом I из (1) на I -м подынтервале строится интерполяционный полином Ньютона (t) с равноотстоящими узлами, где

X X у х , +1 X

t =--, h = — - расстояние между узлами. Степень полинома п выбирается одина-

h П

ковой для всех подынтервалов и минимальной при условии:

/

Интерполяционный полином Ньютона преобразуется к виду:

х-х,

где х е [ х1, х1+1], t = .

h

Искомую оценку выполним в предположении, что у = / (х) определена, непрерывна и дважды непрерывно дифференцируема на[«- 2К0, ¡3 + 2К0] , на концах подразумеваются соответственные односторонние производные. В предположении разбиения (1) и аппроксимации (2) на [ а, Р ] для у = / (х) , в предположении 2 < п < N, при произвольно фиксированном I разложим разность f' (х) — П (х) по формуле Тейлора с двумя членами в окрестности радиуса Нк произвольно выбранного узла интерполяции на [ х ,, х|+1 ] :

(f (х)-(х)'= /'(х,)-^п, (х,) + (/"(х, + вкк)-(хи + вкк))Нк, 0 < в < 1 Отсюда для Ух е [х{, х|+1 ] выполнено:

| /(х) - (х) | < | f'(хи) -V ,п (хи) I + I f"(хи + Щ) - х + еКк)) IК, (4) , Р-а

где К = ~¥П

В данных предположениях

/"(х, +0Лк )|< [ ш« к ]^"(х)| VI = 0,1,...,2к-1.

[а-2 К,р+2 К0]

Иными словами,

1 /Ч+ еКк) 1 < ^ ~00 = const = 0,1,...,2к -1.

где ~00 = г тах 1| /"(х)|.

[а-2й,р+2й0]

Покажем, что

I П (х,1 + екк) I < ~11, ~11 = сош! V £ = 0,п л VI = 0,2к -1 лУ к = 0,1,...

Имеем:

¥",П (х) = ^/п (*),

Кк2

или,

т' п (х)=(' о -1));+/М о (' - 1Х' - 2));+...+(' о - 1)-о - ^+1»:

+... + /01 -1)('-п +1))".

Покажем вначале ограниченность слагаемого, содержащего ———2— .По лемме П1.1,

/, о)

( ^1 / Л" П'-1 -1

представленной в [4], полином I П и — £) ограничен значением ](] — 1) х ]!-. По опре-

110 А

делению, & /(х0 ) = &~1/(хг0 + \ ) — &~1/(х0 ), далее,

&-1/(хго + К ) = Х-2/(х, 0 + 2\ ) — &-2/(Х0 + К ),

& / (Х,о) = &-2/(хг, + К )-Х-2/(х, о),

Отсюда

&1Ы- 1 ( М-1 Г (V _ Л^-1

f, v =h (хго + К)- Aj-1f(xо)) =

'k

Аналогично,

I

A-2/(xi0 + 2hk)- A-2/(xio + hk) = hk§(-1) C/хо + (j-£-1К + hk +^+A),

£=о

j-2 £

Aj/, + hk)-A/o ) = hk §(-1) CjVta + (j - £ - 1)hk + ^+A),

£=о

гдео <e1£+1 < 1 л о <e2£+1 < 1 V£ = о, j - 2.

Почленное вычитание обеих частей двух последних равенств влечет: А/(х о) = (hk )2

j-2 1 hk § (-1)£ cj-2 (/' (х о+(j - £ - 1)hk + hk +eM+A)-/'(хо+(j - £ - 1)hk+eu+A )W

£=о

По формуле Лагранжа, применительно к приращениям производных с величиной приращения аргумента hk + (е2£+1 - e!£+1)hk =(1 + (02£+1 - ©1£+1 ) )hk, получится:

(/' (хго+(j - £ - 1)hk + hk + e2£+А) - f(xtо + (j - £ - 1)hk+e,£+A))=

= f" (Хо + (/ - l - 1)hk + e3£+1 (1 + (e2£+1 - e1£+1 ))hk + e1£+1hk ) X ((1 + (e2£+1 - e1£+1 ))hk X

где о < #3£+х < 1. Отсюда

1 f' (ХЮ +(j - £ - 1)hk + hk + e 2£+1hk )-f'(x, о +(/' - £ - 1)hk +e1£+1hk ) < C11hk, C11 = const,

Aj/

где с,, = max | /"(x) | x2. Из последнего выражения для—:—в [4]выводится

11 [a-2h,p+2h\ (hk )2

неравенство:

А/

(hk )2

j-2 1 < К §Cj-2c11hk .

£=о Vlk

С учетом суммы биномиальных коэффициентов оценка примет вид:

А/

(hk )2

< 21-2 c

11

Аналогично предыдущему, по индукции можно показать ограниченность конечных разностей, а значит и ограниченность всех коэффициентов полинома (х), а соответственно и всех его производных.

Подстановка найденных оценок в выражение второй производной интерполяционного полинома влечет:

п г>1-1 _ 1

\Ч"п (х)<е2;-2сп х ^ - 1)х 71_П -1

или

Отсюда

jA "" ^ " J j!

" и-7'-1 _ 1

|ч"„ МИеЛ/ -1)27-2 х ) cn. /=2

|Ч"г„ (x 2/-1(и/-1 -1)~00,

U1 / 2 и -1

/=2

где С00 - постоянная. Поэтому

Ч"г„ (x )|< и~00 Е ((2и)7-1 - 27-1).

У=2

Окончательно, с добавлением единичных слагаемых под знаком суммы,

г(2п)" -1  л

Ч",и

V 2и -1

Отсюда следует, что

f{2N)N -1 ^

С11 Nc00

- 3

V 3 J

Из данных оценокполучается, что

| f" (x,, + е К) - Чи - x + 0 К) | < | f" (x,, + 0 к) | +1Ч" m x + Qhk) | < С00, с00 = const,

где С00= С00 + С11. Таким образом, имеет место неравенство: |f'

Первое слагаемое в правой части (5) можно оценить, используя формулу Тейлора для f (x) - Ч,и (x) в hk -окрестности узла интерполяции:

f (x )-Чш (x) = f (x, )-Чш (x, ) + (f\xu )-Ч'ш (x, ))hk +

+ (f" (x,, + 00,hk ) - Ч"ш (xu + 00 A ))(hk )2, 0 <00, < 1. По условиям интерполяции f (x,,) = Ч,и (x,,), поэтому

f (x)-4и(x) = (f (x,,)-Ч',„ (x,,))hk + (f "(x,, +0O,hk)-Ч",„ (x,, +0O,hk))(hk)2. Отсюда

I f(xa)-Ч',„ (x,,) |<lf (x)(x) I +(| f "(x,k +00,hk) 1 + 1Ч" "(xft +00,hk)|)hk.

hk

В результате последнее неравенство примет вид оценки: |f'

Подстановка

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

Выход заключается в том, чтобы предположить более высокий порядок дифференцируемо-сти аппроксимируемой функции. Если функция y = f ( x ) непрерывна и непрерывно дифференцируема n +1 раз на отрезке [a — 2h0,Р + 2h0], то для нее сохраняются все проделанные рассуждения и оценки, но кроме того выполняются условия леммы 1.1 из [4]:

Лемма. Пусть для произвольного n = const функция y = f (x) определена, непрерывна

и непрерывно дифференцируема n + 1 раз на отрезке[ a, Р ], на концах которого подразумеваются соответственные односторонние производные. Тогда, каково бы ни было n > 1, последовательность полиномов Yin (t) равномерно сходится к функции f (x) на данном отрезке при k ^ да ,

где k = log2 P, P - число подынтервалов из (1). Скорость сходимости оценивается из соотношения

С ( n ) , 2k—1

|f ( x) — (t )|< hn+\ P = 2 k, [ a, p ] = U [ *г, xi+1],

2 i=0

где С (n) = const, h - шаг интерполирования полинома Y0n (t) на при k = 0.

В силу леммы для рассматриваемой функции на рассматриваемом отрезке имеет место неравенство:

где h0 =

If ( x)(0|< h0"+1, Vx e[a-2h0, p + 2h0 ],[ a, p ] = (J [ хг, xM]

2 i=0

p-a

0

n

Отсюда

.n+1

| f'( x., )-w\n ( x,) I < ^hn1 Ж)'+ ( f "X +00, К ) | + |^и(хл + 00, hk ) \)hk,

hk 2

h0

где h, =—т. Следовательно,

k 2k

hn h I f '(x, ) - (x, ) | < С11-П + (| f " (xA + 00, К ) | +1 y", ( x.k + 00, К ) |) -0

где C11 = max c(n).

2<n< N

На основании изложенногоприходим к неравенству:

h0 h0

f (x)-Пп(x) < С11-кПт + ^00^

h 0 - шаг интерполирования полинома ( x) на [ a, P ], или,

|f "(x) (x)|< C,}^^ + 2C00 Pn .

Таким образом, имеет место

Теорема . Пусть для произвольного п = const, 2 < п < N, функция y = f (x) определена, непрерывна и непрерывно дифференцируема п + 1 раз на отрезке [a - 2k, P + 2h ] ,на концах которого подразумеваются соответственные односторонние производные. Тогда, каково бы ни было п > 2, последовательность полиномов ^ ' in (x) равномерно сходится к производной функции f ' (x ) на отрезке [a, р]при k ^ да, где k = log2 P, P - число подынтервалов из (1). Скорость сходимости оценивается из соотношения

~ p-а ~

1 f '(x) - Win (x) 1 < C00^T~, C00 = const,

2 n

k

2"• -1

_ 2 k-1

Vx e[a, P]aV/ = 0,2k -1,[a, p] = \ [xt, xi+1].

i = 0

С учетом n > 2 из теоремы вытекает

Следствие В условиях теоремы выполняется неравенство

~ В-а ~ 1 f '(x) - W\n (x) 1 < C00 , C00 = С0Ш1,

при этом C00 не зависит от выбора степени полинома n .

Таким образом, если с помощью варьируемого кусочно-полиномиального метода в условиях двукратной дифференцируемости приближается функция, то автоматически приближается производная, причем с равномерной сходимостью при дополнительном требовании (n +1) -кратной дифференцируемости приближаемой функции. Скорость сходимости имеет порядок геометрической прогрессии по числу подынтервалов.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Ромм, Я. Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки: авто-реф. дис. ... докт. техн. наук. / Я.Е. Ромм - Таганрог: ТРТУ. - 1998. - 42 с.

2. Ромм, Я. Е. Минимизация временной сложности вычисления функций с приложением к цифровой обработке сигналов: учеб.пособие / Я. Е. Ромм, С. А. Фирсова. - Таганрог: ТГПИ, 2008. - 124 с.

3. Ромм, Я.Е., Джанунц, Г.А. Кусочно-полиномиальные приближения функций и решений дифференциальных уравнений в применении к моделям периодических реакций./Я.Е. Ромм, Г.А. Джанунц. - Таган-рог:ТГПИ имени А.П. Чехова, 2013. - 240 с.

УДК 517.91: 518.1 ББК 81.11

Т.Г. Каплунов

ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ АВТОМАТИЧЕСКОГО ФОРМИРОВАНИЯ ПРОГРАММ УПРАВЛЕНИЯ ДВИЖЕНИЕМ

Аннотация. В данной статье предложен механизм управления движением робота в конфигурации шагающего механизма на основе генетических алгоритмов.

Ключевые слова: генетические алгоритмы, робототехника, мехатронно-модульные роботы, управление движением.

T.G. Kaplunov

USING GENETIC ALGORITHMS TO AUTOMATICALLY GENERATE TRAFFIC

MANAGEMENT PROGRAMS

Absrtact This article provided a mechanism for managing the movement of the robot in the configuration of the walking mechanism based on genetic algorithms.

Key words: genetic algorithms, robotics, mechatronic-modular robots, motion control.

Эволюционные методы, как и нейросети, позволяют решать вспомогательные задачи теории управления, не привлекая такие базовые понятия, как интеграл, дифференциал, передаточная функция динамического звена и т.п.

Приведем основные сведения об эволюционных методах. В эволюционных методах вначале создается множество случайно сформированных объектов с заданной структурой (такое множество называется популяцией объектов) и функция, определяющая близость объекта к истинному решению, называемая целевой функцией. Далее все эволюционные методы работают по общей схеме: определяется пригодность объектов в популяции, с учетом близости к целевой функции и при внесении элемента случайности создаются объекты для популяции следующей итерации. Данный процесс повторяется либо до получения решения, либо до окончания времени, отведенного на решение. Популяция имеет «память» - в ней накапливаются лучшие результаты предыдущих итераций, и этим эволюционные методы отличаются от других методов случайного поиска. В создании нового объекта популяции обычно участвуют два существующих объекта, от каждого из которых новый объект отбирает часть свойств; этот процесс называется скрещиванием или кроссовером. При кроссовере, кроме того, исходные объекты подвергаются некоторому случайному изменению - мутации. Иногда используется стратегия элитизма, при которой несколько лучших особей переходят в следующее поколение без изменений, не участвуя в кроссовере и отборе [2].