Инструменты сайта


§

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


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

Рассмотрим систему из $ 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_{\mathrm E}/V_{\Pi} $, где $ V_{\mathrm E} $ — объем эллипсоида, а $ 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_{\mathrm E} \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 с.

algebra2/linearsystems/monte_carlo.txt · Последние изменения: 2023/12/22 17:58 — au