Метод рекуррентных формул для научных исследований

Обчислювальна техніка та програмування

ОБЧИСЛЮВАЛЬНА ТЕХНІКА ТА ПРОГРАМУВАННЯ

УДК 621.372

МЕТОД РЕКУРРЕНТНЫХ ФОРМУЛ ДЛЯ НАУЧНЫХ

ИССЛЕДОВАНИЙ

Каширский И. С.

В статье рассматривается новый метод численного дифференцирования сложных функций. Теоретически предела сложности для дифференцирования функций не существует. Однако на практике возможности существующих методов ограничиваются сложностью функций, и для многих функций численный расчет производных высшего порядка невозможен. Новый метод применим для численного расчета производных любого порядка, и его точность определяется только точностью арифметических операций при расчетах. Метод рекуррентных формул (МРФ) существенно отодвигает порог сложности дифференцируемых функций и позволяет вычислять требуемое количество высших производных без ограничений.

1. Классический метод дифференцирования

Этот мощный метод аналитического дифференцирования теоретически применим для любых функций, заданных в аналитическом виде. При необходимости численного расчета в найденные аналитические выражения производных подставляется численное значение переменной. Его основной недостаток в том, что все расчетные производные должны быть найдены в аналитическом виде. Известно, что при дифференцировании функции, аналитическое выражение производной сложнее, чем исходное выражение. При многократном дифференцировании возникает эффект «снежного кома», когда сложность получаемых аналитических выражений производных быстро растет и, даже для несложных функцій, получить выражения для производных выше 3-го порядка практически невозможно. Подчеркнем, что для научных исследований в большинстве случаев необходимы численные производные, а аналитическое дифференцирование является промежуточным и трудоемким этапом расчета. Чтобы освободить пользователя от этой работы, приемы аналитического дифференцирования программируются в компьютерных средах для символьного и численного расчета производных. Аналитические выражения производных настолько сложны, что для многих функций выражение даже для 2-й производной уже нельзя вывести на экран ПК. По этой же причине численный расчет производных ограничен (например, в среде Mathcad не более 5-и производных). Более того, как показано ниже, некоторые выражения содержат ошибки и дают неверные численные значения высших производных.

130

Вісник Національного технічного університету України "КПІ" Серія — Радіотехніка. Радіоапаратобудування.-2010.-№41

Обчислювальна техніка та програмування

2. Формулы производных для элементарных функций

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

dnF

~dxn

= G

В список элементарных включены функции, для которых существуют общие формулы вида (1).

3. Метод рекуррентных формул

Предпосылки к МРФ заложены Коши, впервые выполнившим численные операции над бесконечными степенными рядами.

В настоящей работе выведены рекуррентные формулы (РФ) для численного расчета высших производных. Для любой функции ее высшая производная связана с ее предыдущими некоторой аналитической зависимостью. Набор необходимых производных является уникальным для каждой функции и никогда не повторяется.

Таблица 1

Функция Нач. значения Рекуррентные формулы

sin

1 sin x / = 1 1 sin( x0) / = cos( x0) 2 sin2(x0) k - 3 /k = (4/13/k-1 + Z <2 /12/.1 /k-1-, - (i + 1)(k -1 - i) /2/k i=1 i k - i - 2 + ( Z /q + \/i+\-q X Z /q + \/k-1-i-q )))/(2(k - 1) /2) q = 0 q = 0

ex /1=1 / = /k-1/

x ex -1 /1=1 /k = ( - /k-1 -Z /q+l/k - q )/k q=i

ln

ln

1 / = 1 J1 ln d1 / = - /2. / 2 d 1 /k = (-(k - 2)/k-1 - Z2./q+1/k-i-q )/«k - W q=0

ln

Эта особенность вынуждает искать оригинальные РФ и представлять их в виде справочных данных. Каким бы трудоемким не был вывод таких РФ, он выполняется один раз, а затем легко программируется для практических расчетов. РФ снимают все ограничения на порядок производных и применимы для численного расчета любого их количества. Их реализация пост-

Вісник Національного технічного університету України "КПІ" Серія — Радіотехніка. Радіоапаратобудування.-2010.-№41

131

Обчислювальна техніка та програмування

