Méthodes générées pour l'évaluation polynomiale

algebra c# expression-trees linq math

Question

J'essaie de trouver un moyen élégant de gérer certains polynômes générés. Voici la situation sur laquelle nous allons nous concentrer (exclusivement) pour cette question:

  1. order est un paramètre permettant de générer un polynôme de n ordre, où n: = order + 1.
  2. i est un paramètre entier compris entre 0 et nn
  3. Le polynôme a des zéros à x_j, où j = 1..n et j… (il devrait être clair à ce stade que StackOverflow a besoin d'une nouvelle fonctionnalité ou qu'elle est présente et que je ne le connais pas).
  4. Le polynôme est évalué à 1 en x_i.

Puisque cet exemple de code particulier génère x_1 .. x_n, je vais expliquer comment ils se trouvent dans le code. Les points sont espacés de manière égale x_j = j * elementSize / order , où n = order + 1 .

Je génère un Func<double, double> pour évaluer ce polynôme¹.

private static Func<double, double> GeneratePsi(double elementSize, int order, int i)
{
    if (order < 1)
        throw new ArgumentOutOfRangeException("order", "order must be greater than 0.");

    if (i < 0)
        throw new ArgumentOutOfRangeException("i", "i cannot be less than zero.");
    if (i > order)
        throw new ArgumentException("i", "i cannot be greater than order");

    ParameterExpression xp = Expression.Parameter(typeof(double), "x");

    // generate the terms of the factored polynomial in form (x_j - x)
    List<Expression> factors = new List<Expression>();
    for (int j = 0; j <= order; j++)
    {
        if (j == i)
            continue;

        double p = j * elementSize / order;
        factors.Add(Expression.Subtract(Expression.Constant(p), xp));
    }

    // evaluate the result at the point x_i to get scaleInv=1.0/scale.
    double xi = i * elementSize / order;
    double scaleInv = Enumerable.Range(0, order + 1).Aggregate(0.0, (product, j) => product * (j == i ? 1.0 : (j * elementSize / order - xi)));

    /* generate an expression to evaluate
     *   (x_0 - x) * (x_1 - x) .. (x_n - x) / (x_i - x)
     * obviously the term (x_i - x) is cancelled in this result, but included here to make the result clear
     */
    Expression expr = factors.Skip(1).Aggregate(factors[0], Expression.Multiply);
    // multiplying by scale forces the condition f(x_i)=1
    expr = Expression.Multiply(Expression.Constant(1.0 / scaleInv), expr);

    Expression<Func<double, double>> lambdaMethod = Expression.Lambda<Func<double, double>>(expr, xp);
    return lambdaMethod.Compile();
}

Le problème: je dois aussi évaluer ψ… = dψ / dx. Pour ce faire, je peux réécrire ψ = scaleˆ— (x_0 - x) (x_1 - x) à - .. ˆˆ (x_n - x) / (x_i - x) sous la forme ψ = Î ± _nˆ x ^ n + Î ± _nÎ — x ^ (n-1) + .. + ± ± 1 — x + α ± 0. Cela donne ψ = nà — α ± n ^ (n-1) + (n-1) à — α _ n × x (n-2) + .. + 1 ±.

Pour des raisons de calcul, nous pouvons réécrire la réponse finale sans avoir à appeler Math.Pow en écrivant ψ = 2 × (x × (x × (..) - β_2) - β_1) - β_0.

