失眠网 > 简单的求导的符号运算算法

简单的求导的符号运算算法

时间：2022-09-21 17:37:26

相关推荐

简单的求导的符号运算算法

最近准备做一个有意思的事情，想实现基于符号运算法则来实现求导的算法。

现在做出了一个比较简单的雏形，写一篇博客总结一下，顺便介绍一下这个python小项目。

下面的思路和代码片段展现了我的思路，如果有感兴趣的同学应该可以写出实现，如果需要代码可以联系我。因为完整代码里面有很多无聊的提示信息和格式转化，所以我不打算放上来了。

表达式语法树

语法树

语法树是我这个项目里面所有表达式的存在形式，树的一个结点定义如下:

# the class of expression treeclass ExpTree:def __init__(self, op, args):self.op = opself.args = args

前缀表达式转化为语法树

算法比较简单，递归实现表达式解析即可:

# cast a expression string in scheme formation to a expression treedef expr_to_tree(line):# cast a expression element list in scheme formation to a expression treedef expr_list_to_tree(line_list):del line_list[0]op = line_list[0]del line_list[0]args = []while True:if line_list[0] == ')':del line_list[0]return ExpTree(op, args)if line_list[0] == '(':args.append(expr_list_to_tree(line_list))else:args.append(line_list[0])del line_list[0]line = line.replace('(', '( ')line = line.replace(')', ' )')line_list = line.split()return simplify(expr_list_to_tree(line_list))

对语法树求导

这里是算法的核心，这个版本只加入了二元运算的法则，一元函数的法则以后会加入。

算法为递归求导，规则如下:

1.叶子结点：x导数为1，常数导数为0。

2.非叶子结点，左右子树为l，r。那么结点的运算来递归求导:

( l + r ) ′ = l ′ + r ′ (l+r)'=l'+r' (l+r)′=l′+r′

( l − r ) ′ = l ′ − r ′ (l-r)'=l'-r' (l−r)′=l′−r′

( l ∗ r ) ′ = l ∗ r ′ + l ′ ∗ r (l*r)'=l*r'+l'*r (l∗r)′=l∗r′+l′∗r

( l / r ) ′ = ( l ′ ∗ r − l ∗ r ′ ) / ( r 2 ) (l/r)'=(l'*r-l*r')/(r^2) (l/r)′=(l′∗r−l∗r′)/(r2)

( l r ) ′ = ( r l r − 1 ) ∗ l ′ (l^r)'=(rl^{r-1})*l' (lr)′=(rlr−1)∗l′(这个版本因为不支持一元函数ln，所以r必须为常数表达式)

实现如下:

# get the derivate tree of the derivate of the tree expressiondef derivate(tree):if isinstance(tree, str):if tree == 'x':return '1'else:return '0'op = tree.opargs = tree.argsif op in ['+', '-']:a0 = args[0]a1 = args[1]return simplify(ExpTree(op, [derivate(a0), derivate(a1)]))elif op == '*':a0 = args[0]a1 = args[1]e1 = ExpTree('*', [derivate(a0), a1])e2 = ExpTree('*', [a0, derivate(a1)])return simplify(ExpTree('+', [e1, e2]))elif op == '/':a0 = args[0]a1 = args[1]nom = ExpTree('-', [ExpTree('*', [derivate(a0), a1]), ExpTree('*', [a0, derivate(a1)])])denom = ExpTree('^', [a1, '2'])return simplify(ExpTree('/', [nom, denom]))elif op in ['**', '^']:a0 = args[0]a1 = args[1]e1 = a1e2 = ExpTree('^', [a0, ExpTree('-', [a1 ,'1'])])return simplify(ExpTree('*', [ExpTree('*', [e1, e2]), derivate(a0)]))

表达式化简

因为上述的求导规则经常会产生0或者1项，例如:

( 2 ∗ x ) ′ = ( 2 ) ′ ∗ x + 2 ∗ ( x ) ′ = 0 ∗ x + 2 ∗ 1 (2*x)'=(2)'*x+2*(x)'=0*x+2*1 (2∗x)′=(2)′∗x+2∗(x)′=0∗x+2∗1

所以需要化简，规则为:

1. 0 + M = M + 0 = M 0+M=M+0=M 0+M=M+0=M

2. M − 0 = M M-0=M M−0=M

3. 1 ∗ M = M ∗ 1 = M 1*M=M*1=M 1∗M=M∗1=M

4. 0 ∗ M = M ∗ 0 = 0 0*M=M*0=0 0∗M=M∗0=0

5. M / 1 = M M/1=M M/1=M

6. 0 / M = 0 0/M=0 0/M=0

实现为:

# simplify a expression treedef simplify(tree):# judge whether ele is a constantdef is_constant(ele):if not isinstance(ele, str):return Falsereturn ele != 'x'# judge whether ele is a constant equal to vdef equ_to_constant(ele, v):eps = 1e-5if not is_constant(ele):return Falsereturn abs(float(ele) - v) < epsif isinstance(tree, str):return treearg_num = len(tree.args)for i in range(arg_num):tree.args[i] = simplify(tree.args[i])if tree.op == '+':for i in [0, 1]:if equ_to_constant(tree.args[i], 0):tree = tree.args[1 - i]return treeelif tree.op == '-':if equ_to_constant(tree.args[1], 0):tree = tree.args[0]return treeelif tree.op == '*':for i in [0, 1]:if equ_to_constant(tree.args[i], 0):tree = '0'return treeif equ_to_constant(tree.args[i], 1):tree = tree.args[1 - i]return treeelif tree.op == '/':if equ_to_constant(tree.args[0], 0):tree = '0'return treeif equ_to_constant(tree.args[1], 1):tree = tree.args[0]return treefor i in range(arg_num):if not is_constant(tree.args[i]):return treetree = str(calculate(tree, None))return tree

从语法树生成函数

容易实现求值函数calculate(tree, v)，可以递归计算树在x=v时候的值，那么我们怎么得到树对应的函数呢?

一个lambda表达式足矣:func = lambda x: calculate(tree, x)

注意这个高阶函数的用法。

演示

演示如下:

zzy@zzy-lenovo-g50-80:~/zzy/SICP$ python3 derivate.py
This is a little interpreter for scheme formation function and its’ derivate:
Scheme formation of f(x) = 2 * x + 1 is (+ 1 (2 x)).
f(x) is the function f(x), f(2) is the value f(x)|(x=2).
f, f’, f’’ or f’’’ is (high rank) derivates of f.
Please input f(x) in scheme formation or exit:
(x (^ (+ x 2) 3))
Please input expression or exit:
f(x)
(x (^ (+ x 2) 3))
(x * ((x + 2) ^ 3))
Please input expression or exit:
f’(x)
(+ (^ (+ x 2) 3) (* x (* 3 (^ (+ x 2) 2.0))))
(((x + 2) ^ 3) + (x * (3 * ((x + 2) ^ 2.0))))
Please input expression or exit:
f’’(x)
(+ (* 3 (^ (+ x 2) 2.0)) (+ (* 3 (^ (+ x 2) 2.0)) (* x (* 3 (* 2.0 (^ (+ x 2) 1.0))))))
((3 * ((x + 2) ^ 2.0)) + ((3 * ((x + 2) ^ 2.0)) + (x * (3 * (2.0 * ((x + 2) ^ 1.0))))))
Please input expression or exit:
f(0)
0.0
Please input expression or exit:
f’(0)
8.0
Please input expression or exit:
exit
Please input f(x) in scheme formation or exit:
exit
Thank you!