роена на простейших арифметических операциях, и потому ошибка в расчете определяется только ошибками округления чисел. Далее показано, что каждая элементарная функция имеет не только формулу (1), но и свою оригинальную РФ. В табл.1 представлены некоторые простейшие РФ, которые для МРФ служат иллюстрацией и могут быть альтернативным методом расчета высших производных элементарных функций. Основные РФ приведены в табл. 2, 3. Они содержат сложные функции, для которых произвольное количество производных высокого порядка нельзя вычислить другими методами. Сложность функций состоит в том, что их аргументами являются не переменные, а полиномы высоких порядков от переменных.

Таблица 2

Функция Нач.значения Рекуррентные формулы

eD f _ e"1 k - 2 fk _ ( £ ( q + 1) dq + 2 fk-1-q )/(k - 1) q _ 0

Є f _ e^ f _ "2f f 24І1 fk _ (2d22f1 fk-1 + (2(k - 1)f12d2 - 4f22)dk + + £ ( d 22 f,+ 1 fk-1-i + (i + 1)( k - 1 - i )( f12 d,+ 2 dk-i - 4 d 1 f,+ 2 fk - i) - i_1 -4dk-1-(£ (q + 1)(І + 1 - q) fq + 2 f1+ 2-q) + (£ fq+1 f+1-q) x q _ 0 q _ 0 k - i- 2 x( £ ( q + 1)( k - 1 - І - q ) dq+2 dk - i- q )))/(8( k - 1) d1 f2 ) q _ 0

eD2 r df f _ e 1 k-2 k-i- 2 fk _ 2( £ d + 1( £ (q + 1) dq + 2 fk-1-i - q))/(k -1) i_ 0 q _ 0

