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

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

, i = 1, ..., n. (9.13)

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

, i = 1, ..., n. (9.14)

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

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

Подберем такие множители v_ij, чтобы решения p_ij уравнений α_ij = p_ij×v_ij удовлетворяли условиям:

1) p_ij ³ 0, причем p_ij > 0, если α_ij ¹ 0;

2) i =1, ..., n.

Положим p_{i, n+1} = l – , i = 1, ..., n;

p _{n+1, j} = 0, если j < n + l; p_{n+1, n+1} = l.

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

S₁, S₂, ... , S_n+1,

причем граничное состояние S_n+1 = Г соответствует ос­тановке частицы, так как р_{п+1, j} = 0, т. е. частица не мо­жет выйти из состояния S_n+1.

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

П . (9.15)

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

T_i ={= Г }. (9.16)

Поставим в соответствие траектории T_i случайное чис­ло X_i:

X_i = β_i + ×+ ×+ ××× +×, (9.17)

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

Теорема 9.1. Математические ожидания случайных величин (9.17) равны корням системы (9.14): M(X_i) = x_i, i = 1, ... , п.

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

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

, i = 1, ..., n, ||α|| < 1. (9.18)

2. Подобрать такие числа v_ij, чтобы решения p_ij урав­нений α_ij = p_ij×v_ij удовлетворяли условиям:

1) p_ij ³ 0, причем p_ij > 0, если α_ij ¹ 0;

2) i =1, ..., n. (9.19)

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

p_{i, n+1} = l – , i = 1, ..., n;

p _{n+1, j} = 0, если j < n + l; p_{n+1, n+1} = l. (9.20)

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

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

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

3.1.0. присвоить m = 0; i_m = i; v = 1; x_i = x_i + β_i;

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

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

i_m = , 1 £ j £ n

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

3.1.4. для каждого l = 0, 1, ... , m – 2 вычислить

v = v×, x_i = x_i + v×;

3.2. вычислить x_i = x_i / N.