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

Метод Монтанте — метод лінійної алгебри для розв'язання системи лінійних рівнянь, знаходження обернених матриць та визначників. Метод названий в честь його першовідкривача Рене Марио Монтанте Пардо (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}={\begin{pmatrix}2&-1&-3&1&3\\1&1&-2&-2&2\\3&-2&1&-1&-2\\1&-1&1&3&1\end{pmatrix}}$

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

$A_{1}={\begin{pmatrix}2&-1&-3&1&3\\0&\cdots &\cdots &\cdots &\cdots \\0&\cdots &\cdots &\cdots &\cdots \\0&\cdots &\cdots &\cdots &\cdots \end{pmatrix}}$

Поточний оглядовий елемент $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}={\begin{pmatrix}2&-1&-3&1&3\\0&3&-1&-5&1\\0&-1&11&-5&-13\\0&-1&5&5&-1\end{pmatrix}}$

Друга ітерація: наступний оглядовий елемент $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}}}\qquad \forall (i,j)\in \left\{1,3,4\right\}\times \left\{3,4,5\right\}$

$A_{2}={\begin{pmatrix}3&0&-5&-1&5\\0&3&-1&-5&1\\0&0&16&-10&-19\\0&0&7&5&-1\end{pmatrix}}$

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

$A_{3}={\begin{pmatrix}16&0&0&-22&-5\\0&16&0&-30&-1\\0&0&16&-10&-19\\0&0&0&50&39\\\end{pmatrix}}$

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

$A_{4}={\begin{pmatrix}50&0&0&0&38\\0&50&0&0&70\\0&0&50&0&-35\\0&0&0&50&39\\\end{pmatrix}}$

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

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