Различия между версиями 12 и 13
Версия 12 от 2017-11-07 09:16:38
Размер: 3159
Редактор: FrBrGeorge
Комментарий:
Версия 13 от 2017-11-10 00:25:29
Размер: 3159
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 7: Строка 7:
$$A'_(i,j) = det([[A_(0,0), A_(i+1,0)], [A_(j+1,0), A_(j+1,i+1)]])$$ $$A'_(i,j) = det([[A_(0,0), A_(0,i+1)], [A_(j+1,0), A_(j+1,i+1)]])$$

Ввести квадратную целочисленную матрицу построчно и посчитать её определитель (например, методом конденсации Доджсона). Размер матрицы (1<N<14) определяется длиной её нулевой строки.

Сам метод хорошо описан в Википедии. Приведём слегка модифицированный вариант. Будем строить матрицу $$A'$$ размера $$n-1 xx n-1$$ из матрицы $$A$$ размера $$n xx n$$ таким образом, что каждый её элемент равен определителю минора второго порядка строк $$0$$ и $$j+1$$ и столбцов $$0$$ и $$i+1$$ матрицы $$A$$, т. е.

$$A'_(i,j) = det([[A_(0,0), A_(0,i+1)], [A_(j+1,0), A_(j+1,i+1)]])$$

Согласно алгоритму Доджсона, элементы матрицы $$A''_(i,j)$$ надо поделить на соответствующие внутренние элементы матрицы $$A_(i+1,j+1)$$. В нашем случае делить надо всегда на $$A_(0,0)$$, так что можно посчитать определитель $$A''$$, а потом уже поделить на $$(A_(0,0))^(n-2)$$. Таким образом, на каждом шаге конденсации мы накапливаем общий делитель $$D=(A_(0,0))^(n-2)*(A'_(0,0))^(n-3)*(A''_(0,0))^(n-4)*...$$, а на последнем шаге (когда размерность матрицы становится $$1 xx 1$$) делим $$A'^…'_(0,0)$$ на $$D$$.

Кроме того, исходный алгоритм Доджсона предписывает переставлять строки, если какой-то внешний элемент оказался нулевым. В нашем варианте алгоритма достаточно поддерживать $$A'^…'_(0,0) ≠ 0$$, то есть переставлять в матрице строки до тех пор, пока угловой элемент не окажется ненулевым (если таких нет, определитель 0). Не забываем о знаке определителя при перестановке строк (иногда его надо менять)!

8, 8, 5, 6, 3
1, 4, 4, 9, 0
9, 6, 7, 7, 3
4, 1, 0, 1, 4
6, 7, 9, 7, 3

2784

Для проверки правильности можно воспользоваться модулем numpy (предположим, матрица Array хранится в виде списка списков):

   1 import numpy
   2 print(numpy.linalg.det(numpy.array(Array)))

Да, с модулями в Ptyhon3 жизнь становится намного проще :) . Но наша цель — учёба, а не лёгкая жизнь.


CategoryHomework

LecturesCMC/PythonIntro2017/Homework_DodgsonDet (последним исправлял пользователь FrBrGeorge 2017-11-10 00:25:29)