Pull to refresh

Comments 50

О, не знал, что может быть такое практическое применение, но d^2 = 0 меня сильно смущает.

P.S.: Мне кажется или дейстивительно здесь ошибка:

df(a: double): double
{
f(Dual(a,1)).Imaginary
}
В чем, это Nemerle, а в нем new при вызове конструктора не указывается, return не пишется. Так что все ОК. Или ошибка в семантике?
До этого я вроде дошёл. «Похоже мне кажется». Просто с непривычке, трудно проследить ход вычислений. Распишите, пожалуйста, подробней.

Начал разбираться. Насколько хорошо здесь работает оптимизация?
Ну всё, дошёл. Можно ещё один глупый вопрос? Сколько будет d^3?
Как эмпирический метод это конечно круто.

Но к комплексным числам это не имеет никакого отношения, даже по аналоги. Чисел (действительных) являющихся решением уравнения x^2 + 1 = 0 не существует, мы вводим «другие» числа, в которых оно имеет решение. Действительные и мнимые числа нигде не порождают противоречий, поэтому их можно использовать «совместно». Уравнение x^2 = 0 имеет решение в действительных числах x=0, при введении «дуальных» чисел оно имеет решение и в них x=d.

В коде, по-моему, (в том числе и для C++) видно, что нигде не применяется условие d^=0. «Просто» эмулируются символьные вычисления, т.е. не производится «умножение/сложение» на d, до этапа вычисление второго коэффициента в разложении Тейлора, т.е. первой производной, остальные просто игнорируются. И похоже у функциональных языков здесь явное преимущество именно в предварительной оптимизации, и как мне кажется, в данном случае, отсечение/сокрашение лишних вычислений (шаблоны в C++ в таком применении выглядят как костыль).

Аналогичным методом можно ввести (n+1)-арные (раз эти дуальные) числа, т.е. не вычислять d, d^2, d^3,...,d^n, и соответственно получить n-ю производную (учитывая конечно дополнительные множители в коэффициентах).

Дополнение к предыдущему моему комменту.

n-арное число в данном рассмотрении по сути и есть набор коэффициентов разложения Тейлора. Т. е. коэффициентов при d^0, d^1, (1/2)*d^2, (1/6)*d^3,...,(1/(n!)*d^n.

Для константы a это будет: (a,0,0,...,0).
Для x: (x,1,0,0,...,0).
Для x^2: (x^2,2*x,2,0,0,...).
Для sin(x): (sin(x), cos(x),-sin(x),...).
И т.д.
По-моему, так и работают системы символьных вычислений.

В данном посте рассматриваются два первых коэффициента. И применяется «рекурсивное» вычисление n-ой производной. (А введение d^2=0, по-моему бред сивой кобылы).

В общем, спасибо за наводку, поразмышляю над этим на досуге.
«Занимаясь чем-то ненормальным вы рискуете нарваться на ненормального» — хабромудрость ;-).
Так, ну и кто мне минус влепил, а, признаёмся!!!
Спасибо за освещение хорошего подхода. Хотя конечно не очень приятно объявлять функцию с аргументами класса Dual, вариант с шаблонами в C++ мне больше понравился.
Если вы преобразуете ваш результат «сокращения» ряда Тейлора, то увидите, что вы получили ту же самую формулу f'(x) ~ (f(x + d) — f(x)) / d, которую вы посчитали недостаточно точной.
конечно, так и есть. но здесь отсутствует собственно деление на d и вычисление разности двух значений ф-ции(кстати череватое ошибками машинной точности). Здесь получается идеальный случай d->0
Вы взяли этот d за единицу. Приглядитесь к формулам — вычисление производной будет формулой f(x + 1) = f(x) + f'(x).

Ещё — вы не можете пользоваться вашей мнимой единицей в поле комплексных чисел, которое расширение чисел действительных. Потому что там нет делителей нуля. А если пользуетесь, то там вообще полматана не определено и дифференцирование неизвестно что даст.
Вообще, точного численного дифференцирования не существует в данный момент. Однако есть множество методов приблеженного вычисления производных достаточно высоких порядков с хорошей точностью.
где Вы увидели что d=0? Если это про запись f(Dual(a,1)) то здесь имеется ввиду a+1*d. И где речь шла о комплексных числах? Про доказуемость дифференцируемости спорить не буду, тут нужно думать и смотреть. Может автор топика подскажет что нибудь
В этих формулах d это не переменная, а значение; так же как и i в комплексном случае, поэтому вместо него брать 1 некорректно, то есть тождество f(x + 1) = f(x) + f'(x) не выполняется.

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