Pour faire toute cette "ruse" (toute algèbre très basique), il me faut un moyen propre de:

  1. Développez une Expression factorisée contenant les feuilles ConstantExpression et ParameterExpression et les opérations mathématiques de base ( BinaryExpression avec le type NodeType défini sur l'opération). Le résultat ici peut inclure des éléments InvocationExpression dans le MethodInfo de Math.Pow que nous Math.Pow manière spéciale. tout au long de.
  2. Ensuite, je prends la dérivée par rapport à une certaine ParameterExpression spécifiée. Les termes du résultat où le paramètre de droite dans l'invocation de Math.Pow était la constante 2 sont remplacés par l' Math.Pow ConstantExpression(2) multipliée par celle qui était à gauche (l'invocation de Math.Pow(x,1) est enlevé). Les termes du résultat qui deviennent zéro parce qu'ils étaient constants par rapport à x sont supprimés.
  3. Ensuite, factorisez les occurrences de certaines ParameterExpression spécifiques où elles apparaissent en tant que paramètre de gauche pour un appel de Math.Pow . Lorsque le côté droit de l'invocation devient une ConstantExpression avec la valeur 1 , nous remplaçons l'invocation par la ParameterExpression elle-même.

¹ À l'avenir, j'aimerais que la méthode prenne une ParameterExpression et renvoie une Expression qui évalue en fonction de ce paramètre. De cette façon, je peux agréger les fonctions générées. Je ne suis pas encore là. ² À l'avenir, j'espère publier une bibliothèque générale permettant d'utiliser LINQ Expressions sous forme de calcul symbolique.

Réponse acceptée

J'ai écrit les bases de plusieurs fonctionnalités mathématiques symboliques à l'aide du type ExpressionVisitor dans .NET 4. Ce n'est pas parfait, mais cela ressemble au fondement d'une solution viable.

  • Symbolic est une classe publique statique qui expose des méthodes telles que Expand , Simplify et PartialDerivative
  • ExpandVisitor est un type d'assistance interne qui développe des expressions
  • SimplifyVisitor est un type d'assistance interne qui simplifie les expressions
  • DerivativeVisitor est un type d'assistance interne qui prend la dérivée d'une expression.
  • ListPrintVisitor est un type d'assistance interne qui convertit une Expression en une notation de préfixe avec une syntaxe Lisp.

Symbolic

public static class Symbolic
{
    public static Expression Expand(Expression expression)
    {
        return new ExpandVisitor().Visit(expression);
    }

    public static Expression Simplify(Expression expression)
    {
        return new SimplifyVisitor().Visit(expression);
    }

    public static Expression PartialDerivative(Expression expression, ParameterExpression parameter)
    {
        bool totalDerivative = false;
        return new DerivativeVisitor(parameter, totalDerivative).Visit(expression);
    }

    public static string ToString(Expression expression)
    {
        ConstantExpression result = (ConstantExpression)new ListPrintVisitor().Visit(expression);
        return result.Value.ToString();
    }
}

Expansion d'expressions avec ExpandVisitor

public static class Symbolic
{
    public static Expression Expand(Expression expression)
    {
        return new ExpandVisitor().Visit(expression);
    }

    public static Expression Simplify(Expression expression)
    {
        return new SimplifyVisitor().Visit(expression);
    }

    public static Expression PartialDerivative(Expression expression, ParameterExpression parameter)
    {
        bool totalDerivative = false;
        return new DerivativeVisitor(parameter, totalDerivative).Visit(expression);
    }

    public static string ToString(Expression expression)
    {
        ConstantExpression result = (ConstantExpression)new ListPrintVisitor().Visit(expression);
        return result.Value.ToString();
    }
}

Prendre un dérivé avec DerivativeVisitor

public static class Symbolic
{
    public static Expression Expand(Expression expression)
    {
        return new ExpandVisitor().Visit(expression);
    }

    public static Expression Simplify(Expression expression)
    {
        return new SimplifyVisitor().Visit(expression);
    }

    public static Expression PartialDerivative(Expression expression, ParameterExpression parameter)
    {
        bool totalDerivative = false;
        return new DerivativeVisitor(parameter, totalDerivative).Visit(expression);
    }

    public static string ToString(Expression expression)
    {
        ConstantExpression result = (ConstantExpression)new ListPrintVisitor().Visit(expression);
        return result.Value.ToString();
    }
}

Simplifier les expressions avec SimplifyVisitor

public static class Symbolic
{
    public static Expression Expand(Expression expression)
    {
        return new ExpandVisitor().Visit(expression);
    }

    public static Expression Simplify(Expression expression)
    {
        return new SimplifyVisitor().Visit(expression);
    }

    public static Expression PartialDerivative(Expression expression, ParameterExpression parameter)
    {
        bool totalDerivative = false;
        return new DerivativeVisitor(parameter, totalDerivative).Visit(expression);
    }

    public static string ToString(Expression expression)
    {
        ConstantExpression result = (ConstantExpression)new ListPrintVisitor().Visit(expression);
        return result.Value.ToString();
    }
}

Mise en forme d'expressions à afficher avec ListPrintVisitor

public static class Symbolic
{
    public static Expression Expand(Expression expression)
    {
        return new ExpandVisitor().Visit(expression);
    }

    public static Expression Simplify(Expression expression)
    {
        return new SimplifyVisitor().Visit(expression);
    }

    public static Expression PartialDerivative(Expression expression, ParameterExpression parameter)
    {
        bool totalDerivative = false;
        return new DerivativeVisitor(parameter, totalDerivative).Visit(expression);
    }

    public static string ToString(Expression expression)
    {
        ConstantExpression result = (ConstantExpression)new ListPrintVisitor().Visit(expression);
        return result.Value.ToString();
    }
}

Tester les résultats

public static class Symbolic
{
    public static Expression Expand(Expression expression)
    {
        return new ExpandVisitor().Visit(expression);
    }

    public static Expression Simplify(Expression expression)
    {
        return new SimplifyVisitor().Visit(expression);
    }

    public static Expression PartialDerivative(Expression expression, ParameterExpression parameter)
    {
        bool totalDerivative = false;
        return new DerivativeVisitor(parameter, totalDerivative).Visit(expression);
    }

    public static string ToString(Expression expression)
    {
        ConstantExpression result = (ConstantExpression)new ListPrintVisitor().Visit(expression);
        return result.Value.ToString();
    }
}



Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi