Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Решение систем линейных уравнений




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

. (9.13)

Пусть система (9.13) приведена к виду

(9.14)

где норма матрицы удовлетворяет условию . Тогда система (9.14) имеет единственное решение.

Приведем без доказательства схематическое описание метода Монте-Карло для решения системы линейных уравнений (9.14) (доказательство приведено в [7]).

Подберем такие множители vij, чтобы решения pij уравнений удовлетворяли условиям:

1)

2)

Положим

Будем трактовать число как вероятность перехода некоторой частицы из состояния Si в состояние Sj. Всего состояний :

S1, S2, …, Sn +1,

причем граничное состояние Sn +1 = Г соответствует остановке частицы, так как , т.е. частица не может выйти из состояния Sn +1.

Матрица с элементами называется матрицей перехода состояний {Si}:

 

(9.15)

 

 

Назовем траекторией Ti совокупность состояний, через которые проходит блуждающая частица, начиная с состояния Si и заканчивая граничным состоянием Г. Промежуточные состояния частицы обозначим .

 

(9.16)

 

Поставим в соответствие траектории Ti случайное число Xi:

 

, (9.17)

 

где — свободные члены системы (9.14) с индексами, совпадающими с индексами состояний, образующих траекторию (9.16).

Теорема (доказательство в [7]). Математические ожидания случайных величин (9.17) равны корням системы (9.14): .

Сформулируем алгоритм решения системы линейных уравнений (9.13) методом Монте-Карло.

1. Привести систему (9.13) к виду (9.14):

(9.18)

2. Подобрать такие числа vij, чтобы решения pij уравнений удовлетворяли условиям:

1) 2) (9.19)

Вычислить -й столбец и -ю строку матрицы перехода:

(9.20)

3. Выполнить для каждого :

3.0. Присвоить значение xi = 0;

3.1. Для каждого , (где N число испытаний случайной величины Xi), выполнить статистические испытания по алгоритму:

3.1.0. Присвоить m = 0; im = i; v = 1; xi = xi + βi

3.1.1. Присвоим переменной очередное значение: m = m + 1;

3.1.2. Возьмем случайное число ξ из интервала (0; 1), и выберем значение im по следующему правилу:

3.1.3. Если j < n + 1, перейти к 3.1.1.

3.1.4. Для каждого вычислить

, ;

3.2. Вычислить xi = xi / N.

 

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

Пример 9.3. Решить систему уравнений

 

 

Решение.Приближенное решение x1 = 0,68; x2 = 0,93 получено методом итераций с точностью до 0,01.

Продемонстрируем применение алгоритма метода Монте-Карло, выполнив вычисления вручную. Запишем матрицу α и вектор β:

 

Очевидно, что можно выбрать числа pij и vij следующим образом:

 

 

Тогда выполняются условия (9.19). Вычислим 3-й столбец и 3-ю строку матрицы перехода по формулам (9.20):

 

 

Результаты дальнейших вычислений приведены в таблице 9.4, в которой показано, как вычисляется приближенное значение x1. Мы используем здесь методику записи вычислений из учебника [7], прибегая к более подробному пояснению.

Проведем N = 10 испытаний случайной величины X1. Для этого может понадобиться больше 10-ти случайных чисел. Вычислим с помощью программы Excel последовательность из 30-ти случайных чисел из интервала
(0; 1). Для этого введем в ячейку A1 формулу =СЛЧИС() и маркером заполнения протянем ячейку A1 до A30. Форматируем диапазон A1:A30 с помощью команды меню «Формат — Ячейки — Числовой — Число десятичных знаков 2». В первом столбце таблицы 9.4 записаны полученные в Excel случайные числа.

Так как мы вычисляем X1, то начальное состояние Si есть S1. Всего состояний три: S1, S2 и S3 = Г, Г — граничное состояние.

Согласно алгоритму, нам нужно определить в какой из следующих трех интервалов

[0; 0,4), [0,4; 0,4 + 0,1) = [0,4; 0,5), [0,5; 1)

 

