具体数学-2-2第二章多重和.pptxVIP

具体数学Concrete Mathematics 04 十月 2023 2023/10/422.4 多重和Multiple Sums 2023/10/43多重和的表示方法一个和的项可能是由两个或多个指标来确定，例如两种（?数量）表达一般多指标求和的方法：利用“Iverson约定”对所有整数对j和k求和按特定次序求和，表示为多重∑??? 2023/10/44求和次序的交换交换求和次序的基本法则：具有多个指标的求和式可从任一指标开始求和（交换律和结合律在多指标求和中的应用，推广了结合律）从任一指标开始求和得到的结果是一致的。但是一般来说，从不同的指标入手，计算难度是不一样的。实际计算中往往选择从较简单的指标入手。? 2023/10/45求和次序交换的例子????推广：一般分配律 2023/10/46两种特定P(j,k)下的求和次序及交换（1）P(j,k)可表示为P(j) and P(k) 下标之间是独立的（2）p(j,k)不能表示为p(j) and p(k) 要求??? 2023/10/47第一种形式的例子（1）（2）?? 2023/10/48第二种形式的例子对下面的两重for循环，如果更换循环的顺序，应该怎么写？int s = 0;for (unsigned int j = 1; j n + 1; j ++) { for (unsigned int k = j; k n + 1; k ++) { s += a[j][k]; }} 2023/10/49第二种形式的例子前面的代码相当于计算在Iverson约定下考察如何变换循环的顺序：因此有一般来说，从j或k开始求和的难度是不同的。往往选择从容易的下标开始。??? 2023/10/410第二种形式的例子考虑具有n2个乘积aj ak的阵列目标是计算所有上三角元素之和，即?? 2023/10/411第二种形式的例子容易看出，该矩阵是对称的。因此 应该大约等于矩阵所有元素之和的一半：由于因此??????? 2023/10/412另外一个例子目标是计算注意到j和k的对称性，可以写成而且，在Iverson约定下有??? 2023/10/413另外一个例子因此将S的两个表达式相加，得到显然第2项为0。对于第1项，可以展成4项：??? 2023/10/414Chebyshev单调不等式因此得到如果有 ，则有如果有 ，则有?????切比雪夫不等式彼得堡学派创始人1821—1894 2023/10/415多重和中的交换律??? 2023/10/416一个多重和的concrete example目标是计算先尝试从j开始：??先对j求和用k-j替换j简化j的上下界使用调和数记号用k+1替换k简化k的上下界这里记H0 = 0 2023/10/417一个多重和的concrete example再尝试从k开始：?先对k求和用k+j替换k简化k的上下界使用调和数记号用n-j替换j简化j的上下界这里记H0 = 0结果和方法1一致 2023/10/418一个多重和的concrete example第三种方法：在将Sn表达成多重和之前，用k+j替换k。?计算目标用k+j替换k先在j上求和算出j上的和使用结合律很容易采用调和数记号 2023/10/419一个多重和的concrete example综合前面的三种不同方法，可以得到从代数、几何两种角度总结三种方法中的经验：代数：如果在被加项中有k+f(j)之类的表达式，可以将k替换成k-f(j)，然后在j上求和；几何：?? 2023/10/4202.5 General Methods一般方法总结 2023/10/4212.5 一般方法总结在掌握了求和的记号、求和与递归的关系，以及多重求和的有关技巧之后，对常见的求和方法做一个简明的列举和介绍。通过具体问题展开介绍：计算目标：求前n个平方和的封闭形式解。在解未知之前，将其记做□n ? 2023/10/422方法0~1方法0（查找书籍）： 去书里面查找到答案为 。注：(1) 知道去找什么书往往并不容易，需要积累；(2) 计算机科学或者数学自身内部也有很多方向，而且基本上是“隔行如隔山”，我们很难成为全能选手，所以快速、准确地找到需要的工具和结论是非常重要的，也是研究和开发工作中的关键本领。方法1（猜测证明）： Guess—Prove。首先猜出 再用数学归纳法证明。?? 2023/10/423方法0~1尽管方法0和方法1是常用的基本数学工具，但并