（基础数学专业论文）随机徘徊与电路的一些关系.pdf

新江大学硕士学位论文 摘要 s 与迁1 7 3 本文溅明了任何边值的d i r i c h l e t 问题都可转化为求螭电路电压的阏题；给 塞7 谤舞乎嚣疆轰上d i r i 馥融秘嚣弱5 秘方法；专曩鹱了遥我法襄捡骢法都楚臻 数收敛瓣，并分别给出收敛遮发的估计：讨论了般窀路上斡随机襻徊，验证 了电路与可逆的遍历m a r k o v 链是一一对应的；缭出了电路电压的概率解释：当 把1 伏电压加于4 ，b 两蛹，使得v a = l ，u = 0 时，n x 点的电压u 袋示对应的 m a r k o v 链孛，敞x 出发，到这b 之羲爨这g 瓣壤攀；逡一步遣，绘掇了逮离援 率与裔效电隘之闯的关系：扶尊出发，在到达b 之翦到达a 的壤率为露效传导奉 与通过a 的总传导率之比。 黧琶盔兰鍪圭主簦鎏苎一 a b s t r a c t i nt h i sd i s s e r t a t i n n ，w ef i r s t l yp r o v et h a ta n y d i r i c h l e tp r o b l e mi si n d e e de q u a lt o av o l t a g e sp r o b l e mo fn e t w o r k s w eg i v ef i v es o l u t i n n st od i r i c h l e tp r o b l e m 攮t w o d i m e n s i o n s ；a m o n g t h e s ef i v es o l u t i o n s , w ep r o v et h a tt h ei t e r s f i o ns o l u t i o na n dt h e s o l u t i o no f r e l a x a t i o n sa r ee x p o n e n t i a lc o n v e r g e n c e ，t h e nw ee s t i m a t et h e i r r e s p e c t i v ec o n v e r g e n c er a t e s ；s e c o n d l y ，w ed i s c u s s r a n d o mw a l k so ng e n e r a l n e t w o r k s ，p r o v e t h a tt h e r ei sa nn n et oo n e c o r r e s p n n d e n c eb e t w e e n n e t w o r k sa n d r e v e r s i b l ee r g o d i em a t k n vc h a i n s ；t h i r d l y ，w eg i v ep r o b a b i t i s t i ei n t e r p r e t a t i o no f v o l t a g e sf o rg e n e r a ln e t w o r k s ：w h e nau n i tv o l t a g ei sa p p l i e db e t w e e n 拉a n d b ， m a k i n gk = 1 a n d v b = 0 ，t h ev o l t a g ev ，a ta n yp o i n t 工r e p r e s e n t s t h e p r o b a b i l i t y t h a taw a l k e rs t a r t i n gf r o mxw i l lr e t u r nt o 口b e f o r er e a c h i n g 扫： f u r t h e r m o r e ，w es t u d yt h er e l a t i o n s h i pb e t w e e ne f f e c t i v er e s i s t a n c ea n de s c a p e p r o b a b i l i t y ：s t a r t i n ga t 口t h ep r o b a b i l i t y t h a tt h ew a l kr e a c h e sbb e f o r er e t u r n i n gt o # i st h er a t i oo f t l l ee f f e c t i v ec o n m l c 塘n c ea n dt i i et o t a lc n n d u c t a n c e 浙江大学硕士学位论文 1 引言 1 1 问题的起源与意义 简单随机徘徊是人们最早研究的随机过程之一。至今，它仍然有着十分重 要的科研价值和应用价值。下例给出了人们早期研究的一个一维的简单随机徘徊 的例子。 例1 1 ( 赌徒破产阀题) 设某赌徒有赌本i ( t 1 ) 元，其对手有赌本目一f 0 每赌一次该赌徒均以p 的概率赢一元，以g 一1 - p 的概率输一元。这里疗为正整 数。赌博一直到两赌徒中有一人破产才告结束，因此，赢的赌徒最终有总赌资d 元，求该赌徒的破产概率? 分析：记p 。为赌徒有赌本f 元而最终破产的概率，a 。一 有赌本f 元而最 终破产 ，b = 该赌徒第一次赌赢 。则由全概率公式得对任意l f s 口一l ， p l2 p ( a 。j = 刖，b ) p ( b ) + p ( a ；b 。) p 口。) = p ( a “1 驴+ 刑 2 p p l 十1 + 日p _ 1( 1 1 ) 这是一个差分方程，且有边界条件 ( 1 1 ) 式等价于 p 。= h 有赌本0 元而擐终破产) = l ， p 。= p ( 有赔本口元而最终破产) = 0 p ( p - p 1 ) = g p f p f - 1 ) 所以，当p 0 且p i 2 时，对任意2 f 0 且p 1 2 ( 即p g ) 时 ( 里) r 一( 里) a n 2 乞争 当p = g = 1 2 时，有 p 。一p l2 ( i - 1 ) ( p - 1 ) 令f = 口，可得 d l p l2 ， 从而有 p ，一1 一上 ( 1 2 ) ( 1 3 ) 1 2 一些相关的定义与约定 定义1 1 设有一质点在直线上的攘数点上运动，每隔一个单位时间运动一次， 每次运动的长度为单位长度，若在拧时刻质点位于f ，那么，质点在下一时刻( 即 月+ l 时刻) ，以概率p 跳到i d - i ，以概率q = l - p 跳到t - - 1 ，则称这一过程为贝努利 ( b e r n o u l l i ) 随机徘徊a 特别地，若p = q = l ，2 ，则称此贝努利随机徘徊为简单 随机徘徊。 赌徒破产问题是简单徘徊的中的类很有实际意义的问题带边界吸收 的简单随机徘徊- 在这一过程中，当质点运动到区域的边界时，就被吸收了，整 个随机徘徊就结束了。 浙江大学硕士学位论文 定义1 2 称平面上的具有整数坐标的点为格点( 1 a t t i c e p o i n t ) a 定义1 3 平面上的简单随机徘徊，是指质点在格点上的随机徘徊，若在n 时 刻质点位于6 ) ，那么，质点在下一时刻( 即n + l 时刻) ，或者以l 4 的概率跳 到+ 1 ，6 ) ，或者姒l 4 的概率跳到0 - - i 乒) ，或者以l ，4 的概率跳到( 口，6 + 1 ) ，或者 以i 4 的概率跳到( 4 ，6 一1 ) 。 本文主要讨论的是平面上的边界吸收的简单随机徘徊，因此，约定下文中的 随机徘徊都是指边界吸收的简单随机徘徊。 1 3 本文的结构与组织 本文共分为四章： 第一章，就是本章，介绍随机徘徊问题的起源，意义及一些相关的定义和约 定。 第二章，介绍了调和函数，d i r i c h i e t 问题并证明了任何边值的d i r i c h l c t 问题 都可转化为求解电路电压的问题。 第三章，给出了计算平面格点上d i r i c h l e t 问题的5 种方法：蒙特卡洛方法， 迭代解法，松弛方法，解线性方程组方法以及m a r k o v 链方法，对同一饲子给出 各自相应的计算结果：证明了迭代法也是指数收敛的，并给出其l 范数收敛速 度的估计( 见定理3 2 ) ；同时证明了松弛法是指数收敛的，并给出其一致收敛速 度的估计( 见定理3 3 和定理3 4 ) 第四章，讨论了一般电网上的随机徘徊，证明了电路与可逆的遍历m a r k o v 链是一一对应的：给出了电路电压的概率解释：当把l 伏电压加于a ，b 两端， 使得v a = 1 ，u = 0 时，则x 点的电压叱表示对应的m a r k o v 链中，从工出发，到 达b 之前到达口的概率；进一步地，给出了逃离概率与有效电阻率之间的关系： 若以气，表示从口出发，在到达6 之前到达4 的概率，则，= - 。7 钟- ，这里 一口 是有效传导率， e = 古是通过a 的总传导率。 浙江大学硕士学位论文 2 调和函数及1 ) i r i c h i e t 问题 2 1 直线上的随机徘徊 考虑整数点集s = 0 ，1 ，2 ，) 上的随机徘徊，其中0 点和点为吸收 壁( 即当质点到达0 点或点时，就停留在该点，随机徘徊过程停止) ，p “) 表示从x 点出发，最终到达点的概率，那么，p ) 有以下性质： ( a ) p ( 0 ) = 勺 ( 2 1 ) ( b ) 从) = l ( 2 2 ) ( c ) p ( j ) ( 1 ，2 ) p 0 1 ) + 0 2 ) p o + 1 ) ( 2 3 ) 其中x = l ，2 ，一1 。 称点集d = - 1 ，2 ，- l 中的点为s 的内点，丑= 0 ，册中的点为s 的边 界点。定义在s 上的函数，若满足( c ) ，则称厂是调和的。 因此，直线上的随机徘徊问题实质就是求两个端点的值分别为0 和l 的调 和函数p 。 定理2 1 设f ( x ) 是定义在s 上的调和函数，那么，fo ) 可在边界点上 取到最大值和最小值批 证明：设肼为，的最大值，如果对某个工d ，x x ) = m 。因为 a x ) = ( v 2 1 9 x - 1 ) + ( i 2 f f ( x + t ) ，所以m 1 只融+ 1 ) 爿皈如果x - 1 仍为内点，那么同理， f ( x - - 2 ) = m 。以此类推，可得厂( o ) = m 。所以厂可在边界点上取到最大值m 。 同理可证，可在边界点上取至u 最小值i n 。证毕。 定理2 2 ( 唯一性定理) 如果m ) 和g ( 工) 都是定义在点集s 上的调和函数， 且在边界点b 上有产g 那么对任意的x e s ，m ) 噌口) 。 证明：令h ( x ) = x x ) - g ( x ) ，那么对任意的x d 有 h ( x - 1 ) + h ( x + l ) 2 = ! ：坠! ! 盐g ( x - 1 ) + g ( x + 1 ) 2 2 = j ( x ) - 时) ；h ( x ) 所以， 也是定义在s 上的调和函数。又对任意的z 矗，h ( x ) - - - o , 由定理2 1 得，对任意的x e s ， 浙江大学硕士学位论文 o ) ；o 这就是说对任意的x e s ，瓜) = 9 0 ) 。证毕。 我们考虑另一个不同的问题。 例2 1 考虑如图2 1 的电路 ，“。“”叫 o i 一。三。一曼。 圈2 1 每相邻两节点闽的电阻均为贾，在两端点闽放1 伏电压。以v ( 对表示x 点的电压。 则 v ( o ) = 0 ，( 2 4 ) v ( ) = 1 ( 2 + 5 ) 由k i r c h h o f f 电流定律，对每一点1 x n 一1 ，流进x 的电流与流出x 的电流相 等，即 v ( x + 1 ) - v ( x ) + v ( x - 1 ) - v ( x ) ：0 rr 整理得 啦) ：y ( x + 1 - ) + _ v ( 一x - 1 ) 。 所以v 也是s 上的调和函数且也满足( a ) 和( b ) 由唯一性定理，对所有 o 工，p ( 工) = v ( x ) 。而对于此电路易求得v 。) = 寿因此我们有 推论2 1 对所有o j s ，p 2 嘉。 ( 2 6 ) 2 2 平面上的调和函数及d l r l c h l e l ：问题 定义2 1 设5 为平面上的格点的有限集，若s = 口u 口满足以下条件： ( a ) 口n 占= 中 浙江大学硕士学位论文 ( b ) 口中的每一个点都有s 中的四个点与其相邻 ( c ) b 中的每一个点至少与口中的一个点相邻 进一步地，我们假设s 以一种很漂亮的方式结合在一起，那就是对s 中任意两点 ，和q ，存在d 中点列 只) 使得p 鼻，只，q 组成一条从p 到q 的路径( 即 s 是连通的) 。那么，称口中的点为s 的内点，占中的点为s 的边界点。 定义2 2 定义在j 上的函数f ，若对任意的0 ，b ) e d 满足 ，( 。，6 ) ：丝生业丝生骘也坐业幽( 2 7 ) | 则称厂是调和的。 容易得出， ( 1 ) 常数是s 上的调和函数。 ( 2 ) 如果厂和g 都是s 上的调和函数，则对任意常数c 1 和c 2 ，c , f + c 2 9 ( e 是s 上的调和函数。 ( 3 ) 如果 正 是一列s 上的调和函数且1 m 工= f ，则f 也是s 上的调和 函数。 和一维的情况类似，我们有： 定理2 3 设f ( 工) 是定义在s 上的调和函数，那么，( x ) 在边界点上取到 最大值m 和最小值m 。 定理2 4 ( 唯性定理) 如果艄和gq ) 都是定义在点集s 上的调和函数， 且在边界点矗上有嚏x 卜甄x ) ，那么，( x ) 置武x ) v 工s 。 求给定边界值的调和函数的问题被称为d i r i c h i e f 问题。因此，平面上的带 边界吸收的随机徘徊问题实质就是求边界值为0 或1 的d i r i c h l e t 问题。 倒2 2 如下面前电路图2 2 浙江大学硕士学位论文 这里所有电阻都相等。让v ( a ，6 ) 表示( 口，b ) 点的电压。由基尔霍夫( k ir c h h o f f ) 电流定律，对于电路内部任何一点工一( 口6 ) 有 v ( a + l b ) 一v ( a ，6 ) v ( a 一1 ，6 ) 一v ( a ，6 ) 一一一一f r 一 + v ( a , b + 1 ) - v ( a , 一b ) + v ( a , b - 1 ) - v ( a , b ) ：0 r晨 即v ( a ，b ) ：v ( a + l , b ) + v ( a - l , b ) + v ( a , b + 1 ) + v ( a , b 一- 1 ) ( 2 8 ) 珥 所以，v 是调和的。 由定理2 4 可知，计算在电路内部任何一点上的v 值等价于求在圈2 3 所示 区域上的调和函数工因此边界值为0 或1 的d i r i c h l e t 问题就转化为求相应电 路的各节点的的电压。事实上任何边界值的o ir i c h l e t 问题都可转化为电路电压 的问题。 lil 1 ab 1r- cd e - ili o 图2 3 定理2 5 假设边界丑= 6 l ，岛 ，边界值为，慨) = 岛。令c f 为这样的电路： 浙江太学硕士学位论文 在s 上任意相邻两点接相同的电阻，b 中除b t 外其余节点接地，而n 端接1 伏电 压的电源( 即使得6 l 端保持1 伏的电压) 。则d i r i c h l e t 问题的解，满足对任何点 j 厂( “) = c f u ) ， t = 1 这里u ( “) 为在g 电路中u 点的电压。 证明： 我们已有u 是边界值为 例= o 篇 ( 2 9 ) ( 2 1 0 ) 的调和函数。所以，也是s 上的调和函数且满足边界值 f ( b t ) = q ( 2 1 1 ) 即，为d j r i c h l e t 问题的解。证毕。 当电压容易算出时，相应的d i r i c h l e t 问题就迎刃而解。反之，求解电压也 可以通过求解d i r i c h l e t 问题而得出。d i r i c h l e t 问题的求解有很多方法，在下 一章中我们将给出几种解法。 浙江大学硕士学位论文 3d i r i c h i e t 问题的几种解法 在这一章中，我们对于平面上的d ir i c h l e t 问题给出5 种解决方案，并对图 2 3 所示区域给出鲁自相应的计算结果。其中蒙特卡洛方法，迭代法和松弛法为 该问题近似解法，解线性方程组方法和m a r k o v 链法为精确解法。 3 1 蒙特卡洛方法 蒙特卡洛方法是一种基于计算机模拟的方法。对于任何内点a ，从该点出 发，进行简单随机徘徊，直到第一次到达某一边界点b ，取p 。_ ，( 6 ，) 为这 次简单徘徊的值。如此重复n ( n 足够大) 次，我们得到 p l p 2 ，- - - ，p 取 一 p ， p ：上l ，( 3 1 ) 由大数定理可得：当n 呻时 j 呻p ：= 俐。 对于平面上的简单随机徘徊，设s 为n 次独立的简单随机徘徊中到达值为 1 的边界点的次数，取q = 1 一p ，则由中心极限定理可得，vk 0 有 l i m p ( 一k s n 下- 一n p e ) = 。( ) ( 3 2 ) 4 n p q 其中m ( 七) 为标准正态分布在( “，t ) 区间的概率。 当k = 2 时m ( k ) = o 9 5 ， p ( 一2 与翟 2 ) “o 9 5( 3 3 ) q n p q 即：再 如 桴矾姓 一， 浙江大学硕士学位论文 因为历- 1 2 ， 所以，有 p ( 一 p p ( ) * 0 9 5 ( 3 5 ) v l t吖一 由上式可知，当n = 1 0 0 0 0 ，即；。o 0 1 时，透过蒙特卡洛方法得到的解与 v 再 真值之间的误差小于0 0 1 的概率近似于0 9 5 。 这个例子说明蒙特卡洛方法不是很有效。 3 2 迭代解法 迭代解的基本步骤为：保持函数在边界点上的值不变，令函数在内点上的初 值为0 ，如图3 1 所示 翻3 1 即j ? = 矗。= 。= 圩= 毫= o 因为， = 生产= 等竽t = 字 h = 半l = 半 所以，得到迭代公式： 浙江大学研士学位论文 ，= 半 ，= 竿 ：互芝旦 4 护= 盟竿丝 = 华 写成矩阵形式 令 = 迭代公式等价于： 工+ ，= x h 1 ) # 工；2 ” x 吐” + 1 2 1 ，2 3 4 0 o z ( = 工，1 工 j x 妒1 工 l “ 妒” 毫“ f = l 2 l 2 3 4 o o x ( “i ) = ( 3 6 ) ( 3 7 ) 定理3 1 ( 迭代法基本定理，见【9 】) 设有方程组 x = a x 七f 对于任意初始向量工o 及任意f ，解此方程组的迭代法( 即x ( “1 ) = 月x ( i + 广) 收敛的充要条件是 p 廊( 1 。 其中p ( 加为矩阵彳的谱半径。 可求得我们例子中的a 的谱半径 o心0心o 似o h o 心 l l l 0 o o h o l 心o o 0 似 1 l o m o 似0 妒妒妒妒矿 o心o“o l i 心o h 0 “ l l l o o o 似0 l h o o 0 n l l o 似o h 0 浙江大学硕士学位论文 p ( a ) = o 5 3 3 9 1 ， 由迭代法基本定理可知以上迭代法是收敛的。 一般地，设边界点数为6 ，而内点数为n 。我们可以得到转移概率矩阵的标 准型： p = k 匀 ( 3 8 ) 其中，为6 阶单位矩阵( 对应为口中状态) ，一为n n 的矩阵( 对应为d 中状态 的转移矩阵) 。 对于 维复向量工，我们定义 删。= 瑚x l f ) 忙8 ：= ( h | 2 ) 1 ，2 i - i ( 3 9 ) ( 3 1 0 ) 那么，对我们的例予，用以上方法进行迭代，当b 4 7 时，i 工石壮 0 0 0 1 。 下图是k = - 4 7 时的结果： ll ； i ； 】0 8 2 3 o 7 8 7 l 圈3 2 设初始值为，”，第女步迭代后的值为，“，m 和m 分别为，。的最小值和 最大值设此d i r i c h l e t 问题的精确解为，。 定理3 2 矩阵4 的半径p ( 爿) l ，且对任意七2 0 0 ，“一，1 6 p ( 一) i i f “一，i ( 一) ( ，一m ) 。 o 32 3，； 0 6 l印； o 67 8；，。i 0 一 浙江大学硕士学位论文 证明：因为d 中各点暂留，所以对所有“d 和v s ， ! 蝤搿= o a 因此! i _ m 。a = 0 ，所以p ( 彳) 1 。 令。爿i b = 罂等警因为一对称，所以i i a i k = p ( 一) 。 把厂和，分别写成 ，= 魄 州性 豺( 甜 由于以“”= 晚+ 钟和，d = 矾+ 饥， | l ，m ”- f 1 1 。= lj 厂；“- a1 t 2 - - i 铂“一晚i k - i i aj i h i 以“一厶= p ( _ ) l i f “一fl k 。 因此对任意k 0 ， i i 厂“一，s p ( 彳) i i f “一，i l 。 因为p ( 4 ) 1 ， 所以，”按照k 范数收敛于f ，因而 受“一f 伸1 6 = l l f f 由于，= p k f “，而p 的各行之和均为1 ，所以，1 的各个分量均不小于研且 不大于m 由此得出对所有k 2 1 ， q - f 扣i l = i i ，j “一，j o i b - 4 ；( m m ) 。 证毕。 3 3 松弛法 我们已知d i r i c h l e t 问题就是寻找一个函数，它的边界值已经给定，而 在每一个内点的值都为其4 个相邻点的平均。给定误差， 松弛法的步骤就是： 步骤1 ：给厂一个初始值，且在边界上的初始值就为给定的边界值。 浙江丈学硕士学位论文 步骤2 ：给所有内点排一个序，即这些内点分别为d 。，d ：，d 。 步骤3 ：调整，( d 1 ) 的值为其4 个相邻点的平均，再调整( d 2 ) 的值为其4 个 相邻点的平均，调整，( 或) 的值为其4 个相邻点的平均。 步骤4 ：重复步骤3 ，一直到前后两次，在每个点的差都小于给定的误差。 仍以例2 2 为例，取初始值如图3 1 ，即，在内点的初始值均为0 。给定误 差为0 。0 0 1 取j 崾序为c _ d 一口_ e 专b 。则第一次的调整为 f ( c ) = ( 1 4 ) ( i + 1 + i + 0 ) = o 7 5 f ( d ) = ( 1 4 x o 7 5 + 0 + 0 + 0 ) = o 1 8 7 5 ， ，( 口) = ( 1 4 ) ( 0 1 8 7 5 + i4 - l + 0 ) = 0 5 4 6 9 ， f ( e ) = ( 1 4 ) ( o 1 8 7 5 + 0 + 0 + 0 ) = o 0 4 6 9 f ( b ) = ( 1 4 ) ( o 0 4 6 9 + 0 0 5 4 6 9 + i + i ) = o 6 4 8 4 4 e 重复这样的调整，第8 次和第9 次的调整，得到各值的前三位对应相等，且为如 图3 2 所示的结果。这说明松弛法很有效。下面我们给出理论上的证明。 设，为d i r i c h l e t 问题的解。 引理3 1 若初始值- r 满足每一内点的值均不大于四个相邻点的均值， 则对每一点u e s ，( h ) 单调递增收敛于f ( u ) 。 证明：设m 为厂的最大值，令f 为d l 的四个相邻点组成的集合。由于 f 0 ) ( d ) = ( 川) 广( “) ， 抛把 ，o ( d i ) ，1 ( d 1 ) sm 。 对任意l f s ，令墨= d 1 d 2 ，日 u s 。令昂= 占。假设对任意| s ，已有 f ( 皿) f 1 c 仇) m ， 则，( 1 ( d 。) = ( 1 4 ) 1 f 。( “) +，( 1 ( “) 1 ， 从而 - d n t挑n m 吐t ，o ( d l “) f 1 ( _ d t + 1 ) m 。 哳江大翱i 士学位论文 由归纳法，o ( d f ) ，1 ( d i ) m 对任何l k n 成立，并且 厂m ( a ) = ( 1 4 ) 【 厂鳓 ) +，m ( 耻( 1 4 ) 厂m ( “) a _ e i , u | e j - i 蛳“f ，吐 一l删i 用同样的方法我们可以证明对任何k 0 和任何l ，n ， ，( d j ) s ，h 1 ( d i ) m 。 所以f n ( “) # l i m 厂( “) 在s 上点点存在且不大子m ，并且在b 上有 f = f 。 对任意的k 0 和任何1 i n ， ，“( 马) = ( 1 4 ) f 厂”( 口) + ，“1 ( ”) 】， * n | 螂| l 砸h 两边取极限得 f e ) ( q ) = ( i 4 ) e f e ) ( “) 。 峨m 所以，n 也是s 上的调和函数。由难一性定理，f = f 。证毕。 事实上引理3 1 中，o 的最大值可在边界上达到。若存在点“d ，使得 ，o ) = m a x 厂o = m 。因为，o 0 ) 不大于“的四个相邻点的均值，所以“的相 邻点的值均为材。取一个的相邻点v ，使它x 方向的坐标比“的工方向坐标大i ， 则，o ( v ) = m 。重复我们的方法，最后我们找到一个边界点w ，使得 ，o ( w ) = m 。 与引理3 1 类似，我们有 引理3 2 若初始值，伸满足每一内点的值均不小于四个相邻点的均值，则对 每一点“s ，( “) 单调递减收敛于f ( u ) 。 引理3 2 中，m 的最小值可在边界上达到。一般地。我们有 定理3 3 对任意给定的初始值，“，对每一点h e g ，( “) 收敛于，( ) 。 证明。设i n 和m 分别为厂o 的最小值和最大值。对任意内点“，令 o ( 材) = 肌 浙江大学硕士学位论文 和 g o ( “) = m 则 o f o g “。对任意边界点，令h 。1 ( ) = g o ( “) = f ”( 材) = ，( “) 。对任 意k 2 0 和任意内点“，令 ( “) 和g ( ) 分别表示给定初始值a o 和g “，用松 弛法第i 次调整“点的取值后u 点的取值。则对任意k 0 ， h s f g “。 由于 呻满足每一内点的值均不大于四个相邻点的均值。而g o 满足每一内点的 值均不小于四个相邻点的均值，由引理3 1 和引理3 2 ， i l t l h ”= 1 i r a g 的= f 。 t - * t 因此由夹逼定理 妞，似= 厂- 证毕。 关于这个定理还有另外一种证明，见【1 】中3 5 节的习题2 。 下面给出松弛法的收敛速度。设m 和m 分别为，枇的最小值和最大值。令 f = m i n 。我们取d 中元素的顺序如下：先取d 中一点使得它至少与1 个边界 点相邻，再取d 中一点使得它至少与1 个已取点( 包括边界点) 相邻，后面所取 点均至少与1 个已取点( 包括边界点) 相邻，直到取完为止。因为s 是连通的， 所以能够取尽的。比如我们可以这样来取，d 中点按照x 坐标从小到大来取，对 于相同善坐标的点则按照y 坐标从小到大的顺序来取。令蜀= d 1 。d 2 ，d 。 u 昱 ( 其中e o = b ) 。那我们的取法就是使得对所有l s i ，d l 至少与五。中的一 点相邻。下面定理说明松弛法的收敛速度是指数速度。 定理3 4 对任何t l ，l l f 坤) 一f l l - ( 瓮) s 。 证明由松弛法，对任意七l ，州，”膨所以 m f = 熄f 舢s m 。 因此jj ，“一厂i 乙m - m = s 。假设我们已有 浙江大学硕士学位论文 广( 爿s 。 令为d f 的凹个相邻点组成的集合。凼为d 1 生少与1 个边界点车日邻，j j 叶以 i f “1 ( d 】) - f ( d ，) ：( 1 4 ) i i f ”( v ) 一，( v ) 】i y e n i ( 1 4 ) i f 似( v ) 一，( v ) i + ( 1 4 ) i f 1 ( v ) 一，( v ) j 惟扎瞧口馑m ，傩j 詈( 爿“ 假设我们已有对所有1 f f ， if ( k + 1 ) ( d l h ( 嘟等f 等卜 则因为d r + 。至少与d 1 ，岛，d j 及占中一点相邻，所以 j ，m ”( d f + ，) 一，( d ，；) 峰( 1 ，4 ) i ，“( u ) - f ( u ) i + ( 1 4 ) i ，( ) 一，( ) l s 愀剥占+ ； s 等 铡。占。 由归燃i 协删吕孚降卜降 “对黼姚硪 立。也就黜炉枷，| 【d 剥“1 。 所以对任何l ，i i ，一f l l 4 。- 1 ) s 。 证毕。 在我们这个例子中，步骤2 中内点顺序的选择对松弛法的收敛速度影响不 大- 当取误差占= 1 0 ，终止步数分别为1 0 步或1 1 步，当取误差占= 1 0 ，终止 步数分别为1 4 步或1 5 步。这同时说明了该算法收敛速度很快。 3 4 解线性方程组方法 对于如图2 3 所示的问题，因为 铲掣矗= 生铲罕 铲半t = 半 写成矩阵形式： fl j l 4 1 0 i 一1 4 ( 0 即 一1 4 l o o l 4 o 0 1 1 ，4 o 一1 4 o l 4 l 一1 4 o 一1 4 0 一l 4 1 x 4 托 t 如 t 1 2 l ，2 3 4 o 0 敲= f 系数a 是严格对角占优矩阵。 定理3 5 如果矩阵一严格对角占优的，那么，4 是非奇异的。 由定理3 5 可知矩阵一是可逆的。那么 x - - - - - a 一1 f 0 8 2 3 0 7 8 7 = 10 8 7 6 0 5 0 6 0 3 2 3 ( 3 1 1 ) ( 3 t 2 ) 3 5m a r k o v 链方法 m a r k o v 链最初是由俄国数学家m a r k o v 在1 9 0 6 年引进的，它是自然科学， 工程科学，社会科学各领域中一类常见的随机现象的有力工具。关于i l a r k o v 的 书可参见【2 】， 3 】， 4 】和【5 】。本节所介绍的i l a r l m v 链方法可以看成是一种更 巧妙的解线性方程组方法。 考虑平面上的随机徘徊，质点可能处的位置蜀，屯，j 。在随机徘 徊过程中，我们定义一系列随机变量以，栉= 0 ，1 ，2 其中x 。= i ( f s i , s ：，s ，) ) ，表示经过 步随机徘徊以后，质点处在位置f ( 或者称n 浙江大学硕士学位论文 步后质点处于状态f ) ，称s = 溉，s ：，s ， 为随机过程的状态集。 定义3 1 一随机过程 以，n 0 ) 称为一个离散参数的b a r k o v 链，如果 s ( n = 1 ，2 3 ) ，其中，状态集s 为一个有限或可数集( 称为此m a r k o v 链的状态空间) ，并且对任意的f ，_ ，o ，一，s ，都有 p ( 以。= 爿托= f 0 ，墨= ，z 。= i n - , 以= f ) ；p ( 。k 。= 卅z j = f ) ( 3 1 3 ) 称条件概率，( x = _ ，防。= f ) 为该h r k o v 链的( 一步) 转移概率，记为p o ( n ) 。 若p u ( n ) 与n 无关，则称此如r k 0 v 链为齐次的e 本文讨论的b a r k o v 链都是状态空间有限的齐次h r k o v 链。 定义3 2 称矩阵 p = ( 肌) 为此m a r k o v 链的转移概率矩阵。 对于平面上的随机徘徊，边界点上的状态有着特殊的含义，一旦质点进入这 些状态以后，就再也不能从这些状态中出来了，我们称这样的状态( 即风= 1 的状态) 为吸收态，称其它状态为非吸收态。 设一m a r k o v 链有个吸收态，v 个非吸收态，我们对状态空间s 进行排列， 将吸收态排在非吸收态的前面，如此，我们得到转移概率矩阵的标准型： p ；，g ( 3 1 4 ) 到 其中，为“阶单位矩阵o 为u x v 的零矩阵。 那么， 鲈l i r a 4 = 瞄习 鳓 其中 肛( z - q ) 一1 r ( 3 1 6 ) 设厂为定义在状态空间上的调和函数，即对所有fes ， 浙江大学硕士学位论文 f ( o = p f ，( ，) 写成向量形式，有 p f = f 那么， p 2 f = p ( p o = p f = f 以此类推，有对所有n 1 ， p “f = f 取 f = ( 割 ( 3 1 7 ) ( 3 1 s ) ( 3 1 9 ) ( 3 2 0 ) ( 3 2 1 ) 其中，向量f j 表示，在边界口上的值f c 表示厂在内点d 上的值。这里边界b 为 所有吸收状态组成的集合，而d 则为所有非吸收状态组成的集合。 由( 3 1 5 ) 式可得： 小瞄习( 割 即 f d = 胛j ( 3 2 2 ) ( 3 2 3 ) 对于平面上的d i r i c h l e t 问题f 口是给定的，通过( 3 2 3 ) 式，我们就可以求 褥f d 。 对于图2 3 上的点进行编号，结果如图3 3 i c j k蔓 1r e 1m n王 - ， l r1 l 圈3 3 2 0 堑翌丕堂堡主兰堡丝奎 一 那么转移概率矩阵为 abcd e fg hi j klmn 口 扫 c d f f p | ： f 膏 ? 所 以 ooo o l 4ooo ou 401 4 ooo0 o0 “4o h ；( i - q ) q = 1 1 7 4 2 0 3 3 7 1 0 0 8 9 9 o 3 5 9 6 0 1 7 4 2 0o 00 00 “4o 01 4 0 ：3 3 7 1 1 1 6 8 5 0 0 4 4 9 o 1 7 9 8 0 3 3 7 1 0 0 8 9 9 0 0 4 4 9 1 0 7 8 7 o 3 1 4 6 0 0 8 9 9 2 l o l 4 0 l 4 0 1 1 4 o o o l ，4 0 3 5 9 6 0 1 7 9 8 o 3 1 4 6 1 2 5 8 4 0 3 5 9 6 o o 0 l 4 0 0 1 7 4 2 0 3 3 7 1 o 0 8 9 9 0 3 5 9 6 1 1 7 4 2 l 4 0 l ，4 o 1 4 o l 4 o 1 4 o 0 o o o o o 0 o o o心o心o 1 1 o o 0 o o o o o o m o m o m 1 l 1 o o 0 o o o o o 0 o 0 o 胆h 1 l o o o o o o 0 0 o h o o o o l o o o o o o o o o o 饵o 腿m o o o o o o o o 1 o o o o o o o o o o o o 1 0 o 0 o 心o l 0 o o o o o l o o o o h o o l o o o o o 1 o o 0 o o o o hl o o o o 1 o o o o o o 心0 o l o o o o o 0 o o o 似o o o o o o o 0 o 0 o h o 似o o 1 1 o 1 o o o o o o o o 似o o o i 1 o o o o o o o o m o o o o w o o o o 膳o o o “o o o 0 = 浙江大学硕士学位论文 b = n r = f 口= ，徊) ，( 6 ) ，( c ) 厂( d ) f ( e ) f ( f ) ，( g ) ( ) f ( o 0 2 9 3 5 0 0 8 4 3 o 0 2 2 5 o 0 8 9 9 o 0 4 3 5 o 0 8 4 30 31 6 0n 0 8 4 3o 0 2 2 5 0 - 2 9 2 1n 0 9 5 50 2 9 2 10 0 1 1 2 n o l l 20 2 9 2 lo _ 0 1 1 20 2 6 9 7 n 0 4 4 9o - 1 6 8 5n 0 4 4 90 d 7 8 7 0 0 8 4 3o 0 6 6 00 0 8 4 3o 0 2 2 5 f d = b f j = ，( _ ，) f ( k ) ，( ，) ，( m ) 厂( 再) n 0 4 3 50 0 2 2 5 n 0 8 4 30 o l l 2 0 0 2 2 50 2 6 9 7 o - 0 8 9 9o 0 7 8 7 o 2 9 3 5 瞌0 2 2 5 o 8 2 3 0 1 0 7 8 6 5 l 0 8 7 6 4 l 0 5 0 5 6 l o 3 2 3 0 j 0 0 8 9 9 0 0 4 3 筑 0 0 4 4 90 0 8 4 3 1 0 0 7 8 7n 0 2 2 5 i o 31 4 60 0 8 9 9 1 0 0 8 9 9 0 2 9 3 5 ) 浙江大学硕士学位论文 4 电路上的随机徘徊 4 1 一般电阻的电路和可逆m a r k o v 链 前面我们讨论的是一类特殊的电路，这些电路中的各个电阻均为单位电阻。 下面我们将引入更一般的电阻电路，并考虑它所对应的随机徘徊。( 本章的结果 主要参考【1 】中第三章的结论。) 定义4 1 一个图是一些有限点的集合( 这些点也被称为节点) ，这些点中有 些点之间有边相连。这个图被称为是连通的，如果图上的任何两点都可以通过一 些边来相互到达。 我们现在总假设g 是一个连通图，对每一条边x y ，分配电阻r 。，如图4 1 ， 这条边x y 的传导率为c 0 = 1 r 。，对应各边的传导率见图4 2 。 d t l 圈4 1 圈4 2 定义一个g 上的随机徘徊为这样的一个m a r k o v 链，它的转移矩阵，为 = 争 这里，c = 岛。 、，jv 对于我们的例子 c 4 = 2 ，g - - 3 。c - - 4 ，q - - - 5 ，转移矩阵 口 p = 6 c d abcd 00l 2 l 2 00l ，32 3 l 41 40l ，2 l 52 ，52 5o ( 4 i ) 因为图连通，所以任意两点之间可达，具有这样性质的m a r k o v 链被称为是 * ， x 一彳 风 、 塑坚查兰受主兰垒兰奎 遍历m a r k o v 链。对于遍历m a r k o v 链，存在唯一的不变概率向量w 使得 w p - - w 。 ( 4 2 ) 对于由电路决定的随机徘徊，它的不变概率向量是这样给出的 = 罟 ( 4 s ) 这里c = c ，。 对于我们的例子e = 2 ，g = 3 ，e = 4 ，q = 5 ，c = 1 4 因此 w = ( 西2 ，百3 ，百4 ，西5 ) 。 ( 4 4 ) 一个遍历m a r k o v 链称为是可逆的如果坼岛= & 对所有j ，y 成立。对于 由电路决定的遍历m a r k o v 链，它总是可逆的，这是因为 w ，岛= 告岛= 告鲁= 争= 等= 告苦= w ，。 s ， 假如可逆遍历m a r k o v 链的初始速度为不变概率测度w ，则对任意点列 q ，吼，以，有心。气屹丘一限= 气嘶一，乞 。如我们的例子中的序 列口bcd ，则这个序列发生概率为 匕毛= 云吾i 1 罟= 面t ， ( 4 6 ) 而反列发生概率为 w 。屹气= 百5 号；i 1 = 面1 。 ( 4 7 ) 假如p 是可逆的避历m a r k o v 链，则p 是一个由电路决定的随机徘徊的转移 矩阵( 事实上定义c 。= w z p 。即可) 注意到假如殳0 ，则对应的电路中从x 到x 也需要一个电阻。因此，可逆性刻画了由电路决定的遍历m a