Правда ненормальное программирование )
Удобство в том, что для каждой новой функции производные пишутся один раз. Остальное получается автоматически из алгебраических свойств дифференцирования.
Как эмпирический метод это конечно круто.

Но к комплексным числам это не имеет никакого отношения, даже по аналоги. Чисел (действительных) являющихся решением уравнения x^2 + 1 = 0 не существует, мы вводим «другие» числа, в которых оно имеет решение. Действительные и мнимые числа нигде не порождают противоречий, поэтому их можно использовать «совместно». Уравнение x^2 = 0 имеет решение в действительных числах x=0, при введении «дуальных» чисел оно имеет решение и в них x=d.

В коде, по-моему, (в том числе и для C++) видно, что нигде не применяется условие d^=0. «Просто» эмулируются символьные вычисления, т.е. не производится «умножение/сложение» на d, до этапа вычисление второго коэффициента в разложении Тейлора, т.е. первой производной, остальные просто игнорируются. И похоже у функциональных языков здесь явное преимущество именно в предварительной оптимизации, и как мне кажется, в данном случае, отсечение/сокращение лишних вычислений (шаблоны в C++ в таком применении выглядят как костыль).

Аналогичным методом можно ввести (n+1)-арные (раз эти дуальные) числа, т.е. не вычислять d, d^2, d^3,...,d^n, и соответственно получить n-ю производную (учитывая конечно дополнительные множители в коэффициентах).

n-арное число в данном рассмотрении по сути и есть набор коэффициентов разложения Тейлора. Т. е. коэффициентов при d^0, d^1, (1/2)*d^2, (1/6)*d^3,...,(1/(n!)*d^n.

Для константы a это будет: (a,0,0,...,0).
Для x: (x,1,0,0,...,0).
Для x^2: (x^2,2*x,2,0,0,...).
Для sin(x): (sin(x), cos(x),-sin(x),...).
И т.д.
По-моему, так и работают системы символьных вычислений.

В данном посте рассматриваются два первых коэффициента. И применяется «рекурсивное» вычисление n-ой производной. (А введение d^2=0, по-моему бред сивой кобылы).

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

Но если отталкиваться от кода, то можно действительно заметить, что это он является частной оптимизацией работы с рядом тейлора, когда нас интересует только первый порядок малости.
Я упёртый и настайваю на своём.

И i^2 = -1, i^3=-i и можно «считать дальше», а d^2=0, d^3=0,...,d^n=0 и «облом дальше», вот.
Это разные точки зрения на один и тот же код.

В чем облом?
В том что это эмпирический метод, который срабатывает только для первой производной и всё. Его нельзя использовать для вычисления, например, второй производной по формуле f(x+d) = f(x) + f'(x)*d + f''(x)*(1/2)*d^2, нежно считать d^2 «невычислимой», а у вас d^2=0. Ни проще ли использовать общий метод с набором коэффициентов, а не вводить для вычисления n-ой производной n разных мегачисел.

Т.е. по аналогии с комплексными числами, кватернионами и т.д. Ввести числа компоненты которых будут соответствующими коэффициентами разложения Тейлора (Как в моем комменте выше). И определить для них операции (как в посте). При реализации используем свойство/определение производных f(n)(x) = (f(n-1)(x))', и реализуем операции для первой производной, а остальные определяем через неё рекурсивно. Т.е. так как у вас и сделано, но без эмпирических примочек, которые в общем неверны.
В коде используются соответствующие формулы дифференцирования относительно умножения и деления, по-моему, это очевидно и доказывать нечего.

И меня смущает деление, не проще ли написать:

Dual(a.real/b.real, ((a.imaginary*b.real)-(b.imaginary*a.real))/(b.real*b.real)).

Это проще, если отталкиваться от того, что этот код оптимизация работы с рядом (ваша точка зрения). Я его писал как реализацию кольца действительных чисел дополненных d. В этом случае: a/b определяется как a*b-1, где b*b-1=1, для этого я решил уравнение (a+b*d)(x+y*d)=1 относительно x и y, и получил, что x=1/a; y=-b/(a*a) поэтому там такой код.
Ну всё, сдаюсь :) Я впервые анализировал код на Nemerle, это маленькое достижение.
А как с оптимизацией. Вот напишу я:

