Б.П. Демидович, И.А. Марон - Основы вычислительной математики (1132358), страница 84
Текст из файла (страница 84)
(2) /=ь и 5)»вшвниа систам линнйных ьлгввгличнских тглвняний 651 Введя матрицу а = ~и~1) и векторы х, систему (2) можно записать в матрнчно-векторной форме х=их+р. (2') Будем предпологать, что все собственные значения матрицы а по модулю меньше единицы. В частности, достаточно считать, что какая-нибудь каноническая норма матрицы а подчинена неравенству ИсП~1 ° В этом случае система (2') имеет единственное решение, которое может быть найдено методом итерации (гл. Ч!!1, 2 1О). Подберем систему множителей и~~ таним образом, чтобы числа ргр определяемые уравнениями (4) (1, / 1, ..., л), аг — р, и, удовлетворяли следующим условиям: !) Рг .'р О, причем рг ) 0 при игт~ 0; и 2) ~~ ~рг~(1 (1=1,..., л). ! ! Пусть р, „+1 1 ~ч'~р, (г — 1,..., л).
/=1 Кроме того, условно положим р„+11 — — 0 при /(в+ 1 Р~+ и а+ ~ = 1. Рассмотрим теперь некоторую блуждающую частицу, обладающую конечным числом возможных и несовместимых состояний уы с»ю ' ° з ею 'е»+! Эта частица такова, что с вероятностью рг (1, /=1,..., и+1) переходит из состояния Ю! в состояние бр независимо от прошлых состояний н с неопределенностью будущих. Состояние 8»+1 =Г (аграница» или «поглощающий экран») является о с об ы и и соответствует полной остановке частицы, так как в силу условия Р»+ьу =- 0 (/= 1, ..., л) переходы из состояния Л„+~ в состояние Зт при 21» 652 [гл.
хгв метод монткькьгло у( и -1-1 невозможны. Таким образом, процесс блуждания прекращае1ся, как только частица первый раз попадает на границу Г. Описанная смена состояний обычно называется дискретной цепью Марковав) с конечным числом состояниИ »2». Числа р;т называются лере.
ходными вероятностями, а матрица п-~ Рц " Ры Рц и+~ Рп1 Рн Рп, и+1 О ... О 1 представляет собой матрицу перехода состояний (ЗД (закон цепи). Пусть 5г — некоторое фиксированное состояние, отличное от граничного (1(и+1). Рассмотрим случайное блуждание частицы, нвчинаюшеесЯ в Данном состоЯннн Юг=56 н после Рада пРоменсУ- точных состояний Юн, Юц, ..., Зс заканчивающееся на граннце 5с„+,=Г. Таким образом, Юг„(т~О) есть состояние частицы, непосредственно предшествующее выходу ее на границу.
Совокупность состояний Тг-(дц, Яц, ..., Ю... Я,„„» (6) длн краткости будем называть травкторивй. Пусть Х; †случайная величина, завнсящая от случайных траекторий У;., начинающихся в состоянии 5; (функционал траектории Т;), и принимающая для траектории (6) значение ЦТ,)»)ц+яцц[)ц+яццоцфц+... +оцц...о, [),, (6) (6') В(~с) =»)ц+[)ц+."+[)г„. По теореме умножения вероятностей траектория Тп а следовательно, н значенне $(Т;), реализуется с вероятностшо Р(Тт) = рцц рцц...
р,„~, „ где се=у н ~'„+,— — и+1. Те о р е и а. Математические ожидания (1=1, 2, ..., и) МХс х, являются корнями системы (2). ') Точнее, прас~пой однородной [2[. где [)т Ц= гю 1„..., [„) — соответствующне свободные члены приведенной системы (2). В частности, если о;. = 1, то имеем просто й 5) гвшвнив систвм лннайных хлгявеличаскнх тнхвнвний 653 До к аз а тельство.
Траектории Тп начинающиеся из состояния Я! в зависимости от первого шага можно разбить на п+1 категорий т;,=р, ь,, з,„...); Т,„=Р,, б„, 5,„...); Ть„„=(8о 5„„), т. е. частица, начав блуждание из состояния 5г, прн первом шаге моисет переходить пли в состояние Юы или а состояние 5» н т. д., а затем через некоторое число шагов закончить блуждание на границе. Если частица имеет траекторию Т,=Рп бр З,„..., 5,, 5! =Г), где учил+1, то случайная величина Х! в силу формулы (6) примет значение В( Тг!) ))! + т!!!8! + о!!ог!»6!» + + с!! !! ° ' ' ! ° !' Р!» =))!+игу(()!+ег;,()й+... + игы".пг„„„()г„) =()|+пця(Т!), (8) где Ту †некотор траектория с начальным состоянием Юр В том случае, когда частица сразу попадает на границу Г, т. е. траектория имеет вид Т; „+, —— (5!, 5„+,), то $(т!, „+1) =Рп (8') Вероятность того,что траектория Т! есть траектория типа Т!т, очевидно, равна р!р В силу определения математического ожидания имеем: МХ! = Хит)Р(Т) = ХХиТ;,)Р(Т;,).
Если /(п+1, то траектория Т! состоит из отрезка (Яг, Зу) н некоторой траектории Т!. Поэтому Р(Тг!) =ргтР(Ту). При /=и+1 имеем: $(Т! „) = ()! п Р(Т; „,) = р, „„. Кроме того, так как каждой траектории Т!~ при /(л+1 одно- значно соответствует траектория Ту и обратно, то суммирование по траекториям Тг! для у= 1, 2, ..., п можно заменить суммирова- нием по траекториям Т!, Отсюда, учитывая формулу (8), получаем: МХ! — — ~~ ~~~(()г+о!.';(Т )) р!,Р(Т )+()гр!,„ 1=! ., 654 катод монти.нагло (гл. лтп или МХ,= т, РЮЧ1ХаТ~)Р!Т ! ! ! УР~УР(7~! ! Ро + ] ° ~ г! т, Но, очевидно, ~~~ $ (Т ) Р (Т ) = МХ! (у = 1, 2, ..., л). г! Кроме того, ~Р~Р(Ту) = 1 ' и т, и+ ! х~!РП~~~~Р(Т1)+Р!, а = Х Рц=( ° /=1 г! ' ! ! Следовательно, ~А = Х пц~~~+ гч (1 = ° ° ) 1=! где а! — — Рцо! .
Теорема доказана. 3 а м е ч а н и е. При доказательстве теоремы предполагалось, что математические ожидания х,=МХ, (г=1, ..., л) существуют. Можно доказать, что при выполнении условия (3) случайные величины Х! обладают конечиымн математическими ожиданнямя. Из доказанной теоремы слелует, что корни системы (2) можно рассматривать как математические ожидания случайных величин Хт, ..., Х„. Для экспериментального определения величины х! —— МХ! организуют И случайных блужданий, со случайнымн траекториями Т!!~!(л= 1, ..., Д!) с начальным состоянием Ю! и каждый раз регистрируют значение Р,(Т!! !) случайной величины Х;. Предположим, что испытания независимы между собой н величина Х! имеет ограниченную дисперсию. Тогда в силу теоремы Чебышева 11), [2) при !т' достаточно большом с вероятностью, сколь угодно близкой к 1, будет справедливо неравенство и х! — — ~~! $ (Т,'"') ( в, а=! где е — заданная предельная погрешность.
Таким образом, корни системы (2) приближенно могут быть определены по формулам и х! —,— ~~> $(Т а'). (9) а=! $6) гвшвнин систнм линнйиык ллгнвглнчиских гглвнкний 665 В частности, этим способом можно обращать матрицы вада А Š— и, (10) где ()а)((1 и Е=16гу) — единичная матрица. Для этого заметим, что элементы обратной матрицы А- =(-4 являются корнями линейной системы Яа(бгь — ага)ха! 6!у (1, /= 1, ..., л).
а ! Отсюда получаем, что элементы каждого столбца х!Р ..., х„(/=1, ..., и) матрицы А т определяются из линейной подсистемы н х! = „~~агх +6, (!=1, ..., а) а=! (11) где Т!=(бг, Юс„° бс,бг„+,=Г) и числа игу таковы, что р определяемые из уравнений а! — — Рг/пгж представлнют собой вероятности перехода из состояния 5! в состояние ЮР Математические ожиданиЯ МХ!г — — хы дадУт искомые элементы матРицы А т. Покажем теперь, как практически возможно организовать случайное блуждание частицы с заданными вероятностями перехода Ргж Для простоты продположим, что Р!у суть десятичные дроби с общим знаменателем 10'(а — натуральное число): гп Рп ю Рга 0! ° Р! где 1ды гг„..., 1г,„+,— целые неотрицательные числа, причем 1г!+Ф!а+...
+Ф! „+! — — 1О' (1=1, 2, ..., и). Рассмотрим частицу, имеющую начальное состояние Ю!. Пусть (х) есть а-разрядные числа, меньшие единицы, равномерно распределенные на отрезке (О, 11, например, элементы из соответ. стаующей таблицы случайных чисел. Произведем розыгрыш случайного числа к. Если окажется, что выполнено неравенство На основании предыдущего, отправлянсь из состояния Я!=Ю!„ при фяксярованном / получаем случайную величину Х со значеннямя ьу ( 7'!) = 6!,г + бс,/и!,!, + ° .. + 6! !чгю,к, ...и.
656 )гл. хчп метод монте-канло то будем считать, что частица переходит из состояния 8! в состояние 8,. Далее, если Н~~ ( 10 ец гц+)и то полагаем, что частица переходит из состояния 8! в состояние 8 . Аналогично определяются остальные переходы. В частности, частица попадает на границу 8„+, —— Г, если случайное число х таково, что гп+ "+)ы тп+" + О«+ !д л+» !0» !0» На основании данного соглашения ясно, что количества благоприятных случаев для переходов 8! 8) (г'=1, 2, ..., и+1) пропорциональны соответственно числам )ыг )ы» )ц «чы причем эти случаи равновероятны. Поэтому вероятности перехода Р(8! — 8~)= — рг 6=1, ..., л; т'=1, ..., и+1).
112) Р е ш е н и е. Можно положить и„=1, т»«,=1, Отсюда матрица перехода есть о а=1, о = — 1. О,1 0,2 ! О,Т )у — 0,2 О 3~ 0,5 0 0 1 где элементы первой строки представляют собой соответственно вероятности перехода из состояния 8, в состояния 8„ 8« и 8 = Г, а элементы второй строки — нз состояния 8, в состояния 8„ 8, и 8«, причем «кайма» соответствует границе Г. Так как элементы матрицы П кратны 0,1, то можно использовать одноразрядные случайные числа, цифры которых рекрутируются нз Выбирая последовательность случайных чисел и руководствуясь указанным выше правилом, получаем случайное блуждание частицы с фиксированным начальным состоянием и данными вероятностями перехода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