eD r d3 f _ e 1 k-2 k- i- 2 i fk _ 3( £ ( £ ( q + 1) dq+2 fk-1-i - q )( £ dq+1d,+1-q )V( k - 1) i_ 0 q_0 q_0

eD r df f _ є1 k - 2 k - j - 2 fk _ 4( £ ( £ (q + 1) dq+2 fk - 1 - j - q) x X ( £ d j + 1 _ i ( £ d q + 1 di + 1 _ q )))/( k - 1) i _ 0 q _ 0

1 eD r d-i f _e 1 k - 3 f„ _ ( - ( k - О f1dk - £ ( i + 1)( di + 2 fk - 1-i + i _ 0 k - i - 2 + fi+2 ( £ dq + 1dk-1-q )))/(( k - 1) d 12) q _ 0

1 eD2 r df f1 _ e 1 f _ _2d2 f f d13 f k - 3 fk _ ( - 2( k - 1) f dt - (£ (j + 1)(2 d 2 fk -bj + j _ 0 k - j - 2 i + fj + 2 ( £ dk- j - i ( £ d, +1 d, +1 - q )))))/(( k - 1) d 13) i _ 0 q _ 0

1 eD3 1 r d3 f1 _e 1 fl _ d14 f fk _ (-3(k - 1) f ydk - £ ( j + l)(3dj+2fk-1-j + f]+2 x k- j-2 k- j-i- 2 i x( £ ( £ d -1- q)(£ d d„1- ))))/((k - 1)d14) i_0 q _0 q _0

Сложность функции делает сложнее вывод ее РФ, но практически не увеличивает время счета. В табл. 2, 3 вычисляются коэффициенты fk, кото-

132

Вісник Національного технічного університету України "КПІ" Серія — Радіотехніка. Радіоапаратобудування.-2010.-№41

Обчислювальна техніка та програмування

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

dk -1F

dx

k-1

(k -1)! fk. Для численного расчета производных в точке х0 по ре-

куррентным формулам необходим предварительный расчет начальных коэффициентов f1 = F (х0) , f2- dF (Х0) ны в табл. 2, 3.

dx

, выражения которых также приведе-

Таблица 3

Функция Начальные значения Рекуррентные формулы

ln D f = ln d f2 = d 2 / d1 fk = ((k - 1) dk - X ( q + 1) f + 2 dk-1-q )/((k - 1) d1) q = 0

1 ln D f = 1 1 ln d 1 f = - d 2 f12 f2 d1 k - 3 fk = (-(k - 1)/,2dt - X (i + 1)( f,+2dk-i + i = 0 k - i - 2 + di + 2( X fq + bft-1-i - q )))/(( k - 1) d,) q = 0

VlnD f1 =УІln d1 f2 = d2 2df k - 3 fk = ((k - 1)dk - 2X (d 1(i + 1) fk+2 fk-1-г + i = 0 + dk - i ( X ( q + 1) f + 2 f, + 1-q )))/(2( k - 1) d 1 f1) q = 0

1 f = 1 1 yjln d1 f = -d2 f3 f 2d1 k - 3 fk, = (-(k - 1)f13dk -X (j + 1)(2 fj + 2dk-1-+ j=0 k - j - 2 i + dj+2( X fk-1-j-i(X f,+1 fi+1-,)))) /(2(k - 1)d 1) i= 0 q = 0

Vln D

sin D cos D f = sin f2 = d2 cos d1 f = cos d1 f2 =-d2sin d1 fk = (2(k - 1)d2 (1 - f12)dk - 2d22-1 + X ((i + 1)(k - 1 -i) * i=1 x(-f+2 fk-i + di+2dk-i (1 -/2)) - d22f+Jk-1-i -k-i-2 i -( X fq+1fk -1-i-„ )(X (q + 1)(i + 1 - q )dq+2 d+2-q ))) /(2(k - f q=0 q=0

sin2 D cos2 D f1= sin2 d f2 = d2sin

arcsin D arccosD f = arcsin d1 f2 V1 - d12 f1 = arccos d1 f ~d 2 f2 ^ - d\ k-3 fk = (-2 f22 d1dk-1 - 2(k - 1)d 2dk - X (f22 di+1dk-1-i + (i + 1)(k - 1 - i) X i=1 x((d12 - 1) fi+2fk-І + di+2dk -i ) + (X (q + 1)(i + 1 - q)fq+2f+2-q ) q=0 k-i-2 +((X d+kdk_1_,_4)))/(2(k- 1)(d12 -1)Л) q=0

Вісник Національного технічного університету України "КПІ" Серія — Радіотехніка. Радіоапаратобудування.-2010.-№41

133

Обчислювальна техніка та програмування

Вычислительный эксперимент

Все расчеты выполнены в среде MATLAB. Хотя метод не ограничивает количество высших производных, для каждой функции вычислялись только 25 высших производных. Несмотря на такое количество вычисляемых производных, расчеты выполнялись так быстро, что упоминание о времени счета потеряло смысл. Полученные результаты были проверены в среде Mathcad, в которой можно вычислить только 5 высших производных. Ре-

X

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

d4 F

d5 F

Mathcad неверно вычисляются производные —г = 0.0; —г = 0.0. Прави

dx dx

льные значения этих производных приведены ниже.

Для всех функций аргументом является полином вида

D( x + x0) = d1 + d2( x + x0) + d3( x + x0)2 + ... + dn+1( x + x0)n

где коэффициенты d1, ..., dn заданы при x0 = 0 и пересчитываются в случае ненулевого смещения x0. Таким образом, все производные вычисляются в точке x0. Кроме численного расчета производных, для каждой функции построен степенной ряд в точке x0, который в области радиуса сходимости можно дифференцировать и получать производные в виде степенных рядов, т.е. как функции переменной x. Это означает, что методом рекуррентных формул можно не только вычислить любые производные в точке x0, но и проследить изменения требуемой производной от переменной x.

Для всех примеров был задан полином, который при x0 = 0 имеет вид D(x) = 1 + 2x + x2 - x3 + x4 - x5 + x6 - x7 + x8 - x9 - x10

1. Функция F = e^ в точке x0 = 0. Полученные численные производные:

dF

dx

-2,7183;

d2 F dx2

8,1548;

d 3F dx3

-27,183;

d4 F dx4

d5 F

35,338; XV = 1166,2;

dx5

d 6F

d7 F <d8 F c d9 F

-2,53 59-104; = 4,0090-105; = -5,5183-106-

dxs

dx9

6,3250 -107

dx6 ’ dx1

Степенные ряды: 1) функции

F(x) = 2,7183 - 2,7183x + 4,0774x2 - 4,5305x3 +1,4724x4 + 9,7179x5 -35,221x6 + 79,543x7 -136,86x8 + 174,3x9 - 104,75x10 - 234,45xn + +1075,1x12 -2616,5x13 + 4733,2x14 + ...

2) первой производной

dF

— = -2,7183 + 8,1548x - 13,591x2 + 5,8896x3 + 58,589x4 - 211,32x5 +

dx

+556,80x6 -1094,9x7 +1568,7x8 -1047,5x9 - 2579,0x10 +1,2901 • 104x11 --3,4014 • 104 x12 + 6,6265 • 104 x13 -...

3) второй производной

134

Вісник Національного технічного університету України "КПІ" Серія — Радіотехніка. Радіоапаратобудування.-2010.-№41

Обчислювальна техніка та програмування

d 2 F

= 8,1548 - 2,7183х +17,669х2 +194,36х3 -1056,6х4 + 3340,8х5 -dx

и расчет изменении -0,25 <= х <= 0,25

-7664,3х6 +1,2550 -104х7 - 9427,5х8 - 2,5790 • 104х9 +1,4191-105х10 --4,0815-105х11 + 8,6145-105х12 -1,3414-106х13 +...

Радиус сходимости степенных рядов равен R = 0,25 функции, ее первой и второй производных в пределах обеспечивает необходимую точность расчета .

2. Функция F = , 1 в точке х0 = 0,5.

Vln D

Полученные численные производных:

dF

d% d 6F

= -0,85842;

d2 F d%2

= 2,9355;

d 3F йхъ

= -12,929;

d4 F dx4

= 119,56;

d 5F dj5

= -788,98;

d 7 F

= 1,1445-104; ^4- = -1,2324-10:

/У8г /79Т7

5 = 2,1719 -106; = -3,1395-107

dxi

dx

dx6 ’ dx7

Степенные ряды: 1) функции

