Вычисление определителя

Материал из MachineLearning.

(Различия между версиями)

Версия 17:12, 20 октября 2008

Название статьи необходимо изменить. Текст статьи нуждается в существенной переработке (см. Обсуждение).--Strijov 12:53, 20 октября 2008 (MSD)

Содержание

1 Постановка задачи
2 Основные определения и простейшие свойства
3 Прагматика
4 Примеры работы алгоритма
5 Руководство пользователя
6 Руководство программиста
7 Литература
8 См. также

Постановка задачи

Задание подразумевает знакомство пользователя с основными понятиями численных методов, такими как определитель и обратная матрица, и различными способами их вычислений. В данном теоретическом отчете простым и доступным языком сначала вводятся основные понятия и определения, на основании которых проводится дальнейшее исследование. Пользователь может не иметь специальных знаний в области численных методов и линейной алгебры, но с легкостью сможет воспользоваться результатами данной работы. Для наглядности приведена программа вычисления определителя матрицы несколькими методами, написанная на языке программирования C++. Программа используется как лабораторный стенд для создания иллюстраций к отчету. А также проводится исследование методов для решения систем линейных алгебраических уравнений. Доказывается бесполезность вычисления обратной матрицы, поэтому в работе приводится более оптимальные способы решения уравнений не вычисляя ее. Рассказывается почему существует такое количество различных методов вычисления определителей и обратных матриц и разбираются их недостатки. Также рассматриваются погрешности при вычислении определителя и оценивается достигнутая точность. Помимо русских терминов в работе используются и их английские эквиваленты для понимания, под какими названиями искать численные процедуры в библиотеках и что означают их параметры.

Основные определения и простейшие свойства

Определитель

Введем определение определителя квадратной матрицы любого порядка. Это определение будет рекуррентным, то есть чтобы установить, что такое определитель матрицы порядка $n$ , нужно уже знать, что такое определитель матрицы порядка $n - 1$ . Отметим также, что определитель существует только у квадратных матриц.

Определитель квадратной матрицы $A$ будем обозначать $|A|$ или det $A$ .

Определение 1. Определителем квадратной матрицы второго порядка называется число .

Определителем квадратной матрицы порядка $n$ , $n \geq 3$ , называется число

где $M_k$ - определитель матрицы порядка $n - 1$ , полученной из матрицы $A$ вычеркиванием первой строки и столбца с номером $k$ .

Для наглядности запишем, как можно вычислить определитель матрицы четвертого порядка:

Замечание. Реальное вычисление определителей для матриц выше третьего порядка на основе определения используется в исключительных случаях. Как правило, вычисление ведется по другим алгоритмам, которые будут рассмотрены позже и которые требуют меньше вычислительной работы.

Замечание. В определении 1 было бы точнее сказать, что определитель есть функция, определенная на множестве квадратных матриц порядка и принимающая значения в множестве чисел.

Замечание. В литературе вместо термина "определитель" используется также термин "детерминант", имеющий тот же самый смысл. От слова "детерминант" и появилось обозначение det $A$ .

Рассмотрим некоторые свойства определителей, которые сформулируем в виде утверждений.

Утверждение 1. При транспонировании матрицы определитель не меняется, то есть $|A^T| = |A|$ .

Утверждение 2. Определитель произведения квадратных матриц равен произведению определителей сомножителей, то есть $|AB| = |A||B|$ .

Утверждение 3. Если в матрице $A$ поменять местами две строки, то ее определитель сменит знак.

Утверждение 4. Если матрица $A$ имеет две одинаковые строки, то ее определитель равен нулю.

В дальнейшем нам потребуется складывать строки и умножать строку на число. Эти действия над строками (столбцами) мы будем выполнять так же, как действия над матрицами-строками (матрицами-столбцами), то есть поэлементно. Результатом будет служить строка (столбец), как правило, не совпадающая со строками исходной матрицы. При наличии операций сложения строк (столбцов) и умножения их на число мы можем говорить и о линейных комбинациях строк (столбцов), то есть суммах с числовыми коэффициентами.

Утверждение 5. Если строку матрицы умножить на число $alpha$ , то ее определитель умножится на это число.

Утверждение 6. Если матрица содержит нулевую строку, то ее определитель равен нулю.

Утверждение 7. Если одна из строк матрицы равна другой, умноженной на число (строки пропорциональны), то определитель матрицы равен нулю.

Утверждение 8. Пусть в матрице $A$ i-ая строка имеет вид $(p_1 + q_1, p_2 + q_2 ... p_n + q_n)$ . Тогда $|A| = |A_p| + |A_q|$ , где матрица $A_p$ получается из матрицы $A$ заменой i-ой строки на строку $(p_1 p_2 ... p_n)$ , а матрица $A_q$ - заменой i-ой строки на строку $(q_1, q_2 ... q_n)$ .

Утверждение 9. Если к одной из строк матрицы добавить другую, умноженную на число, то определитель матрицы не изменится.

Утверждение 10. Если одна из строк матрицы является линейной комбинацией других ее строк, то определитель матрицы равен нулю.

Определение 2. Алгебраическим дополнением к элементу $a_i_j$ матрицы $A$ называется число, равное $(-1)^i^+^j * M_i_j$ , где $M_i_j$ - определитель матрицы, полученной из матрицы вычеркиванием i-ой строки и j-ого столбца. Алгебраическое дополнение к элементу $a_i_j$ матрицы $A$ обозначается $A_i_j$ .

Пример. Пусть . Тогда

Замечание. Используя алгебраические дополнения, определение 1 определителя можно записать так:

Утверждение 11. Разложение определителя по произвольной строке. Для определителя матрицы $A$ справедлива формула

Пример. Вычислите .

Решение. Воспользуемся разложением по третьей строке, так выгоднее, поскольку в третьей строке два числа из трех - нули. Получим

Утверждение 12. Для квадратной матрицы $A$ порядка $n$ при $j \neq k$ выполнено соотношение .

Утверждение 13. Все свойства определителя, сформулированные для строк ( предположения 1 - 11), справедливы и для столбцов, в частности, справедливо разложение определителя по j-ому столбцу и равенство при $j \neq k$ .

Утверждение 14. Определитель треугольной матрицы равен произведению элементов ее главной диагонали.

Следствие. Определитель единичной матрицы равен единице, $|E| = 1$ .

Вывод. Перечисленные выше свойства позволяют находить определители матриц достаточно высоких порядков при сравнительно небольшом объеме вычислений. Алгоритм вычислений следующий.

Обратная матрица