Метод Монтанте

Метод Монтанте — метод лінійної алгебри для розв'язання системи лінійних рівнянь, знаходження обернених матриць та визначників. Метод названий в честь його першовідкривача Рене Марио Монтанте Пардо (René Mario Montante Pardo).

Головна особливість — працює використовуючи виключно цілочисельну арифметику для цілочисельних матриць, що дозволяє отримувати точні результати в комп'ютерних реалізаціях.

Історія

Метод був розроблений в 1973 Рене Маріо Монтанте Пардо, на кафедрі механіки і електротехніки Universidad Autónoma de Nuevo León, в Монтеррей, Мексика.

Алгоритм

Візьмемо лінійну систему рівнянь з цілими коефіцієнтами

$2x-y-3z+w=3$

$x+y-2z-2w=2$

$3x-2y+z-w=-2$

$x-y+z+3w=1$

Розширена матриця (включаючи результуючу колонку):

$A_0=\left(\begin{array}{ccccc}2& -1& -3& 1& 3\\ 1& 1& -2& -2& 2\\ 3& -2& 1& -1& -2\\ 1& -1& 1& 3& 1\end{array}\right)$

Перша ітерація: залишаємо перший рядок (оглядовий рядок) як є, під першим елементом цього рядка робимо нулі.

$A_1=\left(\begin{array}{ccccc}2& -1& -3& 1& 3\\ 0& \cdots & \cdots & \cdots & \cdots \\ 0& \cdots & \cdots & \cdots & \cdots \\ 0& \cdots & \cdots & \cdots & \cdots \end{array}\right)$

Поточний оглядовий елемент $p_1=2$ на $a_{11}$ (верхній лівий елемент), попередній оглядовий елемент $p_0=1$.

Кожен елемент в іншій частині матриці (за виключенням оглядового рядка та стовпця) отримані за формулою

$a_{ij}^1\leftarrow \frac{a_{ij}{p}_1-a_{1j}{a}_{i1}}{p_0}$

Отже

$A_1=\left(\begin{array}{ccccc}2& -1& -3& 1& 3\\ 0& 3& -1& -5& 1\\ 0& -1& 11& -5& -13\\ 0& -1& 5& 5& -1\end{array}\right)$

Друга ітерація: наступний оглядовий елемент $p_2=3$ на $a_{22}^1$

Залишіть другий (оглядовий) рядок як є. Робимо нулі під діагональним елементом оглядового рядка, замінюємо всі попередні оглядові елементи на $p_2$. Потім використовуємо формулу детермінанта до інших елементів, у колонках з 3 по 5 та рядках 1, 3 і 4.

$a_{ij}^2\leftarrow \frac{a_{ij}^1{p}_2-a_{2j}^1{a}_{i2}^1}{p_1}\mathrm{\forall }(i,j)\in \{1,3,4\}\times \{3,4,5\}$

$A_2=\left(\begin{array}{ccccc}3& 0& -5& -1& 5\\ 0& 3& -1& -5& 1\\ 0& 0& 16& -10& -19\\ 0& 0& 7& 5& -1\end{array}\right)$

Третя ітерація: як попередня, з оглядовим елементом $p_3=16$ на $a_{33}^2$.

$A_3=\left(\begin{array}{ccccc}16& 0& 0& -22& -5\\ 0& 16& 0& -30& -1\\ 0& 0& 16& -10& -19\\ 0& 0& 0& 50& 39\end{array}\right)$

Четверта ітерація:

$A_4=\left(\begin{array}{ccccc}50& 0& 0& 0& 38\\ 0& 50& 0& 0& 70\\ 0& 0& 50& 0& -35\\ 0& 0& 0& 50& 39\end{array}\right)$

Тоді розв'язання системи (1):

$x=\frac{38}{50}y=\frac{70}{50}z=\frac{-35}{50}w=\frac{39}{50}$