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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Метод Монтанте — метод лінійної алгебри для розв'язання системи лінійних рівнянь, знаходження обернених матриць та визначників. Метод названий в честь його першовідкривача Рене Марио Монтанте Пардо (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^1_{ij} \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^1_{22}

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

 a^2_{ij} \leftarrow \frac{ a^1_{ij} p_2 - a^1_{2j} a^1_{i2} }{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^2_{33}.

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}