F(х) = 1,1378 - 0,85842х +1,4677х2 - 2,1548х3 + 4,9817х4 - 6,5748х5 + +15,896х6 - 24,453х7 + 53,867х8 - 86,518х9 +193,47х10 - 319,42х11 + +695,01х12 -1197,9х13 + 2555,6х14 .

2) первой производной

dF_

dx

= -0,85842 + 2,9355х -6,4644х2 +19,927х3 -32,874х4 + 95,373х5 -

-171,17х6 + 430,93х7 -778,66х8 +1934,7х9 -3513,6х10 + 8340,1хп --1,5572-104 х12 + 3,5779-104 х13 - 6,7589-104 х14 +1,5198-105 х15 -...

Радиус сходимости степенных рядов равен R = 0,25, и расчет изменений функции, ее первой производной в пределах -0,25 <= х <= 0,25 обеспечивает необходимую точность расчета .

3. Функция F = sin D в точке х0 = 0.

Полученные численные производные:

dF _ dx d6 F dx6

1,0806;

= 630,65;

d2 F _ dx2 d7 F dx1

-2,2853;

-6698,5;

d 3F = dK3 d 8F dx*

d 4 F d 5F

17,662; —r = 30,789; —5- = 50,949;

Сіл Сіл

d 9 F

3,9394-104; ^4 = -2,7130-105 dx

Степенные ряды: 1) функции

F(х) = 0,84147 +1,0806х -1,1426х2 - 2,9436х3 +1,2829х4 + 0,42457х5 + +0,87590х6 -1,3291х7 + 0,97703х8 - 0,74762х9 - 0,60753х10 + 3,8954х11 + +0,99934х12 - 0,046969х13 -...

2) первой производной

= 1,0806 - 2,2853х - 8,8309х2 + 5,1315х3 + 2,1229х4 + 5,2554х5 -dx

-9,3034х6 + 7,8162х7 - 6,7286х8 - 6,2753х9 + 42,850х10 +11,992х11 --0,61060х12 - 81,491х13 + 75,222х14 + .

Вісник Національного технічного університету України "КПІ" Серія — Радіотехніка. Радіоапаратобудування.-2010.-№41

135

Обчислювальна техніка та програмування

3) второй производной

d2 F (x) _

dx2

= -2,2853-

17,662x + 15,395x2 + 8,4914x3 + 26,277x4

+54,714x6 -53,829x7 - 54,678x8 + 428,50x9 + 131,91x10 - 7,3272x11 -

-55,820x5 +

11

-1059,4x12 +1053,1x12 - 909,20x14 +...

Радиус сходимости степенных рядов равен R = 0,35, и расчет изменений функции, ее первой и второй производных в пределах -0,35<=x<=0,35 обеспечивает точность расчета. В указанном интервале при значении x=0,26 функция F (x) имеет максимальное значение F(0,26)=1,0000 и убывает до предельного значения F(-0,35) = 0,46921. Чтобы определить период изменения функции, надо расширить пределы интервала в сторону x<-0,35. Для этого повторяем расчет функции с новым смещением x0 = - 0,35 и получаем новый степенной ряд функции

