Как стать автором
Обновить

Комментарии 23

Их надо упрощать, для чего может быть написана отдельная функция. Упрощение выражений также рассматривается в SICP.

Упрощение выражений, конечно же, следует производить прямо в процессе вычисления производной, обрабатывая соответствующие варианты типа: X+0 = X, X*0 = 0, X*1 = X,
это существенно ускорит дальнейшую обработку при дифференцировании сложных выражений с большой вложенностью

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

В таком подходе есть свои плюсы. Рядом можно написать независимую функцию интегрирования и упрощать её результаты с помощью готового метода. Или написать функцию сложения или умножения выражений, и тоже упрощать результат, просто вызывая Symplify.

Кент Бек советовал следовать трём правилам при написании кода: сначала надо сделать так, чтобы код работал правильно; потом переписать его так, чтобы он был понятен; и лишь в конце его следует оптимизировать, если это, конечно, надо.

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

В таком подходе есть свои плюсы. Рядом можно написать независимую функцию интегрирования и упрощать её результаты с помощью готового метода. Или написать функцию сложения или умножения выражений, и тоже упрощать результат, просто вызывая Symplify
Один подход не противоречит другому, просто функцию упрощения следует применять непосредственно при обработке каждой из бинарных операций при дифференцировании
image
Есть и еще один аспект — выражения, упрощенные в процессе отыскания выражения для производной, при отладке намного удобнее того, что может получиться при дифференцировании даже относительно простых выражений без упрощений

Я ещё раз перечитал, прикинул и, думаю, вы правы.

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

Expression<Func<double, double>> expSquare = x => x * x;

он понимает, что не нужно генерировать код для лямбды, а нужно превратить ее в синтаксическое дерево? А для каких объектов это еще работает, кроме лямбд?

Да, в C# 3.5 завезли именно такой мощный вывод типов. Завозили, чтобы там работал LINQ и им было удобно пользоваться. Работает эта штука и для лямбд, и для других выражений, где используются деревья. Скажем, если LINQ запрос приводить к IQueryable<T>, он тоже не будет выполняться сразу, его нужно будет во что-то скомпилировать. В Entity Framework такие запросы компилируют в SQL, но можно обращаться и к обычным коллекциям дотнета.

imho, тут не нужен вывод типов. Компилятор всегда заранее знает (из контекста), интерпретировать выражение как AST (Expression) или как вычисляемое непосредственно.

Если я напишу что-то вроде

var v = x => x * x;

то что такое v - лямбда или дерево?

Это недопустимое выражения для C#
А вот если написать
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.
Ещё производные можно считать при помощи дуальных чисел. Это будет попроще манипуляций с деревом выражений и поточнее конечной разности — за исключением особых случаев типа sin(x)/x при x=0.
Аналитическое и численное дифференцирование — это совершенно разные области вычислений. При численном дифференцировании часто требуется находить значения первой и высших производных для функции, заданной не формулой, а поточечно. При этом могут использоваться несколько соседних точек, они позволяют вычислять производную в заданной точке намного точнее.
Кстати, формула   image, которую автор приводит в начале публикации, имеет точность порядка h, а формула для вычисления по предыдущей и последующей точкам   image — точность порядка h^2
Википедия предлагает ещё вариант с 4-мя и более точками. А если значения функции заданы поточечно, то имеет смысл использовать полиномиальную интерполяцию или МНК.
У многоточечных формул для численного дифференцирования есть существенный недостаток — для их применения требуется, чтобы шаг изменения аргумента был постоянным. В общем же случае, например, при применении МНК приходится для каждой точки решать системку линейных уравнений, зависящую от соседних точек — для линейной аппроксимации второго порядка, для квадратичной — третьего и т.д.
требуется, чтобы шаг изменения аргумента был постоянным
Не требуется, это просто в готовых формулах используют для удобства — на вики даже ссылка есть для произвольного количества произвольных. Они же получаются тоже из полиномиальной интерполяции — строим аналитический полином по n точкам, а затем он очень просто дифференцируется до нужного порядка. Другой вопрос, что вычислительную точность таким образом увеличить не получится, и это имеет смысл только для производных высшего порядка. А для обычных имеет смысл использовать расширенную точность в промежуточных вычислениях.
Не требуется, это просто в готовых формулах используют для удобства — на вики даже ссылка есть для произвольного количества произвольных
Сходил по ссылке, не увидел, как там можно пользоваться не равноотстоящими точками. Т.е. пользоваться то можно, конечно, но при изменении относительного положения точек формула изменяется, для получения этой формулы нужно решить систему линейных уравнений, различную для различных значений шага
Последняя точка - половинный шаг
image

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

Процедура для численного дифференцирования
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;

Для различных значений шага систему линейных уравнений решать не надо, потому что решение в общем виде достаточно легко выводится через произведение корней и сложение (лень подробно расписывать). Ну типа x*(x-x1)*(x-x2)*(x-x3)… очевидно что в точках x=x1,x=x2,x=x3 полином будет равен нулю.
Для различных значений шага систему линейных уравнений решать не надо, потому что решение в общем виде достаточно легко выводится через произведение корней и сложение (лень подробно расписывать)
Возможно, когда вам будет не лень, вы таки выпишете выражения для коэффициентов в общем виде, можно будет сравнить, а пока мне кажется, что приведенная выше работающая процедура является приемлемым простым решением
Всё уже придумано до нас и решение в общем виде известно как "Интерполяционный многочлен Лагранжа". Для равноотстоящих точек значения в явном виде выражаются через биномиальные коэффициенты, для произвольных чуть сложнее, но по схожей процедуре, через свёртку — программно несложно реализовать. В сети наверняка есть посвящённые этому работы, написанные чуть более авторитетными людьми.

приведенная выше работающая процедура является приемлемым простым решением
Если вы о процедуре (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();
        }
    }
}


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

в sicp и в этой статье описано в точности "символьное дифференцирование" (symbolic differentiation), у вас в статье по ссылке оно тоже упоминается. а вот чем от него отличается автоматическое, я что-то сходу из статьи на вики не понял. там видимо что-то среднее между численным и символьным

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Публикации

Истории