Documentation |
Simplify an expression
This functionality does not run in MATLAB.
Simplify(f) Simplify(f, Steps = numberOfSteps) Simplify(f, options)
Simplify(f) applies term-rewriting rules to f and returns the simplest expression it can find.
The methods of searching for the simplest representation of an expression are different for Simplify and simplify. The simplify function performs a linear search trying to improve the result returned by the previous simplification step. The Simplify function uses the results returned by all previous simplification steps (the best-first search). The simplify function is faster. The Simplify function is slower, but more effective and more configurable.
The term "simplest" is defined as follows. One object is simpler than another if it has smaller valuation. If two objects have the same valuation, Simplify chooses the simpler object using internal heuristics. A valuation is a function that assigns a nonnegative real number to each MuPAD^{®} object. To override the default valuation used by Simplify, use the Valuation option. Simplify uses the valuation for the best-first search as for determining the best result at the final step. However, you can define a separate method for the final simplification step by using the Criterion option.
The simplification process consists of steps. In each step, Simplify performs one of the following kinds of tasks for a := f or some (previously obtained) object a equivalent to f. In each step, Simplify can produce new objects equivalent to f (results) or new tasks to do or both:
Initial step: Find all rules for a. The Simplify function performs the search for all rules for every new object a. This search produces no new result.
Rewriting step: Apply one rule to a. This step can either fail or produce an equivalent object as result.
Subexpression step: Perform one step in simplifying an operand of a. Replace the operand with the returned result (if there are any results). This step can produce a new equivalent object.
Each open task has a priority that determines what to do next. Simplification terminates in any of the following cases:
There are no more open tasks.
Simplify reached the time limit specified by Seconds.
Simplify performed the maximal number of simplification steps specified by Steps.
Simplify returned the object specified by Goal.
Simplify always returns the "simplest" equivalent object found in all simplification steps unless you specify another OutputType.
Rules form a particular domain Rule. They consist of a pattern (left side), an expression (right side), and options.
MuPAD organizes rules for Simplify in rule bases. You can change the default rule base by using the RuleBase option. You also can define your own rule selection mechanism by using the SelectRules option.
Typically, Simplify applies the selected rules to the given object a as a whole. The following case is an exception from this rule. If the pattern of the rule and the object a are both a sum or a product, then Simplify applies the rule to each subsum or subproduct of a that has the same number of operands as the pattern.
By using the ApplyRule option, you can specify your own function that applies a particular rule to a particular object. Otherwise, Simplify uses a default method.
The application of a rule to an object a fails if the pattern does not match (see match) the object a. The performance of Simplify strongly depends on the number of successful matches. Therefore, if you specify your own rule base, it must dispose of non-matching rules before rule selection.
A simplification step for an operand works like a simplification step on simplifying f. The exceptions are as follows. Performing a simplification step for an operand, MuPAD does not apply certain rules (see the details on SelectRules).
MuPAD determines priorities of open tasks as follows. The priority of doing the initial step for an expression depends on the valuation of the expression. The priority of doing a simplification step on an operand depends on the ratio between the overall valuation of the expression and the valuation of the operand and the priority of the highest-rank task in the to-do list of the operand. Finally, the priority of applying a rule to an expression equals to the priority of the rule multiplied by the valuation of the expression.
The strategy determines the priority of a rule. See the Strategy option for details.
Simplify never uses the symmetry of mathematical equivalence of expressions. Therefore, you can use Simplify as a general rewriting system.
Simplify maps to lists, sets, and tables.
For domain elements d, Simplify can be overloaded in two ways. First, Simplify uses the slot d::dom::Simplify. If that slot does not exist, Simplify uses d::dom::simplify. If the slot that Simplify uses is not a list, Simplify calls the slot and accepts the result as simple (even if the valuation does not agree). In this case, Simplify does not apply any other rules to d. However, Simplify uses the valuation to decide whether it must replace a domain element that occurs as an operand in another object with its "simplified" version. If the slot is a list, its entries must be rules, and Simplify applies them according to their priority.
The easiest way to use Simplify is to accept all defaults, and then plug in the expression you want to simplify:
Simplify(sin(x)^2 + cos(x)^2)
By default, Simplify returns only one expression that the function considers as simplest. To return a list of all equivalent expressions, use the All option:
Simplify(sin(x)^2 + cos(x)^2, All)
The output of the previous example is short because as soon as the simplifier finds 1, it stops immediately. After that, the simplifier does not look for other equivalent expressions. In addition, the simplifier discards the equivalent expressions that are significantly more complicated than the best expression found earlier. You can switch off both mechanisms:
Simplify(sin(x)^2 + cos(x)^2, All, Discard = FALSE, IsSimple = FALSE)
By default, Simplify uses a valuation that favors expressions with fewer different irrational subexpressions. For example, Simplify assumes that an expression containing only sin(x) or cos(x) is simpler than an expression containing both:
Simplify(cos(x)*sin(x))
If you take the length as a complexity measure for expressions, Simplify returns another result:
Simplify(cos(x)*sin(x), Valuation = length)
The default number of steps is 100. To change the maximal number of possible simplification steps, use the Steps option. For example, decrease (resulting in a speedup) and increase (resulting in a probably better simplification) the number of simplification steps:
f := ln(x) + ln(3) - ln(3*x) + (exp(x) - 1)/(exp(x/2) + 1): Simplify(f, Steps = 8), Simplify(f, Steps = 120)
delete f:
For many expressions, the default number of simplification steps does not allow the simplifier to find a good simplification:
Simplify(e^(a* x *(a + 1) + b2* y *(y + b2* x* y)))
Increasing this limit often helps:
Simplify(e^(a* x *(a + 1) + b2* y *(y + b2* x* y)), Steps=125)
By default, simplification functions do not combine logarithms:
Simplify(ln(x^3 - 1) - ln(x - 1))
Using the IgnoreAnalyticConstraints option, you often can get shorter results:
Simplify(ln(x^3 - 1) - ln(x - 1), IgnoreAnalyticConstraints)
You can write the same expression in different coordinate systems. For example, use Cartesian and polar coordinates:
assume(x/r = cos(Symbol::theta)): assumeAlso(y/r = sin(Symbol::theta)): assumeAlso(r = sqrt(x^2+y^2)): x/sqrt(x^2+y^2) + I*y/sqrt(x^2+y^2) = exp(I*Symbol::theta); Simplify(%)
The following expression is equivalent to exp(x):
a := -1/(sin(1/2*I*x)^2 + 4*sin(1/4*I*x)^4 - 4*sin(1/4*I*x)^2 + 1)*(sin(1/2*I*x)^2 - 4*I*sin(1/2*I*x)*sin(1/4*I*x)^2 + 2*I*sin(1/2*I*x) - 4*sin(1/4*I*x)^4 + 4*sin(1/4*I*x)^2 - 1)
Simplify recognizes the equivalence of a and exp(x) within 100 steps. To show how the function proves the equivalence at each step, use the OutputType option. Note that the proof returned by Simplify is not a proof in a strict mathematical sense. Simplify uses the rules from the default rule base:
Simplify(a, OutputType = "Proof")
Input was -(sin((x*I)/2)^2 - 4*sin((x*I)/2)*sin((x*I)/4)^2*I + 2*sin((x*I)/2)*I - 4*sin((x*I)/4)^4 + 4*sin((x*I)/4)^2 - 1)/(sin\ ((x*I)/2)^2 + 4*sin((x*I)/4)^4 - 4*sin((x*I)/4)^2 + 1) Applying the rule Simplify::combineSinCos gives cos(x*I) - sin(x*I)*I Applying the rule Simplify::expand gives cosh(x) + sinh(x) Applying the rule X -> rewrite(X, exp) gives exp(x) END OF PROOF
You also can use Simplify for experiments with formal grammars given by only a few rules. In this case, the better approach is not to use rule bases, but to use a SelectRules method that returns a list of all rules. The following example presents a general associative operator ?. The example computes the number of all possible placements of parentheses. First, define the operator, and then attach it to a function that controls its output (see funcenv). Specify that the only applicable rule is the associative law. In the call to Simplify, set the number of steps to a very large value to perform a complete search. Note that most grammars produce infinitely many words and spend infinite time to finish a complete search:
_f := funcenv(() -> procname(args())): operator("?", _f, Binary, 1000): R := Rule((X ? Y) ? Z, X ? (Y ? Z)): selectProc := () -> [R]: S := Simplify(u ? v ? x ? y ? z, Steps = 10^10, SelectRules = selectProc, All):
PRETTYPRINT := FALSE: print(Plain, S): PRETTYPRINT := TRUE:
[u ? (v ? (x ? (y ? z))), u ? (v ? ((x ? y) ? z)), u ? ((v ? (x ? y)) ? z), u ? (((v ? x) ? y) ? z), u ? ((v ? x) ? (y \ ? z)), (u ? (v ? x)) ? (y ? z), ((u ? v) ? x) ? (y ? z), (u ? v) ? (x ? (y ? z)), (u ? v) ? ((x ? y) ? z), (u ? (v ? (x\ ? y))) ? z, (u ? ((v ? x) ? y)) ? z, ((u ? (v ? x)) ? y) ? z, (((u ? v) ? x) ? y) ? z, ((u ? v) ? (x ? y)) ? z]
There are 14 possible ways of placing parentheses:
nops(S); delete fout, _f, R, S, selectProc: operator("?", Delete):
If you want to specify a larger set of rules, the best approach is to use your own rule base. A classic example is differentiation. Although a heuristic search must be slower than a simple recursive algorithm, this example is suitable for demonstrating some efficiency considerations. Start by defining a function environment mydiff that does not do anything:
mydiff := funcenv(mydiff): mydiff::type := "mydiff"
The goal of this definition is to show that MuPAD sorts rules in rule bases by the types of expressions to which MuPAD applies those rules. Therefore, mydiff gets its own type. Now, define a rule base Myrules with the usual differentiation rules. Do not use any additional rules:
Myrules := newDomain("Myrules"): Myrules::mydiff := [Rule(mydiff(f, x), 0, {(f, x) -> not has(f, x)}), Rule(mydiff(x, x), 1), Rule(mydiff(x^n, x), n*x^(n - 1)), Rule(mydiff(f*g, x), f*mydiff(g, x) + g*mydiff(f, x)), Rule(mydiff(f + g, x), mydiff(f, x) + mydiff(g, x)) ]:
This rule base works for the expression x^{2}:
Simplify(mydiff(x^2, x), RuleBase = Myrules)
However, the rule base does not work for the following expression:
Simplify(mydiff(x + 3, x), RuleBase = Myrules)
Try to improve that rule base. As a first step, increase the number of simplification steps. Increasing the number of steps does not help in this case:
Simplify(mydiff(x + 3, x), RuleBase = Myrules, Steps = 200)
As a second step, take a closer look on the equivalent expressions returned by Simplify. Sometimes, Simplify finds the expected result, but does not return it because the valuation of the expected result is higher than the valuation of some other equivalent expression. For the expression x + 3, the Simplify function does not find the expected result:
l := Simplify(mydiff(x + 3, x), RuleBase = Myrules, All)
Note that the derivative of 1 appears in the result. Use the OutputType option, to check how Simplify manipulates the third term l[3] and how it proves the equivalence of input and output at each step:
Simplify(mydiff(x + 3, x), RuleBase = Myrules, Goal = l[3], OutputType = "Proof")
Input was mydiff(x + 3, x) Applying the rule mydiff(f*g, x) -> f*mydiff(g, x) + g*mydiff(f, x) gives (x + 3)*mydiff(1, x) + mydiff(x + 3, x) END OF PROOF
Now you can see that for each expression f, you must specify the rule for diffentiating products because f = 1 f. Modify that rule:
(Myrules::mydiff)[4] := Rule(mydiff(f*g, x), f*mydiff(g, x) + g*mydiff(f, x), {(f, g) -> f <> 1 and g <> 1}):
The updated rule base works:
Simplify(mydiff(x + 3, x), RuleBase=Myrules, Remember=FALSE)
Use a few options to optimize the call to Simplify. As a first step, measure how many steps a typical example takes before returning the expected output:
Simplify(mydiff(5*x^4 + x^3 + x^2 + x + 1, x), RuleBase = Myrules, Steps = 2000, Goal = 20*x^3 + 3*x^2 + 2*x + 1, OutputType = "NumberOfSteps")
Avoid the application of the equality f = f + 0. Switch off the remember mechanism. When the remember mechanism works, Simplify ignores changes in the rule base:
Myrules::mydiff[5] := Rule(mydiff(f + g, x), mydiff(f, x) + mydiff(g, x), {(f, g) -> f <> 0 and g <> 0}): Simplify(mydiff(5*x^4 + x^3 + x^2 + x + 1, x), RuleBase = Myrules, Steps = 2000, Goal = 20*x^3 + 3*x^2 + 2*x + 1, OutputType = "NumberOfSteps", Remember = FALSE)
Next, try to change the valuation criteria. For example, use length:
Simplify(mydiff(5*x^4 + x^3 + x^2 + x + 1, x), RuleBase = Myrules, Steps = 2000, Goal = 20*x^3 + 3*x^2 + 2*x + 1, OutputType = "NumberOfSteps", Valuation = length)
To optimize the call to Simplify, you also can specify your own simplification strategy. For example, the first rule seems to provide a very useful simplification whenever it applies. Therefore, assign a high priority to this rule by assuming that on average this rule simplifies its input to 0.03 of the original complexity:
Myrules::mydiff[1] := subsop(Myrules::mydiff[1], 4 = table("MyStrategy" = 0.03)): Simplify(mydiff(5*x^4 + x^3 + x^2 + x + 1, x), RuleBase = Myrules, Steps = 3000, Goal = 20*x^3 + 3*x^2 + 2*x + 1, OutputType = "NumberOfSteps", Strategy = "MyStrategy")
When using the valuation length, you get the following result:
Simplify(mydiff(5*x^4 + x^3 + x^2 + x + 1, x), RuleBase = Myrules, Steps = 3000, Goal = 20*x^3 + 3*x^2 + 2*x + 1, OutputType = "NumberOfSteps", Strategy = "MyStrategy", Valuation = length)
When you use a matcher-based simplification, most of the rules do not match to most objects. Trying to match all rules to all objects produces many failing rewriting steps. The recommended approach is to discard these failing rules during the initial step. Discarding failling rules decreases the number of steps. It also increases the running time per step by a small amount. Defining a procedure instead of a list of rules can help you to discard the failing rules during an initial step. You can define the rules by using a pattern or a procedure as their first argument:
Myrules::mydiff := proc(df) begin [if not has(op(df, 1), op(df, 2)) then Rule(X -> 0) else case type(op(df, 1)) of "_plus" do Rule(X -> map(op(X, 1), mydiff, op(X, 2))); break of "_mult" do Rule(mydiff(f*g, x), f*mydiff(g, x) + g*mydiff(f, x)); break of "_power" do Rule(X -> op(X, [1,2])*op(X, [1,1])^(op(X, [1,2]) - 1)); break of DOM_IDENT do assert(op(df, 1) = op(df, 2)); Rule(X -> 1); break otherwise null() end_case end_if] end_proc: Simplify(mydiff(5*x^4 + x^3 + x^2 + x + 1, x), RuleBase = Myrules, Steps = 200, Goal = 20*x^3 + 3*x^2 + 2*x + 1, OutputType = "NumberOfSteps")
delete Myrules, mydiff:
All |
When you use the All option, the Simplify function returns a list of all equivalent objects that the function can find. This syntax is a shortcut for OutputType = "All". |
ApplyRule |
Option, specified as ApplyRule = applyFunction Specify the function applyFunction that Simplify calls every time when a rule R must be applied to an object a. Here, applyFunction must be a function of two arguments R (a rule) and a (an object). It must return the result of applying the rule R to an object a. If the rule is not applicable, the applyFunction function must return FAIL. |
Discard |
Option, specified as Discard = discardFunction Specify the function discardFunction(newvalue, bestvalue) that Simplify calls every time it finds a new object equivalent to f. Here newvalue is the valuation of the new object, and bestvalue is the minimal valuation among all equivalent objects that Simplify found earlier. If Boolean evaluation of the result produces TRUE, then Simplify discards the new object. By default, Simplify discards a result if its valuation exceeds 10×current best valuation + 1. To prevent the loss of results, switch this mechanism off: Discard = FALSE. |
Criterion |
Option, specified as Criterion = CriterionFunction Specify the function CriterionFunction(a, vala) that Simplify calls at the end of the computation to perform the final sorting of the results. For each result a and its valuation vala, CriterionFunction(a, vala) returns a number. Simplify uses that number to sort the results. By default, Simplify uses vala to sort the results. |
Goal |
Option, specified as Goal = a If the Simplify function finds the equivalent object a, stop the computation and return a even if this object is not the simplest equivalent expression found. |
IgnoreAnalyticConstraints |
With this option the simplifier applies the following rules to expressions:
With this option, the Simplify function can return simple results for expressions for which Simplify without this option returns more complicated results. With this option the simplifier does not guarantee the equality of the initial expression and the result for all symbolic parameters. See Example 7. |
IsSimple |
Option, specified as IsSimple = B Specify the function B(a) that the Simplify function calls for any expression a that is equivalent to any subexpression of the input. If the result of the call is TRUE, then the Simplify function does not simplify this subexpression any further. B must return TRUE or FALSE for every input. |
KernelSteps |
Option, specified as KernelSteps = n Limit the effort invested in one simplification step. Here n must be a positive integer. The default value is 100. |
OutputType |
Option, specified as OutputType = output Specify the type of return value. The value output must be one of the strings "All", "Best", "NumberOfSteps", or "Proof". This option makes Simplify return all results, the best result, the number of performed simplification steps, or a proof for the equivalence of the input and the best result. By default, Simplify returns the simplest result found. Even if you specify the output type as "All", Simplify does not return any results discarded due to the Discard option. To get all results, set Discard to FALSE. See Example 3. If you set this option to "Proof", the Simplify function returns text displaying proof steps and lemmas. Proof steps state that f_{i - 1} is equivalent to f_{i} for 1 ≤ i ≤ n, where f_{0} = f is the input and f_{n} is the result of the simplification. Each proof step is either a rule application or a lemma application. A rule application step shows that applying a rule to f_{i - 1} gives f_{i}. A lemma application steps shows that replacing some operand of f_{i - 1} by an equivalent object gives f_{i}. A lemma consists of the statement that two objects are equivalent, a proof in the above sense, and the END OF LEMMA tag. Technically, proofs are objects of the same type as the output of expose. |
Remember |
Option, specified as Remember = bool The Remember option switches the remember mechanism on and off. If you call Simplify with the same argument several times, the remember mechanism saves running time. If the argument of one call reappears as a subexpression in the argument of another call, the remember mechanism does not help to save time. By default, bool is TRUE. |
RuleBase |
Option, specified as RuleBase = base A rule base base is a domain that contains its rules for expressions of type T in its slot slot(base, T). In addition, the following three slots can contain rules for a rule base: base::All, base::Global, and base::Local. The base::All slot contains generally applicable rules. The base::Global slot contains rules that the Simplify function applies only to expressions. Simplify does not apply the rules defined in base::Global within a subexpression step. The base::Local slot contains rules that the Simplify function applies only within a subexpression step. If no slots exist for the type of a given object, MuPAD does not generate any rules for that object. A slot of a rule base is a list of rules or a procedure that returns such a list for any given object of appropriate type. Any rule must be an object of type Rule. See the Rule help page for details. If you use your own SelectRules, you can ignore these conventions. See Example 11. |
Seconds |
Option, specified as Seconds = t When you use the Seconds option, the Simplify function limits the time allowed for the internal simplification process. The value t is the maximal time in seconds. By default, the simplification process never terminates due to a time limitation: t = infinity. |
SelectRules |
Option, specified as SelectRules = selFunction When you use the SelectRules option, MuPAD lets you specify the function selFunction(base, ex, global, strat) that Simplify calls to obtain the rules applicable to ex in the rule base base for strategy strat. The boolean flag global indicates whether ex is the whole expression accepted by Simplify (global = TRUE) or a subexpression of the original expression (global = FALSE). Using the arguments given to selFunction is optional. For example, for small rule bases the easiest method is to return a list of all rules independent of the given expression. See Example 10. However, returning a list of all rules can result in unnecessary rule applications. Applying each unnecessary rule returns FAIL and only affects the performance. You can define any rule base and use any kind the rules. The only restriction is that selFunction must return a list of rules. |
Steps |
Option, specified as Steps = numberOfSteps When you use the Steps option, the Simplify function terminates a simplification after numberOfSteps simplification steps. The default number of steps is 100. |
StopIf |
Option, specified as StopIf = B When you use the StopIf option, the Simplify function lets you specify the function B(a) that Simplify calls for any expression a that is equivalent to the original expression. If the result is TRUE, the simplification stops immediately, and the Simplify function returns the expression a as the simplest result regardless of its valuation. The specified function B must return TRUE or FALSE for any input. |
Strategy |
Option, specified as Strategy = strat When you use the Strategy option, the Simplify function lets you set the rule selection strategy. The value of strat must be a string. The SelectRules option uses strat as an argument that determines the priority for applying each rule. By default, Simplify uses the strategy "Default". The default rule base also uses the strategy "Default". If a particular rule does not recognize the strategy strat, the Simplify function uses the strategy "Default" to determine the priority of that rule. Finally, if no entry for the default strategy is available, the rule has the priority 1. In this case, expect an output to be as complicated as the input. If you use the IgnoreAnalyticConstraints, Simplify uses the strategy that comes with that option instead of using the strategy "Default". If Simplify uses a strategy, that strategy does not affect the valuation of results of rule applications. |
Valuation |
Option, specified as Valuation = valFunction When you use the Strategy option, the Simplify function lets you specify a function MuPAD uses for computing valuations of returned objects. Simplify computes the valuation for many intermediate results. Generally, to compute the valuation, Simplify evaluates each node of the expression tree. Therefore, the Valuation option can significantly affect the running time. A good valuation is a compromise between context-free and maximum-type concepts. For a context-free valuation, both the operator of an expression and the valuations of the operands determine the valuation of the expression. For a maximum-type valuation, generally the valuation of an expression equals the maximum of valuations of its operands. A typical context-free example is length. A typical maximum-type example is X -> 2^nops(indets(X)) . MuPAD offers a context-free valuation Simplify::complexity. This valuation favors usual operators like exp over unusual ones like besselJ and puts a penalty factor on arguments of unusual operators. |
Simplify returns an object mathematically equivalent to the input. With the option OutputType = "All", the Simplify function returns a list of all equivalent objects found during the simplification. With the option OutputType = "NumberOfSteps", the function returns a positive integer. With the option OutputType = "Proof", the function returns a string containing a proof of the equivalence of the input and the result.