F(x) = 0,46921 + 0,56094x + 6,1930x2 - 35,189x3 +106,72x4 - 402,11x5 -

-5141,9x6 +1,9529 -105 x7

-4,05 08 -106 x8 + 7,3 7 63 • 107 x9

1,2664 • 109 x10 +

+1,9818-1010 x11 - 2,5116-1011 x12 +1,3776 4012 x13 + 6,1387 • 1013 x14 --3,3920 • 1015x15 +1,1991 • 1017x16 - 3,6006 • 1018x17 + 9,7338 • 1019x18 - .

Радиус сходимости нового степенного ряда R = 0,3, и расчет изменений необходимо проводить в пределах - 0,65 <= x <= - 0,05. В этом интервале функция F(x) имеет минимальное значение F(-0,4235) = 0,44717, т.е. четверть периода равно 0,6825.

X

4. Функция F = eD3 в точке x0 = 0.

В этом примере в среде Mathcad получены неверные значения производ-

d4 F d5 F

ных —т-т- = 0.0; —г-т- = 0.0. Правильные численные производные равны:

dx

4

dx

5

dF d 2F d 3F

~T = 2,5496; -~T = 94,547; = 4653,5;

dx dx dx

d 4 F d5 F

d F = 2,8921405; = 2,1672407;

dx4

dx5

d 6F

= 1,9029 40

9 .

d7 F

= 1,9173-10

11.

d8 F

= 2,1813 40

13.

d9 F

= 2,7663•10

15

dx6 ’ dx1 ’ dx^ ’ dx9

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

Литература

1. Бронштейн Н.Н., Семендяев К.А. Справочник по математике для инженеров и

136

Вісник Національного технічного університету України "КПІ" Серія — Радіотехніка. Радіоапаратобудування.-2010.-№41

Обчислювальна техніка та програмування

учащихся втузов. Изд. 13-е, испр.- М.: Наука - 1986. - 531 с.

2. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М.: Наука - 1968. - 720 с.

3. Фильчаков П.Ф. Численные и графические методы прикладной математики. -Киев: Наукова думка - 1970. - 792 с.

4. Каширский И.С., Трохименко Я.К. Обобщенная оптимизация электронных схем. - Киев: Техника - 1979. - 192 с.

Каширский И.С. Метод рекуррентных формул для научных исследований. В статье описан новый метод рекуррентных формул для численного расчета производных высоких порядков сложных функций. Сложность функций в том, что их аргументами являются не переменные, а полиномы от переменных. Метод удобен для ПК, имеет высокую точность и не ограничивает порядок вычисляемых производных.

Ключевые слова: рекуррентный, производная, полином

Каширський І.С. Метод рекурентних формул для наукових досліджень. В статті описан новий метод рекурентних формул для чисельного розрахунку похідних вищих порядків. Складність функцій полягає в тому, що їх аргументами є не змінні, а поліноми від змінних. Метод просто програмується, має високу точність розрахунку и не обмежує порядок обчислюваних похідних.

Ключові слова: рекурентний, похідна, поліном_____________________________________

Kashirsky I.S. Method of recurrent formulas for science research. This paper describes new method, based on recurrent formulas, for numerical calculation of derivatives for complicated functions. Arguments of those complicated functions are not simple variables, but poli-noms of variables. Method is easy for programming and has not any limits for order of derivatives.

Key words: recurrent, derivative, polynomial

УДК621.372

ПРОИЗВОДИТЕЛЬНОСТЬ И ОПТИМИЗАЦИЯ ПРОГРАММ.

ПОПУЛЯРНЫЕ АЛГОРИТМЫ

Реутская Ю.Ю., Новиченко А.А.

В современном мире программы все чаще становятся неотъемлемой частью различных устройств и систем (УиС), и многие программисты часто сталкиваются с ситуациями, когда вычислительной мощности оборудования недостаточно для успешной работы УиС. Оптимизация программ позволяет экономней использовать ресурсы питания во встраиваемых системах, повысить быстродействие программ обработки в реальном времени, уменьшить экономические затраты на оборудование.

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

Сложность алгоритмов будет оцениваться выражениями O(f(n)), где n — количество обрабатываемых данных, а f(n) — функция, асимптотичес-

Вісник Національного технічного університету України "КПІ" Серія — Радіотехніка. Радіоапаратобудування.-2010.-№41

137