如何不用计算机,得到证明根号2近似值4.1的近似解

Mathematical Induction 数学归纳法 使用数学归纳法这個大家基本都清楚,就是假设一个在 n 的时候结论成立证明在 n+1的 时候结论也成立,当然在我们这里,稍微有点变化举个例子。 T(n) = T(n/2) + T(n/4) + T(n/8) + n 现在我們要就上面表达式 T(n)现在我们就先 guess T(n) = Theta(n)。 当然我们知道要证明

即(6.2)仍然成立于是对所有 n≥n0,(6.2)成立可见我们的推测是正确的。因而得出结 论:遞归方程(6.1)的解的渐近阶为 O(nlogn) 当 n 充分大时

相差无几。因此可以推测(6.3)与(6.1)有类似的上界

T(n)=O(nlogn)进一步,数学归纳将证明此推测是正确的

,有相关定悝知根据 f(n)有 T(n)的渐近估计式第一类情况

算一个 i 次多项式与一个一次多项式的乘积,以及一个算法能在 O ( i log i ) 时间内计算两个 i 次多项式的乘积对於任意给定的 d 个整数 n , n ,..., n ,用分治法设计一个有效算法计

效率。 9、设计一个 O(n2)的时间算法找出由 n 个数组成的序列的最长单调递增子序列。 10、設计一个在 O(n)时间内计算 p ( x ) ? a ? a x ? ... ? a x 的算法

11、数组 A[1..n]中存放正整数和负整数,设计一个在 O(n)时间内将所有负整数放置所有正 整数之前的算法 12、掌握鼡动态规划解 0-1 背包问题。 【见文档】 13、掌握用贪心算法(prim 算法)无向连通图的最小生成树 14、掌握回溯法解 0-1 背包问题的解空间树[见文档] 15、掌握单纯形算法解线性规划问题[见文档 8 章] 16、掌握顶点覆盖问题的近似算法【9.4.2 】 无向图 G=(V,E)的顶点覆盖是它的顶点集 V 的一个子集 V’ V, ? 使得若(u,v)是 G 的┅ 条边则 v∈V’或 u∈V’ 。顶点覆盖 V’的大小是它所包含的顶点个数|V’| 【 Cset 用来存储顶点覆盖中的各顶点。初始为空不断从边集 e1 中选取一邊(u,v),将边 的端点加入 cset 中并将 e1 中已被 u 和 v 覆盖的边删去,直至 cset

图(a)~(e)说明了算法的运行过程及结果(e)表示算法产生的近似最优顶点覆盖 cset,它 由頂点 b,c,d,e,f,g 所组成(f)是图 G 的一个最小顶点覆盖,它只含有 3 个顶点:b,d 和 e 性能分析:若用 A,B 分别来计算算法循环中选取的边的集合和点的集合,由算法的构造克 制 A 中任何两条边没有公共断点且 B 中的点也互不关联因为算法选了一条边,并在将其 断点加入顶点覆盖集 C 后就将 E1 中与该边关聯的所有边从 E1 中删去,对于每次选择的 点也是同样处理故算法终止时有|C|=2A+B,而图 G 的最小顶点覆盖 C’ 则|C’|≥|A|+|B 由此可得,|C|≥2|C'|-|B ,与原算法的|C|≥2|C'|,相仳当|B 远远大于|A|时,此算法比原算法显 示了更大的优越性 17、什么是 P 类和 NP 类问题 P 问题:如果一个问题可以找到一个能在多项式的时间里解決它的算法,那么这个问题 就属于 P 问题 我们常见到的一些信息奥赛的题目都是 P 问题。 NP 类问题:首先 NP 问题不是非 P 类问题NP 问题是指可以在哆项式的时间里验证一 个解的问题,即可以在多项式的时间里猜出一个解的问题像 Hamilton 回路问题。所有的 P 问题都是 NP 问题即能用多项式解决┅个问题,必然能用多项式验证一个问题的解 递归方程解的渐近阶的求法 1. 代入法 这个方法的基本步骤是先推测递归方程的显式解, 然后鼡数学归纳法证明这 一推测的正确性那么,显式解的渐近阶即为所求 2. 迭代法 这个方法的基本步骤是通过反复迭代,将递归方程的右端變换成一个级数 然后求级数的和,再估计和的渐近阶;或者不求级数的和而直接估计级数的渐近 阶,从而达到对递归方程解的渐近阶嘚估计 3. 套用公式法 这个方法针对形如:T (n)=aT (n / b)+f (n) 的递归方程,给出三种情况 下方程解的渐近阶的三个相应估计公式供套用 4. 差分方程法 有些递归方程可以看成一个差分方程,因而可以用解差分方程(初值问 题)的方法来解递归方程然后对得到的解作渐近阶的估计。 母函数法 这是一个囿广泛适用性的方法它不仅可以用来求解线性常系数高阶齐次和非齐 次的递归方程, 而且可以用来求解线性变系数高阶齐次和非齐次的遞归方程 甚至可以用来 求解非线性递归方程。方法的基本思想是设定递归方程解的母函数 例如,我们要估计 T(n)的上界T(n)满足递归方程:

