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 U n 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 . S c , The U n i v e r s i t y of B r i t i s h Columbia,  1961  M.A.Sc, The U n i v e r s i t y of B r i t i s h Columbia,  196 3  FRIDAY, OCTOBER 22, 1965, a t 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. Z e i g e r Research S u p e r v i s o r : A. D. Soudack E x t e r n a l Examiner: L. D. Kovach Pepperdine C o l l e g e Los A n g e l e s , California  HYBRID COMPUTER SOLUTIONS OF PARTIAL DIFFERENTIAL EQUATIONS BY MONTE CARLO METHODS ABSTRACT A continuous Markov process i s examined f o r t h e purpose of d e v e l o p i n g Monte C a r l o methods f o r s o l v i n g differential for  equations.  Backward Kolmogorov  partial  equations  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 and more  g e n e r a l 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 dens i t y functions are derived. the i n i t i a l  From these equations and  and boundary c o n d i t i o n s t h a t t h e d e n s i t y  functions s a t i s f y , differential  i t i s shown t h a t s o l u t i o n s of p a r t i a l  equations a t an i n t e r i o r p o i n t of- a r e g i o n  can be w r i t t e n as t h e expected v a l u e of r a n d o m l y - s e l e c t e d initial  and boundary v a l u e s .  From these r e s u l t s , Monte  C a r l o methods f o r s o l v i n g homogeneous and nonhomogeneous elliptic,  and homogeneous p a r a b o l i c p a r t i a l  differential  equations a r e proposed. H y b r i d computer techniques f o r mechanizing C a r l o methods a r e g i v e n . ted  computer i s  t o c o n t r o l t h e analog computer and t o form t h e r e -  q u i r e d averages. of  The Markov process i s simula-  on the analog computer and t h e d i g i t a l  used  the Monte  Methods f o r d e t e c t i n g the boundaries  r e g i o n s u s i n g analog f u n c t i o n g e n e r a t o r s and e l e c t r o n i c  comparators  a r e proposed.  Monte C a r l o s o l u t i o n s a r e obtained on a h y b r i d  system  c o n s i s t i n g of a PACE 231 R-V analog computer and an ALWAC I I I - E d i g i t a l two  computer.  The i n t e r f a c e f o r t h e  computers and a multichannel, 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 a r e d e s c r i b e d .  With t h i s  equipment,  solu-  t i o n s having a s m a l l v a r i a n c e a r e obtained a t a r a t e of approximately  f i v e minutes p e r s o l u t i o n ,  Example  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 two and three dimensionsPoisson'.s and  the heat  e q u a t i o n in'two  dimensions  e q u a t i o n i n ' one, two and t h r e e  dimensions.  GRADUATE STUDIES  Field  of Study:  Electrical  Engineering  A p p l i e d E l e c t r o m a g n e t i c Theory  G. B. Walker  Electronic  F. K.  Instrumentation  Network. Theory  A  Servomechanisms Solid-State  Electronic  N o n l i n e a r Systems Electron Digital  0  Bowers  D. Moore  E. V. Bohn Devices  Mo  P. Beddoes  A. C. Soudack  Dynamics  G. B. Walker  Computers  E. V. Bohn  Related Studies: Numerical A n a l y s i s I Computer  Programming  Integral  Equations  T. H u l l 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 Param e t r i c Frequency Converters w i t h N o n l i n e a r Conduct ance and C a p a c i t a n c e " , Proc, IEEE, V o l . 52, No. 3, p. 333, March, 1954. Soudack, A.C. and L i t t l e , W.D., "An Economical H y b r i d i z i n g Scheme f o r A p p l y i n g Monte C a r l o Methods to the S o l u t i o n of 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, No. 1, pp. 9-11, J u l y , 1965. L i t t l e , W.D., "An E l e c t r o n i c SPDT Switch", t i o n , Vol.- 5, No. 1, P. 12, July, 1965  Simula-  L i t t l e , W.D., and Soudack, A . C , "On the Analog Computer S o l u t i o n of F i r s t - O r d e r 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 M u l t i c h a n n e l Noise Source", S i m u l a t i o n , to be p u b l i s h e d , November, 1965.  HYBRID  COMPUTER  DIFFERENTIAL  SOLUTIONS  EQUATIONS  OP  B Y MONTE  WARREN D A V I D  PARTIAL CARLO  METHODS  LITTLE  B.A.Sc,  University  of  B r i t i s h  Columbia,  1961  M.A.Sc.,  University  of  B r i t i s h  Columbia,,  1963  SUBMITTED  IN  PARTIAL  FULFILMENT  OF  A  THESIS THE  We  accept  REQUIREMENTS  THE  DOCTOR  OF  in  Department  the  DEGREE  of  Engineering  this  as  thesis  Members of  of  conforming  to  the  standard  the  Electrical  UNIVERSITY  OF  PHILOSOPHY  Electrical  required  THE  FOR  Department Engineering  OF B R I T I S H  October,  1965  COLUMBIA  In p r e s e n t i n g the  r e q u i r e m e n t s f o r an  British  Columbia,  available for mission  representatives,,  cation  of  w i t h o u t my  Department  this  by  the  of Columbia  of  University  of  s h a l l make i t  thesis  Head o f my  permission.  fulfilment  I f u r t h e r agree that  this  for financial  The U n i v e r s i t y o f B r i t i s h V a n c o u v e r 8, C a n a d a Date  study.  the  Library  It i s understood  thesis  written  the  copying of  granted  in p a r t i a l  advanced degree at  r e f e r e n c e and  be  thesis  I agree that  for extensive  p u r p o s e s may his  this  copying or  shall  not  per-  scholarly  Department or  that  gain  for  freely  be  by publi-  allowed  ABSTRACT  A of  continuous  developing  ential  equations.  probability fied  by  From  these  that  the  of  Monte  differential be  and  boundary  methods  for  solving  Carlo  methods  the  partial  computer  are  analog  computer  and  the  the  analog  computer  and  to  for  detecting  generators  and  Monte consisting d i g i t a l  of  this  obtained Example three heat  a  PACE  computer.  multichannel With  Carlo  a  rate  solutions  dimensions, equation  231  for  the  of  of  interface  in  of are  solutions  Poisson's one,  two  three  ii  of  Monte  Carlo  e l l i p t i c a n d f  equations  are the  proposed. Monte  is  used  required  averages.  using  are  a  in  analog  on  a  and  two  control Methods  function  hybrid an  source  per  equation  two  in  dimensions  dimensions.  and  are  variance  minutes  system  ALWAC  computers  small  five  to  on  proposed.  computer the  a  randomly-selected  mechanizing  Laplace's  equation  and  point  computer  having  for  solutions  simulated  for  approximately given  derived. conditions  results,  obtained  analog  satis-  is  regions  are  conditional  process  comparators  R-V  value  differ-  that  interior  discrete-interval binary-noise  equipment, at  form  are  nonhomogeneous  Markov  solutions  The  and  d i g i t a l  boundaries  electronic  an  purpose  equations  shown  differential  The  the  is  the  for  boundary  these  techniques  given.'  the  From  general  i t  expected  homogeneous  equations  and  at  for  partial  functions  i n i t i a l  values.  parabolic  Hybrid  density  satisfy,  examined  solving  more  equations  w r i t t e n as  i n i t i a l  homogeneous  the  functions  for  and  probability and  is  Kolmogorov  functions  equations  can  process  methods  Backward  auxiliary  partial  region  Carlo  density  density  Markov  III-E a  described. are  solution. two and  and the  TABLE  OF CONTENTS Page  List  of  Illustrations  Acknowledgements 1.  . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . . . . . .  Thesis  '..  Outline  . . , . . . . * . . . « . . . . . . . « .  FUNDAMENTAL RELATIONS  FOR MARKOV P R O C E S S E S  2.2  Chapman-Kolmogorov Equations f o r Continuous Markov Processes w i t h i n Bounded Regions . . . . . . .  2.5  «  10  A Continuous Markov Process f o r which Backward Kolmogorov Equations are V a l i d . . . . . . . . . . . . . . . .  17  P a r t i a l Differential Equations Satisfied by Auxiliary Probability Density Functions .......  23  In *t 1*0(3. H C " t  3.2  Solutions P a r t i a l  1011  of Boundary-Value  Solutions  Estimates  Equations  f o r  . . . . . . . . . . . . . . . .  Problems  f o r  o f t h e Number  Carlo  Solutions  3.5A  Convergence  3»5B  Number P a r t i a l Number P a r t i a l  o f Random  39  o f Random  Walks  Carlo  Walks  Solutions  f o r  . . . .  45 45  Homogeneous  Equations  Walks  Differential i i i  f o r  42  f o r  . . . . . . . . . . . . . . . . . . . . . . . . .  Differential  31  Boundary-Value  o f Random  o f Monte  30  E l l i p t i c  Equations  o f Nonhomogeneous  30  Parabolic  «»»»».»..<>..*..«e»o»»«.».o«.»«.««»«o»»  Monte  3.5C  Problems  of Boundary-Value  Differential  Problems  BOUNDARY-  « 9 < * * « e » e a a * « » * » * « * * 9 * 9 « « * « « * e * » * « *  Differential  Solutions P a r t i a l  3.5  5  Backward Kolmogorov P a r t i a l Differential Equations . . . . . . . . . . . * . . . . . . . * . . . . . . « . . . . . . . * * .  3*1  3.4  1  5  MONTE CARLO METHODS F O R T H E S O L U T I O N S D F V A L U E P R O B L E M S ««o*#**e*«o-«« « • • ••••••  3o3  v i i i  5  Introduction  2.4  1  4  2.1  2.3  3.  V  INTRODUCTION  1.2 2.  ...............  .....,.*..  46  Nonhomogeneous  Equations  « . . . . . * . * .  47  Page 4.  COMPUTER MECHANIZATION OP MONTE CARLO METHODS FOR SOLVING- PARTIAL DIFFERENTIAL EQUATIONS .............  50  4.1  I n t r o d u c t i o n ««»«*..«»««««.....«*»..««««..«««*.  50  4.2  S i m u l a t i o n o f the S t o c h a s t i c Process on an Analog Computer  »»..•.•....«•.•......«...*.....  52  4.2A  Analog Computer Setup ••••••*•••••••••.•«  52  4.2B  Noise Source Requirements ...............  55  4.2C  E f f e c t of F i n i t e Bandwidths on S o l u t i o n Times  4.5  . . . . . . . . . . . . . . a . * . . . . * . . . . * . . . . * * . .  D e t e c t i o n o f Boundaries .......*«.............. 4.3A 4.5B 4.5C  57  D e t e c t i o n o f Boundaries f o r Problems w i t h One Space Detection Two Space Detection  V a r i a b l e «»....o............... of Boundaries f o r Problems w i t h V a r i a b l e s »««.««««.««....»...«« o f Boundaries f o r Problems w i t h  Three Space V a r i a b l e s »••«••••»..*•»'«••»•  5.  56  60 61 66  4.4  Generation o f 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  HYBRID COMPUTER SOLUTIONS OF ILLUSTRATIVE  PROBLEMS .  75  5*1  I n t r o d u c t i o n «..«.«.*«.««..«  5.2  One-Dimensional Boundary-Value Problems .......  73  5.3  L a p l a c e s Equation i n Two Dimensions •«....•,«»  79  5»4  Poisson's Equation i n Two Dimensions ..........  79  5.5  Heat Equation i n One  Two and Three Dimensions.  84  5*6  Laplace's Equation i n Three Dimensions ........  86  5.7  D i s c u s s i o n o f R e s u l t s .•»•»..•*».*«*•*•«•.«...*  86  « « « . » .  . . . o • > * . . « . « « .  T  t  iv  73  Page APPENDIX I I N T E R F A C E FOR T R A N S F E R OF DATA BETWEEN THE P A C E 2 3 1 R - V AND THE ALWAC I I I - E • • • » • • • » • • • • • • • • • • • • • • * • APPENDIX  II  MULTICHANNEL  DISCRETE-INTERVAL  APPENDIX III AN ELECTRONIC APPENDIX A  91  SPDT  SWITCH  BINARY-NOISE  SOURCE  . . . . . . . . . . . . . . . . . .  95  98  IV  PROGRAM FOR  APPENDIX V AVERAGE REFERENCES  IMPLEMENTING  DURATION ««  v  •  o  o o  »  »  MONTE  OF RANDOM WALES i  o  e  9  C A R L O METHODS  .....  «•»•••••*•••••-•-  e a o « g r 4 * o < T * « * « « f t « « 4 r « « « « < r « « « e * * « « o  100  101 103  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 C o n d i t i o n s of a T y p i c a l Problem with 1 Space V a r i a b l e •••••••••••  32  4-1*  Block Diagram 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 Equation ••»•*««.*«»••*•«••«»*».*••«.«  "X  5 3  4 - 2 *  B l o c k Diagram f o r Generation of  4-3*  T r i g g e r i n g o f Mode-Control F l i p - P l o p .............. 5 8  4 - 4 .  D e t e c t i o n o f Termination Time t =  0  « • • « • • • • • » • • • * • •  . . • • • • • • • • • • « * •  5 4  5 9  4-5*  Boundary D e t e c t i o n f o r Problems with. One Space V a r i a b l e ••••••»•••••*«••.•*••••••*••••.••••••«*.*. 6 0  4-6*  Two-Dimensional Region..**<,..«.••*...«.«»...«..».». 6 1  4 - 7 *  Two-Dimensional Boundary D e t e c t i o n  4-8.  Coordinate Transformation used f o r Boundary  • « « « o » « * * * * » » « « *  6 2  D e t e c t i o n 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 f o r a T y p i c a l H y b r i d Computer Program. 7 2 5 - 1 .  5 - 2 .  5-3*  S o l u t i o n s o f D. ^ — ^ + K dx  0  • • « « * • « . • • • • • * * • • *  7 4  o  Values of 1 0 0 0^(07 obtained w i t h N = 1 0 0 0 . . . . . . . . 7 5 Average Time f o r a Random Walk used f o r the S o l u t i o n of a One-Dimensional Laplace Equation **»•»»«•*««»« 7 6 2  5 - 4 *  =  •  Solutions of — %  -  ( 1  - x )  0 = 0  • « • « » . . . . « • • • • « • «  7 8  o 5-5. 5-6* 5-7.  S o l u t i o n s o f Laplace's Equation as a F u n c t i o n o f a Boundary P o s i t i o n * . » « • « • « • « . * . • « • * « * * * « . * « « « • * * • • 8 0 S o l u t i o n s o f Poisson's Equation and L a p l a c e s Equation i n the Region Shown ***•.»*.•**•*.***'**** 8 2 T  S o l u t i o n s of the Heat Equation used i n the S o l u t i o n of P o i s s o n s Equation ••**»••*••*•*•»*•*•****«•«•• 8 3 r  vi  Page 5-8*  5-9»  S o l u t i o n s o f the Heat Equation a t the Centre of a L i n e * a Square and a Cubic Region *.»••••*•«••»*•>  85  S o l u t i o n s o f Laplace's Equation i n Three Dimensions  87  AI-1* I n t e r f a c e f o r T r a n s f e r of Data Between PACE and ALWAC • « • * • « • "«• • * « * • • • *'» » * » • • • ••'• «•••*««*»*••••*«•• AI-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 " Stepping Motor .»•*•«.  94  AII-1«. B l o c k Diagram o f 3-Channel Noise Source • •••».«••<  96  A I I I - 1 . C i r c u i t and P a t c h i n g f o r a SPDT Switch .*<•«•-»•<•'»  99  1  vii  92  ACKNOWLEDGEMENT  Acknowledgement the my his  course thanks  of to  this Dr.  assistance  E l e c t r i c a l support;  A,  and  H.  hybridization; .  work. C.  encouragement  and  and  for  Mr.  R*  thanks  equipment  E l e c t r i c a l  particular,  his E.  are  I  supervisor Dr.  E.  assistance  given  for  to  helped  would of  like  this  Noakes,  U.B.C.,  Butler  have  for  with many  his  express  of  for  the  interest  and  computer  helpful  my w i f e ,  to  project,  Head  the  during  discussions.  Laurie,  for  her  help.  Research Council.for for  a l l who  Department,  Acknowledgement  and  In  to  encouragement;  Kohne  Special  due  Soudack,  Engineering  Mr.  is  is  gratefully given  Studentships  made  Engineering  available  to  awarded  in  through  Block  Department,  U.B.C.  v i i i  the  1962,  National and  1963,  Grants  to  the  1964,  1. 1.1  INTRODUCTION  Introduction High-speed  computing devices together with s o p h i s t i c a t e d  numerical methods are inadequate f o r s o l v i n g many p a r t i a l e n t i a l equations encountered  i n the study of continuous  differ-  systems."*"  Numerical methods c a l l e d Monte C a r l o methods are known f o r s o l v i n g many f u n c t i o n a l equations i n c l u d i n g a c l a s s 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 g e n e r a l l y proven to be v e r y / i n e f f i c i e n t . r 4  In  I960 a Michigan r e p o r t  an  o u t l i n e d a Monte Carlo method u s i n g  analog computer f o r s o l v i n g a c l a s s 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 w i t h a slow analog computer at approximately the same r a t e as that p o s s i b l e with a f a s t d i g i t a l computer. In t h i s p r o j e c t , a h y b r i d new  computer i s used to implement  Monte C a r l o methods that are developed f o r s o l v i n g a l a r g e  c l a s s of both e l l i p t i c and 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 equations.  Computing techniques are developed so t h a t , u n l i k e the  Michigan study, no s p e c i a l purpose the h y b r i d approach, many f e a t u r e s , program an e n t i r e problem  equipment i s r e q u i r e d .  With  i n c l u d i n g the c a p a c i t y to  s o l v i n g procedure and the c a p a c i t y to  o b t a i n automatic p r i n t o u t of a l l s o l u t i o n s , are made p o s s i b l e . Most computer methods f o r s o l v i n g p a r t i a l equations depend upon approximating the equations 1  f i n i t e - d i f f e r e n c e equations. '  differential by a set of  5  The number of d i f f e r e n c e  equations i n the s e t depends g e o m e t r i c a l l y  upon the number of  2  independent  variables  approximated For  digital  is  the  partial  differential  and upon t h e . p r e c i s i o n r e q u i r e d  many p r o b l e m s  required  in  such  the  number  that  computation,  of  storage or  difference  and  i n the  times  requirements  that  in  for  being  solution.  equations  solution  equipment  equation  the  are  case  of  COm-  analog zr  putation* as  are  solving  elements, are  entirely  the  set  for  Monte of  solutions to  the  that  Carlo  stochastic solve  inadequate  random p r o c e s s e s  as  a means  of  mathematical which  values  sense  to  problems* a  solution  determined the  solution*  random p r o c e s s In  the  processes  equations  that  by  in  of  the  are  The  for  lumped  analogies  many  involve  others. the  approximating  random p r o c e s s  is  desired  In  the  process  converge  be  found,  partial  form  of  in; -some :  passive  such  such  and f o r  differential  random walks  way  related  to  the  is a  related  manner in  F o r many m a t h e m a t i c a l  cannot  case  methods  a n d membrane  which  repeated  a  but  with  methods  problem f o r  such  equations  simulations  problems,  analog  are  many are, known*  to  some  Other  methods  of  statistical blems  difference  electrolytic-tank  suitable  sampling  of  unrealistic*  a pro-  others, equations,  c a n be  used  diffusion  * A random 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 from 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 , no amount 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 * ?  of  The t e r m s t o c h a s t i c p r o c e s s a time-dependent nature.'  is  used  to  denote  a  random  process  3 processes. the  three  (e.g.  Such  p a r t i a l d i f f e r e n t i a l equations  linear  Laplace's  second-order equation)  equation)  equations.  hyperbolic  type  solution  by  the  In the A  point  for  is  value, walk,  is  sense  A  the  As  the  started.  By  est  can  be  to  (e.g.  equation)  be  is  random  at  a  walks  be  this  is  to  are  obtain  are  desired,  value,  of  a  shown, at  to  this the  number  point  of  where  solution  at  this  work,the  random  walks  function  generators  well  to  determine  d i g i t a l the  random  walks.  random the  the  in  is  boundary or  boundary  of  a  each  is  deter-  s t a t i s t i c a l  walks  points  values  dynamic  is  random-noise  used  to  associated  This  walks  generated  on  terminal positions  computer  average  as  walk  values  random a l l  are  and  as  a  a  were  of  i n t e r -  obtained.  comparators  which  such  the  at  random  converges  tronic  with  to  solutions.  terminal position  to  the  each  i n i t i a l  response  of  the  considered,  sequence  an  the  to  be  normally  average  procedure,the  to  when  as  and  of  amenable  or  computer  adjoining  diffusion  time  the  large  in  and  analog  used  not  of  e l l i p t i c  approximate  started  predetermined  according  solution  In  are  the  two  discussed.  used  solution  average  w i l l  to  wave  prescribed  selected  and  mined.  a  either  reached.  parabolic  namely,  p a r t i a l d i f f e r e n t i a l equations  of  which  terminated  the  procedure  number  and  types;  P a r t i a l d i f f e r e n t i a l equations  methods  a l l  following  large  (e.g.  canonic  include  approach  can range  be  control with  takes  generated  and  memory  the  the  the  an  Elec-  analog  computer  walks.  analog  terminal  advantage on  the  sources.  the of  on  capabilities  computer positions  of  analog  The  the  speed  computer of  a  d i g i t a l  4 computer. 1.2  Thesis  Outline  F o l l o w i n g t h i s i n t r o d u c t o r y chapter,  partial  differ-  e n t i a l equations are d e r i v e d f o r c e r t a i n 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 of a c l a s s of Markov processes.  In Chapter  3>these 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 are used to d e r i v e Monte C a r l o methods that are proposed f o r  solving a large.class  of homogeneous and nonhomogeneous e l l i p t i c , a n d homogeneous 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 equations.  The  convergence of  the Monte C a r l o s o l u t i o n s to the exact s o l u t i o n i s a l s o The  use  considered.  of a h y b r i d computer 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 equations by Monte C a r l o methods i s discussed i n Chapter 4.  Computing techniques,  by the equipment, are o u t l i n e d .  as w e l l as l i m i t a t i o n s imposed Novel methods f o r d e t e c t i n g  boundaries f o r problems with one,  two  and three s p a t i a l dimen-  s i o n s are a l s o proposed. Experimental r e s u l t s are given i n Chapter 5 examples i n t h i s chapter and Poisson's  equation  i n c l u d e s o l u t i o n s of Laplace's  i n two  s o l u t i o n s of the heat equation  and  The equation  three dimensions,as w e l l as  i n one,  two  and three dimensions.  F i v e appendices f o l l o w the c o n c l u s i o n s g i v e n i n Chapter 6.  Included  i n these appendices are the d e t a i l s of the  8 i n t e r f a c e that was scription..of a new  b u i l t to l i n k the two type of multichannel  developed f o r t h i s p r o j e c t .  Q  computers  and  noise source that  the was  de-  5 2.  2.1  FUNDAMENTAL RELATIONS FOR  MARKOV PROCESSES  Introduction In t h i s chapter c e r t a i n 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 of s t o c h a s t i c processes known as continuous Markov processes are d e f i n e d and shown to be fundamental s o l u t i o n s of a c l a s s of 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 equations.  The  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  form is  c l o s e l y r e l a t e d to the form of the equations f o r the boundaryvalue problems that can be solved by the proposed Monte C a r l o methods.  In order that the methods apply to p a r t i a l  differential  equations of a v e r y g e n e r a l form, a v e r y g e n e r a l 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 w i t h i n Bounded Regions To s o l v e a boundary-value problem that i s d e f i n e d on  an open bounded r e g i o n R and i t s boundary C, a continuous Markov process r ( t ) , d e f i n e d on R and C, i s considered. R i s assumed to be a one,  two  In t h i s work,  or three-dimensional r e g i o n , and  the v e c t o r r ( t ) i s assumed to have components x, y and z i n a c a r t e s i a n coordinate system. A continuous Markov process can be d e f i n e d as a s t o c h a s t i c process h a v i n g the-property that future^ v a l u e s of .r.,.; depend upon a time-Ordered  set of known values of. r only 7 through the l a s t a v a i l a b l e value,*  6 T h a t i s , i f r i s known t o e q u a l r a t some f u t u r e t i m e t of r  i  2  s  i-  n  r n  o  a t time t ,then the value  Q  w  a  d e p e n d e n t upon known  v  a t some e a r l i e r t i m e t , <^t . - l ^ o  of  values  From t h i s d e f i n i t i o n  i t  7 can  be shown  f(1*2^2  that the c o n d i t i o n a l p r o b a b i l i t y density  ^ '^ ) completely 0  describes  0  the s t a t i s t i c a l  function  properties  Do fe f ir n where i t i o n f i s d e f i n e d as f o l l o w s . f(?2,t2  | ? *"fc )01^*2 i s t h e p r o b a b i l i t y t h a t t h e q  Q  random v e c t o r r i s i n d ^ t  a t time t  2  i f a t time.  , r = v . o' o  The t e r m s g i v e n  i n the d e f i n i t i o n are i l l u s t r a t e d  The d i f f e r e n t i a l d r  o f g e n e r a l i z e d volume a t t h e p o i n t d e f i n e d e i t h e r d x , dx,dy  of  R.  2  2-1.  t h a t i s used i n the d e f i n i t i o n i s an element  2  is  i n Figure  o  by ? .  That i s , d r ^  2  d x d y 2 d Z 2 d e p e n d i n g upon t h e d i m e n s i o n  r  2  2  An e l e m e n t a r y p r o p e r t y  of the c o n d i t i o n a l density  f u n c t i o n f f o r a Markov process 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 ^  2  > t  2  | r ,t ) = Q  o  Jf(? ,t 2  for a l l t This  equation  |r  2  <. t O  equation  n  1  1  , t  1  ) f ( r ^ ^  |r , t ) d r o  o  1  (2.1)  <_t . 0  2  expresses the f a c t that a t r a n s i t i o n of r from r  7 at  t  o  to  r~ a t 2 In  function t i o n - g,  f, is  t  2  0  occurs  addition the  to  via  some  the  conditional  following  also  point .  conditional  r, 1  at  time  t-, . 1  probability  probability  density  density  func-  defined.  Definition g(r^,t^  jr  Q  , t ^ d r ^ d t ^  random v e c t o r  r  between  t^  r  =  r  times  w i l l  is  the  reach  probability  boundary i f  at  that  C within  and  t^  +  dt^  time  definition  is  a  d i f f e r e n t i a l  area  a  t  Q  the  .  dr^  ,  . o  The  term  dr^  generalized  in  the  surface  about  point  r^  on  C.  element (see  Figure  3  x Figure  2-1. !  Space  Region  Illustrating  Defined  of  Terms  2-1)  8  From the Markov property walk from an i n t e r i o r  point r  t ^ must pass through some ?  and the f a c t  at t  Q  that a random  t o a boundary  point r ^ a t  a t time t ^ <_ t ^ , i t f o l l o w s  1  g must a l s o s a t i s f y  a Chapman-Kolmogorov equation; i . e . ,  S^b^b  h h>\  V V  =  ? ,t )f(r ,t  {  for a l l t  < o —  1  1  1  r ,t )d  1  o  o  r i  that  (2.2)  t , < L t. 1 b •  The Markov processes used f o r s o l v i n g p a r t i a l differential  equations are i n i t i a t e d a t time t  a t a point  r  Q  w i t h i n R,and are terminated e i t h e r at a predetermined time ±2 ^  t Q or whenever the random v a r i a b l e r reaches a boundary  point r ^ on C.  Hence, i f a process i s terminated due to a  boundary a b s o r p t i o n ,  i t occurs a t a time t ^ <_ t .  these statements, f and g must s a t i s f y and boundary A.  In view of  2  the f o l l o w i n g  initial  conditions.  I n i t i a l condition f o r f . lim  f(? ,t | r ,t ) = 2  2  o  §(?  Q  2  (2.3)  - r ) Q  where  S(?  " o^ ?  2  =  0  f  o  r  ?  2 ^ *o  a  n  d  J^8^  2  R  " o^ ?  d r  2  =  1  *  9 T h i s c o n d i t i o n expresses the f a c t that the point of t e r m i n a t i o n ? 2 i s the same as the s t a r t i n g point r  Q  i f the process i s  terminated immediately a f t e r i t i s i n i t i a t e d . B.  I n i t i a l c o n d i t i o n f o r g. lim  g(? t v  b  | ? ,t ) 0  Q  = 0  (2.4)  That i s , the p r o b a b i l i t y of reaching  a boundary point r ^ i s zero  f o r a walk s t a r t i n g at an i n t e r i o r point r  when the walk i s  Q  terminated immediately a f t e r i t i s i n i t i a t e d . C.  Boundary c o n d i t i o n f o r f . lim  ?  f(? ,t 2  2  |r  o >  t ) = 0  (2.5)  Q  o"^ b ?  T h i s c o n d i t i o n s t a t e s that i f the s t a r t i n g point r a boundary point ?  Q  approaches  there i s zero p r o b a b i l i t y that r w i l l be  b  i n an i n t e r i o r r e g i o n d r a t a time t 2  2  > t  .  Q  T h i s i s true  s i n c e the process w i l l terminate immediately a t the boundary point r ^ . D.  Boundary c o n d i t i o n f o r g. lim o  g(r ,t b  b  r , t ) = §(?<, - 5? ) § (* o  Q  b  b  "  V  b  where o(r w  v  o  - r, ) b ( t , - t ) = 0 b b o  unless  r  o  = r, b  and  t, = t D  O  10  t.  2  and  As  /  the  ? ,  interior  the  b  / g(r  n  - ?)  starting  process  is  § (\  b  point  certain to  - V  r  d r  b  d t  = 1  b  approaches  Q  a  boundary  point  terminate immediately at  the  point i* . b  In  addition to  these  i n i t i a l  the  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 must  and  t  o  2  , t  I  2  r  Q  , t  o  ) d r  2  f i r s t  of  term  the  bability  that  the  v a l i d  for  a l l  r  Q  +  this  r  two  has  time  t  and  reached  a  must  1 (2.7)  is  events  =  C  Q  equation  at  r ^ t j d r ^ o' o b b  h  2  be  ,  the  probability that  the  boundary true,  second  term i s  within time  the  sum  of  the  r the  tg.  is pro-  Since  two  terms  unity.  gral  the  equations  partial  following section  (2.1)  differential  and  previous  are  Partial  Chapman-Kolmogorov  section  expanding  (2.2)  a  are  the  Chapman-Kolmogorov  converted to  inte-  second-order  equations.  Backward Kolmogorov  The  by  of  boundary  In  2.3  • H / ' I S(r ,\ t  within  is  be  conditions,  •  R  one  also  boundary  :  f ( ?  The  and  converted  term i n  the  to  Differential  Equations  integral equations partial  integrands  of  of  differential the  integral  the equations equations  11 in a  a Taylor limit.  series  series  about  F o ra general  arerequired  in  which  in  a small  series  t h e random time  Kolmogorov  1  f ( r  = t  2  , t  2  |  process  r  , andthen  a l l terms  variable  by only  r  changes  t h el i m i t  t h ef i r s t  processes  a small  t w ot e r m s  i s taken.  taking  o f the^ T a y l o r  b u t f o rMarkov  amount of t h e  The r e s u l t i n g  p a r t i a l d i f f e r e n t i a l equations  a r ecalled  backward  equations.  At;  +  point  i n t h eexpansions,  when  Consider t  Markov  interval At,only  contribute  second-order  thei n i t i a l  ? ,t o  Q  Chapman-Kolmogorov  equation  (2.1) f o r  i . e . ,  )  Jf(? ,t |  =  2  r  2  1  , t  +At)f(? ,t 1  Q  Q  +  At|r  R For incremental gives If  At  At  probability equation  ,t )dr o  (2.8)  small,  transition  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  probability density  t h ed i s t r i b u t i o n o f displacements  after  Q  t h edisplacement of reaching  from  r  a boundary  Q  o f t h eprocess.  after  a small  i s so small  i s zero,  It  time  At.  that the  i t follows  from  (2.7) that  f(r ,t  lim  1  At-^O  o  +A t  r  o'  ,t  o  )d r  n  1  1  (2.9)  R To equation,the  convert  equation  term f ( ?  2  , t  2  (2.8) into  ^^.'^o  +  ^  a p a r t i a l d i f f e r e n t i a l ^  n  ^  e  equation  i s  expanded i n a T a y l o r s e r i e s about r -  F  o  "the expansion, a l l  r  0  v a r i a b l e s but  are assumed t o be f i x e d .  f(r ,t 2  The expansion y i e l d s  r ,t + A t )  2  o  Q  R  ll(r ,t |r ,t -r At)(x -z )  +  2  2  o  o  1  0  4K? ,t |r ,t At)(y -y )  +  2  2  o  o +  1  o  +  (? +  2  * 21 o ' o 1  ?  t  +A  t  }  ( x  i- o x  }  (yi-y > Q  A f(r ,t |r ,t +At)(x -x )(z -2 ) 2  2  6  +  x  2  o  o  1  1  o  o  6 o z  0  ^ 2,1 1? , t + At) (y-L-y ) 2f(?  2  +  Q  i^f£(? ,t 2  bx  2  2  o  r ,t o  0  o +  At)(  (Z-L-Z  -x )  X l  2  o  2  |^ f(? ,t |r ,t At)(y -y )' 2  +  +  2 ^2  2  2  o  o +  1  0  1 ^ f(? ,t |r ,t At)(z -z ) 2  2 ^2  2  2  o  o +  1  o  ;  O  )  13  + higher-order terms  f(r  l f  t fAt  V  0  t  ^ (2.10)  1.  If,  terms not involving x^, y^ or z^ are taken outside the integral,  2.  equation (2.9) i s used,  3.  a l l terms are divided by A t , and the following limits are assumed;  i i m  r^ i- o r o i o' o i  Tit  At—o  x  x  )f(? t  +At  ?  t  )dr  a  l  ( r  o' o t  (2.11)  )  J  lim A t -*-o  (2.12)  2 o^o  a  J  (r  )  R  lim At-*0  1  (z -z )f(r ,t +At  At  1  o  1  o  R  lim At 0  W  J  C ^ - V ^ l ' V ^ o ' V ^ l  =  ( 2  '  1 4 )  R  lim At-^0  J^yi-yo^^^i^o^^o^o^ *! = b ( r , t )  2fe  1  R  2  o  Q  (2.15)  14  lim  /  2ST  ,  ( «  1  - .  0  )  2  f ( p  l  t  f  0  +  A t | p  o  f  t  0  ) d P  b (r ,t )  1  3  0  ( 2 . 1 6 )  Q  At—0 R 1  lim At*-0  >  At  (x - )(y -y )f(r ,t At|r ,t )dr 1  X o  1  o  1  o +  o  o  = ^(r^tj  1  R  ( 2 . 1 7 )  1  lim At^o  (x -x )(z - )f(r ,t 4-At|r ,t )dr  "St  1  o  1  Z o  0  1  o  o  = Cg^o'V  1  R  ( 2 . 1 8 )  l At  lim At—O  (y -y )(z -z )f(r ,t At|r ,t )dr 1  0  1  o  1  o +  0  o  = « (r t )  1  3  0>  0  R  ( 2 . 1 9 )  R  ( 2 . 2 0 )  ZSt  1 X m  At—o  ^g^lvVAt)  lim At—o  - f(r  2 >  t |f 2  Q >  t )  I-  t  o  t  )  ( 2 . 2 1 )  then equation  ( 2 . 1 0 )  becomes  -£(ro,tJr / 2 ' " 2 r V ",t o ') ^ = a (r ,t )-p 1  i t  o  o  o  +  a (r ,t )^ 2  Q  o  o  +  a (r ,t )^ 3  Q  o  +  + c,(r ,t ) ^ + c ( r ,t ) § \ + c,(r ,t )ft , °' 6 <^o 6 W o 6*o6 o f  1  0  f  v  x  0 2  0  0  f  3  0  0  v z  0  ( 2 . 2 2 )  Z o  . 15 This  equation  Section  is  a  2.4  Kolmogorov  known  a  backward  p a r t i c u l a r Markov  equation Backward  conveniently  as  in  is  valid  terms  of  an  process  w i l l  Kolmogorov  Kolmogorov  be  for  equation.  which  the  In  backward  considered.  (2.22)  equation  operator  L  can  be  written  as r  ,t • o' o  (2.23) O  o  r  ,t _ o o 7  where  = r  a  ,t o'  ( r , t  n 1  °  0  )-££>  +  , ( r  a  x  2  , t •)•$0  is are  function with  position in  the  r  ?  respect vector  (2.23)  and  Q  of  p a r t i a l  equation  0  0  0  ) e^o  o  subscripts a  a , ( r . t 5  o  The  +  0  o  to r  .  t  O  are  and o  t  used  and  components The  to  that x  vector  0  > y  one  dimension  o  o  indicate  that  d i f f e r e n t i a l a  n  o  r^  and  d i f f e r e n t i a l equation. in  y  is  d  Z  q  time To  of tg  the are  c l a r i f y  the  operator  operations i n i t i a l parameters the  notation,  16  _ _kf_U ,t |x ,t ) 2  O  6  2  o  o  =  (  o  ,  x  ±  0  + b (x  )^(x  0  ,t  2  |x  o  ,t  o  )  Q  ) - ^ f Or o  ,t  1  x  Q  2  U  2 '  t  2 |  o '  X  t  o  (2.25)  )  ) x  By  a  procedure  Chapman-Kolmogorov converted V  r ,t  b  Using  1  Q  equation  backward  +At)  i s  the previously  operator  ^  to a  b  '  similar  Kolmogorov  expanded defined  i t follows  S  = L_  V  V  The  for  w i l l  solving  equations  partial  proceeding: t o Chapter limits  (2.11)  Kolmogorov  to  , t  In  series  (2.11)  to  Q  )  c  a  be  n  this  case  about  (2.21)  3,  w i l l  the  r  Q  .  and the  b  0  (2.26)  o  o  equations  3 to derive  problems  similar  (2.21)  equations  Q  out above,  that  differential  f o r m  » t-^J r  equation.  limits  b  boundary-value a  b  i n a Taylor  be used' i n Chapter  of  £ ^  carried  g(5 ,t |r ,t ) o'  derived  (2.2) f o r  notation,  l  to that  to  a Markov  that  (2.2fc). process  and a method be  that Monte  have Carlo  methods  are governed  by  However,  before  that  gives  rise  f o r generalizing  considered.  been  the  to  17 2.4  A Continuous  Markov Process f o r which Backward Kolmogorov  Equations are V a l i d In the Monte C a r l o methods to be o u t l i n e d , the coeff i c i e n t s i n the Kolmogorov equations c o i n c i d e w i t h 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 a p p l i c a b l e .  I t i s t h e r e f o r e 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 d e f i n e d  by the f o l l o w i n g set of s t o c h a s t i c d i f f e r e n t i a l equations*.  | | + A (x.,y.,z,t) = B ( x , y , z , t ) N ( t )  (2.27)  |2  + A (x-,y,z,t) = B ( x , y , z , t ) N ( t )  (2.28)  f | + A (x,y,z,t) = B (x,y,z,t)N (t)  (2.29)  1  2  3  1  1  2  2  3  3  These equations can be w r i t t e n i n matrix form  as  | | + A(r,t) = B(?,t)N(t)  (2.30)  The dependent v a r i a b l e s x, y and z i n t h i s model are the components of the random v e c t o r r , f o r which d e n s i t y func-r t i o n s f and g have been d e f i n e d .  The  c o e f f i c i e n t s A. and'B. 1  i  are, i n g e n e r a l , s l o w l y v a r y i n g continuous f u n c t i o n s of x, y, z and t .  The d r i v i n g terms N^(t) are u n c o r r e l a t e d with each  other, and each term i s s t a t i o n a r y Gaussian white n o i s e with  1 8  zero average.  These p r o p e r t i e s of N^Ct) are expressed i n the  f o l l o w i n g manner:  = 0  N^*)/  (2.3D  <^ (t )N (t ^> i  1  i  2  = 2D. § ( t t )  (2.32)  =0  (2.33)  r  ^ (t)N (ty> i  /  j  N (t )N.(t ) . . . K i  1  2  . (t )N (t ) 1  1  1  2  ^  2  . . . N.(t  N all  ±  i (  m  2 m  +  1  2  =0  ) \  (2.34)  (2.35)  )^  t.)N.(t.)>  ( ^ ( t ^ ^ t , ) )  ,  pairs  In these equations the brackets <^ ^ s i g n i f y an ensemble average.  S ( t ) i s tb.e u n i t impulse f u n c t i o n , and 2D^ i s the  power s p e c t r a l d e n s i t y of N ^ t ) .  Equations (2.34) and ( 2 . 3 5 ) ,  or s i m i l a r equations, are r e q u i r e d i n order to show that the l i m i t s of the h i g h e r - o r d e r moments (2.20) are a c t u a l l y zero. The properties that have been assumed f o r the model imply that each N^(t) has a Gaussian d i s t r i b u t e d a m p l i t u d e I n ( 2 . 3 5 ) , t h e sum i s to be taken over the  equation  ' p o s s i b l e ways  2 m! that 2m p o i n t s can be d i v i d e d i n t o m p a i r s . To show t h a t the process d e f i n e d by equation (2.30)  19 is  actually  given  r ( t  by  the  t ^  <  Q  )  a  Markov  =  r ,  process,  the  Q  i t  statistics  additional  information:  t  From  <  Q  t^.  x  )  = r  +  n  sufficient  o f r f t ^ )  that  equation * l  r ( t  is  are  r(t_^)  =  to in  show no  r_-^  that,  way  affected  where  (2.30),  r  |B(r,t)N(t)  j  -  dt  A(r,t)  (2.36)  t  Since upon ( t  Q  r ( t the  Q  )  r  is  Q  s t a t i s t i c s  , t ^ ) .  giyen,  =  If  the  fixed,  the  of  driving  the  additional  s t a t i s t i c s  of  vector  information  r(t^)  R(t)  in  r(t_^)  =  =  T_  depend the  r_-^  only  interval is  also  then  *o  B(f,t)N(t)  This in  condition  the  N(t)  interval  in  ( t  intervals do  on  not  Q  r(t)  ing  by  the  , t  Q  since  upon  is The  given  1  the  indeed limits  equations equations  A(r,t)  integral but  does  by  equation  Markov (2.11)  (2.27) between  not  r  to t  give  (2.32),  (2.37)  ±  any  about  N(t)  information  N(.t)  in  of  r(t-^)  information  the  about  two  therefore  r(t_^)  =  r_^.  process. to  (2.20)  (2.29) =  -  Q  information  The • s t a t i s t i c s  additional a  dt  provides  ) ,  uncorrelated.  depend  Hence,  ( t _  , t ^ ) ,  is  the  -  t  and  of  are t  the  Markov  calculated =  t  +  At  by and  process integratthen'  20  taking  the required  equation  (2.27)  Integration  ensemble  with  averages  l  - x  notation,  gives o  X  Consider  the coefficients written i n vector  t +At (  and l i m i t s .  o  )  =  A t  V  -  A (r,t)dt  +  1  J3 (.r,t)N (t)dt  J  1  1  (2.38)  Under rate  thfe than  condition N^(t),  that  this  A^(r,t)  equation  and B-^(r,t)  c a n be  vary  1  Q  o  1  Q  slower  A t  ( -x ) = - A ( r , t ) A t + B ( r , t ) o  a much  written  V  Xl  at  N ^ t j d t + o(At)  o  (2.39)  where  l i m  o(At) _  o  (2.40)  At—0 th The by  ensemble  average  of  the n  t h e Binomial! Theorem  power  of  ( X - ^ - X  q  i s  )  expressed  as  n k  n-k < ( * l - o ^  k.'(n-k)J  -  A  l (  ?  o '  t  o  )  A  t  k=0 V  A t ^N (t )N (t ) 1  1  1  2  . . ^(t^)^-  dt^tg  .  . .  .dt  k  + o(At) (2.41)  21. where, Prom  for  k  =  0,  conditions  N  the  multiple  (2.32),  1  ( t  1  ) N  (2.34)  ( t  1  2  )  .  integral and  .  is  (2.35),  R (t )J>  .  1  k k , ^ ^2, (2D )^(At)'  I  k  for!k  A  1  ,dt •=  d ^ d t g  k  for  ki  unity.  k  0  odd  (2.42)  even  (2.43)  2 (|)J 2  Hence,  A ( r , t 1  =  limits  obtained  Q  taking  a l l  the  are  valid  the  for For  b^(r ,t )  o  o  from  limit.  By  in  the  in  stochastic  x  A t  Markov  the  a  for  +  that  process a l l  by  defined  by  equations,  d i f f e r e n t i a l equations  1  for  n  for  n _>  (2.44)  =2  i t in  (2.45)  3  (2.46)  limit  dividing  assumed  relationships  Kolmogorov  =  o(At)  procedure, were  n  higher-order  expressions  a similar  completeness,  coefficients  o(At)  and  Q  these  conditions  the  or  +  D  , t ) ,  limiting  ) A t  o(At)  directly  and  (2.29).  a ^ ( r  Q  2  =  The  o  are  by  follows  A t that  Section  equations  2.3  (2.27)  to  between  the  and  coefficients  (2.27)  the to  (2.29)  limits,  are  22 listed  below:  a  i vV (  (2.47)  (2.48)  a  5  ( r  o  , t  )  Q  =  ~  3  A  (2.49)  V V  (  -I  2 (2.50)  (2.5D 2  V o'V = ?  B  3  (  =  The  fact  (2.52)  V V  C  =  that  3 o'V  coefficients  c.(r  °  =  ( ?  ,t  )  1 0  consequence  of  correlated  with  theory,  but  in  realize  noise  the  assumption  each  other.  practice sources  i t  that This  would  with  the  noise  zero  terms is  extremely  specified  are  -  is  55)  a  0  assumption be  (2  NV(t)  not  are  not  necessary  d i f f i c u l t  crosscorrelation  in  to  as  well  as  autocorrelation. A density ential  functions equations  following satisfy  Markov  Kolmogorov  f  and  (2.23)  section,  more  process g  giving that  and  auxiliary  general  equations  partial w i l l  be  rise  satisfy  (2.26)  has  to  Kolmogorov been  probability d i f f e r e n t i a l studied.  conditional  probability  partial  discussed.  density  In  functions  equations  than  d i f f e r the that the  23 2.5  P a r t i a l D i f f e r e n t i a l Equations Probability  The  Density  are  partial  d i f f e r e n t i a l equations. only  functions partial  contain  and  Monte  terms  g^which  Carlo  in  means  The the  form  variable  of  the  i t s e l f  of  Kolmogorov can  be  equations methods  Auxiliary  this  equations by  can  been  equations, of  problems form  have  solving  Kolmogorov  only  obtained  that  for  derivatives  that  d i f f e r e n t i a l equations  extended ent  f  of  Kolmogorov  derived  however,  basis  by  Functions  second-order  the  Satisfied  the  density  yielding be  treated.  containing  considering  the  An  depend-  auxiliary  12 density  functions  functions in  the  are  u ( r  f  and  v  defined  from  the  section  by  g.  this  With  same  weighting  below. Markov the  extension,  These  auxiliary  process  probability  as  considered density  p a r t i a l d i f f e r e n t i a l  equa-  c o n t a i n i n g a t e r m : i n the - dependent v a r i a b l e i t s e l f c a n be s o l v e d . The 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 and v  defined  2  and  obtained  previous  functions tions  are  u  , t  2  r  as  o  , t  follows:  Q  )  =  /exp  -m(t ,t 2  Q  )  ^ 2 ^ 2  V V  (2.54)  ; (r, ,t, ' -b' b  r  o'  ,t  o  (2.55)  )  24 The  term m(t  ,t ) Q  is  m(t ,t ) 2  where  d[r(t),t]  vector  r(t)  and  Q  =  is  a  given  /  by  the  (2.56)  d[r(t),t]dt  continuous  time  functional  positive  of  the  random  t.  r(t )=r 2  The  function  2  denote  brackets  a  r(t )=r Q  conditional  expectation;  that  tion  the  subject  within  r(t  )  =  r  12 Siegert, satisfy  ^2'*2 '  and  brackets r ( t )  is  2  In  a manner  i t  w i l l  the  be  a  p a r t i a l  0  T  to  that  = L_  the to  small  similar shown  following  IV V  in  is,  expected  the  conditions  region  that u ( r  2  dr  given  , t  value  r  2  Q  d i f f e r e n t i a l  by Q  func-  v^-  Darling )  the  that  about  2  , t  of  and  _ v(r^,t^  and  _ -o'^r) r  equations:  u ( r , t | r , t ) - d(r ,t ) u ( r , t r ^ t j 2  2  Q  o  Q  2  g  o' o l  (2.57)  V V  =L._  . v ( r o'  b  , t  b  r , t o  Q  )  -  d ( r  o  , t  o  ) v ( r  b  , t J r  o (2.58)  o  , t  o  )  25 Prom  the  identity  exp  -m(t ,t  and  the  ^ m ( t  i t  )  2  2  , t  1  )  -^r^exp  - m ( t  2  , t  1  ) d t  (2.59)  1  =-d[r(t ),t ] 1  2  the  multiplying  (2.60)  1  that  -m(t ,t )  Taking  1 -  relation  follows  exp  =  =  o  -  1  d[r(t ).,t ]exp 1  conditional by  f ( ?  2  , t  2  1  expectation r  Q  ,t  )  and  of  - m ( t  both  applying  1  ) d t  sides  of  2  , t  (2.61)  1  this  definition  equation, (2.54),  gives  u ( r  2  , t  r  2  o'  ,t  o  )  -  r ( t  ^ y ^ < ^ [ r ( t  1  ) ,t ]exp 1  2  ) = r  -m(t ,t ) 2  2  dt-jf ( r  1  r(t  2  , t  2  r  o'  ,t  o  )=r (2.62)  )  !  . 26 The c o n d i t i o n a l expectation,  i f r ( t ^ ) is,considered fixed at  r-^, can be w r i t t e n r(t )=r 2  d[r(t ),t ]exp 1  2  -m(t ,t )  1  2  1  r(t )=f. 0  r(t .)=r  N  2  d(r ,t- )exp 1  L  -m(t ,t ) 2  1  r(t )=r 1  ^  where p ( ? » ' 1  t  r ,t ;r ,t )dr  1  Q  Q  2  2  2N  0  ^  0  \p(r ,t  1  1  r ,t ;r ,t )dr  1  o  Q  2  2  (2.63)  /  i s the p r o b a b i l i t y that the  1  random v a r i a b l e r i s i n the r e g i o n dr-^ a t t-^ i f i t i s given that r i s at r tively.  P(r » 1  Q  and i n the r e g i o n d r a t times t 2  Q  and t  respec-  2  F o r a Markov process  t 1  r„,tj 0 '  1  O'  f(? ,t 2  2  r ,t ) 1  1  (2.64)  t  Now, s i n c e r-^, w i t h i n the c o n d i t i o n a l e x p e c t a t i o n , i s fixed, d ( ? , t ) 1  i n the second member o f equation ' {2£ft)  1  taken outside the c o n d i t i o n a l e x p e c t a t i o n . Markov process, i s given and t  c  a  2  >  Q  "> t .  The c o n d i t i o n r ( t ) = r  t h e r e f o r e be d e l e t e d from the c o n d i t i o n a l  t  Also, f o r r ( t ) a  r ( t ) i s independent o f ? ( t ) when r(t^) = 2  n  Q  Q  expectation.  can  e  1  27 Therefore,  R  f ( r  1  >  t  |r  1  f  Substituting  equation  using  the definition  u ( r  2  2  , t  |  r  , t  o  Jyd(r ,t )u(r ,t 1  *o  If  1  2  Q  )  = f ( r  (  , t  2 '  ?  o  of u ( ?  2  , t  r  2  1  2  , t  1  2  ) = r  r(t  Q  )=r  r ( t  2  ) = r  2  r ( t  1  ) = r  1  ) f ( r  2  t  back , t  0  2  o '  ?  (2.65)  r  2  Q  r ( t  , t t  o  2  I r  2  , t  1  ) d r  1  (2.65)  )  into  equation  (2.62),  and  gives  2  , t  1  Q  ) f ( r  )  -  1  , t  1  j  r  Q  , t  0  ) d r  1  d t  (2.66)  1  R  the order  equation where  of integration  are operated  from  (2.23)  upon  i s with  reversed  and both  the operator  sides  L  of the  + -^-r , o'  o  28  r  ,t ) = 0 o' o  the f o l l o w i n g equation i s obtained;  + "TT  yd(r  l  1u ( r , t 2  t )u(r  f  0  2  f  t  |r  2  r 0^ , tO ' j =  2  l f  t )f(r ,t Q  1  Q  j r ^ t ^ d ^  (2,67)  R  Prom equation (2.3),  lim  f(r ,t 1  however,  S (? - r )  | r |,t ) =  1  o  o  1  Therefore,  u(? ,t 2' 2 st o  L  0  u  .r , t J -V V  0  =L  o  u(r ,t 2  2  r ,t ) -d(r ,t )u(r ,t o  Q  Q  Q  2  2  (2.57) as was to be shown. By a s i m i l a r a n a l y s i s , w i t h p ( ? , t 1  r e p l a c e d by q ( ? , t 1  q(r ,t 1  1  I r ^ t ^ r ^ t ^ ) , where  1  |,r ,t ;r ,t )g(r ,t o  o  b  ^o'"* o'^2'^2^ ;  1  b  b  f(r ,t 1  1  b  r ,t ) o  Q  r ,t )g(r ,t o  o  b  b  r^t-J  (2.68)  29  i t  follows  that It  functions  from  is  u  conditions  (2.3)  definitions  partial  suggests as  , v > t O'  that  the  to  satisfy  to  (2.6)  (2.54) of  and  the  density  solutions This  r  t  ) o  satisfies  note  the as  differential  problems.  chapter.  v  form  fundamental  value  r  important  and  The the  >  f  that  same  g  (2.58).  auxiliary and  density  boundary  respectively.  This  follows  (2.55).  i n i t i a l  and  equations functions or  the  i n i t i a l  1  and  equation  Green's  property  w i l l  boundary  developed f,  g,  u  in and  functions be  condition's  studied  this v  for in  can  for  chapter be  regarded  boundarythe  following  30  MONTE C A R L O METHODS  3.  FOR  THE  SOLUTIONS  OF  BOUNDARY-VALUE  PROBLEMS  Introduction  3.1  In density value can  functions  problems  be  i t s e l f  of is  point  is  values point  for  or  u  a l l  and  analog  sense  to  as  of  the  the  true  The  the  time  derivatives.  and  in  and  way  problem  defining  a  new  B  n o w "be  for  and be  is  not  can  the  standard  the  form  be  described  and  v  in  which  solution  functions value walks  in  that  is  convenient since  transformed  to  at  f  and  the  a  walks  increases. in  preceeds  the  analysis,  required  of  an  form  variable.  for  outlined.  solving  the  various  classes  of  on  s t a t i s t i c a l  equations  the  g,  simulated  sign  for  is  determined  equations  minus  the  boundary  is  in  random  differential a  a  expected value  converges of  and  at  originating  The  random  number  methods  be  i n i t i a l  expected  of  boundary-  differential  the  density  the  to  u  walks  desired.  partial  This  of  random  to  of  boundaries.  value  number  as  g,  considered,  of is  f,  a l l  approximation  always  time  on  probability  the  restricts  Methods w i l l  as  large  of  A  actual  partial  expected  The  Problems  no  by  those  probability-  0  governed  to  solution  form  solutions methods  solution  computer. the  form  a  and  between  The  approximation from  v  developed.  i n i t i a l l y  the  An  experimentally an  be  u  problems  terms  v.  and  g,  terminal points  which  in  f,  same  given  the  relationships  problems  obtained  at  written  to  the  In  chapter  w i l l  applied  equations 0  this  problems  by  31 3.2  Solutions  of Boundary-Value  Differential  The section  i s  f o r Parabolic  of the problem  t o be c o n s i d e r e d  Determine  0(r  o  ,t  o  0  is (2)  satisfied  a piecewise is  (3)  C  b  ,t  Q  o f R;  o  7  a bounded  continuous  region  i n i t i a l  R*,  condition'0 (r ) o  )  (3.2)  o  continuous  i s  boundary  satisfied  on t h e  condition boundary  i . e .,  W ^ o W ' The  The time  that  0(r  o  ,t  7  o  ,t 0  ),  with  determine  random  t  defined  walks  (3  and i n i t i a l  one space  variable  ) i s  To (r  boundaries  problem  that f o r t  variable  i s o  and boundary  shown  <  If  a walk  0 (r ,t^) c  with  b  as  0 of Problem  at point  soon as a boundary  terminates i s  position  o n a- b o u n d a r y  recorded, r^,  whereas  the i n i t i a l  i n  i n the figure  (r  of  Figure i s  i s at  reached ( r ^ t ^ )  i f a walk value  i s  0 (r^) q  A at a  ,t 0  terminated  3)  such  0.  the solution are started  '  conditions  a r e shown  0  is  Q  w i t h i n R;. i . e . ,  Q  a piecewise c  3-1.  this  that :  = 0 (r ) ;  Q  0 (r  ) such  within  satisfied (r ,0)  0  typical  i n  follows.  Problem.A  a  Partial  Equations  statement  as  Problems  ).  point  Each  walk  0  or at t  = 0 .  the boundary terminated  is  recorded.  value  at t It  =  0  Figure  Random W a l k s  5-1. of  a  Typical  and  Problem  I n i t i a l with  1  and Space  Boundary Variable.  Conditions  33 The can  expected  be w r i t t e n  f(r ,0  i n terms  0(r ,t ) o  0  Q  = ^  o  b  ( 5  2  ) f ( r  2  of the i n i t i a l  of the probability  r ,t ) and g(r ,t  2  Q  value  r  b  0  , t  0  )  and boundary density  values  functions  as  | r , t ) d r .  , 0  0  o  R  0 (3.4)  where tion. (3.4)  i t has been I t must  ential  be proven  i s actually To  prove  equation  operator  h  assumed  o  and t  o  that  a solution that  + L_  .  , the result  i s  the expected 0(r ,t ) o  Q  value  as given  i s the solu-  by  equation  of Problem A.  0(r >t ) o  o f Problem  ^ o ?  that  o  satisfies  A, operate  Since  the partial  on equation  the operator  differ-  (3.4) w i t h t h e  i s with  respect  to  34  , *o  \  + L r . t o'  0(r  1  ,t 0  ) 0  o  R  0  0J*V,tJ  +  / ^ r  +  L_  ^ ( r  b  , t  b  | r  o  , t  o  ) d r .  b  d t  b  (3.5)  The  right  (2.23)  side  and  of  equation  (2.26)  _ 4 | ( r  0  and  , t  Q  i n i t i a l  )  also A,  prove  satisfies consider  the  Q  o '  by  Kolmogorov  (2.4).  equations  Therefore,  o  and  o  (  3  >  1  )  o  0(r ,t )  i n i t i a l  zero  0(r ,t ) r  that  is  condition  = L  0*0  To  (3.5)  Q  as  defined  boundary  by  equation  conditons  of  (3.4)  Problem  .  35  lim  0(r ,t ) = o  A ^ r ) lim f(? ,0  o  2  r ,t )dr  2  0  Q  t * 0 R  0  +  0 c (  r  v V  l  i  m  g ( r  b' b t  r  t -*o  , t )dr,dt, o' o b b  (3.6)  0  By equations ( 2 . 3 ) and ( 2 . 4 ) ,  lim  0(r ,t ) = o  Q  y 0  o  ( ?  2  ) S  equation ( 3 . 6 ) becomes  (r  2  - r )dr Q  2  = 0 (r ) . o  Q  (3.7)  t ^ O R  Therefore,  0 ( r ,0') =  (3.2)  0 (^ ) Q  O  Also,  lim r  /0 (? )  0(r ,t ) = Q  O  o  lim 'f(r 0 V * o o b  2  2 >  o^ b r  R  ) d r  2  0  r  + o *o  0  b  , t )dr, dt, o' o b b  (3.8)  36  By equations  lim  (2.5)  0(r ,t ) = Q  o  and  t h i s equation becomes  (2.6),  f /0 (r t ) 8 ( r ^ ) § c  v  b  ( V V ^ l  r —*r.  Therefore,  ^b'V  •  =  Since a l l c o n d i t i o n s of Problem A are s a t i s f i e d , 0 ( r ,t ) o o as d e f i n e d by equation  (3*4)  i s a s o l u t i o n of the problem.  The Monte C a r l o s o l u t i o n of Problem A i s obtained approximating  the expected value 0 ( ? >t ) given by  by  equation  (3.4) with the average 0 - ^ ( r » ) of the i n i t i a l and boundary Q  0  values 0^ that are recorded from a set of N random walks o r i g i n a t i n g at ( r , t ) . 0  Q  T h i s average i s N  i=l  The  convergence of 0^(? >"t ) "to 0 ( r , t ) i s considered i n  Section  q  3•5•  Q  Q  Q  Problem  B  Determine  0(r ,t ) o  such  Q  that :  _ 4f v v - ^vv - ^o-v^vv  (1)  \  =  l  V  6*0  +  ^  1  (3.11) is  satisfied  (2) .a p i e c e w i s e fied  within  continuous  Q  a piecewise (r, , t  0  i.e.  Problem equation 2.5).  as  solution  0  (  V V  that  t  v  o  Q  )  = 0  c  ( ?  R  0  +  satis-  condition  on t h e boundary  2  with  ? ,t )dr o  o  v  t  o  problem  density  by analogy  2  boundary  satisfied  0 satisfies  /0 (r )u(r ,O o  i s  (3.12)  Q  )  C of  « i s  t h e same functions  R;  (3.13) t h e same partial u and v  the previous  i s  =  condition  = 0 (r ) ;  of this  the auxiliary  Therefore,  R*,  ,  statement  A except  i n i t i a l  continuous  ) i s  0 ( r The  region  w i t h i n R; i . e . , 0(r ,O)  (3)  a bounded  2  as  that  f o r  differential (Section  problem,  the  38 Prom  (2.54)  definitions  (2.55),  and  equation  (3-14)  r(0)=r  0  0(r  |  ,t )  J0 (r )  =  Q  Q  J  ^exp -  2  d[r(t),t]dt r(t )=r  R  f ( ?  Q  2'° I VV* "; 1  ?  +  /  / 0  *o  expected  approximated N  walks  value  ( c  v V < ^  e  x  <V  =  ?  b  d[r(t), t]dt  p  r(t )=r Q  C  r  The  becomes  o  ,t  value  o'  )dr,dt, b b  0(r ,t ) o  Q  by t h e average  originating  at  at the terminal  (3.15)  given  0^(^ f^ ) o  (? »"t ) 0  point  by equation  Q  Q  where  (3.15)  c a n be  o f "the p r o d u c t  7 j_0j_ f  0^ i s  of the i * *  1  walk  the i n i t i a l a n d "Y^ i s  /  or  °  r  boundary  the value  of  T y  = exp - / t. o  d[r(t),t]dt  (3.16)  39  for T,  the corresponding is  0 f o r walks  minating  walk.  The upper  terminating  at a boundary.  at t  The Monte  limit  = 0,  of integration...  and t ^ f o r walks  Carlo  solution  is  ter-  therefore  N  i=l  Solutions  3.3  of Boundary-Value  Differentjial  The arise  and  boundary-value  The  Problem  problems  of steady-state  equations  the Poisson  f o r these  statement  L_  0(r  problems  Typical  discussed  partial  are the Laplace  ) = 0. i s  0(r  C i s  as  equation  ) such  satisfied  follows.  that: within  a  bounded  o  (3.18)  region (2)  C, D and E t o be  fields.  of Problem  Determine  P  P a r t i a l  equation.'  C (1)  f o r E l l i p t i c  Equations  i n the study  differential  Problems  RJ  a piecewise is  continuous  satisfied  on t h e boundary  . 0(r ) b  The  boundary  subscript  t  = 0 (r ) c  is  b  .  deleted  condition  C o f R„  c  b  i.e-.,  .  from  0 (? )  (.3,19),  operator  L_  0* 0 to  indicate  that  L_ r_  i s ^.independent  of  time.,  40  The solution  of  conditions expected random  solution  of  this  problem  problem  of  type  A.  a  are  value  walks  of  of  values  originating  value  is  written  g ( ?  b  r ,0)  b  , t  Since  independent boundary  in  at  terms  r  of  t  ,  the at  at  Q  is  the L  steady-state and  solution the  time  the  at  terminal  t  =  probability  0.  r  is  Q  the  points  The  density  boundary  of  expected  function  as  Q  oo 0(? )  =  o  J ^ 0  0  Prom  equation  follows solution  that of  c  ( ?  (2.26) 0(r  }  ) g ( r  )  and  as  Problem  o  b  , t  b  b  |  r ,0)dr dt o  (3.20)  b  C  Equation  0  ( r  boundary  given  equation  (2.6)  (3.20)  is  for  g,  indeed  i t a  C.  (3.20)  = j f 0  by  condition  c  <  5  b  can  )  G  <  also  b l  5  ?  o  be  )  d  r  written  as  (3.21)  b  C where  oo g ( ?  0  b  , t  b  r  r t >  0)dt  b  3.22)  41  i  is  the  at  time  t  C.  As  for  tion of  probability =  Q  w i l l  or  problems,  (3.21)  terminal  that  a  eventually  previous  (3.20)  the  0  density  can  boundary  random  terminate the  be  walk  starting  in  b  expected  approximated  values  on  value by  That  0^.  dr  the  given  the  at  r  Q  boundary by  equa-  0jj(? )  average  Q  is,  IT  i  is  the  Monte  Problem  Carlo  Determine L_  -  0(? ) Q  0(r )  such  Q  d(r )0(r )  =  o  Q  that:  0  within  a  (3.24)  o  r  bounded (2)  1  solution.  D (1)  =  a  region  piecewise  0 (? ) c  is  b  R\  continuous  satisfied  boundary  on  the  condition  boundary  C  of  R;  i . e . ,  0(r )  =  b  Operator  L_ ?  time  t  , but  a  solution  problem  solution  of  type  c  .  b  (3-25)  coefficient d(r  ) are  independent  of  o  otherwise  The of  and  0 (r )  are of  B.  as  defined  by  (2.24)  this  problem  is  the  Hence,  by  analogy  and  (2.56).  steady-state  with  Problem  C,  solution the  is  00 0(r ) Q  =  J  T/0 (? )v(r ,t  0  c  b  b  b  b  |r ,0)dr dt Q  b  b  .  (3.26)  42  For t  a =  large 0,the  number  N  expected  of  random  value  walks can  0(? ) Q  starting be  from  r  approximated  at  Q  time  by  N  )  0„(?) = 1 o  7A  (5.27)  i=l  where  is  y^  the  value  of  y  exp  -  -  /  d[r(t)]dt  V  for of  3.4  the the  i * * i  t  1  Solutions  be  and  of  the  boundary  Nonhomogeneous  solutions  constructed  independent dependent  is  0^  value  at  the  terminal  point  walk.  h  The can  walk  of  from  boundary-value  typical  example  for  Problem  E  follows.  Problem  E  is  nonhomogeneous  the  boundary-value  as  solutions problem  problem.  problems  Determine (1)  L  0(r) r  =  Boundary-Value  -  and  type  0(r  )  )  a  boundary-value a  homogeneous  homogeneous  Poisson's  of  H(r  0  of  is  E.  such  Problems  The  problems time-  time-  equation statement  is  a of  that:  satisfied  within  a (3.28)  0  o bounded  region  continuous (2)  a  piecewise  R,  where  H(r  )  is  a  piecewise  function*,. continuous  boundary  condition  (r, )  0 C  D  43 i s s a t i s f i e d on.the boundary C o f R; i . e . , 0(r ) = 0 ( r ) b  c  (3.29)  .  b  To determine the s o l u t i o n o f Problem E, consider the time-independent boundary-value problem o f type C: (1)  L_ 0 ( r ) = 0 w i t h i n R,  (3-30)  1  r  o  0 (? )  (2) 0 ( r ) = x  c  b  .(3.31)  on the boundary C o f R •.  b  and the time-dependent boundary-value problem o f type A: (!)  _ 4O^o  =  -  L  r  w  i  t  h  i  n  R  i  ( 5  '  3 2 )  o  (2) 0 ( r , O ) = H ( r )  (3.33)  (3) 0 ( r , t ) = 0  (3.34)  2  Q  2  b  Q  .  Q  The s o l u t i o n o f Problem E i s g i v e n by 0  0(r ) Q  = 0 ^ )  J  +  0 (r ,t )dt 2  Q  o  (3.35)  .  o  -OO Proof  Operate on 0(r ) with L_ r  and use ( 3 . 3 0 ) and (3.32) .  o  0 L_ 0 ( r ) = o  J  o  ^  0  ( 2  V V  d  t  o  (  "  6  )  - OO = 0 (r ,-oO) - 0 (r ,O) 2  Q  2  Q  .  (3.37)  44 Since  the boundary-values  Therefore,  r  (3.35),  a r e 0, 0 (r ,-oO) = 0. 2  2  Q  (3.33),  by  L_  Prom  f o r 0  f o r r  Q  0 ( r ) = - H(5 ).  (3.28)  .  o  =  r  v  0  0(? ) b  = 0 (r ) 1  +  b  y 0  2  ( r  b  , t  ) d t  o  .  o  (3.38)  - oo Therefore,  (3-31)  by conditions  0(r )  = 0 (r )  b  The  solution  Problem  E,  determining  some  ) given  and i s  The  and  0(r  Carlo  numerical  problems  satisfies  a l l conditions  of  solution.  solution  integrating  of Problem t  y  "  02^o'^o^  t  h  e  m  e  w i _ t : t l  '  t  t  l  E i s o  d  s  o  respect  f  obtained  by  Problems  A  to t  Q  by  technique.  0(? )  L_  solved  (3.35) a  (3.29)  .  b  0-j_(r ) a n d 02^o'^o^  Nonhomogeneous  are  by  therefore  Monte  C and then  r  c  (3.34),  and  Q  -  equations  d(r )0(r ) o  Q  = -  o f the form  H ( r  o  (3.39)  )  o i n t h e same  o f type  manner  B a n d D.  as Problem  E by  considering  45 Estimates  3.5-  o f t h e Number  o f Random Walks  f o r Monte  Carlo  Solutions  Convergence  3.5A  Monte equations  o f Monte  Carlo  are given  Carlo  solutions  Solutions.  o f homogeneous  p a r t i a l d i f f e r e n t i a l  by N  0, i=l where  f o r problems  Let  the recorded  the  random  measure  o f type  values  variable  t r i a l s ,  the Central  i s given  distributed  Limit  f o r a given  a s ,7=W. UN^  by  a factor  random  Q  )  ±  be denoted  by  1  Q  of 0jj(? »t ) o  ±  o  i s  obtained  a on  T  Theorem, It  0  0]^(? »' ) t  o  o  (3.40)  w i l l  be n e a r l y  therefore- follows  that  normally  the probability  .05 t h a t  To reduce  the standard  o f 2, f o r^example,  walks.  o  'Y 0 '  by  t h e s t a t i s t i c a l convergence  is  ( r , t  by  of 0^(r ,t^), which  of values  >  Hence,  i s replaced  ±  0, (r , t ) = 1 v a r  f o r N large.  approximately  0  The v a r i a n c e  0.  var  is  0^,  of the fluctuations  different  From  B a n d D,  21  var. 0 N •  (3.41)  o f 0]\j-( >t ) r  o  deviation  i t Is  o  to  0(r ,t ) o o' o7  n  , / v a r 0T, (r , t ).' V N o' o  necessary  T v  to simulate  4N  46  3*5B  Number  of. Random  Walks  for.Homogeneous  P a r t i a l Differential  Equations  An required If  an  with  estimate  f o r a given  error  o f t h e number tolerable  0 (r ,t ) N  probability  Q  o  ;05  i s  ?  N >  is  a  var  sufficient 0  number  -  gives  a lower  an •estimate  error o  greater  Q  tolerable, then  f  Y  a  f d r W : canobe  that  from  than  €  ,  as  occurring  inequality  (3.41)  (3.42)  walks.  that  E o r some  f o r these  f o r N.  When  cases  special  v a r 0 cannot  obtained 'by"noting-  of  0  max  i s  t h e maximum  t h e r e q u i r e d number  value  o f random  40  Por that  example,  be c a l c u l a t e d ,  that  whereas  i f  (3.43)  of 0  0  walks  A pessimistic i s  €  then =  f o r  .01, then  €  estimate  therefore  2  i f the p a r t i a l d i f f e r e n t i a l equation  = 1,  0  cases,  condition  var 0 < 0 ^ where  are follows.  g A.  o f random  bound  walks  can be determined  0(r yt )  can be c a l c u l a t e d , , so  (3.42)  N o f random  =  .05, N should  N should  i s  scaled  be g r e a t e r  be g r e a t e r  than  than  40,000,  so 1,600?  47 3.5C  Number o f Random Walks f o r Nonhomogeneous Differential The  equations  Partial  Equations.  s o l u t i o n of nonhomogeneous p a r t i a l  differential  of type E i s g i v e n by  0(r ) = 0 (r ) + Q  1  0 (r ,t )dt  /  Q  2  o  Q  .(3.35)  o  -oo Por a Monte C a r l o s o l u t i o n , 0 ^ ( r ) i s approximated by Q  0J_-JJ(^ ') • O  and the i n t e g r a l i s approximated by M  .  I =  )  i-1  ^  ^  (  ^  .  i  A  t  (3.45)  J  where the Ct ^ depend upon the numerical i n t e g r a t i o n t h a t i s used. s u b s c r i p t L i n d i c a t e s that each value o f 0 ( r , t •) i s t o ber  The  o  2  r  obtained u s i n g L random walks.  O  O  The s e l e c t i o n o f numbers N and  L w i l l now be c o n s i d e r e d . L e t the Monte C a r l o approximation t o 0 ( r ) be denoted by 0 u j ( ) > then r  J  o  o  M  v a r  0  NL  ( r  o  }  =  v  a  r  0  IN  ( r  o  }  V  a  i  v  a  r  0  2L  (  V  i  A  t  o  }  i=l  (3.46)  48 If  v a r0~  x  ( r ,j A t ) i s t h e maximum  2L 1=1,  o  . . .  value  o f v a r 0 {v  ,i>At  nr  o  ,oi  ^2L o  . M , a n d i f Ct^ a r e c h o s e n  ).  by thetrapezoidal  rule;  i . e . ,  A t i =  a  a  = A t  ±  =~2 '  M  a  '  a  i  o  = 2,3  .  .  ^.47)  .(M-l)  then  0  var  N L  0 (? )  (? ) < v a r Q  IN  + v a r 0  Q  2  L  (r  Q  , jA t  ) ( A t ) ' ( M - §) 2  Q  0  (3.48) 0-^ a n d 0^ ^  Let  02j (r , j A t j  Q  Q  t h e random  e  ) a r e formed;  var  0 „(r  var  0  ) -  T  v  a  variables  from which  0jjj( ) r  r  0  1  <. c max  •  0  2  0  c  o  o  =  v  a  2  r 0  —  ^ andH „ a r e t h e maximum max c max  function It  r T  0 ( -^) T  a  dfunction H(r ),  n  O  therefore  Q  follows  The  a  r  numbers  side where  of this  0  N L  (  r  o  }  2  ^  H  d  H  max  L"  absolute  (3.49)  (3-50)  •  values  o f t h e boundary "  respectively,  f o rt h e problem.  +  2  _ ^ - (  W a n d :L c a nhe chosen expression  Q i s thetotal  n  that  0  v  a  then  (r,,,j At.)  2L  o  subject  number  A t  0  )  2  ( M  t o minimize  - § )  the right-hand  to. t h e c o n s t r a i n t  o f random  walks  (3.51)  that  N+ML = Q , a r e taken.to  49 obtain  a value  of  0(r).  The  minimization  /M  gives  !'/H  -  (3.52)  This  results,  gave  I  when  =  133  for  example,  the  time  integral  I  value  0  of  was l N  used  N  =  Q  1,000  required  only  (r ).  with  about  the  and to  Poisson  M =  19.  obtain  twice  the  equation Thus,  a Monte time  at  in  least  Carlo  required  Section for  value to  of  obtain  5.4, this the a  50 4.  COMPUTER  M E C H A N I Z A T I O N OP MONTE PARTIAL  4.1  Monte  upon  Carlo  the  system  following  operations.  with for the  The  equations  solutions  computing  1.  DIFFERENTIAL  METHODS  FOR  SOLVING ,  EQUATIONS  Introduction  Based the  CARLO  for  of  given  partial  in  Chapters  differential  implementing the methods must  stochastic differential  equations  of  2 and  for  3  equations, perform  Section  a  the  2.4, namely  ||  + A (x,y,z,t)  = B (x,y,z,t)N (t)  (2.27)  |£  + A (x,y,z,t)  =  B (x,y,z,t)N (t)  (2.28)  | |  + A (x,y,z,t)  = B (x,y,z,t)N (t)  (2.29)  i n i t i a l partial  1  1  2  3  2  2  5  conditions r(t differential  1  ) =  3  r  Q  equations  must  he  simulated.  that  contain 0  In  addition,  itself,  functional  T  J  =  exp  -  d[r(t),t]dt  *o must  he  generated.  (3.16)  51  2. t  The s t o c h a s t i c =  0  This 3. of  or whenever requires  The  a  The  4.  must  the boundary  method  i n i t i a l  t h e random  process  or  walks  be  terminated  C of  f o r storing  boundary must  region  R  is  0^  at  at  time  reached.  and d e t e c t i n g  values  be  a  either  boundaries.  the terminal  points  generated.  average  N  ^  i=l  or N  i=l •  for  U very  which  a  large  solution  must is  5.  The s t o c h a s t i c  for  each  ment  of  (? >"fc )  after  In 1,  this  2 and 3 are  4 and 5 are be  process  walk.  0  carried  must  at  be  Automatic each  chapter  carried  obtained  each  point  (  r 0  >"t )  f o r  0  desired.  random 0  be  set  a  initiated,  readout  of  o f N random  computing  system  out by an analog  terminated and  0^(^ '^ ) o  walks  out by an associated  i s  d i g i t a l  n  d  also  i n which  computer  a  o  and  reset  adjustdesirable.  operations operations  computer  w i l l  described. The  Electronics Logistics  experimental Associates  Research  studies  Inc.  ALWAC  PACE  III-E  were  carried  231 R-V  d i g i t a l  out  analog  computer.  on  an  computer The  and  design  a  and  construction  computers  of  interface  was a n i n t e g r a l  equipment  part  of  f o r hydridizing  the project.  t h e two  Details  of  this  Q aspect  4*2  of  t h e work  Simulation  4»2A  Analog  is  of  simulated  defined  of  f i r s t  and  nonautonomous.  equations  heat of  order,  the noise  stochastic shown  this and  V7 0 2  computer  are  of  a  for  generation  single  diagram  (2.27)  form.  0=0,  involve  of  The and the  integration  simply  variable.  with  whenever  A2 s h o w n  variable  x»  Special  o f a more  i n i t s most  diode  general  function  closed-form  techniques  4-1  used  track-and-hold  i n  mathematical functions  are  form.  form  generators  o r whenever t h e 1"5  i s  the  indicated  general  i n Figure This  f o r simulating  generation  f o r the functions  functions  Integrator t h e random  only  nonlinear  differential  y  f  equations  equations  autonomous  equation  The f u n c t i o n  multipliers  a r e known  hold"  linear  block  equation  4-1*  expressions  of  the stochastic  (2.29)  N^(t)*  can be r e a l i z e d  quarter-square  only  however,  differential  are coupled,  sto-  to  (2.27)  differential  = ~^+» f o r example,  analog  i n Figure  I.  Computer  the general  equations  These  they  partial  f o r Laplace's  differential  figure  computer.  independent,  terms  An  is  to  on an Analog  methods,  by differential  P o r many  equations  equation,  Carlo  and i n general  importance*  reduce  stochastic  Monte  on t h e analog  are  Process  and i n Appendix  Setup  the proposed  process  engineering  i n the literature  the Stochastic  Computer  In chastic  appear  to  required  "track  feature  i s  and used  53  Figure  Block  4-1.  Diagram  for  Simulation  Differential  to  hold  the at  the  terminal value  i n i t i a l a  or  constant  computer.  boundary value  The  of  while  0^  mode-control  0^ or  random  ( 7^0^)  synchronize  the  compute  i n i t i a l - c o n d i t i o n modes  Al.  The  and  generation  comparators For  and  the  of  these  d i g i t a l  problems  in  c  modes  ^ and of  and  from  r,  (Section  read  by  the  l o g i c a l  integrator  respectively  computer the  s  r,  its  mode-control  which  Stochastic  vector  generated  signal  track-and-hold  a  Equation  the  value  of  is  signals  discussed  functional  7  /  4.4)  d i g i t a l  inverse with  A2  of  consequently  c  the  integrator  from in must  electronic  Section be  4.3.  generated,  54 the  following  implicit  method  is  used.  Prom  equation  (3-16),  ="7d[r(t),t] (4.1) and  0  An  analog  computer  block  in  Pigure  4-2.  'X  is  that  the  A3.  1  7(t )  Note  diagram  available  mode  of  for at  these  the  integrator  equations  output A3  is  of  also  is  shown  integrator c o n t r o l l e d by  r(t) d[r(t),t]  7(tJ= l  t  +  7d[r(t),  Pigure  4-2.  Block  Diagram  for  Generation  of  t]  c.  55 4.2B.  Noise  Source  The theory are  physically  derived If  uncorrelated  (Section  Gaussian  the  t i e s  Requirements  2.4)  must  gas  noise of  he  but  tube's,  analog  errors  resulting  analog  computer  Noise with  is  and  limited  larger  computer,  from  finite  not  the  noise  then  noise  with  number than  i t  specified  can  are  sources.  that  CL)^ c a n  bandwidth  be  the  approximately  generators"*"  the  in  sources  bandwidth  bandwidths noise  by  sources  pseudo-random  b a n d w i d t h CO ^  the  white  approximated  realizable'.  distributions from  Gaussian  assumed  etc.  4  capabili-  that  caused  by  In  case  the  be  any  the of  a  c PACE  231  R-V  analog  radians/sec.  to  be  computer.  The  the  computer  analog In  of  the  computer, above  effect  noise  of  is  addition  solving  time  hours.  Without  special  sources To  tions  that  f a i l  were  in  larger  than  10  of  the  capabilities  some  in  many  this  study,  within  the  the  s t a t i s t i c s  complete be  several  commercially  bandwidth  •  C.  could  requirement.  noise-source  encountered  during  problems  precautions, this  4.2  requirements,  stationary  for  to.meet  Section  bandwidth  be  which  overcome  bandwidth  be  limited-bandwidth amplifier  the  must  problem  noise  a  should  considered  to  sources  the  60^  available  4  and the  s t a b i l i t y  l i m i t a -  multichannel  noise  Q source  described  produces -  5.0  volts,  bandwidth Gaussian by  stable  of  in  Appendix  was  developed.  discrete-interval binary  and  has  the  analog  distributed  low-pass  II  f i l t e r i n g  an  adjustable computing  noise the  can  be  binary  noise  bandwidth elements.  This with  that  noise  source  levels  can  exceed  the  Approximately  obtained from 14 noise. I t was  this found  noise in  source the  56 experimental be  obtained  the  step  to  the  in  r(t)  made  study by  size  size  of  of  noise.  One,  precisely the  and  the  4.2C.  obtain into  to  the  the  grator  by  of  i f  scale  walks  at  CO  is  a  extremely  small  u n t i l  be  so  could  good  the  the  use  results,  compared  the  that  the  from  change assumptions  the  noise  Two,  the  discrete  the  step R.  Bandwidths  on  stochastic  size  on is  Solution  infinite-bandwidth noise etc.)  the an  were  due  in  of  to  have  known nature  d i f f e r e n t i a l oscilloscope, small  Times  and i t  analog would  4-1  the  Some  bandwidths  a l l  computing  are  ideal  transfer  comput-  be to  insight is elements  except  function  inte-  15  (4.2)  -  the  are  extremely  rate..  finite  Assume  Figure  an  binary  d i f f e r e n t i a l equation  a r b i t r a r i l y high  integrator A l  =  realizable,  stochastic  of  of  monitored  region  shown  measure  condition,  result  f o l l o w i n g , means.  T(s)  where  For  small,  scaling can  limitations  source  Let  is  solutions  directly.  this  easily.  in  the  Finite  time  noise A l .  checked  (amplifiers  the  At  response  size  time-scaling  obtained  Under  advantages  adjusted  of  random  be  Carlo  approximated.  helpful  theory,  elements  possible  are  be  is  the  Effect  time  noise  must  R.  Monte  s t a t i s t i c a l properties  can  scaling  In  and  the  since  to  response  small  good  binary  region  2.4  response  compared  ing  a  the  inherent  and  equations  the  the  Section Some  of  using  during  in  however.that  bandwidth  of  the  a m p l i f i e r , and  Q  57 is  a  time-scaling  factor  computer v a r i a b l e  (*§-)  + fr"  T  where  =  CCt  x  satisfies  the  computer  variable  of  the  response  to  to  choosing  the  with  made  The  of  small.  of  for  whenever are  computer  equations f o r section.  terminating r  novel  generators  in  that  are  the In  the  reaches  (2.27),  but  reduce  that  must  values  equation  deviate  checking  at  from  several  c a n be  of  the  the  Hence,  to  experimentally.  experimental  results  statistics  negligible.  compromise  determined  By  good  small,  statistics  the  equation be  equation;  solution be  made  This  is  solution  solutions  points,  the  larg-  ascertained.  Boundaries  An a n a l o g  previous  be  Cl u n t i l  CL f o r  Detection  ential  large.  differential Ct  t e r m must kept  F o r the  approximate  differential  derivative  CL c a n b e s t  partial  value  4.3  be  closely  the  (4.3)  1  variable.  CL s h o u l d b e  increasing  obtained est  error  to  stochastic  second  GL s h o u l d  done.by of  the  minimize  time in  of  x  differential  1  scaled-time  of  effect  following  assumptions,  = B (x,y,z, T)N (T)  1  the  Under these  the  A (x,y,z,T)  +  is  (gain).  simulation of  random v e c t o r  this  section,  stochastic a  boundary  only  C of  Hence,  was  methods  process  electronic  required.  r  the  a  at  a  stochastic  discussed will given  r e g i o n R.  comparators special  be  in  differthe  outlined  time  t  = 0  The methods and diode  purpose  or given  function  equipment  such  4 as,an  oscilloscope  mask  and a  phototube  detector  is  not  required.  58  Upon control in  the  signal  the  detection  c must  be  i n i t i a l - c o n d i t i o n mode. are  fiers  in  the  hold  mode.  In  on C,  or  terminal  point  r(0)  i  controlled  or  after the  is the  from  the  is to  held  the  and  a  from  a  the  new  signals  mode-control comparators  d i g i t a l  f l i p - f l o p  c  the  computer. is  shown  places  c  a  is  is  are  reversed  can  be  computer  or  from  scheme  4-3 •  -3<—* c  -=s—•  c  d i g i t a l  computer  Triggering  of  by  triggered  Control  4-5.  value  Immediately  Tip-Flop  Figure  r^  terminal  Mode-  From  ampli-  conveniently  JT  From t=0 comparator  ampli-  point  detection OR  integrators  these  boundary-  comparators  mode-  initiated.  triggering  Figure  a l l  computer.  that  analog The  in  c  place  while  walk  and  the  =0,  boundary  computer,  f l i p - f l o p  on  c  fixed  random  t  track-and-hold  the  d i g i t a l  at  to  of  state,  computer,  mode-control  the  reversal  this  or  order  Since  d i g i t a l  mode-control  From  c,  in  the  electronic  pulse  boundary  to  The generated  by  transferred  transfer  d i g i t a l  from  a  reversed  fiers  0  of  Mode-Control  Flip-Flop  for  a the  59 A pulse at input ( l ) terminates a s i m u l a t i o n of the s t o c h a s t i c d i f f e r e n t i a l equations, and a pulse at input s i m u l a t i o n of the equations.  (2) i n i t i a t e s a new  With t h i s scheme, the problem of  d e t e c t i n g boundaries and time t = 0 i s reduced to the problem of e n e r g i z i n g e l e c t r o n i c 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 modecontrol  F i g u r e 4-4.-  flip-flop  D e t e c t i o n of Termination Time t = 0  The use of an e l e c t r o n i c comparator to detect time t = 0 f o r random walks s t a r t i n g at time t A signal c  Q  i s shown i n F i g u r e  i s obtained from the comparator when t = 0 .  4-4. Note  that c c o n t r o l s the mode of the i n t e g r a t o r t h a t i s shown i n t h i s figure.  Hence, t h i s i n t e g r a t o r i s placed i n the i n i t i a l - c o n d i t i o n  mode a t t = 0 or when a boundary i s reached, and i n the compute mode at t = t . o  60 4.3A  D e t e c t i o n of Boundaries  f o r Problems with One  Space  Variable Por problems with one space v a r i a b l e x, and at  p o i n t s x^^ and x^g-  "t  n e  boundaries  boundary d e t e c t i o n comparators are  energized by comparing the random v o l t a g e x with v o l t a g e s and  x, . 9  (see Pigure  x^^  4-5).  from analog c i r c u i t simulating the s t o c h a s t i c d i f f e r e n t i a l equations  to of  OR  gate  mode-control  flip-flop  xb l  F i g u r e 4-5.  v  b2  Boundary D e t e c t i o n f o r Problems with One Variable.  When x reaches x ^  or X - ^ J "the mode-control  gered by e i t h e r comparator output c^ or  c^.  flip-flop  Space  is trig  r  61 4.3B  D e t e c t i o n of Boundaries  f o r Problems with Two  Space  Variables Consider f i r s t  the simple two-dimensional  with boundary C as shown i n F i g u r e  region R  4-6.  Y  F i g u r e 4-6•  Two-Dimensional Region  The boundary of t h i s r e g i o n i s composed of two C-^ = C-^X)  curves  and Cg = C^CX), each of which i s a s i n g l e - v a l u e d  f u n c t i o n of X.  A t y p i c a l random walk with instantaneous compon-  ents (x,y) i s a l s o shown i n the f i g u r e . It i s c l e a r from F i g u r e 4-6 a boundary whenever  that a random walk reaches  62  or  This  boundary  computer  by  and  c (x)  y  =  c,(x)  block  diagram  l  detection  Cg(x)  Figure  =  comparing  C^(x)  in  y  that of  criterion  the are  this  (4.4)  random set  simple  on  is  implemented  variable diode  boundary  y  with  function  on  the  analog  functions  generators.  detection  scheme  A  is  shown  4-7.  2  To  OR  gate  of  mode-control f l i p - f l o p  Figure  Now dividing  line  single-valued This  type  considered special  of  4-7.  Two-Dimensional  consider D  can  be  more  region  of  a  general  constructed  functions w i l l  previously  case  a  in  simple  of be  Boundary  such  U measured called  which  a  U was  region.  region  Detection  R  in  that.C^  along simple  D,  which and (see  region.  coincident  with  Cg  a are  Figure The X,is  4-8),  region a  63 Y  A  F i g u r e 4-,8.  Coordinate Transformation used f o r Boundary-  D e t e c t i o n of Two-Dimensional Simple  The boundaries  Regions.  of an a r b i t r a r y simple r e g i o n are  detected by t r a n s f o r m i n g the random v a r i a b l e s x and y to  new  v a r i a b l e s u and v f o r which the boundary d e t e c t i o n equations v =  C (u) 1  (4.5) and  can be used.  v =  The new  C (u) 2  v a r i a b l e s u and v  are obtained from x  64 and  y  by  the  u  transformation  =  x  c o s fj  -  y  sinyCj?  -  a  (4.6) v  where to x  =  x  constants  detect and  y,  scheme  this  of  cannot  be  each  the  AND  a  gate, R^  case, than  the that  boundary  of  a  R  signal  b  defined  used  region  in  Figure  variables with  .  is  the  u  and  Hence,  4-8. v  boundary  region  is  region  can  above.  C defined  from  be  instead  of  detection,  the  (X  + b  a )  the  expression.  d e t e c t e d by  .  (Y  the  dividing or  method  a l l  variable  given.  region the  line  more  random  By  with  an  simple  boundaries  for  an  + d  c )  When even  example,  equation  2  two  simple  leaves  a  R,  Consider,  by  of the  each r  which  into  exit  problems  mathematical  boundaries  the  o b t a i n e d when the  in  d e t e c t e d by  obtained  is  R  divided  and  engineering  simple  given  are  are  •  2  hence  many  j2  -  boundary,  the  signals  and  In by  R-^,  simple  combining  cribed  and  c o s ^  complicated regions  fouhd,  r  y  4-7.  more  regions  regions  b  type  Figure  simple from  a,  +  respectively,  For D  siny$  2  _  n  are  this  simpler an  des-  is  the  method  e l l i p t i c a l  65 The  function  f(x, )  =  y  is  generated  y,  and  compared  at  the  boundary.  are  by  with  required  meters  a,  b,  c  Whenever  Hence, detect d  only  this  of  two  type  the  4-9-  This  simple  region with  a  was the  horizontal  is  example  vertical  axis  visible)  for  distributed  two  regions.  A  dot  each  random  walk.  on  was  from  by  this a  a  the  in  is  comparator the  be a  and  para-  varied  simply  solution can  is be  5.3). d e t e c t i o n methods  region  exposing  by  random  variable were  between the  one  parameters,  photograph  photograph  at  can  x  walk  Since  which  the  circular  random  produced  and  region  of  driven  circle  random  boundary.  continuously axis  driven  of  boundary  of  variables  the  1  problems  the  photograph by  =  of.Section  evident  taken  random  multipliers  function  v e r s a t i l i t y of  proposed  the  e l l i p t i c a l  as  (see  2  f(x,y)  point,  Figure  uniformly  from  some  The  (not  c  voltage,  easily.  walks  (y % ) d^  analog  handled  the  +  2  an  at  display  a  multipliers  and  desired  been  % > b  x  toll-  to  adjusting  have  <  the  x.  shown within an  in a  oscilloscope  variable The  started  that  y  and  random at  boundaries  termination^,point  points of of  the  66  *  Figure  Photograph  4-9•  Detection  4.3C  of  Illustrating  Boundaries  for  a  Detected  Problems  Boundary  with  Three  Space  in  Section  4.3B  by  using  a  dividing  and  below  the. p l a n e  the  plane.  "Variables  The be  generalized  plane is  a  such  that  in  not  the the  of  boundary function  simple two  dividing case,  method  would  of  above  position  mathematical  variables  plane,  however, have  regions  surface  this  that  special  to  be  used.  on  expressions define  method  13 techniques  discussed  three-dimensional  the  which  functions  below is  to  single-valued  regions the  dividing-line  is  purpose  the  easy  are  For known  surface to  apply.  function  can  for  above If  and this  generation  67 The type  of  boundaries  symmetry  described  for  the  region  cubic  comparators  in  be  with  detected  two  the  a  5-6  manner  problems.  Generation  At is  In  is  regions.  a  single  addition,  manner  for  as  combining  detected by  that  expression,  same  ing  of  the  by  this  (Figure  the  some  methods  example,  using  3 pairs  pair  is  boundaries  example  with  For  used  that  corresponding  of  for  can  ellipsoids,  be  can  boundaries  are  of  r.  on  in  \.  out  i n i t i a l  of  x,  of  a  y  and  single  dividing  boundary  time  t  =  or  0  a  is  the  methods  have  discussed.  the x,  the  y,  and  analog with  with  or  values  so  z  r  function  is  are  that are  used  The  can  are be  as  expressed  detecting  conveniently  these  above  known  the  generated  be whenever  simple as  a  functions  function in  which  boundaries, a  values  components  can  problems  as  of  boundary  multipliers  two-dimensional for  trigger-  constant  and  from  prescribed  values  The  a  amplifiers  as  i n i t i a l  and  from  terminal values  available  generators  they  the  generators  generation  For  been  boundary  triggered  track-and-hold  computer.  whenever  D  of  boundary  variable.  the  mode  function  and/or  line  that  places  hold  function  z  terminal  Values  f l i p - f l o p  generated  carried  the  Boundary  mode-control  in  The  the  instant  and  the  components  0^  I n i t i a l  f l i p - f l o p  4-1)  voltages  of  the  reached,  comparator  a  Section same  the  d e t e c t e d by  two-dimensional  single  in  be  regions  dimensions.  4-4  C  of  three-dimensional  often  one-and  one-dimensional defined  can  of  function  the of  68 the  variable  u defined  When t h e analog the  computer  d i g i t a l  along  values  the  0^  cannot  techniques,they  computer.  dividing  can  When t h e  generation,the  components  position  vector  r^  the  computer  determine value  the  must  d i g i t a l  scanned,  be  However,  is  read  more  with  terminal  are  or  by  the  are  x,  value  of  d i g i t a l  consuming  d i g i t a l  components  y  computer  is  and  the  and  z  of  table  method  computer  and  z  analog i t  of  is  the  used  more  to  than  with  slow  d i g i t a l  generation.  to  walk  one  additional  function  th  within  used,  possible i  for  terminal  since  procedure  by  within  stored  is  Since  than  conveniently  be;generated  0^.  equipment  x,  y  other  required, this  time  fast  always  read; then a  some  corresponding  operations  equipment  the  is  or  generated  d i g i t a l  function  r(0)  be  line.  store  with  a S "fc  track-and-hold walk. are  Thus,  i f  the  s u f f i c i e n t l y  d i g i t a l while  time  is  For tion  within  computer to  a  patching  }  a  computer  procedure  wasted  between  problems the  analog  gating  is  them  x,  y  the  i  and  and th  z  efficient  can.be  the in  the  (i  d i g i t a l  walk  simulating  very  during  equipment  for  is  can (i  that  l )  s  l)  computer  read  be  +  +  and  the  carried  out  ^  random  essentially  no  walks. in  which  voltages  computer  arrangement  single  analog-to-  an  amplifier  EAI  read  values  generation  analog  This  and  conversion  fast,the  function  the  walk.  ing  arrangement  must  is  often  d i g i t a l equipped  an  electronic  SPDT  switch  that  be  realized.  This  switch  is  is  be  from  more  read  by  with  By  in  for  this  Appendix  one  loca-  d i g i t a l  for  electronic  suitable  described  the  necessary  converter.  than  multiplex-  suitably switching purpose III.  9  can  69 4.5  Operations  The walk The  are  terminal  generated  main  average  P e r f o r m e d . . b y ...the D i g i t a l  function of  the  values  by of  the the  0.  (or  Y.0.)  techniques d i g i t a l  terminal values  Computer  that  computer  and  to  for  each  random  have  been  described.  is  to  control  compute  the  the  analog  comi  puter  during  the  The a  solution  value  complete  average °  is  computer.  A  completed  is  t a l l y kept  a  of  the  by  is  typed  method,  is  necessary  to  -  the The  are  carried  and  by  a  computer These  out  to  the  logic  used  for  the  analog  the  in  ,t ) o o  stored  within  of  random  walks  the  A  d i g i t a l  computer,  at  operation  extremely  large  because  dynamic  have  been  N walks  least for  range  each  d i g i t a l  that  after  this  which  sequence,  sum  or  at  a  N  is  the  d i g i t a l  large required  precisely. functions  logic  the  mode-control  lines and  control  multiplexing,  performed  (flags)  logic  and  other  the  of  d i g i t a l  f l i p - f l o p  running  unit  electronic  by  the  (Section  from  the  analog  switches  and  switching  computer 4-3)  d i g i t a l  computer.  relays  that' >  operations  on  computer.  The  analog  adding,  (r  computer, and  memory  lines  number  by  point  d i g i t a l  through of  p a r t i a l  for  control  group  are  Carlo  sum  formed  each  time.  the  out.  40,000)^an  obtain  is  solving  for  T  to  average  (1,000  0-. (r , t ) H o o  desired  ( o r i "Y^fi^)  0^  problem  methods  complete is  computer  shown are  hybrid in  Pigure  converted  analog-to-digital  system  to  converter  for  4-10.  implementing Voltage  binary-coded of  the  EAI  the  levels  decimal  d i g i t a l  Monte  on form  the by  voltmeter.  A-D Converter  Interface  (Digital Voltmeter)  hold logic  lines  Analog  Digital  Mode-  Computer  Computer  Control Flip-Flop  Stepping Motors Driving Potentiometers  o Figure  4-10.  Hybrid  Computer  System  The  interface,  the  binary-coded  the  input  for  the  the  under  register  is  of  of  the  data  initiated,  mode-control  described  control  in  from  f l i p - f l o p .  prescribed  rate  of  100 in  of  accordance  rather  slow,  Monte  but  Carlo  for  each  of  random  set  R  The the  detailed  program flow for  used  diagram, the  flow for  given  Appendix  in the a  this  analog  class  a  the  the  d i g i t a l  signal  from  interface  is  is  As  sent the  achieved  by  driving  explained  in  Appendix  to  a  stepping  motor  of  pulses  transmitted.  conversion  scheme  is  number  digital-to-analog of  the  starting  I,  at  voltage  of  the  of  complete  (Figure Carlo  a  to  adequate  This for  conversion, is  points  4-11)  system of  a  methods.  computer  is  terminal values  corresponding  »t  )  . after  to  the  is  hybrid  In  of a  ^^0^).  (or  above  to  flow  by  computer  terms  equivalent  0^  clarified  this subroutine A  diagram  machineis  IV.  are  practicability large  by  to  procedure  wiper-arm  since  Monte  hybrid  chapter  entire  "with  walks.  the  program  are  the  diagram  the  The  of  transforms  compatible  computer  operation  cause  adjustment  generation  The  to  with  operation  language in  pulses  methods  only  is  described,  motors.  economical,  required  that  analog  71  computer,  computer.  conversion  stepping  number  form  been The  d i g i t a l  .  I.  pulses/sec.  change  the  with  a  the  has  Digital-to-analog  a  the  d i g i t a l  as  Appendix  potentiometers  of  information!; to  transfer  computer  ..  of  computer used  of  in  Monte  partial  methods  the  that  following  Carlo  methods  differential  have  been  chapter for  to  solving  equations.  outlined demonstrate  72 Start  Set r and t pote n t i o m e t e r s t o d e s i r i d v a l u e "by- s e n d i n g p u l s e s stepping motors.  i  a to  ' \  Read the v a l u e s of r arid' t have been s e t on t h e analog computer and type out r and  that t  Q  .  Place analog computer i n compute mode 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. (or y.0.) from the analog c o m p u t e r w h e n the" m o d e - c o n t r o l f l i p - f l o p i s placed i n the hold mode.  f  Add 0 (or  y0) ±  sum.  ±  >  No  R  values  •u  of  /"ide  sum  R  have  ' XX ' Yes  by  partial  y.0.)  X  read.  the  i  (or  0.  J  been  to  then  1 output  \  Ro  The a l l  solution has been obtained points (r , t ) desired.  at  Q  Yes Stop  Figure  4-11.  Flow  Diagram  for  a  Typical  Hybrid  Computer  Program  5. 5.1  HYBRID  COMPUTER  OP  ILLUSTRATIVE  PROBLEMS  Introduction Hybrid  erential are to  SOLUTIONS  computer  equations  given  in  this  substantiate to  that  the  type  results  exact  with  the  5.2  One-Dimensional  Carlo  of  methods.  The  analytical solutions  Monte  Three  Carlo  relationship  density  examples  show,  for  that  the  are  special  of  have  Carlo  been  that  problems  could  Boundary-Value  between  spectral  conditions,  a  partial  techniques  be  put  can  found  were  chosen  forward  be  were  d i f f -  expected  also  for  as  chosen  so  comparison  solutions.  examples  actually  of  i l l u s t r a t i v e problems  indicate  Monte  number Monte  that  that  Example  The  by  methods  the  with  solved  a  new  from  ment  of  the  as  is  were  chapter.  well  which  solutions  the the  noise  Monte  exact  case  in of  duration  various  the  given  Problems this the  of  Carlo  second,  random  source.  equation  section.  The  f i r s t ,  demonstrates  walks  and  the  second  and  third  parameters  solutions  The  and  are  in  a  power  boundary close  agree-  solutions.  1,  d ^ _ 2  0  * x d -o  0(-D = -  1  0(+l)  1  2  The  stochastic  simulated  for  of  (Section  type  Monte  line Carlo  C  Carlo  this  one-dimensional 3.3)  solutions  in. P i g u r e  5-1 •  solutions,  differential  =  equation  Laplace  +  that  equation  must  be  which  is  is  of  To  this  problem  i l l u s t r a t e the  numerous  solutions  are  shown a l o n g  variance  that  were  of  the  obtained  the  ir 1  =  0  =  0  Monte at  x  Q  7 4  0  i.o  4  -1.0  -.6  -.2  .2  .6  1.0  2 Figure  5-1.  Solutions  of  D, 1  ^  + K  P~ d  = x  o  0.  o  75 are  l i s t e d  in  of  solutions  of  this  with  Table is  order  only  of  This useful  for  source  N-^(t).  of  a  is  related  problem,  As  walk to  the  are  deviation  boundary  typical  in  this  values.  for  set  Deviations  solutions  obtained  walks.  determining  random  largest  of  2.41$  magnitude  random  1,000  The  5-2.  is  which the  the  power  t r i v i a l  power  shown  starting  is  in at  spectral  Appendix x  to  =  x  spectral  V,  and  Q  density  set  up,  density the  is  extremely of  2D-^  average  through  noise  duration  terminating at 2D^  a  x  =  -  equation  AV-10.  1 I  Since be  T(x ), Q  for  determined.  random  walks  Table  1  Por  2T(o)  unit  =  100  5-2.  this  1  ~  of  X ,  x  1 o  2  =  Q  is  q  example  at  =  x  = - 2 D f  )  value  starting  l  D  where  any  ^o  -  the  0 was  units  72  2  easily  measured,  average 290  duration  ms.  Prom  T(0)  this  /sec.  volts.  0.21  1.61  0.61  -2.19  0.41  -0.59  0.81  -2.39  1.01  -0.79  -0.98  2.41  2.41  -0.99  -0.59  -1.39  -2.19  -0.79  Values  D^  of  iqO  0 (O) N  obtained  with  N  =  1000.•  can of  value  1  76 As AV-lOy  a  values  of  graph  is  graph T(x  a  f o r . D^  in  and  by  measuring  prior  Figure  since  to  the  5-3.  i t  complex  Average of  a  =  units  equipment  and  equation  values  and  two " s e t s  / s e c ,  was  plotted.  of  measured  This  5-3.  above  is  computer  1.72  important  T(0),  more  the  the  theoretical  Figure  Since up  on  comparing ),  shown  check  problem  is  extremely  parameter  D^  can  often  worthwhile  to  be  simple  easily  run  this  to  set  determined problem  problems.  Time  for  a  Random  One-Dimensional  Walk  Laplace  used  for  Equation.  the  Solution  77 Example 2,  D,1 df0 + Z d0_  TT dx_  dxo =  0(-D  A  0  =  -1  0(+l) = +1  The s t o c h a s t i c d i f f e r e n t i a l equation f o r t h i s example of Problem C is  i f -  K  =  N  i  (  t  )  -  S o l u t i o n curves f o r  | •"l  = 0, 0.5 and 2.0  2 with  = 1.72 u n i t / s e c . (from Example 1.) a r e shown i n Pigure  .5-1. Example 3.  *-§ - ( l dx:  2 x  0 ( - l ) = -1  )0 = 0 0  0(+l) = A  T h i s i s an example o f Problem D, S e c t i o n 3.3-  The s t o c h a s t i c  d i f f e r e n t i a l equation i s  If - i<*> H  and the r e l a t e d f u n c t i o n a l i s  "Y  e x  P  (1 - x ^ ) d t  (  78  79 The  integral  the  noise  than  2  Carlo  source  as  computer  Laplace's  convenient  in  function Carlo are  of  shown  for  at  the  for  problem  d e t e c t e d by  Two  point  portion  Figure  of  Q  of  and  5-5.  A  =  that  of  10,000  2  sets  since  rather  2T>^  of  compared  Monte  -.75,  d  time  x  are  D^  Monte  with  direct  5-4.  Figure  walks.  comparing  Two  differential  X  1,000  density  by  Dimensions  position  1,000  A,  Figure  partial  centre  each  in  scaled  equation.  values in  is  spectral  demonstrates  the  for  expression  power  three  solving  centre  in  the  example  for  the  has  Equation  solutions  required were  N^(t)  solutions  potential 0  shown  functional  i m p l i e d by  This  The  the  solutions,  analog  5.3  in  of  y  =  Q  5-5  0  is  the  of  2  at  the  this  example  with  1  of  the  and  per  a  Monte solution  2 minutes  the  (x  point*  as  circle.  walks  a  are  region  determined  inner  random  methods  equations  approximately  In +  y  Carlo  -  was  boundaries d)  2  +  y  2  2 with  (.25)  varied 5.4  .  simply  Poisson's  The by  centre  position  adjusting  Equation  in  a  d  Two  equation,  ~ \ 2  \  0  = c  region  R  chosen  to  (see  insert  satisfy  the  in  ^Jo 2  Figure  Poisson  2  oy  =  0  2 condition  solved  \ 2 +  oo boundary  ^ }is  was  Dimensions  x  with  circle  potentiometer.  \ 2 Poisson's  inner  2 + ^b  on  the  boundary  C  of  2 5-6). equation  The so  boundary that  an  condition exact  was  solution,  80  Figure  5-5.  Solutions  of  Laplace's  Boundary  Equation  Position.  as  a  Function  of  a  8 1  could  be  found.  solution  is  however,  cannot  be  choice  of  boundary  independent  of  the  predicted  by  the  shape  computer  condition of so  R. that  the  exact  This, no  loss  of  results. As  this  this  actually  generality  of  For  outlined  problem  in  Section  is.given  Problem  3-3,  E,  the  solution  by  0  0(r )  0 (? ) +  =  Q  1  Q  J" 0 (vt )dt -  where  0j[_(^) > o  f °  r  this  Q  2  OO  example,  is  the  solution  equation  Cbx  _ y b-  with  boundary  J  0  with  o  o  is  i n i t i a l  the  y,  = - £ + - £ C  2  o  condition x,  0 (r ,t )  ~  2  2  o  solution  on  c.  d  of  the  heat  condition  0 (r ,O) 2  Q  (3.35)  o  =  -2  C of  equation  R.  of  Laplace's  82  and  zero  boundary The  example  conditions  stochastic  on  C  of  differential  R, equations  used  for  are-'  ! ? = »2<*>  Figure  5-6.  Solutions  of  Equation  Poisson's in  the  Equation  Region  and  Shown.  Laplace's  this  83  0  @ x =y =.4 Q  0  2  *  Monte  Carlo  Solutions  Interpolated  240  Figure  Solutions  5-7.  of  of  with of  D^  = Dg  time,  = D.  the Heat  Poisson's  Since  the computer  Equation  =  133)  Solution  320  -t  used  i n  the  (ms.)  c  Solution  Equation.  the function  time  (1  variable  $2^ o'^o^ T  t  must  i  he  s  a  f  u  scaled  n  c  "  t  i n  l  0  n  accord-  | ance  with  D.  The c o r r e c t  scaling  i s  t  = Dt o  Monte are  shown  example, respect 0^  at  from  a  Figure  i n Figure is  to  x-  Carlo  5-6.  t h e sum o f t  Q  of  = y  Q  =  .4  i s  0^  at  0^  trapezoidal 5-7  solutions  is  X .44  rule  -.2 7 .  q  of  0(r )  along  Q  The s o l u t i o n  0 at  at  .4  = y .  X Q  q  = y  =  The  =  Q  As  .4.  Hence,  0 at  X  of q  X  the line q  = y  Q  q  of  0g  at  =  .4  is  X of  q  y  Q  with 5-6,  = y  0g  =  f o r  .4,  i n Figure  the values  = y  =  Q  X  and the i n t e g r a l given  integral  integration  . c  Q  =  given  .4, i n  84  .44  -  .27  Pigure  =  •  .17  This  value  is  one  of  the  values  walks  and  plotted  in  5-6. For  walks  were  These  values,  ance  with  time  for  5.5  Heat  this  problem,  simulated N  the each  =  for  each and  1,000  analysis  of  value  0(r )  Equation  of  in  Solutions  value  L  =  One,  was  the  Two  of  and  0^,  The  respectively.  total  approximately  Three  random  133  determined  C.  3.5  and  heat  0^  were  133,  Section Q  of  random  1,000  in  accord-  solution  minutes.  12  Dimensions  equation  with 0  i n i t i a l  (r, )  =  conditions at  +1,  the  0 (r ) o  Q  centre  of  = a  -1,  and  line,  a  boundary square  conditions  and  a  cubic  region  C D  are of D  shown  in  Figure  Problem A, =  Section  units  1.72  comparators important to  reach  of  the  to  to a  in  and  In  using  the  that  three  were  3.2,  detect  boundary  problem.  established  /sec.  note  The  5-8.  the  problems,  solved two,  four  boundaries. average  using or  For  time  significantly  a l l  T(0)  Appendix  cases V.  f a l l s  noise six  these  T(0)  decreases  which  for with  within  are  examples  sources  with  electronic problems,it a  random  the the  is  walk  dimensionbounds  85  Figure  5-8.  Solutions a  of  Line,  the a  Heat  Square  Equation and  a  at  Cubic  the  Centre  Region.  of  86  5•6  Laplace's  Equation  in  Three  Dimensions 2  The in z  the  cubic  - 1.  =  c  (  b  ?  are  is  (  x  shown  satisfy  is  of  region  bounded  by  planes  Carlo  solutions  b  "  in  Figure  the  known  b  z  }  +  (  a l l  x  b  "  z  5-9.  Laplace  for  y  b>  detect  used for  to  equation  , y o' o  and  For  this  the  boundaries,  generate  each  5.7  point  close were  set  up  the  0  of  obtained  the  "  y  boundary so  line  x  =  =  Q  1, y  Q  0,  and =  Z  x  q  for  the  that  b b z  +  x  b b z  c o n d i t i o n was  the  exact  chosen  analytical  to  solution  z . o six  and  (r^).  e l e c t r o n i c comparators  quarter-square  Approximately  were  multipliers  5 minutes  were  used  were  required  in  Results  this  with a  given  study,  exact  and the  in  many  Monte  solutions.  other  Carlo  In  a l l  s t r a i g h t - f o r w a r d manner  examples  solutions cases,  without  were  good  the  that in  results  need  of  adjustments. For-most  gave  average  example,  examples  during  agreement  c r i t i c a l  walks  y  0 =  solution.  Discussion  In were  equation,  = - 1,  x  along  V t  +  The  J  to  Laplace's  condition  =  }  example  Monte  boundary  0  f i n a l  results  of  about  time  with  a  fast  d i g i t a l  fast  point  solutions  satisfactory  5 minutes analog  computer  was  for  be  was  (20  found  verifying  required  computer  could  i t  mc  reduced  for  that  the  each  methods. solution.  bandwidth) to  about  1,000  1  coupled sec*;.  .  random An This to  a  87  0  .8 .6  )  x\  .4  [\ :  /  .2  1—JS -1.0  -.8  -.6  *  0  .2  .6  .4  .8  Monte  Carlo  Solutions  (N =  1000)  o Monte  Carlo  Solutions  (N= =  2000)  —  Figure  -.2  - . 4  Analytical  Solutions  5-9.  1.0  x  o~ o~ o y  Solution  of  Laplace's  Equation  in  Three  Dimensions.  i Even  with  slow can  computers,  few  points  be  for  finite-difference  obtained  finite-difference obtained  values, unique  about  solutions  methods,  ease  demonstrated  position  in  Monte  on  the a  however,  Carlo same  fast  solutions  time  that  d i g i t a l  solutions  at  at  is  a  required  computer. many  points  With are  simultaneously. The  was  however,  and can  in  shape be  feature  with which the of  boundary  example  regions,  of as  Section well  altered very  easily,  of  Carlo  the  Monte  positions  i t  5.3.  can  Since  as  boundary  is  suggested  methods  could  be  be  changed ' the  and that used  i n i t i a l this to  z  88 advantage solution  in of  value  must  point  could  computer, grid  and  boundary  engineering a  be be  design found  solving or  problem to  solved  however,  give  boundary  a  For  in a  which  This  require  complete  value.  example, a  a  boundary  particular  easily.  would  for  design.  Monte or  of  problem  setting  up  a  set  of  boundary  potential at  type  new  potentials  Carlo  on  a  specified a  d i g i t a l  finite-difference for  each  t r i a l  89 CONCLUSIONS  6.  Monte approximate and  Carlo  solutions  homogeneous  equations e l l i p t i c solved  of  a  to  much more  Monte  have  partial general  treated in  Carlo  tested.  techniques  use  the  computer as  dynamic  of  range  of  program,  and  boundary  values On  the  example  about  cases,  the  a  solutions.  does  upon  be  the  not  advantage well  class  report  been  as  of  homogeneous  c a n now  4  proposed  be  the  memory are  and  for  and  high-speed  boundaries,  Hence,  techniques  Problems  system  random  walks  fast  hybrid  were  maximum  for  the  the  hybrid  simulated  Thus,  parallel and  easy  i n i t i a l  to and  i n  system  about  i n i t i a l  1  or  be  used  however, sec.  In  1,000  walks,  to  solve  simulated  boundary  random  engineering  was  could  obtained with  w i t h 1,000 many  that  1,000  nearly random  value  of  solutions  problems  are  in  a l l walks the with  obtained  time.  the in  a  that  the  accuracy  obtained  point or  of  reasonable  1,000  With  have  e l l i p t i c ,  equations.  computer  computer.  obtaining  modified.  PACE-A1WAC  could  w i t h i n 5$  In are  the  to  parameters,  easily  solutions  sufficient in  are  methods  d i g i t a l  equation  5 minutes. walks  exact  the  problems,  random  were  analog  than  Hybrid  for  nonhomogeneous  Michigan  the  operation  and  form  implementing The  Carlo  developed  differential  the  methods.  Monte  been  homogeneous  parabolic  equations  by  methods  methods a  have  been  developed,  p o i n t - b y - p o i n t manner.  depend  total  that  upon  number  of  the  solutions  solutions  The at  that  the  solution  solutions at  neighboring are  obtained.  one  points Por  90 this  reason  the  that  require  many  points  methods  solutions are  are at  required,  particularly well  only  a  few  points.  suited If  to  problems  solutions  f i n i t e - d i f f e r e n c e methods  are  at  more  efficient. The  Monte  require  only  methods  for  a  analog  large  Carlo  a  f a c i l i t i e s methods.  small  solving  methods  Carlo  or  a  that  where  i t  methods  hybrid  that  computer  have  whereas  been  proposed  finite-difference  p a r t i a l d i f f e r e n t i a l equations large have  d i g i t a l  been  would  not  computer.  developed be  seem  possible  to  require  Hence, ideal  the  for  employ  either  Monte  small  other  hybrid  computing  91 APPENDIX INTERFACE  FOR TRANSFER AND  A from  block  t h e PACE  OF DATA BETWEEN T H E P A C E THE ALWAC  diagram  t o t h e ALWAC  i s  (DVM) o f t h e PACE  version.  The f l i p - f l o p s  f l i p - f l o p s  shown  i s  that  o f t h e ALWAC  f o r transfer  i n Figure  used  AI-1.  of  i n the figure  are normally  data  The d i g i t a l  f o r analog-to-digital  a r e shown that  R-V  231  III-E*  of the interface  voltmeter  input  I  con-  are the  set from the  flexowriter. The  value  PACE  t o t h e ALWAC  led,  normally ALWAC  the  application  the  puts  a signal  This  sign  a  g  1  0 or l )  next  *  l ' s  of the analog  The s i g n  g  which  (8).  and each  allows  i s  then  supplied.  from  t o t h e ALWAC This  i s  digit  as follows.  the sign  allows  a  About  plus  voltage  decimal  f l i p - f l o p s  transferred  to enter  5-digit  allows  sign  binary-  available are  has been detailed  read.  After  description  at  transferred  T h e ALWAC  accumulator.  t h e 10,000's  1,000's  The data  and the process  value.  out-  t h e DVM t o e n t e r  the binary-coded  F F 1 , F F 2 , FF3 a n d FF4•  signal-  30 m s . a f t e r  i s  a l l digits  i s  FF4.  The  digit  F F 1 on i t s way t o t h e accumulator.  which  from t h e  i s  t o read  a  then  F o r a more  f l i p - f l o p ,  signal  i s  digit  T h e ALWAC  of the hold  f e r r e d iro" t h e " a c c u m u l a t o r , the  manner.  t o t h e DVM.  t o t h e ALWAC  f l i p - f l o p s  transferred  signal  equivalent  outputs  enter  a  i s  "hold"  DVM o u t p u t .  signal  i n the following  supplies  sequentially  voltage  v i a the mode-control  The  coded-decimal  of an analog  (either  T h e ALWAC digit then  continued  to trans-  until  o f t h e DVM h a v e  of the interface,  see reference  ^sf F l e x o w r i t e r A I D ] — b.  Sign  J  g 10'  AND  8  2l  HAND 1 — c  OR  FFI  1  z  Am  4  102  i  '1 d  g  92  AND ggj F l e x o w r i t e r  -—j  1 g 8  Analog Input  HAND I— d  OR  FF2  OR  FF?  OR  F F 4  z  g 4  <AND I—•  d,  IL  10'  AND  2  11  1  AND l. Flexowriter l  41  Hold  8  AND 4 1  AND.  4  to  g 2 g  i l  AND. 4_1  AID 1. Flexowriter  1  5 1 8-  15_L  4-  AND  g 2  5 1  AND g  1-  51  AND  Digital "Voltmeter Figure  AI-1.  Interface  b,  AND  for  l 4 Interface x  Transfer ALWAC  x  of  Data  ALWAC  Between  III-E  PACE  and  93 been  read  from  the  into  the  ALWAC.  accumulator,  The  entire  the  "hold"  reading  is  released  by  a  operation  requires  about  signal 10  ms. The must  be  held  registered  by  the  at  the  conveniently led  analog  by  an  is  by  a  rotation  15°  rotation. 12-to-l has  voltage this of  The  on on  volts the a  scheme,  while  a  pulse  are  gears. i t ,  arm  100  by  can  u n t i l  ms.).  This  the  ALWAC  motors. from  input at  coupled  the to  be  144  pulses  An  example  a  20  volts  sent  pulses/sec.  to  is a  ALWAC  the  DVM  has  is  .the  accomplished  that  to  the  is  PACE  stepping  input  motor  are a  10-turn  causes  shown  in  stepping  in  the  a  -15°  through  potentiometer  required program  through  causes  potentiometers a  control-  motors  instructions  stepping  other  of  the  4-10),  The  dummy  of  to  circuit  Figure  Therefore,.if  arm.  pulses  approximately  stepping  one  wiper  least  (see  from  originating  across  transferred  track-and-hold  at  wiper  at  f l i p - f l o p  by  motors  is  (^30  pulse  reduction  - 100  change  single  value  transferred  pulses  A  +  analog  driven  ALWAC.  that  number  mode-control  potentiometers driven  constant  correct  Data  are  a  voltage  for to  10-volt  change  Figure motor  a  at  the  AI-2. a  rate  By  94  P l a c e t h e Number 288 i n the E-Register  Dummy (Send  a  Instruction Pulse  Decrease E  E>0  to  Number by  AI-2.  in  1  Compare E  Figure  Motor)  Instructions  for  =  0  Activating  Stepping  Motor  95 APPENDIX MULTICHANNEL  DISCRETE-INTERVAL  Numerous quired  for  3-channel AII-1. 0  "k"  Monte  The —*-  Schmitt  1  state  applied  cyclically  If  f , the  is  essentially  For  output  to  the  zero  levels  0  A  is  E  ( T ) = E  the  pulse  AND  gate  from  2  | T I ^>  volts,  is an  the rate  N^(t)  an  shown  ring of  f  of  re-  economical in  average  are  function  are  Figure  rate  of  of  the  counter  lowis  pulses/sec. c essentially  each  channel  ^ c  the  (1 - f  a  and  2  of  zero-crossings  at  N (t)  at  SOURCE*  npise  diagram  properties  autocorrelation for  -  block  by  N-^t),  wide-band  triggered  sharp  each  outputs  and  A  these  trigger  source.  Q  uncorrelated  with  BINARY-NOISE  stable,  changes/sec.  noise  »  of  methods.  source  quality  k  channels  Carlo  noise  II  autocorrelation  \T\  )  function  \T\ <i  is  ^ c  =  The  power  spectral  correlation  0  |T|  density  function  cj? ( C d )  *  For  (9)  a  more  (GJ)  = 2f E  detailed  to  -± c  this  (AII.l)  auto-  is 1  Cp  corresponding  >  2  -  c  analysis  COS  ,  (<£—) ,  c  (All.2)  CO  2  of  this  noise  source  see  reference  Lowqualitynoise source  N-^t) Schmitt Trigger  Clock of requency  F l i p Flop  3  AND  FlipFlop  Level Shifterl  AND  FlipFlop  Level Shifter  F l i p Flop  Level Shifter  stage Ring  _N^(t)  Counter  3f  AND  VO  Figure  AII-1.  Block  Diagram  of  3-Channel  Noise  Source.  97  The obtained  with  Monte k  =  Carlo  .4  solutions  mc/sec,  f  =  given  in  20kc/sec.  Chapter  5  were  and  5  volts.  E  =  c With width  these of  b i l i t i e s  values  the of  noise the  the  criterion  channels  analog  is  k  ^>  greater  computer.  f  is  than  met, the  and  the  hand-  bandwidth  capa-  98  APPENDIX AN  By with The  suitably  electronic required  plugs  as  feedback  switching,  in  capacitor  on  mode-control  the  c  0 volts,  In  =  this  mode  - Y-^  Q  u  t  V-J-Q  switch  =  -  =  +  from  t o - V-j-Q i n 1 0 0  a  SWITCH  PACE  fast  231  SPDT  AIII-1. a  1  T-^ a n d  switch by  can  be  placement  equipped  realized.  of  bottle  replaces  ohm  resistor  R  -  V j ^ and  When  c  =  +  so  that  V  conduct  amplifier  patching  ; M  c.  R-V  This  between  signal gate  SPDT  accomplished  with  transistor V  a  switched  electronic  For ^out  be  C  V  and  to  is  Pigure  output the  patching  patching  shown  ^  ELECTRONIC  III  the  -  and  V-^  5 volts, ^. =  electronic  -  allows  under  the  control  transistor  VJQ.  gate  the  T^  When  are  open.  V^. 100 -  volts  V-^  jjisec.  to  and -  V-^  Vj =  -  in  160  N  100  volts,the  jjisec.  and  output from  100K  -AA/VV  IC  lOOK  IC  PS  O  put  O  Coil  Q  Coil  \  a  •  1 /  1  /  •  F  W W 1  a 0  meg  f r o m mode control circuitry  - c o n n e c t i o n s made by b o t t l e plugs  r e p l a c e C by R by p a t c h i n g as shown  Figure  AIII-1.  Circuit  and  Patching  for  a  SPDT  Switch  100  APPENDIX A  PROGRAM  An similar  to  Section  4.5  b4  POR  ALWAC  those is  I M P L E M E N T I N G MONTE C A R L O  III-E  program  indicated  given  IV  in  that  the  carries  flow  METHODS..  out  diagram  operations  of  Pigure  4-11,  below:  1  00  83b5 5 7 0 f  80  01  4917  fffO  81  02  dfOO  d903  82  03  0001  0000  83  04  ffaO  1704  84  05| f 9 e 0  f9eO  85  06  dlOc  dfda  86  07  03e8  0000  87  08  5703  118c  88  09  fie 5 fffO  89  Oa  lb08  2800  8a  ob  0000  0013  8b  Oc, 5 7 0 5  2800  8c  0d| f f e O  1320  8d  oe  6d8b  2 4 0 0 |8e  of  0090  0000  8f  10  4913 4 9 1 7  90  11  4913 1 7 1 4  91  12  4d8b  1 9 8 0 |92  13 0 0 0 0 0 0 0 0 9 3  14  f9e0  fffO  94  15  6117  95  16  1116  0 0 0 0 |96  17  18  7913  fffO  98  19 e b l b 3 2 0 0 9 9 l a  0000  0 0 0 0 |9a l b  |05f5 e l O O 9 b  IC  6117  fffO  9c I d  0 0 0 0 |9e  |oooo  OeOO  d580  f 5 c 8 |9d l e jOOOO  If  loooo  0000  97  0000  9f  8fb649be  Immediately of  Of)  are  multiplex  sent  the  These the  total  of  are  numbers  out.  motor,and  a  r  19  #l)  is  Q  07) upon  added have  motor  allows i t  are  then  signals  been  is  initiated,  read,  to  144  process  times  is  stepping  of  Another the  program  (flag  computer  numbers  1,000  typed  after  (contents  analog  the  to  signal  Immediately numbers  after  a  for  is  typed  read  pulses  the  then  repeated.  The  (contents  of  8b).  a  T  Q  (contents  of  r  to  be  as  A read.  thousand  fixed  terminal  they  are  to  process  the is  of  f l i p - f l o p .  read.  together^the  sent  .  One  mode-control  added  are  of  out.  from  p a r t i a l sum and  pulses  adjustment  the ; value  from  read  144  sum  After is  stepping repeated  a  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 d e r i v e d f o r the average  time T '(r ) that i s r e q u i r e d f o r a  random walk s t a r t i n g a t r time. age  The equation  Q  t o reach a boundary f o r the f i r s t  i s solved f o r s p e c i a l cases t o give the aver-  d u r a t i o n o f a random walk t h a t i s used f o r the s o l u t i o n of  Laplace's  equation  i n a one, a two and a three-dimensional  ized s p h e r i c a l r e g i o n .  general-  The approach that i s used i s s i m i l a r t o ,  but not as i n v o l v e d as, the method of Wasow f o r c a l c u l a t i n g the 1 fi  mean d u r a t i o n o f d i s c r e t e random walks. From the d e f i n i t i o n of g C r ^ t ^ | r , t ) and from o  Chapman-Kolmogorov equation  J^vM  vV^b  =  C  Q  (2.2) i t f o l l o w s that  yy^'SlA'V^b^i^il vV i d r  E C (AV.l)  i s the p r o b a b i l i t y d e n s i t y f o r a random walk t o reach a boundary f o r the f i r s t  time a t t, i f i t s t a r t e d a t ( r , t ). The b o o  average d u r a t i o n of a random walk s t a r t i n g a t ( r , t ) i s t h e r e o  f o r e g i v e n by -©o  Q  dr, dt, b b  oo oo ( t  R -oo  b -  C  Vfz w\ I ^l^i^W^i^i I {  vV^i  C (AV.2)  102 OO  = JJ(\ R  J  ~V  - o o  «<  Jg(? ,t |  -t )  b  Q  5  b  l f  IV V  d  r  b  d  V  ^ 1 ' %  I  t )dr dt f(r .,t | 1  b  b  1  1  R (AV..3)  Therefore,  T ( r , t ) = JH\,\WTV\ o  \ ? ,t )d  o  0  0  r i  R  - t ) j  +  f  Q  ^  r  ^  d  r  , (AV.4)  R The l a s t term f o l l o w s from the f a c t  that  oo (AV.5) - oo c  f o r random walks that are c e r t a i n t o terminate at a boundary. Now l e t t-, = t 1  a T a y l o r s e r i e s about r Chapter 2.  Q  o  + A t and expand T ( r , , t + A t ) i n 1' o  i n the same manner that was done i n  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 f o l l o w s that 6t  (AY.6) r  Q  o ^ o  ?  o' o t  ) d r  103 I f the operator L-  ^ i s independent of t , then o' o Q  T ( r , t ) i s a l s o independent of t . o  Q  For t h i s case T ( r ,t ) can  be denoted by T ( r ) and L- T ( r ) + 1 = 0 o The  (AV.7)  boundary c o n d i t i o n f o r T ( r ) i s T ( r ^ ) = 0 Q  I f Lof Laplace's  o  i s the operator that i s used f o r t h e . s o l u t i o n  equation,then  D y T ( ? ) +,1 2  Q  = 0  (AV.8)  For an n - d i m e n s i o n a l j g e n e r a l i z e d depends only upon r  D r  1 n-1 o  Q  dr  = |r |  sphere of r a d i u s "a", T ( r ) o  , therefore,  Q  r^dTC^) d r  + 1 = 0  o  T(a) = 0  (AV.9) i  The'solution  of the problem given by a  2  - r  2  T h i s r e s u l t shows e x p l i c i t l y how  the d u r a t i o n of a random walk  depends upon the s t a r t i n g r a d i u s r sphere.  By e n c l o s i n g any  (AV.9) .is  Q  and  the dimension of the  other shape of r e g i o n with a g e n e r a l -  i z e d s p h e r i c a l region,an upper bound on the average d u r a t i o n of  104 a random walk can be obtained.  A lower bound can be  obtained  by e n c l o s i n g a g e n e r a l i z e d s p h e r i c a l r e g i o n by the r e g i o n f o r which the lower bound i s d e s i r e d .  For example, the average  d u r a t i o n T(0) of a random walk s t a r t i n g at the centre of a square r e g i o n w i t h s i d e s 2a i s  (AV.ll)  The average d u r a t i o n T(0) of a random walk s t a r t i n g at the centre of a cubic r e g i o n with edges 2a i s  h  <  T ( 0 )  <  %  (AV.12)  105  REFERENCES  F o r s y t h e , G . E . , and Wasow, 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 . John.. W i l e y a n d S o n s I n c . , New Y o r k , I960. C u r t i s s , T . J . H . , "Sampling Methods A p p l i e d to D i f f e r e n t i a l and D i f f e r e n c e E q u a t i o n s " , P r o c . Seminar on 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 . , New Y o r k , N . Y . , November 1949.  -  1  M e y e r , H e r b e r t A . , E d i t o r , Symposium., on 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 , 1956... Chuang, K., K a z d a , I.F., and Windeknecht, T., "A S t o c h a s t i c Method of S o l v i n g P a r t i a l Differential. Equations using an E l e c t r o n i c Analog Computer", P r o j e c t M i c h i g a n R e p o r t 2900-91-T. W i l l o w Run l a b o r a t o r i e s , U n i v e r s i t y of M i c h i g a n , June I960. MacKay, D.M., and F i s h e r , U l t r a - H i g h Speed. Chapter I n c . , New Y o r k , 1962.  M.E., Analogue 16, John W i l e y  Karplus, Walter J . , Analog Simulation, B o o k C o m p a n y , I n c . , New Y o r k , 1958.  Computing and Sons  McGraw  at .  H i l l  Middleton, David, S t a t i s t i c a l Communication Theory, C h a p t e r s 1 and 10, McGraw H i l l Book Company, Inc., New Y o r k , I960. Soudack, A . C , and L i t t l e , W.D.,]"An E c o n o m i c a l H y b r i d i z i n g Scheme f o r A p p l y i n g Monte C a r l o M e t h o d s the S o l u t i o n of P a r t i a l D i f f e r e n t i a l Equations", S i m u l a t i o n , V o l . 5, N o . 1, pp. 9 - 1 1 , J u l y , 1965. Kohne, H. , L i t t l e , Multichannel Noise November, 1965-  W.D., Soudack, A . C , Source", Simulation.  to  "An Economical V o l . 5, N o . 8,  Bharucha-Reid, A.T., "Elements of the Theory of Markov 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 H i l l B o o k C o m p a n y , I n c . , New Y o r k , I960. 1  Wang, M i n g C h e n , and U h l e n b e c k , G . E . , "On t h e T h e o r y of Brownian Motion II", Reviews of Modern..Physics. 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 1945. D a r l i n g , D.A., and 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 to a C l a s s of Problems i n the Theory of Noise and Other R a n d o m P h e n o m e n a , P a r t I", IRE T r a n s , on Information T h e o r y . V o l . I T - 3 , p p . 3 2 -37, M a r c h , 1957.  106 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 Several V a r i a b l e s using Analog Diode L o g i c " , IEEE T r a n s . On E l e c t r o n i c Computers. V o l . EC-12, pp. 112129, A p r i l , 1963. Hampton, R . L . T . , "A H y b r i d A n a l o g - D i g i t a l 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.. 185, March, 1965.  Pseudo 3, pp.  Random 179-  T o m o v i c , R., and 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 Inc.., New York, 1962. Wasow, W o l f g a n g , "On t h e Mean D u r a t i o n o f Random W a l k s " , Journal of Research of the National Bureau of Standards. V o l . 46, No. 6, p p . 462 - 4 7 1 , J u n e , 1 9 5 1 .  Addendum Since the p r e p a r a t i o n of t h i s t h e s i s , the f o l l o w i n g hooks have been brought to the author's a t t e n t i o n : Dynkin, E.B.. Markov Processes. V o l . I and V o l . I I , Academic Press I n c . P u b l i s h e r s . , New York, 1965. These books c o n t a i n an extensive treatment processes.  of Markov  I n p a r t i c u l a r , Chapter 13 of Volume I I has a t h e o r  e t i c a l d i s c u s s i o n of problems s i m i l a r to those d i s c u s s e d i n S e c t i o n 3.3  of t h i s  thesis.  

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