下载文档原格式
常用降维动态规划1 逐次逼近动态规划（DPSA）逐次逼近动态规划是求解多维问题的有效方法之一，它的基本思想是把带有若干决策变量的问题分解成仅带有1个决策变量的若干个子问题，每个子问题比原来的总问题具有较少的状态变量，从而大大节省状态存储量及计算工作量，便于计算机求解。
对于多库联调优化问题，在确定初始可行调度线后采用DPSA求解的过程如下：（1）先假定第2个到最后一个水库的调度过程全部固定，对第1个水库进行优化，这时相当于单库优化调度，可以通过常规动态规划找到第1个水库的最优调度过程，此时其它水库仅进行简单的水务计算即可。
计算完成后用最优结果替代初始解中第1个水库的调度过程。
（2）假定第1个，第3个到最后一个水库的调度过程全部固定，求第2个水库的最优过程，这也相当于单库优化调度，同样通过常规动态规划找到第2个水库的最优调度过程。
并将其最优结果替代初始解中第2个水库的调度过程。
（3）依次类推，直至最后一个水库计算完成。
此时初始可行解依次被各次的单库最优结果替代，一轮计算完成。
（4）以上一轮最优结果为基础，重新依次计算单个电站的最优过程，并替换总体最优结果，反复轮流优选，直至收敛。
DPSA的思想是通过减少每次参与计算的电站数目，达到降维效果，其搜索结果精度与初始状态序列有关，因此它不能保证在所有情况下都收敛到真正的总体最优解，求解过程中可以从多个不同的初始状态(库群初始调度过程)开始，求得多个最优值，然后选择最好的结果。
2 增量动态规划（DDDP）DDDP是用逐次逼近方法寻优，每次寻优只在某个状态序列附近的小范围内，用动态规划法进行搜索。
其搜索流程是先根据一般经验或常规方法获得初始状态序列作为初始调度线，然后在该初始状态序列的上下各变动一个小范围，这个变动范围成为增量，形成一个带状“廊道”，接着在该廊道内用常规的动态规划寻优，可求得一条新的更接近于最优的状态序列。
这样就完成了一轮寻优，然后在新的状态序列上下再变动一个增量，并进行寻优。
逐步逼近法介绍逐步逼近法介绍也称逐级逼近。
一种宏观上的数学分析方法数学猜想中有不少是世界上著名难题，对于这些数学难题，人们常常设法先证明它的一种减弱命题，然后一步一步地向它逐渐逼近。
例如，对于哥德巴赫猜想的研究就是采用这样的步骤，自1742年提出后，许多数学家陆续作出了越来越接近最后解决（假定以偶数（1+1）来表示）的成果：1920年挪威数学家布克龙证明了偶数=9+9；1924年德国数学家马哈证明了偶数=7+7；1932年英国数学家爱斯特曼证明了偶数=6+6；1938年苏联数学家布赫斯塔勃证明了偶数=5+5；1940年布赫斯塔勃又证明了偶数=4+4；1950年苏联数学家维诺格拉多夫证明了偶数=3+3；1957年中国数学家王元证明了奇数=2+3；1962年中国数学家潘承洞证明了偶数=1+5；1962年中国数学家王元、潘承洞证明了奇数=1+4；1965年布赫斯塔勃、维诺格拉多夫和明比科都证明了偶数=1+3；1966年中国数学家陈景润证明了奇数=1+2目前距哥德巴赫猜想最终得证只剩一步之遥。
一种解题方法与上述宏观上的方法类似，在解决具体问题时，在以下情况下：1、没有现成的公式可用，如高级方程或微分议程2、有现成的公式但求解过程非常复杂3、不要求精确求解，只要求在一定范围内控制误差这时，可用逐级逼近方式求解。
具体方法是：在已经被确定的函数单调区间内，先将假定的解代入方程，然后根据方程的误差反过来修正解，直到方程的误差降至设定的范围。
上述方法在求解某些问题时也被称作逐级叠代法（实际上逐级叠代法是逐级逼近法的一种应用）。
一种电路理论或电路结构基于前述的理论方法，在电子电路中，也存有逐级逼近式电路。
典型应用就是逐级逼近式ADC（也称作逐级比较式ADC），这种电路的原理是：1、电路核心部分由DAC、时钟、计数器、比较器组成；2、计数器对时钟信号计数，可实现加/减双向；3、计数计数的加/减控制信号由比较器产生；4、比较器产生加/减指令的依据是比较输入电压和DAC输出电压的结果而定，DAC输出电压高于输入电压时，输出减指令，DAC输出电压低于输入电压时，输出加指令。
举例：设被测电压Ux = 3.285V ，逐次逼近寄存器和D/A变换器都为6位，基准电压Uref = 10V 。
解：最后输出010101，显示3.281V
过程：
首先因为是6位的，所以先将10V分成64份(二进制数111111即为十进制64)，即10/64，接下来就可以开始计算了。
1)100000，即32，所以第一个比较电压是32*10/64=5V，显然Ux＜5V，所
以最高位为0（表示去码）；
2)010000（注意：之前确定的位要保留），即16，所以第二个比较电压是2.5V，
由于Ux>2.5V，所以第二位为1（表示留码）；
3)011000，即24，所以第三个比较电压是24*10/64=3.75V，同上，第三位取
0；
4)010100，即20，所以第四个比较电压是20*10/64=3.125V，同上，第四位
取1；
5)010110，即22，所以第五个比较电压是22*10/64=3.4375V，同上，第五位
取0；
6)010101，即21，所以第六个比较电压是21*10/64=3.28125，同上，第六位
取1。
综上可知，输出010101，显示3.281V。
由于D/A变换器输出的基准电压是量化的，因此经变换后显示的数值3.281V比实际电压值低0.004V，这就是A/D变换的量化误差。
减小量化误差的方法是增加比较次数，即增加逐次比较式A/D变换器的位数。
（正好复习时也有疑问，百度上却没有明确的解析，自己明白后就做了这个，希望对大家有帮助！
——1103子夜）。
A/D转换器A/D转换器是用来通过一定的电路将模拟量转变为数字量。
模拟量可以是电压、电流等电信号，也可以是压力、温度、湿度、位移、声音等非电信号。
但在A/D转换前，输入到A/D 转换器的输入信号必须经各种传感器把各种物理量转换成电压信号。
A/D转换后，输出数字信号可以有8位、10位、12位和16位等。
AD转换器的工作原理主要介绍3种：逐次逼近法双积分法电压频率转化法1 逐次逼近法：逐次逼近式A/D是比较常见的一种A/D转换电路，转换的时间为微秒级。
采用逐次逼近法的A/D转换器是由一个比较器、D/A转换器、缓冲寄存器及控制逻辑电路组成，如图4.21所示。
基本原理是从高位到低位逐位试探比较，好像用天平称物体，从重到轻逐级增减砝码进行试探。
图4.21 逐次逼近式A/D转换器原理框图逐次逼近式A/D转换器原理框图逐次逼近法转换过程是：初始化时将逐次逼近寄存器各位清零；转换开始时，先将逐次逼近寄存器最高位置1，送入D/A转换器，经D/A转换后生成的模拟量送入比较器，称为Ｖo，与送入比较器的待转换的模拟量Ｖi进行比较，若Ｖ，该位1被保留，否则被清除。
然后再置逐次逼近寄存器次高位为1，将寄存器中新的数字量送D/A转换器，输出的Ｖo再与Ｖi比较，若ＶoＶi，该位1被保留，否则被清除。
重复此过程，直至逼近寄存器最低位。
转换结束后，将逐次逼近寄存器中的数字量送入缓冲寄存器，得到数字量的输出。
逐次逼近的操作过程是在一个控制电路的控制下进行的。
2双积分法：采用双积分法的A/D转换器由电子开关、积分器、比较器和控制逻辑等部件组成。
如图4.22所示。
基本原理是将输入电压变换成与其平均值成正比的时间间隔，再把此时间间隔转换成数字量，属于间接转换。
图4.22 双积分式A/D转换的原理框图双积分法A/D转换的过程是：先将开关接通待转换的模拟量Ｖi，Ｖi采样输入到积分器，积分器从零开始进行固定时间Ｔ的正向积分，时间Ｔ到后，开关再接通与Ｖi极性相反的基准电压ＶＲＥF，将ＶＲＥF输入到积分器，进行反向积分，直到输出为0V时停止积分。
第三章 逐次逼近法1.1内容提要1、一元迭代法x n+1=φ(x n )收敛条件为：1）映内性x ∈[a,b]，φ(x) ∈[a,b] 2）压缩性∣φ(x) -φ(y)∣≤L ∣x-y ∣其中L ＜1，此时φ为压缩算子，在不断的迭代中，就可以得到最终的不动点集。
由微分中值定理，如果∣φ’∣≤L ＜1，显然它一定满足压缩性条件。
2、多元迭代法x n+1=φ(x n )收敛条件为：1）映内性x n ∈Ω，φ(x n ) ∈Ω 2）压缩性ρ（▽φ）＜1，其中▽φ为x n 处的梯度矩阵，此时φ为压缩算子，在不断的迭代中，就可以得到最终的不动点集。
3、当φ(x )= Bx+f 时，收敛条件为，ρ（B ）＜1，此时x n+1= Bx n +f ，在不断的迭代中，就可以得到线性方程组的解。
4、线性方程组的迭代解法，先作矩阵变换 U L D A --= Jacobi 迭代公式的矩阵形式 f Bxb Dx U L Dx nn n +=++=--+111)(Gauss-Seidel 迭代公式的矩阵形式 f Bx b L D Ux L D x n n n +=-+-=--+111)()( 超松弛迭代法公式的矩阵形式f Bxb L D x U D L D xkk k +=-++--=--+ωωωωω111)(])1[()(三种迭代方法当1)(<B ρ时都收敛。
5、线性方程组的迭代解法，如果A 严格对角占优，则Jacob 法和Gauss-Seidel 法都收敛。
6、线性方程组的迭代解法，如果A 不可约对角占优，则Gauss-Seidel 法收敛。
7、Newton 迭代法，单根为二阶收敛 2211'''21lim)(2)(lim---∞→+∞→--=-==--k k k k k k k k x x x x f f c x x ξξαα8、Newton 法迭代时，遇到重根，迭代变成线性收敛，如果知道重数m ， )()('1k k k k x f x f m x x -=+仍为二阶收敛 9、弦割法)()())((111--+---=k k k k k k k x f x f x x x f x x 的收敛阶为1.618，分半法的收敛速度为（b-a ）/2n-110、Aitken 加速公式11211112)(),(),(+----+-+--+---+---===k k k k k k k k k k k x x x x x x x x x x x ϕϕ1.2 典型例题分析1、证明如果A 严格对角占优，则Jacob 法和Gauss-Seidel 法都收敛。
一、逐次逼近式AD转换器与计数式A/D转换类似，只是数字量由“逐次逼近寄存器SAR”产生。
SAR使用“对分搜索法”产生数字量，以8位数字量为例，SAR首先产生8位数字量的一半，即10000000B,试探模拟量Vi的大小，若Vo>Vi，清除最高位，若Vo<Vi,保留最高位。
在最高位确定后，SAR又以对分搜索法确定次高位，即以低7位的一半y1000000B(y为已确定位) 试探模拟量Vi的大小。
在bit6确定后，SAR以对分搜索法确定bit5位，即以低6位的一半yy100000B(y为已确定位) 试探模拟量的大小。
重复这一过程，直到最低位bit0被确定，转换结束。
转换过程：(1)首先发出“启动信号”信号S。
当S由高变低时，“逐次逼近寄存器SAR”清0，DAC输出Vo=0，“比较器”输出1。
当S变为高电平时，“控制电路”使SAR开始工作。
(２)SAR首先产生8位数字量的一半，即10000000B,试探模拟量的Vi大小，若Vo>Vi，“控制电路”清除最高位，若Vo<Vi,保留最高位。
(３)在最高位确定后，SAR又以对分搜索法确定次高位，即以低7位的一半y1000000B(y 为已确定位) 试探模拟量Vi的大小。
在bit6确定后，SAR以对分搜索法确定bit5位，即以低6位的一半yy100000B(y为已确定位) 试探模拟量Vi的大小。
重复这一过程，直到最低位bit0被确定。
(4)在最低位bit0确定后，转换结束，“控制电路”发出“转换结束”信号EOC。
该信号的下降沿把SAR的输出锁存在“缓冲寄存器”里，从而得到数字量输出。
从转换过程可以看出：启动信号为负脉冲有效。
转换结束信号为低电平。
我觉得，这有点像数学中的二分法，如给一个数a，先用8'b1000000（设为b）与a相比较，如果a大于b，则保留最高位1，即原来的范围变成了0-7'b1111111（第8位已确认）。
第六章 逐次逼近法 §1 线性方程组解的误差分析 因为线性方程组涉及到矩阵和向量，为了对线性方程组的近似解进行误差估计，以及后面研究迭代法解线性方程组的收敛性，需要对向量和矩阵引进范数的概念。
一、向量和矩阵的范数 1．向量的范数定义 1 如果向量空间nR 上的某个非负实值函数()N =x x 满足条件：（1）正定性：0≥x ，当且仅当=0x 时0=x ；（2）齐次性：c c =x x ，c 为任意实数； （3）三角不等式：+≤+x y x y 。
则称⋅为n R 上的一个向量范数。
n 维向量空间12{|(,,,),,1,2,,}nn i R x x x x R i n ==∈= x x上常用的三种范数：（1）向量的2—范数：2=x；（2）向量的∞—范数：1max i i nx ∞≤≤=x； （3）向量的1—范数：∑==ni ix x 11。
例1 设(1,2,3,4)T=--x ，则2141max 4,123410.i i x ∞≤≤=====++-+-=x xx后面我们研究迭代法解线性方程组时，需要讨论算法的收敛性。
为此，先给出算法产生的迭代点列收敛的概念。
定义2 设()()()1(,,)k k k nnx x R =∈ x，***1(,,)nnx x R =∈ x ，若),,2,1(,lim *)(n i x xik ik ==∞→，则称点列(){}k x 收敛于*x ，并记作()*lim k k →∞=x x。
由定义可知：()*lim k k →∞=xx ()*lim k k ∞→∞⇔-=0xx，()*lim k k →∞=xx ()*1lim k k →∞⇔-=0x x ，()*lim k k →∞=xx ()*2lim k k →∞⇔-=0xx。
2．矩阵的范数定义 3 如果矩阵空间nn R⨯上的某个非负实值函数()N =A A 满足以下条件：（1） 正定性：0≥A ，且0=⇔=0A A ；（2）齐次性：c c =A A ，c 为任意实数； （3）三角不等式：+≤+A B A B ； 则称()N A 为nn R⨯上的一个矩阵范数。