昰地板(floors)函数的记号,

表示不大于 n 的最大整数

即(6.2)仍然成立,于是对所有 n≥n0(6.2)成立。可见我们的推测是正确的因而得出结 论:递归方程(6.1)的解的渐近阶为 O(nlogn)。 这个方法的局限性在于它只适合容易推测出答案的递归方程或善于进行推测的高手 推测递 归方程的正确解,没有一般的方法得靠经验的积累和洞察力。我们在这里提三点建议: (1) 如果一个递归方程类似于你从前见过的已知其解的方程 那么推测它有类似的解是合理 的。作为例子考虑递归方程:

右边项的变元中加了一个数 17, 使得方程看起来难于推测 但是它在形式上与(6.1)很类似。 实际上当 n 充分大时

与 相差无几。因此可以推测(6.3)与(6.1)有类似的上界 T(n)=O(nlogn)进一步,数学归纳将 证明此推测是正确的 (2)从较宽松的界开始推测,逐步逼近精确堺比如对于递归方程(6.1),要估计其解的渐近 下界由于明显地有 T(n)≥n,我们可以从推测 T(n)=Ω (n)开始发现太松后,把推测的阶 往上提就可以得箌 T(n)=Ω (nlog n)的精确估计。 (3)作变元的替换有时会使一个末知其解的递归方程变成类似于你曾见过的已知其解的方 程从而使得只要将变换后的方程嘚正确解的变元作逆变换,便可得到所需要的解例如考 虑递归方程:

看起来很复杂,因为右端变元中带根号2近似值但是,如果作变元替换 m=logn即令 n=2 ,将其 代入(6.4)则(6.4)变成:

把 m 限制在正偶数集上,则(6.5)又可改写为:


与(6.1)类似因而有:
进而得到 T(n)=T(2 )=S(m)=O(m1ogm)=O(lognloglogn) (6.6) 上面的论证只能表明: 当(充分大的)n 是 2 嘚正偶次幂或换句话说是 4 的正整数次幂时(6.6) 才成立。进一步的分析表明(6.6)对所有充分大的正整数 n 都成立从而,递归方程(6.4) 解的渐近阶得到估计 在使用代入法时,有三点要提醒: (1)记号 O 不能滥用比如,在估计(6.1)解的上界时有人可能会推测 T(n)=O(n),即对于 充分大的 n有 T(n)≤Cn ,其中 C 是确定的囸的常数他进一步运用数学归纳法,推出:

从而认为推测 T(n)=O(n)是正确的实际上,这个推测是错误的原因是他滥用了记号 O , 错误地把(C+l)n 与 Cn 等哃起来 (2)当对递归方程解的渐近阶的推测无可非议,但用数学归纳法去论证又通不过时不妨在 原有推测的基础上减去一个低阶项再试试。作为一个例子考虑递归方程

是天花板(floors)函数的记号。我们推测解的渐近上界为 O(n)我们要设法证明对

于适当选择的正常数 C 和自然数 n0,当 n≥n0 時有 T(n)≤Cn把我们的推测代入递归方程, 得到:

我们不能由此推断 T(n)≤Cn归纳法碰到障碍。原因在于(6.8)的右端比 Cn 多出一个低阶 常量为了抵消这┅低阶量,我们可在原推测中减去一个待定的低阶量 b即修改原来的推 测为 T(n)≤Cn-b 。现在将它代人(6.7)得到:

只要 b≥1,新的推测在归纳法中将得箌通过 (3)因为我们要估计的是递归方程解的渐近阶,所以不必要求所作的推测对递归方程的初始 条件(如 T(0)、T(1))成立而只要对 T(n)成立,其中 n 充分大比如,我们推测(6.1) 的解 T(n)≤Cnlogn而且已被证明是正确的,但是当 n=l 时这个推测却不成立,因为 (Cnlogn)|n=1=0 而 T(l)>0 递归方程组解的渐进阶的求法――迭玳法 用这个方法估计递归方程解的渐近阶不要求推测解的渐近表达式,但要求较多的代数运算 方法的思想是迭代地展开递归方程的右端, 使之成为一个非递归的和式 然后通过对和式的 估计来达到对方程左端即方程的解的估计。 作为一个例子考虑递归方程:

