Expression Облегчение

Question

У меня есть этот код для вычисления производных:

(define (diff x expr) 
    (if (not (list? expr)) 
    (if (equal? x expr) 1 0) 
    (let ((u (cadr expr)) (v (caddr expr))) 
    (case (car expr) 
     ((+) (list '+ (diff x u) (diff x v))) 
     ((-) (list '- (diff x u) (diff x v))) 
     ((*) (list '+ 
        (list '* u (diff x v)) 
        (list '* v (diff x u)))) 
     ((/) (list ‘div (list '- 
        (list '* v (diff x u)) 
        (list '* u (diff x v))) 
        (list '* u v))) 
)))) 

Как можно упростить алгебраические выражения?

вместо x + x показать 2x

и

вместо x * x показать x^2

Answer 1

Пожалуй this code из PAIP будет полезно. Это Common Lisp, который очень похож на Scheme. Точкой входа является функция simp.

Обратите внимание, что он также использует this file.

Историческая справка: В соответствующей главе PAIP содержится ссылка на Macsyma, систему компьютерной алгебры, разработанную в Массачусетском технологическом институте в 1960-х годах и являющуюся основой для Mathematica, Maple (теперь в Matlab) и других инструментов.

Answer 2

Вот начало:

Изменение вашей производной функции от (define (diff x expr) ...) к чему-то вроде (define (simp expr) ...).

для x + x случае, сделать что-то вроде

(case (car expr) 
    ((+) (if (equal u v) ; check for identical subexpressions 
     `(* ,(simp u) 2) ; if u==v, simplify 2u 
     `(+ ,(simp u) ,(simp v)))) 
    ...) 

x * x случай должен быть похож. В конце концов вы можете конвертировать if в cond, если вам нужно сделать много разных упрощений.

Это трудная задача для решения полностью, и ссылки, которые дает eliben, стоит посмотреть.

Answer 3

Упрощение алгебраических выражений довольно сложно, особенно по сравнению с вычислением производных. Упрощение должно выполняться рекурсивно. Сначала вы упрощаете самые сокровенные выражения. Не пытайтесь слишком много за раз. Я хотел бы начать с самым основными упрощениями только например:

0 + x -> x 
0 * x -> 0 
1 * x -> x 
x^0 -> 1 
x^1 -> x 

Заменить вычитание путем сложения и делением умножения

x - y -> x + (-1)*x 
x/y -> x^(-1) 

это может выглядеть как упрощение, но это упростит код. Вы всегда можете отменить этот шаг в конце.

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

(x * y) * z -> x * (y * z) 
x * 2 -> 2 * x 
2 * (x * 3) -> 2 * (3 * x) 

Simplify экспонент

(x^y)^z -> x^(y * z) 

Упростить числовую частей.

2 * (3 * x) -> 6 * x 
2 + (3 + x) -> 5 + x 

Как только вы это сделаете, вы можете подумать о сборе общих выражений.

Answer 4

Общая проблема сложна, но вы можете получить длинный путь с нормальной формой суммы продуктов, представленной как конечное отображение из ключа (имя переменной) в коэффициент. Эта форма отлично подходит для линейных уравнений и линейного решения, и она может быть распространена на умножение и полномочия без особых проблем. Если вы определяете «умные конструкторы» для арифметики на этой форме, вы можете получить разумное символическое дифференцирование и решение уравнений.

Это быстрый взлом, но я использовал его в нескольких приложениях. Несколько из них работали; пару раз это было недостаточно. Для чего-то более серьезного вы говорите годы работы.

Если вы хотите привести примеры кода, вы можете прочитать о one of my equation solvers.