Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Hybrid computer solutions of partial differential equations by Monte Carlo methods Little, Warren David 1965

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1965_A1 L5.pdf [ 4.93MB ]
Metadata
JSON: 831-1.0104848.json
JSON-LD: 831-1.0104848-ld.json
RDF/XML (Pretty): 831-1.0104848-rdf.xml
RDF/JSON: 831-1.0104848-rdf.json
Turtle: 831-1.0104848-turtle.txt
N-Triples: 831-1.0104848-rdf-ntriples.txt
Original Record: 831-1.0104848-source.json
Full Text
831-1.0104848-fulltext.txt
Citation
831-1.0104848.ris

Full Text

The Un i v e r s i t y of B r i t i s h Columbia FACULTY OF GRADUATE STUDIES PROGRAMME OF THE FINAL ORAL EXAMINATION FOR THE DEGREE OF DOCTOR OF PHILOSOPHY of WARREN DAVID LITTLE B.A.Sc, The University of B r i t i s h Columbia, 1961 M.A.Sc, The University of B r i t i s h Columbia, 196 3 FRIDAY, OCTOBER 22, 1965, at 4:00 P„M, IN ROOM 402, MacLEOD BUILDING COMMITTEE IN CHARGE Chairman: L McT, Cowan E„ V. Bohn A, D„ Moore R. W. Donaldson C/A,~Swanson H. P. Zeiger Research Supervisor: A. D. Soudack External Examiner: L. D. Kovach Pepperdine College Los Angeles, C a l i f o r n i a HYBRID COMPUTER SOLUTIONS OF PARTIAL DIFFERENTIAL EQUATIONS BY MONTE CARLO METHODS ABSTRACT A continuous Markov process i s examined for the pur-pose of developing Monte Carlo methods for solving p a r t i a l d i f f e r e n t i a l equations. Backward Kolmogorov equations for conditional p r o b a b i l i t y density functions and more general equations s a t i s f i e d by a u x i l i a r y p r o b a b i l i t y den-s i t y functions are derived. From these equations and the i n i t i a l and boundary conditions that the density functions s a t i s f y , i t i s shown that solutions of p a r t i a l d i f f e r e n t i a l equations at an i n t e r i o r point of- a region can be written as the expected value of randomly-selected i n i t i a l and boundary values. From these r e s u l t s , Monte Carlo methods for solving homogeneous and nonhomogeneous e l l i p t i c , and homogeneous parabolic p a r t i a l d i f f e r e n t i a l equations are proposed. Hybrid computer techniques for mechanizing the Monte Carlo methods are given. The Markov process i s simula-ted on the analog computer and the d i g i t a l computer i s used to control the analog computer and to form the re-quired averages. Methods for detecting the boundaries of regions using analog function generators and electron i c comparators are proposed. Monte Carlo solutions are obtained on a hybrid system consisting of a PACE 231 R-V analog computer and an ALWAC III-E d i g i t a l computer. The in t e r f a c e for the two computers and a multichannel, d i s c r e t e - i n t e r v a l binary-noise source are described. With t h i s equipment, solu-tions having a small variance are obtained at a rate of approximately f i v e minutes per sol u t i o n , Example solutions are given for Laplace's equation i n two and three dimensionsPoisson'.s equation in'two dimensions and the heat equation in' one, two and three dimensions. GRADUATE STUDIES F i e l d of Study: E l e c t r i c a l Engineering Applied Electromagnetic Theory E l e c t r o n i c Instrumentation Network. Theory Servomechanisms Solid-State E l e c t r o n i c Devices Nonlinear Systems Electron Dynamics D i g i t a l Computers Related Studies: G. B. Walker F. K. Bowers A 0 D. Moore E. V. Bohn M o P. Beddoes A. C. Soudack G. B. Walker E. V. Bohn Numerical Analysis I Computer Programming Integral Equations T. Hull C. Froese E. Macskasy PUBLICATIONS Beddoes, M.P. and L i t t l e . W.D., " U n i l a t e r a l Para-metric Frequency Converters with Nonlinear Conduct -ance and Capacitance", Proc, IEEE, Vol. 52, No. 3, p. 333, March, 1954. Soudack, A.C. and L i t t l e , W.D., "An Economical Hybridizing Scheme for Applying Monte Carlo Methods to the Solution of P a r t i a l D i f f e r e n t i a l Equations", Simulation, Vol 5, No. 1, pp. 9-11, July, 1965. L i t t l e , W.D., "An E l e c t r o n i c SPDT Switch", Simula- tion, Vol.- 5, No. 1, P. 12, July, 1965 L i t t l e , W.D., and Soudack, A.C, "On the Analog Computer Solution of First-Order P a r t i a l D i f f e r e n t i a l Equations", Annales AsICA, October, 1965. Kohne, H., L i t t l e , W.D., and Soudack, A.C, "An Economical Multichannel Noise Source", Simulation, to be published, November, 1965. H Y B R I D COMPUTER S O L U T I O N S OP P A R T I A L D I F F E R E N T I A L E Q U A T I O N S B Y MONTE C A R L O METHODS WARREN D A V I D L I T T L E B . A . S c , U n i v e r s i t y o f B r i t i s h C o l u m b i a , 1961 M . A . S c . , U n i v e r s i t y o f B r i t i s h C o l u m b i a , , 1963 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L M E N T OF T H E R E Q U I R E M E N T S F O R T H E D E G R E E OF DOCTOR OF P H I L O S O P H Y i n t h e D e p a r t m e n t o f E l e c t r i c a l E n g i n e e r i n g We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d M e m b e r s o f t h e D e p a r t m e n t o f E l e c t r i c a l E n g i n e e r i n g T H E U N I V E R S I T Y OF B R I T I S H C O L U M B I A O c t o b e r , 1965 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an advanced degree a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r -m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e Head o f my Department o r by h i s r e p r e s e n t a t i v e s , , I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i -c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada Date A B S T R A C T A c o n t i n u o u s M a r k o v p r o c e s s i s e x a m i n e d f o r t h e p u r p o s e o f d e v e l o p i n g M o n t e C a r l o m e t h o d s f o r s o l v i n g p a r t i a l d i f f e r -e n t i a l e q u a t i o n s . B a c k w a r d K o l m o g o r o v e q u a t i o n s f o r c o n d i t i o n a l p r o b a b i l i t y d e n s i t y f u n c t i o n s a n d m o r e g e n e r a l e q u a t i o n s s a t i s -f i e d b y a u x i l i a r y p r o b a b i l i t y d e n s i t y f u n c t i o n s a r e d e r i v e d . F r o m t h e s e e q u a t i o n s a n d t h e i n i t i a l a n d b o u n d a r y c o n d i t i o n s t h a t t h e d e n s i t y f u n c t i o n s s a t i s f y , i t i s s h o w n t h a t s o l u t i o n s o f p a r t i a l d i f f e r e n t i a l e q u a t i o n s a t a n i n t e r i o r p o i n t o f a r e g i o n c a n b e w r i t t e n a s t h e e x p e c t e d v a l u e o f r a n d o m l y - s e l e c t e d i n i t i a l a n d b o u n d a r y v a l u e s . F r o m t h e s e r e s u l t s , M o n t e C a r l o m e t h o d s f o r s o l v i n g h o m o g e n e o u s a n d n o n h o m o g e n e o u s e l l i p t i c f a n d h o m o g e n e o u s p a r a b o l i c p a r t i a l d i f f e r e n t i a l e q u a t i o n s a r e p r o p o s e d . H y b r i d c o m p u t e r t e c h n i q u e s f o r m e c h a n i z i n g t h e M o n t e C a r l o m e t h o d s a r e g i v e n . ' T h e M a r k o v p r o c e s s i s s i m u l a t e d o n t h e a n a l o g c o m p u t e r a n d t h e d i g i t a l c o m p u t e r i s u s e d t o c o n t r o l t h e a n a l o g c o m p u t e r a n d t o f o r m t h e r e q u i r e d a v e r a g e s . M e t h o d s f o r d e t e c t i n g t h e b o u n d a r i e s o f r e g i o n s u s i n g a n a l o g f u n c t i o n g e n e r a t o r s a n d e l e c t r o n i c c o m p a r a t o r s a r e p r o p o s e d . M o n t e C a r l o s o l u t i o n s a r e o b t a i n e d o n a h y b r i d s y s t e m c o n s i s t i n g o f a P A C E 2 3 1 R - V a n a l o g c o m p u t e r a n d a n ALWAC I I I - E d i g i t a l c o m p u t e r . T h e i n t e r f a c e f o r t h e t w o c o m p u t e r s a n d a m u l t i c h a n n e l d i s c r e t e - i n t e r v a l b i n a r y - n o i s e s o u r c e a r e d e s c r i b e d . W i t h t h i s e q u i p m e n t , s o l u t i o n s h a v i n g a s m a l l v a r i a n c e a r e o b t a i n e d a t a r a t e o f a p p r o x i m a t e l y f i v e m i n u t e s p e r s o l u t i o n . E x a m p l e s o l u t i o n s a r e g i v e n f o r L a p l a c e ' s e q u a t i o n i n t w o a n d t h r e e d i m e n s i o n s , P o i s s o n ' s e q u a t i o n i n t w o d i m e n s i o n s a n d t h e h e a t e q u a t i o n i n o n e , t w o a n d t h r e e d i m e n s i o n s . i i T A B L E OF C O N T E N T S P a g e L i s t o f I l l u s t r a t i o n s . . . . . . . . . . . . . . . V 1 A c k n o w l e d g e m e n t s . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . . . . . . v i i i 1. I N T R O D U C T I O N ' . . 1 1.2 T h e s i s O u t l i n e . . , . . . . * . . . « . . . . . . . « . 4 2. F U N D A M E N T A L R E L A T I O N S FOR MARKOV P R O C E S S E S 5 2.1 I n t r o d u c t i o n « 5 2.2 C h a p m a n - K o l m o g o r o v E q u a t i o n s f o r C o n t i n u o u s M a r k o v P r o c e s s e s w i t h i n B o u n d e d R e g i o n s . . . . . . . 5 2.3 B a c k w a r d K o l m o g o r o v P a r t i a l D i f f e r e n t i a l E q u a t i o n s . . . . . . . . . . . * . . . . . . . * . . . . . . « . . . . . . . * * . 10 2.4 A C o n t i n u o u s M a r k o v P r o c e s s f o r w h i c h B a c k w a r d K o l m o g o r o v E q u a t i o n s a r e V a l i d . . . . . . . . . . . . . . . . 17 2.5 P a r t i a l D i f f e r e n t i a l E q u a t i o n s S a t i s f i e d b y A u x i l i a r y P r o b a b i l i t y D e n s i t y F u n c t i o n s . . . . . . . 23 3. MONTE C A R L O METHODS F O R T H E S O L U T I O N S D F B O U N D A R Y -V A L U E P R O B L E M S ««o*#**e*«o-«« « • • •••••• 30 3*1 In *t 1*0(3. H C " t 1 0 1 1 « 9 < * * « e » e a a * « » * » * « * * 9 * 9 « « * « « * e * » * « * 30 3.2 S o l u t i o n s o f B o u n d a r y - V a l u e P r o b l e m s f o r P a r a b o l i c P a r t i a l D i f f e r e n t i a l E q u a t i o n s . . . . . . . . . . . . . . . . 31 3o3 S o l u t i o n s o f B o u n d a r y - V a l u e P r o b l e m s f o r E l l i p t i c P a r t i a l D i f f e r e n t i a l E q u a t i o n s 39 3.4 S o l u t i o n s o f N o n h o m o g e n e o u s B o u n d a r y - V a l u e P r o b l e m s « » » » » . » . . < > . . * . . « e » o » » « . » . o « . » « . « « » « o » » 42 3.5 E s t i m a t e s o f t h e N u m b e r o f R a n d o m W a l k s f o r M o n t e C a r l o S o l u t i o n s . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.5A C o n v e r g e n c e o f M o n t e C a r l o S o l u t i o n s . . . . 45 3»5B N u m b e r o f R a n d o m W a l k s f o r H o m o g e n e o u s P a r t i a l D i f f e r e n t i a l E q u a t i o n s . . . . . , . * . . 46 3.5C N u m b e r o f R a n d o m W a l k s f o r N o n h o m o g e n e o u s P a r t i a l D i f f e r e n t i a l E q u a t i o n s « . . . . . * . * . 47 i i i Page 4. COMPUTER MECHANIZATION OP MONTE CARLO METHODS FOR SOLVING- PARTIAL DIFFERENTIAL EQUATIONS ............. 50 4.1 Introduction ««»«*..«»««««.....«*»..««««..«««*. 50 4.2 Simulation of the Stochastic Process on an Analog Computer »»..•.•....«•.•......«...*..... 52 4.2A Analog Computer Setup ••••••*•••••••••.•« 52 4.2B Noise Source Requirements ............... 55 4.2C Ef f e c t of F i n i t e Bandwidths on Solution Times . . . . . . . . . . . . . . a . * . . . . * . . . . * . . . . * * . . 56 4.5 Detection of Boundaries .......*«.............. 57 4.3A Detection of Boundaries for Problems with One Space Variable «»....o............... 60 4.5B Detection of Boundaries f o r Problems with Two Space Variables »««.««««.««....»...«« 61 4.5C Detection of Boundaries for Problems with Three Space Variables »••«••••»..*•»'«••»• 66 4.4 Generation of I n i t i a l and Boundary Values ..... 67 4.5 Operations Performed by the D i g i t a l Computer 69 5. HYBRID COMPUTER SOLUTIONS OF ILLUSTRATIVE PROBLEMS . 75 5*1 Introduction «..«.«.*«.««..« « « « . » . . . . o • > * . . « . « « . 73 5.2 One-Dimensional Boundary-Value Problems ....... 73 5.3 Laplace Ts Equation i n Two Dimensions •«....•,«» 79 5»4 Poisson's Equation i n Two Dimensions .......... 79 5.5 Heat Equation i n Onet Two and Three Dimensions. 84 5*6 Laplace's Equation i n Three Dimensions ........ 86 5.7 Discussion of Results .•»•»..•*».*«*•*•«•.«...* 86 i v P a g e A P P E N D I X I I N T E R F A C E F O R T R A N S F E R OF D A T A B E T W E E N T H E P A C E 2 3 1 R - V AND T H E ALWAC I I I - E • • • » • • • » • • • • • • • • • • • • • • * • 9 1 A P P E N D I X I I M U L T I C H A N N E L D I S C R E T E - I N T E R V A L B I N A R Y - N O I S E SOURCE 9 5 A P P E N D I X I I I A N E L E C T R O N I C S P D T S W I T C H . . . . . . . . . . . . . . . . . . 9 8 A P P E N D I X I V A P R O G R A M F O R I M P L E M E N T I N G MONTE C A R L O METHODS . . . . . 1 0 0 A P P E N D I X V A V E R A G E D U R A T I O N OF RANDOM W A L E S «•»••••• * ••••• - • - 1 0 1 i R E F E R E N C E S « « v • o o o » » o e 9 e a o « g r 4 * o < T * « * « « f t « « 4 r « « « « < r « « « e * * « « o 1 0 3 LIST OP ILLUSTRATIONS Page 2 - 1 , Space Region I l l u s t r a t i n g Defined Terms »...»..«.«. 7 3 - 1 * Random Walks and I n i t i a l and Boundary Conditions of a Typical Problem with 1 Space Variable ••••••••••• 32 4 - 1 * Block Diagram f o r Simulation of a Stochastic D i f f e r e n t i a l Equation ••»•*««.*«»••*•«••«»*».*••«.« 5 3 4 - 2 * Block Diagram f o r Generation of "X « • • « • • • • • » • • • * • • 5 4 4 - 3 * Triggering of Mode-Control Flip-Plop .............. 5 8 4 - 4 . Detection of Termination Time t = 0 . . • • • • • • • • • • « * • 5 9 4 - 5 * Boundary Detection f o r Problems with. One Space Variable ••••••»•••••*«••.•*••••••*••••.••••••«*.*. 6 0 4 - 6 * Two-Dimensional Region..**<,..«.••*...«.«»...«..».». 6 1 4 - 7 * Two-Dimensional Boundary Detection • « « « o » « * * * * » » « « * 6 2 4 - 8 . Coordinate Transformation used f o r Boundary Detection of Two-Dimensional Simple Regions ••«»... 6 3 4 - 9 * Photograph I l l u s t r a t i n g a Detected Boundary 6 6 4 - 1 0 * Hybrid Computer System *»•••.*«•»«•••«•«.«•«•««•««» 7 0 4 - 1 1 . Flow Diagram for a Typical Hybrid Computer Program. 7 2 5 - 1 . Solutions of D. ^—^ + K = 0 • • « « * • « . • • • • • * * • • * 7 4 dx o 5 - 2 . Values of 1 0 0 0^(07 obtained with N = 1 0 0 0 . . . . . . . . 7 5 5 - 3 * Average Time f o r a Random Walk used f o r the Solution of a One-Dimensional Laplace Equation **»•»»«•*««»« 7 6 2 • 5 - 4 * Solutions of — % - ( 1 - x ) 0 = 0 • « • « » . . . . « • • • • « • « 7 8 o 5 - 5 . Solutions of Laplace's Equation as a Function of a Boundary Posit i o n * . » « • « • « • « . * . • « • * « * * * « . * « « « • * * • • 8 0 5 - 6 * Solutions of Poisson's Equation and Laplace Ts Equation i n the Region Shown ***•.»*.•**•*.***'**** 8 2 5 - 7 . Solutions of the Heat Equation used i n the Solution of Poisson rs Equation ••**»••*••*•*•»*•*•****«•«•• 8 3 v i Page 5-8* Solutions of the Heat Equation at the Centre of a Line* a Square and a Cubic Region *.»••••*•«••»*•> 85 5-9» Solutions of Laplace's Equation i n Three Dimensions 87 AI-1* Interface f o r Transfer of Data Between PACE and ALWAC • « • * • « • "«• • * « * • • • *'» » * » • • • • •'• «•••*««*»*••••*«•• 92 AI-2. Instructions f o r Activating" Stepping 1 Motor .»•*•«. 94 AII-1«. Block Diagram of 3-Channel Noise Source • •••».«••< 96 AIII-1. C i r c u i t and Patching for a SPDT Switch .*<•«•-»•<•'» 99 v i i ACKNOWLEDGEMENT A c k n o w l e d g e m e n t i s d u e t o a l l w h o h a v e h e l p e d d u r i n g t h e c o u r s e o f t h i s w o r k . I n p a r t i c u l a r , I w o u l d l i k e t o e x p r e s s my t h a n k s t o D r . A , C . S o u d a c k , s u p e r v i s o r o f t h i s p r o j e c t , f o r h i s a s s i s t a n c e a n d e n c o u r a g e m e n t ; D r . E . N o a k e s , H e a d o f t h e E l e c t r i c a l E n g i n e e r i n g D e p a r t m e n t , U . B . C . , f o r h i s i n t e r e s t a n d s u p p o r t ; M r . H . K o h n e f o r h i s a s s i s t a n c e w i t h t h e c o m p u t e r h y b r i d i z a t i o n ; a n d M r . R* E . B u t l e r f o r m a n y h e l p f u l d i s c u s s i o n s . . S p e c i a l t h a n k s a r e g i v e n t o my w i f e , L a u r i e , f o r h e r e n c o u r a g e m e n t a n d h e l p . A c k n o w l e d g e m e n t i s g r a t e f u l l y g i v e n t o t h e N a t i o n a l R e s e a r c h C o u n c i l . f o r S t u d e n t s h i p s a w a r d e d i n 1962, 1963, a n d 1964, a n d f o r e q u i p m e n t m a d e a v a i l a b l e t h r o u g h B l o c k G r a n t s t o t h e E l e c t r i c a l E n g i n e e r i n g D e p a r t m e n t , U . B . C . v i i i 1. INTRODUCTION 1.1 Introduction High-speed computing devices together with sophisticated numerical methods are inadequate for solving many p a r t i a l d i f f e r -e n t i a l equations encountered i n the study of continuous systems."*" Numerical methods called Monte Carlo methods are known for solving many functional equations including a class of p a r t i a l d i f f e r -2 e n t i a l equations, but when implemented on a d i g i t a l computer 3 the methods have generally proven to be v e r y / i n e f f i c i e n t . In r 4 I960 a Michigan report outlined a Monte Carlo method using an analog computer f o r solving a class of homogeneous e l l i p t i c p a r t i a l d i f f e r e n t i a l equations. In the Michigan study, solutions were obtained with a slow analog computer at approximately the same rate as that possible with a fast d i g i t a l computer. In t h i s project, a hybrid computer i s used to implement new Monte Carlo methods that are developed for solving a large class of both e l l i p t i c and parabolic p a r t i a l d i f f e r e n t i a l equa-tions. Computing techniques are developed so that, unlike the Michigan study, no special purpose equipment i s required. With the hybrid approach, many features, including the capacity to program an entire problem solving procedure and the capacity to obtain automatic printout of a l l solutions, are made possible . Most computer methods for solving p a r t i a l d i f f e r e n t i a l equations depend upon approximating the equations by a set of 1 5 f i n i t e - d i f f e r e n c e equations. ' The number of difference equations i n the set depends geometrically upon the number of 2 i n d e p e n d e n t v a r i a b l e s i n t h e p a r t i a l d i f f e r e n t i a l e q u a t i o n b e i n g a p p r o x i m a t e d a n d u p o n t h e . p r e c i s i o n r e q u i r e d i n t h e s o l u t i o n . F o r many p r o b l e m s t h e n u m b e r o f d i f f e r e n c e e q u a t i o n s t h a t a r e r e q u i r e d i s s u c h t h a t s t o r a g e a n d s o l u t i o n t i m e s i n t h e c a s e o f d i g i t a l c o m p u t a t i o n , o r e q u i p m e n t r e q u i r e m e n t s f o r a n a l o g C O m -zr p u t a t i o n * a r e e n t i r e l y u n r e a l i s t i c * O t h e r a n a l o g m e t h o d s s u c h a s s o l v i n g t h e s e t o f d i f f e r e n c e e q u a t i o n s w i t h p a s s i v e l u m p e d e l e m e n t s , e l e c t r o l y t i c - t a n k s i m u l a t i o n s a n d membrane a n a l o g i e s a r e s u i t a b l e f o r some p r o b l e m s , b u t i n a d e q u a t e f o r many o t h e r s . M o n t e C a r l o m e t h o d s a r e m e t h o d s w h i c h i n v o l v e t h e s a m p l i n g o f r a n d o m p r o c e s s e s a s a means o f a p p r o x i m a t i n g t h e s o l u t i o n s o f m a t h e m a t i c a l p r o b l e m s * T h e r a n d o m p r o c e s s i s r e l a t e d t o t h e p r o b l e m f o r w h i c h a s o l u t i o n i s d e s i r e d I n s u c h a m a n n e r t h a t r e p e a t e d v a l u e s d e t e r m i n e d b y t h e p r o c e s s c o n v e r g e i n a s t a t i s t i c a l s e n s e t o t h e s o l u t i o n * F o r many m a t h e m a t i c a l p r o -b l e m s s u c h a r a n d o m p r o c e s s c a n n o t b e f o u n d , a n d f o r o t h e r s , many are, k n o w n * I n t h e c a s e o f p a r t i a l d i f f e r e n t i a l e q u a t i o n s , s t o c h a s t i c p r o c e s s e s i n t h e f o r m o f r a n d o m w a l k s c a n b e u s e d t o s o l v e e q u a t i o n s t h a t a r e in; : -some way r e l a t e d t o d i f f u s i o n * A r a n d o m p r o c e s s i s a p r o c e s s e x h i b i t i n g v a r i a t i o n s f r o m o b s e r v a t i o n t o o b s e r v a t i o n w h i c h , n o a m o u n t o f e f f o r t o r c o n t r o l i n t h e c o u r s e of" a r u n o r t r i a l " c a n r e m o v e * ? T h e t e r m s t o c h a s t i c p r o c e s s i s u s e d t o d e n o t e a r a n d o m p r o c e s s o f a t i m e - d e p e n d e n t n a t u r e . ' 3 p r o c e s s e s . S u c h p a r t i a l d i f f e r e n t i a l e q u a t i o n s i n c l u d e t w o o f t h e t h r e e l i n e a r s e c o n d - o r d e r c a n o n i c t y p e s ; n a m e l y , e l l i p t i c ( e . g . L a p l a c e ' s e q u a t i o n ) a n d p a r a b o l i c ( e . g . t h e d i f f u s i o n e q u a t i o n ) e q u a t i o n s . P a r t i a l d i f f e r e n t i a l e q u a t i o n s o f t h e h y p e r b o l i c t y p e ( e . g . t h e w a v e e q u a t i o n ) a r e n o t a m e n a b l e t o s o l u t i o n b y t h e m e t h o d s t o b e d i s c u s s e d . I n a l l p a r t i a l d i f f e r e n t i a l e q u a t i o n s t o b e c o n s i d e r e d , t h e f o l l o w i n g p r o c e d u r e i s u s e d t o o b t a i n a p p r o x i m a t e s o l u t i o n s . A l a r g e n u m b e r o f r a n d o m w a l k s a r e s t a r t e d i n s e q u e n c e a t a p o i n t f o r w h i c h a s o l u t i o n i s d e s i r e d , a n d e a c h r a n d o m w a l k i s t e r m i n a t e d e i t h e r a t a p r e d e t e r m i n e d t i m e o r w h e n a b o u n d a r y i s r e a c h e d . A p r e s c r i b e d v a l u e , n o r m a l l y a n i n i t i a l o r b o u n d a r y v a l u e , i s s e l e c t e d a c c o r d i n g t o t h e t e r m i n a l p o s i t i o n o f e a c h w a l k , a n d t h e a v e r a g e o f a l a r g e n u m b e r o f s u c h v a l u e s i s d e t e r -m i n e d . A s w i l l b e s h o w n , t h i s a v e r a g e c o n v e r g e s i n a s t a t i s t i c a l s e n s e t o t h e s o l u t i o n a t t h e p o i n t w h e r e t h e r a n d o m w a l k s w e r e s t a r t e d . B y t h i s p r o c e d u r e , t h e s o l u t i o n a t a l l p o i n t s o f i n t e r -e s t c a n b e o b t a i n e d . I n t h i s w o r k , t h e r a n d o m w a l k s a r e g e n e r a t e d o n t h e a n a l o g c o m p u t e r a s t h e r e s p o n s e t o r a n d o m - n o i s e s o u r c e s . E l e c -t r o n i c c o m p a r a t o r s a n d f u n c t i o n g e n e r a t o r s o n t h e a n a l o g c o m p u t e r a r e u s e d t o d e t e r m i n e t h e t e r m i n a l p o s i t i o n s o f t h e w a l k s . T h e a d j o i n i n g d i g i t a l c o m p u t e r i s u s e d t o c o n t r o l t h e a n a l o g c o m p u t e r a n d t o a v e r a g e t h e v a l u e s a s s o c i a t e d w i t h t h e t e r m i n a l p o s i t i o n s o f t h e r a n d o m w a l k s . T h i s a p p r o a c h t a k e s a d v a n t a g e o f t h e s p e e d w i t h w h i c h r a n d o m w a l k s c a n b e g e n e r a t e d o n a n a n a l o g c o m p u t e r a s w e l l a s t h e d y n a m i c r a n g e a n d m e m o r y c a p a b i l i t i e s o f a d i g i t a l 4 computer. 1.2 Thesis Outline Following t h i s introductory chapter, p a r t i a l d i f f e r -e n t i a l equations are derived f o r certain conditional probability density functions of a class of Markov processes. In Chapter 3>these pro b a b i l i t y density functions are used to derive Monte Carlo methods that are proposed for solving a large.class of homogeneous and nonhomogeneous e l l i p t i c , a n d homogeneous parabolic p a r t i a l d i f f e r e n t i a l equations. The convergence of the Monte Carlo solutions to the exact solution i s also considered. The use of a hybrid computer fo r solving p a r t i a l d i f f e r e n t i a l equations by Monte Carlo methods i s discussed i n Chapter 4. Computing techniques, as well as l i m i t a t i o n s imposed by the equipment, are outlined. Novel methods fo r detecting boundaries for problems with one, two and three s p a t i a l dimen-sions are also proposed. Experimental results are given i n Chapter 5 - The examples i n t h i s chapter include solutions of Laplace's equation and Poisson's equation i n two and three dimensions,as well as solutions of the heat equation i n one, two and three dimensions. Five appendices follow the conclusions given i n Chapter 6. Included i n these appendices are the d e t a i l s of the 8 interface that was b u i l t to l i n k the two computers and the de-scription..of a new type of multichannel noise source that was Q developed f o r t h i s project. 5 2. FUNDAMENTAL RELATIONS FOR MARKOV PROCESSES 2.1 Introduction In t h i s chapter certain conditional probability density functions of stochastic processes known as continuous Markov processes are defined and shown to be fundamental solutions of a class of parabolic p a r t i a l d i f f e r e n t i a l equations. The form of the p a r t i a l d i f f e r e n t i a l equations that are developed i s closely related to the form of the equations f o r the boundary-value problems that can be solved by the proposed Monte Carlo methods. In order that the methods apply to p a r t i a l d i f f e r e n t i a l equations of a very general form, a very general Markov process that can be r e a d i l y simulated on an analog computer i s considered. 2.2 Chapman-Kolmogorov Equations f o r Continuous Markov Processes  within Bounded Regions To solve a boundary-value problem that i s defined on an open bounded region R and i t s boundary C, a continuous Markov process r(t ) , defined on R and C, i s considered. In this work, R i s assumed to be a one, two or three-dimensional region, and the vector r ( t ) i s assumed to have components x, y and z i n a cartesian coordinate system. A continuous Markov process can be defined as a sto-chastic process having the-property that future^ values of .r.,.; depend upon a time-Ordered set of known values of. r only 7 through the l a s t available value,* 6 That i s , i f r i s known t o e q u a l r Q a t time t ,then the v a l u e o f r a t some f u t u r e time t 2 i s i - n n o w a v dependent upon known v a l u e s o f r a t some e a r l i e r time t , <^t . From t h i s d e f i n i t i o n i t - l ^ o 7 can be shown t h a t the c o n d i t i o n a l p r o b a b i l i t y d e n s i t y f u n c t i o n f ( 1 * 2 ^ 2 ^ 0'^ 0) c o m p l e t e l y d e s c r i b e s the s t a t i s t i c a l p r o p e r t i e s o f r where f i s d e f i n e d as f o l l o w s . D e f i n i t i o n f ( ? 2 , t 2 | ?q*"fcQ)01^*2 i s the p r o b a b i l i t y t h a t the random v e c t o r r i s i n d ^ a t time t 2 i f a t time. t , r = v . o' o The terms g i v e n i n the d e f i n i t i o n a r e i l l u s t r a t e d i n F i g u r e 2 - 1 . The d i f f e r e n t i a l d r 2 t h a t i s used i n the d e f i n i t i o n i s an element o f g e n e r a l i z e d volume a t the p o i n t d e f i n e d by ? 2 . That i s , d r ^ i s e i t h e r d x 2 , dx,dy 2 o r d x 2 d y 2 d Z 2 depending upon the dimension o f R. An elementary p r o p e r t y o f the c o n d i t i o n a l d e n s i t y f u n c t i o n f f o r a Markov p r o c e s s i s t h a t i t s a t i s f i e s the f o l l o w -7 i n g Chapman-Kolmogorov i n t e g r a l e q u a t i o n ^ 2 > t 2 | r Q , t o ) = Jf(?2,t2 | r 1 , t 1 ) f ( r ^ ^ | r o , t o ) d r 1 ( 2 . 1 ) f o r a l l t <. t n < _ t 0 . O 1 2 T h i s e q u a t i o n e x p r e s s e s the f a c t t h a t a t r a n s i t i o n of r from r 7 a t t t o r ~ a t t 0 o c c u r s v i a s o m e p o i n t r , a t t i m e t-, . o 2 2 . 1 1 I n a d d i t i o n t o t h e c o n d i t i o n a l p r o b a b i l i t y d e n s i t y f u n c t i o n f , t h e f o l l o w i n g c o n d i t i o n a l p r o b a b i l i t y d e n s i t y f u n c -t i o n - g, i s a l s o d e f i n e d . D e f i n i t i o n g ( r ^ , t ^ j r Q , t ^ d r ^ d t ^ i s t h e p r o b a b i l i t y t h a t t h e . r a n d o m v e c t o r r w i l l r e a c h b o u n d a r y C w i t h i n d r ^ b e t w e e n t i m e s t ^ a n d t ^ + d t ^ i f a t t i m e t Q , r = r . o T h e t e r m d r ^ i n t h e d e f i n i t i o n i s a d i f f e r e n t i a l e l e m e n t o f g e n e r a l i z e d s u r f a c e a r e a a b o u t a p o i n t r ^ o n C . ( s e e F i g u r e 2 - 1 ) 3 x F i g u r e 2 - 1 . S p a c e R e g i o n I l l u s t r a t i n g D e f i n e d T e r m s ! 8 From the Markov property and the fact that a random walk from an i n t e r i o r point r Q at t to a boundary point r ^ at t^ must pass through some ? 1 at time t ^ <_ t^, i t follows that g must also s a t i s f y a Chapman-Kolmogorov equation; i . e . , S ^ b ^ b V V = h{h>\ ? 1 , t 1 ) f ( r 1 , t 1 r o , t o ) d r i (2.2) f o r a l l t < t, < L t. o — 1 b • The Markov processes used f o r solving p a r t i a l d i f f e r e n t i a l equations are i n i t i a t e d at time t at a point rQ within R,and are terminated either at a predetermined time ±2 ^  t Q or whenever the random variable r reaches a boundary point r ^ on C. Hence, i f a process i s terminated due to a boundary absorption, i t occurs at a time t ^ <_ t 2 . In view of these statements, f and g must s a t i s f y the following i n i t i a l and boundary conditions. A. I n i t i a l condition f o r f. lim f ( ? 2 , t 2 | r o , t Q ) = § ( ? 2 - r Q ) (2.3) where S ( ? 2 " ?o^ = 0 f o r ? 2 ^ *o a n d J^8^2 " ? o ^ d r 2 = 1 * R 9 This condition expresses the fact that the point of termination ? 2 i s the same as the star t i n g point r Q i f the process i s terminated immediately af t e r i t i s i n i t i a t e d . B. I n i t i a l condition for g. lim g ( ? v t b | ? 0 , t Q ) = 0 (2.4) That i s , the probability of reaching a boundary point r ^ i s zero fo r a walk s t a r t i n g at an i n t e r i o r point r Q when the walk i s terminated immediately af t e r i t i s i n i t i a t e d . C. Boundary condition for f. lim f ( ? 2 , t 2 | r o > t Q ) = 0 ( 2 . 5 ) ? o " ^ ? b This condition states that i f the st a r t i n g point r Q approaches a boundary point ? b there i s zero probability that r w i l l be i n an i n t e r i o r region d r 2 at a time t 2 > t Q . This i s true since the process w i l l terminate immediately at the boundary point r ^ . D. Boundary condition for g. lim g ( r b , t b r o , t Q ) = §(?<, - 5?b) § (*b " V o b where o ( r - r, ) b ( t , - t ) = 0 unless r = r, and t, = t w v o b b o o b D O 10 t . 2 a n d / / g ( r n - ? b) § ( \ - V d r b d t b = 1 A s t h e i n t e r i o r s t a r t i n g p o i n t r Q a p p r o a c h e s a b o u n d a r y p o i n t ? b , t h e p r o c e s s i s c e r t a i n t o t e r m i n a t e i m m e d i a t e l y a t t h e p o i n t i * b . I n a d d i t i o n t o t h e s e i n i t i a l a n d b o u n d a r y c o n d i t i o n s , t h e f o l l o w i n g i n t e g r a l r e l a t i o n m u s t a l s o b e v a l i d f o r a l l r Q a n d t : • o • H f ( ? 2 , t 2 I r Q , t o ) d r 2 + / ' I S(rh,\ r ^ t j d r ^ = 1 o ' o b b R t Q C (2.7) T h e f i r s t t e r m o f t h i s e q u a t i o n i s t h e p r o b a b i l i t y t h a t r i s w i t h i n t h e b o u n d a r y a t t i m e t 2 , a n d t h e s e c o n d t e r m i s t h e p r o -b a b i l i t y t h a t r h a s r e a c h e d a b o u n d a r y w i t h i n t i m e t g . S i n c e o n e o f t h e t w o e v e n t s m u s t b e t r u e , t h e s u m o f t h e t w o t e r m s i s u n i t y . I n t h e f o l l o w i n g s e c t i o n t h e C h a p m a n - K o l m o g o r o v i n t e -g r a l e q u a t i o n s (2.1) a n d (2.2) a r e c o n v e r t e d t o s e c o n d - o r d e r p a r t i a l d i f f e r e n t i a l e q u a t i o n s . 2.3 B a c k w a r d K o l m o g o r o v P a r t i a l D i f f e r e n t i a l E q u a t i o n s T h e C h a p m a n - K o l m o g o r o v i n t e g r a l e q u a t i o n s o f t h e p r e v i o u s s e c t i o n a r e c o n v e r t e d t o p a r t i a l d i f f e r e n t i a l e q u a t i o n s b y e x p a n d i n g a t e r m i n t h e i n t e g r a n d s o f t h e i n t e g r a l e q u a t i o n s 1 1 i n a T a y l o r s e r i e s a b o u t t h e i n i t i a l p o i n t r , a n d t h e n t a k i n g a l i m i t . F o r a g e n e r a l M a r k o v p r o c e s s a l l t e r m s o f t h e ^ T a y l o r s e r i e s a r e r e q u i r e d i n t h e e x p a n s i o n s , b u t f o r M a r k o v p r o c e s s e s i n w h i c h t h e r a n d o m v a r i a b l e r c h a n g e s b y o n l y a s m a l l a m o u n t i n a s m a l l t i m e i n t e r v a l A t , o n l y t h e f i r s t t w o t e r m s o f t h e s e r i e s c o n t r i b u t e w h e n t h e l i m i t i s t a k e n . T h e r e s u l t i n g s e c o n d - o r d e r p a r t i a l d i f f e r e n t i a l e q u a t i o n s a r e c a l l e d b a c k w a r d K o l m o g o r o v e q u a t i o n s . C o n s i d e r C h a p m a n - K o l m o g o r o v e q u a t i o n ( 2 . 1 ) f o r t 1 = t + At; i . e . , f ( r 2 , t 2 | ? o , t Q ) = J f ( ? 2 , t 2 | r 1 , t Q + A t ) f ( ? 1 , t Q + A t | r Q , t o ) d r R ( 2 . 8 ) F o r A t s m a l l , t h e t e r m f (r - , , t + A t I r , t ) i s t h e 1 o l o o i n c r e m e n t a l t r a n s i t i o n p r o b a b i l i t y d e n s i t y o f t h e p r o c e s s . I t g i v e s t h e d i s t r i b u t i o n o f d i s p l a c e m e n t s a f t e r a s m a l l t i m e A t . I f a f t e r At t h e d i s p l a c e m e n t f r o m r Q i s s o s m a l l t h a t t h e p r o b a b i l i t y o f r e a c h i n g a b o u n d a r y i s z e r o , i t f o l l o w s f r o m e q u a t i o n ( 2 . 7 ) t h a t l i m A t - ^ O f ( r 1 , t o + A t r , t ) d r n o ' o 1 1 ( 2 . 9 ) R T o c o n v e r t e q u a t i o n ( 2 . 8 ) i n t o a p a r t i a l d i f f e r e n t i a l e q u a t i o n , t h e t e r m f ( ? 2 , t 2 ^^.'^o + ^ ^ n ^ e e q u a t i o n i s expanded i n a Taylor series about r 0 - F o r "the expansion, a l l variables but are assumed to be fixed. The expansion yields f ( r 2 , t 2 r o,t Q+ At) R + l l ( r 2 , t 2 | r o , t o - r At)(x 1-z 0) + 4K? 2,t 2|r o,t o +At)(y 1-y o) + + ( ?2 * 1 21 ? o ' t o + A t } ( x i - x o } (yi-y Q> A 2 f ( r 2 , t 2 | r o , t o + A t ) ( x 1 - x o ) ( z 1 - 2 o ) + 6 x 0 6 z o ^ 2 f ( ?2,1 21? Q, t o+ At) (y-L-y0) ( Z - L - Z O ) + i^f£(? 2,t 2 r o , t o + A t ) ( X l - x o ) 2 2 b x 2 + | ^ 2 f ( ? 2 , t 2 | r o , t o + A t ) ( y 1 - y 0 ) ' 2 ^2 + 1 ^ 2 f ( ? 2 , t 2 | r o , t o + A t ) ( z 1 - z o ) ; 2 ^2 13 + higher-order terms f ( r l f t 0 f A t V t ^ (2.10) I f , 1. terms not involving x^, y^ or z^ are taken outside the integral, 2. equation (2.9) is used, 3. a l l terms are divided by At, and the following limits are assumed; i i m Tit r^xi-xo)f(?rto+Ati?o'to)dri A t — o J a l ( r o ' t o ) (2.11) lim At -*-o J a2(ro^o) (2.12) R lim At-*0 1 At R ( z 1 - z o ) f ( r 1 , t o + A t lim At W C ^ - V ^ l ' V ^ o ' V ^ l = ( 2 ' 1 4 ) 0 J R lim At-^0 2 f e J^yi-yo^^^i^o^^o^o^1*! = b 2(r o,t Q) (2.15) R 14 lim A t — 0 2 S T / , ( « 1 - . 0 ) 2 f ( p l f t 0 + A t | p o f t 0 ) d P 1 R b 3(r 0,t Q) ( 2 . 1 6 ) lim At*-0 1 At R > ( x 1 - X o ) ( y 1 - y o ) f ( r 1 , t o + A t | r o , t o ) d r 1 = ^ ( r ^ t j ( 2 . 1 7 ) lim A t ^ o 1 "St R ( x 1 - x o ) ( z 1 - Z o ) f ( r 1 , t 0 4 - A t | r o , t o ) d r 1 = C g ^ o ' V ( 2 . 1 8 ) lim A t — O lim A t — o l At 1 X m ZSt A t — o R R ( y 1 - y 0 ) ( z 1 - z o ) f ( r 1 , t o + A t | r 0 , t o ) d r 1 = « 3(r 0 >t 0) ( 2 . 1 9 ) ( 2 . 2 0 ) ^ g ^ l v V A t ) - f ( r 2 > t 2 | f Q > t o ) t I- t ) ( 2 . 2 1 ) then equation ( 2 . 1 0 ) becomes -£(ro,tJr ,t ) ^  i t/2'"2rV"o' = a 1 ( r o,t o ) - p o + a 2 ( r Q , t o ) ^ o + a 3 ( r Q , t o ) ^ Z o + + c,(r ,t ) ^  f v + c 0(r ,t ) § f \ + c,(r ,t ) ft f v , 1 ° ' 0 6 x 0<^o 2 0 0 6 W o 3 0 0 6*o6 zo ( 2 . 2 2 ) . 15 T h i s e q u a t i o n i s k n o w n a s a b a c k w a r d K o l m o g o r o v e q u a t i o n . I n S e c t i o n 2 .4 a p a r t i c u l a r M a r k o v p r o c e s s f o r w h i c h t h e b a c k w a r d K o l m o g o r o v e q u a t i o n i s v a l i d w i l l b e c o n s i d e r e d . B a c k w a r d K o l m o g o r o v e q u a t i o n ( 2 . 2 2 ) c a n b e w r i t t e n c o n v e n i e n t l y i n t e r m s o f a n o p e r a t o r L a s r , t • o ' o O o r , t _ ( 2 . 2 3 ) o 7 o w h e r e = a n ( r , t ) - £ - + a , ( r , t • ) • $ - + a , ( r . t ) r , t 1 0 ° £ > x 0 2 0 0 5 0 0 e ^ o o ' o o O y o o T h e s u b s c r i p t s r Q a n d t a r e u s e d t o i n d i c a t e t h a t t h e o p e r a t o r i s a f u n c t i o n o f ? a n d t a n d t h a t d i f f e r e n t i a l o p e r a t i o n s o o a r e w i t h r e s p e c t t o c o m p o n e n t s x 0 > y o a n d Z q o f t h e i n i t i a l p o s i t i o n v e c t o r r . T h e v e c t o r r ^ a n d t i m e t g a r e p a r a m e t e r s i n t h e p a r t i a l d i f f e r e n t i a l e q u a t i o n . T o c l a r i f y t h e n o t a t i o n , e q u a t i o n ( 2 . 2 3 ) i n o n e d i m e n s i o n i s 1 6 _ _ k f _ U 2 , t 2 | x o , t o ) = ( x , ) ^ ( x 2 , t 2 | x o , t o ) O 6 o ± 0 0 Q x Q + b 1 ( x , t ) - ^ f U 2 ' t 2 | X o ' t o ) ( 2 . 2 5 ) O r ) x o B y a p r o c e d u r e s i m i l a r t o t h a t c a r r i e d o u t a b o v e , t h e C h a p m a n - K o l m o g o r o v e q u a t i o n ( 2 . 2 ) f o r £ ^ b » t-^J r Q , t Q ) c a n b e c o n v e r t e d t o a b a c k w a r d K o l m o g o r o v e q u a t i o n . I n t h i s c a s e V b r 1 , t Q + A t ) i s e x p a n d e d i n a T a y l o r s e r i e s a b o u t r Q . U s i n g t h e p r e v i o u s l y d e f i n e d l i m i t s ( 2 . 1 1 ) t o ( 2 . 2 1 ) a n d t h e o p e r a t o r n o t a t i o n , i t f o l l o w s t h a t ^ b ' S l V V = L _ g ( 5 b , t b | r 0 , t o ) ( 2 . 2 6 ) o ' o T h e p a r t i a l d i f f e r e n t i a l e q u a t i o n s t h a t h a v e b e e n d e r i v e d w i l l b e u s e d ' i n C h a p t e r 3 t o d e r i v e M o n t e C a r l o m e t h o d s f o r s o l v i n g b o u n d a r y - v a l u e p r o b l e m s t h a t a r e g o v e r n e d b y e q u a t i o n s o f a f o r m s i m i l a r t o ( 2 . 2 f c ) . H o w e v e r , b e f o r e p r o c e e d i n g : t o C h a p t e r 3 , a M a r k o v p r o c e s s t h a t g i v e s r i s e t o l i m i t s ( 2 . 1 1 ) t o ( 2 . 2 1 ) a n d a m e t h o d f o r g e n e r a l i z i n g t h e K o l m o g o r o v e q u a t i o n s w i l l b e c o n s i d e r e d . 17 2.4 A Continuous Markov Process f o r which Backward Kolmogorov  Equations are V a l i d In the Monte Carlo methods to be outlined, the coef-f i c i e n t s i n the Kolmogorov equations coincide with the coef.-f i c i e n t s i n the p a r t i a l d i f f e r e n t i a l equations f o r which the methods are applicable. It i s therefore necessary to consider, a Markov process f o r which the assumed l i m i t s (2.11) to (2.21) i are v a l i d . A mathematical model of such a process i s defined by the following set of stochastic d i f f e r e n t i a l equations*. | | + A1(x.,y.,z,t) = B 1(x,y,z,t)N 1(t) (2.27) |2 + A 2(x-,y,z,t) = B 2(x,y,z,t)N 2(t) (2.28) f | + A 3(x,y,z,t) = B 3(x,y,z,t)N 3(t) (2.29) These equations can be written i n matrix form as | | + A(r,t) = B(?,t)N(t) (2.30) The dependent variables x, y and z i n t h i s model are the components of the random vector r, for which density func-r tions f and g have been defined. The c o e f f i c i e n t s A. and'B. 1 i are, i n general, slowly varying continuous functions of x, y, z and t. The driving terms N^(t) are uncorrelated with each other, and each term i s stationary Gaussian white noise with 1 8 zero average. These properties of N^Ct) are expressed i n the following manner: N ^ * ) / = 0 ( 2 . 3 D < ^ i ( t 1 ) N i ( t 2 ^ > = 2D. § ( t r t 2 ) (2.32) ^ i ( t ) N j ( t y > = 0 (2.33) / N i ( t 1 ) N . ( t 2 ) . . . K ± ^ 2 m + 1 ) \ = 0 (2.34) . 1 ( t 1 ) N 1 ( t 2 ) . . . N . ( t 2 m ) ^ ( 2 . 3 5 ) N i ( t . ) N . ( t . ) > ( ^ ( t ^ ^ t , ) ) , a l l pairs In these equations the brackets <^ ^ s i g n i f y an ensemble average. S ( t ) i s tb.e unit impulse function, and 2D^ i s the power spectral density of N ^ t ) . Equations (2.34) and (2.35), or similar equations, are required i n order to show that the l i m i t s of the higher-order moments (2.20) are actually zero. The properties that have been assumed for the model imply that each N^(t) has a Gaussian distributed a m p l i t u d e I n equation (2.35),the sum i s to be taken over the ' possible ways 2 m! that 2m points can be divided into m pairs. To show that the process defined by equation (2.30) 19 i s a c t u a l l y a M a r k o v p r o c e s s , i t i s s u f f i c i e n t t o s h o w t h a t , g i v e n r ( t Q ) = r Q , t h e s t a t i s t i c s o f r f t ^ ) a r e i n n o w a y a f f e c t e d b y t h e a d d i t i o n a l i n f o r m a t i o n : t h a t r ( t _ ^ ) = r_-^ w h e r e t ^ < t Q < t ^ . F r o m e q u a t i o n ( 2 . 3 0 ) , * l r r ( t x ) = rn + j | B ( r , t ) N ( t ) - A ( r , t ) t d t ( 2 . 3 6 ) S i n c e r ( t Q ) = r Q i s f i x e d , t h e s t a t i s t i c s o f r ( t ^ ) d e p e n d o n l y u p o n t h e s t a t i s t i c s o f t h e d r i v i n g v e c t o r R ( t ) i n t h e i n t e r v a l ( t Q , t ^ ) . I f t h e a d d i t i o n a l i n f o r m a t i o n r ( t _ ^ ) = r_-^ i s a l s o g i y e n , t h e n * o B ( f , t ) N ( t ) - A ( r , t ) d t = r Q - T_± ( 2 . 3 7 ) T h i s c o n d i t i o n o n t h e i n t e g r a l p r o v i d e s i n f o r m a t i o n a b o u t N ( t ) i n t h e i n t e r v a l ( t _ 1 , t Q ) , b u t d o e s n o t g i v e a n y i n f o r m a t i o n a b o u t N ( t ) i n ( t Q , t ^ ) , s i n c e b y e q u a t i o n ( 2 . 3 2 ) , N ( . t ) i n t h e t w o i n t e r v a l s i s u n c o r r e l a t e d . T h e • s t a t i s t i c s o f r ( t - ^ ) t h e r e f o r e d o n o t d e p e n d u p o n t h e a d d i t i o n a l i n f o r m a t i o n r ( t _ ^ ) = r _ ^ . H e n c e , r ( t ) i s i n d e e d a M a r k o v p r o c e s s . T h e l i m i t s ( 2 . 1 1 ) t o ( 2 . 2 0 ) o f t h e M a r k o v p r o c e s s g i v e n b y e q u a t i o n s ( 2 . 2 7 ) t o ( 2 . 2 9 ) a r e c a l c u l a t e d b y i n t e g r a t -i n g t h e e q u a t i o n s b e t w e e n t = t a n d t = t + A t a n d t h e n ' 20 t a k i n g t h e r e q u i r e d e n s e m b l e a v e r a g e s a n d l i m i t s . C o n s i d e r e q u a t i o n ( 2 . 2 7 ) w i t h t h e c o e f f i c i e n t s w r i t t e n i n v e c t o r n o t a t i o n , I n t e g r a t i o n g i v e s t +At o VA t ( X l - x o ) = - A 1 ( r , t ) d t + J J 3 1 ( . r , t ) N 1 ( t ) d t ( 2 . 3 8 ) U n d e r th fe c o n d i t i o n t h a t A ^ ( r , t ) a n d B - ^ ( r , t ) v a r y a t a m u c h s l o w e r r a t e t h a n N ^ ( t ) , t h i s e q u a t i o n c a n b e w r i t t e n V A t ( X l-x o) = - A 1 ( r Q , t o ) A t + B 1 ( r Q , t o ) N ^ t j d t + o(At) w h e r e l i m A t — 0 o(At) _ o ( 2 . 3 9 ) ( 2 . 4 0 ) t h T h e e n s e m b l e a v e r a g e o f t h e n p o w e r o f ( X - ^ - X q ) i s e x p r e s s e d b y t h e B i n o m i a l ! T h e o r e m a s n < ( * l - o ^ V A t k . ' ( n - k ) J - A l ( ? o ' t o ) A t n - k k k = 0 ^ N 1 ( t 1 ) N 1 ( t 2 ) . . ^ ( t ^ ) ^ - d t ^ t g . . . . d t k + o ( A t ) ( 2 . 4 1 ) w h e r e , f o r k = 0 , t h e m u l t i p l e i n t e g r a l i s u n i t y . P r o m c o n d i t i o n s ( 2 . 3 2 ) , ( 2 . 3 4 ) a n d ( 2 . 3 5 ) , 21 . N 1 ( t 1 ) N 1 ( t 2 ) . . . R 1 ( t k ) J > d ^ d t g f o r k o d d , d t k • = 0 ( 2 . 4 2 ) I k k k i , ^ ^2, A 2 2 ( | ) J ( 2 D 1 ) ^ ( A t ) ' f o r ! k e v e n ( 2 . 4 3 ) H e n c e , A 1 ( r o , t Q ) A t + o ( A t ) f o r n = 1 ( 2 . 4 4 ) = 2 D x A t + o ( A t ) f o r n = 2 ( 2 . 4 5 ) = o ( A t ) f o r n _> 3 ( 2 . 4 6 ) T h e l i m i t s a ^ ( r Q , t o ) , b ^ ( r o , t Q ) a n d a h i g h e r - o r d e r l i m i t a r e o b t a i n e d d i r e c t l y f r o m t h e s e e x p r e s s i o n s b y d i v i d i n g b y A t a n d t a k i n g t h e l i m i t . B y a s i m i l a r p r o c e d u r e , i t f o l l o w s t h a t a l l t h e l i m i t i n g c o n d i t i o n s t h a t w e r e a s s u m e d i n S e c t i o n 2 . 3 a r e v a l i d f o r t h e M a r k o v p r o c e s s d e f i n e d b y e q u a t i o n s ( 2 . 2 7 ) t o ( 2 . 2 9 ) . F o r c o m p l e t e n e s s , a l l r e l a t i o n s h i p s b e t w e e n t h e l i m i t s , o r c o e f f i c i e n t s i n t h e K o l m o g o r o v e q u a t i o n s , a n d t h e c o e f f i c i e n t s i n t h e s t o c h a s t i c d i f f e r e n t i a l e q u a t i o n s ( 2 . 2 7 ) t o ( 2 . 2 9 ) a r e 2 2 l i s t e d b e l o w : a i (vV ( 2 . 4 7 ) ( 2 . 4 8 ) a 5 ( r o , t Q ) = V ? o ' V = ~ A 3 ( V V -I 2 B 3 ( V V 2 ( 2 . 4 9 ) ( 2 . 5 0 ) ( 2 . 5 D ( 2 . 5 2 ) = = C 3 ( ? o ' V = ° ( 2 - 5 5 ) T h e f a c t t h a t c o e f f i c i e n t s c . ( r , t ) a r e z e r o i s a 1 0 0 c o n s e q u e n c e o f t h e a s s u m p t i o n t h a t t h e n o i s e t e r m s N V ( t ) a r e n o t c o r r e l a t e d w i t h e a c h o t h e r . T h i s a s s u m p t i o n i s n o t n e c e s s a r y i n t h e o r y , b u t i n p r a c t i c e i t w o u l d b e e x t r e m e l y d i f f i c u l t t o r e a l i z e n o i s e s o u r c e s w i t h s p e c i f i e d c r o s s c o r r e l a t i o n a s w e l l a s a u t o c o r r e l a t i o n . A M a r k o v p r o c e s s g i v i n g r i s e t o c o n d i t i o n a l p r o b a b i l i t y d e n s i t y f u n c t i o n s f a n d g t h a t s a t i s f y K o l m o g o r o v p a r t i a l d i f f e r -e n t i a l e q u a t i o n s ( 2 . 2 3 ) a n d ( 2 . 2 6 ) h a s b e e n d i s c u s s e d . I n t h e f o l l o w i n g s e c t i o n , a u x i l i a r y p r o b a b i l i t y d e n s i t y f u n c t i o n s t h a t s a t i s f y m o r e g e n e r a l p a r t i a l d i f f e r e n t i a l e q u a t i o n s t h a n t h e K o l m o g o r o v e q u a t i o n s w i l l b e s t u d i e d . 23 2.5 P a r t i a l D i f f e r e n t i a l E q u a t i o n s S a t i s f i e d b y A u x i l i a r y d e r i v e d a r e t h e b a s i s o f M o n t e C a r l o m e t h o d s f o r s o l v i n g p a r t i a l d i f f e r e n t i a l e q u a t i o n s . T h e K o l m o g o r o v e q u a t i o n s , h o w e v e r , o n l y c o n t a i n t e r m s i n t h e d e r i v a t i v e s o f t h e d e n s i t y f u n c t i o n s f a n d g ^ w h i c h m e a n s t h a t o n l y p r o b l e m s y i e l d i n g p a r t i a l d i f f e r e n t i a l e q u a t i o n s o f t h i s f o r m c a n b e t r e a t e d . A n e x t e n d e d f o r m o f t h e K o l m o g o r o v e q u a t i o n s c o n t a i n i n g t h e d e p e n d -e n t v a r i a b l e i t s e l f c a n b e o b t a i n e d b y c o n s i d e r i n g a u x i l i a r y 12 d e n s i t y f u n c t i o n s u a n d v d e f i n e d b e l o w . T h e s e a u x i l i a r y f u n c t i o n s a r e o b t a i n e d f r o m t h e s a m e M a r k o v p r o c e s s a s c o n s i d e r e d i n t h e p r e v i o u s s e c t i o n b y w e i g h t i n g t h e p r o b a b i l i t y d e n s i t y f u n c t i o n s f a n d g . W i t h t h i s e x t e n s i o n , p a r t i a l d i f f e r e n t i a l e q u a -t i o n s c o n t a i n i n g a t e r m : i n t h e - d e p e n d e n t v a r i a b l e i t s e l f c a n b e s o l v e d . P r o b a b i l i t y D e n s i t y F u n c t i o n s T h e s e c o n d - o r d e r K o l m o g o r o v e q u a t i o n s t h a t h a v e b e e n T h e a u x i l i a r y p r o b a b i l i t y d e n s i t y f u n c t i o n s u a n d v a r e d e f i n e d a s f o l l o w s : u ( r 2 , t 2 r o , t Q ) = / e x p - m ( t 2 , t Q ) ^ 2 ^ 2 V V (2.54) ; ( r , , t , r , t ) ' - b ' b o ' o (2.55) 2 4 T h e t e r m m ( t , t Q ) i s g i v e n b y t h e f u n c t i o n a l m ( t 2 , t Q ) = / d [ r ( t ) , t ] d t ( 2 . 5 6 ) w h e r e d [ r ( t ) , t ] i s a c o n t i n u o u s p o s i t i v e f u n c t i o n o f t h e r a n d o m v e c t o r r ( t ) a n d t i m e t . T h e b r a c k e t s r ( t 2 ) = r 2 r ( t Q ) = r d e n o t e a c o n d i t i o n a l e x p e c t a t i o n ; t h a t i s , t h e e x p e c t e d v a l u e o f t h e f u n c -t i o n w i t h i n t h e b r a c k e t s s u b j e c t t o t h e c o n d i t i o n s t h a t r ( t ) = r a n d r ( t 2 ) i s i n a s m a l l r e g i o n d r 2 a b o u t v^-I n a m a n n e r s i m i l a r t o t h a t g i v e n b y D a r l i n g a n d 1 2 _ _ S i e g e r t , i t w i l l b e s h o w n t h a t u ( r 2 , t 2 r Q , t Q ) a n d v ( r ^ , t ^ r-o'^r) s a t i s f y t h e f o l l o w i n g p a r t i a l d i f f e r e n t i a l e q u a t i o n s : ^2'*2 I V V = L_ u ( r 2 , t 2 | r Q , t o ) - d(r Q,t )u(r 2,t g r ^ t j ' 0 T o ' l o ( 2 . 5 7 ) V V = L . _ . v ( r b , t b r o , t Q ) - d ( r o , t o ) v ( r b , t J r o , t o ) o ' o ( 2 . 5 8 ) 25 P r o m t h e i d e n t i t y e x p - m ( t 2 , t ) = 1 - - ^ r ^ e x p - m ( t 2 , t 1 ) d t 1 ( 2 . 5 9 ) a n d t h e r e l a t i o n ^ m ( t 2 , t 1 ) = - d [ r ( t 1 ) , t 1 ] ( 2 . 6 0 ) i t f o l l o w s t h a t e x p - m ( t 2 , t o ) = 1 - d [ r ( t 1 ) . , t 1 ] e x p - m ( t 2 , t 1 ) d t 1 (2 . 6 1 ) T a k i n g t h e c o n d i t i o n a l e x p e c t a t i o n o f b o t h s i d e s o f t h i s e q u a t i o n , m u l t i p l y i n g b y f ( ? 2 , t 2 r Q , t ) a n d a p p l y i n g d e f i n i t i o n ( 2 . 5 4 ) , g i v e s u ( r 2 , t 2 r , t ) -o ' o ^ y ^ < ^ [ r ( t 1 ) , t 1 ] e x p - m ( t 2 , t 1 ) r ( t 2 ) = r 2 r ( t ) = r d t - j f ( r 2 , t 2 r , t ) o ' o ( 2 . 6 2 ) ! . 26 The conditional expectation, i f r ( t ^ ) is,considered fixed at r-^, can be written d [ r ( t 1 ) , t 1 ] e x p -m(t 2,t 1) r ( t 2 ) = r 2 r(t 0)=f. d(r 1,t- L)exp -m(t 2,t 1) r(t 2.)=r N 2 N r ( t 1 ) = r 1 \ p ( r 1 , t 1 r o , t Q ; r 2 , t 2 ) d r 1 ^ 0 ^ 0 / (2.63) where p ( ? 1 » ' t 1 r Q , t Q ; r 2 , t 2 ) d r 1 i s the probability that the random variable r i s i n the region dr-^ at t-^ i f i t i s given that r i s at r Q and i n the region d r 2 at times t Q and t 2 respec-t i v e l y . For a Markov process P ( r 1 » t 1 r„,tj f ( ? 2 , t 2 0 ' 1 O ' r 1 , t 1 ) t (2.64) Now, since r-^, within the conditional expectation,is fixed, d ( ? 1 , t 1 ) i n the second member of equation ' {2£ft) c a n t e taken outside the conditional expectation. Also, f o r r ( t ) a Markov process, r ( t 2 ) i s independent of ? ( t Q ) when r(t^) = i s given and t 2 > "> t . The condition r ( t Q ) = r Q can therefore be deleted from the conditional expectation. 27 T h e r e f o r e , r ( t 2 ) = r 2 r ( t Q ) = r R r ( t 2 ) = r 2 r ( t 1 ) = r 1 f ( r 1 > t 1 | r Q , t o ) f ( r 2 , t 2 I r 1 , t 1 ) d r 1 f ( ? 2 ' t 2 ? o ' t o ) ( 2 . 6 5 ) S u b s t i t u t i n g e q u a t i o n ( 2 . 6 5 ) b a c k i n t o e q u a t i o n ( 2 . 6 2 ) , a n d u s i n g t h e d e f i n i t i o n o f u ( ? 2 , t 2 g i v e s u ( r 2 , t 2 | r o , t Q ) = f ( r 2 , t 2 r 0 , t Q ) -Jyd(r1,t1)u(r2,t2 r 1 , t 1 ) f ( r 1 , t 1 j r Q , t 0 ) d r 1 d t 1 ( 2 . 6 6 ) * o R I f t h e o r d e r o f i n t e g r a t i o n i s r e v e r s e d a n d b o t h s i d e s o f t h e e q u a t i o n a r e o p e r a t e d u p o n w i t h t h e o p e r a t o r L + - ^ - r , w h e r e f r o m ( 2 . 2 3 ) o ' o 28 r ,t ) = 0 o' o the following equation i s obtained; + "TT 1 u ( r 2 , t 2 r ^ , t j = 0 O ' y d ( r l f t 0 ) u ( r 2 f t 2 | r l f t Q ) f ( r 1 , t Q j r ^ t ^ d ^ R Prom equation (2.3), however, (2,67) lim f ( r 1 , t 1 | r o|,t o) = S ( ? 1 - r ) Therefore, L u ( ? 0 , t 0 . r o , t J st o 2'u2 - V V = L u ( r 2 , t 2 r o , t Q ) - d ( r Q , t Q ) u ( r 2 , t 2 (2.57) as was to be shown. By a si m i l a r analysis,with p ( ? 1 , t 1 ^o'"*;o'^2'^2^ replaced by q ( ? 1 , t 1 I r ^ t ^ r ^ t ^ ) , where q ( r 1 , t 1 | , r o , t o ; r b , t b ) g ( r b , t b r o , t Q ) f ( r 1 , t 1 r o , t o ) g ( r b , t b r^t-J (2.68) 2 9 i t f o l l o w s t h a t > r , v > t r t ) s a t i s f i e s e q u a t i o n ( 2 . 5 8 ) . O' o I t i s i m p o r t a n t t o n o t e t h a t t h e a u x i l i a r y d e n s i t y f u n c t i o n s u a n d v s a t i s f y t h e same 1 i n i t i a l a n d b o u n d a r y c o n d i t i o n s ( 2 . 3 ) t o (2.6) a s f a n d g r e s p e c t i v e l y . T h i s f o l l o w s f r o m d e f i n i t i o n s ( 2 . 5 4 ) a n d ( 2 . 5 5 ) . T h e f o r m o f t h e i n i t i a l a n d b o u n d a r y c o n d i t i o n ' s f o r t h e p a r t i a l d i f f e r e n t i a l e q u a t i o n s d e v e l o p e d i n t h i s c h a p t e r s u g g e s t s t h a t t h e d e n s i t y f u n c t i o n s f , g , u a n d v c a n b e r e g a r d e d a s f u n d a m e n t a l s o l u t i o n s o r G r e e n ' s f u n c t i o n s f o r b o u n d a r y -v a l u e p r o b l e m s . T h i s p r o p e r t y w i l l b e s t u d i e d i n t h e f o l l o w i n g c h a p t e r . 30 3. MONTE C A R L O METHODS FOR T H E S O L U T I O N S OF B O U N D A R Y - V A L U E P R O B L E M S 3.1 I n t r o d u c t i o n I n t h i s c h a p t e r r e l a t i o n s h i p s b e t w e e n p r o b a b i l i t y -d e n s i t y f u n c t i o n s f , g , u a n d v a n d s o l u t i o n s 0 o f b o u n d a r y -v a l u e p r o b l e m s w i l l b e d e v e l o p e d . T h e m e t h o d s t o b e d e s c r i b e d c a n b e a p p l i e d t o p r o b l e m s g o v e r n e d b y p a r t i a l d i f f e r e n t i a l e q u a t i o n s o f t h e s a m e f o r m a s t h o s e f o r f , g , u a n d v i n w h i c h 0 i t s e l f i s g i v e n i n i t i a l l y a n d o n a l l b o u n d a r i e s . I n a l l p r o b l e m s t o b e c o n s i d e r e d , t h e s o l u t i o n a t a p o i n t i s o b t a i n e d a s t h e e x p e c t e d v a l u e o f i n i t i a l a n d b o u n d a r y v a l u e s a t t h e t e r m i n a l p o i n t s o f r a n d o m w a l k s o r i g i n a t i n g a t t h e p o i n t f o r w h i c h t h e s o l u t i o n i s d e s i r e d . T h e e x p e c t e d v a l u e i s w r i t t e n i n t e r m s o f t h e p r o b a b i l i t y d e n s i t y f u n c t i o n s f a n d g , o r u a n d v . A n a p p r o x i m a t i o n t o t h e e x p e c t e d v a l u e i s d e t e r m i n e d e x p e r i m e n t a l l y f r o m a l a r g e n u m b e r o f r a n d o m w a l k s s i m u l a t e d o n a n a n a l o g c o m p u t e r . T h e a p p r o x i m a t i o n c o n v e r g e s i n a s t a t i s t i c a l s e n s e t o t h e t r u e s o l u t i o n a s t h e n u m b e r o f r a n d o m w a l k s i n c r e a s e s . T h e f o r m o f t h e p a r t i a l d i f f e r e n t i a l e q u a t i o n s i n P r o b l e m s A a n d B i s n o t s t a n d a r d i n t h a t a m i n u s s i g n p r e c e e d s t h e t i m e d e r i v a t i v e s . T h i s f o r m i s c o n v e n i e n t f o r t h e a n a l y s i s , a n d i n n o w a y r e s t r i c t s t h e m e t h o d s s i n c e t h e e q u a t i o n s o f a n a c t u a l p r o b l e m c a n a l w a y s b e t r a n s f o r m e d t o t h e r e q u i r e d f o r m b y d e f i n i n g a n e w t i m e v a r i a b l e . M e t h o d s f o r s o l v i n g t h e v a r i o u s c l a s s e s o f p r o b l e m s w i l l n o w "be o u t l i n e d . 3 1 3 . 2 S o l u t i o n s o f B o u n d a r y - V a l u e P r o b l e m s f o r P a r a b o l i c P a r t i a l D i f f e r e n t i a l E q u a t i o n s T h e s t a t e m e n t o f t h e p r o b l e m t o b e c o n s i d e r e d i n t h i s s e c t i o n i s a s f o l l o w s . P r o b l e m . A D e t e r m i n e 0 ( r , t ) s u c h t h a t : o o 0 7 o i s s a t i s f i e d w i t h i n a b o u n d e d r e g i o n R*, ( 2 ) a p i e c e w i s e c o n t i n u o u s i n i t i a l c o n d i t i o n ' 0 o ( r Q ) i s s a t i s f i e d w i t h i n R;. i . e . , 0 ( r Q , 0 ) = 0 Q ( r o ) ; ( 3 . 2 ) ( 3 ) a p i e c e w i s e c o n t i n u o u s b o u n d a r y c o n d i t i o n 0 c ( r b , t Q ) i s s a t i s f i e d o n t h e b o u n d a r y C o f R; i . e . , W ^ o W ' ( 3 ' 3 ) T h e b o u n d a r i e s a n d i n i t i a l a n d b o u n d a r y c o n d i t i o n s o f a t y p i c a l p r o b l e m w i t h o n e s p a c e v a r i a b l e a r e s h o w n i n F i g u r e 3 - 1 . T h e t i m e v a r i a b l e t t h a t i s s h o w n i n t h e f i g u r e i s s u c h t h a t 0 ( r , t ) i s d e f i n e d f o r t < 0 . o 7 o o T o d e t e r m i n e t h e s o l u t i o n 0 o f P r o b l e m A a t a p o i n t ( r , t ) , r a n d o m w a l k s a r e s t a r t e d a t p o i n t ( r , t ) . E a c h w a l k 0 0 0 0 i s t e r m i n a t e d a s s o o n a s a b o u n d a r y i s r e a c h e d o r a t t = 0 . I f a w a l k t e r m i n a t e s o n a - b o u n d a r y a t ( r ^ t ^ ) t h e b o u n d a r y v a l u e 0 c ( r b , t ^ ) i s r e c o r d e d , w h e r e a s i f a w a l k i s t e r m i n a t e d a t t = 0 w i t h p o s i t i o n r ^ , t h e i n i t i a l v a l u e 0 q ( r ^ ) i s r e c o r d e d . I t F i g u r e 5-1. R a n d o m W a l k s a n d I n i t i a l a n d B o u n d a r y C o n d i t i o n s o f a T y p i c a l P r o b l e m w i t h 1 S p a c e V a r i a b l e . 33 T h e e x p e c t e d v a l u e o f t h e i n i t i a l a n d b o u n d a r y v a l u e s c a n b e w r i t t e n i n t e r m s o f t h e p r o b a b i l i t y d e n s i t y f u n c t i o n s f ( r 2 , 0 r 0 , t Q ) a n d g ( r b , t b r 0 , t 0 ) a s 0 ( r Q , t o ) = ^ o ( 5 2 ) f ( r 2 , 0 | r 0 , t o ) d r . R 0 (3 .4) w h e r e i t h a s b e e n a s s u m e d t h a t t h e e x p e c t e d v a l u e i s t h e s o l u -t i o n . I t m u s t b e p r o v e n t h a t 0 ( r o , t Q ) a s g i v e n b y e q u a t i o n (3 .4) i s a c t u a l l y a s o l u t i o n o f P r o b l e m A . T o p r o v e t h a t 0 ( r o > t o ) s a t i s f i e s t h e p a r t i a l d i f f e r -e n t i a l e q u a t i o n o f P r o b l e m A , o p e r a t e o n e q u a t i o n (3 .4) w i t h t h e o p e r a t o r h + L_ . S i n c e t h e o p e r a t o r i s w i t h r e s p e c t t o ^ o ? a n d t , t h e r e s u l t i s o o 3 4 , + L \ 0 ( r , t ) * o r . t 1 0 0 o ' o R 0 + 0 J * V , t J / ^ r + L_ ^ ( r b , t b | r o , t o ) d r . b d t b ( 3 . 5 ) T h e r i g h t s i d e o f e q u a t i o n ( 3 . 5 ) i s z e r o b y K o l m o g o r o v e q u a t i o n s ( 2 . 2 3 ) a n d ( 2 . 2 6 ) a n d i n i t i a l c o n d i t i o n ( 2 . 4 ) . T h e r e f o r e , _ 4 | ( r 0 , t Q ) = L 0 ( r Q , t o ) ( 3 > 1 ) . 0 * 0 r o ' o T o p r o v e t h a t 0 ( r o , t Q ) a s d e f i n e d b y e q u a t i o n ( 3 . 4 ) a l s o s a t i s f i e s t h e i n i t i a l a n d b o u n d a r y c o n d i t o n s o f P r o b l e m A , c o n s i d e r 35 lim 0(r o,t o) = A ^ r 2 ) lim f ( ? 2 , 0 r 0 , t Q ) d r t * 0 R 0 + 0 c ( r v V l i m g ( r b ' t b t 0 - * o r ,t )dr,dt, ( 3 . 6 ) o' o b b By equations ( 2 . 3 ) and ( 2 . 4 ) , equation ( 3 . 6 ) becomes lim 0(r o,t Q) = t ^ O y 0 o ( ? 2 ) S ( r 2 - r Q ) d r 2 = 0 o(r Q) . ( 3 .7 ) R Therefore, 0(r ,0') = 0Q(^O) ( 3 . 2 ) Also, lim 0(r Q,t o) = /0O(?2) lim ' f ( r 2 > 0 V * o ) d r 2 r o ^ r b o b R 0 + r ,t )dr, dt, o' o b b ( 3 . 8 ) o b *o 0 36 By equations ( 2 . 5 ) and ( 2 . 6 ) , t h i s equation becomes lim 0(r Q,t o) = f / 0 c ( r v t b ) 8 ( r ^ ) § ( V V ^ l r — * r . Therefore, ^ b ' V = • Since a l l conditions of Problem A are s a t i s f i e d , 0(r ,t ) o o as defined by equation (3*4) i s a solution of the problem. The Monte Carlo solution of Problem A i s obtained by approximating the expected value 0(? >t ) given by equation (3.4) with the average 0-^(r Q» 0) of the i n i t i a l and boundary values 0^ that are recorded from a set of N random walks origina-t i n g at ( r 0 , t Q ) . This average i s N i = l The convergence of 0^(?q>"tQ) "to 0 ( r Q , t Q ) i s considered i n Section 3 • 5 • P r o b l e m B D e t e r m i n e 0 ( r o , t Q ) s u c h t h a t : ( 1 ) \ _ 4f v v = l- + ^ vv - ^o-v^vv 6*0 V 1 ^ ( 3 . 1 1 ) i s s a t i s f i e d w i t h i n a b o u n d e d r e g i o n R*, ( 2 ) . a p i e c e w i s e c o n t i n u o u s i n i t i a l c o n d i t i o n i s s a t i s -f i e d w i t h i n R; i . e . , 0 ( r Q , O ) = 0 o ( r Q ) ; ( 3 . 1 2 ) ( 3 ) a p i e c e w i s e c o n t i n u o u s b o u n d a r y c o n d i t i o n 0 ( r , , t ) i s s a t i s f i e d o n t h e b o u n d a r y C o f R; i . e . , 0 ( r v t Q ) = 0 c ( ? v t o ) « ( 3 . 1 3 ) T h e s t a t e m e n t o f t h i s p r o b l e m i s t h e s a m e a s t h a t f o r P r o b l e m A e x c e p t t h a t 0 s a t i s f i e s t h e s a m e p a r t i a l d i f f e r e n t i a l e q u a t i o n a s t h e a u x i l i a r y d e n s i t y f u n c t i o n s u a n d v ( S e c t i o n 2 . 5 ) . T h e r e f o r e , b y a n a l o g y w i t h t h e p r e v i o u s p r o b l e m , t h e s o l u t i o n i s 0 ( V V = / 0 o ( r 2 ) u ( r 2 , O ? o , t o ) d r 2 R 0 + 38 P r o m d e f i n i t i o n s (2.54) a n d ( 2 . 5 5 ) , e q u a t i o n (3-14) b e c o m e s 0 0(r | , t Q ) = J0Q(r2) ^ e x p - J d [ r ( t ) , t ] d t R r ( 0 ) = r r ( t Q ) = r f ( ? 2 ' ° I V V * 1 " ; + / / 0 c ( v V < ^ e x p * o C d [ r ( t ) , t ] d t ? < V = ? b r ( t Q ) = r r , t ) d r , d t , o o ' b b (3.15) T h e e x p e c t e d v a l u e 0 ( r o , t Q ) g i v e n b y e q u a t i o n ( 3 . 1 5 ) c a n b e a p p r o x i m a t e d b y t h e a v e r a g e 0^(^of^Q) o f " the p r o d u c t 7/j_0j_ f ° r N w a l k s o r i g i n a t i n g a t ( ? 0 » " t Q ) w h e r e 0^ i s t h e i n i t i a l o r b o u n d a r y v a l u e a t t h e t e r m i n a l p o i n t o f t h e i * * 1 w a l k a n d "Y^ i s t h e v a l u e o f T y = e x p - / d [ r ( t ) , t ] d t t . (3.16) o 39 f o r t h e c o r r e s p o n d i n g w a l k . T h e u p p e r l i m i t o f i n t e g r a t i o n . . . T, i s 0 f o r w a l k s t e r m i n a t i n g a t t = 0 , a n d t ^ f o r w a l k s t e r -m i n a t i n g a t a b o u n d a r y . T h e M o n t e C a r l o s o l u t i o n i s t h e r e f o r e N i = l 3 . 3 S o l u t i o n s o f B o u n d a r y - V a l u e P r o b l e m s f o r E l l i p t i c P a r t i a l  D i f f e r e n t j i a l E q u a t i o n s T h e b o u n d a r y - v a l u e p r o b l e m s C , D a n d E t o b e d i s c u s s e d a r i s e i n t h e s t u d y o f s t e a d y - s t a t e f i e l d s . T y p i c a l p a r t i a l d i f f e r e n t i a l e q u a t i o n s f o r t h e s e p r o b l e m s a r e t h e L a p l a c e e q u a t i o n a n d t h e P o i s s o n e q u a t i o n . ' T h e s t a t e m e n t o f P r o b l e m C i s a s f o l l o w s . P r o b l e m C D e t e r m i n e 0 ( r ) s u c h t h a t : ( 1 ) L_ 0 ( r ) = 0. i s s a t i s f i e d w i t h i n a b o u n d e d P o ( 3 . 1 8 ) r e g i o n R J ( 2 ) a p i e c e w i s e c o n t i n u o u s b o u n d a r y c o n d i t i o n 0 c ( ? b ) i s s a t i s f i e d o n t h e b o u n d a r y C o f R „ i . e - . , . 0 ( r b ) = 0 c ( r b ) . . ( .3,19), T h e s u b s c r i p t t i s d e l e t e d f r o m o p e r a t o r L_ 0* 0 t o i n d i c a t e t h a t L _ i s ^ . i n d e p e n d e n t o f t i m e . , r _ 4 0 T h e s o l u t i o n o f t h i s p r o b l e m i s t h e s t e a d y - s t a t e s o l u t i o n o f a p r o b l e m o f t y p e A . S i n c e L a n d t h e b o u n d a r y c o n d i t i o n s a r e i n d e p e n d e n t o f t , t h e s o l u t i o n a t r Q i s t h e e x p e c t e d v a l u e o f b o u n d a r y v a l u e s a t t h e t e r m i n a l p o i n t s o f r a n d o m w a l k s o r i g i n a t i n g a t r Q a t t i m e t = 0 . T h e e x p e c t e d v a l u e i s w r i t t e n i n t e r m s o f p r o b a b i l i t y d e n s i t y f u n c t i o n g ( ? b , t b r Q , 0 ) a s oo 0 ( ? o ) = J ^ 0 c ( r b ) g ( r b , t b | r o , 0 ) d r b d t ( 3 . 2 0 ) 0 C P r o m e q u a t i o n ( 2 . 2 6 ) a n d b o u n d a r y c o n d i t i o n ( 2 . 6 ) f o r g , i t f o l l o w s t h a t 0 ( r ) a s g i v e n b y e q u a t i o n ( 3 . 2 0 ) i s i n d e e d a s o l u t i o n o f P r o b l e m C . E q u a t i o n ( 3 . 2 0 ) c a n a l s o b e w r i t t e n a s 0 ( ? o } = j f 0 c < 5 b ) G < 5 b l ? o ) d r b ( 3 . 2 1 ) C w h e r e o o g ( ? b , t b r r t > 0 ) d t b 3 . 2 2 ) 0 4 1 i i s t h e p r o b a b i l i t y d e n s i t y t h a t a r a n d o m w a l k s t a r t i n g a t r Q a t t i m e t Q = 0 w i l l e v e n t u a l l y t e r m i n a t e i n d r b o n t h e b o u n d a r y C . A s f o r p r e v i o u s p r o b l e m s , t h e e x p e c t e d v a l u e g i v e n b y e q u a -t i o n ( 3 . 2 0 ) o r ( 3 . 2 1 ) c a n b e a p p r o x i m a t e d b y t h e a v e r a g e 0 j j ( ? Q ) o f t h e t e r m i n a l b o u n d a r y v a l u e s 0^. T h a t i s , IT i = 1 i s t h e M o n t e C a r l o s o l u t i o n . P r o b l e m D D e t e r m i n e 0 ( r Q ) s u c h t h a t : ( 1 ) L_ 0 ( ? Q ) - d ( r Q ) 0 ( r o ) = 0 w i t h i n a ( 3 . 2 4 ) r o b o u n d e d r e g i o n R\ ( 2 ) a p i e c e w i s e c o n t i n u o u s b o u n d a r y c o n d i t i o n 0 c ( ? b ) i s s a t i s f i e d o n t h e b o u n d a r y C o f R; i . e . , 0 ( r b ) = 0 c ( r b ) . ( 3 - 2 5 ) O p e r a t o r L_ a n d c o e f f i c i e n t d ( r ) a r e i n d e p e n d e n t o f ? o t i m e t , b u t o t h e r w i s e a r e a s d e f i n e d b y ( 2 . 2 4 ) a n d ( 2 . 5 6 ) . T h e s o l u t i o n o f t h i s p r o b l e m i s t h e s t e a d y - s t a t e s o l u t i o n o f a p r o b l e m o f t y p e B . H e n c e , b y a n a l o g y w i t h P r o b l e m C , t h e s o l u t i o n i s 00 0 ( r Q ) = J T / 0 c ( ? b ) v ( r b , t b | r Q , 0 ) d r b d t b . ( 3 . 2 6 ) 0 b 4 2 F o r a l a r g e n u m b e r N o f r a n d o m w a l k s s t a r t i n g f r o m r Q a t t i m e t = 0 , t h e e x p e c t e d v a l u e 0 ( ? Q ) c a n b e a p p r o x i m a t e d b y N 0„(?o) =1 ) 7 A (5 . 2 7 ) i = l w h e r e y^ i s t h e v a l u e o f y - e x p - / d [ r ( t ) ] d t V f o r t h e i * * 1 w a l k a n d 0^ i s t h e b o u n d a r y v a l u e a t t h e t e r m i n a l p o i n t o f t h e i t h w a l k . 3 . 4 S o l u t i o n s o f N o n h o m o g e n e o u s B o u n d a r y - V a l u e P r o b l e m s T h e s o l u t i o n s o f n o n h o m o g e n e o u s b o u n d a r y - v a l u e p r o b l e m s c a n b e c o n s t r u c t e d f r o m t h e s o l u t i o n s o f a h o m o g e n e o u s t i m e -i n d e p e n d e n t b o u n d a r y - v a l u e p r o b l e m a n d a h o m o g e n e o u s t i m e -d e p e n d e n t b o u n d a r y - v a l u e p r o b l e m . P o i s s o n ' s e q u a t i o n i s a t y p i c a l e x a m p l e f o r p r o b l e m s o f t y p e E . T h e s t a t e m e n t o f P r o b l e m E i s a s f o l l o w s . P r o b l e m E D e t e r m i n e 0 ( r ) s u c h t h a t : ( 1 ) L 0 ( r ) = - H ( r ) i s s a t i s f i e d w i t h i n a r 0 0 ( 3 . 2 8 ) o b o u n d e d r e g i o n R, w h e r e H ( r ) i s a p i e c e w i s e c o n t i n u o u s f u n c t i o n * , . ( 2 ) a p i e c e w i s e c o n t i n u o u s b o u n d a r y c o n d i t i o n 0 ( r , ) C D 43 i s s a t i s f i e d on.the boundary C of R; i . e . , 0(r b) = 0 c(r b) . (3.29) To determine the solution of Problem E, consider the time-independent boundary-value problem of type C: (1) L_ 0 1(r ) = 0 within R, (3-30) r o (2) 0 x(r b) = 0c(?b) on the boundary C of R •. .(3.31) and the time-dependent boundary-value problem of type A: (!) _ 4- = L - w i t h i n R i ( 5 ' 3 2 ) O^o r o (2) 0 2(r Q,O) = H(r Q) (3.33) (3) 0 2 ( r b , t Q ) = 0 . (3.34) The solution of Problem E i s given by 0 0(r Q) = 0 ^ ) + J 0 2 ( r Q , t o ) d t o . (3.35) -OO Proof Operate on 0(r ) with L_ and use (3.30) and (3.32) . r o 0 L_ 0(r o) = - J ^ 0 2 ( V V d t o ( " 6 ) o - OO = 0 2(r Q,-oO) - 0 2(r Q,O) . (3.37) 44 S i n c e t h e b o u n d a r y - v a l u e s f o r 02 a r e 0 , 0 2 ( r Q , - o O ) = 0 . T h e r e f o r e , b y (3.33), L_ 0(r ) = - H(5 ). . (3 .28) r o P r o m (3.35), f o r r Q = r v 0 0(?b) = 0 1 ( r b ) + y 0 2 ( r b , t o ) d t o . (3.38) - oo T h e r e f o r e , b y c o n d i t i o n s (3-31) a n d (3.34), 0 ( r b ) = 0 c ( r b ) . (3.29) T h e s o l u t i o n 0(r ) g i v e n b y (3.35) s a t i s f i e s a l l c o n d i t i o n s o f P r o b l e m E , a n d i s t h e r e f o r e a s o l u t i o n . T h e M o n t e C a r l o s o l u t i o n o f P r o b l e m E i s o b t a i n e d b y d e t e r m i n i n g 0-j_(r ) a n d 02^o'^o^ t y " t h e m e ' t t l o d s o f P r o b l e m s A a n d C a n d t h e n i n t e g r a t i n g 0 2 ^ o ' ^ o ^ w i _ t : t l r e s p e c t t o t Q b y s o m e n u m e r i c a l t e c h n i q u e . N o n h o m o g e n e o u s e q u a t i o n s o f t h e f o r m L_ 0(?Q) - d ( r o ) 0 ( r Q ) = - H ( r o ) (3.39) r o a r e s o l v e d i n t h e s a m e m a n n e r a s P r o b l e m E b y c o n s i d e r i n g p r o b l e m s o f t y p e B a n d D. 4 5 3.5- E s t i m a t e s o f t h e N u m b e r o f R a n d o m W a l k s f o r M o n t e C a r l o  S o l u t i o n s 3.5A C o n v e r g e n c e o f M o n t e C a r l o S o l u t i o n s . M o n t e C a r l o s o l u t i o n s o f h o m o g e n e o u s p a r t i a l d i f f e r e n t i a l e q u a t i o n s a r e g i v e n b y N i = l 0, w h e r e f o r p r o b l e m s o f t y p e B a n d D, 0± i s r e p l a c e d b y 'Y±0±' L e t t h e r e c o r d e d v a l u e s 0^, f o r a g i v e n ( r o , t Q ) b e 1 d e n o t e d b y t h e r a n d o m v a r i a b l e 0. T h e v a r i a n c e o f 0 ^ ( r Q , t ^ ) , w h i c h i s a m e a s u r e o f t h e f l u c t u a t i o n s o f v a l u e s o f 0 j j ( ? o » t o ) o b t a i n e d o n d i f f e r e n t t r i a l s , i s g i v e n b y v a r 0 , T ( r , t ) = 1 v a r 0 ( 3 . 4 0 ) F r o m t h e C e n t r a l L i m i t T h e o r e m , 0]^(?o»'to) w i l l b e n e a r l y n o r m a l l y d i s t r i b u t e d f o r N l a r g e . I t t h e r e f o r e - f o l l o w s t h a t t h e p r o b a b i l i t y i s a p p r o x i m a t e l y . 0 5 t h a t > 21 v a r . 0 N • ( 3 . 4 1 ) H e n c e , t h e s t a t i s t i c a l c o n v e r g e n c e o f 0 ] \ j - ( r o >t o ) t o 0 ( r o , t n ) o 7 o ' i s a s ,7=W. T o r e d u c e t h e s t a n d a r d d e v i a t i o n , / v a r 0T,T(r , t ).' U N ^ V N v o ' o b y a f a c t o r o f 2 , f o r ^ e x a m p l e , i t I s n e c e s s a r y t o s i m u l a t e 4 N r a n d o m w a l k s . 4 6 3 * 5 B N u m b e r o f . R a n d o m W a l k s f o r . H o m o g e n e o u s P a r t i a l D i f f e r e n t i a l  E q u a t i o n s A n e s t i m a t e o f t h e n u m b e r N o f r a n d o m w a l k s t h a t a r e r e q u i r e d f o r a g i v e n t o l e r a b l e e r r o r c a n b e d e t e r m i n e d a s f o l l o w s . I f a n e r r o r 0 N ( r Q , t o ) - 0 ( r o y t Q ) g r e a t e r t h a n € , o c c u r r i n g w i t h p r o b a b i l i t y ; 0 5 ? i s t o l e r a b l e , t h e n f r o m i n e q u a l i t y ( 3 . 4 1 ) N > f Y a g A. ( 3 . 4 2 ) i s a s u f f i c i e n t n u m b e r o f r a n d o m w a l k s . E o r s o m e s p e c i a l c a s e s , v a r 0 c a n b e c a l c u l a t e d , , s o t h a t f o r t h e s e c a s e s c o n d i t i o n ( 3 . 4 2 ) g i v e s a l o w e r b o u n d f o r N . W h e n v a r 0 c a n n o t b e c a l c u l a t e d , a n • e s t i m a t e f d r W : c a n o b e o b t a i n e d ' b y " n o t i n g - t h a t v a r 0 < 0 ^ (3.43) w h e r e 0 i s t h e m a x i m u m v a l u e o f 0 0 A p e s s i m i s t i c e s t i m a t e m a x o f t h e r e q u i r e d n u m b e r o f r a n d o m w a l k s i s t h e r e f o r e 402 P o r e x a m p l e , i f t h e p a r t i a l d i f f e r e n t i a l e q u a t i o n i s s c a l e d s o t h a t 0 = 1 , t h e n f o r € = . 0 5 , N s h o u l d b e g r e a t e r t h a n 1 , 6 0 0 ? w h e r e a s i f € = . 0 1 , t h e n N s h o u l d b e g r e a t e r t h a n 4 0 , 0 0 0 , 47 3.5C Number of Random Walks for Nonhomogeneous P a r t i a l D i f f e r e n t i a l Equations. The solution of nonhomogeneous p a r t i a l d i f f e r e n t i a l equations of type E i s given by 0 ( r Q ) = 0 1 ( r Q ) + / 0 2 ( r o , t Q ) d t o .(3.35) -oo Por a Monte Carlo solution, 0 ^ ( r Q ) i s approximated by 0J_ - J J ( ^ O ' ) • and the in t e g r a l i s approximated by M . I = ) ^ ^ ( ^ . i A t J (3.45) i-1 where the Ct ^  depend upon the numerical integration that i s used. The subscript L indicates that each value of 0 o ( r ,t •) i s to ber r 2 O O obtained using L random walks. The selection of numbers N and L w i l l now be considered. Let the Monte Carlo approximation to 0 ( r o ) be denoted by 0 u j J ( r o ) > then M v a r 0NL ( ro } = v a r 0 I N ( r o } V a i v a r 0 2 L ( V i A t o } i = l (3.46) 48 I f v a r 0 ~ x ( r , j A t ) i s t h e m a x i m u m v a l u e o f v a r 0nr{v , i > A t ). 2 L o o ^ 2 L o ,oi 1 = 1 , . . . . M , a n d i f C t ^ a r e c h o s e n b y t h e t r a p e z o i d a l r u l e ; i . e . , A t a i = a M = ~ 2 a ' ' ^ . 4 7 ) a ± = A t o i = 2,3 . . . ( M - l ) t h e n v a r 0 N L ( ? Q ) < v a r 0 I N(? Q) + v a r 0 2 L ( r Q , j A t Q ) ( A t 0 ) 2 ' ( M - §) (3.48) L e t 0-^  a n d 0^ ^ e t h e r a n d o m v a r i a b l e s f r o m w h i c h 0 j j j ( r o ) a n d 0 2 j j ( r Q , j A t Q ) a r e f o r m e d ; t h e n v a r 0 T „ ( r ) - v a r 0 1 < . 0 c m a x • (3.49) 2 v a r 0 r T ( r , , , j A t . ) = v a r 0 2 H m a x (3-50) 2 L o o — L" • 0 ^ a n d H „ a r e t h e m a x i m u m a b s o l u t e v a l u e s o f t h e b o u n d a r y c m a x c m a x " f u n c t i o n 0O(T-^) a n d f u n c t i o n H ( r Q ) , r e s p e c t i v e l y , f o r t h e p r o b l e m . I t t h e r e f o r e f o l l o w s t h a t 0 2 H 2 v a r 0 N L ( r o } ^ + _ ^ - ( A t 0 ) 2 ( M - § ) (3.51) T h e n u m b e r s W a n d : L c a n h e c h o s e n t o m i n i m i z e t h e r i g h t - h a n d s i d e o f t h i s e x p r e s s i o n s u b j e c t t o . t h e c o n s t r a i n t N+ML = Q, w h e r e Q i s t h e t o t a l n u m b e r o f r a n d o m w a l k s t h a t a r e t a k e n . t o 49 o b t a i n a v a l u e o f 0 ( r ) . T h e m i n i m i z a t i o n g i v e s / M - !'/H T h i s r e s u l t s , w h e n u s e d w i t h t h e P o i s s o n e q u a t i o n i n S e c t i o n 5.4, g a v e I = 1 3 3 f o r N = 1 , 0 0 0 a n d M = 19. T h u s , a t l e a s t f o r t h i s e x a m p l e , t h e t i m e r e q u i r e d t o o b t a i n a M o n t e C a r l o v a l u e o f t h e i n t e g r a l I w a s o n l y a b o u t t w i c e t h e t i m e r e q u i r e d t o o b t a i n a v a l u e o f 0 l N ( r Q ) . (3 . 5 2 ) 50 4. COMPUTER M E C H A N I Z A T I O N OP MONTE C A R L O METHODS FOR S O L V I N G , P A R T I A L D I F F E R E N T I A L E Q U A T I O N S 4 .1 I n t r o d u c t i o n B a s e d u p o n t h e e q u a t i o n s g i v e n i n C h a p t e r s 2 a n d 3 f o r t h e M o n t e C a r l o s o l u t i o n s o f p a r t i a l d i f f e r e n t i a l e q u a t i o n s , a c o m p u t i n g s y s t e m f o r i m p l e m e n t i n g t h e m e t h o d s m u s t p e r f o r m t h e f o l l o w i n g o p e r a t i o n s . 1. T h e s t o c h a s t i c d i f f e r e n t i a l e q u a t i o n s o f S e c t i o n 2.4, namely | | + A 1 ( x , y , z , t ) = B 1 ( x , y , z , t ) N 1 ( t ) ( 2 . 2 7 ) | £ + A 2 ( x , y , z , t ) = B 2 ( x , y , z , t ) N 2 ( t ) ( 2 . 2 8 ) | | + A 3 ( x , y , z , t ) = B 5 ( x , y , z , t ) N 3 ( t ) ( 2 . 2 9 ) w i t h i n i t i a l c o n d i t i o n s r ( t ) = r Q m u s t h e s i m u l a t e d . I n a d d i t i o n , f o r p a r t i a l d i f f e r e n t i a l e q u a t i o n s t h a t c o n t a i n 0 i t s e l f , t h e f u n c t i o n a l T J = e x p - d [ r ( t ) , t ] d t (3.16) * o m u s t h e g e n e r a t e d . 5 1 2 . T h e s t o c h a s t i c p r o c e s s m u s t b e t e r m i n a t e d e i t h e r a t t i m e t = 0 o r w h e n e v e r t h e b o u n d a r y C o f a r e g i o n R i s r e a c h e d . T h i s r e q u i r e s a m e t h o d f o r s t o r i n g a n d d e t e c t i n g b o u n d a r i e s . 3 . T h e i n i t i a l o r b o u n d a r y v a l u e s 0^ a t t h e t e r m i n a l p o i n t s o f t h e r a n d o m w a l k s m u s t b e g e n e r a t e d . 4. T h e a v e r a g e N ^ i = l o r N i = l • f o r U v e r y l a r g e m u s t b e o b t a i n e d a t e a c h p o i n t ( r 0 > " t 0 ) f o r w h i c h a s o l u t i o n i s d e s i r e d . 5 . T h e s t o c h a s t i c p r o c e s s m u s t b e i n i t i a t e d , t e r m i n a t e d a n d r e s e t f o r e a c h r a n d o m w a l k . A u t o m a t i c r e a d o u t o f 0^(^ o '^ o) a n d a d j u s t -m e n t o f ( ? 0 > " f c 0 ) a f t e r e a c h s e t o f N r a n d o m w a l k s i s a l s o d e s i r a b l e . I n t h i s c h a p t e r a c o m p u t i n g s y s t e m i n w h i c h o p e r a t i o n s 1 , 2 a n d 3 a r e c a r r i e d o u t b y a n a n a l o g c o m p u t e r a n d o p e r a t i o n s 4 a n d 5 a r e c a r r i e d o u t b y a n a s s o c i a t e d d i g i t a l c o m p u t e r w i l l b e d e s c r i b e d . T h e e x p e r i m e n t a l s t u d i e s w e r e c a r r i e d o u t o n a n E l e c t r o n i c s A s s o c i a t e s I n c . P A C E 2 3 1 R - V a n a l o g c o m p u t e r a n d a L o g i s t i c s R e s e a r c h ALWAC I I I - E d i g i t a l c o m p u t e r . T h e d e s i g n a n d c o n s t r u c t i o n o f i n t e r f a c e e q u i p m e n t f o r h y d r i d i z i n g t h e t w o c o m p u t e r s w a s a n i n t e g r a l p a r t o f t h e p r o j e c t . D e t a i l s o f t h i s Q a s p e c t o f t h e w o r k a p p e a r i n t h e l i t e r a t u r e a n d i n A p p e n d i x I . 4*2 S i m u l a t i o n o f t h e S t o c h a s t i c P r o c e s s o n a n A n a l o g C o m p u t e r 4»2A A n a l o g C o m p u t e r S e t u p I n t h e p r o p o s e d M o n t e C a r l o m e t h o d s , t h e g e n e r a l s t o -c h a s t i c p r o c e s s d e f i n e d b y d i f f e r e n t i a l e q u a t i o n s ( 2 . 2 7 ) t o ( 2 . 2 9 ) i s s i m u l a t e d o n t h e a n a l o g c o m p u t e r . T h e s e d i f f e r e n t i a l e q u a t i o n s a r e o f f i r s t o r d e r , a n d i n g e n e r a l t h e y a r e c o u p l e d , n o n l i n e a r a n d n o n a u t o n o m o u s . P o r m a n y p a r t i a l d i f f e r e n t i a l e q u a t i o n s o f e n g i n e e r i n g i m p o r t a n c e * h o w e v e r , t h e s t o c h a s t i c d i f f e r e n t i a l e q u a t i o n s r e d u c e t o i n d e p e n d e n t , l i n e a r a u t o n o m o u s f o r m . T h e s t o c h a s t i c e q u a t i o n s f o r L a p l a c e ' s e q u a t i o n f y 0 = 0 , a n d t h e h e a t e q u a t i o n , V7 20 = ~ ^ + » f o r e x a m p l e , o n l y i n v o l v e i n t e g r a t i o n o f t h e n o i s e t e r m s N ^ ( t ) * A n a n a l o g c o m p u t e r b l o c k d i a g r a m f o r s i m u l a t i n g t h e s t o c h a s t i c d i f f e r e n t i a l e q u a t i o n ( 2 . 2 7 ) i n i t s m o s t g e n e r a l f o r m i s s h o w n i n F i g u r e 4 -1 * T h e f u n c t i o n g e n e r a t i o n i n d i c a t e d i n t h i s f i g u r e c a n b e r e a l i z e d s i m p l y w i t h d i o d e f u n c t i o n g e n e r a t o r s a n d q u a r t e r - s q u a r e m u l t i p l i e r s w h e n e v e r c l o s e d - f o r m m a t h e m a t i c a l e x p r e s s i o n s a r e k n o w n f o r t h e f u n c t i o n s o r w h e n e v e r t h e f u n c t i o n s 1"5 a r e o f o n l y a s i n g l e v a r i a b l e . S p e c i a l t e c h n i q u e s a r e r e q u i r e d f o r g e n e r a t i o n o f f u n c t i o n s o f a m o r e g e n e r a l f o r m . I n t e g r a t o r A 2 s h o w n i n F i g u r e 4-1 i s u s e d t o " t r a c k a n d h o l d " t h e r a n d o m v a r i a b l e x » T h i s t r a c k - a n d - h o l d f e a t u r e i s u s e d 53 F i g u r e 4 - 1 . B l o c k D i a g r a m f o r S i m u l a t i o n o f a S t o c h a s t i c D i f f e r e n t i a l E q u a t i o n t o h o l d t h e t e r m i n a l v a l u e o f t h e r a n d o m v e c t o r r , a n d c o n s e q u e n t l y t h e i n i t i a l o r b o u n d a r y v a l u e 0^  g e n e r a t e d f r o m r , ( S e c t i o n 4 .4) a t a c o n s t a n t v a l u e w h i l e 0^  o r ( 7^0 )^ ^ s r e a d b y t h e d i g i t a l c o m p u t e r . T h e m o d e - c o n t r o l s i g n a l c a n d i t s l o g i c a l i n v e r s e c s y n c h r o n i z e t h e t r a c k - a n d - h o l d m o d e s o f i n t e g r a t o r A2 w i t h t h e c o m p u t e a n d i n i t i a l - c o n d i t i o n m o d e s r e s p e c t i v e l y o f i n t e g r a t o r A l . T h e g e n e r a t i o n o f t h e s e m o d e - c o n t r o l s i g n a l s f r o m e l e c t r o n i c c o m p a r a t o r s a n d t h e d i g i t a l c o m p u t e r i s d i s c u s s e d i n S e c t i o n 4 . 3 . F o r p r o b l e m s i n w h i c h t h e f u n c t i o n a l 7 / m u s t b e g e n e r a t e d , 54 t h e f o l l o w i n g i m p l i c i t m e t h o d i s u s e d . P r o m e q u a t i o n ( 3 - 1 6 ) , ="7d [ r(t),t] (4.1) a n d 7 ( t 0 ) 1 A n a n a l o g c o m p u t e r b l o c k d i a g r a m f o r t h e s e e q u a t i o n s i s s h o w n i n P i g u r e 4 - 2 . 'X i s a v a i l a b l e a t t h e o u t p u t o f i n t e g r a t o r A 3 . N o t e t h a t t h e m o d e o f i n t e g r a t o r A3 i s a l s o c o n t r o l l e d b y c . r ( t ) 7 ( t J = + l t d [ r ( t ) , t ] 7 d [ r ( t ) , t ] P i g u r e 4 - 2 . B l o c k D i a g r a m f o r G e n e r a t i o n o f 5 5 4 . 2 B . N o i s e S o u r c e R e q u i r e m e n t s T h e u n c o r r e l a t e d G a u s s i a n w h i t e n o i s e s p e c i f i e d i n t h e t h e o r y ( S e c t i o n 2 . 4 ) m u s t h e a p p r o x i m a t e d b y n o i s e s o u r c e s t h a t a r e p h y s i c a l l y r e a l i z a b l e ' . N o i s e s o u r c e s w i t h a p p r o x i m a t e l y G a u s s i a n d i s t r i b u t i o n s b u t w i t h l i m i t e d b a n d w i d t h CL)^ c a n b e d e r i v e d f r o m g a s t u b e ' s , p s e u d o - r a n d o m n u m b e r g e n e r a t o r s " * " 4 e t c . I f t h e n o i s e b a n d w i d t h CO ^ i s l a r g e r t h a n t h e b a n d w i d t h c a p a b i l i -t i e s o f t h e a n a l o g c o m p u t e r , t h e n i t c a n b e a s s u m e d t h a t a n y e r r o r s r e s u l t i n g f r o m f i n i t e b a n d w i d t h s a r e c a u s e d b y t h e a n a l o g c o m p u t e r a n d n o t t h e n o i s e s o u r c e s . I n t h e c a s e o f a c P A C E 2 3 1 R - V a n a l o g c o m p u t e r , 6 0 ^ s h o u l d b e l a r g e r t h a n 1 0 • r a d i a n s / s e c . t o b e a b o v e t h e b a n d w i d t h c a p a b i l i t i e s o f t h e c o m p u t e r . T h e e f f e c t o f a l i m i t e d - b a n d w i d t h a m p l i f i e r w i t h i n t h e a n a l o g c o m p u t e r i s c o n s i d e r e d i n S e c t i o n 4 . 2 C . I n a d d i t i o n t o t h e b a n d w i d t h r e q u i r e m e n t s , t h e s t a t i s t i c s o f t h e n o i s e s o u r c e s m u s t b e s t a t i o n a r y d u r i n g t h e c o m p l e t e p r o b l e m s o l v i n g t i m e w h i c h f o r s o m e p r o b l e m s c o u l d b e s e v e r a l h o u r s . W i t h o u t s p e c i a l p r e c a u t i o n s , m a n y c o m m e r c i a l l y a v a i l a b l e n o i s e s o u r c e s f a i l t o . m e e t t h i s r e q u i r e m e n t . 4 T o o v e r c o m e n o i s e - s o u r c e b a n d w i d t h a n d s t a b i l i t y l i m i t a -t i o n s t h a t w e r e e n c o u n t e r e d i n t h i s s t u d y , t h e m u l t i c h a n n e l n o i s e Q s o u r c e d e s c r i b e d i n A p p e n d i x I I w a s d e v e l o p e d . T h i s n o i s e s o u r c e p r o d u c e s s t a b l e d i s c r e t e - i n t e r v a l b i n a r y n o i s e w i t h l e v e l s - 5 . 0 v o l t s , a n d h a s a n a d j u s t a b l e b a n d w i d t h t h a t c a n e x c e e d t h e b a n d w i d t h o f t h e a n a l o g c o m p u t i n g e l e m e n t s . A p p r o x i m a t e l y G a u s s i a n d i s t r i b u t e d n o i s e c a n b e o b t a i n e d f r o m t h i s n o i s e s o u r c e 1 4 b y l o w - p a s s f i l t e r i n g t h e b i n a r y n o i s e . I t w a s f o u n d i n t h e 56 e x p e r i m e n t a l s t u d y h o w e v e r . t h a t g o o d M o n t e C a r l o s o l u t i o n s c o u l d b e o b t a i n e d b y u s i n g t h e b i n a r y n o i s e d i r e c t l y . F o r g o o d r e s u l t s , t h e s t e p s i z e o f t h e r e s p o n s e m u s t b e e x t r e m e l y s m a l l c o m p a r e d t o t h e s i z e o f t h e r e g i o n R. U n d e r t h i s c o n d i t i o n , t h e c h a n g e i n r ( t ) d u r i n g a s m a l l t i m e A t i s s m a l l , s o t h a t t h e a s s u m p t i o n s m a d e i n S e c t i o n 2 . 4 a r e a p p r o x i m a t e d . Some i n h e r e n t a d v a n t a g e s r e s u l t f r o m t h e u s e o f b i n a r y n o i s e . O n e , t h e s t a t i s t i c a l p r o p e r t i e s o f t h e n o i s e a r e k n o w n p r e c i s e l y a n d c a n b e c h e c k e d e a s i l y . T w o , t h e d i s c r e t e n a t u r e o f t h e r e s p o n s e i s h e l p f u l i n s c a l i n g t h e s t o c h a s t i c d i f f e r e n t i a l e q u a t i o n s s i n c e t h e r e s p o n s e c a n b e m o n i t o r e d o n a n o s c i l l o s c o p e , a n d t h e s c a l i n g a d j u s t e d u n t i l t h e s t e p s i z e i s e x t r e m e l y s m a l l c o m p a r e d t o t h e s i z e o f t h e r e g i o n R. 4 . 2 C . E f f e c t o f F i n i t e B a n d w i d t h s o n S o l u t i o n T i m e s I n t h e o r y , i f i n f i n i t e - b a n d w i d t h n o i s e a n d a n a l o g c o m p u t -i n g e l e m e n t s ( a m p l i f i e r s e t c . ) w e r e r e a l i z a b l e , i t w o u l d b e p o s s i b l e t o t i m e s c a l e t h e s t o c h a s t i c d i f f e r e n t i a l e q u a t i o n t o o b t a i n r a n d o m w a l k s a t a n a r b i t r a r i l y h i g h r a t e . . Some i n s i g h t i n t o t i m e - s c a l i n g l i m i t a t i o n s d u e t o f i n i t e b a n d w i d t h s i s o b t a i n e d b y t h e f o l l o w i n g , m e a n s . A s s u m e a l l c o m p u t i n g e l e m e n t s a n d t h e n o i s e s o u r c e s h o w n i n F i g u r e 4 - 1 a r e i d e a l e x c e p t i n t e -1 5 g r a t o r A l . L e t i n t e g r a t o r A l h a v e t h e t r a n s f e r f u n c t i o n T ( s ) = - ( 4 . 2 ) w h e r e CO i s a m e a s u r e o f t h e b a n d w i d t h o f t h e a m p l i f i e r , a n d Q 57 i s a t i m e - s c a l i n g f a c t o r ( g a i n ) . U n d e r t h e s e a s s u m p t i o n s , t h e c o m p u t e r v a r i a b l e x s a t i s f i e s t h e f o l l o w i n g d i f f e r e n t i a l e q u a t i o n ; (*§-) + f r " + A 1 ( x , y , z , T ) = B 1 ( x , y , z , T ) N 1 ( T ) ( 4 . 3 ) w h e r e T = CCt i s t h e s c a l e d - t i m e v a r i a b l e . F o r t h e s t a t i s t i c s o f t h e c o m p u t e r v a r i a b l e x t o c l o s e l y a p p r o x i m a t e t h e s t a t i s t i c s o f t h e r e s p o n s e t o s t o c h a s t i c d i f f e r e n t i a l e q u a t i o n (2.27), t h e e f f e c t o f t h e s e c o n d d e r i v a t i v e t e r m m u s t be n e g l i g i b l e . H e n c e , t o m i n i m i z e e r r o r CL s h o u l d be k e p t s m a l l , b u t t o r e d u c e s o l u t i o n t i m e GL s h o u l d be made l a r g e . T h e c o m p r o m i s e t h a t m u s t be made i n c h o o s i n g CL c a n b e s t be d e t e r m i n e d e x p e r i m e n t a l l y . T h i s i s d o n e . b y i n c r e a s i n g C l u n t i l e x p e r i m e n t a l v a l u e s o f t h e s o l u t i o n o f t h e p a r t i a l d i f f e r e n t i a l e q u a t i o n d e v i a t e f r o m s o l u t i o n s o b t a i n e d w i t h Ct s m a l l . B y c h e c k i n g a t s e v e r a l p o i n t s , t h e l a r g -e s t v a l u e o f CL f o r g o o d r e s u l t s c a n be a s c e r t a i n e d . 4 . 3 D e t e c t i o n o f B o u n d a r i e s A n a n a l o g c o m p u t e r s i m u l a t i o n o f t h e s t o c h a s t i c d i f f e r -e n t i a l e q u a t i o n s f o r t h e r a n d o m v e c t o r r was d i s c u s s e d i n t h e p r e v i o u s s e c t i o n . I n t h i s s e c t i o n , m e t h o d s w i l l b e o u t l i n e d f o r t e r m i n a t i n g t h e s t o c h a s t i c p r o c e s s a t a g i v e n t i m e t = 0 o r w h e n e v e r r r e a c h e s a b o u n d a r y C o f a r e g i o n R . T h e m e t h o d s g i v e n a r e n o v e l i n t h a t o n l y e l e c t r o n i c c o m p a r a t o r s a n d d i o d e f u n c t i o n g e n e r a t o r s a r e r e q u i r e d . H e n c e , s p e c i a l p u r p o s e e q u i p m e n t s u c h 4 a s , a n o s c i l l o s c o p e mask a n d a p h o t o t u b e d e t e c t o r i s n o t r e q u i r e d . 58 U p o n t h e d e t e c t i o n o f a b o u n d a r y o r a t t = 0 , t h e m o d e -c o n t r o l s i g n a l c m u s t b e r e v e r s e d i n o r d e r t o p l a c e a l l i n t e g r a t o r s i n t h e i n i t i a l - c o n d i t i o n m o d e . S i n c e t h e t r a c k - a n d - h o l d a m p l i -f i e r s a r e c o n t r o l l e d b y c , t h e r e v e r s a l o f c p l a c e s t h e s e a m p l i -f i e r s i n t h e h o l d m o d e . I n t h i s s t a t e , t h e b o u n d a r y p o i n t r ^ o n C , o r t e r m i n a l p o i n t r ( 0 ) i s h e l d f i x e d w h i l e a t e r m i n a l v a l u e 0 i o r i s t r a n s f e r r e d t o t h e d i g i t a l c o m p u t e r . I m m e d i a t e l y a f t e r t h e t r a n s f e r t o t h e d i g i t a l c o m p u t e r , c i s r e v e r s e d b y t h e d i g i t a l c o m p u t e r , a n d a n e w r a n d o m w a l k i s i n i t i a t e d . T h e m o d e - c o n t r o l s i g n a l s c a n d c a r e c o n v e n i e n t l y g e n e r a t e d f r o m a m o d e - c o n t r o l f l i p - f l o p t h a t c a n b e t r i g g e r e d f r o m e l e c t r o n i c c o m p a r a t o r s o n t h e a n a l o g c o m p u t e r o r f r o m a p u l s e f r o m t h e d i g i t a l c o m p u t e r . T h e t r i g g e r i n g s c h e m e f o r t h e m o d e - c o n t r o l f l i p - f l o p i s s h o w n i n F i g u r e 4 - 3 • F r o m b o u n d a r y -d e t e c t i o n c o m p a r a t o r s F r o m t=0 c o m p a r a t o r OR JT F r o m d i g i t a l c o m p u t e r M o d e -C o n t r o l T i p - F l o p -3<—* c - = s — • c F i g u r e 4 - 5 . T r i g g e r i n g o f M o d e - C o n t r o l F l i p - F l o p 59 A pulse at input ( l ) terminates a simulation of the stochastic d i f f e r e n t i a l equations, and a pulse at input (2) i n i t i a t e s a new simulation of the equations. With th i s scheme, the problem of detecting boundaries and time t = 0 i s reduced to the problem of energizing electronic comparators whenever a boundary i s reached or whenever t = 0 . c from mode-control f l i p - f l o p to OR gate of mode-control f l i p - f l o p Figure 4-4.- Detection of Termination Time t = 0 The use of an electronic comparator to detect time t = 0 f o r random walks s t a r t i n g at time t i s shown i n Figure 4-4. A signal c Q i s obtained from the comparator when t = 0 . Note that c controls the mode of the integrator that i s shown i n t h i s figure. Hence, t h i s integrator i s placed i n the i n i t i a l - c o n d i t i o n mode at t = 0 or when a boundary i s reached, and i n the compute mode at t = t . o 60 4 . 3 A Detection of Boundaries f o r Problems with One Space  Variable Por problems with one space variable x, and boundaries at points x^^ and x^g- " t n e boundary detection comparators are energized by comparing the random voltage x with voltages x^^ and x, 9 . (see Pigure 4-5). from analog c i r c u i t simulating the stochastic d i f f e r e n t i a l equations x to OR gate of mode-control f l i p - f l o p b l vb2 Figure 4-5. Boundary Detection for Problems with One Space Variable. When x reaches x ^ or X - ^ J "the mode-control f l i p - f l o p i s t r i g r gered by either comparator output c^ or c^. 61 4.3B Detection of Boundaries f o r Problems with Two Space  Variables Consider f i r s t the simple two-dimensional region R with boundary C as shown i n Figure 4-6. Y Figure 4-6• Two-Dimensional Region The boundary of t h i s region i s composed of two curves C-^  = C-^X) and Cg = C^CX), each of which i s a single-valued function of X. A t y p i c a l random walk with instantaneous compon-ents (x,y) i s also shown i n the figure. It i s clear from Figure 4-6 that a random walk reaches a boundary whenever o r y = c l ( x ) y = c , ( x ) 6 2 (4.4) T h i s b o u n d a r y d e t e c t i o n c r i t e r i o n i s i m p l e m e n t e d o n t h e a n a l o g c o m p u t e r b y c o m p a r i n g t h e r a n d o m v a r i a b l e y w i t h f u n c t i o n s C ^ ( x ) a n d C g ( x ) t h a t a r e s e t o n d i o d e f u n c t i o n g e n e r a t o r s . A b l o c k d i a g r a m o f t h i s s i m p l e b o u n d a r y d e t e c t i o n s c h e m e i s s h o w n i n F i g u r e 4 - 7 . 2 T o OR g a t e o f m o d e - c o n t r o l f l i p - f l o p F i g u r e 4 - 7 . T w o - D i m e n s i o n a l B o u n d a r y D e t e c t i o n Now c o n s i d e r a m o r e g e n e r a l r e g i o n R i n w h i c h a d i v i d i n g l i n e D c a n b e c o n s t r u c t e d s u c h t h a t . C ^ a n d C g a r e s i n g l e - v a l u e d f u n c t i o n s o f U m e a s u r e d a l o n g D, ( s e e F i g u r e 4 - 8 ) , T h i s t y p e o f r e g i o n w i l l b e c a l l e d a s i m p l e r e g i o n . T h e r e g i o n c o n s i d e r e d p r e v i o u s l y i n w h i c h U w a s c o i n c i d e n t w i t h X , i s a s p e c i a l c a s e o f a s i m p l e r e g i o n . 63 Y A Figure 4-,8. Coordinate Transformation used f o r Boundary-Detection of Two-Dimensional Simple Regions. The boundaries of an a r b i t r a r y simple region are detected by transforming the random variables x and y to new variables u and v f o r which the boundary detection equations v = C 1(u) (4.5) and v = C 2(u) can be used. The new variables u and v are obtained from x 64 a n d y b y t h e t r a n s f o r m a t i o n u = x c o s fj - y s inyCj? - a (4.6) v = x s i n y $ + y c o s ^ - b w h e r e c o n s t a n t s a , b a n d j2 a r e d e f i n e d i n F i g u r e 4-8. H e n c e , t o d e t e c t t h i s t y p e o f b o u n d a r y , v a r i a b l e s u a n d v i n s t e a d o f x a n d y , r e s p e c t i v e l y , a r e u s e d w i t h t h e b o u n d a r y d e t e c t i o n , s c h e m e o f F i g u r e 4-7. F o r m o r e c o m p l i c a t e d r e g i o n s R i n w h i c h a d i v i d i n g l i n e D c a n n o t b e f o u h d , t h e r e g i o n i s d i v i d e d i n t o t w o o r m o r e s i m p l e r e g i o n s R-^, R 2 • . a n d t h e e x i t o f t h e r a n d o m v a r i a b l e r f r o m e a c h s i m p l e r e g i o n i s d e t e c t e d b y t h e m e t h o d g i v e n . B y c o m b i n i n g t h e s i g n a l s o b t a i n e d f r o m e a c h s i m p l e r e g i o n w i t h a n A N D g a t e , a s i g n a l i s o b t a i n e d w h e n r l e a v e s a l l t h e s i m p l e r e g i o n s R^ a n d h e n c e t h e r e g i o n R, I n m a n y e n g i n e e r i n g p r o b l e m s t h e b o u n d a r i e s a r e d e s -c r i b e d b y a s i m p l e m a t h e m a t i c a l e x p r e s s i o n . W h e n t h i s i s t h e c a s e , t h e b o u n d a r i e s c a n b e d e t e c t e d b y a n e v e n s i m p l e r m e t h o d t h a n t h a t g i v e n a b o v e . C o n s i d e r , f o r e x a m p l e , a n e l l i p t i c a l b o u n d a r y C d e f i n e d b y t h e e q u a t i o n ( X + a ) 2 . ( Y + c ) 2 _ n b d 65 T h e f u n c t i o n f ( x , y ) = <x % a > 2 + (y % c ) 2 b d ^ i s g e n e r a t e d w i t h m u l t i p l i e r s f r o m t h e r a n d o m v a r i a b l e s x a n d y , a n d c o m p a r e d t o l l - W h e n e v e r f ( x , y ) = 1 t h e r a n d o m w a l k i s a t t h e b o u n d a r y . H e n c e , o n l y t w o m u l t i p l i e r s a n d o n e c o m p a r a t o r a r e r e q u i r e d t o d e t e c t t h i s t y p e o f b o u n d a r y . S i n c e t h e p a r a -m e t e r s a , b , c a n d d o f t h e e l l i p t i c a l r e g i o n c a n b e v a r i e d s i m p l y b y a d j u s t i n g a n a n a l o g v o l t a g e , p r o b l e m s i n w h i c h a s o l u t i o n i s d e s i r e d a t s o m e p o i n t , a s a f u n c t i o n o f t h e p a r a m e t e r s , c a n b e h a n d l e d e a s i l y . ( s e e e x a m p l e o f . S e c t i o n 5 . 3 ) . T h e v e r s a t i l i t y o f t h e b o u n d a r y d e t e c t i o n m e t h o d s t h a t h a v e b e e n p r o p o s e d i s e v i d e n t f r o m t h e p h o t o g r a p h s h o w n i n F i g u r e 4 - 9 - T h i s p h o t o g r a p h o f a c i r c u l a r r e g i o n w i t h i n a s i m p l e r e g i o n w a s t a k e n b y c o n t i n u o u s l y e x p o s i n g a n o s c i l l o s c o p e d i s p l a y w i t h t h e v e r t i c a l a x i s d r i v e n b y r a n d o m v a r i a b l e y a n d t h e h o r i z o n t a l a x i s d r i v e n b y r a n d o m v a r i a b l e x . T h e r a n d o m w a l k s ( n o t v i s i b l e ) f o r t h i s p h o t o g r a p h w e r e s t a r t e d a t p o i n t s u n i f o r m l y d i s t r i b u t e d o n a c i r c l e b e t w e e n t h e b o u n d a r i e s o f t h e t w o r e g i o n s . A d o t w a s p r o d u c e d a t t h e t e r m i n a t i o n ^ , p o i n t o f e a c h r a n d o m w a l k . 66 * F i g u r e 4-9• P h o t o g r a p h I l l u s t r a t i n g a D e t e c t e d B o u n d a r y 4.3C D e t e c t i o n o f B o u n d a r i e s f o r P r o b l e m s w i t h T h r e e S p a c e  " V a r i a b l e s T h e d i v i d i n g - l i n e m e t h o d d i s c u s s e d i n S e c t i o n 4.3B c a n b e g e n e r a l i z e d t o t h r e e - d i m e n s i o n a l r e g i o n s b y u s i n g a d i v i d i n g p l a n e s u c h t h a t t h e b o u n d a r y s u r f a c e a b o v e a n d b e l o w t h e . p l a n e i s a s i n g l e - v a l u e d f u n c t i o n o f p o s i t i o n o n t h e p l a n e . F o r r e g i o n s i n w h i c h s i m p l e m a t h e m a t i c a l e x p r e s s i o n s a r e k n o w n f o r t h e f u n c t i o n s o f t w o v a r i a b l e s t h a t d e f i n e t h e s u r f a c e a b o v e a n d b e l o w t h e d i v i d i n g p l a n e , t h i s m e t h o d i s e a s y t o a p p l y . I f t h i s i s n o t t h e c a s e , h o w e v e r , s p e c i a l p u r p o s e f u n c t i o n g e n e r a t i o n 13 t e c h n i q u e s w o u l d h a v e t o b e u s e d . 67 T h e b o u n d a r i e s o f t h r e e - d i m e n s i o n a l r e g i o n s w i t h s o m e t y p e o f s y m m e t r y c a n o f t e n b e d e t e c t e d b y c o m b i n i n g t h e m e t h o d s d e s c r i b e d f o r o n e - a n d t w o - d i m e n s i o n a l r e g i o n s . F o r e x a m p l e , t h e c u b i c r e g i o n o f S e c t i o n 5 - 6 i s d e t e c t e d b y u s i n g 3 p a i r s o f c o m p a r a t o r s i n t h e s a m e m a n n e r t h a t a s i n g l e p a i r i s u s e d f o r o n e - d i m e n s i o n a l p r o b l e m s . I n a d d i t i o n , b o u n d a r i e s t h a t c a n b e d e f i n e d w i t h a s i n g l e e x p r e s s i o n , f o r e x a m p l e e l l i p s o i d s , c a n b e d e t e c t e d i n t h e s a m e m a n n e r a s c o r r e s p o n d i n g b o u n d a r i e s i n \. t w o d i m e n s i o n s . 4-4 G e n e r a t i o n o f I n i t i a l a n d B o u n d a r y V a l u e s A t t h e i n s t a n t t h e t e r m i n a l t i m e t = 0 o r a b o u n d a r y C i s r e a c h e d , t h e m o d e - c o n t r o l f l i p - f l o p i s t r i g g e r e d f r o m a c o m p a r a t o r b y t h e m e t h o d s t h a t h a v e b e e n d i s c u s s e d . T h e t r i g g e r -i n g o f t h i s f l i p - f l o p p l a c e s t h e t r a c k - a n d - h o l d a m p l i f i e r s ( F i g u r e 4-1) i n t h e h o l d m o d e s o t h a t t h e t e r m i n a l v a l u e s o f t h e c o m p o n e n t s x , y , a n d z o f r a r e a v a i l a b l e a s c o n s t a n t v o l t a g e s o n t h e a n a l o g c o m p u t e r . T h e i n i t i a l a n d b o u n d a r y v a l u e s 0^ a r e g e n e r a t e d w i t h f u n c t i o n g e n e r a t o r s f r o m t h e s e c o m p o n e n t s o f r . T h e f u n c t i o n g e n e r a t i o n p r e s c r i b e d a b o v e c a n b e c a r r i e d o u t w i t h f u n c t i o n g e n e r a t o r s a n d m u l t i p l i e r s w h e n e v e r t h e i n i t i a l a n d / o r b o u n d a r y v a l u e s a r e k n o w n a s s i m p l e f u n c t i o n s o f x , y a n d z o r w h e n e v e r t h e y c a n b e e x p r e s s e d a s a f u n c t i o n o f a s i n g l e v a r i a b l e . F o r t w o - d i m e n s i o n a l p r o b l e m s i n w h i c h a d i v i d i n g l i n e D i s u s e d f o r d e t e c t i n g t h e b o u n d a r i e s , t h e b o u n d a r y v a l u e s a r e c o n v e n i e n t l y g e n e r a t e d a s a f u n c t i o n o f 68 t h e v a r i a b l e u d e f i n e d a l o n g t h e d i v i d i n g l i n e . W h e n t h e v a l u e s 0^  c a n n o t b e g e n e r a t e d c o n v e n i e n t l y b y a n a l o g c o m p u t e r t e c h n i q u e s , t h e y c a n a l w a y s b e ; g e n e r a t e d w i t h i n t h e d i g i t a l c o m p u t e r . W h e n t h e d i g i t a l c o m p u t e r i s u s e d f o r f u n c t i o n g e n e r a t i o n , t h e c o m p o n e n t s x , y a n d z o f t h e t e r m i n a l p o s i t i o n v e c t o r r ( 0 ) o r r ^ a r e r e a d ; t h e n a t a b l e s t o r e d w i t h i n t h e c o m p u t e r i s s c a n n e d , o r s o m e o t h e r m e t h o d i s u s e d , t o d e t e r m i n e t h e c o r r e s p o n d i n g v a l u e o f 0^ . S i n c e m o r e t h a n o n e v a l u e m u s t b e r e a d b y t h e d i g i t a l c o m p u t e r a n d s i n c e a d d i t i o n a l d i g i t a l o p e r a t i o n s a r e r e q u i r e d , t h i s p r o c e d u r e w i t h s l o w d i g i t a l e q u i p m e n t i s m o r e t i m e c o n s u m i n g t h a n a n a l o g f u n c t i o n g e n e r a t i o n . H o w e v e r , w i t h f a s t d i g i t a l e q u i p m e n t i t i s p o s s i b l e t o s t o r e t h t h e t e r m i n a l c o m p o n e n t s x , y a n d z o f t h e i w a l k w i t h a S "fc t r a c k - a n d - h o l d a r r a n g e m e n t a n d r e a d t h e m d u r i n g t h e ( i + l ) w a l k . T h u s , i f t h e c o n v e r s i o n e q u i p m e n t a n d d i g i t a l c o m p u t e r a r e s u f f i c i e n t l y f a s t , t h e v a l u e s x , y a n d z c a n . b e r e a d a n d t h e t h d i g i t a l f u n c t i o n g e n e r a t i o n f o r t h e i w a l k c a n b e c a r r i e d o u t w h i l e t h e a n a l o g c o m p u t e r i s s i m u l a t i n g t h e ( i + l ) s ^ r a n d o m w a l k . T h i s p r o c e d u r e i s v e r y e f f i c i e n t i n t h a t e s s e n t i a l l y n o t i m e i s w a s t e d b e t w e e n w a l k s . F o r p r o b l e m s i n w h i c h v o l t a g e s f r o m m o r e t h a n o n e l o c a -t i o n w i t h i n t h e a n a l o g c o m p u t e r m u s t b e r e a d b y t h e d i g i t a l c o m p u t e r } a g a t i n g a r r a n g e m e n t i s o f t e n n e c e s s a r y f o r m u l t i p l e x -i n g t o a s i n g l e a n a l o g - t o - d i g i t a l c o n v e r t e r . B y s u i t a b l y p a t c h i n g a n E A I a m p l i f i e r e q u i p p e d w i t h e l e c t r o n i c s w i t c h i n g 9 a n e l e c t r o n i c S P D T s w i t c h t h a t i s s u i t a b l e f o r t h i s p u r p o s e c a n b e r e a l i z e d . T h i s s w i t c h i s d e s c r i b e d i n A p p e n d i x I I I . 69 4 . 5 O p e r a t i o n s P e r f o r m e d . . b y ...the D i g i t a l C o m p u t e r T h e t e r m i n a l v a l u e s 0. ( o r Y.0.) f o r e a c h r a n d o m w a l k a r e g e n e r a t e d b y t h e t e c h n i q u e s t h a t h a v e b e e n d e s c r i b e d . T h e m a i n f u n c t i o n o f t h e d i g i t a l c o m p u t e r i s t o c o m p u t e t h e a v e r a g e o f t h e t e r m i n a l v a l u e s a n d t o c o n t r o l t h e a n a l o g c o m -i p u t e r d u r i n g t h e c o m p l e t e p r o b l e m s o l v i n g t i m e . T h e a v e r a g e 0-.T(r , t ) f o r e a c h p o i n t ( r , t ) a t w h i c h ° H o o o o a s o l u t i o n i s d e s i r e d i s f o r m e d b y a d d i n g , i n s e q u e n c e , e a c h v a l u e 0^  ( o r i "Y^fi^) t o a p a r t i a l s u m s t o r e d w i t h i n t h e d i g i t a l c o m p u t e r . A t a l l y o f t h e n u m b e r o f r a n d o m w a l k s t h a t h a v e b e e n c o m p l e t e d i s k e p t b y t h e d i g i t a l c o m p u t e r , a n d a f t e r N w a l k s t h e a v e r a g e i s t y p e d o u t . A d i g i t a l c o m p u t e r , o r a t l e a s t a d i g i t a l m e t h o d , i s n e c e s s a r y f o r t h i s o p e r a t i o n b e c a u s e f o r N l a r g e ( 1 , 0 0 0 - 4 0 , 0 0 0 ) ^ a n e x t r e m e l y l a r g e d y n a m i c r a n g e i s r e q u i r e d t o o b t a i n t h e s u m p r e c i s e l y . T h e c o n t r o l f u n c t i o n s p e r f o r m e d b y t h e d i g i t a l c o m p u t e r a r e c a r r i e d o u t t h r o u g h t h e m o d e - c o n t r o l f l i p - f l o p ( S e c t i o n 4 - 3 ) a n d b y a g r o u p o f l o g i c l i n e s ( f l a g s ) r u n n i n g f r o m t h e d i g i t a l c o m p u t e r t o t h e m e m o r y a n d l o g i c u n i t o f t h e a n a l o g c o m p u t e r . T h e s e l o g i c l i n e s c o n t r o l e l e c t r o n i c s w i t c h e s a n d r e l a y s t h a t ' > a r e u s e d f o r m u l t i p l e x i n g , a n d o t h e r s w i t c h i n g o p e r a t i o n s o n t h e a n a l o g c o m p u t e r . T h e c o m p l e t e h y b r i d s y s t e m f o r i m p l e m e n t i n g t h e M o n t e C a r l o m e t h o d s i s s h o w n i n P i g u r e 4 - 1 0 . V o l t a g e l e v e l s o n t h e a n a l o g c o m p u t e r a r e c o n v e r t e d t o b i n a r y - c o d e d d e c i m a l f o r m b y t h e a n a l o g - t o - d i g i t a l c o n v e r t e r o f t h e E A I d i g i t a l v o l t m e t e r . A - D C o n v e r t e r ( D i g i t a l V o l t m e t e r ) I n t e r f a c e h o l d l o g i c l i n e s A n a l o g C o m p u t e r M o d e -C o n t r o l F l i p - F l o p D i g i t a l C o m p u t e r S t e p p i n g M o t o r s D r i v i n g P o t e n t i o -m e t e r s o F i g u r e 4 - 1 0 . H y b r i d C o m p u t e r S y s t e m - .. . 71 T h e i n t e r f a c e , u n d e r c o n t r o l o f t h e d i g i t a l c o m p u t e r , t r a n s f o r m s t h e b i n a r y - c o d e d i n f o r m a t i o n ! ; t o a f o r m t h a t i s c o m p a t i b l e " w i t h t h e i n p u t r e g i s t e r o f t h e d i g i t a l c o m p u t e r . T h e e n t i r e p r o c e d u r e f o r t h e t r a n s f e r o f d a t a f r o m t h e a n a l o g c o m p u t e r t o t h e d i g i t a l c o m p u t e r i s i n i t i a t e d , a s h a s b e e n d e s c r i b e d , b y a s i g n a l f r o m t h e m o d e - c o n t r o l f l i p - f l o p . T h e o p e r a t i o n o f t h e i n t e r f a c e i s d e s c r i b e d i n A p p e n d i x I. D i g i t a l - t o - a n a l o g c o n v e r s i o n i s a c h i e v e d b y d r i v i n g p o t e n t i o m e t e r s w i t h s t e p p i n g m o t o r s . A s e x p l a i n e d i n A p p e n d i x I, a p r e s c r i b e d n u m b e r o f p u l s e s a r e s e n t t o a s t e p p i n g m o t o r a t a r a t e o f 1 0 0 p u l s e s / s e c . t o c a u s e t h e w i p e r - a r m v o l t a g e t o c h a n g e i n a c c o r d a n c e w i t h t h e n u m b e r o f p u l s e s t r a n s m i t t e d . T h i s r a t h e r s l o w , b u t e c o n o m i c a l , c o n v e r s i o n s c h e m e i s a d e q u a t e f o r t h e M o n t e C a r l o m e t h o d s s i n c e d i g i t a l - t o - a n a l o g c o n v e r s i o n , i s . r e q u i r e d o n l y f o r a d j u s t m e n t o f t h e s t a r t i n g p o i n t s » t ) a f t e r e a c h s e t o f R r a n d o m w a l k s . T h e o p e r a t i o n o f t h e c o m p l e t e s y s t e m i s c l a r i f i e d b y t h e d e t a i l e d f l o w d i a g r a m ( F i g u r e 4 - 1 1 ) o f a h y b r i d c o m p u t e r p r o g r a m u s e d f o r t h e M o n t e C a r l o m e t h o d s . I n t e r m s o f t h i s f l o w d i a g r a m , t h e a n a l o g c o m p u t e r i s e q u i v a l e n t t o a s u b r o u t i n e f o r t h e g e n e r a t i o n o f t e r m i n a l v a l u e s 0^ ( o r ^^0^). A m a c h i n e -l a n g u a g e p r o g r a m c o r r e s p o n d i n g t o t h e a b o v e f l o w d i a g r a m i s g i v e n i n A p p e n d i x I V . T h e h y b r i d c o m p u t e r m e t h o d s t h a t h a v e b e e n o u t l i n e d i n t h i s c h a p t e r a r e u s e d i n t h e f o l l o w i n g c h a p t e r t o d e m o n s t r a t e t h e p r a c t i c a b i l i t y o f M o n t e C a r l o m e t h o d s f o r s o l v i n g a l a r g e c l a s s o f p a r t i a l d i f f e r e n t i a l e q u a t i o n s . S t a r t 72 N o R o S e t r a n d t p o t d e s i r i d v a l u e "by-s t e p p i n g m o t o r s . e n t i o m e t e r s t o a s e n d i n g p u l s e s t o i ' \ R e a d t h e v a l u e s o f r a r i d ' t t h a t h a v e b e e n s e t o n t h e a n a l o g c o m p u t e r a n d t y p e o u t r a n d t Q . P l a c e a n a l o g c o m p u t e r i n c o m p u t e m o d e b y t r i g g e r i n g t h e m o d e - c o n t r o l f l i p - f l o p . R e a d 0. ( o r y . 0 . ) f r o m t h e a n a l o g c o m p u t e r w h e n t h e " m o d e - c o n t r o l f l i p - f l o p i s p l a c e d i n t h e h o l d m o d e . f A d d 0 ( o r y±0±) s u m . t o t h e p a r t i a l > i R v a l u e s o f 0. ( o r y.0.) h a v e •u J X ' XX b e e n r e a d . ' Y e s 1 / " ide s u m b y R t h e n o u t p u t \ T h e s o l u t i o n h a s a l l p o i n t s ( r , t Q b e e n o b t a i n e d a t ) d e s i r e d . Y e s S t o p F i g u r e 4 - 1 1 . F l o w D i a g r a m f o r a T y p i c a l H y b r i d C o m p u t e r P r o g r a m 5 . H Y B R I D COMPUTER S O L U T I O N S OP I L L U S T R A T I V E P R O B L E M S 5 . 1 I n t r o d u c t i o n H y b r i d c o m p u t e r s o l u t i o n s o f a n u m b e r o f p a r t i a l d i f f -e r e n t i a l e q u a t i o n s t h a t w e r e s o l v e d b y M o n t e C a r l o t e c h n i q u e s a r e g i v e n i n t h i s c h a p t e r . T h e i l l u s t r a t i v e p r o b l e m s w e r e c h o s e n t o s u b s t a n t i a t e t h e n e w m e t h o d s t h a t h a v e b e e n p u t f o r w a r d a s w e l l a s t o i n d i c a t e t h e t y p e o f r e s u l t s t h a t c a n b e e x p e c t e d f r o m t h e M o n t e C a r l o m e t h o d s . T h e p r o b l e m s w e r e a l s o c h o s e n s o t h a t e x a c t a n a l y t i c a l s o l u t i o n s c o u l d b e f o u n d f o r c o m p a r i s o n w i t h t h e M o n t e C a r l o s o l u t i o n s . 5 . 2 O n e - D i m e n s i o n a l B o u n d a r y - V a l u e P r o b l e m s T h r e e e x a m p l e s a r e g i v e n i n t h i s s e c t i o n . T h e f i r s t , w h i c h i s a c t u a l l y a s p e c i a l c a s e o f t h e s e c o n d , d e m o n s t r a t e s a r e l a t i o n s h i p b e t w e e n t h e d u r a t i o n o f r a n d o m w a l k s a n d t h e p o w e r s p e c t r a l d e n s i t y o f t h e n o i s e s o u r c e . T h e s e c o n d a n d t h i r d e x a m p l e s s h o w , f o r v a r i o u s e q u a t i o n p a r a m e t e r s a n d b o u n d a r y c o n d i t i o n s , t h a t t h e M o n t e C a r l o s o l u t i o n s a r e i n c l o s e a g r e e -m e n t w i t h t h e e x a c t s o l u t i o n s . E x a m p l e 1 , d 2 ^ _ 0 0(-D = - 1 * 2 d x -o 0 ( + l ) = + 1 T h e s t o c h a s t i c d i f f e r e n t i a l e q u a t i o n t h a t m u s t b e s i m u l a t e d f o r t h i s o n e - d i m e n s i o n a l L a p l a c e e q u a t i o n w h i c h i s o f t y p e C ( S e c t i o n 3 . 3 ) i s M o n t e C a r l o s o l u t i o n s o f t h i s p r o b l e m a r e s h o w n a l o n g t h e ir = 0 1 l i n e i n . P i g u r e 5 - 1 • T o i l l u s t r a t e t h e v a r i a n c e o f t h e M o n t e C a r l o s o l u t i o n s , n u m e r o u s s o l u t i o n s t h a t w e r e o b t a i n e d a t x Q = 0 7 4 0 i.o 4 - 1 . 0 - . 6 - . 2 . 2 . 6 1 . 0 o 2 F i g u r e 5 - 1 . S o l u t i o n s o f D, ^ + K P~ = 0 . 1 d x o 75 a r e l i s t e d i n T a b l e 5-2. T h e l a r g e s t d e v i a t i o n i n t h i s s e t o f s o l u t i o n s i s o n l y 2.41$ o f t h e b o u n d a r y v a l u e s . D e v i a t i o n s o f t h i s o r d e r o f m a g n i t u d e a r e t y p i c a l f o r s o l u t i o n s o b t a i n e d w i t h 1,000 r a n d o m w a l k s . T h i s p r o b l e m , w h i c h i s t r i v i a l t o s e t u p , i s e x t r e m e l y u s e f u l f o r d e t e r m i n i n g t h e p o w e r s p e c t r a l d e n s i t y 2D-^  o f a n o i s e s o u r c e N - ^ ( t ) . A s i s s h o w n i n A p p e n d i x V , t h e a v e r a g e d u r a t i o n o f a r a n d o m w a l k s t a r t i n g a t x = x Q a n d t e r m i n a t i n g a t x = - 1 i s r e l a t e d t o t h e p o w e r s p e c t r a l d e n s i t y 2D^ t h r o u g h e q u a t i o n A V - 1 0 . 1 - x 2  I ^ o ) = - 2 D f S i n c e T ( x Q ) , f o r a n y v a l u e o f X q , i s e a s i l y m e a s u r e d , D^ c a n b e d e t e r m i n e d . P o r t h i s e x a m p l e t h e a v e r a g e d u r a t i o n T ( 0 ) o f r a n d o m w a l k s s t a r t i n g a t x Q = 0 w a s 290 m s . P r o m t h i s v a l u e 1 2 D l ~ 2T(o) = 1 o 7 2 u n i t s / s e c . w h e r e 1 u n i t = 100 v o l t s . 0 . 2 1 1.61 0.61 -2.19 0.41 - 0 . 5 9 0 . 8 1 - 2 . 3 9 1.01 - 0 . 7 9 - 0 . 9 8 2.41 2.41 - 0 . 9 9 - 0 . 5 9 -1 .39 -2 .19 - 0 . 7 9 T a b l e 5 -2 . V a l u e s o f i q O 0 N ( O ) o b t a i n e d w i t h N = 1000.• 7 6 A s a c h e c k o n t h e c o m p u t e r e q u i p m e n t a n d e q u a t i o n A V - l O y a g r a p h c o m p a r i n g t h e o r e t i c a l v a l u e s a n d t w o " s e t s o f m e a s u r e d v a l u e s o f T ( x ) , f o r . D^ = 1 . 7 2 u n i t s / s e c , w a s p l o t t e d . T h i s g r a p h i s s h o w n i n F i g u r e 5 - 3 . S i n c e t h e a b o v e p r o b l e m i s e x t r e m e l y s i m p l e t o s e t u p a n d s i n c e t h e i m p o r t a n t p a r a m e t e r D^ c a n b e e a s i l y d e t e r m i n e d b y m e a s u r i n g T ( 0 ) , i t i s o f t e n w o r t h w h i l e t o r u n t h i s p r o b l e m p r i o r t o m o r e c o m p l e x p r o b l e m s . F i g u r e 5 - 3 . A v e r a g e T i m e f o r a R a n d o m W a l k u s e d f o r t h e S o l u t i o n o f a O n e - D i m e n s i o n a l L a p l a c e E q u a t i o n . 77 Example 2, D, df0 + Z d0_ A 1 TT dx = 0 dx_ o 0 ( - D = -1 0(+l) = +1 The stochastic d i f f e r e n t i a l equation for t h i s example of Problem C i s i f - K = N i ( t ) -Solution curves f o r | = 0, 0.5 and 2.0 • " l 2 with = 1.72 unit /sec. (from Example 1.) are shown i n Pigure .5-1. Example 3. *-§ - ( l - x 2 ) 0 = 0 dx: 0 0(-l) = -1 0(+l) = A This i s an example of Problem D, Section 3.3- The stochastic d i f f e r e n t i a l equation i s If - Hi<*> and the related functional i s "Y e x P (1 - x^)dt ( 78 7 9 T h e i n t e g r a l i n t h e f u n c t i o n a l e x p r e s s i o n i s s c a l e d b y D^ s i n c e t h e n o i s e s o u r c e N ^ ( t ) h a s p o w e r s p e c t r a l d e n s i t y 2T>^ r a t h e r t h a n 2 a s i m p l i e d b y t h e p r o b l e m e q u a t i o n . Two s e t s o f M o n t e C a r l o s o l u t i o n s , f o r t h r e e v a l u e s o f A , a r e c o m p a r e d w i t h d i r e c t a n a l o g c o m p u t e r s o l u t i o n s i n F i g u r e 5 - 4 . 5 . 3 L a p l a c e ' s E q u a t i o n i n Two D i m e n s i o n s T h i s e x a m p l e d e m o n s t r a t e s t h a t M o n t e C a r l o m e t h o d s a r e c o n v e n i e n t f o r s o l v i n g p a r t i a l d i f f e r e n t i a l e q u a t i o n s a t a p o i n t * T h e p o t e n t i a l 0 a t t h e p o i n t X Q = - . 7 5 , y Q = 0 o f t h e r e g i o n s h o w n i n t h e c e n t r e p o r t i o n o f F i g u r e 5 - 5 i s d e t e r m i n e d a s a f u n c t i o n o f t h e c e n t r e p o s i t i o n d o f t h e i n n e r c i r c l e . M o n t e C a r l o s o l u t i o n s f o r 1 , 0 0 0 a n d 1 0 , 0 0 0 r a n d o m w a l k s p e r s o l u t i o n a r e s h o w n i n F i g u r e 5 - 5 . A t i m e o f a p p r o x i m a t e l y 2 m i n u t e s w a s r e q u i r e d f o r e a c h 1 , 0 0 0 w a l k s . I n t h i s e x a m p l e t h e b o u n d a r i e s 2 2 2 2 w e r e d e t e c t e d b y c o m p a r i n g x + y w i t h 1 a n d ( x - d ) + y 2 w i t h ( . 2 5 ) . T h e c e n t r e p o s i t i o n d o f t h e i n n e r c i r c l e w a s v a r i e d s i m p l y b y a d j u s t i n g a p o t e n t i o m e t e r . 5 . 4 P o i s s o n ' s E q u a t i o n i n Two D i m e n s i o n s \ 2 \ 2 P o i s s o n ' s e q u a t i o n , ~ \ 2 + \ 2 = ^ } i s s o l v e d oxo oy0 2 2 w i t h b o u n d a r y c o n d i t i o n 0 = ^Jo + ^ b o n t h e b o u n d a r y C o f c 2 2 r e g i o n R ( s e e i n s e r t i n F i g u r e 5 - 6 ) . T h e b o u n d a r y c o n d i t i o n w a s c h o s e n t o s a t i s f y t h e P o i s s o n e q u a t i o n s o t h a t a n e x a c t s o l u t i o n , 80 F i g u r e 5-5. S o l u t i o n s o f L a p l a c e ' s E q u a t i o n a s a F u n c t i o n o f a B o u n d a r y P o s i t i o n . 8 1 c o u l d b e f o u n d . F o r t h i s c h o i c e o f b o u n d a r y c o n d i t i o n t h e e x a c t s o l u t i o n i s a c t u a l l y i n d e p e n d e n t o f t h e s h a p e o f R. T h i s , h o w e v e r , c a n n o t b e p r e d i c t e d b y t h e c o m p u t e r s o t h a t n o l o s s o f g e n e r a l i t y r e s u l t s . A s o u t l i n e d i n S e c t i o n 3-3, P r o b l e m E , t h e s o l u t i o n o f t h i s p r o b l e m i s . g i v e n b y 0 0 ( r Q ) = 0 1 ( ? Q ) + J" 0 2(vt Q)dt o (3.35) - OO w h e r e 0j[_(^ o) > f ° r t h i s e x a m p l e , i s t h e s o l u t i o n o f L a p l a c e ' s e q u a t i o n Cbx2 b-2 ~ _ yo J o w i t h b o u n d a r y c o n d i t i o n x , y , 0 = - £ + - £ o n C o f R. C c. d 0 2 ( r o , t o ) i s t h e s o l u t i o n o f t h e h e a t e q u a t i o n w i t h i n i t i a l c o n d i t i o n 0 2 ( r Q , O ) = -2 82 a n d z e r o b o u n d a r y c o n d i t i o n s o n C o f R, T h e s t o c h a s t i c d i f f e r e n t i a l e q u a t i o n s u s e d f o r t h i s e x a m p l e a r e - ' !? = »2<*> F i g u r e 5 - 6 . S o l u t i o n s o f P o i s s o n ' s E q u a t i o n a n d L a p l a c e ' s E q u a t i o n i n t h e R e g i o n S h o w n . 83 02 @ x 0 = y Q = . 4 * M o n t e C a r l o S o l u t i o n s ( 1 = 1 3 3 ) I n t e r p o l a t e d S o l u t i o n 240 320 - t ( m s . ) c F i g u r e 5 - 7 . S o l u t i o n s o f t h e H e a t E q u a t i o n u s e d i n t h e S o l u t i o n o f P o i s s o n ' s E q u a t i o n . w i t h D^ = Dg = D. S i n c e t h e f u n c t i o n $2^To'^o^ i s a f u n c " t l 0 n o f t i m e , t h e c o m p u t e r t i m e v a r i a b l e t m u s t h e s c a l e d i n a c c o r d -| a n c e w i t h D. T h e c o r r e c t s c a l i n g i s t = D t . o c M o n t e C a r l o s o l u t i o n s o f 0 ( r Q ) a l o n g t h e l i n e X q = y Q a r e s h o w n i n F i g u r e 5-6. T h e s o l u t i o n 0 a t X q = y Q = . 4 , f o r e x a m p l e , i s t h e s u m o f 0^  a t X q = y Q = .4 a n d t h e i n t e g r a l w i t h r e s p e c t t o t Q o f 0^  a t X q = y Q = . 4 . A s g i v e n i n F i g u r e 5-6, 0^  a t x- = y Q = .4 i s .44 . T h e i n t e g r a l o f 0g a t X q = y Q = . 4 , f r o m a t r a p e z o i d a l r u l e i n t e g r a t i o n o f t h e v a l u e s o f 0g g i v e n i n F i g u r e 5-7 i s - . 2 7 . H e n c e , 0 a t X q = y Q = .4 i s 8 4 . 4 4 - . 2 7 = . 1 7 • T h i s v a l u e i s o n e o f t h e v a l u e s p l o t t e d i n P i g u r e 5 - 6 . F o r t h i s p r o b l e m , 1 , 0 0 0 r a n d o m w a l k s a n d 1 3 3 r a n d o m w a l k s w e r e s i m u l a t e d f o r e a c h v a l u e o f 0^  a n d 0^, r e s p e c t i v e l y . T h e s e v a l u e s , N = 1 , 0 0 0 a n d L = 1 3 3 , w e r e d e t e r m i n e d i n a c c o r d -a n c e w i t h t h e a n a l y s i s o f S e c t i o n 3 . 5 C . T h e t o t a l s o l u t i o n t i m e f o r e a c h v a l u e o f 0 ( r Q ) w a s a p p r o x i m a t e l y 12 m i n u t e s . 5 . 5 H e a t E q u a t i o n i n O n e , Two a n d T h r e e D i m e n s i o n s S o l u t i o n s o f t h e h e a t e q u a t i o n -w i t h i n i t i a l c o n d i t i o n s 0 o ( r Q ) = - 1 , a n d b o u n d a r y c o n d i t i o n s 0 ( r , ) = +1 , a t t h e c e n t r e o f a l i n e , a s q u a r e a n d a c u b i c r e g i o n C D a r e s h o w n i n F i g u r e 5 - 8 . T h e t h r e e p r o b l e m s , w h i c h a r e e x a m p l e s o f P r o b l e m A , S e c t i o n 3 . 2 , w e r e s o l v e d u s i n g n o i s e s o u r c e s w i t h D = 1 . 7 2 u n i t s / s e c . a n d u s i n g t w o , f o u r o r s i x e l e c t r o n i c c o m p a r a t o r s t o d e t e c t t h e b o u n d a r i e s . F o r t h e s e p r o b l e m s , i t i s i m p o r t a n t t o n o t e t h a t t h e a v e r a g e t i m e T ( 0 ) f o r a r a n d o m w a l k t o r e a c h a b o u n d a r y d e c r e a s e s s i g n i f i c a n t l y w i t h t h e d i m e n s i o n -o f t h e p r o b l e m . I n a l l c a s e s T ( 0 ) f a l l s w i t h i n t h e b o u n d s e s t a b l i s h e d i n A p p e n d i x V . 8 5 F i g u r e 5 - 8 . S o l u t i o n s o f t h e H e a t E q u a t i o n a t t h e C e n t r e o f a L i n e , a S q u a r e a n d a C u b i c R e g i o n . 8 6 5•6 L a p l a c e ' s E q u a t i o n i n T h r e e D i m e n s i o n s 2 T h e f i n a l e x a m p l e i s o f L a p l a c e ' s e q u a t i o n , 0 = 0 , i n t h e c u b i c r e g i o n b o u n d e d b y p l a n e s x = - 1 , y = - 1 , a n d x z = - 1 . M o n t e C a r l o s o l u t i o n s a l o n g t h e l i n e x Q = y Q = Z q f o r t h e b o u n d a r y c o n d i t i o n 0 c ( ? b } = ( x b " z b } + ( y b " z b > + V t " y b z b + x b z b a r e s h o w n i n F i g u r e 5 - 9 . T h e b o u n d a r y c o n d i t i o n w a s c h o s e n t o s a t i s f y t h e L a p l a c e e q u a t i o n s o t h a t t h e e x a c t a n a l y t i c a l s o l u t i o n i s k n o w n f o r a l l x , y a n d z . o' Jo o F o r t h i s e x a m p l e , s i x e l e c t r o n i c c o m p a r a t o r s w e r e u s e d t o d e t e c t t h e b o u n d a r i e s , a n d q u a r t e r - s q u a r e m u l t i p l i e r s w e r e u s e d t o g e n e r a t e 0 ( r ^ ) . A p p r o x i m a t e l y 5 m i n u t e s w e r e r e q u i r e d f o r e a c h p o i n t s o l u t i o n . 5 . 7 D i s c u s s i o n o f R e s u l t s I n t h e e x a m p l e s g i v e n a n d i n m a n y o t h e r e x a m p l e s t h a t w e r e s e t u p d u r i n g t h i s s t u d y , t h e M o n t e C a r l o s o l u t i o n s w e r e i n c l o s e a g r e e m e n t w i t h e x a c t s o l u t i o n s . I n a l l c a s e s , g o o d r e s u l t s w e r e o b t a i n e d i n a s t r a i g h t - f o r w a r d m a n n e r w i t h o u t t h e n e e d o f c r i t i c a l a d j u s t m e n t s . F o r - m o s t p o i n t s o l u t i o n s i t w a s f o u n d t h a t 1 , 0 0 0 r a n d o m w a l k s g a v e r e s u l t s s a t i s f a c t o r y f o r v e r i f y i n g t h e m e t h o d s . A n a v e r a g e o f a b o u t 5 m i n u t e s w a s r e q u i r e d f o r e a c h s o l u t i o n . T h i s t i m e w i t h a f a s t a n a l o g c o m p u t e r ( 2 0 mc b a n d w i d t h ) c o u p l e d t o a f a s t d i g i t a l c o m p u t e r c o u l d b e r e d u c e d t o a b o u t 1 s e c * ; . . 87 0 . 8 .6 .4 . 2 1—JS ) x \ [\ : / - 1 . 0 - . 8 - . 6 - . 4 - . 2 0 . 2 . 4 .6 . 8 1 . 0 x o ~ y o ~ z o * M o n t e C a r l o S o l u t i o n s (N = 1 0 0 0 ) o M o n t e C a r l o S o l u t i o n s (N= = 2 0 0 0 ) — A n a l y t i c a l S o l u t i o n F i g u r e 5-9. S o l u t i o n s o f L a p l a c e ' s E q u a t i o n i n T h r e e D i m e n s i o n s . i E v e n w i t h s l o w c o m p u t e r s , h o w e v e r , M o n t e C a r l o s o l u t i o n s a t a f e w p o i n t s c a n b e o b t a i n e d i n a b o u t t h e s a m e t i m e t h a t i s r e q u i r e d f o r f i n i t e - d i f f e r e n c e s o l u t i o n s o n a f a s t d i g i t a l c o m p u t e r . W i t h f i n i t e - d i f f e r e n c e m e t h o d s , h o w e v e r , s o l u t i o n s a t m a n y p o i n t s a r e o b t a i n e d s i m u l t a n e o u s l y . T h e e a s e w i t h w h i c h b o u n d a r y p o s i t i o n s c a n b e c h a n g e d ' w a s d e m o n s t r a t e d i n t h e e x a m p l e o f S e c t i o n 5.3. S i n c e t h e p o s i t i o n a n d s h a p e o f r e g i o n s , a s w e l l a s b o u n d a r y a n d i n i t i a l v a l u e s , c a n b e a l t e r e d v e r y e a s i l y , i t i s s u g g e s t e d t h a t t h i s u n i q u e f e a t u r e o f t h e M o n t e C a r l o m e t h o d s c o u l d b e u s e d t o 8 8 a d v a n t a g e i n e n g i n e e r i n g d e s i g n . F o r e x a m p l e , a M o n t e C a r l o s o l u t i o n o f a d e s i g n p r o b l e m i n w h i c h a b o u n d a r y o r b o u n d a r y v a l u e m u s t b e f o u n d t o g i v e a p a r t i c u l a r p o t e n t i a l a t a s p e c i f i e d p o i n t c o u l d b e s o l v e d e a s i l y . T h i s t y p e o f p r o b l e m o n a d i g i t a l c o m p u t e r , h o w e v e r , w o u l d r e q u i r e s e t t i n g u p a n e w f i n i t e - d i f f e r e n c e g r i d a n d s o l v i n g f o r a c o m p l e t e s e t o f p o t e n t i a l s f o r e a c h t r i a l b o u n d a r y o r b o u n d a r y v a l u e . 89 6 . C O N C L U S I O N S M o n t e C a r l o m e t h o d s h a v e b e e n d e v e l o p e d f o r o b t a i n i n g a p p r o x i m a t e s o l u t i o n s t o h o m o g e n e o u s a n d n o n h o m o g e n e o u s e l l i p t i c , a n d h o m o g e n e o u s p a r a b o l i c p a r t i a l d i f f e r e n t i a l e q u a t i o n s . H e n c e , e q u a t i o n s o f a m u c h m o r e g e n e r a l f o r m t h a n t h e c l a s s o f h o m o g e n e o u s e l l i p t i c e q u a t i o n s t r e a t e d i n t h e M i c h i g a n r e p o r t 4 c a n n o w b e s o l v e d b y M o n t e C a r l o m e t h o d s . H y b r i d c o m p u t e r t e c h n i q u e s f o r i m p l e m e n t i n g t h e M o n t e C a r l o m e t h o d s h a v e b e e n p r o p o s e d a n d t e s t e d . T h e t e c h n i q u e s u s e t o a d v a n t a g e t h e h i g h - s p e e d p a r a l l e l o p e r a t i o n o f t h e a n a l o g c o m p u t e r a s w e l l a s t h e m e m o r y a n d d y n a m i c r a n g e o f t h e d i g i t a l c o m p u t e r . P r o b l e m s a r e e a s y t o p r o g r a m , a n d e q u a t i o n p a r a m e t e r s , b o u n d a r i e s , a n d i n i t i a l a n d b o u n d a r y v a l u e s a r e e a s i l y m o d i f i e d . On t h e P A C E - A 1 W A C h y b r i d s y s t e m t h a t w a s u s e d t o s o l v e t h e e x a m p l e p r o b l e m s , 1 , 0 0 0 r a n d o m w a l k s c o u l d b e s i m u l a t e d i n a b o u t 5 m i n u t e s . W i t h a f a s t h y b r i d s y s t e m h o w e v e r , 1 , 0 0 0 r a n d o m w a l k s c o u l d b e s i m u l a t e d i n a b o u t 1 s e c . I n n e a r l y a l l c a s e s , t h e s o l u t i o n s t h a t w e r e o b t a i n e d w i t h 1 , 0 0 0 r a n d o m w a l k s w e r e w i t h i n 5 $ o f t h e m a x i m u m i n i t i a l o r b o u n d a r y v a l u e o f t h e e x a c t s o l u t i o n s . T h u s , w i t h 1 , 0 0 0 r a n d o m w a l k s , s o l u t i o n s w i t h s u f f i c i e n t a c c u r a c y f o r m a n y e n g i n e e r i n g p r o b l e m s a r e o b t a i n e d i n a r e a s o n a b l e t i m e . I n t h e m e t h o d s t h a t h a v e b e e n d e v e l o p e d , t h e s o l u t i o n s a r e o b t a i n e d i n a p o i n t - b y - p o i n t m a n n e r . T h e s o l u t i o n a t o n e p o i n t d o e s n o t d e p e n d u p o n t h e s o l u t i o n s a t n e i g h b o r i n g p o i n t s o r u p o n t h e t o t a l n u m b e r o f s o l u t i o n s t h a t a r e o b t a i n e d . P o r 90 t h i s r e a s o n t h e m e t h o d s a r e p a r t i c u l a r l y w e l l s u i t e d t o p r o b l e m s t h a t r e q u i r e s o l u t i o n s a t o n l y a f e w p o i n t s . I f s o l u t i o n s a t m a n y p o i n t s a r e r e q u i r e d , f i n i t e - d i f f e r e n c e m e t h o d s a r e m o r e e f f i c i e n t . T h e M o n t e C a r l o m e t h o d s t h a t h a v e b e e n p r o p o s e d r e q u i r e o n l y a s m a l l h y b r i d c o m p u t e r w h e r e a s f i n i t e - d i f f e r e n c e m e t h o d s f o r s o l v i n g p a r t i a l d i f f e r e n t i a l e q u a t i o n s r e q u i r e e i t h e r a l a r g e a n a l o g o r a l a r g e d i g i t a l c o m p u t e r . H e n c e , t h e M o n t e C a r l o m e t h o d s t h a t h a v e b e e n d e v e l o p e d s e e m i d e a l f o r s m a l l h y b r i d f a c i l i t i e s w h e r e i t w o u l d n o t b e p o s s i b l e t o e m p l o y o t h e r c o m p u t i n g m e t h o d s . 91 A P P E N D I X I I N T E R F A C E F O R T R A N S F E R OF DATA B E T W E E N THE P A C E 231 R - V AND THE ALWAC I I I - E * A b l o c k d i a g r a m o f t h e i n t e r f a c e f o r t r a n s f e r o f d a t a f r o m t h e P A C E t o t h e ALWAC i s s h o w n i n F i g u r e A I - 1 . T h e d i g i t a l v o l t m e t e r (DVM) o f t h e P A C E i s u s e d f o r a n a l o g - t o - d i g i t a l c o n -v e r s i o n . T h e f l i p - f l o p s t h a t a r e s h o w n i n t h e f i g u r e a r e t h e i n p u t f l i p - f l o p s o f t h e ALWAC t h a t a r e n o r m a l l y s e t f r o m t h e f l e x o w r i t e r . T h e v a l u e o f a n a n a l o g v o l t a g e i s t r a n s f e r r e d f r o m t h e P A C E t o t h e ALWAC i n t h e f o l l o w i n g m a n n e r . T h e ALWAC i s s i g n a l -l e d , n o r m a l l y v i a t h e m o d e - c o n t r o l f l i p - f l o p , t o r e a d a v a l u e . T h e ALWAC s u p p l i e s a " h o l d " s i g n a l t o t h e D V M . A b o u t 30 m s . a f t e r t h e a p p l i c a t i o n o f t h e h o l d s i g n a l a 5 - d i g i t p l u s s i g n b i n a r y -c o d e d - d e c i m a l e q u i v a l e n t o f t h e a n a l o g v o l t a g e i s a v a i l a b l e a t t h e DVM o u t p u t . T h e s i g n a n d e a c h d e c i m a l d i g i t a r e t r a n s f e r r e d s e q u e n t i a l l y t o t h e ALWAC f l i p - f l o p s a s f o l l o w s . T h e ALWAC o u t -p u t s a s i g n a l g w h i c h a l l o w s t h e s i g n f r o m t h e DVM t o e n t e r FF4. T h i s s i g n i s t h e n t r a n s f e r r e d t o t h e ALWAC a c c u m u l a t o r . T h e s i g n a l g 1 i s t h e n s u p p l i e d . T h i s a l l o w s t h e 10 ,000's d i g i t ( e i t h e r a 0 o r l ) t o e n t e r F F 1 o n i t s w a y t o t h e a c c u m u l a t o r . T h e ALWAC n e x t o u t p u t s w h i c h a l l o w s t h e b i n a r y - c o d e d 1 , 0 0 0 ' s d i g i t t o e n t e r f l i p - f l o p s F F 1 , F F 2 , FF3 a n d FF4• T h e d a t a i s t h e n t r a n s -f e r r e d i ro " t h e " a c c u m u l a t o r , a n d t h e p r o c e s s i s c o n t i n u e d u n t i l t h e l ' s d i g i t h a s b e e n r e a d . A f t e r a l l d i g i t s o f t h e DVM h a v e * F o r a m o r e d e t a i l e d d e s c r i p t i o n o f t h e i n t e r f a c e , s e e r e f e r e n c e ( 8 ) . S i g n 1 0 ' 1 0 -A n a l o g I n p u t 1 0 ' H o l d to 8 4 2 1 8 4 2 1 8 4 2 1 8 -4 -2 1-^ s f F l e x o w r i t e r A I D ] — b . g J i AND '1 g 2 l HAND 1 — c z d 1 A m OR AND g g j F l e x o w r i t e r - — j g HAND I— d z g <AND I—• d, I L AND OR 1 1 AND l l . 41 AND F l e x o w r i t e r 4 1 AND. g i l AND. g 4_1 OR A I D 1 . F l e x o w r i t e r 5 1 AND b, 15_L AND g 5 1 AND g 5 1 AND D i g i t a l x l x 4 I n t e r f a c e OR 92 F F I FF2 F F ? F F 4 ALWAC I I I - E " V o l t m e t e r F i g u r e A I - 1 . I n t e r f a c e f o r T r a n s f e r o f D a t a B e t w e e n P A C E a n d ALWAC 93 b e e n r e a d i n t o t h e a c c u m u l a t o r , t h e " h o l d " i s r e l e a s e d b y a s i g n a l f r o m t h e A L W A C . T h e e n t i r e r e a d i n g o p e r a t i o n r e q u i r e s a b o u t 10 m s . T h e a n a l o g v o l t a g e t h a t i s t r a n s f e r r e d t o t h e ALWAC m u s t b e h e l d a t a c o n s t a n t v a l u e a t l e a s t u n t i l t h e DVM h a s r e g i s t e r e d t h e c o r r e c t n u m b e r ( ^ 3 0 m s . ) . T h i s i s a c c o m p l i s h e d c o n v e n i e n t l y b y a n a n a l o g t r a c k - a n d - h o l d c i r c u i t t h a t i s c o n t r o l -l e d b y t h e m o d e - c o n t r o l f l i p - f l o p ( s e e F i g u r e 4 - 1 0 ) , D a t a i s t r a n s f e r r e d f r o m t h e ALWAC t o t h e P A C E t h r o u g h p o t e n t i o m e t e r s d r i v e n b y s t e p p i n g m o t o r s . T h e s t e p p i n g m o t o r s a r e d r i v e n b y p u l s e s o r i g i n a t i n g f r o m dummy i n s t r u c t i o n s i n t h e A L W A C . A s i n g l e p u l s e a t o n e i n p u t o f a s t e p p i n g m o t o r c a u s e s a + 1 5 ° r o t a t i o n w h i l e a p u l s e a t t h e o t h e r i n p u t c a u s e s a - 1 5 ° r o t a t i o n . T h e m o t o r s a r e c o u p l e d t o . the p o t e n t i o m e t e r s t h r o u g h 1 2 - t o - l r e d u c t i o n g e a r s . T h e r e f o r e , . i f a 1 0 - t u r n p o t e n t i o m e t e r h a s - 100 v o l t s a c r o s s i t , 144 p u l s e s a r e r e q u i r e d f o r a 1 0 - v o l t c h a n g e o n t h e w i p e r a r m . A n e x a m p l e o f a p r o g r a m t o c h a n g e t h e v o l t a g e o n a w i p e r a r m b y 20 v o l t s i s s h o w n i n F i g u r e A I - 2 . B y t h i s s c h e m e , p u l s e s c a n b e s e n t t o a s t e p p i n g m o t o r a t a r a t e o f a p p r o x i m a t e l y 100 p u l s e s / s e c . 94 P l a c e t h e N u m b e r 2 8 8 i n t h e E - R e g i s t e r Dummy I n s t r u c t i o n ( S e n d a P u l s e t o M o t o r ) D e c r e a s e N u m b e r i n E b y 1 E > 0 C o m p a r e E = 0 F i g u r e A I - 2 . I n s t r u c t i o n s f o r A c t i v a t i n g S t e p p i n g M o t o r 95 A P P E N D I X I I M U L T I C H A N N E L D I S C R E T E - I N T E R V A L B I N A R Y - N O I S E S O U R C E * N u m e r o u s c h a n n e l s o f s t a b l e , w i d e - b a n d n p i s e a r e r e -q u i r e d f o r M o n t e C a r l o m e t h o d s . A b l o c k d i a g r a m o f a n e c o n o m i c a l 3 - c h a n n e l n o i s e s o u r c e w i t h t h e s e p r o p e r t i e s i s s h o w n i n F i g u r e A I I - 1 . T h e S c h m i t t t r i g g e r i s t r i g g e r e d a t a n a v e r a g e r a t e o f " k " 0 — * - 1 s t a t e c h a n g e s / s e c . b y t h e z e r o - c r o s s i n g s o f t h e l o w -q u a l i t y n o i s e s o u r c e . A s h a r p p u l s e f r o m t h e r i n g c o u n t e r i s a p p l i e d c y c l i c a l l y t o e a c h AND g a t e a t a r a t e o f f p u l s e s / s e c . c I f k » f Q , t h e o u t p u t s N - ^ t ) , N 2 ( t ) a n d N ^ ( t ) a r e e s s e n t i a l l y u n c o r r e l a t e d a n d t h e a u t o c o r r e l a t i o n f u n c t i o n o f e a c h c h a n n e l i s e s s e n t i a l l y z e r o f o r |T I >^ ^ c F o r o u t p u t l e v e l s - E v o l t s , t h e a u t o c o r r e l a t i o n f u n c t i o n i s 0 ( T ) = E 2 (1 - f \T\ ) \T\ <i ^ c = 0 |T| > -± ( A I I . l ) c T h e p o w e r s p e c t r a l d e n s i t y cj? ( C d ) c o r r e s p o n d i n g t o t h i s a u t o -c o r r e l a t i o n f u n c t i o n i s Cp (GJ) = 2f E 2 c 1 - COS (<£—) , , c CO 2 ( A l l . 2 ) * F o r a m o r e d e t a i l e d a n a l y s i s o f t h i s n o i s e s o u r c e s e e r e f e r e n c e (9) L o w -q u a l i t y -n o i s e s o u r c e S c h m i t t T r i g g e r F l i p -F l o p C l o c k o f r e q u e n c y 3 f 3 s t a g e R i n g C o u n t e r AND F l i p -F l o p L e v e l S h i f t e r l N - ^ t ) AND F l i p -F l o p L e v e l S h i f t e r _ N ^ ( t ) AND F l i p -F l o p L e v e l S h i f t e r F i g u r e A I I - 1 . B l o c k D i a g r a m o f 3 - C h a n n e l N o i s e S o u r c e . VO 9 7 T h e M o n t e C a r l o s o l u t i o n s g i v e n i n C h a p t e r 5 w e r e o b t a i n e d w i t h k = .4 m c / s e c , f = 2 0 k c / s e c . a n d E = 5 v o l t s . c W i t h t h e s e v a l u e s t h e c r i t e r i o n k ^ > f i s m e t , a n d t h e h a n d -w i d t h o f t h e n o i s e c h a n n e l s i s g r e a t e r t h a n t h e b a n d w i d t h c a p a -b i l i t i e s o f t h e a n a l o g c o m p u t e r . 98 A P P E N D I X I I I A N E L E C T R O N I C S P D T S W I T C H B y s u i t a b l y p a t c h i n g a P A C E 2 3 1 R - V a m p l i f i e r e q u i p p e d w i t h e l e c t r o n i c s w i t c h i n g , a f a s t SPDT s w i t c h c a n b e r e a l i z e d . T h e r e q u i r e d p a t c h i n g i s a c c o m p l i s h e d b y p l a c e m e n t o f b o t t l e p l u g s a s s h o w n i n P i g u r e A I I I - 1 . T h i s p a t c h i n g r e p l a c e s t h e f e e d b a c k c a p a c i t o r C w i t h a 1 ; M ohm r e s i s t o r R a n d a l l o w s t h e o u t p u t V ^ t o b e s w i t c h e d b e t w e e n - V j ^ a n d - V - ^ u n d e r c o n t r o l o n t h e m o d e - c o n t r o l s i g n a l c . W h e n c = + 5 v o l t s , t r a n s i s t o r T ^ a n d t h e e l e c t r o n i c g a t e c o n d u c t s o t h a t V .^ = - V J Q . W h e n c = 0 v o l t s , t r a n s i s t o r T-^ a n d t h e e l e c t r o n i c g a t e a r e o p e n . I n t h i s m o d e V Q u t = - V ^ . F o r V - J - Q = + 1 0 0 v o l t s a n d V j N = - 1 0 0 v o l t s , t h e o u t p u t ^ o u t s w i t c h f r o m - V - ^ t o - V - ^ i n 1 6 0 jjisec. a n d f r o m - Y-^ t o - V-j-Q i n 1 0 0 jjisec. I C 1 0 0 K -AA/VV l O O K put • W W 1 m e g I C O P S O C o i l Q \ C o i l • 1 / a 1 / a F 0 f r o m mode c o n t r o l c i r c u i t r y r e p l a c e C b y R b y p a t c h i n g a s s h o w n - c o n n e c t i o n s m a d e b y b o t t l e p l u g s F i g u r e A I I I - 1 . C i r c u i t a n d P a t c h i n g f o r a S P D T S w i t c h 1 0 0 A P P E N D I X I V A P R O G R A M POR I M P L E M E N T I N G MONTE C A R L O METHODS.. A n ALWAC I I I - E p r o g r a m t h a t c a r r i e s o u t o p e r a t i o n s s i m i l a r t o t h o s e i n d i c a t e d i n t h e f l o w d i a g r a m o f P i g u r e 4 - 1 1 , S e c t i o n 4 . 5 i s g i v e n b e l o w : b 4 1 0 0 83b5 5 7 0 f 8 0 0 1 4 9 1 7 f f f O 8 1 0 2 d f O O d 9 0 3 8 2 0 3 0 0 0 1 0 0 0 0 8 3 0 4 f f a O 1 7 0 4 8 4 0 5 | f 9 e 0 f 9 e O 8 5 0 6 d l O c d f d a 8 6 0 7 0 3 e 8 0 0 0 0 8 7 0 8 5 7 0 3 1 1 8 c 8 8 0 9 f i e 5 f f f O 8 9 O a l b 0 8 2 8 0 0 8 a o b 0 0 0 0 0 0 1 3 8 b Oc, 5 7 0 5 2 8 0 0 8 c 0 d | f f e O 1 3 2 0 8 d o e 6 d 8 b 2 4 0 0 |8e o f 0 0 9 0 0 0 0 0 8 f 1 0 4913 4 9 1 7 9 0 1 1 4913 1 7 1 4 9 1 1 2 4 d 8 b 1 9 8 0 |92 13 0 0 0 0 0 0 0 0 9 3 1 4 f 9 e 0 f f f O 9 4 1 5 6 1 1 7 OeOO 9 5 1 6 1 1 1 6 0 0 0 0 |96 1 7 loooo 0 0 0 0 9 7 1 8 7 9 1 3 f f f O 9 8 19 e b l b 3 2 0 0 9 9 l a 0 0 0 0 0 0 0 0 |9a l b |05f5 e l O O 9 b I C 6 1 1 7 f f f O 9c I d d 5 8 0 f 5 c 8 |9d l e jOOOO 0 0 0 0 |9e I f |oooo 0 0 0 0 9 f 8 f b 6 4 9 b e I m m e d i a t e l y a f t e r t h e p r o g r a m i s i n i t i a t e d , 1 4 4 p u l s e s ( c o n t e n t s o f O f ) a r e s e n t t o a s t e p p i n g m o t o r f o r a d j u s t m e n t o f r . A m u l t i p l e x s i g n a l ( f l a g # l ) a l l o w s t h e ; v a l u e o f TQ t o b e r e a d . I m m e d i a t e l y a f t e r r Q i s r e a d , i t i s t y p e d o u t . One t h o u s a n d n u m b e r s ( c o n t e n t s o f 0 7 ) a r e t h e n r e a d f r o m a f i x e d t e r m i n a l o f t h e a n a l o g c o m p u t e r u p o n s i g n a l s f r o m t h e m o d e - c o n t r o l f l i p - f l o p . T h e s e n u m b e r s a r e a d d e d t o a p a r t i a l s u m a s t h e y a r e r e a d . A f t e r t h e 1 , 0 0 0 n u m b e r s h a v e b e e n r e a d a n d a d d e d t o g e t h e r ^ t h e s u m i s t y p e d o u t . A n o t h e r 1 4 4 p u l s e s a r e t h e n s e n t t o t h e s t e p p i n g m o t o r , a n d t h e p r o c e s s i s r e p e a t e d . T h e p r o c e s s i s r e p e a t e d a t o t a l o f 1 9 t i m e s ( c o n t e n t s o f 8 b ) . 101 APPENDIX V AVERAGE DURATION OP RANDOM WALKS In t h i s appendix a p a r t i a l d i f f e r e n t i a l equation i s derived for the average time T '(r ) that i s required f o r a random walk s t a r t i n g at r Q to reach a boundary f o r the f i r s t time. The equation i s solved f o r special cases to give the aver-age duration of a random walk that i s used for the solution of Laplace's equation i n a one, a two and a three-dimensional general-ized spherical region. The approach that i s used i s similar to, but not as involved as, the method of Wasow fo r calculating the 1 fi mean duration of discrete random walks. From the d e f i n i t i o n of g C r ^ t ^ | r o , t Q ) and from Chapman-Kolmogorov equation (2.2) i t follows that J^vM v V ^ b = y y ^ ' S l A ' V ^ b ^ i ^ i l v V d r i C E C (AV.l) i s the prob a b i l i t y density for a random walk to reach a bound-ary f o r the f i r s t time at t, i f i t started at (r ,t ). The b o o average duration of a random walk star t i n g at ( r o , t Q ) i s there-fore given by o o dr, dt, b b -©o C oo ( t b - V f z { w \ I ^ l ^ i ^W^i^i I vV^i R -oo C (AV.2) 102 OO = JJ(\ ~ V J «< I V V d r b d V ^ 1 ' % I ? o ' t o ) d r l R - o o - t Q ) Jg(?b,tb| 5 l f t 1 ) d r b d t b f ( r 1 . , t 1 | R -(AV..3) Therefore, T ( r o , t o ) = JH\,\WTV\ \ ? 0 , t 0 ) d r i R + - t Q ) j f ^ r ^ d r , R The l a s t term follows from the fact that (AV.4) oo - o o c (AV.5) for random walks that are certain to terminate at a boundary. Now l e t t-, = t + A t and expand T(r, ,t + A t ) i n 1 o 1 ' o a Taylor series about r Q i n the same manner that was done i n Chapter 2. I f t h i s i s done and equation (2,9) and the l i m i t s (2.11) to (2.21) are used, i t follows that 6t Q r o ^ o (AY.6) 103 I f the operator L- ^ i s independent of t Q , then o' o T ( r o , t Q ) i s also independent of t . For t h i s case T(r ,t ) can be denoted by T(r ) and L- T(r ) + 1 = 0 (AV.7) o The boundary condition for T ( r Q ) i s T(r^) = 0 If L- i s the operator that i s used f o r the.solution o of Laplace's equation,then D y 2 T ( ? Q ) +,1 = 0 (AV.8) For an n-dimensionaljgeneralized sphere of radius "a", T(r ) o depends only upon r Q = | r Q | , therefore, D 1 n-1 dr r o r ^ d T C ^ ) d r o + 1 = 0 T(a) = 0 (AV.9) i The'solution of the problem given by (AV.9) .is a 2 - r 2 This result shows e x p l i c i t l y how the duration of a random walk depends upon the s t a r t i n g radius r Q and the dimension of the sphere. By enclosing any other shape of region with a general-ized spherical region,an upper bound on the average duration of 104 a random walk can be obtained. A lower bound can be obtained by enclosing a generalized spherical region by the region f o r which the lower bound i s desired. For example, the average duration T(0) of a random walk s t a r t i n g at the centre of a square region with sides 2a i s (AV.ll) The average duration T(0) of a random walk s t a r t i n g at the centre of a cubic region with edges 2a i s h < T ( 0 ) < % (AV.12) 1 0 5 R E F E R E N C E S F o r s y t h e , G . E . , a n d W a s o w , W . R . , F i n i t e - D i f f e r e n c e  M e t h o d s f o r P a r t i a l D i f f e r e n t i a l . E q u a t i o n s . J o h n . . W i l e y a n d S o n s I n c . , New Y o r k , I 9 6 0 . C u r t i s s , T . J . H . , " S a m p l i n g M e t h o d s A p p l i e d t o D i f f e r e n t i a l a n d D i f f e r e n c e E q u a t i o n s " , P r o c . S e m i n a r o n S c i e n t i f i c C o m p u t a t i o n , I n t e r n a t i o n a l B u s i n e s s -M a c h i n e s C o r p . 1 , New Y o r k , N . Y . , N o v e m b e r 1 9 4 9 . M e y e r , H e r b e r t A . , E d i t o r , S y m p o s i u m . , o n M o n t e . - C a r l o .  M e t h o d s , J o h n W i l e y a n d S o n s I n c . , New Y o r k , 1 9 5 6 . . . C h u a n g , K . , K a z d a , I . F . , a n d W i n d e k n e c h t , T . , " A S t o c h a s t i c M e t h o d o f S o l v i n g P a r t i a l D i f f e r e n t i a l . E q u a t i o n s u s i n g a n E l e c t r o n i c A n a l o g C o m p u t e r " , P r o j e c t M i c h i g a n R e p o r t 2 9 0 0 - 9 1 - T . W i l l o w R u n l a b o r a t o r i e s , U n i v e r s i t y o f M i c h i g a n , J u n e I 9 6 0 . M a c K a y , D . M . , a n d F i s h e r , M . E . , A n a l o g u e C o m p u t i n g a t . U l t r a - H i g h S p e e d . C h a p t e r 1 6 , J o h n W i l e y a n d S o n s I n c . , N e w Y o r k , 1 9 6 2 . K a r p l u s , W a l t e r J . , A n a l o g S i m u l a t i o n , M c G r a w H i l l B o o k C o m p a n y , I n c . , N e w Y o r k , 1 9 5 8 . M i d d l e t o n , D a v i d , S t a t i s t i c a l C o m m u n i c a t i o n T h e o r y , C h a p t e r s 1 a n d 1 0 , M c G r a w H i l l B o o k C o m p a n y , I n c . , New Y o r k , I 9 6 0 . S o u d a c k , A . C , a n d L i t t l e , W . D . , ] " A n E c o n o m i c a l H y b r i d i z i n g S c h e m e f o r A p p l y i n g M o n t e C a r l o M e t h o d s t o t h e S o l u t i o n o f P a r t i a l D i f f e r e n t i a l E q u a t i o n s " , S i m u l a t i o n , V o l . 5 , N o . 1 , p p . 9 - 1 1 , J u l y , 1 9 6 5 . K o h n e , H . , L i t t l e , W . D . , S o u d a c k , A . C , " A n E c o n o m i c a l M u l t i c h a n n e l N o i s e S o u r c e " , S i m u l a t i o n . V o l . 5 , N o . 8 , N o v e m b e r , 1 9 6 5 -B h a r u c h a - R e i d , A . T . , " E l e m e n t s o f t h e T h e o r y o f M a r k o v  P r o c e s s e s a n d t h e i r A p p l i c a t i o n s , C h a p t e r 3, M c G r a w 1 H i l l B o o k C o m p a n y , I n c . , N e w Y o r k , I 9 6 0 . W a n g , M i n g C h e n , a n d U h l e n b e c k , G . E . , " O n t h e T h e o r y o f B r o w n i a n M o t i o n I I " , R e v i e w s o f M o d e r n . . P h y s i c s . V o l . 1 7 , N o s . 2 a n d 3, p p . 3 2 3 - 3 4 2 , A p r i l - J u l y 1 9 4 5 . D a r l i n g , D . A . , a n d S i e g e r t , A . J . , " A S y s t e m a t i c A p p r o a c h t o a C l a s s o f P r o b l e m s i n t h e T h e o r y o f N o i s e a n d O t h e r R a n d o m P h e n o m e n a , P a r t I", I R E T r a n s , o n I n f o r m a t i o n  T h e o r y . V o l . I T-3, p p . 3 2 -37, M a r c h , 1 9 5 7 . 1 0 6 W i l k i n s o n , R . H . , " A M e t h o d o f G e n e r a t i n g F u n c t i o n s o f S e v e r a l V a r i a b l e s u s i n g A n a l o g D i o d e L o g i c " , I E E E  T r a n s . On E l e c t r o n i c C o m p u t e r s . V o l . E C - 1 2 , p p . 1 1 2 -1 2 9 , A p r i l , 1 9 6 3 . H a m p t o n , R . L . T . , " A H y b r i d A n a l o g - D i g i t a l P s e u d o R a n d o m N o i s e G e n e r a t o r " , S i m u l a t i o n . V o l . 4 , No.. 3 , p p . 1 7 9 -1 8 5 , M a r c h , 1 9 6 5 . T o m o v i c , R . , a n d K a r p l u s , W . , H i g h - s p e e d A n a l o g  C o m p u t e r s , C h a p t e r 5 , J o h n W i l e y a n d S o n s I n c . . , N e w Y o r k , 1 9 6 2 . W a s o w , W o l f g a n g , " O n t h e M e a n D u r a t i o n o f R a n d o m W a l k s " , J o u r n a l o f R e s e a r c h o f t h e N a t i o n a l B u r e a u o f S t a n d a r d s . V o l . 4 6 , N o . 6 , p p . 4 6 2 - 4 7 1 , J u n e , 1 9 5 1 . Addendum Since the preparation of t h i s thesis, the following hooks have been brought to the author's attention: Dynkin, E.B.. Markov Processes. Vol. I and Vol. I I , Academic Press Inc. Publishers., New York, 1965. These books contain an extensive treatment of Markov processes. In p a r t i c u l a r , Chapter 13 of Volume II has a theor e t i c a l discussion of problems sim i l a r to those discussed i n Section 3.3 of th i s t h e s i s . 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0104848/manifest

Comment

Related Items