Матрицы определитель метод гаусса: Ваш браузер не поддерживается

Особенности вычисления определителя матрицы (Контрольная работа)

Содержание

Введение 2

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

2. Математические и алгоритмические основы решения задачи 5

2.1 Определитель матрицы 5

2.2 Метод Гаусса для решения систем линейных уравнений 6

2.3 Метод Гаусса для вычисления определителя 8

3. Функциональные модели и блок-схемы решения задачи 9

4. Программная реализация решения задачи 11

5. Пример выполнения программы 16

Заключение 18

Список использованных источников и литературы 19

Введение

Многие проблемы, возникающие в экономических исследованиях, планировании и управлении, будучи сформулированными математически, представляют собой задачи, в которых необходимо решить систему алгебраических уравнений.

Исторически первым, наиболее распространенным методом решения систем линейных уравнений является метод Гаусса, или метод последовательного исключения неизвестных. Сущность этого метода состоит в том, что посредством последовательных исключений неизвестных данная система превращается в ступенчатую (в частности, треугольную) систему, равносильную данной.

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

Помимо аналитического решения СЛАУ, метод Гаусса также применяется для нахождения матрицы, обратной к данной, определения ранга матрицы и нахождения определителя.

Целью данной курсовой работы является реализация вычисления определителя методом исключения Гаусса.

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

Пусть дана квадратная матрица A размером NxN. Требуется вычислить её определитель.

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

Пример 1.

Вычислить определитель матрицы методом A исключения Гаусса.

.

Решение:

Приведем матрицу к диагональному виду методом Гаусса.

~.

Тогда определитель матрицы равен произведению ее элементов, стоящих на диагонали:

.

Знак определяется количеством обменов строк, следовательно определитель матрицы .

Пример 2.

Вычислить определитель матрицы методом A исключения Гаусса.

.

Решение:

Приведем матрицу к диагональному виду методом Гаусса.

~.

Тогда определитель матрицы равен произведению ее элементов, стоящих на диагонали:

.

Знак определяется количеством обменов строк, следовательно определитель матрицы .

2. Математические и алгоритмические основы решения задачи

2.1 Определитель матрицы

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

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

Определение. Определителем квадратной матрицы

второго порядка называется число

.

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

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

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

2.2 Метод Гаусса для решения систем линейных уравнений

Пусть дана квадратная матрица A размером NxN. Требуется вычислить её определитель.

Воспользуемся идеями метода Гаусса решения систем линейных уравнений.

Дана система:

a11 x1 + a12 x2 + … + a1n xn = b1

a21 x1 + a22 x2 + … + a2n xn = b2

an1 x1 + an2 x2 + . .. + ann xn = bn

Выполним следующий алгоритм.

На первом шаге найдём в первом столбце наибольший по модулю элемент, поставим уравнение с этим элементом на первую строчку (обменяв две соответствующие строки матрицы A и два соответствующих элемента вектора B), а затем будем отнимать это уравнение от всех остальных, чтобы в первом столбце все элементы (кроме первого) обратились в ноль. Например, при прибавлении ко второй строке будем домножать первую строку на -a21/a11, при добавлении к третьей – на -a31/a11, и т.д.

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

Т.е. на i-ом шаге найдём в i-ом столбце, начиная с i-го элемента, наибольший по модулю элемент, поставим уравнение с этим элементом на i-ю строчку, и будем отнимать это уравнение от всех остальных. Понятно, что это никак не повлияет на все предыдущие столбцы (с первого по (i-1)-ый).

В конце концов, мы приведём систему к так называемому диагональному виду:

c11 x1 = d1

c22 x2 = d2

cnn xn = dn

Т.е. мы нашли решение системы.

Замечание 1. На каждой итерации найдётся хотя бы один ненулевой элемент, иначе система бы имела нулевой определитель, что противоречит условию.

Замечание 2. Требование, что на каждом шаге мы выбираем наибольший по модулю элемент, очень важно в смысле численной устойчивости метода. Если выбирать произвольный ненулевой элемент, то это может привести к гигантской погрешности, когда получившееся решение будет отличаться в разы от правильного.

2.3 Метод Гаусса для вычисления определителя

Будем выполнять те же самые действия, что и при решении системы линейных уравнений, исключив только деление текущей строки на a[i][i] (точнее, само деление можно выполнять, но подразумевая, что число выносится за знак определителя). Тогда все операции, которые мы будем производить с матрицей, не будут изменять величину определителя матрицы, за исключением, быть может, знака (мы только обмениваем местами две строки, что меняет знак на противоположный, или прибавляем одну строку к другой, что не меняет величину определителя).

Но матрица, к которой мы приходим после выполнения алгоритма Гаусса, является диагональной, и определитель её равен произведению элементов, стоящих на диагонали. Знак, как уже говорилось, будет определяться количеством обменов строк (если их нечётное, то знак определителя следует изменить на противоположный). Таким образом, мы можем с помощью алгоритма Гаусса вычислять определитель матрицы за O(N3).

Осталось только заметить, что если в какой-то момент мы не найдём в текущем столбце ненулевого элемента, то алгоритм следует остановить и вернуть 0.

3. Функциональные модели и блок-схемы решения задачи

Блок-схема решения задачи представлена на рисунке 1.

Рисунок 1 – Блок-схема решения задачи для функции DETERMINATE

4 Программная реализация решения задачи

;ФУНКЦИЯ, ВЫЧИСЛЯЮЩАЯ ОПРЕДЕЛИТЕЛЬ

(DEFUN DETERMINANT (MATRIX SIZE)

;ОБЪЯВЛЕНИЕ ПЕРЕМЕННЫХ

;ОПРЕДЕЛИТЕЛЬ

(DECLARE (SPECIAL DET))

;ВСПОМОГАТЕЛЬНЫЕ МАССИВЫ И ПЕРЕМЕННЫЕ

(DECLARE (SPECIAL PAR))

(DECLARE (SPECIAL R))

(DECLARE (SPECIAL T_))

(DECLARE (SPECIAL I))

(DECLARE (SPECIAL II))

;*********************

(SETQ R (MAKE-ARRAY SIZE :ELEMENT-TYPE ‘FLOAT :INITIAL-ELEMENT 0))

(SETQ T_ 1)

(SETQ DET 1)

(DO

((J 0))

((>= J (- SIZE 1)))

;ИСКЛЮЧАЕМ ДЕЛЕНИЕ НА 0

(IF (= (AREF MATRIX J J) 0)

(PROGN

(SETQ II (+ J 1))

;ИЩЕМ СТРОКУ В КОТОРОЙ J-Й ЭЛЕМЕНТ НЕ 0

(DO

(())

((OR (/= (AREF MATRIX II J) 0) (= II (- SIZE 1))))

(SETQ II (+ II 1))

)

;ЕСЛИ НЕТ ТАКОЙ СТРОКИ ОПРЕДЕЛИТЕЛЬ РАВЕН 0

(IF (AND (= (AREF MATRIX II J) 0) (= II (- SIZE 1))) (SETQ T_ 0))

;МЕНЯЕМ J СТРОКУ И НАЙДЕННУЮ

(DO

((K 0))

((>= K SIZE))

(SETF (AREF R K) (AREF MATRIX J K))

(SETF (AREF MATRIX J K) (AREF MATRIX II K))

(SETF (AREF II K) (AREF R K))

(SETQ K (+ K 1))

)

)

)

;ПРЯМОЙ ХОД

;ПРИВЕДЕНИЕ К ТРЕУГОЛЬНОМУ ТИПУ

(DO

((I (+ J 1)))

((>= I SIZE))

;ЕСЛИ (AREF MATR I J)=0 ДЕЛАТЬ НИЧЕГО НЕ НАДО

(IF (/= (AREF MATRIX I J) 0)

(PROGN

(SETQ PAR (/ (AREF MATRIX I J) (AREF MATRIX J J)))

(DO

((JJ J))

((>= JJ SIZE))

(SETF (AREF MATRIX J JJ) (* (AREF MATRIX J JJ) PAR))

(SETF (AREF MATRIX I JJ) (- (AREF MATRIX I JJ) (AREF MATRIX J JJ)))

(SETF (AREF MATRIX J JJ) (/ (AREF MATRIX J JJ) PAR))

(SETQ JJ (+ JJ 1))

)

)

)

(SETQ I (+ I 1))

)

(SETQ J (+ J 1))

)

(IF (/= T_ 0)

(PROGN

(DO

((I 0))

((>= I SIZE))

(SETQ DET (* DET (AREF MATRIX I I)))

(SETQ I (+ I 1))

)

)

;ИНАЧЕ

(SETQ DET 0)

)

;ВОЗВРАЩАЕМ ОПРЕДЕЛИТЕЛЬ

DET

)

(SETQ N 0)

(SETQ INPUT_STREAM (OPEN ” D:\MATRIX. TXT” :DIRECTION :INPUT))

;РАЗМЕР МАТРИЦЫ

(SETF N (READ INPUT_STREAM))

(SETQ MATR (MAKE-ARRAY (LIST N N) :ELEMENT-TYPE ‘FLOAT :INITIAL-ELEMENT 0))

(SETF MATR (READ INPUT_STREAM))

(CLOSE INPUT_STREAM)

(SETQ DETERM (DETERMINANT MATR N))

;РЕЗУЛЬТАТ

(SETQ OUTPUT_STREAM (OPEN ” D:\DETERMINANT.TXT” :DIRECTION :OUTPUT))

;ЗАПИСЫВАЕМ ОПРЕДЕЛИТЕЛЬ

(PRINT ‘DETERMINANT OUTPUT_STREAM)

(PRINT DETERM OUTPUT_STREAM)

;ЗАКРЫВАЕМ ФАЙЛ

(TERPRI OUTPUT_STREAM)

(CLOSE OUTPUT_STREAM)

5 Пример выполнения программы

Пример 1.

Рисунок 2 – Входные данные

Рисунок 3 – Выходные данные

Пример 2.

Рисунок 4 – Входные данные

Рисунок 5 – Выходные данные

Пример 3.

Рисунок 6 – Входные данные

Рисунок 7 – Выходные данные

Заключение

Проблема повышения качества вычислений, как несоответствие между желаемым и действительным, существует и будет существовать в дальнейшем. Ее решению будет содействовать развитие информационных технологий, которое заключается как в совершенствовании методов организации информационных процессов, так и их реализации с помощью конкретных инструментов – сред и языков программирования.

Итогом работы можно считать созданную функциональную модель для вычисления определителя методом исключения Гаусса. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.