попадает очередное случайное число ξ.

Если число попадает в первый интервал, то очередное состояние есть S1, т.е. имеем переход S1 S1. Если число попадает во второй интервал, то имеем переход S1 S2, если в третий, то S1 S3, т.е. частица переходит граничное состояние.

Если начальное состояние есть S2, то надо проверять попадание частицы в интервалы

[0; 0,2), [0,2; 0,7), [0,7; 1).

 

Первое случайное число 0,07 попадает в интервал [0; 0,4), следовательно, частица переходит из S1 в S1. Второе случайное число 0,25 также попадает в интервал [0; 0,4), частица переходит из S1 в S1. Третье число 0,99 попадает в третий интервал [0,5; 1), поэтому частица переходит в граничное состояние S3 = Г. Получаем траекторию S1 S1 S1 →Г.

Теперь вычислим по формуле (9.17) значение X1. Значения индексов im следующие: i0 = 1, i1 = 1, i2 = 1, i3 = 3 (m = 3).

 

.

 

Аналогично вычислим второе значение X1. Следующее случайное число 0,73 попадает в третий интервал, получаем траекторию S1 →Г и значение .

При вычислении третьего значения X1 первое случайное число 0,14 попадает в первый интервал, второе случайное число 0,06 опять попадает в первый интервал, третье случайное число 0,54 попадает во второй интервал. Имеем часть траектории S1 S1 S1 S2. Для состояния S2 следующее случайное число 0,58 проверяем на интервалах

 

[0; 0,2), [0,2; 0,7), [0,7; 1).

 

Число 0,58 попадает во второй интервал, а следующее 0,68 — в третий. Траектория имеет вид S1 S1 S1 S2 S2→Г и значение X1 для этой траектории равно

 

Таблица 9.4

№   Сл. число Траектория блуждания частицы Значение случайной величины X1
0,07 S1 S1 S1 →Г 0,5 + 0,5 + 0,5 = 1,5
0,25
0,99
0,73 S1 →Г 0,5
0,14 S1 S1 S1 → →S2 S2→Г 0,5 + 0,5 + 0,5 – 0,6 – 0,6 = 0,3
0,06
0,54
0,58
0,68
0,86 S1 →Г 0,5
0,73 S1 →Г 0,5
0,65 S1 →Г 0,5
0,29 S1 S1 →Г 0,5 + 0,5 = 1
0,84
0,22 S1 S1 →Г 0,5 + 0,5 = 1
0,57
0,90 S1 →Г 0,5
Среднее значение величины X1 = 6,3 / 10 = 0,63

 

Аналогично можно вычислить среднее арифметическое для X2.

Результаты вычислений приведены в таблице 9.5. Здесь начальное состояние есть S2.

Таблица 9.5

№   Сл. число Траектория блуждания частицы Значение случайной величины X2
0,10 S2 S1 S2 S2 →Г 0,6 – 0,5 + 0,6 + 0,6 = 1,3
0,49
0,37
0,94
0,75 S2 →Г 0,6
0,86 S2 →Г 0,6
0,63 S2 S2 S1 →Г 0,6 + 0,6 – 0,5 = 0,7
0,04
0,80
0,68 S2 →Г 0,6
0,41 S2 S2 →Г 0,6 + 0,6 = 1,2
0,78
0,43 S2 S2 S2 S2 →Г 0,6 + 0,6 + 0,6 + 0,6 = 2,4
0,23
0,20
0,92
0,91 S2 →Г 0,6
0,90 S2 →Г 0,6
0,49 S2 S2 →Г 0,6 + 0,6 = 1,2
0,70
Среднее значение величины X2 = 9,8 / 10 = 0,98

 

Сравнивая полученные значения X1 = 0,63; X2 = 0,98 с приближенными корнями x1 = 0,68; x2 = 0,93, видим, что получены удовлетворительные результаты. Очевидно, для повышения точности необходимо провести значительно большее число испытаний.

 


Поделиться:

Дата добавления: 2015-09-13; просмотров: 39; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты