Решение линейных систем уравнений методом Монте-Карло

Содержание

 

ВВЕДЕНИЕ          2

1. МЕТОД           5
1. Построение матрицы перехода      5
2. Нахождение корней системы уравнений    8

2. ПРИМЕР

2.1 Пример построения траекторий блуждания частицы  12

2.2 Пример решения  системы уравнений методом Монте-Карло 14

3. РЕАЛИЗАЦИЯ МЕТОДА НА ЭВМ      15

 

ЗАКЛЮЧЕНИЕ          20

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ    21

 

Приложение 1. Листинг программы      22

Приложение 2. Пример результата работы программы   23

 

ВВЕДЕНИЕ

Обычный путь решения задачи состоит  в том, что указывается алгоритм, с помощью которого искомая величина находится или точно, или с заданной погрешностью. А именно, если через обозначить соответствующие результаты последовательно накопляющихся действий, то

причем в случае конечного  числа операций процесс обрывается на некотором шаге. Здесь процесс  вычислений является строго детерминированным: два различных вычислителя при отсутствии ошибок приходят к одному и тому же результату.

Однако встречаются задачи, где построение такого рода алгоритма практически невыполнимо или сам алгоритм оказывается чрезмерно сложным. В этих случаях часто прибегают к моделированию математической или физической сущности задачи и использованию законов больших чисел теории вероятностей. Оценки искомой величины получаются на основании статистической обработки материала, связанного с результатами некоторых многократных случайных испытаний. При этом требуется, чтобы случайная величина при по вероятности сходилась к искомой величине , т. е. для любого должно иметь место предельное соотношение

,

где обозначает соответствующую вероятность.

Выбор величины обусловливается конкретными особенностями задачи. Например, часто искомую величину трактуют как вероятность некоторого случайного события или как математическое ожидание некоторой случайной величины. Тогда частоту появления события при соответствующих случайных испытаниях в широких предположениях можно рассматривать как вероятностную оценку искомой величины. Возможны также и другие варианты. Заметим, что в этих случаях вычислительный процесс является недетерминированным, так как он определяется итогами случайных испытаний.

Способы решения задач, использующие случайные величины, получили общее название метода Монте-Карло. Более точно под методом Монте-Карло понимается совокупность приемов, позволяющих получать решения математических или физических задач при помощи многократных случайных испытаний. Оценки искомой величины выводятся статистическим путем и носят вероятностный характер. На практике случайные испытания заменяются результатами некоторых вычислений, производимых над случайными числами.

Эффективное применение метода Монте-Карло  стало возможным после появления  быстродействующих электронных машин, так как для получения достаточно точной оценки искомой величины требуются выполнение вычислений для весьма большого количества частных случаев и последующая статистическая обработка колоссального числового материала. Заметим, что при пользовании методом Монте-Карло нет необходимости знать точные соотношения между данными и искомыми величинами задачи, а достаточно лишь выявить тот комплекс условий, при наличии которого соответствующее явление имеет место. Это обстоятельство делает возможным использование метода Монте-Карло для решения логических задач.

Из математических задач, для которых  разработано применение метода Монте-Карло, отметим следующие: решение систем линейных уравнений, обращение матриц, нахождение собственных значений и  собственных векторов матрицы, вычисление кратных интегралов, решение задачи Дирихле, решение функциональных уравнений различных типов и др. Метод Монте-Карло успешно используется также для решения задач ядерной физики. Заметим, что для решения одной и той же конкретной задачи схема применения метода может быть существенно различной.

Далее подробно рассмотрим решение  систем линейных уравнений методом  Монте-Карло.

 

1. МЕТОД
1. Построение матрицы перехода

Рассмотрим линейную систему

    (1.1)

Некоторым способом приведем систему (1.1) к специальному виду

    (1.2)

Введя матрицу  и векторы

систему (1.2) можно записать в матрично-векторной  форме

      (1.2`)

Будем предполагать, что все собственные значения матрицы по модулю меньше единицы. В частности, достаточно считать, что какая-нибудь каноническая норма матрицы подчинена неравенству

       (1.3)

В этом случае система (1.2`) имеет единственное решение которое  может быть найдено методом итерации.

Подберем систему множителей таким образом, чтобы числа определяемые уравнениями

     (1.4)

удовлетворяли следующим  условиям:

1. , причем при ;

2) .

 

Пусть

.

Кроме того, условно положим

 при 

.

Рассмотрим теперь некоторую  блуждающую частицу, обладающую конечным числом возможных и несовместимых  состояний

.

Эта частица такова, что  с вероятностью переходит из состояния , в состояние , независимо от прошлых состояний и с неопределенностью будущих. Состояние является особым и соответствует полной остановке частицы, так как в силу условия   переходы из состояния в состояние при невозможны. Таким образом, процесс блуждания прекращается, как только частица первый раз попадает на границу . Описанная смена состояний обычно называется дискретной цепью Маркова (простой одинарной) с конечным числом состояний. Числа называются переходными вероятностями, а матрица

представляет собой  матрицу перехода состояний (закон цепи).

