离散微积分

  对 OIer 来说, 离散微积分主要用于计算这样一个问题:

    ? $$sum = \sum_{a \le i < b} f_i$$ .

  先回顾一些微积分的基础知识.

  微积分有微分算子 $D$ , 我们研究了常见函数的导数与导数的运算法则, 以及在最值问题和解方程上的应用.

  很多运算都是成对出现的, 我们定义了微分, 就存在着微分的逆运算: 不定积分(原函数系). 我们直接继续推广微分的结论, 得到了常见函数的不定积分以及不定积分的运算法则.

  最后从黎曼和开始, 引出了定积分的定义, 并且给出了微积分第一基本定理, 微积分第二基本定理, 联系了定积分, 不定积分与微积分.

  我们尝试类比微积分, 构造一种运算以得到解法, 我们称其为离散微积分.

  对应无限微积分的微分算子 $D$ , 不定积分 $\int$ , 定积分 $\int_a^b$ , 我们定义了差分算子 $\Delta$ , 不定和式 $\Sigma$ , 定和式 $\Sigma_a^b$ .

  $\Delta f(x) = f(x+1) - f(x)$ .

  微积分第二基本定理被类比为一个简化物.

  构造 $g$ , 使得 $\Delta g(x) = f(x)$ .

  $$\sum_{a \le i < b} f_i = \Sigma_a^b g(x) \delta x = f(x)|_a^b = \sum_{i = a}^b (g_{i+1} - g_i) = f_b - f_a$$ .

  我们尝试找到 $D(x^n) = n x ^ {n - 1}$ 的类似物.

  定义了下降幂 $x^\underline{n} = x (x-1) (x-2) ... (x-n+1)$ .

  ? 那么 $\Delta(x^\underline{n}) = nx^\underline{n-1}$ .

  并尝试将其扩充到 $n < 0$ 的情况, 例如 $x^\underline{-2} = \frac{1}{(x+1)(x+2)}$ .

  当 $n\ne -1$ 时, 对应有 $\Sigma x^{\underline{n}} = \frac{x^\underline{n+1}}{n+1} + C$ .

  当 $n = -1$ 时, $D(\ln x) = \frac{1}{x}$ , 我们发现了 $\ln x$ 的类似物, $\Delta H(x) = x^\underline{-1}$ .

  综上, 有 $$\Sigma_a^bx^\underline{n}\delta x = \left\{\begin{aligned}&\frac{x^\underline{n+1}}{n+1}|_a^b&n\ne -1\\ &H_x|_a^b&n = -1\end{aligned}\right.$$

  

  对于一般幂来说, 需要通过 Stirling数 或者 观察法 转化成下降幂后, 再进行求不定和.

  类似的, 我们尝试发掘 $c^x$ 这个常见函数.

  $\Delta c^x = c^{x+1} - c^x = (c-1)c^x$ .

  当 $c\ne 1$ 时, $\sum c^x = \frac{c^x}{c-1}$ .

  这也可以解释几何级数: $$\sum_{k = 0}^{n} c^k = \Sigma_0^{n+1} c^k\delta k = \frac{c^k}{c-1}|_0^{n+1} = {c^{n+1} - 1 \over c-1}$$ .

  尝试类比积分的分布求和法.

  定义 $Ev(x) = v(x+1)$ .

  推导得 $\Delta(uv) = u\Delta v + Ev\Delta u$ .

  $u\Delta v = \Delta(uv) - Ev\Delta u$ .

  对两边取不定和得 $\Sigma u\Delta v = uv - \Sigma Ev\Delta u$ .

  如果左边计算麻烦, 那么可以考虑转化为右边.

  ? 举个例子, 计算 $ans = \sum_{k = 0} ^ {n-1} k2 ^ k$ .

  ? 设 $u(x) = x, \Delta v(x) = 2 ^ x$ .

  ? 所以 $v(x) = 2 ^ x + C_1, Ev(x) = 2 ^ {x+1} + C_1, \Delta u(x) = 1$ .

  ? 所以
  $$
  \begin{aligned} ans & = \sum_{k = 0} ^ {n-1} k 2 ^ k \\ & = (u(x) \Delta v(x)) | _0 ^ n \\ & = [u(x)v(x) - Ev(x) \Delta u(x)] | _0 ^ n \\ & = n 2 ^ n - 2 ^ {n+1} - 2 \end{aligned}
  $$

时间: 09-14

离散微积分的相关文章

康复计划#3 简单常用的几种计算自然数幂和的方法

本篇口胡写给我自己这样的东西都忘光的残废选手 以及暂时还不会自然数幂和的人- 这里大概给出最简单的几种方法:扰动法(化为递推式),斯特林数(离散微积分),高阶差分(牛顿级数),伯努利数(指数生成函数)- 不同方法的思维难度.普适程度.实现难度.时间复杂度上面都有差异-同时自然数幂和是探究各种求和方法的经典例子,了解多一点它的做法对于处理各种求和问题是有所帮助的- 问题:求$\sum_{k=0}^{n} k^t$,其中$t \in \mathbb{N}$是一个常数.要求求解的时间复杂度与$n$无关

Mathematica

Mathematica是一款科学计算软件,很好地结合了数值和符号计算引擎.图形系统.编程语言.文本系统.和与其他应用程序的高级连接.很多功能在相应领域内处于世界领先地位,它也是使用最广泛的数学软件之一.Mathematica的发布标志着现代科技计算的开始.Mathematica是世界上通用计算系统中最强大的系统.自从1988发布以来,它已经对如何在科技和其它领域运用计算机产生了深刻的影响. Mathematica和MATLAB.Maple并称为三大数学软件. 软件名称 Mathematica 开

大学里面重要的课程

首先说一下 搞了acm 我现在几乎就只会acm其他课程没怎么学好 只是懂一点皮毛 课也越来越多 也没时间去补 唉 再说一下旷课问题 我旷课很严重 但是感觉老师讲的都是皮毛 完全可以自学 不过时间也花在做题上了 又没怎么学好课程 大一上 c语言 微积分 首先acm基本上是用c和c++写的 所以我c学的不会很差 微积分的话只是期末复习的时候学了点  大部分没怎么懂 数学我不排斥 但学好也要花时间 时间投资了acm 大一下 数据结构 离散 微积分 acm也有用到数据结构 我的数据结构给力虽然和大牛比起

离散外微积分(DEC:Discrete Exterior Calculus)基础

原文链接 “若人们不相信数学简单,只因为他们未意识到生命之复杂.”——Johnvon Neumann DEC主要讨论离散情况下的外积分,它在计算机领域有重要用途.我们知道,使用计算机来处理几何图形的时候是不可能完全光滑的(计算机是只有0和1组成的离散化世界),利用DEC的概念也给我们提供了一种刻画离散几何的更好的工具.比如在几何分析中常用的“有限元分析(Finite Element Method)”中使用基于DEC的方法可以使用未uniform的曲面,更加方便简单. 外代数(Exterior A

算法基础之微积分--线性代数--离散数学

?? 近期在实施算法的时候.感觉数学知识不足了,在此大补一哈 --------------------------------------------------微积分---------------------------------------------------------- 微积分公开课: 麻省理工学院:单变量微积分 http://ocw.mit.edu/courses/mathematics/18-01sc-single-variable-calculus-fall-2010/ ht

离散事件模型

0x01 代码框架逻辑 模拟内容: 1.离散事件模拟,模拟银行营业时的排队情况 2.不考虑顾客中途离开,顾客到达事件随机,业务办理时间 3.长度随机,选择最短的队排队,不再换队 代码逻辑: 1.一个事件链表,四个窗口排队队列 2.事件驱动:每有一个新的顾客到达,将产生下一个新顾客到达的新事件按时间顺序从小到大(OccurTime)插入事件链表(EventList) (如果此时窗口队列只有 一个顾客,还将产生此顾客离开事件插入事件链表中)      每有一个顾客从某一队列首离开,将产生他的后一位顾

补零与离散傅里叶变换的分辨率

离散傅里叶变换(DFT)的输入是一组离散的值,输出同样是一组离散的值.在输入信号而言,相邻两个采样点的间隔为采样时间Ts.在输出信号而言,相邻两个采样点的间隔为频率分辨率fs/N,其中fs为采样频率,其大小等于1/Ts,N为输入信号的采样点数.这也就是说,DFT的频域分辨率不仅与采样频率有关,也与信号的采样点数有关.那么,如果保持输入信号长度不变,但却对输入信号进行补零,增加DFT的点数,此时的分辨率是变还是不变? 答案是此时分辨率不变.从时域来看,假定要把频率相差很小的两个信号区分开来,直观上

算法系列之二十三:离散傅立叶变换之音频播放与频谱显示

算法系列之二十三:离散傅立叶变换之音频播放与频谱显示 算法系列之二十三离散傅立叶变换之音频播放与频谱显示 导语 什么是频谱 1 频谱的原理 2 频谱的选择 3 频谱的计算 显示动态频谱 1 实现方法 2 杂项说明 结果展示 导语 频谱和均衡器,几乎是媒体播放程序的必备物件,没有这两个功能的媒体播放程序会被认为不够专业,现在主流的播放器都具备这两个功能,foobar 2000的十八段均衡器就曾经让很多人着迷.在上一篇对离散傅立叶变换介绍的基础上,本篇就进一步介绍一下频谱是怎么回事儿,下一篇继续介绍

hdu1542 Atlantis(扫描线+线段树+离散)矩形相交面积

题目链接:点击打开链接 题目描写叙述:给定一些矩形,求这些矩形的总面积.假设有重叠.仅仅算一次 解题思路:扫描线+线段树+离散(代码从上往下扫描) 代码: #include<cstdio> #include <algorithm> #define MAXN 110 #define LL ((rt<<1)+1) #define RR ((rt<<1)+2) using namespace std; int n; struct segment{ double l