Комментарии 23
Их надо упрощать, для чего может быть написана отдельная функция. Упрощение выражений также рассматривается в SICP.
Упрощение выражений, конечно же, следует производить прямо в процессе вычисления производной, обрабатывая соответствующие варианты типа: X+0 = X, X*0 = 0, X*1 = X,
это существенно ускорит дальнейшую обработку при дифференцировании сложных выражений с большой вложенностью
В SICP это предлагают делать именно так, но здесь я предпочёл писать (относительно) простые методы, каждый из которых делают свою работу. Своеобразное переложение принципа единственной ответственности для методов.
В таком подходе есть свои плюсы. Рядом можно написать независимую функцию интегрирования и упрощать её результаты с помощью готового метода. Или написать функцию сложения или умножения выражений, и тоже упрощать результат, просто вызывая Symplify
.
Кент Бек советовал следовать трём правилам при написании кода: сначала надо сделать так, чтобы код работал правильно; потом переписать его так, чтобы он был понятен; и лишь в конце его следует оптимизировать, если это, конечно, надо.
Возможно, и есть задачи, где требуется быстро дифференцировать десятки тысяч сложных выражений с большой вложенностью. Пожелаем удачи программистам, которые это пишут. Она им пригодится.
В таком подходе есть свои плюсы. Рядом можно написать независимую функцию интегрирования и упрощать её результаты с помощью готового метода. Или написать функцию сложения или умножения выражений, и тоже упрощать результат, просто вызывая SymplifyОдин подход не противоречит другому, просто функцию упрощения следует применять непосредственно при обработке каждой из бинарных операций при дифференцировании
Есть и еще один аспект — выражения, упрощенные в процессе отыскания выражения для производной, при отладке намного удобнее того, что может получиться при дифференцировании даже относительно простых выражений без упрощений
Я знаю C# весьма поверхностно, и не знал что лямбда-функции могут компилироваться в деревья выражений. Как это происходит? Вывод типов настолько мощный, что для выражения
Expression<Func<double, double>> expSquare = x => x * x;
он понимает, что не нужно генерировать код для лямбды, а нужно превратить ее в синтаксическое дерево? А для каких объектов это еще работает, кроме лямбд?
Да, в C# 3.5 завезли именно такой мощный вывод типов. Завозили, чтобы там работал LINQ и им было удобно пользоваться. Работает эта штука и для лямбд, и для других выражений, где используются деревья. Скажем, если LINQ запрос приводить к IQueryable<T>
, он тоже не будет выполняться сразу, его нужно будет во что-то скомпилировать. В Entity Framework такие запросы компилируют в SQL, но можно обращаться и к обычным коллекциям дотнета.
Если я напишу что-то вроде
var v = x => x * x;
то что такое v - лямбда или дерево?
А вот если написать
var v = (int x) => x * x;
или так Func<int,int> v = x => x * x;
будет лямбда, тип указан снаружи, в контексте использования выражения. А такExpression<Func<int,int>> t = x => x * x;
Уже будет Expression. Компилятору нужны подсказки из контекста.Ещё производные можно считать при помощи дуальных чисел. Это будет попроще манипуляций с деревом выражений и поточнее конечной разности — за исключением особых случаев типа sin(x)/x при x=0.Аналитическое и численное дифференцирование — это совершенно разные области вычислений. При численном дифференцировании часто требуется находить значения первой и высших производных для функции, заданной не формулой, а поточечно. При этом могут использоваться несколько соседних точек, они позволяют вычислять производную в заданной точке намного точнее.
Кстати, формула , которую автор приводит в начале публикации, имеет точность порядка h, а формула для вычисления по предыдущей и последующей точкам — точность порядка h^2
требуется, чтобы шаг изменения аргумента был постояннымНе требуется, это просто в готовых формулах используют для удобства — на вики даже ссылка есть для произвольного количества произвольных. Они же получаются тоже из полиномиальной интерполяции — строим аналитический полином по n точкам, а затем он очень просто дифференцируется до нужного порядка. Другой вопрос, что вычислительную точность таким образом увеличить не получится, и это имеет смысл только для производных высшего порядка. А для обычных имеет смысл использовать расширенную точность в промежуточных вычислениях.
Не требуется, это просто в готовых формулах используют для удобства — на вики даже ссылка есть для произвольного количества произвольныхСходил по ссылке, не увидел, как там можно пользоваться не равноотстоящими точками. Т.е. пользоваться то можно, конечно, но при изменении относительного положения точек формула изменяется, для получения этой формулы нужно решить систему линейных уравнений, различную для различных значений шага
Когда-то писАл программу, в которой использовалось численное дифференцирование, там формируется и решается маленькая системка на каждом шаге
procedure DiffTsNumLS(N:integer; var X,F,DF:LongVector; var RC:SmallInt);
{ получение производной временного ряда линейной МНК-аппроксимацией }
{ по соседним точкам }
var
DiffPnts : integer;
i, j, k, jlo, jhi : integer;
R, A11, A12, A21, A22, B1, B2, D : real;
begin
{ кол-во точек, по которым стррится линейная аппроксимация }
DiffPnts:=2*RcnSmoo+1;
for i:=1 to TsCnt do
begin
{ в крайних точках вычисляем по формулам дифференцирования }
{ назад (в начале) и вперед (в конце) второго порядка }
if i <= round((DiffPnts)/2) then
begin
D:=X[i+1]-X[i];
DF[i]:=(-3*F[i]+4*F[i+1]-F[i+2])/(2*D);
end
else if i >= TsCnt-round((DiffPnts-1)/2) then
begin
D:=X[i]-X[i-1];
DF[i]:=(F[i-2]-4*F[i-1]+3*F[i])/(2*D);
end
{ иначе используем линейную аппроксимацию }
else
begin
jlo:=i-round((DiffPnts-1)/2);
jhi:=i+round((DiffPnts-1)/2);
{ формируем лин.систему второго порядка для коэфф.лин.аппрокс.}
R:=0.0;
for j:=jlo to jhi do
R:=R+sqr(X[j]-X[i]);
A11:=R;
R:=0.0;
for j:=jlo to jhi do
R:=R+(X[j]-X[i]);
A12:=R;
A21:=A12;
A22:=DiffPnts;
R:=0.0;
for j:=jlo to jhi do
R:=R+F[j]*(X[j]-X[i]);
B1:=R;
R:=0.0;
for j:=jlo to jhi do
R:=R+F[j];
B2:=R;
{ значение производной-коэфф. A в выражении Y=A(X-X0)+B }
DF[i]:=(B1*A22-B2*A12)/(A11*A22-A12*A21);
end;
end;
end;
Для различных значений шага систему линейных уравнений решать не надо, потому что решение в общем виде достаточно легко выводится через произведение корней и сложение (лень подробно расписывать)Возможно, когда вам будет не лень, вы таки выпишете выражения для коэффициентов в общем виде, можно будет сравнить, а пока мне кажется, что приведенная выше работающая процедура является приемлемым простым решением
приведенная выше работающая процедура является приемлемым простым решениемЕсли вы о процедуре
(f(x+h) - f(x-h)) / (2*h)
— то она тоже верна только для равноотстоящих точек. Немного погоняв её по тестам подбирая h, я не смог получить точность результата выше половины исходной. Если двукратная потеря точности допустима — то да, вполне приемлемое решение. Но как я уже писал вам когда-то давно, в обработке сигналов такой фокус не всегда прокатит из-за наложения спектра, а коэффициенты (и их необходимое количество) считаются явным образом из произведения производной sinc-функции на оконную функцию. Да и в прочих случаях нет оснований полагать, что исходная функция наилучшим образом аппроксимируется именно полиномом.Если вы о процедуре (f(x+h) — f(x-h)) / (2*h) — то она тоже верна только для равноотстоящих точек.Нет, я о процедуре численного дифференцирования в этом комментарии. Она предназначена для дифференцирования при помощи линейной аппроксимации, работает для переменного шага и позволяет поэкспериментировать с количеством соседних точек. Её можно бы и обобщить, добавив туда параметром степень полинома для аппроксимации, но это уже намного сложнее. И кстати, в результате получится примерно то же самое, что предлагаете вы.
Вообще, как уже неоднократно бывало в дискуссиях с вами, в случае, когда я
я предлагаю демонстрирую готовое работающее решение, вы обычно оперируете понятиями типа «программно несложно реализовать»Ну да. Я могу сделать намного больше, чем уже сделал. И «несложно» не значит написать за 5 минут, а результат уместить в комментарий. «Несложно» значит, что можно написать за несколько часов/дней, а все проблемы в процессе решаются первой строчкой гугла.
Ну вот накидал я класс для работы с полиномами в C#:
using System;
using System.Text;
namespace Polynomial
{
public class Polynomial
{
public double[] data;
int order = 0;
public int Order { get { return order; } }
private Polynomial(int order)
{
this.order = order;
data = new double[order + 1];
}
public Polynomial(params double[] args)
{
order = args.Length - 1;
data = new double[order+1];
Array.Copy(args, 0, data, 0, args.Length);
}
public double this[int index]
{
get
{
if (index >= data.Length)
return 0;
return data[index];
}
set
{
if (index >= data.Length)
{
order = index;
double[] data2 = new double[index + 1];
Array.Copy(data, 0, data2, 0, data.Length);
data = data2;
}
data[index] = value;
}
}
public void Scale(double v)
{
for (int i = 0; i <= order; i++)
data[i] *= v;
}
public double Calc(double x)
{
double y = 0;
for (int i = order; i > 0; i--)
{
y += data[i];
y *= x;
}
y += data[0];
return y;
}
public static Polynomial Add(Polynomial p1, Polynomial p2)
{
Polynomial p3 = new Polynomial(Math.Max(p1.order, p2.order));
for (int i = 0; i <= p3.order; i++)
p3.data[i] = p1[i] + p2[i];
return p3;
}
public static Polynomial Sub(Polynomial p1, Polynomial p2)
{
Polynomial p3 = new Polynomial(Math.Max(p1.order, p2.order));
for (int i = 0; i <= p3.order; i++)
p3.data[i] = p1[i] - p2[i];
return p3;
}
public static Polynomial Multiply(Polynomial p1, Polynomial p2)
{
Polynomial p3 = new Polynomial(p1.order + p2.order + 1);
for (int i = 0; i <= p1.order; i++)
for (int j = 0; j <= p2.order; j++)
p3.data[i + j] += p1.data[i] * p2.data[j];
return p3;
}
public override string ToString()
{
string format = "0.0";
StringBuilder sb = new StringBuilder();
sb.Append(data[0].ToString(format));
for (int i = 1; i <= order; i++)
{
var v = data[i];
if (v >= 0.0)
{
sb.Append(" + ");
sb.Append(v.ToString(format));
if (i == 1)
{
sb.Append("*x");
}
else
{
sb.Append("*x^");
sb.Append(i.ToString());
}
}
else
{
sb.Append(" - ");
sb.Append((-v).ToString(format));
if (i == 1)
{
sb.Append("*x");
}
else
{
sb.Append("*x^");
sb.Append(i.ToString());
}
}
}
return sb.ToString();
}
}
}
И что? Мне он сейчас не нужен, вам он не нужен тем более, на практике потребуется оптимизация для частных случаев, чтобы не терять в производительности. Впустую потраченное время.
По-моему это звучит как автоматическое дифференциорвание. Кстати, вот реализация на хаскеле https://hackage.haskell.org/package/ad
Цитирование в языках программирования