Пусть - некоторое фиксированное состояние, отличное от граничного .  Рассмотрим случайное блуждание частицы, начинающееся в данном состоянии и после ряда промежуточных состояний заканчивающееся на границе . Таким образом, есть состояние частицы, не посредственно предшествующее выходу ее на границу. Совокупность состояний

     (1.5)

для краткости будем  называть траекторией. Пусть  - случайная величина, зависящая от случайных траекторий , начинающихся в состоянии (функционал траектории ), и принимающая для траектории (1.5) значение

,   (1.6)

где - соответствующие свободные члены приведенной системы (1.2).

В частности, если , то имеем просто

.     (1.6`)

По теореме умножения  вероятностей траектория , а следовательно, и значение , реализуется с вероятностью

,     (1.7)

где и .

 

1.2 Нахождение корней системы  уравнений

 

Покажем, что математические ожидания

являются  корнями системы (1.2).

Траектории  начинающиеся из состояния , в зависимости от первого шага можно разбить на категорий

т. е. частица, начав блуждание  из состояния  при первом шаге может переходить или в состояние или в состояние и т. д., а затем через некоторое число шагов закончить блуждание на границе.

Если частица имеет  траекторию

,

где , то случайная величина в силу формулы (6) примет значение

  (1.8)

где - некоторая траектория с начальным состоянием .

В том случае, когда частица сразу  попадает на границу  , т. е. траектория имеет вид , то

.      (8`)

Вероятность того, что  траектория есть траектория типа , очевидно, равна .

В силу определения математического  ожидания имеем:

.

Если  , то траектория состоит из отрезка и некоторой траектории . Поэтому

.

При имеем:

 и  .

Кроме того, так как  каждой траектории при однозначно соответствует траектория и обратно, то суммирование по траекториям для можно заменить суммированием по траекториям .

Отсюда, учитывая формулу (1.8), получаем:

или

.

Но, очевидно,

.

Кроме того,

и

Следовательно,

,

где .

Из сказанного выше следует, что  корни системы (1.2) можно рассматривать  как математические ожидания случайных  величин  . Для  экспериментального  определения  величины организуют случайных блужданий, со случайными траекториями с начальным состоянием и каждый раз регистрируют значение случайной величины . Предположим, что испытания независимы между собой и величина имеет ограниченную дисперсию. Тогда в силу теоремы Чебышева при достаточно большом с вероятностью, сколь угодно близкой к 1, будет справедливо неравенство

,

где - заданная предельная погрешность. Таким образом, корни системы (1.2) приближенно могут быть определены по формулам

.     (1.9)

В частности, этим способом можно обращать матрицы вида

      (1.10)

где и - единичная матрица. Для этого заметим, что элементы обратной матрицы

являются корнями линейной системы

.

Отсюда получаем, что  элементы каждого столбца

матрицы определяются из линейной подсистемы

    (1.11)

На основании предыдущего, отправляясь из состояния , при фиксированном получаем  случайную величину со значениями

,

где и числа таковы, что определяемые из уравнений

представляют собой вероятности  перехода из состояния  , в состояние . Математические ожидания

дадут искомые элементы матрицы .

 

2.1 Пример построения траекторий  блуждания частицы

 

 

Покажем теперь, как практически  возможно организовать случайное блуждание частицы с заданными вероятностями перехода . Для простоты предположим, что суть десятичные дроби с общим знаменателем ( —натуральное число):

,

 

где - целые неотрицательные числа, причем

.

Рассмотрим  частицу,   имеющую   начальное   состояние  . Пусть есть -разрядные числа, меньшие единицы, равномерно распределенные на отрезке , например, элементы из соответствующей таблицы случайных чисел. Произведем розыгрыш случайного числа . Если окажется, что выполнено неравенство

.

то будем считать, что  частица переходит из состояния  в состояние . Далее, если

,

то полагаем, что частица  переходит из состояния  в состояние . Аналогично определяются остальные переходы. В частности, частица попадает на границу , если случайное число таково, что

На основании данного  соглашения ясно, что количеств благоприятных случаев для переходов пропорциональны числам

,

причем эти случаи равновероятны. Поэтому вероятности  перехода

.

Выбирая последовательность случайных чисел и руководствуясь указанным выше правилом, получаем случайное блуждание частицы  с фиксированным начальным состоянием и данными вероятностями перехода. Для достижения нужной точности корней следует рассмотреть достаточно большое количество независимых блужданий.

 

2.2 Пример решения  системы уравнений методом Монте-Карло.

Методом Монте-Карло решить систему уравнений

   (2.1)

Приведем систему к  специальному виду (1.2)

   (2.2)

Можно положить

Отсюда матрица перехода есть

где элементы первой строки представляют собой соответственно вероятности перехода из состояния в состояния , а элементы второй строки – из состояния в состояния , причем нижняя строка таблицы соответствует границе .

Полученные результаты для 20 случайных блужданий с начальным  состоянием приведены в таблице в приложении 2. Случайное число обеспечивало переходы состояний согласно следующей инструкции:

Для начального состояния  :

1. если , то
2. если , то
3. если , то
4. если , то
5. если , то

и так далее.