다항식 평가를위한 생성 방법
-
06-07-2019 - |
문제
나는 생성 된 다항식을 다루는 우아한 방법을 생각해 내려고 노력하고 있습니다. 다음은이 질문에 대해 (독점적으로) 집중할 상황입니다.
- 주문하다 생성의 매개 변수입니다 NTh order polynomial, 여기서 n : = order + 1.
- 나 범위 0..n의 정수 매개 변수입니다
- 다항식은 X_J에 0을 가지고 있는데, 여기서 J = 1..N 및 J ≠ I (이 시점에서 STACKOVERFLOW가 새로운 기능이 필요하거나 현재 존재한다는 것이 명확해야합니다).
- 다항식은 X_I에서 1로 평가합니다.
이 특정 코드 예제는 X_1을 생성하기 때문에 X_N이므로 코드에서 어떻게 찾을 수 있는지 설명하겠습니다. 포인트는 균등하게 간격을두고 있습니다 x_j = j * elementSize / order
별로, 어디에 n = order + 1
.
나는 a를 생성한다 Func<double, double>
이 다항식 ¹.
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();
}
문제 : 또한 ψ ′ = dψ/dx를 평가해야합니다. 이렇게하려면 ψ = scale × (x_0 -x) (x_1 -x) × .. × (x_n -x)/(x_i -x)를 다시 작성할 수 있습니다. ^(n-1) + .. + α_1 × x + α_0. 이것은 ψ '= n × α_n × x^(n-1) + (n-1) × α_n × x^(n-2) + .. + 1 × α_1을 제공합니다.
계산 이유로, 우리는 전화없이 최종 답변을 다시 작성할 수 있습니다. Math.Pow
ψ ′ = x × (x × (x × (..) - β_2) - β_1) -β_0을 작성함으로써.
이 모든 "Trickery"(매우 기본적인 대수)를하려면 다음과 같은 깨끗한 방법이 필요합니다.
- 고려 된 것을 확장하십시오
Expression
포함ConstantExpression
그리고ParameterExpression
잎과 기본 수학적 작업 (끝납니다BinaryExpression
이랑NodeType
작업으로 설정) - 여기에 결과에는 포함 할 수 있습니다.InvocationExpression
요소MethodInfo
~을 위한Math.Pow
우리는 전체적으로 특별한 방식으로 처리 할 것입니다. - 그런 다음 지정된 일부와 관련하여 파생물을 취합니다.
ParameterExpression
. 오른쪽 매개 변수가Math.Pow
상수 2가ConstantExpression(2)
왼쪽이 무엇인지 곱한 것 (Math.Pow(x,1)
제거). 결과의 용어는 x와 관련하여 일정했기 때문에 0이되는 용어가 제거됩니다. - 그런 다음 특정 인스턴스를 고려하십시오
ParameterExpression
왼쪽 매개 변수로 발생하는 곳Math.Pow
. 호출의 오른쪽이ConstantExpression
가치와 함께1
, 우리는 호출을만으로 대체합니다ParameterExpression
그 자체.
¹ 미래에, 나는 방법을 ParameterExpression
그리고 반환 Expression
그것은 그 매개 변수를 기반으로 평가합니다. 그렇게하면 생성 된 기능을 집계 할 수 있습니다. 나는 아직 거기에 없다. ² 향후, 나는 LINQ 표현을 상징적 수학으로 작업하기위한 일반 라이브러리를 출시하고자합니다.
해결책
나는 expressionvisitor .NET 4를 입력하십시오. 완벽하지는 않지만 실행 가능한 솔루션의 기초처럼 보입니다.
Symbolic
공개 정적 클래스 노출 방법과 같은 공개 정적 클래스입니다Expand
,Simplify
, 그리고PartialDerivative
ExpandVisitor
표현을 확장하는 내부 도우미 유형입니다SimplifyVisitor
표현식을 단순화하는 내부 도우미 유형입니다DerivativeVisitor
표현식의 미분을 취하는 내부 도우미 유형입니다.ListPrintVisitor
변환하는 내부 도우미 유형입니다Expression
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();
}
}
표현 확장 ExpandVisitor
internal class ExpandVisitor : ExpressionVisitor
{
protected override Expression VisitBinary(BinaryExpression node)
{
var left = Visit(node.Left);
var right = Visit(node.Right);
if (node.NodeType == ExpressionType.Multiply)
{
Expression[] leftNodes = GetAddedNodes(left).ToArray();
Expression[] rightNodes = GetAddedNodes(right).ToArray();
var result =
leftNodes
.SelectMany(x => rightNodes.Select(y => Expression.Multiply(x, y)))
.Aggregate((sum, term) => Expression.Add(sum, term));
return result;
}
if (node.Left == left && node.Right == right)
return node;
return Expression.MakeBinary(node.NodeType, left, right, node.IsLiftedToNull, node.Method, node.Conversion);
}
/// <summary>
/// Treats the <paramref name="node"/> as the sum (or difference) of one or more child nodes and returns the
/// the individual addends in the sum.
/// </summary>
private static IEnumerable<Expression> GetAddedNodes(Expression node)
{
BinaryExpression binary = node as BinaryExpression;
if (binary != null)
{
switch (binary.NodeType)
{
case ExpressionType.Add:
foreach (var n in GetAddedNodes(binary.Left))
yield return n;
foreach (var n in GetAddedNodes(binary.Right))
yield return n;
yield break;
case ExpressionType.Subtract:
foreach (var n in GetAddedNodes(binary.Left))
yield return n;
foreach (var n in GetAddedNodes(binary.Right))
yield return Expression.Negate(n);
yield break;
default:
break;
}
}
yield return node;
}
}
파생물을 복용합니다 DerivativeVisitor
internal class DerivativeVisitor : ExpressionVisitor
{
private ParameterExpression _parameter;
private bool _totalDerivative;
public DerivativeVisitor(ParameterExpression parameter, bool totalDerivative)
{
if (_totalDerivative)
throw new NotImplementedException();
_parameter = parameter;
_totalDerivative = totalDerivative;
}
protected override Expression VisitBinary(BinaryExpression node)
{
switch (node.NodeType)
{
case ExpressionType.Add:
case ExpressionType.Subtract:
return Expression.MakeBinary(node.NodeType, Visit(node.Left), Visit(node.Right));
case ExpressionType.Multiply:
return Expression.Add(Expression.Multiply(node.Left, Visit(node.Right)), Expression.Multiply(Visit(node.Left), node.Right));
case ExpressionType.Divide:
return Expression.Divide(Expression.Subtract(Expression.Multiply(Visit(node.Left), node.Right), Expression.Multiply(node.Left, Visit(node.Right))), Expression.Power(node.Right, Expression.Constant(2)));
case ExpressionType.Power:
if (node.Right is ConstantExpression)
{
return Expression.Multiply(node.Right, Expression.Multiply(Visit(node.Left), Expression.Subtract(node.Right, Expression.Constant(1))));
}
else if (node.Left is ConstantExpression)
{
return Expression.Multiply(node, MathExpressions.Log(node.Left));
}
else
{
return Expression.Multiply(node, Expression.Add(
Expression.Multiply(Visit(node.Left), Expression.Divide(node.Right, node.Left)),
Expression.Multiply(Visit(node.Right), MathExpressions.Log(node.Left))
));
}
default:
throw new NotImplementedException();
}
}
protected override Expression VisitConstant(ConstantExpression node)
{
return MathExpressions.Zero;
}
protected override Expression VisitInvocation(InvocationExpression node)
{
MemberExpression memberExpression = node.Expression as MemberExpression;
if (memberExpression != null)
{
var member = memberExpression.Member;
if (member.DeclaringType != typeof(Math))
throw new NotImplementedException();
switch (member.Name)
{
case "Log":
return Expression.Divide(Visit(node.Expression), node.Expression);
case "Log10":
return Expression.Divide(Visit(node.Expression), Expression.Multiply(Expression.Constant(Math.Log(10)), node.Expression));
case "Exp":
case "Sin":
case "Cos":
default:
throw new NotImplementedException();
}
}
throw new NotImplementedException();
}
protected override Expression VisitParameter(ParameterExpression node)
{
if (node == _parameter)
return MathExpressions.One;
return MathExpressions.Zero;
}
}
표현을 단순화합니다 SimplifyVisitor
internal class SimplifyVisitor : ExpressionVisitor
{
protected override Expression VisitBinary(BinaryExpression node)
{
var left = Visit(node.Left);
var right = Visit(node.Right);
ConstantExpression leftConstant = left as ConstantExpression;
ConstantExpression rightConstant = right as ConstantExpression;
if (leftConstant != null && rightConstant != null
&& (leftConstant.Value is double) && (rightConstant.Value is double))
{
double leftValue = (double)leftConstant.Value;
double rightValue = (double)rightConstant.Value;
switch (node.NodeType)
{
case ExpressionType.Add:
return Expression.Constant(leftValue + rightValue);
case ExpressionType.Subtract:
return Expression.Constant(leftValue - rightValue);
case ExpressionType.Multiply:
return Expression.Constant(leftValue * rightValue);
case ExpressionType.Divide:
return Expression.Constant(leftValue / rightValue);
default:
throw new NotImplementedException();
}
}
switch (node.NodeType)
{
case ExpressionType.Add:
if (IsZero(left))
return right;
if (IsZero(right))
return left;
break;
case ExpressionType.Subtract:
if (IsZero(left))
return Expression.Negate(right);
if (IsZero(right))
return left;
break;
case ExpressionType.Multiply:
if (IsZero(left) || IsZero(right))
return MathExpressions.Zero;
if (IsOne(left))
return right;
if (IsOne(right))
return left;
break;
case ExpressionType.Divide:
if (IsZero(right))
throw new DivideByZeroException();
if (IsZero(left))
return MathExpressions.Zero;
if (IsOne(right))
return left;
break;
default:
throw new NotImplementedException();
}
return Expression.MakeBinary(node.NodeType, left, right);
}
protected override Expression VisitUnary(UnaryExpression node)
{
var operand = Visit(node.Operand);
ConstantExpression operandConstant = operand as ConstantExpression;
if (operandConstant != null && (operandConstant.Value is double))
{
double operandValue = (double)operandConstant.Value;
switch (node.NodeType)
{
case ExpressionType.Negate:
if (operandValue == 0.0)
return MathExpressions.Zero;
return Expression.Constant(-operandValue);
default:
throw new NotImplementedException();
}
}
switch (node.NodeType)
{
case ExpressionType.Negate:
if (operand.NodeType == ExpressionType.Negate)
{
return ((UnaryExpression)operand).Operand;
}
break;
default:
throw new NotImplementedException();
}
return Expression.MakeUnary(node.NodeType, operand, node.Type);
}
private static bool IsZero(Expression expression)
{
ConstantExpression constant = expression as ConstantExpression;
if (constant != null)
{
if (constant.Value.Equals(0.0))
return true;
}
return false;
}
private static bool IsOne(Expression expression)
{
ConstantExpression constant = expression as ConstantExpression;
if (constant != null)
{
if (constant.Value.Equals(1.0))
return true;
}
return false;
}
}
디스플레이를위한 서식 표현 ListPrintVisitor
internal class ListPrintVisitor : ExpressionVisitor
{
protected override Expression VisitBinary(BinaryExpression node)
{
string op = null;
switch (node.NodeType)
{
case ExpressionType.Add:
op = "+";
break;
case ExpressionType.Subtract:
op = "-";
break;
case ExpressionType.Multiply:
op = "*";
break;
case ExpressionType.Divide:
op = "/";
break;
default:
throw new NotImplementedException();
}
var left = Visit(node.Left);
var right = Visit(node.Right);
string result = string.Format("({0} {1} {2})", op, ((ConstantExpression)left).Value, ((ConstantExpression)right).Value);
return Expression.Constant(result);
}
protected override Expression VisitConstant(ConstantExpression node)
{
if (node.Value is string)
return node;
return Expression.Constant(node.Value.ToString());
}
protected override Expression VisitParameter(ParameterExpression node)
{
return Expression.Constant(node.Name);
}
}
결과 테스트
[TestMethod]
public void BasicSymbolicTest()
{
ParameterExpression x = Expression.Parameter(typeof(double), "x");
Expression linear = Expression.Add(Expression.Constant(3.0), x);
Assert.AreEqual("(+ 3 x)", Symbolic.ToString(linear));
Expression quadratic = Expression.Multiply(linear, Expression.Add(Expression.Constant(2.0), x));
Assert.AreEqual("(* (+ 3 x) (+ 2 x))", Symbolic.ToString(quadratic));
Expression expanded = Symbolic.Expand(quadratic);
Assert.AreEqual("(+ (+ (+ (* 3 2) (* 3 x)) (* x 2)) (* x x))", Symbolic.ToString(expanded));
Assert.AreEqual("(+ (+ (+ 6 (* 3 x)) (* x 2)) (* x x))", Symbolic.ToString(Symbolic.Simplify(expanded)));
Expression derivative = Symbolic.PartialDerivative(expanded, x);
Assert.AreEqual("(+ (+ (+ (+ (* 3 0) (* 0 2)) (+ (* 3 1) (* 0 x))) (+ (* x 0) (* 1 2))) (+ (* x 1) (* 1 x)))", Symbolic.ToString(derivative));
Expression simplified = Symbolic.Simplify(derivative);
Assert.AreEqual("(+ 5 (+ x x))", Symbolic.ToString(simplified));
}