接连迭代二佽可将右端项展开为:

由于对地板函数有恒等式:

这仍然是一个递归方程,右端项还应该继续展开容易看出,迭代 i 次后将有

时,(6.11)不再昰递归方程这时:

从这个例子可见迭代法导致繁杂的代数运算。 但认真观察一下 要点在于确定达到初始条件 的迭代次数和抓住每次迭玳产生出来的"自由项"(与 T 无关的项)遵循的规律。 顺便指出 迭 代法的前几步迭代的结果常常能启发我们给出递归方程解的渐近阶的正确推测。 这时若换用 代入法将可免去上述繁杂的代数运算。

图 6-1 与方程(6.15)相应的递归树 为了使迭代法的步骤直观简明、图表化我们引入递归树。靠着递归树人们可以很快地得 到递归方程解的渐近阶。它对描述分治算法的递归方程特别有效我们以递归方程


为例加以说明。图 6-1 展示絀(6.15)在迭代过程中递归树的演变为了方便,我们假设 n 恰好是 2 的幂在这里,递归树是一棵二叉树因为(6.15)右端的递归项 2T(n/2)可看成 T(n/2)+T(n/2)。图 6-1(a)表示 T(n)集中茬递归树的根处(b)表示 T(n)已按(6.15)展开。 2 也就是将组成它的自由项 n 留在原处 而将 2 个递归项 T(n/2)分别摊给它的 2 个儿子结点。 (c)表示迭代被执行一次图 6-1(d)展示出迭代的最终结果。 图 6-1 中的每一棵递归树的所有结点的值之和都等于 T(n)特别,已不含递归项的递归树 (d)中所有结点的值之和亦然我们嘚目的是估计这个和 T(n)。我们看到有一个表格化的办 法:先按横向求出每层结点的值之和并记录在各相应层右端顶格处,然后从根到叶逐層地 2 将顶格处的结果加起来便是我们要求的结果照此,我们得到(6.15)解的渐近阶为 θ (n ) 再举一个例子。递归方程:
的迭代过程相应的递归树洳图 6-2 所示其中,为了简明再一次略去地板函数和天花板函 数。

图 6-2 迭代法解(6.16)的递归树 当我们累计递归树各层的值时得到每一层的和都等于 n,从根到叶的最长路径是

设最长路径的长度为 k则应该有

即 T(n)=O(nlogn) 。 以上两个例子表明借助于递归树,迭代法变得十分简单易行 递归方程组解的渐进阶的求法――套用公式法


的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的 a≥1 和 b≥1 是常数f (n)是 一个确定的正函数。 (6.17)是一类汾治法的时间复杂性所满足的递归关系 即一个规模为 n 的问题被分成规模均 为 n/b 的 a 个子间题,递归地求解这 a 个子问题然后通过对这 a 个子间題的解的综合,得 到原问题的解如果用 T(n)表示规模为 n 的原问题的复杂性,用 f(n)表示把原问题分成 a 个子问题和将 a 个子问题的解综合为原问题的解所需要的时间我们便有方程(6.17)。 这个方法依据的是如下的定理:设 a≥1 和 b≥1 是常数 f (n)是定义在非负整数上的一个确 定的非负函数又设 T(n)也是萣义在非负整数上的一个非负函数,且满足递归方程(6.17) 方程(6.17)中的 n/b 可以是[n/b], 也可以是 n/b 那么,

近些年来由布朗运动驱动的随機微分方程已经在很多文章中被广泛讨论了,例如Mao [1] Mao [2] 等。考虑标量随机微分方程

是一个标准的布朗运动 是三个正常数,我们称这样的随機微分方程为Ginzburg-Landan方程这一类的随机微分方程有很多好的性质,例如: 强收敛性解的二阶矩渐近稳定性(见Guo [3] )。

上的非线性函数然而在现实卋界中,许多问题都需要我们用α-稳定过驱动的随机微分方程搭建的数学模型来解决例如:Mandelbrot [4] 指出1890年至1937年月度羊毛价格变化的分布遵循α = 1.7嘚α-稳定分布。从Embrechts [5] 我们可知SDE驱动因子为0.018时对于 0 的取值可能随着时间而取负值,也就是说这个SDE的数值解随时会爆炸然而现实生活中的许哆问题都需要我们用收敛的数值解去解决,但是在讨论数值解之前,我们必须确保SDE的解是存在的所以我们有足够的理由去讨论以下SDE:

昰一个α-稳定过程,且 0

0 0

0 为补偿泊松测度写做:

0

0 0 0

0 时,我们称该过程为对称α稳定过程。本文仅对对称α稳定过程进行讨论且规定

是一个Gamma函數,定义为:

0 0

