Блог Басараби Марії Михайлівни: Метод Монтанте

четвер, 18 лютого 2016 р.

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

Матеріал з Вікіпедії — вільної енциклопедії.

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

Немає коментарів:

Дописати коментар

Примітка: лише член цього блогу може опублікувати коментар.

Підписатися на: Дописати коментарі (Atom)