Список использованных источников и литературы

  1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с.

  2. Васильев, Ф.П. Численные методы решения экстремальных задач. [Текст] / Ф.П. Васильев – М.: Наука, 2002. C. 415.

  3. Калиткин, Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. – М.: Питер, 2001. С. 504.

  4. Кнут, Д.Э. Искусство программирования. Основные алгоритмы [Текст] / Д.Э. Кнут. – М.: Вильямс, 2007. Т.1. – 712 с.

  5. Метод Гаусса [Электронный ресурс] – Режим доступа: http://www.wikipedia.org/wiki/Метод_Гаусса.

  6. Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.

  7. Симанков, В. 2-{\color{Red} \alpha } -1 & {\color{Red} \alpha } +1 \end{array} \right| \ . $$

    Решение. Разложение по общей формуле даст величину этого определителя в виде полинома от $ {\color{Red} \alpha } $. С другой стороны, если для его вычисления мы попытаемся применить метод Гаусса, то на первом же шаге элементы преобразованного определителя окажутся дробно–рациональными функциями от параметра $ {\color{Red} \alpha } $. Понятно, что после приведения определителя к треугольному виду и перемножения стоящих на диагонали дробей мы, в конце концов, получим тот же ответ полиномиального вида, но сам факт, что для его получения потребовалось «выйти за пределы» множества полиномиальных функций не свидетельствует в пользу метода Гаусса… ♦

    Универсальных методов вычисления подобных определителей (отличных, естественно, от определения) не существует. Успех во многом будет зависеть от искусства вычислителя. Здесь мы покажем несколько полезных приемов, которые иногда помогают.

    Выделение линейных множителей

    Этот прием основан на свойстве полиномиальности определителя как функции его элементов. Если элементы зависят — также полиномиально — от одного параметра, то можно попытаться определить линейные множители «полинома из ответа»: иногда из особенностей определителя очевидно при каких значениях параметра этот определитель обращается в нуль.

    П

    Пример. Вычислить определитель

    $$\left|\begin{array}{ccccc} 1&1&1&\dots&1\\ 1&2-x&1&\dots&1\\ 1&1&3-x&\dots&1\\ \vdots& & &\ddots&\vdots\\ 1&1&1&\dots&n+1-x \end{array}\right|.$$

    Решение. Ответом в этой задаче должен быть полином по $ x_{} $. Обозначим его $ F(x)_{} $ и попробуем догадаться какие корни он может иметь. Обратим внимание на структуру определителя. Если положить $ x=1_{} $, то вторая строка будет одинаковой с первой, на основании свойства 3 определителя, при этом значении $ x_{} $ будем иметь $ F(1)=0 $. Аналогично убеждаемся, что $ F(2)=0, \dots, F(n)=0 $. Итак, на основании теоремы Безу, имеем: $$ F(x) \equiv F_1(x) (x-1)\times \dots \times (x-n) \ , $$ где через $ F_1(x) $ обозначен полином, являющийся частным от деления $ F(x)_{} $ на произведение линейных множителей. Оценим степень полинома $ F(x)_{} $. Очевидно, что при разложении определителя по общей формуле из определения, каждое слагаемое представляет произведение элементов определителя и будет полиномом по $ x_{} $. В каждом слагаемом максимально возможная степень может быть достигнута если каждый элемент в произведении будет иметь максимально возможную степень — в нашем случае равную $ 1_{} $. Отсюда с неизбежностью следует, что самым «большим» по степени может быть только главный член определителя, т.е. произведение элементов его главной диагонали: $$ F(x) \equiv 1\cdot (2-x)\times \dots \times (n+1-x) + \dots \ , $$ где многоточия скрывают все оставшиеся слагаемые полного разложения определителя и имеют степени меньшие степени выделенного слагаемого. 2 \ . $$

    Метод рекуррентных соотношений

    Основная идея метода заключается в том, что некоторые определители можно свести к вычислению определителей, имеющих аналогичный вид, но меньший порядок. Если удается установить вид этой зависимости в виде явной формулы, то эта формула — последовательным ее применением — позволит нам «спуститься» к определителям малых порядков.

    П

    Пример. Вычислить определитель

    $$D_n=\left|\begin{array}{ccccc} a_1&x&x&\dots&x\\ x&a_2&x&\dots&x\\ x&x&a_3&\dots&x\\ \vdots&&&\ddots&\vdots\\ x&x&x&\dots&a_n \end{array}\right|.$$

    Решение. Представив элемент в правом нижнем углу в виде $ a_n=x+(a_n-x) $, можем определитель $ D_n $ разбить на сумму двух определителей: $$D_n=\left|\begin{array}{ccccc} a_1&x&x&\dots&x\\ x&a_2&x&\dots&x\\ x&x&a_3&\dots&x\\ \vdots&&&\ddots&\vdots\\ x&x&x&\dots&x \end{array}\right|+\left|\begin{array}{ccccc} a_1&x&x&\dots&0\\ x&a_2&x&\dots&0\\ x&x&a_3&\dots&0\\ \vdots&&&\ddots&\vdots\\ x&x&x&\dots&a_n-x \end{array}\right|. $$ В первом определителе последний столбец вычтем из остальных, а второй определитель разложим по последнему столбцу: $$D_n=x(a_1-x)(a_2-x)\times\dots\times(a_{n-1}-x)+(a_n-x)D_{n-1}\ .$$ Это и есть рекуррентное соотношение. Подставляя в него аналогичное выражение для $ D_{n-1} $, найдем $$\begin{array}{l} D_n=x(a_1-x)(a_2-x)\times\dots\times(a_{n-1}-x)+\\ +x(a_1-x)(a_2-x)\times\dots\times(a_{n-2}-x)(a_n-x)+D_{n-2}(a_{n-1}-x)(a_n-x). \end{array}$$ Повторяя то же рассуждение $ n-1 $ раз и замечая, что $ D_1=a_1=x+(a_1-x) $, найдем $$\begin{array}{l} D_n=x(a_1-x)(a_2-x)\dots(a_{n-1}-x)+x(a_1-x)\times\dots\times(a_{n-2}-x)(a_n-x)+\dots+\\ +x(a_2-x)\times\dots\times(a_n-x)+(a_1-x)(a_2-x)\times\dots\times(a_n-x)=\\ \displaystyle =x(a_1-x)(a_2-x)\times\dots\times(a_n-x)\left( \frac{1}{x}+\frac{1}{a_1-x}+\dots+\frac{1}{a_n-x}\right). \end{array}$$

    ?

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

    $$\left|\begin{array}{ccccc} a_1b_1&a_1b_2&a_1b_3&\dots&a_1b_n\\ a_1b_2&a_2b_2&a_2b_3&\dots&a_2b_n\\ a_1b_3&a_2b_3&a_3b_3&\dots&a_3b_n\\ \vdots&&&&\vdots\\ a_1b_n&a_2b_n&a_3b_n&\dots&a_nb_n \end{array}\right|. {n-1}(a_{j+1}b_j-a_jb_{j+1}) $ .

    П

    Пример. Вычислить определитель

    $$D_n=\left|\begin{array}{ccccc} a_1&x&x&\dots&x\\ y&a_2&x&\dots&x\\ y&y&a_3&\dots&x\\ \vdots&&&\ddots&\vdots\\ y&y&y&\dots&a_n \end{array}\right|.$$

    Решение начинается тем же приемом, что и в предыдущем примере: $$ D_n= \left|\begin{array}{ccccc} a_1&x&x&\dots&x\\ y&a_2&x&\dots&x\\ y&y&a_3&\dots&x\\ \vdots&&&\ddots&\vdots\\ y&y&y&\dots&x \end{array}\right|+(a_n-x)D_{n-1}=x(a_1-y)(a_2-y)\times \dots \times (a_{n-1}-y)+(a_n-x)D_{n-1} \ . $$ Можно было бы идти по проторенному пути и «разделывать» определитель $ D_{n-1} $ с использованием уже полученной формулы. Имеется, однако, более эффективный прием. Заметим, что начальный определитель симметричен относительно вхождения параметров $ x_{} $ и $ y_{} $, и эта симметрия должна проявляться в окончательном ответе. 2 \end{array}\right| \ . $$ Но этот определитель — тот же определитель Вандермонда, только порядка меньшего исходного. Возвращая переменной $ x $ ее исходное значение, получаем рекуррентное соотношение: $$ V(x_1,x_2,x_3,x_4)\equiv V(x_1,x_2,x_3) (x_4-x_1)(x_4-x_2)(x_4-x_3) \ . $$ Раскладываем определитель в правой части по той же схеме: $$ V(x_1,x_2,x_3) \equiv \left|\begin{array}{ll} 1 &x_1\\ 1 &x_2 \end{array}\right| (x_3-x_1)(x_3-x_2) \equiv (x_3-x_1)(x_3-x_2)(x_2-x_1) \ . $$ Таким образом, $$ V(x_1,x_2,x_3,x_4)= $$ $$ =(x_2-x_1)(x_3-x_1)(x_3-x_2)(x_4-x_1)(x_4-x_2)(x_4-x_3) \ . $$ А в общем случае получаем ответ $$ V(x_1,\dots,x_n)= \prod_{1\le j < k \le n} (x_k-x_j)\ . $$ ♦

    Определитель трёхдиагональной матрицы

    Более сложный пример применения метода дает задача вычисления определителя трехдиагональной матрицы, представленного в следующем виде (определитель Якоби):

    $$ {\mathfrak J}_n = \left|\begin{array}{ccccccc} a_1 &b_1&0&0& \dots & 0 & 0\\ -c_2 &a_2&b_2&0& \dots & 0 & 0\\ 0 &-c_3&a_3&b_3& \dots & 0 & 0\\ \vdots &&& &\ddots&& \vdots \\ 0 &0&0&0& \dots & a_{n-1} & b_{n-1}\\ 0 &0&0&0& \dots & -c_n & a_{n} \end{array}\right|_{n\times n} \ . $$ Формальное вычисление этого определителя (в соответствии с определением) даст полином по $ a_1,\dots,a_n,b_1,\dots,b_{n-1},c_2,\dots,c_n $, линейный по каждой из этих переменных. Если разложить $ {\mathfrak J}_n $ по последней строке, то получим: $$ \begin{matrix} {\mathfrak J}_n&=&a_n{\mathfrak J}_{n-1}+b_{n-1}c_n{\mathfrak J}_{n-2} =a_n(a_{n-1}{\mathfrak J}_{n-2}+b_{n-2}c_{n-1}{\mathfrak J}_{n-3})+ b_{n-1}c_n{\mathfrak J}_{n-2}= \\ &=&(a_na_{n-1}+b_{n-1}c_n){\mathfrak J}_{n-2}+a_nb_{n-2}c_{n-1}{\mathfrak J}_{n-3}= \dots \end{matrix} $$

    П

    Пример.

    $ {\mathfrak J}_2=a_1a_2+b_1c_2 $ , $ {\mathfrak J}_3=a_1a_2a_3+a_1b_2c_3+b_1c_2a_3 $, $$ {\mathfrak J}_5=a_1a_2a_3a_4a_5+b_1c_2a_3a_4a_5+a_1b_2c_3a_4a_5+a_1a_2b_3c_4a_5 +a_1a_2a_3b_4c_5+b_1c_2b_3c_4a_5+b_1c_2a_3b_4c_5+a_1b_2c_3b_4c_5 \ . $$

    Т

    Теорема. Значение $ {\mathfrak J}_n $ равно сумме главного члена $ a_1a_2\times \dots \times a_{n} $ и всевозможных произведений, получающихся из него заменой одной или нескольких пар соседних множителей $ a_ja_{j+1} $ на $ b_jc_{j+1} $.

    Частный случай определителя Якоби — континуант: $$ Q_n(x_1,x_2,\dots,x_{n}) = \left|\begin{array}{ccccccc} x_1 &1&0&0& \dots & 0 & 0\\ -1 &x_2&1&0& \dots & 0 & 0\\ 0 &-1&x_3&1& \dots & 0 & 0\\ \vdots &&& &\ddots&&\vdots \\ 0 &0&0&0& \dots & x_{n-1} & 1\\ 0 &0&0&0& \dots & -1 & x_{n} \end{array}\right|_{n\times n} $$

    Т

    Теорема. Континуант равен сумме произведения $ x_1\cdot x_2 \times \dots \times x_n $ и всевозможных произведений, получающихся из него вычеркиванием пар соседних множителей (и добавлением $ 1 $ в случае четного $ n $).

    П

    Пример.

    $$ \begin{array}{lcl} Q_2(x_1,x_2)&=&x_1x_2+1 \ , \\ Q_3(x_1,x_2,x_3)&=& x_1x_2x_3+x_3+x_1 \ , \\ Q_6(x_1,x_2,x_3,x_4,x_5,x_6)&=&x_1x_2x_3x_4x_5x_6+\\ &&+x_3x_4x_5x_6 +x_1x_4x_5x_6+ x_1x_2x_5x_6+ x_1x_2x_3x_6+x_1x_2x_3x_4+ \\ &&+x_5x_6+x_1x_6+x_1x_2+x_1x_4+x_3x_4+x_3x_6+1 . \end{array} $$

    Исследуем еще один частный случай определителя Якоби — при одинаковых элементах на диагоналях $$a_1=\dots=a_n = a, \ b_1=\dots=b_{n-1} = b, \ c_2=\dots=c_n = c \ ; $$ таким образом: $$ {\mathfrak J}_n= \left|\begin{array}{ccccccc} a &b&0&0& \dots & 0 & 0\\ c &a&b&0& \dots & 0 & 0\\ 0 &c&a&b& \dots & 0 & 0\\ \vdots &&& &\ddots&& \vdots \\ 0 &0&0&0& \dots & a & b\\ 0 &0&0&0& \dots & c & a \end{array}\right|_{n\times n} \ . $$ В этом случае уравнение, связывающее определители трех последовательных порядков, принимает вид: $$ {\mathfrak J}_n=a{\mathfrak J}_{n-1}-bc{\mathfrak J}_{n-2} \ .$$ Оно может быть решено применением общего приема решения линейного разностного уравнения.

    П

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

    $$ \left|\begin{array}{cccccc} 2 &2&0& \dots & 0 & 0\\ 1 & 2 &2& \dots & 0 & 0\\ 0 &1&2& \dots & 0 & 0\\ \vdots && \ddots &\ddots&& \vdots\\ 0 &0&0& \dots & 2 & 2\\ 0 &0&0& \dots & 1 & 2 \end{array}\right|_{n\times n} \ . n $ определителей.

    Если при каждом разложении за первые слагаемые принимать числа $ a_i $, а за вторые — числа $ b_j $, то строки полученных определителей будут либо вида $ (a_i,a_i,\dots,a_i) $, либо вида $ (b_1,b_2,\dots,b_n) $. Две строки первого типа пропорциональны, а второго типа равны. При $ n>2 $ в каждый получившийся определитель попадут по крайней мере две строки одного типа, и он обратится в нуль. Таким образом, $$D_n=0 \ npu \ n>2,\ D_1=a_1+b_1,\quad D_2=\left|\begin{array}{cc} a_1&a_1\\ b_1&b_2 \end{array}\right|+\left|\begin{array}{cc} b_1&b_2\\ a_2&a_2 \end{array}\right|=(a_1-a_2)(b_2-b_1).$$

    ?

    Вычислить определитель методом представления его в виде суммы определителей

    $$\left|\begin{array}{ccccc} x_1&a_1b_2&a_1b_3&\dots&a_1b_n\\ a_2b_1&x_2&a_2b_3&\dots&a_2b_n\\ a_3b_1&a_3b_2&x_3&\dots&a_3b_n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ a_nb_1&a_nb_2&a_nb_3&\dots&x_n \end{array}\right|. {n-1} = \left| \begin{array}{llll} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} \\ \dots & & & \dots \\ s_{n-1}x-s_{n} & s_{n}x-s_{n+1} & \dots & s_{2n-2}x-s_{2n-1} \end{array} \right|_{n\times n} $$ при заданных числовых значениях $ s_0,s_1,\dots,s_{2n-1} $.

    Решение. Здесь каждый элемент определителя зависит от переменной $ x $. Как уже отмечалось в начале раздела, применение метода Гаусса к вычислению такого определителя неэффективно. Сформируем новый определитель порядка $ n+1 $, дополнив исходный одной строкой и одним столбцом: $$ \left| \begin{array}{llllc} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-1}x-s_{n } & s_{n}x-s_{n+1} & \dots & s_{2n-2}x-s_{2n-1}& 0 \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ . $$ Разложение нового определителя по последнему столбцу приведет к исходному определителю. С другой стороны, выполним элементарные преобразования нового определителя: прибавим последнюю строку к предпоследней: $$ \left| \begin{array}{llllc} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-1}x & s_{n}x & \dots & s_{2n-2}x& 1 \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ ; $$ вынесем общий множитель: $$ x\left| \begin{array}{llllc} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ ; $$ предпоследнюю строку прибавим к предыдущей: $$ x\left| \begin{array}{llllc} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-2}x & s_{n-1}x & \dots & s_{2n-3}x& 1/x \\ s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ ; $$ и снова вынесем общий множитель: $$ x^2\left| \begin{array}{lllll} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-2} & s_{n-1} & \dots & s_{2n-3}& 1/x^2 \\ s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ . {n} \end{array} \right|_{(n+1)\times (n+1)} \ . $$ Получившийся определитель имеет порядок больший исходного. Тем не менее, выражения его элементов стали проще с той точки зрения, что переменная оказалась «выметена на край» определителя. Если разложить теперь определитель по последнему столбцу, то коэффициентами при степенях $ x $ становятся числовые определители, для вычисления которых уже можно применять метод Гаусса. ♦

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

    Интерполяция

    Для понимания материалов настоящего раздела рекомендуется ознакомиться с разделом “ИНТЕРПОЛЯЦИЯ”. .

    Можно считать излагаемый ниже метод обобщением приведенного выше метода выделения линейных множителей: если матрица имеет полиномиальную зависимость от параметра (параметров), то угадать корни ее определителя — также полинома от этого параметра — удается не всегда, а вот его значения при конкретных величинах параметра (параметров) всегда можно вычислить. 8 $.

    Итак, неизвестный полином $ F(\alpha) $ имеет степень $ 8_{} $. Для его определения у нас имеется представление этого полинома в форме определителя. При этом считается, что числовые определители мы вычислять умеем. Будем искать полином $ F(\alpha) $ как решение задачи интерполяции. Зададим произвольные числовые значения для $ \alpha_{} $ — в количестве $ 9_{} $ штук (по числу коэффициентов полинома, требующих определения), вычислим соответствующие числовые определители, составим интерполяционную таблицу: $$ \begin{array}{c|cccc} \alpha & \alpha_1 & \alpha_2 & \dots & \alpha_9 \\ \hline F & \det A (\alpha_1) &\det A (\alpha_2) & \dots & \det A (\alpha_9) \end{array} $$ и вычислим $ F(\alpha) $ по одному из методов вычисления интерполяционного полинома.

    На виду лежат два соображения:

    1. имеет смысл в качестве чисел $ \alpha_j $ выбирать возможно минимальные по модулю;

    2. 2-3\,\alpha-4 $.

    При решении примера настоящего пункта мы столкнулись со следующей задачей. Составим матрицу степеней полиномов, содержащихся в матрице $ A_{} $:

    $$ B=\left( \begin{array}{cccc} 1 &2 &2 &1 \\ 2 &2 &2 & 0 \\ 1 &2 &1 & 2 \\ 1 & 2 & 2 & 1 \end{array} \right) \ . $$ Требуется выбрать по одному элементу из каждой строки и каждого столбца этой матрицы, так, чтобы получившаяся сумма стала максимальной: $$ b_{1j_1}+b_{2j_2}+b_{3j_3}+b_{4j_4} \quad \mbox{ при различных } \quad \{ j_1,j_2,j_3,j_4\} \subset \{ 1,2,3,4 \} . $$ Иными словами, после выбора какого-то кандидата в сумму, из матрицы вычеркиваются строка и столбец его содержащие, и дальнейший выбор осуществляется в оставшейся подматрице. Задача оказывается нетривиальной уже хотя бы потому, что «жадная стратегия» выбора — когда на каждом шаге выбирается максимальный из оставшихся элементов — не приводит к правильному ответу: $$ B=\left( \begin{array}{cc} 4 &3 \\ 3 &1 \end{array} \right) \quad \Rightarrow \quad 4+1 < 3 + 3 \ . 2} \prod_{0\le k < j \le 2n} \sin \frac{x_k-x_j}{2} \ . $$ Рассматривается ☞ ЗДЕСЬ.

    [1]. Микеладзе Ш.Е. Решение численных уравнений. Тбилиси.Мецниереба. 1965

    algebra2/dets/special_cases.txt · Последние изменения: 2021/09/28 00:26 — au

    50398 (Вычисление определителя матрицы прямым методом) – документ

    Размещено на http://www.allbest.ru/

    Федеральное агентство по образованию

    Государственное образовательное учреждение высшего профессионального образования

    Тульский государственный университет

    Кафедра “Автоматика и телемеханика”

    ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ

    по дисциплине: «Программирование на языке высокого уровня»

    на тему: «Вычисление определителя матрицы прямым методом»

    Выполнил: студент группы 260661

    Ю.В. Красов

    Проверил: ассистент кафедры АТМ

    А. С. Карцева

    Тула 2008

    СОДЕРЖАНИЕ

    ВВЕДЕНИЕ

    1. ВЫБОР И ОБОСНОВАНИЕ ЧИСЛЕННОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ

      1. Определение матрицы

      2. Определение детерминанта

      3. Метод исключения Гаусса. Вычисление определителя методом исключения

    1. АЛГОРИТМ РАБОТЫ ПРОГРАММЫ

      1. Структура алгоритма и данных

      2. Схема алгоритма

    1. ТЕКСТ ПРОГРАММЫ

      1. Описание переменных и структур данных

      2. Текст программы на языке Pascal

  8. ТЕСТОВАЯ ЗАДАЧА

    1. Математическое решение задачи

    2. Решение, полученное с использованием разработанного программного обеспечения

  9. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

  10. ЗАКЛЮЧЕНИЕ

    СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

    ВВЕДЕНИЕ

    Современная математика ориентирована на использование компьютеров для прикладных расчетов. Любые математические приложения начинаются с построения модели явления (изделия, действия, ситуации или другого объекта), к которому относится изучаемый вопрос. Классическими примерами математических моделей могут служить определенный интеграл, уравнение колебаний маятника, уравнение теплообмена, уравнения упругости, уравнения электромагнитных волн и другие уравнения математической физики и даже модель формальных рассуждений – алгебру Буля.

    Основополагающими средствами изучения математических моделей являются аналитические методы: получение точных решений в частных случаях (например, табличные интегралы), разложения в ряды. Определенную роль издавна играли приближенные вычисления. Например, для вычисления определенного интеграла использовались квадратурные формулы.

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

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

    С использованием компьютера стал возможен вычислительный эксперимент, т. e. расчет в целях проверки гипотез, а также в целях наблюдения за поведением модели, когда заранее не известно, что именно заинтересует исследователя. В процессе численного эксперимента происходит по существу уточнение исходной математической постановки задачи. В процессе расчетов на компьютере происходит накопление информации, что дает возможность в конечном счете произвести отбор наиболее интересных ситуаций. На этом пути сделано много наблюдений и открытий, стимулирующих развитие теории и имеющих важные практические применения.

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

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

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

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

    1. ВЫБОР И ОБОСНОВАНИЕ ЧИСЛЕННОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ

      1. Определение матрицы

    Матрицей называют совокупность чисел, расположенных в прямоугольной таблице

    ,

    состоящей из m строк и n столбцов.

    Числа называют элементами матрицы. Первый индекс в обозначении элемента ( i ) указывает на номер строки, а второй индекс ( j )- на номер столбца, в которых расположен этот элемент.

    В нашем случае ( ) матрица называется прямоугольной размера . Если число строк в матрице равно числу столбцов (m=n), то матрицу называют квадратной порядка m.

      1. Определение детерминанта

    Для квадратной матрицы может быть введено понятие детерминанта (определителя). Детерминант матрицы [A] обозначают

    6

    или .

    Детерминантом матрицы порядка n>1 называют число

    , (1)

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

    Матрица порядка 1 состоит из одного числа, и ее детерминант по определению считают равным этому числу:

    (2)

    Детерминант матрицы второго порядка в соответствии с (1) и (2) можно вычислить по следующей формуле:

    .

    Для матрицы третьего порядка

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

    Число называют дополнительным минором элемента . Для произвольного элемента матрицы также можно ввести понятия дополнительного минора: – это определитель матрицы, получаемой из исходной вычеркиванием i -ой строки и j-ого столбца. Например, для матрицы [A] третьего порядка дополнительным минором элемента будет определитель

    Одним из важных свойств определителей является то, что при перестановке местами двух строк или двух столбцов определителя, он должен быть умножен на -1:

    .

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

      1. Метод исключения Гаусса. Вычисление определителя методом исключения

    Пусть дана матрица

    Метод Гаусса можно интерпретировать как метод, в котором матрица приводится к верхней треугольной форме (прямой ход).

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

    Запишем общие формулы метода Гаусса. Пусть проведено исключение к элементов из (k-1)-го столбца. Тогда останутся строки с ненулевыми элементами ниже главной диагонали.

    Умножим k-ю строку на число

    m > k (3)

    и вычтем из m-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам

    ( 4)

    k

    Проведя вычисления по этим формулам при всех указанных индексах, обратим в нуль элементы k-го столбца, лежащие ниже главной диагонали. Аналогичная процедура приводит матрицу системы к верхней треугольной форме, при этом весь процесс приведения называется прямым ходом метода Гаусса.

    Определитель треугольной матрицы равен произведению диагональных элементов. В результате выполнения прямого хода метода исключения система линейных уравнений приводится к верхней треугольной матрице. Следовательно, определитель матрицы системы может быть вычислен как произведение диагональных элементов:

    (6)

    где k- количество перестановок строк при использовании метода исключения с выбором главного элемента.

    На некотором шаге прямого хода может оказаться, что коэффициент но мал по сравнению с остальными элементами матрицы системы и, в частности, мал по сравнению с элементами первого столбца. Деление коэффициентов системы на малую величину может привести к значительным ошибкам округления.

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

    Важным достоинством данного метода, является то, что вычисление определителя требует примерно (2/3)n³ операций, что несравнимо меньше с операциями, при вычислении определителя по правилу Крамера, поэтому метод Гаусса с выбором главного элемента наиболее применим при обработке данных на компьютере.

    Визуализация исключения Гаусса. Определитель связан с… | Николя Бертаньолли

    Определитель связан с объемом параллелепипеда, натянутого на векторы в матрице, давайте посмотрим, как.

    Недавно меня попросили создать видео, демонстрирующее, как преобразование матрицы в форму редуцированного эшелона строк (RREF) раскрывает определитель. Я знаю, это звучит неправдоподобно, но это произошло. Цель этого поста не в том, чтобы описать все свойства определителя, и не в том, чтобы объяснить, как работает исключение Гаусса, для этого есть много других ресурсов, а в том, чтобы показать изящную демонстрацию того, как геометрия матрицы связанный с определителем, и что преобразование матрицы в RREF раскрывает объем этого геометрического объекта. Прежде всего, давайте подумаем о том, как рассматривать матрицу геометрически. На протяжении всего обсуждения я буду использовать матрицу:

    Один из способов представить эту матрицу как набор векторов-строк, которые можно увидеть на рисунке 1.

    Эта матрица связана с параллелограммом на рисунке 2, где абсолютное значение определяющим является его объем. Мы проверим это в конце, а пока просто доверься мне.

    Берем определитель ad bc = 1.Это здорово, и большинство из вас уже знают, как вычислить определитель, но как к этому приводит сокращение строк в матрице? Когда мы уменьшаем матрицу, мы начинаем концентрировать значения на диагонали матрицы. Это в основном эквивалентно выравниванию векторов с декартовыми осями. Чтобы увидеть это, давайте сделаем шаг в сторону сокращенной формы строки для матрицы A . Давайте несколько раз снимем .1 × A_1 с A_2 и посмотрим, что получится.

    Мы видим, что нижний вектор постепенно выравнивается с каноническими осями x, y! Если мы сделаем то же самое, но вычтем A_2 из A_1, мы выровняем другой вектор. Это означает, что еще один способ просмотра уменьшенной эшелонированной формы строки – это выровненная по оси версия исходной матрицы. Это можно увидеть на видео ниже.

    Визуализация исключения Гаусса

    Теперь мы можем легко вычислить объем этого уменьшенного параллелограмма, потому что высота и размеры основания являются просто диагональными элементами, и они оба равны 1, подразумевая, что объем равен 1.

    Чтобы убедиться, что объем исходного параллелограмма равен 1 мы можем использовать стандартный расчет Volume = Base × Height.Прежде чем начать этот путь, нам нужно подумать о нашей базе и высоте. Мы назовем нашу базу ||A_1||, и мы можем найти нашу высоту, используя формулу тригонометрии sin (θ) = противоположность / гипотенуза и скалярное произведение a⋅ b = ||a||||b|| потому что (θ). В этом контексте наша противоположная сторона ||A_2|| и теперь у нас есть все необходимое для расчета объема.

    Что действительно 1! Здесь мы убедились, что определители и объемы всех наших матриц одинаковы. Мы также можем видеть, как уменьшение матрицы изменяет геометрию лежащих в основе векторов, чтобы они были выровнены по осям и их было легче интерпретировать.Если вы хотите увидеть тот же процесс в более высоких измерениях, я сделал еще одно видео для матрицы 3 × 3.

    Визуализация исключения Гаусса на матрице 3×3

    Исключение Гаусса

    Исключение Гаусса

    Исключение Гаусса

    Гаусс (биография) разработал единственный практический алгоритм вычисления определителя больших матриц, и он используется до сих пор. Процедура известна как исключение Гаусса, или det6 в наших обозначениях. Он преобразует произвольную матрицу в верхнюю треугольную матрицу, затем применяет det5, как описано в предыдущем разделе.

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

    Если верхний левый элемент равен 0, просмотрите первый столбец вниз. и найти ненулевую запись. Если их нет, то столбец равен 0, как и определитель. В противном случае поменяйте местами две строки, так что верхний левый элемент не равен нулю. Это отрицает определитель; запишите это.

    Переместитесь вниз по первому столбцу и выполните операцию со строкой, когда запись отлична от нуля.Если M1,1 = x и Mi,1 = y, вычесть первую строку, умноженную на y/x, из i-й строки. Это не меняет определителя. Теперь первая запись в i-й строке равна 0. Когда мы закончим с первым столбцом, только верхняя запись будет отличной от нуля.

    Перейдите ко второму столбцу и спросите, равно ли M2,2 0. Если это так, найдите более низкую строку для замены, чтобы M2,2 было ненулевым. Если все в столбце 2, ниже строки 1, равно 0, перейдите к столбцу 3. Остановиться на столбце j, когда M2,j отличен от нуля, или под ним есть ненулевая запись, которая может участвовать в обмене.Не забудьте инвертировать определитель, если вам нужно поменять местами строки. Как только ненулевая запись установлена, пробежать по столбцу и выполнить операции вычитания строк, чтобы остальная часть столбца стала 0.

    Когда исключение Гаусса завершено, у нас есть верхняя треугольная матрица. Перемножьте диагональные элементы вместе, чтобы получить определитель. Результат равен 0 тогда и только тогда, когда некоторые из диагональных элементов равны 0. Если мы обнаружим, например, что M2,2 равно 0 со всеми нулями под ним, мы можем остановиться прямо здесь.Что-то справа может быть ненулевым, и все записи ниже и справа от него также могут быть ненулевыми, но это все выше главная диагональ. Начиная с M2,2, на главной диагонали все нули. Конечно, это случается не очень часто; определитель матрицы обычно отличен от нуля.

    Этот алгоритм перебирает столбцы, затем петли над рядами ниже главной диагонали, затем перебирает столбцы справа от очищаемого столбца. Это выполняется за время n3 и пространство n2, предполагая ограничение на размер элементов в матрице.

    [PDF] определитель интервальной матрицы с использованием гауссовского метода устранения

    показаны 1-10 из 20 ссылок

    Сортировка Byrelevancancemost под влиянием Papercrections

    Обратная интервальная матрица: новый подход

    Мы предлагаем новый метод для вычисления обратного интервальной матрицы на основе модифицированной интервальной арифметики. Вводятся понятия определителя, регулярности и обратной матрицы интервала… Развернуть

    • Посмотреть 1 отрывок, библиографический список

    О некоторых свойствах интервальных матриц

    Используя новый набор арифметических операций над интервальными числами, мы обсудить некоторые арифметические свойства интервальных матриц, которые intern помогают нам вычислить степени интервальных матриц и… Expand

    Обратная интервальная матрица

    Обратная интервальная матрица определяется как самая узкая интервальная матрица, содержащая обратные значения всех матриц из заданного интервальная матрица.Как теоретические, так и практические результаты по… ​​Развернуть

    Интервальные методы для систем уравнений

    Предисловие Индекс символов 1. Основные свойства интервальной арифметики 2. Вложения для области значений функции 3. Матрицы и сублинейные отображения 4. Решение квадратно-линейных системы уравнений 5.… Expand

    Интервальный анализ в расширенном пространстве интервалов IR

    В этой статье показано, как можно использовать расширенное пространство интервалов IR для записи формул, теорем и доказательств в замкнутой форме, т. е.е. без использования левой и правой границ интервала. Итак, базовый… Expand

    • Посмотреть 6 выдержек, справочная информация

    Прикладная линейная алгебра и матричный анализ

    Линейные системы уравнений.- Матричная алгебра.- Векторные пространства.- Геометрические аспекты стандартных пространств.- Проблема собственных значений. – Геометрические аспекты абстрактных пространств.

    Об арифметических операциях над интервальными числами

    Используя метод сравнения интервальных чисел Сенгупты и Пала и новый набор арифметических операций над интервальными числами, предлагается теория изучения арифметических операций над интервальными числами.Expand
    • Просмотр 7 выдержек, библиография

    Методы и приложения интервального анализа

    Конечные представления Конечная оценка Конечная сходимость Вычислимые достаточные условия существования и сходимости Безопасные начальные области для итерационных методов Приложения к математическим… Expand

    (PDF) ОПРЕДЕЛИТЕЛЬ ИНТЕРВАЛЬНОЙ МАТРИЦЫ методом исключения Гаусса

    ОПРЕДЕЛИТЕЛЬ ИНТЕРВАЛЬНОЙ МАТРИЦЫ. .. 31

    ˜a22 = [3.2581,4.2419] ; ˜a23 = [−1,5,−0,5]

    Сокращенная матрица: ,4,2419] [-1,5,-0,5]

    [0,0] [-1,5,-0,5] [3,7,4,3] 

    Шаг 2: Элемент Pivot равен ˜m32 = [0,1179,0,4154] ˜a32 =˜

    0; ˜a33 = [3,2256,

    4,2411]. Следовательно, приведенная матрица имеет вид

    ˜

    B=

    [3,7,4,3] [−1,5,−0,5] [0,0]

    [0,0] [3.2581,4,2419] [-1,5,-0,5]

    [0,0] [0,0] [3,2256,4,2411] 

    .

    Теперь определитель ˜

    Bi является произведением элементов на его главной диагонали,

    и, следовательно, если мы вычислим определитель интервальной матрицы ˜

    A прямым путем из определения, мы получим

    A|=

    [3,7,4,3] [−1,5,−0,5] [0,0]

    [−1,5,−0,5] [3,7,4,3] [−1,5 ,−0,5]

    [0,0] [−1,5,−0.5] [3.7,4.3] 

    ≈[44.178,75.822] + [−7.075,−0.925]

    ≈[37.103,74.897]

    5 90 90

    Здесь мы видим, что |) = m(|˜

    B|) = 56. Следовательно, по теореме (4) и (5)

    имеем |˜

    A|≈ [38,8846,73,1159] .

    Пример 7. Использование алгоритма удаления гаусса, фиксируемое детерминант

    Интервальная матрица ~

    a, где ~

    a = 

    [4,6] [-1 ,1] [−1,1] [−1,1]

    [−1,1] [−6,−4] [−1,1] [−1,1]

    [−1,1] [−1,1] [9,11] [−1,1]

    [−1,1] [−1,1] [−1,1] [−11,−9]

    Шаг 1: Элемент Pivot равен ˜m21 = [−0.2333,0,2333]; ˜a21 =˜

    0; ˜a22 =

    [−6,2334, −3,7666]; ˜a23 = [−1,2334,1,2334]; ˜a24 = [−1,2334,1,2334].

    Элемент Pivot равен ˜m31 = [−0,2333,0,2333]; ˜a31 =˜

    0; ˜a32 = [−1,2334,1,2334];

    ˜a33 = [8,7666,11,2334]; ˜a34 = [−1,2334,1,2334].

    Элемент Pivot равен ˜m41 = [−0,2334,0,2334]; ˜a41 =˜

    0; ˜a42 = [−1,2334,1,2334];

    ˜a43 = [−1,2334,1,2334]; ˜a44 = [−11,2334, −8,7666]. Сокращенная матрица:

    [4,6] [−1,1] [−1,1] [−1,1]

    [0,0] [− 6. 2334,−3,7666] [−1,2334,1,2334] [−1,2334,1,2334]

    [0,0] [−1,2334,1,2334] [8,7666,11,2334] [−1,2334,1,2334]

    [0,0]02 [0,0] .

    Рандомизированное исключение Гаусса

    Рандомизированное исключение Гаусса
    Д. СТОТТ ПАРКЕР
    Департамент компьютерных наук Калифорнийского университета в Лос-Анджелесе
    3532 Boelter Hall
    (310) 825-6871 (OFC)
    (310) 825-1322 (SEC)
    (310) 825-2273 (ФАКС)

    • Как исключить разворот из исключения Гаусса
      — вместо рандомизации
      (Технический отчет CSD-950022) (Аннотация) (pdf) (пс)
    • Случайные превращения бабочки
      с приложениями в вычислительной линейной алгебре
      (Технический отчет CSD-950023) (Аннотация) (pdf) (пс)
    • Случайное преобразование бабочки
      Полезно в вычислениях блочной матрицы
      (Технический отчет CSD-950024) (Аннотация) (pdf) (пс)
    • Явные формулы для результатов исключения Гаусса
      (Технический отчет CSD-950025) (Аннотация) (pdf) (пс)
    • Две новые переформулировки исключения Гаусса
      (Технический отчет CSD-950026) (Аннотация) (pdf) (пс)
    • Дополнения Шура подчиняются категориальной грамматике Ламбека:
      другое представление исключения Гаусса и разложения LU
      (Технический отчет CSD-950027) (Аннотация) (pdf) (пс)
    • Еще раз о матричных алгоритмах Quadtree:
      Основные проблемы и их решение
      (Технический отчет CSD-950028) (Аннотация) (пс)
    • Рандомизирующее БПФ:
      альтернатива вращению в исключении Гаусса
      (Технический отчет CSD-950037) (Аннотация) (pdf) (пс)
    • Рандомизация ввода и автоматическое получение
      систолических массива для вычисления матрицы
      (Технический отчет CSD-950038) (Аннотация) (pdf) (пс)
    • Практические алгоритмы матрицы рекурсивной блочной декомпозиции, Алгоритмы
      и Quadtree с помощью рандомизации
      (Технический отчет CSD-950039) [пересмотрено в марте 1999 г. ] (Аннотация) (пс) (пс)
    • Блочное матричное обобщение исключения Гаусса-Жордана
      с использованием формулы отношения Хейнсворта для дополнений Шура
      (Технический отчет CSD-950063) (Аннотация) (pdf) (пс)
    • Блочная реализация случайного преобразования бабочки (Фортран) (выход)
    • Рекурсивная реализация случайного преобразования бабочки (Фортран) (выход)

      В настоящее время доступны версии FORTRAN которые сравнивают выполнение с dgefa/dgesl от LINPACK.Если вы хотите использовать этот исходный код, пожалуйста, свяжитесь с Стотт Паркер.


    Как устранить разворот из исключения Гаусса — вместо этого рандомизируя

    Д. Стотт Паркер и Дин Ле

    Исключение Гаусса, вероятно, является наиболее известным и наиболее широко используемым методом. метод решения линейных систем, вычисления определителей и нахождения матричные разложения. Хотя основная процедура устранения проста сформулировать и реализовать, становится сложнее с добавлением поворотной процедуры, которая работает с вырожденными матрицами, имеющими ноль элементов на диагонали. Поворот может значительно усложнить алгоритм, увеличить перемещение данных и снизить скорость, особенно на высокопроизводительных компьютерах.

    В этой статье мы предлагаем альтернативную схему выполнения гауссова исключение, которое сначала предварительно обусловливает входную матрицу путем ее умножения со случайными матрицами, чьи обратные могут быть применены впоследствии. В счет этих умножений и создание линейной системы плотной, если она еще не была, такой подход делает систему `невырожденные’ — подсистемы имеют полный ранг — с вероятностью 1.Эта предварительная подготовка приводит к (почти наверняка) устранению необходимость поворота.

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


    Случайные превращения бабочки с приложениями в вычислительной линейной алгебре

    Д. Стотт Паркер

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

    Исключение Гаусса — важный пример алгоритма, затронутого возможностью вырождения. При этом основная ликвидация процедура проста в формулировке и реализации, она усложняется с добавлением поворотной процедуры, которая обрабатывает вырожденные матрицы с нулями на диагонали.Поворот может значительно усложнить алгоритм, увеличить перемещение данных и снизить скорость, особенно на высокопроизводительных компьютерах.

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

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

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


    Случайное преобразование бабочки Полезно в вычислениях с блочной матрицей

    Д. Стотт Паркер

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

    В частности, в этой статье мы рассматриваем случайные матрицы, которые «случайные бабочки» и называют их приложение Random Butterfly. Трансформация (РБТ). RBT могут быть выполнены эффективно, и в особенно полезно на параллельных и векторных машинах с архитектуры, которые поддерживают вычисления, подобные БПФ.

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

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


    Явные формулы для Результаты исключения Гаусса

    Д. Стотт Паркер

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

    В этой статье мы воскресим характеристику поведения Исключение Гаусса, а именно, что каждый из его промежуточных результатов есть отношение определителей подматриц входной матрицы, и показать его эквивалентность другой характеристике в терминах Шура дополняет. Эти характеристики кажутся незнакомыми численных аналитиков, но заслуживают более широкого внимания, поскольку они приводят к глубокая признательность за исключение Гаусса.

    Характеристики можно использовать для получения границ округления. ошибка с исключением Гаусса. Характеристики также помогают в лучше понять влияние ошибки округления и поворота.


    Две новые переформулировки исключения Гаусса

    Д. Стотт Паркер

    В этой статье мы используем детерминантное тождество Сильвестра, чтобы вывести две переформулировки алгоритма исключения Гаусса. Один переформулировка устраняет необходимость в операциях деления, а другой дает промежуточные результаты, которые всегда являются специфическими детерминантами подматрицы входной матрицы. T-разложения когда А симметричен. Хотя они выполняют совсем другие вычисления чем традиционный алгоритм, они отличаются формально только лежащее в основе изменение переменных.

    Дополнения Шура подчиняются категориальной грамматике Ламбека: другой взгляд на исключение Гаусса и разложение LU

    Д. Стотт Паркер

    В течение двух десятилетий дополнения Шура находят все более широкое применение в линейная алгебра, часто как абстракции исключения Гаусса.это известно, что они подчиняются некоторым нетривиальным тождествам, таким как Crabtree и факторное свойство Хейнсворта. Мы начали эту работу с вопроса, есть ли были теорией для определения их свойств вообще.

    Категориальная грамматика Ламбека — дедуктивная система, введенная в 1958 г. Ламбек как математическая основа синтаксического исчисления английского языка предложения. Мы показываем, что категориальная грамматика дает дедуктивную систему для определения свойств LU- и UL-разложений, а также о гауссовских устранение. Его также можно использовать для получения тождеств, которым подчиняется Шур. дополняет.

    На первый взгляд это кажется странным результатом, соединяющим два несвязанные темы. Однако в ретроспективе это является следствием как оба используют частные. Он может найти применение в разработке как грамматические формализмы и числовые алгоритмы.


    Еще раз о матричных алгоритмах Quadtree: Основные вопросы и их решение

    Д. Стотт Паркер и Дин Ле

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

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

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


    Рандомизирующее БПФ: альтернатива повороту в методе исключения Гаусса

    Д. Стотт Паркер, Брэд Пирс

    Недавно были разработаны рандомизирующие входные преобразования для упрощение исключения Гаусса.Умножение на специальное разреженное случайных матриц эти преобразования дают эквивалентную линейную система, которую с вероятностью 1 может решить метод исключения Гаусса без какой-либо аугментации путем поворота.

    В этой статье мы изучаем свойства унитарного рандомизирующего дискретного Преобразование Фурье (RDFT), которое масштабирует строки по случайным значениям из комплексный единичный круг, а затем применяет обычное ДПФ. Когда размер задачи равен степени двойки, Рандомизированное быстрое преобразование Фурье (RFFT) алгоритм может эффективно реализовать RDFT, используя существующий FFT кода на множестве параллельных и векторных машин, архитектура которых поддерживают вычисления, подобные БПФ.


    Рандомизация ввода и автоматическое получение систолические массивы для вычисления матрицы

    Дин Ле, Д. Стотт Паркер, Брэд Пирс

    Многие стандартные матричные алгоритмы трудно реализовать как систолические. массивы, потому что они связаны с перемещением данных, которое не может быть определено априори, что приводит к высокой временной сложности. В случае плотного матричная инверсия, исключение Гаусса (GE) с поворотом в значительной степени были вытеснены альтернативными схемами, такими как вращения Гивенса и метод Грама-Шмидта, которые являются дорогостоящими и сложными, и более простой GE с попарным поворотом и GE без поворота, которые могут ломаться на “вырожденных” входах, т.е.е., обратимые матрицы с необратимыми подматрицы.

    Новый метод рандомизации ввода эффективно преобразует линейный задачу Ax=b в рандомизированную задачу VAx = Vb, где матрица V выбирается из специального класса случайных матриц. Если A неособо, тогда с вероятностью 1 можно успешно применить ОЭ без поворота к ВА. Как показано в расширенном учебном примере, этот простой алгоритм поддается компиляторам матричных алгоритмов текущего поколения, например, система MAMACG Калифорнийского университета в Лос-Анджелесе.


    Практические алгоритмы матрицы рекурсивной блочной декомпозиции, и алгоритмы Quadtree с помощью рандомизации

    Дин Ле, Д. Стотт Паркер

    Алгоритмы рекурсивной блочной декомпозиции (также известные как алгоритмы дерева квадрантов). когда все блоки квадратные) были предложены для решения известной такие задачи, как сложение матриц, умножение, обращение, вычисление определителя, блочное разложение LDU, дискретное преобразование Фурье преобразование, Холецкого и QR-факторизацию.

    До сих пор такие алгоритмы часто считались непрактичными для создание общих инструментов. В частности, рекурсивная блочная декомпозиция методы непрактичны для обращения матриц и исключения Гаусса, поскольку оба требуют, чтобы ведущие подматрицы входной матрицы были неособый (что не всегда гарантировано).

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


    Блочное матричное обобщение исключения Гаусса-Жордана используя формулу отношения Хейнсворта для дополнений Шура

    Брэд Пирс, Д. Стотт Паркер

    Алгоритм блочной матрицы для решения линейных систем получен с использованием Частная формула Хейнсворта для дополнений Шура.Алгоритм по существу, обобщение исключения Гаусса-Жордана.

    Линейные рандомизирующие преобразования: априорная альтернатива стратегиям динамического исключения например, частичный поворот

    Брэд Пирс, Д. Стотт Паркер

    Недавно мы сообщали о новой факторизации LU и блочной матрице. методы, использующие рандомизированное линейное предварительное обусловливание вместо динамического такие стратегии, как частичный или парный поворот.

Оставить комментарий

Ваш адрес email не будет опубликован.