f(a: Dual): Dual { a*a+3.0/a }
f(a: double): double { f(Dual(a,0)).Real }
df(a: double): double { f(Dual(a,1)).Imaginary }

он мне при компиляции сократит до df(a: double): double { 2*a-3.0/(a^2) }?

Поздравляю.

Сомневаюсь, что это сократит компилятор, но вполне вероятно, что это сделает JIT, если Dual пометить как sealed. Знаю точно, что Nemerle оптимизирует хвостовую рекурсию локальных функций (объявленных внутри метода).
А если ввести бесконечно малое число d, и далее как у вас. Результат будет тот же, так?
Видимо это моя проблема, но ух как мне не нравится эта nilpotent-ность при дифференцировании. Лучше вводить «бесконечно малое число».
И да, и нет. Отбрасывание бесконечномалой порядка k очень похоже на то, что она является нильпотентной порядка k, но в первом случае мы оперируем бесконечным рядом и пределами, а во втором вполне конкретной алгебраической структурой.
При введении «бесконечно малого числа», ничего не обнуляется и не отбрасывается, так только с пределами так можно, и то не всегда. Например, как в дискретке с производящими ф., берём соответствующий коэффициент ряда при разложении. А «порядок малости» рассматривается как и для обычных чисел меньших единицы: d^n больше d^(n+1) — и всё. Также получается конкретная алгебраическая структура с прикольным числами z1=x1+y1*d, z2=x1+y1*d^2,… и z1>z2, ну и т.д. Просто чуть другим «языком» получается почти «дословно» матан, что не так круто, как «вообще другая» алгебра, по-моему.
Здесь вы не правы) можно ввести числа для третьей и тд производных:

вводим d и e:
d^2=2 e
e^2=0

Тогда числа a0+a1*d+a2*e при умножении/сложении обладают теми же алгебраическими свойствами, что и f, f', f''.
d^3 = 0
разделим на d (он же не равен нулю ;-))
d^2 = 0/d
разделим на d ещё раз
d = 0/d^2
заметим, что d^2 = 0
d = 0/0

чак норрис, я узнал тебя XD
Подскажите, пожалуйста, а где это может применяться?
Там, где нужно численно дифференцировать. Этот метод использовался в софте, который использовался при post-production фильмов Matrix Reloaded и Matrix Revolution.
Жаль, что так можно дифференцировать только простые функции. Что делать с производными типа х^x или более сложными я не понял :(
(кроме как численные методы использовать)
Метод можно обобщить на функции от двух переменных — нужно будет расширить вещественные числа двумя нульпотентными элементами.
Спасибо, почитаю вечером подробно. Сейчас, при чтении по диагонали споткнулся об haskell на 6-7 страницах, до этого совпадает с тем, что здесь описано.
Что мне в нём понравилось — благодаря возможности переписывания операторов (особенности языка, конечно) мы можем записывать выражение естественным образом. У Вас это тоже есть. Однако, использовав ленивость by default мы бесплатно получаем целую цепочку производных

x = dVar value
f = x^3
f' = df f
f'' = df f'

и т.д.

Причём реализация этого очень проста:

data Dif a = C a | D a (Dif a) -- второй конструктор содержит выражение (функцию) и производную.

dVar value = D value 1.0 -- маленький кирпичик, из которого всё собирается.

p@(D x x’) * q@(D y y’) = D (x*y)(x’*q+p*y’) -- правило Лейбница

df (D _ p) = p -- "вычисление" производной (форсируем ленивый thunk)


Например, let x = dVar 3.0 in df (df (x^3)) вернёт нам 18.0
А можно чуть подробней про «Таким образом, что бы узнать значение производной функции f в точке x достаточно взять коэффициент при мнимой части числа f(x+d).»? Как это получилось и что за коэффициент, а то немного не догоняю :)
Главное не показывать Dual «наружу», а использовать только для определения функций.
Для простых действий вы описали производную в правилах арифметических операций над dual-числами.

Для более сложных вам придётся «вбивать» производную в определение функции.

Более того, нельзя называть 'd' «мнимой единицей», так как: 1) имя занято, 2) «мнимая единица» i не меняет модуля комплексного числа. Для дуальных чисел модуль не определён. И, очевидно, (a+b*d) * d = a*d.

Кстати, в wikipedia не говорится, что это разложение в ряд Тэйлора. Там просто раскрывают полином.
Only those users with full accounts are able to leave comments. Log in, please.