Разыскивается формула численного дифференцирования.

[AD]

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

Так вот, нужно сочинить выражение вида

$$\frac{\hat F[x,x+h]-F''(x)}{\alpha h}\eqno(*)$$

(ну то есть сочинить выражение $\hat{F}$ и, на всякий случай, число $\alpha$) так, чтобы
1. слагаемое $\hat F[x,x+h]$ должно зависеть только от значений функции на отрезке $[x,x+h]$ (ну или $[x+h,x]$, если $h<0$), и, более того, должно быть симметрично относительно точки $h/2$ (То есть что-то типа $\hat F[x,x+h]=\hat F[x+h,x]$).

Например, требованию 1 удовлетворяет выражение $\hat F[x,x+h]=\frac{F(x+h)-2F(x+h/2)+F(x)}{h^2/4}$, и оно действительно хорошо смотрится в том смысле, что если третья производная у функции $F$ есть, то $(*)$ к ней сойдётся при $h\to0$. В-общем бредятина: используем симметричную производную как приближение левого края. Но вот надо.

2. Получающаяся производная должна быть точнее т.н. "пеановской" (сейчас объясню), причем не в смысле порядка сходимости на гладких функциях, а в смысле точного неравенства: если мы обозначим "пеановскую разность"

$$\Delta^3F(x;h)=\dfrac{\dfrac{\dfrac{F(x+h)-F(x)}h-F'(x)}{h/2}-F''(x)}{h/3}=\frac{F(x+h)-F(x)-hF'(x)-\frac{h^2}2F''(x)}{h^3/6}$$

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

$$\varliminf_{h\to0} \Delta^3F(x;h)\le \varliminf_{h\to0} \frac{\hat F[x,x+h]-F''(x)}{\alpha h}\le\varlimsup_{h\to0} \frac{\hat F[x,x+h]-F''(x)}{\alpha h}\le \varlimsup_{h\to0} \Delta^3F(x;h)$$

[Circiter]

Ничего не понял, но может быть вам как-нибудь может помочь автоматическое дифференцирование [получение значений производных $f'(x)$ как коэффициентов при делителе нуля $\varepsilon\ |\ \varepsilon^2=0\land\varepsilon\neq 0$ в выражении для $f(x+\varepsilon)$, i.e. с использованием алгебры дуальных чисел]? Вроде бы можно и до третьего порядка обобщить...

Даже литературы никакой по данной тематике незнаю, хотя где-то видел книжку Успенского про нестандартный анализ, может там есть что-нибудь такое...

[AD]

Circiter в сообщении #240645 писал(а):

Ничего не понял

+1 То есть я у Вас тоже ничего не понял. Успенский тоже был где-то, гляну, спасибо.

Но у меня вроде всё стандартное, функция $F:\mathbb{R}\to\mathbb{R}$, просто учусь точнее считать третью производную

[Circiter]

Я имел ввиду, что можно рассматривать исходную функцию на поле $\mathbb{R}$, расширенном ненулевым нильпотентом $\varepsilon^2=0$.

По определению производной $f'(x)=[f(x+\delta)-f(x)]/\delta$, $\delta\to 0$. При $\delta=\varepsilon$ получается, что $f(x+\varepsilon)=f(x)+f'(x)\varepsilon$. Тогда если дуальным числом назвать число вида $(\alpha,\beta)\equiv\alpha+\beta\varepsilon$, где $\alpha$ -- действительная, а $\beta$ -- инфинитезимальная часть числа, то вычислив функцию $f(\cdot)$ в точке $(x,1)$, получим другое число $(y,z)$, в котором $z$ -- первая производная от $f$.

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

При выполнении арифметических операций действительными частями манипулируют как обычно (складывают, умножают и т.д.), но с инфинитезимальными компонентами обращаются как будто ищут производную от результата. Например $(a,b)+(c,d)=(a+c,b+d)$, $(a,b)(c,d)=(ac,bc+ad)$, $(a,b)/(c,d)=(a/c,[bc-ad]/c^2)$, etc. Стандартные функции тоже расширяют на такие числа, e.g.: $\exp(a,b)=(e^a,e^a b)$, $\sin(a,b)=(\sin a,b\cos a)$ и т.д.

Это очень похоже на комплексные числа, которые получаются расширением действительных с помощью $i^2=-1$, только здесь $\varepsilon^2=0$. Вот в книжке Успенского как раз таки и ведется речь о всяких там гиперкомплексных обобщениях...

На самом деле такой прием в computer science где только не используют, так что можно вбить в поисковик что-то вроде automatic differentiation & dual numbers. Очень красиво это в C++ реализуется, исходная функция шаблонизируется и вычисляется в точке (обернутой в экземпляр класса дуального числа) с единичной бесконечно малой частью. Можно применить такую-же процедуру к результату и получить вторую производную, ну и так далее (точнее говоря искомую производную находят просто извлекая инфинитезимальную компоненту). Только приходится кучу операторов и математических функций перегружать, чтобы выполнялись все правила такой вот дуальной арифметики...

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

[ewert]

Circiter в сообщении #240746 писал(а):

Я имел ввиду, что можно рассматривать исходную функцию на поле $\mathbb{R}$, расширенном ненулевым нильпотентом $\varepsilon^2=0$.

Боюсь, что нельзя. Речь-то ведь шла о вполне конкретных вычислительных процедурах, а не о каких-то там абстрактных аксиоматиках.

(Хотя исходного вопроса я, каюсь, тоже не понял.)

[AD]

ewert в сообщении #240755 писал(а):

Боюсь, что нельзя.

+1.

-- Сб сен 05, 2009 20:21:59 --

AD в сообщении #240787 писал(а):

Хотя исходного вопроса я, каюсь, тоже не понял.

Так, ну если ewert не понял, то уже пора пояснять, да?

Ну вот можно сказать, что производная есть $f'(x)=\lim\limits_{h\to0}\frac{f(x+h)-f(x)}{h}$, а можно - что она есть $Df(x)=\lim\limits_{h\to0}\frac{f(x+h)-f(x-h)}{2h}$. Во втором случае по сравнению с первым произойдет две вещи:
1. У функции $f(x)=\frac1{x^2}$ будет в нуле производная, равная нулю. Ну и прочие уродства возникнут. Но очевидно, что если у функции была производная в обычном смысле, то будет и в таком такая же.
2. Производная будет лучше считаться, то есть предел будет быстрее сходиться. Например, при $x=0$ и $f(t)=t^2$ будет $f'(x)=0$, и при этом $\frac{f(x+h)-f(x)}{h}=h$, но $\frac{f(x+h)-f(x-h)}{2h}$, что стремится к нулю гораздо быстрее

Формализовать это дело можно двумя способами. Первый - оценить порядок сходимости на гладких функциях, как это принято в вычмате. То есть заметить, что для хороших $f$ будет $\frac{f(x+h)-f(x-h)}{2h}-f'(x)=O(h^2)$. Это иллюстрирует пункт 2.

Второй способ - это доказать неравенство $\underline{f}'(x)\le \underline{D}f(x)\le\overline{D}f(x)\le\overline{f}'(x)$, где черточки означают замену пределов на нижние / верхние пределы. То есть неравенство связывает "верхние" и "нижние" производные двух сортов. Этот способ интереснее, когда речь идет о плохих функциях $f$, то есть у которых еще фиг поймешь, существует производная или нет. Тогда такое неравенство покажет, что наша "симметричная" производная существует чаще.
_________________

Так вот, мне нужно проделать то же самое с третьей производной, считая "изначальным" определение производной по Пеано:
$F_{(3)}(x)=\lim\limits_{h\to0}\frac{F(x+h)-F(x)-hF'(x)-\frac{h^2}{2!}F_{(2)}(x)}{h^3/3!}$, где $F_{(2)}$ - это предполагаемая a priori существующей вторая производная в том же смысле: $F_{(2)}(x)=\lim\limits_{h\to0}\frac{F(x+h)-F(x)-hF'(x)}{h^2/2!}$, причем усиленность должна проверяться вторым способом (через неравенство для частичных пределов), а разностное соотношение, определяющее эту гипотетическую производную, должно обладать некоторой хитрой симметрией.
Что такое разностное соотношение вообще, и какими они бывают, я не знаю, в этом нечеткость постановки. Можно для конкретности искать его среди выражений вида

$$D^3F(x)=\lim_{h\to0}\frac{\int_0^{h/2}(F(x+t)+F(x+h-t))\,dG(ht)-F_{(2)}(x)}{\alpha h},$$

тогда симметрия автоматически есть, и получается задача: найти функцию $G\in\mathrm{VB}[0,1]$ такую, что как только функция $F$ разлагается в точке $x$ в ряд Тэйлора с остаточным членом в форме Пеано до $o(h^2)$ (это, очевидно, равносильно существованию $F_{(2)}$), то $\underline{f}'(x)\le \underline{D}f(x)\le\overline{D}f(x)\le\overline{f}'(x)$

-- Сб сен 05, 2009 20:25:20 --

Appendix:

AD в сообщении #240293 писал(а):

$\hat F[x,x+h]=\frac{F(x+h)-2F(x+h/2)+F(x)}{h^2/4}$,

Эту производную тоже понятно как записать в виде только что предложенного интегральчика, но неравенства для нее смотрят не в ту сторону. Причем строго. То есть она хуже пеановской.

[Circiter]

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

$$\sum_{i=-n}^n a_i f'(y_i)=\sum_{j=-n}^n b_j f(y_j),$$

где $y_k\equiv x+k\delta$ и $a_i$, $b_j$ -- просто числа, а потом находить производные из такого "рекуррентного" равенства (предварительно придумав нечно подобное для третьих производных)? Cf. компактные разностные схемы, кажется...

[Pavia]

Цитата:

должно быть симметрично относительно точки

Если бы это был придел, а не численное то да.

Цитата:

Так вот, мне нужно проделать то же самое с третьей производной, считая "изначальным" определение производной по Пеано:

Не понимаю. Зачем вы пытаетесь идти от Пеано когда хотите совсем другого.

$f'(x)=\lim\limits_{h\to0}\frac{f(x+h)-f(x-h)}{2*h}$

$f'''(x)=\frac{\frac{\frac{f(x+h+h+h)-f(x+h+h-h)}{2*h}-\frac{f(x+h-h+h)-f(x+h-h-h)}{2*h}}{2*h}-\frac{\frac{f(x-h+h+h)-f(x-h+h-h)}{2*h}-\frac{f(x-h+h-h)-f(x-h-h-h)}{2*h}}{2*h}}{2*h}=\frac{f(x+3*h)+f(x-h)-f(x+h)-f(x-3*h)}{8*h^3}$
Явно тут можно повысить точность если учесть взять точки с координатами кратными h. Вообще-то это еще доказать надо
Заменим $3h$ на $2c$
$\frac{f(x+2*c)+f(x-2/3*c)-f(x+2/3*c)-f(x-2*c)}{8/9*c^3}=\frac{f(x+2*с)-f(x-2*c)}{8/9*c^3}-\frac{f(x+2/3*c)-f(x-2/3*c)}{8/9*c^3}$ так как слева и справа у нас производные то в принципе правую часть мы можем переписать через придел и предти к другому размеру c

$\frac{f(x+2/3*c)-f(x-2/3*c)}{8/9*c^3}=\frac{1}{4/6*c^2}*\frac{f(x+2/3*c)-f(x-2/3*c)}{2/3*c}=>\frac{1}{4/6*c^2}*\frac{f(x+c)-f(x-c)}{2*c}$
собираем обратно
$\frac{f(x+2*c)-f(x-2*c)}{8/9*c^3}-\frac{f(x+с)-f(x-c)}{8/6*c^3}=\frac{f(x+2*с)-1/3*f(x+c)+1/3*f(x-c)-f(x-2*c)}{8/9*c^3}=\frac{9*f(x+2*c)-3*f(x+c)+3*f(x-c)-9*f(x-2*c)}{8*c^3}$

[AD]

Pavia в сообщении #242230 писал(а):

Зачем вы пытаетесь идти от Пеано когда хотите совсем другого.

Этими словами я заявляю, что хочу усилить Пеано, вот и всё.

Pavia в сообщении #242230 писал(а):

Если бы это был придел, а не численное то да.

Этого я не понял вообще. У меня требование такое - чтобы допредельное выражение имело указанный вид. Ваши формулы не тянут на

AD в сообщении #240293 писал(а):

$$F'''(x)\sim\frac{\hat F[x,x+h]-F''(x)}{\alpha h}$$

Давайте еще раз: вся $\hat F[x,x+h]$ должна определяться только значениями $F$ на $[x,x+h]$ (Ваши формулы симметричны относительно $x$, и потому не подходят), и быть симметричной относительно $x+h/2$ (поэтому не подходит пеановская).

А вообще спасибо, чувствую поддержку