更为一般的我们讨论漂移算子和积分算子都是非线性的随机微分方程,即:

0 上的对称α-稳定过程规定初始值为 0 0

由α-稳定過程驱动的SDE在近几年已经被很多学者探讨(参见Applebaum [6] ),然而目前为止还没有人给出SDE(1.3)的数值解,在此之前讨论SDE (1.3)解的存在唯一性就成了我们需要解决的问题。在解决这个问题之前我们先来对文中出现的符号和需要用到的预备知识进行说明。

2. 符号说明和预备知识

首先我们队文本Φ出现的随机过程进行符号解释。 是一个完备概率空间其中 0 上的α-稳定过程。如果 是一个集合它的示性函数表示为当 表示实数集以及鈈包含0的实数集,定义

2.2. α-稳定过程的无穷小生成元

我们介绍由谱正稳定过程驱动的带马尔科夫调制穷小生成元

只有正跳的稳定过程叫做譜正稳定过程,谱正稳定过程的Lévy测度

0 0 0

的普正稳定过程驱动的模型

0

3. 解的存在并且唯一满足的假设条件

为了方便下文的证明我们提出以下幾个基本假设。

从(3.1)可得线性增长条件即存在一个 0

0 0 0 0 0

0

0 0 0

4. 解存在唯一性定理及解的收敛性

这小结分为两部分,第一部分给出SDE (1.3)解存在唯一的证明苐二部分给出解收敛的证明。

0

4.1. 解的存在唯一性

定理B1:若假设A1~A3成立则SDE (1.3)有一个唯一的全局解

0 0 0 0 0

0

因为SDE (1.3)的系数满足局部Lipschitz条件,所以对于给定的初始值 0 0 上存在一个唯一的局部解 0 0 0 0 0 0 0 0

0 0

0 0

0 0

是一个局部鞅,定义如下:

0

0 0

由Taylor公式可知存在一个

0 0 0

从这个式子我们立即得到

0

,从式(3.9)我们可得

0 0 0

从我们选择的p值鈈难看出

0

0 0

0 0

0

的选择由基本不等式可得

结合假设式(3.2),可得

0 0 0

0 0

0

0 0

则由式(3.19)我们可得

0 0

0 0

0

0

0 上存在一个唯一的全局解

若SDE (1.3)的解存在且唯一,即定理B1成立下,對任意的 0 0

0

0 0 0

0 0

0 0 0

0 0

1.1. 给出黑体辐射频率分布函数 R(? , T ) 的单位 1.2. 分别计算红光 ? =600 nm 和 X 射线 ? =100 pm 的 1 个光子的能量、 动量和质 量。 1.3. 计算波长 ? =400nm 的光照射到金属铯上所产生的光电子的初速度 已知铯 的临阈波长为 600nm。 1.4. 氫原子光谱中巴尔麦系中波长最长的一条谱线的波数、波长和频率各是多 少波长最短的一条呢? 1.5. 求氢原子光谱中赖曼系第 3 条谱线的波数、波长和频率 1.6. 氢原子光谱中赖曼系、巴尔麦系和帕邢系的谱线能否互相穿插,为什么 1.7. 在氢原子光谱的各线系中,相邻两谱线间的距离昰等间隔、还是朝着短波 的方向递减或递增 1.8. 求波长为 0.1 nm 的电子和中子的动量和动能。 1.9. 求下列粒子的德布罗意波长: (1) 能量为100 eV的自由电子; (2) 能量為0.1 eV的自由中子; (3) 能量为0.1 eV质量为1g的粒子。 1.10. 用速度 ? ? 1? 109 cm ? s ?1 的电子进行衍射试验 若所用晶体粉末的面间距离 为 242 pm,晶体粉末离底板距离为 2.5 cm求第 2 条和第 3 條衍射环纹的 半径。 1.11. 一个运动速度为 v 的自由粒子有人作了如下推导: 1 E e


1 得出 1= 的错误结论,试问其推导过程中哪些过程是错误的 2 测不准关系限制我们同时测定粒子的动量和坐标, 但为什么经典的物体不 -6 受限制呢计算一个在一球拍上 10 m 范围内的质量为 500 g 的球的速度 的最小不确定程度是多少?一个质量为 5 g速度在 35.00001 至 35.00000 ms-1 的物体,其位置的不确定程度是多少由此可知为什么经典物理不受

的本征函数,本征值是多少 dx d 下列哪些函数是算符 的本征函数,本征值是多少 dx ikx (1) e ; (2) ln x ; (3)k; (4)kx d2 下列哪些函数是算符 2 的本征函数,本征值是多少 dx 2 ikx (1) e ; (2)

我要回帖

更多关于 根号二的近似值 的文章

 

随机推荐