УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ
Для понимания материалов этого пункта полезно ознакомиться с идеологией метода Монте-Карло


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

Рассмотрим систему из n_{} линейных уравнений относительно n_{} неизвестных

\left\{ \begin{array}{lllll} a_{11}x_1 &+a_{12}x_2&+ \ldots&+a_{1n}x_n &=b_1,\\ a_{21}x_1 &+a_{22}x_2&+ \ldots&+a_{2n}x_n &=b_2,\\ \dots & & & & \dots \\ a_{n1}x_1 &+a_{n2}x_2&+ \ldots&+a_{nn}x_n &=b_n, \end{array} \right.

которую иногда будем представлять и в матричном виде

AX= \mathcal B \ .

Решение этой системы равносильно нахождению минимума квадратичной функции

F(X)=\sum_{j=1}^n \alpha_j \left(a_{j1}x_1+\dots+a_{in}x_n-b_j \right)^2= (AX-\mathcal B)^{\top} \left( \begin{array}{cccc} \alpha_1 & 0 & \dots & 0 \\ 0 & \alpha_2 & \dots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \dots & \alpha_n \end{array} \right) (AX-\mathcal B) \ ,

где \{ \alpha_j\}_{j=1}^n — положительные числа, а {}^{\top} означает транспонирование.

Если исходная система линейных уравнений имеет единственное решение X=X_{\ast}=(x_{1\ast},\dots, x_{n\ast}), то в пространстве \mathbb R^{n} уравнение

F(X) = 1

задает эллипсоид с центром в точке X_{\ast}. Каждая из (n_{}-1)-мерных гиперплоскостей x_k=x_{k\ast} ( линейных многообразий), проходящих через центр эллипсоида, делит его объем пополам.

Построим n_{}-мерный параллелепипед

A_1<x_1<B_1,\ A_2<x_2<B_2,\ \dots, A_n<x_n<B_n,

заведомо содержащий рассматриваемый эллипсоид. Генерируем последовательность случайных векторов

\{\Xi_i =(\xi_1^{[i]},\xi_2^{[i]},\dots, \xi_n^{[i]})\}_{i=1}^N

в которых случайные величины \{\xi_j^{[i]}\}_{j=1}^n попарно независимы и равномерно распределены каждая на своем отрезке ]A_j,B_j[. Обозначим через M_{} количество случайных векторов, удовлетворяющих соотношению

F(\Xi_i)\le 1 \ ,

т.е. попавших внутрь эллипсоида. Тогда частота M/N сходится по вероятности к отношению V_{\Epsilon}/V_{\Pi}, где V_{\Epsilon} — объем эллипсоида, а V_{\Pi} — объем содержащего его параллелепипеда. Теперь перенумеруем случайные векторы, попавшие внутрь эллипсоида в порядке возрастания координаты x_{k}. Возьмем теперь случайный вектор, имеющий в новой нумерации порядковый номер M/2. Тогда его k_{}-ю координату \xi_k^{[M/2]} можно принять в качестве приближенного значения координаты x_{k\ast} центра эллипсоида. Можно поступить и иначе, а именно, взять среднее арифметическое

\overline{\xi_k} = \frac{1}{M} \sum_{i=1}^M \xi_k^{[i]} \approx x_{k\ast} \ .
П

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

\left\{\begin{array}{rrrrr} 2\,x_1&-x_2&+5\,x_3&-x_4&=9, \\ 3\,x_1&+x_2&-3\,x_3&+2\,x_4&=5, \\ -3\,x_1&-4\,x_2&+2\,x_3&-7\,x_4&=1, \\ -x_1&-4\,x_2&+x_3&-3\,x_4&=-2. \end{array} \right.

Решение. Уравнение эллипсоида F(X) подобрал в виде

\frac{1}{400} (AX-\mathcal B)^{\top} (AX-\mathcal B) =1 \ .

Пришлось повозиться с задачей нахождение параллелепипеда, содержащего этот эллипсоид. Универсальный алгоритм не придумал, но некоторым «обходным манёвром» удалось решить задачу хотя бы для небольших систем:

-4<x_1<11,\ -9 < x_2 < 12,\ -4 < x_3 < 5,\ - 12 < x_4 < 7 \ .

Таким образом, V_{\Pi} = 53865.

Для генерации случайной последовательности использовал стандартную функцию randvector системы Maple 15. Для контроля сравнивал приближение величины V_{\Pi} M/N к величине объема эллипсоида, вычисленной по формуле, приведенной ЗДЕСЬ:

V_{\Epsilon} \approx 3133.207748 \ .
\begin{array}{r|r|r|r|r|r} N & 1000 & 5000 & 10000 & 20000 & 50000 \\ \hline M & 62 & 297 & 581 & 1181 & 2885 \\ \hline V_{\Pi} M/N & 3339.6300 & 3199.581 & 3129.5565 & 3180.7282 & 3108.0105 \\ \hline \overline{\xi_1} & 3.2592 & 3.2745 & 3.1230 & 3.1020 & 3.1798 \\ \hline \overline{\xi_2} & 0.9406 & 1.5346 & 1.4669 & 1.4867 & 1.5141 \\ \hline \overline{\xi_3} & 0.3453 & 0.5163 & 0.3996 & 0.5001 & 0.4299 \\ \hline \overline{\xi_4} & -1.7029 & -2.2198 & -2.1676 & -2.1545 & -2.2413\\ \end{array}

Решение системы

x_1=\frac{257}{84} \approx 3.05952,\ x_2=\frac{53}{36} \approx 1.47222,\ x_3=\frac{55}{126} \approx 0.43651 , x_4=-\frac{547}{252} \approx -2.17063 \ .

Источник

Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний Монте-Карло и его реализация в цифровых машинах. М.: Физматгиз, 1961. 266 с.


2014/11/15 09:11 редактировал au