!!§!! Вспомогательная страница к разделу ((:algebra2:linearsystems СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ))\\
Для понимания материалов этого пункта полезно ознакомиться с идеологией ((http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9C%D0%BE%D0%BD%D1%82%D0%B5-%D0%9A%D0%B0%D1%80%D0%BB%D0%BE метода Монте-Карло))


---- 


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

 
Рассмотрим систему из $ 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} $ означает ((:algebra2#транспонирование транспонирование)). 

Если исходная система линейных уравнений имеет единственное решение $ 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} $ ( ((:linear_space#линейные_многообразия линейных многообразий))), проходящих через центр эллипсоида,
делит его объем пополам.

Построим $ 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 $ к величине объема эллипсоида, вычисленной по формуле, приведенной <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html>  ((:dets:geometry#объемы ЗДЕСЬ)):
$$ 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 с.