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

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

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

Історія

Метод був розроблений в 1973 Рене Маріо Монтанте Пардо, на кафедрі механіки і електротехніки , в Монтеррей, Мексика.

Алгоритм

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

${\displaystyle 2x-y-3z+w=3\,}$

${\displaystyle x+y-2z-2w=2\,}$

${\displaystyle 3x-2y+z-w=-2\,}$

${\displaystyle x-y+z+3w=1\,}$

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

${\displaystyle 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}}}$

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

${\displaystyle 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}}}$

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

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

${\displaystyle a_{ij}^{1}\leftarrow {\frac {a_{ij}p_{1}-a_{1j}a_{i1}}{p_{0}}}}$

Отже

${\displaystyle 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}}}$

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

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

${\displaystyle 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\}}$

${\displaystyle 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}}}$

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

${\displaystyle 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}}}$

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

${\displaystyle 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):

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