Найти ранг матрицы методом окаймляющих миноров как: Вычисление ранга матрицы методом окаймляющих миноров.

Что такое ранг матрицы в математике

Оглавление

Время чтения::  7 минут

379

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

Ранги матриц

Определение

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

Объясним это понятие на примерах. Допустим нам дана матрица

\[\begin{array}{cccc} 1 & 5 & 9 & 13 \\ 2 & 6 & 10 & 14 \\ 3 & 7 & 11 & 15 \\ 4 & 8 & 12 & 16 \end{array}\]

Чтобы найти минор M₂₃ вычёркиваем из неё вторую строку и третий столбец. В результате получаем

\[\begin{array}{lll} 1 & 5 & 13 \\ 3 & 7 & 15 \\ 4 & 8 & 16 \end{array}\]

Это и есть искомый, нужный нам минор. Посмотрим матрицы низших порядков.

Если нам дана матрица первого порядка, то её минором будет сама эта матрица.

Если нам дана матрица второго порядка, допустим

\[\begin{array}{ll} 1 & 2 \\ 3 & 4 \end{array}\]

То её минорами будут M₁₁=4, M₁₂ = 3, M₂₁=2, M₂₂=1

Для матрицы порядка pxn число миноров k-го порядка равно C^k_p*C^k_n , где C^k_p=p!/k!(p-k)!, C^k_n=n!/k!(n-k)! являются числом сочетаний из p по k и из n по k.

Определение

Ранг матрицы — это максимальный порядок её миноров, для которых определитель не равен нулю. Обозначается ранг матрицы A, как rang A.

Из выше приведённого определения можно сделать два важных заключения:

1. Ранг любой ненулевой матрицы отличен от нуля;
2. Ранг нулевой матрицы равняется нулю.

Эквивалентными матрицами называют матрицы, которые имеют один и тот же ранг.

Методы нахождения ранга матрицы

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

Нет времени решать самому?

Наши эксперты помогут!

Контрольная

| от 300 ₽ |

Реферат

| от 500 ₽ |

Курсовая

| от 1 000 ₽ |

Нахождение ранга матрицы по определению

Нам нужно узнать, какой ранг матрицы А порядка p×n. Для нахождения ранга матрицы по определению последовательность действий и рассуждений следующая:

1. Проверяем миноры первого порядка. Если все они (именно все) в нашей матрице равны нулю, то rang A = 0;
2. Проверяем миноры второго порядка. Если они оказались равными нулю, то. rang A = 1;
3. Проверяем миноры третьего порядка. Если они нулевые, то rang A = 2.

Продолжаем исследования, каждый раз увеличивая порядок на один. Возможны следующие две ситуации:

1. Если среди миноров k-го порядка будет иметься хоть один, отличающийся от нуля, а все без исключения миноры (k+1)-го порядка окажутся нулевыми, то ранг будет равным k.
2. Если из миноров k-го порядка хоть один ненулевой, а миноры (k+1)-го порядка получить уже нельзя, то ранг матрицы тоже будет k.

Примеры

Пример 1. Требуется определить ранг матрицы A

\[\begin{array}{lllll}5 & 0 & -3 & 0 & 2 \\7 & 0 & -4 & 0 & 3 \\2 & 0 & -1 & 0 & 1\end{array}\]

Решение:

Т. к. размер матрицы 3 на 5, и минимальным из этих чисел является 3, то rang A≤ 3. Связано это с
тем, что миноры 4-го порядка из данной матрицы уже не создашь, предел достигнут.

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

Из миноров 2-го порядка \[\begin{array}{ll}5 & 0 \\7 & 0\end{array}\] равен нулю, поэтому смотрим
следующий минор. Ясно, что \[\begin{array}{ll}7 & 0 \\2 & 0\end{array}\] тоже будет равняться нулю.
Постараемся найти более удачные варианты. Возможно \[\begin{array}{ll}5 & 2 \\7 & 3\end{array}\]
нулю не будет равен. Вычислим его. 5*3 – 7*2 = 1.

Наши предположения оправдались. Так как нашёлся хоть один минор второго порядка, который не равен нулю, нужно
приступить к исследованию миноров третьего порядка. Выберем тот из них, в котором нет нулей, например:

\[\begin{array}{ccc}5 & -3 & 2 \\-7 & -4 & 3 \\2 & -1 & 1\end{array}\]

Вычисляем его. -20 — 18 — 14 + 16 + 21 + 16 = 0. Как видим, он нулевой. Исследовав другие миноры третьего
порядка тоже узнаем, что они тоже нулевые. Нет ни одного отличного от нуля. Следовательно, rang A = 2.
Задачу можно считать решённой.

Ответ: rang A = 2.

---

Пример 2. Определить ранг матрицы B

\[\begin{array}{cccc}-1 & 3 & 2 & -3 \\4 & -2 & 5 & 1 \\-5 & 0 & -4 & 0 \\9 & 7 & 8 & -7\end{array}\]

Это квадратная матрица четвёртого порядка. Ранг её не должен превышать четырёх. Видно, что среди миноров
первого ранга есть ненулевые.

Сразу переходим к исследованию миноров второго ранга. Посмотрим, например, \[\begin{array}{cc}4 & -2 \\5
& 0 \end{array}\]. Он равен 0 – 10 = -10. Приступаем к исследованию миноров третьего ранга. Возьмём:

\[\begin{array}{ccc}-1 & 3 & -3 \\-5 & 0 & 0 \\9 & 7 & -7\end{array}\]

Его значение 105 – 105 =0. Придётся исследовать другой подобный минор. Берём

\[\begin{array}{ccc}-2 & 5 & 1 \\0 & -4 & 0 \\7 & 8 & -7\end{array}\]

Он равен -28, т. е. отличен от нулевого, поэтому переходим к минорам ещё на один порядок выше. Здесь у нас
только один выбор – сама матрица.

\[\begin{array}{cccc}-1 & 3 & 2 & -3 \\4 & -2 & 5 & 1 \\5 & 0 & -4 & 0 \\9 & 7 & 8 & -7\end{array}\]

Её минор равен 86, т. е. опять же отличен от нуля. Это значит, что ранг нашей матрицы равен 4. Решение
найдено.

Ответ: rang B = 4.

Нахождение ранга матрицы методом окаймляющих миноров

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

Теорема

Если все миноры, которые окаймляют минор k-го порядка, относящийся к матрице А, имеющей порядок p на n, равны нулю, то все миноры порядка (k+1) матрицы А будут тоже нулевыми.

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

1. Смотрим на миноры первого порядка. Если они все нулевые, значит и ранг нашей матрицы будет равным нулю. Если хотя бы один из них отличен от нуля, переходим к следующему шагу;
2. Смотрим, какие миноры окаймляют минор M₁. Если они все равны нулю, то ранг матрицы будет равен 1. При наличии хотя бы одного отличного от нуля ранг матрицы будет равен 2 или числу, превосходящему 2;
3. Исследуем миноры, окаймляющие минор M_2.. Они будут третьего порядка. Если все они нулевые, то ранг нашей матрицы будет равным 2. Если найдётся хотя бы один отличный от нуля, то ранг матрицы будет больше или равен 3.

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

Примеры

Пример 3. Дана матрица С

\[\begin{array}{cccc}-1 & 2 & 1 & 3 \\-3 & 0 & 5 & 4 \\-5 & 4 & 7 & 10\end{array}\]

Решение: Сразу приступим к исследованию миноров второго порядка. Возьмём \[\begin{array}{ll}-1 & 2 \\-3 & 0\end{array}\].

Он будет равным 6, т.е. отличным от нуля.

Составляем окаймляющий минор. Для этого прибавляем к нашему минору следующую строку и следующий столбец. Получаем:

\[\begin{array}{lll}-1 & 2 & 1 \\-3 & 0 & 5 \\-5 & 4 & 7\end{array}\]

Он равен нулю. Исследование окаймляющих миноров придётся продолжить. Берём следующий за добавленным столбец и получаем

\[\begin{array}{ccc}-1 & 2 & 3 \\-3 & 0 & 4 \\-5 & 4 & 10\end{array}\]

Он тоже оказывается равным нулю. Других окаймляющих миноров нет, а значит ранг нашей матрицы будет равен 2. Решение найдено.

Ответ: rang С = 2.

---

Пример 4. Дана матрица D

\[\begin{array}{ccccc}1 & 2 & 0 & 4 & 5 \\3 & 6 & -2 & -1 & 3 \\-2 & -4 & 2 & 5 & 7 \\-1 & -2 & 2 & 9 & 11\end{array}\]

Решение:

Как и в предыдущем случае, лучше его начать с вычисления минора второго порядка. Посмотрим \[\begin{array}{ll}1 & 2 \\3 & 6\end{array}\]. Он равен нулю. Берём другой минор \[\begin{array}{cc}2 & 0 \\6 & -2\end{array}\]. Он оказался равен -4.

Берём один из окаймляющих его миноров, например, \[\begin{array}{ccc}1 & 2 & 0 \\3 & 6 & -2 \\-2 & -4 & 2\end{array}\].

Он равен нулю. Берём ещё один \[\begin{array}{ccc}2 & 0 & 4 \\3 & 6 & -2 \\-2 & -4 & 2\end{array}\].

Он также равен нулю.

Посмотрим \[\begin{array}{ccc}2 & 0 & 5 \\6 & -2 & -3 \\-4 & 2 & 7\end{array}\]. Он равен 4.

Переходим к четвёртому порядку.

\[\begin{array}{cccc}1 & 2 & 0 & 5 \\3 & 6 & -2 & -3 \\-2 & -4 & 2 & 7 \\-1 & -3 & 2 & 1\end{array}\]

Он равен нулю. Придётся взять другой.

\[\begin{array}{cccc}2 & 0 & 4 & 5 \\6 & -2 & -1 & -3 \\-4 & 2 & 5 & 7 \\-2 & 2 & 9 & 11\end{array}\]

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

Ответ: rang E = 3.

Нахождение ранга матрицы методом элементарных преобразований или методом Гаусса

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

Все указанные преобразования не меняют ранга матрицы. Пользуясь ими можно привести матрицу к виду, когда все из её элементов кроме a₁₁, a₂₂, a₃₃ … a_rr будут равны нулю, а значит ранг матрицы станет равняться r.

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

Пример 5

Дана матрица F

\[\begin{array}{cccc}25 & 31 & 17 & 43 \\75 & 94 & 53 & 132 \\75 & 94 & 54 & 134 \\25 & 32 & 20 & 48\end{array}\]

Решение:

Из третьей строки этой матрицы вычитаем вторую, Из второй строки вычитаем первую

\[\begin{array}{cccc}25 & 31 & 17 & 43 \\75 & 94 & 53 & 132 \\0 & 0 & 1 & 2 \\0 & 1 & 2 & 5\end{array}\]

Далее из второй строки вычитаем первую, умноженную на три

\[\begin{array}{cccc}25 & 31 & 17 & 43 \\0 & 1 & 2 & 3 \\0 & 0 & 1 & 2 \\0 & 1 & 3 & 5\end{array}\]

Из четвёртой строки отнимаем третью и вторую

\[\begin{array}{cccc}25 & 31 & 17 & 43 \\0 & 1 & 2 & 3 \\0 & 0 & 1 & 2 \\0 & 0 & 0 & 0\end{array}\]

Из четвёртого столбца вычитаем третий, предварительно помноженный на два

\[\begin{array}{cccc}25 & 31 & 17 & 0 \\0 & 1 & 2 & -1 \\0 & 0 & 1 & 0 \\0 & 0 & 0 & 0\end{array}\]

Делим первый столбец на 25 и вычитаем из второго столбца первый, до этого помножив его на 31

\[\begin{array}{cccc}1 & 0 & 17 & 9 \\0 & 1 & 2 & -1 \\0 & 0 & 1 & 0 \\0 & 0 & 0 & 0\end{array}\]

От третьего столбца отнимаем первый до этого помножив его на 17, а второй на 2; от четвёртого столбца отнимаем первый, умноженный на 9 и прибавляем второй, помноженный на 2

\[\begin{array}{llll}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & 1 & 0 \\0 & 0 & 0 & 0\end{array}\]

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

Ответ: rang F = 3.

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

Ранг матрицы. Метод окаймляющих миноров

Похожие презентации:

Линейная алгебра. Ранг матрицы. (Тема 2)

Определители матриц. Обратная матрица, ранг матрицы

Линейная алгебра. Ранг матрицы. Метод Гаусса решения систем линейных уравнений. Лекция 5

Ранг матрицы

Обратная матрица. Ранг матрицы

Метод Гаусса решения систем линейных уравнений. Ранг матрицы. Исследование систем линейных уравнений

Ранг матрицы. Собственные числа и собственные векторы

Матрицы и их виды. Действия над матрицами

Ранг матрицы. Лекция 2.2

Матрицы, определители. Обратная матрица. Ранг матрицы. Системы линейных уравнений элементы векторной алгебры

Ранг матрицы.
Метод окаймляющих миноров
Ранг матрицы — это число линейно независимых строк (столбцов) этой матрицы.
Суть метода окаймляющих миноров выражается парой пунктов простого алгоритма:
1) Пусть некий минор M k-го порядка не равен нулю.

2) Если окаймляющие миноры для минора M (это уже будут миноры (k+1)-го
порядка), составить невозможно (т.е. матрица содержит k строк или k столбцов), то
ранг равен k. Если окаймляющие миноры существуют и все равны нулю, то ранг равен
k. Если среди окаймляющих миноров есть хотя бы один, отличный от нуля, то
повторяем для него пункт №1, приняв k+1 вместо k.
Наглядно всё вышеизложенное можно выразить следующей схемой:
Поясню эту схему более подробно. Станем рассуждать с самого начала, т.е. с
миноров первого порядка. Если все миноры первого порядка некоей матрицы A
(миноры первого порядка – это элементы матрицы) равны нулю, то rangA=0. Если в
матрице есть минор первого порядка M1≠0, то rangA≥1.
Проверяем окаймляющие миноры для минора M1. Это уже будут миноры второго
порядка. Если все миноры, окаймляющие M1, равны нулю, то rangA=1. Если среди
миноров второго порядка, окаймляющих M1, есть хоть один минор M2≠0, то
rangA≥2.
Проверяем окаймляющие миноры для минора M2. Это будут миноры третьего
порядка. Если все миноры третьего порядка, окаймляющие M2, равны нулю, то
rangA=2. Если среди миноров третьего порядка, окаймляющих M2, есть хоть один
минор M3≠0, то rangA≥3.
Проверяем окаймляющие миноры для минора M3. Если все миноры четвёртого
порядка, окаймляющие M3, равны нулю, то rangA=3. Если среди миноров
четвёртого порядка, окаймляющих M3, есть хоть один минор M4≠0, то rangA≥4.
Проверяем все окаймляющие миноры для минора M4, и так далее. В конце
концов возможны два случая: либо на каком-то шаге окажется, что все
окаймляющие миноры равны нулю, либо окаймляющий минор составить просто
не получится, так как в матрице «закончатся» строки или столбцы. Порядок
последнего составленного ненулевого минора и будет равен рангу матрицы.
Пример №1
Найти ранг матрицы A=
-1
2
1
3
-3
0
5
4
-5
4
7
10
методом окаймляющих миноров.
Решение
Можно, конечно, начать с миноров первого порядка, которые представляют собой
просто элементы данной матрицы. Но лучше сразу выбрать какой-либо не равный
нулю минор второго порядка, тем паче что такой выбор большой сложности не
представляет.
Например, на пересечении строк №1, №2 и столбцов №1, №2 расположены
элементы минора , который несложно вычислить
-1
2
1
3
-3
0
5
4
-5
4
7
10
−1⋅0−2⋅(−3)=6.
Итак, существует минор второго порядка, не равный нулю, из чего следует, что
rangA≥2. Рассмотрим миноры третьего порядка, окаймляющие данный минор
второго порядка. Как составить окаймляющий минор? Для этого к набору строк и
столбцов, на пересечении которых лежат элементы минора второго порядка, нужно
добавить ещё одну строку и ещё один столбец.
Вспоминаем, что элементы записанного нами минора второго порядка расположены
на пересечении строк №1, №2 и столбцов №1, №2. Добавим к строкам ещё строку
№3, а к столбцам – столбец №3. Мы получим минор третьего порядка, элементы
которого (они для наглядности показаны в матрице красным цветом) лежат на
пересечении строк №1, №2, №3 и столбцов №1, №2, №3. Найдём значение этого
минора
-1
2
1
3
-3
0
5
4
-5
4
7
10
Окаймляющий минор равен нулю. О чём это говорит? Это говорит о том, что нам
нужно продолжить нахождение окаймляющих миноров. Либо они все равны нулю
(и тогда ранг будет равен 2), либо среди них найдётся хотя бы один, отличный от
нуля.
-1
2
1
3
-3
0
5
4
-5
4
7
10
-1
2
3
-3
0
4
-5
4
10
И этот окаймляющий минор равен нулю. Иных окаймляющих миноров нет.
Следовательно, все окаймляющие миноры равны нулю. Порядок последнего
составленного ненулевого минора равен 2. Вывод: ранг равен 2, т.е. rangA=2.
Домашнее задание

English     Русский Правила

Методы и примеры 4 Ранг матрицы

Рассмотрим прямоугольную матрицу. Если в этой матрице выбрать произвольно k строк и k столбцов, то элементы на пересечении выделенных строк и столбцов образуют квадратную матрицу k-го порядка. Определитель этой матрицы называется минором k-го порядка матрицы A. Очевидно, что матрица A имеет миноры любого порядка от 1 до наименьшего из чисел m и n. Среди всех ненулевых миноров матрицы A есть хотя бы один минор, имеющий наибольший порядок. Наибольший из ненулевых порядков миноров данной матрицы называется матрицы ранга . Если ранг матрицы A равен r , то это означает, что матрица A имеет ненулевой минор порядка r , но каждый минор порядка больше r равен нулю. Ранг матрицы A обозначается через r(A). Очевидно, что соотношение

Вычисление ранга матрицы с помощью миноров

Ранг матрицы находится либо окаймлением миноров, либо методом элементарных преобразований. При вычислении ранга матрицы первым способом следует переходить от миноров низших порядков к минорам более высокого порядка. Если ненулевой минор D k-го порядка матрицы A уже найден, то необходимо вычислить только миноры (k + 1)-го порядка, граничащие с минором D, т.е. содержащие его в качестве минора. Если все они равны нулю, то ранг матрицы равен 9.0003 к .

Пример 1 Найти ранг матрицы методом окаймляющих миноров

.

Раствор. Начнем с миноров 1-го порядка, т.е. с элементов матрицы А. Выберем, например, минор (элемент) М 1 = 1, расположенный в первой строке и первом столбце. Соединяя с помощью второй строки и третьего столбца, получаем минор M 2 = , отличный от нуля. Обратимся теперь к минорам 3-го порядка, граничащим с M 2 . Их всего два (можно добавить второй столбец или четвертый). Рассчитываем их: = 0. Таким образом, все окаймляющие миноры третьего порядка оказались равными нулю. Ранг матрицы А равен двум.

Вычисление ранга матрицы с помощью элементарных преобразований

Элементарных Следующие преобразования матриц называются:

1) перестановка любых двух строк (или столбцов),

2) умножение строки (или столбца) на ненулевое число,

3) добавление к одной строке (или столбцу) другой строки (или столбца), умноженное на некоторое число.

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

Эквивалентные матрицы, вообще говоря, не равны, но их ранги равны. Если матрицы A и B эквивалентны, то это записывается следующим образом: A~b.

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

.

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

Пример 2 Найти ранг матрицы

и привести ее к каноническому виду.

Раствор. Вычтите первую строку из второй строки и переставьте эти строки:

.

Теперь из второй и третьей строк вычитаем первую, умноженную на 2 и 5 соответственно:

;

из третьего ряда вычесть первое; получаем матрицу

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

Очевидно, что ранг матрицы B равен 2, а значит, r(A)=2. Матрица B легко приводится к канонической. Вычитая первый столбец, умноженный на подходящие числа, из всех последующих обращаем в нуль все элементы первой строки, кроме первой, а элементы остальных строк не меняем. Затем, вычитая второй столбец, умноженный на соответствующие числа, из всех последующих, обращаем в ноль все элементы второй строки, кроме второго, и получаем каноническую матрицу:

.

Определение. Ранг матрицы — это максимальное количество линейно независимых строк, рассматриваемых как векторы.

Теорема 1 о ранге матрицы. Ранг матрицы — это максимальный порядок ненулевого минора матрицы.

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

Определитель этой матрицы будет минором k-го порядка, если упомянутое «что-то» (количество строк и столбцов) обозначить через k.

Определение. Минор ( r +1)-й порядок, внутри которого лежит выбранный минор r -й порядок, называется граничным для данного минора.

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

Метод окаймления миноров основан на следующей теореме.

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

При методе элементарных преобразований используется следующее свойство:

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

Нахождение ранга матрицы методом окаймляющих миноров

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

Например, дана матрица

Возьмем минор

окантовкой будут такие миноры:

Алгоритм нахождения ранга матрицы следующий.

1. Находим миноры второго порядка, не равные нулю. Если все миноры второго порядка равны нулю, то ранг матрицы будет равен единице ( г =1 ).

2. Если существует хотя бы один минор второго порядка, не равный нулю, то составим окаймляющие миноры третьего порядка. Если все граничные миноры третьего порядка равны нулю, то ранг матрицы равен двум ( r =2 ).

3. Если хотя бы один из окаймляющих миноров третьего порядка не равен нулю, то составим окаймляющие его миноры. Если все граничащие миноры четвертого порядка равны нулю, то ранг матрицы равен трем ( r =2 ).

4. Продолжайте, пока позволяет размер матрицы.

Пример 1 Найти ранг матрицы

.

Раствор. Минор второго порядка.

Обрамляем. Будет четыре окаймляющих минора:

,

,

Таким образом, все окаймляющие миноры третьего порядка равны нулю, следовательно, ранг этой матрицы равен двум ( r =2 ).

Пример 2 Найти ранг матрицы

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

Пример 3 Найти ранг матрицы

Решение. Минор второго порядка этой матрицы равен , а все миноры третьего порядка этой матрицы равны нулю. Следовательно, ранг этой матрицы равен двум.

Пример 4 Найти ранг матрицы

Решение. Ранг этой матрицы равен 3, потому что единственный минор третьего порядка этой матрицы равен 3.

Нахождение ранга матрицы методом элементарных преобразований (методом Гаусса)

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

Под элементарными преобразованиями матрицы понимаются следующие операции:

1) умножение любой строки или любого столбца матрицы на число, отличное от нуля;

2) добавление к элементам любой строки или любого столбца матрицы соответствующих элементов другой строки или столбца, умноженных на то же число;

3) перестановка двух строк или столбцов матрицы;

4) удаление «нулевых» строк, то есть таких, все элементы которых равны нулю;

5) удаление всех пропорциональных линий, кроме одной.

Теорема. Элементарное преобразование не меняет ранг матрицы. Другими словами, если с помощью элементарных преобразований из матрицы A перейти к матрице B , то .

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

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

Эквивалентные матрицы — это матрицы, ранги которых равны друг другу.

Поясним подробнее. Предположим, что среди миноров второго порядка есть хотя бы один, отличный от нуля. А все миноры, порядок которых выше двух, равны нулю. Вывод: ранг матрицы равен 2. Или, например, среди миноров десятого порядка есть хотя бы один, не равный нулю. А все миноры, порядок которых выше 10, равны нулю. Вывод: ранг матрицы равен 10.

Ранг матрицы $A$ обозначается следующим образом: $\rang A$ или $r(A)$. Ранг нулевой матрицы $O$ полагается равным нулю, $\rang O=0$. Напомню, что для формирования минора матрицы требуется вычеркнуть строки и столбцы, но нельзя вычеркнуть больше строк и столбцов, чем содержит сама матрица. Например, если матрица $F$ имеет размер $5\times 4$ (т.е. содержит 5 строк и 4 столбца), то максимальный порядок ее миноров равен четырем. Миноры пятого порядка образовать уже не получится, так как для них потребуется 5 столбцов (а у нас всего 4). Это означает, что ранг матрицы $F$ не может быть больше четырех, т.е. $\rang F≤4$.

В более общем виде вышеизложенное означает, что если матрица содержит $m$ строк и $n$ столбцов, то ее ранг не может быть больше наименьшего из чисел $m$ и $n$, т.е. $\rang A≤ \мин(м,п)$.

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

Поясню эту диаграмму подробнее. Начнем рассуждения с самого начала, т.е. с миноров первого порядка некоторой матрицы $A$.

1. Если все миноры первого порядка (то есть элементы матрицы $A$) равны нулю, то $\rang A=0$. Если среди миноров первого порядка есть хотя бы один, не равный нулю, то $\rang A≥ 1$. Переходим к проверке миноров второго порядка.
2. Если все миноры второго порядка равны нулю, то $\rang A=1$. Если среди миноров второго порядка есть хотя бы один, не равный нулю, то $\rang A≥ 2$. Переходим к проверке миноров третьего порядка.
3. Если все миноры третьего порядка равны нулю, то $\rang A=2$. Если среди миноров третьего порядка есть хотя бы один, не равный нулю, то $\rang A≥ 3$. Перейдем к проверке миноров четвертого порядка.
4. Если все миноры четвертого порядка равны нулю, то $\rang A=3$. Если существует хотя бы один ненулевой минор четвертого порядка, то $\rang A≥ 4$. Переходим к проверке миноров пятого порядка и так далее.

Что нас ждет в конце этой процедуры? Возможно, что среди миноров k-го порядка найдется хотя бы один, отличный от нуля, а все миноры (k + 1)-го порядка будут равны нулю. Это означает, что k — максимальный порядок миноров, среди которых есть хотя бы один, не равный нулю, т. е. ранг будет равен k. Возможна и другая ситуация: среди миноров k-го порядка будет хотя бы один, не равный нулю, а миноры (k + 1)-го порядка не могут быть образованы. В этом случае ранг матрицы также равен k. Короче говоря, порядок последнего составленного ненулевого минора и будет равен рангу матрицы .

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

Кстати, вовсе не обязательно начинать процедуру нахождения ранга с миноров самого маленького порядка, как это было сделано в примерах №1 и №2. Можно сразу перейти к минорам более высоких порядков ( см. пример №3).

Пример #1

Найти ранг матрицы $A=\left(\begin(array)(ccccc) 5 & 0 & -3 & 0 & 2 \\ 7 & 0 & -4 & 0 & 3 \ \ 2 & 0 & -1 & 0 & 1 \end(массив)\right)$.

Эта матрица имеет размер $3\times 5$, т.е. содержит три строки и пять столбцов. Из чисел 3 и 5 3 является минимальным, поэтому ранг матрицы $A$ не превосходит 3, т.е. $\rank A≤ 3$. И это неравенство очевидно, так как мы уже не можем формировать миноры четвертого порядка — им нужно 4 строки, а у нас всего 3. Перейдем непосредственно к процессу нахождения ранга заданной матрицы.

Среди миноров первого порядка (т.е. среди элементов матрицы $A$) есть ненулевые. Например, 5, -3, 2, 7. В общем случае нас не интересует общее количество ненулевых элементов. Есть хотя бы один ненулевой элемент — и этого достаточно. Поскольку среди миноров первого порядка есть хотя бы один ненулевой, заключаем, что $\rang A≥ 1$, и переходим к проверке миноров второго порядка.

Приступим к изучению миноров второго порядка. Например, на пересечении строк №1, №2 и столбцов №1, №4 находятся элементы следующего минора: $\left|\begin(array)(cc) 5 & 0 \\ 7 & 0 \end (массив) \право| $. Для этого определителя все элементы второго столбца равны нулю, следовательно, и сам определитель равен нулю, т. е. $\left|\begin(array)(cc) 5 & 0 \\ 7 & 0 \end(array) \right|=0$ (см. свойство №3 в свойстве определителей). Либо можно просто вычислить этот определитель по формуле №1 из раздела о вычислении определителей второго и третьего порядка:

$$ \left|\begin(массив)(cc) 5 & 0 \\ 7 & 0 \end(массив) \right|=5\cdot 0-0\cdot 7=0. $$

Первый минор второго порядка, который мы проверили, оказался равным нулю. Что это говорит? О необходимости дополнительной проверки миноров второго порядка. Либо все они окажутся нулевыми (и тогда ранг будет равен 1), либо среди них есть хотя бы один минор, отличный от нуля. Попробуем сделать лучший выбор, написав минор второго порядка, элементы которого расположены на пересечении строк №1, №2 и столбцов №1 и №5: $\left|\begin(array)(cc) 5 & 2 \\ 7 & 3 \end(массив)\right|$. Найдем значение этого минора второго порядка:

$$ \left|\begin(массив)(cc) 5 & 2 \\ 7 & 3 \end(массив) \right|=5\cdot 3-2\cdot 7=1. $$

Этот минор не равен нулю. Вывод: среди миноров второго порядка есть хотя бы один, отличный от нуля. Следовательно, $\rank A≥ 2$. Необходимо перейти к изучению миноров третьего порядка.

Если для образования миноров третьего порядка выбрать столбец №2 или столбец №4, то такие миноры будут равны нулю (поскольку они будут содержать нулевой столбец). Осталось проверить только один минор третьего порядка, элементы которого расположены на пересечении столбцов №1, №3, №5 и строк №1, №2, №3. Запишем этот минор и найти его значение:

$$ \left|\begin(array)(ccc) 5 & -3 & 2 \\ 7 & -4 & 3 \\ 2 & -1 & 1 \end(array) \right|=-20-18 -14 +16+21+15=0. $$

Итак, все миноры третьего порядка равны нулю. Последний ненулевой минор, который мы собрали, был второго порядка. Вывод: максимальный порядок миноров, среди которых есть хотя бы один отличный от нуля, равен 2. Следовательно, $\rang A=2$.

Ответ : $\rank A=2$.

Пример #2

Найти ранг матрицы $A=\left(\begin(array) (cccc) -1 & 3 & 2 & -3\\ 4 & -2 & 5 & 1\\ -5 & 0 & -4 & 0\\ 9& 7 & 8 & -7 \end(массив) \right)$.

У нас есть квадратная матрица четвертого порядка. Сразу отметим, что ранг этой матрицы не превосходит 4, т.е. $\rank A≤ 4$. Начнем с нахождения ранга матрицы.

Среди миноров первого порядка (то есть среди элементов матрицы $A$) есть хотя бы один, не равный нулю, поэтому $\rang A≥ 1$. Переходим к проверке миноров второго порядка. Например, на пересечении строк №2, №3 и столбцов №1 и №2 получаем следующий минор второго порядка: $\left| \begin(массив) (cc) 4 & -2 \\ -5 & 0 \end(массив) \right|$. Подсчитаем:

$$ \слева| \begin(массив) (cc) 4 & -2 \\ -5 & 0 \end(массив) \right|=0-10=-10. $$

Среди миноров второго порядка хотя бы один не равен нулю, поэтому $\rang A≥ 2$.

Перейдем к минорам третьего порядка. Найдем, например, минор, элементы которого находятся на пересечении строк №1, №3, №4 и столбцов №1, №2, №4:

$$ \left | \begin(массив) (cccc) -1 & 3 & -3\\ -5 & 0 & 0\\ 9 & 7 & -7 \end(массив) \right|=105-105=0. $$

Поскольку этот минор третьего порядка оказался равным нулю, необходимо исследовать еще один минор третьего порядка. Либо все они будут равны нулю (тогда ранг будет равен 2), либо среди них будет хотя бы один, не равный нулю (тогда мы начнем изучать миноры четвертого порядка). Рассмотрим минор третьего порядка, элементы которого расположены на пересечении строк №2, №3, №4 и столбцов №2, №3, №4:

$$ \left| \begin(массив) (ccc) -2 & 5 & 1\\ 0 & -4 & 0\\ 7 & 8 & -7 \end(массив) \right|=-28. $$

Среди миноров третьего порядка есть хотя бы один ненулевой минор, поэтому $\rang A≥ 3$. Перейдем к проверке миноров четвертого порядка.

Любой минор четвертого порядка находится на пересечении четырех строк и четырех столбцов матрицы $A$. Другими словами, минор четвертого порядка является определителем матрицы $A$, поскольку эта матрица как раз содержит 4 строки и 4 столбца. Определитель этой матрицы вычислялся в примере №2 темы «Понижение порядка определителя. Разложение определителя в строку (столбец)» , так что давайте просто возьмем готовый результат:

$$ \слева| \begin(array) (cccc) -1 & 3 & 2 & -3\\ 4 & -2 & 5 & 1\\ -5 & 0 & -4 & 0\\ 9 & 7 & 8 & -7 \end (массив)\справа|=86. $$

Итак, минор четвертого порядка не равен нулю. Мы больше не можем образовывать миноров пятого порядка. Вывод: наивысший порядок миноров, среди которых есть хотя бы один отличный от нуля, равен 4. Результат: $\rang A=4$.

Ответ : $\rank A=4$.

Пример №3

Найти ранг матрицы $A=\left(\begin(array) (cccc) -1 & 0 & 2 & -3\\ 4 & -2 & 5 & 1\\ 7 & -4 & 0 & — 5 \конец(массив)\справа)$.

Сразу заметим, что эта матрица состоит из 3 строк и 4 столбцов, поэтому $\rang A≤ 3$. В предыдущих примерах мы начали процесс нахождения ранга с рассмотрения миноров наименьшего (первого) порядка. Здесь мы постараемся сразу проверить миноры максимально возможного порядка. Для матрицы $A$ это миноры третьего порядка. Рассмотрим минор третьего порядка, элементы которого лежат на пересечении строк №1, №2, №3 и столбцов №2, №3, №4:

$$ \слева| \begin(массив) (ccc) 0 & 2 & -3\\ -2 & 5 & 1\\ -4 & 0 & -5 \end(массив) \right|=-8-60-20=-88. $$

Итак, высший порядок миноров, среди которых есть хотя бы один, не равный нулю, равен 3. Следовательно, ранг матрицы равен 3, т.е. $\rank A=3$.

Ответ : $\rank A=3$.

Вообще, нахождение ранга матрицы по определению в общем случае является довольно трудоемкой задачей. Например, относительно небольшая матрица $5\times 4$ имеет 60 миноров второго порядка. И даже если 59из них равны нулю, то 60-й минор может оказаться ненулевым. Затем нужно исследовать миноры третьего порядка, которых в этой матрице 40 штук. Обычно стараются использовать менее громоздкие методы, например метод окаймляющих миноров или метод эквивалентных преобразований.

В каждой матрице могут быть связаны два ранга: ранг строки (ранг системы строк) и ранг столбца (ранг системы столбцов).

Теорема

Ранг строки матрицы равен рангу ее столбца.

Ранг матрицы

Определение

Ранг матрицы $A$ — это ранг ее системы строк или столбцов.

Обозначается $\operatorname(rang) A$

На практике для нахождения ранга матрицы используется следующее утверждение: ранг матрицы равен количеству ненулевых строк после матрица приведена к ступенчатой ​​форме.

Элементарные преобразования над строками (столбцами) матрицы не изменяют ее ранга.

Ранг ступенчатой ​​матрицы равен количеству ее ненулевых строк.

Пример

Задача. Найти ранг матрицы $ A=\left(\begin(array)(cccc)(0) & (4) & (10) & (1) \\ (4) & (8) & (18) & (7) \ \ (10) & (18) & (40) & (17) \\ (1) & (7) & (17) & (3)\end(массив)\right) $

Решение . Элементарными преобразованиями над ее строками приводим матрицу $A$ к ступенчатому виду. Для этого сначала вычтите вторые две из третьей строки:

$$ A \sim \left(\begin(array)(cccc)(0) & (4) & (10) & (1) \\ ( 4) & (8) & (18) & (7) \\ (2) & (2) & (4) & (3) \\ (1) & (7) & (17) & (3)\конец (массив)\справа) $$

Из второй строки вычитаем четвертую строку, умноженную на 4; из третьего — две четвертых:

$$ A \sim \left(\begin(array)(rrrr)(0) & (4) & (10) & (1) \\ (0) & (-20) & (-50) & (-5 ) \\ (0) & (-12) & (-30) & (-3) \\ (1) & (7) & (17) & (3)\end( array)\right) $$

Прибавляем первые пять ко второй строке, а три трети к третьей:

$$ A \sim \left(\begin(array)(cccc)(0) & (4 ) & (10) & (1) \\ (0) & (0) & (0) & (0) \\ (0) & (0) & (0) & (0) \\ (1) & ( 7) & (17) & (3)\конец(массив)\справа) $$

Поменять местами первую и вторую строки:

$$ A \sim \left(\begin(array)(cccc)(0) & (0) & (0) & (0) \\ (0) & (4) ) & (10) & (1) \\ (0) & (0) & (0) & (0) \\ (1) & (7) & (17) & (3)\end(массив)\right ) $$

$$ A \sim \left(\begin(array)(cccc)(1) & (7) & (17) & (3) \\ (0) & (4) & (10) & (1) \\ (0) & (0) & (0) & (0) \\ (0) & (0) & (0) & (0)\конец(массив)\вправо) \Стрелка вправо\имя_оператора( ранг) А=2 $$

Ответ. (2) $ . Таких миноров два: сочетание третьего ряда со вторым столбцом или с четвертым столбцом. Вычислим эти миноры.

Любую матрицу A порядка m×n можно рассматривать как набор m векторов-строк или n векторов-столбцов.

ранг матрицы Порядок m×n — это максимальное количество линейно независимых векторов-столбцов или векторов-строк.

Если ранг матрицы A равен r , то записывается:

Нахождение ранга матрицы

Пусть A матрица произвольного порядка м × n . Чтобы найти ранг матрицы A , применим к ней метод исключения Гаусса.

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

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

Количество ненулевых векторов-строк будет рангом матрицы A .

Давайте рассмотрим все это на простых примерах.

Пример 1

Умножая первую строку на 4 и прибавляя ко второй строке и умножая первую строку на 2 и добавляя к третьей строке мы имеем:

Умножаем вторую строку на -1 и добавляем к третья строка:

Получились две ненулевые строки и, следовательно, ранг матрицы равен 2.

Пример 2

Найдите ранг следующей матрицы:

Умножьте первую строку на -2 и прибавьте ко второй строке. Аналогично обнуляем элементы третьей и четвертой строк первого столбца:

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

Наиболее распространенные изотопные пики и эффективный отбор на $Y=X_1+X_2+\cdots + X_m$ – arXiv Vanity

Патрик Крайцберг
Университет Монтаны
Департамент компьютерных наук
Кампус Драйв, 32, Миссула, Монтана
Соединенные Штаты Америки Кайл Лак
Университет Монтаны
Департамент компьютерных наук
Кампус Драйв, 32, Миссула, Монтана
Соединенные Штаты Америки Оливер Серанг
Университет Монтаны
Департамент компьютерных наук
Кампус Драйв, 32, Миссула, Монтана
Соединенные Штаты Америки

14 марта 2021 г.

Abstract

Массы изотопов и относительное содержание каждого элемента фундаментальные химические знания. Вычисление масс изотопов соединений и их относительных содержаний является важным и трудным задача по аналитической химии. Мы показываем, что эта проблема эквивалентно сортировке Y=X1+X2+⋯+Xm. Представляем роман, практически эффективный метод вычисления верхних значений Y. затем продемонстрируйте применимость этого метода, вычислив наиболее распространенные массы изотопов (и их содержания) из соединений нетривиального размера.

1 Введение

Атомы одного и того же элемента могут иметь различное число нейтронов в их значения. Количество нейтронов в ядре атома влияет на его массу. Относительное обилие, с которым различные изотопы встречаются в природе, хорошо известно. [5]

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

Для небольших задач это можно решить методом грубой силы: это возможно чтобы вычислить все массы изотопов и их соответствующее содержание, сортировать их в порядке убывания содержания, а затем извлечение изотопа пики (мы будем иметь в виду массу и относительное содержание конкретный изотоп как изотопный пик, потому что именно так они наблюдается в масс-спектрометрии) с наибольшей распространенностью; Однако, время выполнения этого метода грубой силы слишком неэффективно, потому что он растет ∈Ω(2n).

Лацки и др. [5] недавно представил статистический подход к этой проблеме, согласно которому пики верхних изотопов соединения может быть эффективно аппроксимирована. Для каждого элемента метод генерирует данные из изотополога ( т.е. , из вклады всех возможных изотопов этого элемента). Для каждого элемент, его возможные вклады следуют полиномиальному распределению, который Łącki et al. приблизительно с использованием многовариантности Гауссианы и генерировать в порядке убывания или вероятности. вклады изотопологов объединяются по соответствующему элементу наборы. В этот момент они генерируют изотопные конфигурации соединение в порядке убывания вероятности, что эквивалентно нахождение k наиболее вероятных изотопологов молекулы.

В этой статье мы показываем, что нахождение верхних k изотопных пиков соединения, состоящего из m элементов, эквивалентно нахождению верхние значения k (и соответствующие индексы) в Y=X1+X2+⋯+Xm, где Xi — векторы длины n, а Y — декартово произведение этих векторов под оператором +. Эта проблема, которая важное значение для других проблем, таких как max-convolution [2] и max-product Bayesian вывод [8, 6] , является обобщением парной задачи, в которой мы вычисляем верхние k значений в С=А+В.

Поиск верхних значений k в C=A+B нетривиален. На самом деле есть нет известного подхода, который сортирует все n2 значений C быстрее, чем наивно вычисляя и сортируя их в O(n2log(n2))=O(n2log(n)) [1] ; Однако, Frederickson & Johnson продемонстрировали, что верхние значения n в C можно вычислить ∈O(nlog(n)) [4] . Фредериксон и Джонсон обобщили проблему до получения k-е верхнее значение в матрице, отсортированной по обоим столбцам и строки [3] . Отсортированную матрицу можно построить с X1+X2, но представленный метод предполагает, что матрица уже такой формы и не учитывает работы по производству матрица из векторов.

Это можно увидеть, отсортировав A и B в порядке убывания, а затем разреженное построение матрицы Ai+Bj. Если А’ и В’ представляют отсортированные векторы такие, что A′1≥A′2≥⋯ и B′1≥B′2≥⋯, то максимальное значение C равно А′1+В′1. Второе по величине значение в C равно max(A′1+B′2,A′2+B′1).

W.l.o.g, мы знаем, что никогда не будем вставлять A′i+1+B′j в отсортированный результат верхних значений в C без предварительной вставки большего (или равное) значение A′i+B′j. Таким образом, каждый раз значение из матрицы A′i+B′j оказывается следующим по величине в C, последующее следующее наибольшее значение в C может быть среди непосещенных существующих соседей (ряд или столбец, но не по диагонали) ранее не посещенных ценности. Эти рассматриваемые значения образуют «окантовку» вокруг индексов значения которых уже вставлены в результат. Мы находим следующий значение для вставки в результат путем нахождения минимального значения в настоящее время в этой окраине. Поскольку ≤2 значения будут вставлены в бахрома на каждой итерации ( т. е. , если только что было вставлено A′i+Bj в результат, то A′i+1+B′j и A′i+B′j+1 будут добавлены в бахрому, если они находятся в границах). Таким образом, минимальное значение в периферии можно обновлять редко, используя двоичную кучу. Запись что только индексы и значения, составляющие полосу, являются единственными сохраненные значения, и что полная матрица, которая будет иметь пространство n2 и, таким образом, время выполнения ∈ Ω(n2) никогда не реализуется. Бахрома может никогда не имеют размера ∈ω(n) (поскольку в худшем случае он перемещается на n шагов вверх и на n шагов вправо), и так каждый следующий наибольшее значение в C будет иметь стоимость ∈O(log(n)). Вычисление Таким образом, верхние значения k в C равны ∈O(klog(n)).

В этой статье мы сначала строим прямое обобщение Метод Фредериксона и Джонсона к задаче нахождения вершины k значения в Y=X1+X2+⋯+Xm. Затем мы создаем более эффективную метод путем обобщения метода C=A+B Фредериксона и Джонсона на случай, когда A и B являются произвольными структурами данных кучи и вычислить самые большие значения k в Y, построив сбалансированный двоичное дерево, каждый узел которого является одной из этих структур данных. Этот Затем метод применяется для нахождения наиболее распространенных изотопных пиков для заданная молекулярная формула.

2 метода

2.1. Прямое m-мерное обобщение теории Фредериксона и Джонсона 90 447.

Прямое обобщение метода Фредериксона и Джонсона, которое очень напоминает Łącki et al. Подход к генерации верхний изотоп достигает пика [5] , это просто: вместо матрицы, мы имеем тензор Rm. Как и прежде, мы храним только текущий край, который хранится в куче. В каждой итерации мы удаляем минимальное значение в бахроме и добавляем его к результирующий вектор. Пусть это минимальное значение исходит из индекса (i1,i2,…im). Теперь мы вставляем m значений от соседей индекса (i1,i2,…im) в кучу, удерживающую край: (i1+1,i2,…,im),(i1,i2+1,…,im),…(i1,i2,…,im+1). Как и в случае двумерного метода, можно хранить не только X1,i1+X2,i2+X3,i3+⋯Xm,im в куче, но и хранить индексный кортеж из что пришло. Это показано в Листинг 2. 

Этот m-мерный метод будет существенно медленнее, чем двумерный метод: полоса в этой версии m-мерный метод представляет собой плоскость ширины ≤n и размерности m−1 и, таким образом, может иметь размер до O(nm−1).

⬇

Import Heapq

класс MaxIndexHeap:

def __init __ (self, value_and_indices = []):

Self.min_Heap = [-a, b) для A, b in values_and_indices]

heApq.Heap (b) (b) (b). self.min_heap)

    self.descending_values_and_indices = []

def вставка (self, val_and_index):

#Примечание: не защищает от двойной вставки индекса

val, index = val_and_index

Heapq. heapus def pop_max_and_index (self):

neg_val, index = heapq.heappop (self.min_heap)

self.descending_values_and_indices.append (-neg_val, index))

return (-neg_val, index_val, index))

(-neg_val, index_val, index))

. , ранг):

    утвердить(ранг >= 0 и ранг < len(self.descending_values_and_indices))

    return self.descending_values_and_indices[rank]

  def __len__(self):

7

    Листинг 1: MaxIndexHeap.py: класс Python с максимальной кучей.

⬇

от MaxIndexHeap Import*

класс TensorCartesianSumHeap:

def __init __ (Self, Vectors):

Self.m = LEN (Vectors)

Self.Descending_VECTOR ,b в enumerate(v)], reverse=True) для v в векторах ]

    max_value = sum([a for a,b в [v[0] для v in , Zero_tup)])

self.sorted_indices_in_fringe = set ([Zero_tup])

def pop_max_and_index (self):

al, index = self.fringe.pop_max_andex ()

Self.shindices_Ince_Ince_Ince_Inge_Ingige_INGIGE_INGERICE_INGINGE_INGERICE_INGERICE_INGERICE_INGERICE_INGERICE_INGERICE_INGERICE_INGERICE_INGEX_INDEX ()

. # вставьте соседей из края, если еще не посещали:

для I в диапазоне (self.m):

new_index = list (index)

new_index [i]+= 1

new_index = tuple (new_index)

desc_vec_i = self.descending_vectors_undex_unsorted_indices. new_index [i]

self.fringe.insert ((new_val, new_index))

self.sorted_indices_in_fringe.add (new_index)

unsorted_index = tuple.add (new_index)

. ] для i,j в enumerate(index) ])

    return (val, unsorted_index)

Листинг 2: TensorCartesianSumHeap.py: обобщение метода Фредериксона и Джонсона, которое вычисляет верхние k значений Y=X1+X2+⋯+Xm. Этот метод использует экземпляры класса MaxIndexHeap (листинг 1).

2.2 Иерархический m-мерный метод нахождения k верхних значений Y

Во-первых, заметим, что в двумерном случае C=A+B это не необходимые для того, чтобы A и B были отсортированными векторами; вместо этого это достаточно, чтобы A и B были просто структурами данных с максимальной кучей, из который мы можем неоднократно запрашивать следующее наибольшее значение. Метод таким образом работает аналогично двумерному случаю: верхний левый угол C вычисляется через максимальное значение A и максимальное значение B. Это вставляет в полосу два значения: либо сумму наибольшее значение в A и второе по величине значение в B или сумма второе по величине значение в A и наибольшее значение в B. Ни полное отсортированное содержимое A или полное отсортированное содержимое B нужны.

Таким образом, мы строим сбалансированное бинарное дерево из этих кучи конструкции:

	Д =	(X1+X2+⋯+Xn2)+(Xn2+1+Xn2+2+⋯+Xn)
	=	(X1+X2+⋯+Xn4)+(Xn4+1+Xn4+2+⋯+Xn2)+
		(Xn2+1+Xn2+2+⋯+X3n4)+(X3n4+1+X3n4+2+⋯+Xn
	=	⋯

Каждая куча-подобная структура имеет форму C=A+B, где A и B кучеобразные структуры (рис. 1). Базовый случай (в листья) достигается простым использованием двоичной кучи входных вектор (листинг 4).

Рисунок 1: Иллюстрация иерархического метода. Попарно Декартовы кучи сумм (листинг 3) собраны в сбалансированное бинарное дерево. Серые квадраты в каждом 2D grid представляют значения, которые уже были извлечены из этой CartesianSumPairHeap по запросу родительского узла в дерево. Когда значение выталкивается из дочернего элемента в родительский, оно продвигает соответствующее поле по одной оси родительского сетка. Синие квадраты — это значения на краю поля, но не все же выскочил. Ребенок слева вытащил шесть значений и в настоящее время имеет четыре значения на краю; ось строки родителя имеет шесть значений, которые были реализованы до сих пор. Ребенок на right извлек четыре значения и в настоящее время имеет четыре значения в своем бахрома; ось столбца родителя имеет четыре значения, которые имеют реализовано до сих пор. Индексы, из которых выскочил дочерний элемент, также включены, что позволяет искать индекс (i1,i2,…im) было следующим по величине значением Y=X1,i1+X2,i2+⋯+Xm,im.

⬇

от MaxIndexHeap Import*

def int_or_tuple_to_tuple (int_or_tuple):

, if Type (int_or_tuple) не является TUPLE:

return (int_or_tuple,)

return_trep net_or heap_like_a, heap_like_b):

    self.heap_like_a = heap_like_a

    self.heap_like_b = heap_like_b

     self.number_remaining_like_elements = len(heap_lenlike_a) _*  0017

    max_a, index_a = heap_like_a.pop_max_and_index()

    max_b, index_b = heap_like_b.pop_max_and_index()

    index_a = int_or_tuple_to_tuple(index_a)

    index_b = int_or_tuple_to_tuple(index_b)

    max_value = max_a + max_b

    zero_tup = ( 0,0)

    self.fringe = MaxIndexHeap([(max_value, (zero_tup, index_a+index_b))])

    self.sorted_indices_in_fringe = set( [zero_tup] )

] _c dic_values[and ending_selfes0017

def insert_into_fringe (self, a_int_ind, b_int_ind):

#Проверьте, что индексы находятся в границах:

, если a_int_ind! = Len (self. heap_lize_a.descending_values_and_indizer_send_vens_vens_send_sence_send_send_send_send_sendizer_send_send_send_send_send_send_send_send_send_send_send_send_send_send_send_send_send_send_send_sendizer_sinde_w

matrix_index = (a_int_ind, b_int_ind)

, если matrix_index не в Self.sorted_indices_in_fringe:

new_val_a, new_index_a = self.heap_liz0017

        new_val_b, new_index_b = self.heap_like_b.get_value_and_index_at_rank(b_int_ind)

        new_index_a = int_or_tuple_to_tuple(new_index_a)

        new_index_b = int_or_tuple_to_tuple(new_index_b)

        self.fringe.insert( (new_val_a+new_val_b, (matrix_index, new_index_a+new_index_b) ) )

        self.sorted_indices_in_fringe.add(matrix_index)

  def pop_max_and_index(self):

    self.number_remaining_elements -= 1

val, (twa_d_sorted_index, full_index) = self.fringe.pop_max_and_index ()

self.sorted_indices_in_fringe.remove (twa_d_sorted_index)

#Insert. secless Of Selected Cell, если not visited_index)

#Insert. current_b = two_d_sorted_index[1]

    if len(self.heap_like_a)!=0 и current_a+1 == len(self.heap_like_a.descending_values_and_indices):

      self.heap_like_a.pop_max_and_index()0017

    if len(self.heap_like_b)!=0 и current_b+1 == len(self.heap_like_b.descending_values_and_indices):

      self.heap_like_b.pop_max_and_index()

     , # в правой этой ячейке В Heap_Like_a/B

Self.insert_into_fringe (current_a+1, current_b)

self.insert_into_fring

def get_value_and_index_at_rank (self, rank):

Assert (Rank> = 0 и Rank

return self.descend_values_and_indices [rank]

def ____len __ (self _values_and_ndices [rank]

def ____len __ (self _values_and_ndices [rank]

def ____le. python разрешает возвращать только примитивное значение int для __len__:

    if self.number_remaining_elements > 2**32-1:

      return 2**32-1

    return self. number_remaining_elements Листинг 3. CartesianSumPairHeap.py. Класс CartesianSumPairHeap представляет собой структуру, подобную куче, которая получает следующее наибольшее значение либо из одного из дочерних элементов структуры, подобной куче, либо из двух отсортированных векторов, содержащихся в классе. Этот класс используется в иерархическом методе.

⬇

от CartesiansumpairHeap Import*

класс TreeCartesiansumHeap:

def __init __ (Self, Vectors):

Vectors_and_indices = [(b, a) для A, b in enumerate (ve)] для V ectors]

777777777777777777777777777777777777777 для

#Создайте сбалансированное двоичное дерево и сохраните корень:

current_layer = [maxIndexHeap (v) для v in vectors_and_indices]

, в то время как Len (Current_Layer)> 1:

lext_layer = []

для I в диапазоне (Len (текущий_слой) // 2):

        next_layer.append( CartesianSumPairHeap(current_layer[2*i], current_layer[2*i+1]) )

      if len(current_layer)%2 == 1:

      текущий слой[next_layer)_layer. append.

current_layer = next_layer

self.root = current_layer [0]

def pop_max_and_index (self):

Val, index = int.root.pop_max_and_index ()

return (val_or_tuple) Листинг 4. TreeCartesianSumHeap.py: иерархический метод для вычисления k верхних значений Y=X1+X2+⋯+Xm, использующий объекты класса из листинга 3.

2.3 Расчет наиболее распространенных изотопных пиков 90 447

Пусть углерод представлен как вектор C=(log(0,9892),log(0,0108))=(−0,0108,−4,5282), а водород как вектор H=(log(0,9999),log(0,0001))=(-0,0001,-9,2103). [5] Пропан, \ceC3H8, в изобилии состоит из Y=C+C+C+H+H+H+H+H+H+H+H. Чтобы уменьшить количество векторов от 11 до двух вычисляется мультином для каждого элемента, чтобы найти вклад всех изотопов. Этот многочлен представляется как вектор, который заменяет все векторы для этого элемента. Таким образом, пропан можно оценить как сумму двух многочленов, которые закодированы как векторы: один для C и один для H. Молекулы, которые состоят из любых количеств водорода, углерода, азота, кислорода, серы, и т. д. можно решить с помощью векторов: H,C,N,O,S…. Большинство обильные изотопные пики обнаруживаются по верхним значениям Y.

.

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

⬇

import numpy

from collections import defaultdict

import sys

from scipy.special import gammaln

from functools import reduce

from TreeCartesianSumHeap import *

from TensorCartesianSumHeap import *

from BruteForceCartesianSumHeap import *

def read_in_elements(element_file):

  element_to_masses_and_abundances = {}

  для строки в open(element_file):

    words = line.split()

    element_abbrev = words[0]

CUPLES = [Tuple ([float (x) для x in w. split (‘,’)]) для w в словах [1:]]

element_to_masses_and_abundances [elect_abrev] = Круплы

return element_to_masses_and_abundances

def_molecular_formula_formula_formula_formula_formula_formula_formula_formula_formula_formula_formular Формула):

element_to_count = defaultdict (int)

elements_and_count = 1:

E = E_AND_COUNT [0]

COUN = 1

ELSE:

E, COUNT = E_AND_COUNT

COUNT = INT (COUNT)

element_to_count [E]+= count

return_to_to_count

Def gogal -mial (e]+= count

. log_probs, tup):

 result = gammaln(sum(tup)+1)

 for x in tup:

    result -= gammaln(x+1)

 for i in range(len(log_0probs)17):

    результат += log_probs[i]*tup[i]

Результат возврата

DEF CUPLE_WITH_FIXED_SUM (B, N):

MASK = NUPPIENTIONTION (B, DTYPE = Int)

для C в итуолете. )

#повернуть массы/log_abundances из одного элемента во все комбинации:

def element_to_multinomial_masses_and_log_abundances (element_masses, element_log_abundancs, trials):

n = len (element_masses)

Mass_resl0017

log_abundance_results = []

для tup в cuples_with_fixed_sum (n, испытания):

Mass = sum ([i]*element_masses [i] для i в диапазоне (n)])

log_prob = log_multinomial (n)))

, Tup)

mass_results. append (Mass)

log_abundance_results.append (log_prob)

return mass_results, log_abundance_results

DEF USAGE ():

PRINT (‘usage: ␣ element␣file> ␣ formul␣ <). ␣например, ␣H:2,S,O:4>␣<число_пиков>␣[дерево(ПО УМОЛЧАНИЮ)␣ИЛИ␣тензор␣ИЛИ␣грубая сила]’ )

  exit(1)

def main(args):

  if len(args) != 3:

    if len(args) != 4 или len(args) == 4 и args[3] не в (‘tree’, ‘tensor’, ‘bruteforce’):

usage ()

element_to_isotop_mass_and_abundance = read_in_elements (args [0])

element_to_count = parse_molecular_formul ])

  if len(args) == 4:

    mode = args[3]

  mass_vectors = []

abundance_vectors = []

для e, c in element_to_count.items ():

element_masses = [a for a, b in element_to_isotop_mass_and_abundance [e]]

element_log_abundances = [numpy.log (b) для A, b in a, b in a, b in a, b in a, b in a, b in a, b in a, b in a, b in a, b in a, b in a, b in a, b in a, b in aemportemb element_to_isotop_mass_and_abundance[e]]

    isotopologue_masses, isotopologue_log_abundances = element_to_multinomial_masses_and_log_abundances(element_masses, element_log_abundances, c)

 0isotopologue_mass(10ses)topologue_mass_vectors. append(10ses)topologue_mass_vectors.append0002 abundance_vectors.append (isotopologue_log_abundances)

total_heap_size = уменьшить ((lambda x, y: x*y), [len (mv) для mv in mass_vectors])

K = min (k, total_heap_siz Args)! = 4 или режим == ‘Tree’:

Cartesian_Heap = TreeCartesiansumHeap (Abundance_Vectors)

MODE == ‘TENSOR’:

Cartesian_Heap = TensorCarteSiansHeap (Abundance_Vectors)

lethereSiansiAp (abundance_vectors)

:

:

. )

  log_abundance_and_index = [ cartesian_heap.pop_max_and_index() for i in range(k) ]

  print(‘Наибольшие␣значения␣in␣X_1*X_2*…:’)

  print(‘{:8}␣ :8}␣{:8}’.format(‘log(вероятность)’, ‘вероятность’, ‘масса’) )

  для i в диапазоне (k):

    log_abund, ind = log_abundance_and_index[i]

mass = sum([ mass_vectors[ell][j] для ell,j in enumerate(ind) ])

    print( {:8f}␣{:8f}␣{:8f}’.format(log_abund, numpy. exp(log_abund), mass))

print ()

mass_to_total_abundance = defaultdict (float)

для i в диапазоне (k):

log_abund, ind = log_abundance_and_index [i]

Mass = sum ([mass_vector in enumerate(ind) ])

    mass_to_total_abundance[mass] += numpy. exp(log_abund)

  print(‘Самые␣обильные␣пики:’)

  print( ‘{:8}␣{:8}’. format(‘prob’, ‘mass’))

 для a,m в отсортированном([ (b,a) для a,b в mass_to_total_abundance.items() ], reverse=True):

    print( {:8f}␣{:8f}’.format(a,m) )

if __name__ == ’__main__’:

  main(sys.argv[1:])

Листинг 5: theodolite.py: метод вычисления пиков наиболее распространенных изотопов с использованием иерархического m-мерного метода для нахождения верхних значений k Y.

3 результатов

3.1 Эффективное вычисление изотопного пика

На поддельном компаунде, составленном из
\ceCl800V800He800C800H800N800O100S6Cu800Ga800Ag800Tl800Ne800 без учета стоимости вычисления полиномиальных изотопологов (эта стоимость была одинакова для обоих методов и требовала ≈1 во-вторых), вычисление 512 лучших изотопов с помощью реализации на основе TensorCartesianSumHeap.py заняло 0,002984046 секунд, в то время как реализация на основе TreeCartesianSumHeap. py заняло 0,00146198272 секунды.

3.2 Использование времени и памяти для произвольного Y=X1+X2+⋯+Xm

Задачи различной размерности m выполнялись с длиной вектора n=m, извлечение верхних значений m в Y. Подход грубой силы не был считается из соображений эффективности. Время и использование памяти TensorCartesianSumHeap.py и TreeCartesianSumHeap.py на двойной Xeon с 128 ГБ ОЗУ показаны на Рисунок 2.

Рис. 2. Время и использование памяти TensorCartesianSumHeap.py и TreeCartesianSumHeap.py. Проблемы разного размера м а при k=n=m — время (левая панель) и использование памяти (правое панель) нанесены на график. Использование памяти 0 ГБ связано с достаточно низким след, который команда ps не смогла оценить; поэтому мы показываем только m∈{1024,2048}, для которых оба метода имел ненулевое использование памяти. Растущий разрыв в обоих этих логарифмических графики показывают нелинейное ускорение и преимущество нелинейной памяти. В m=2048, использование памяти TensorCartesianSumHeap.py составляет 66,3 ГБ, в то время как предлагаемый иерархический метод TreeCartesianSumHeap.py использует только 1,15 ГБ.

4 Обсуждение

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

Несмотря на то, что подход, который мы здесь предлагаем, полезен для вычислений интенсивных изотопных пиков, ограниченное количество элементов (в настоящее время m=118) лишь немного выигрывает от нашего подхода. Кроме того, это редко когда многие элементы соединяются в одном соединении. Наш демонстрационная реализация генерирует многочлены наивно, в отличие от Лонцки и др. ; тем больше время работы от этого ненужного наивность в предварительной обработке приглушает ускорение иерархического метод для элементов с несколькими вероятными изотопами; Однако, можно использовать этот иерархический подход, но с многочленами создан ненаивно, как Łącki et al. сделать, что бы вероятно, достигнут скромного ускорения по сравнению с их текущим подходом.

Однако есть случаи, не связанные с расчетом интенсивных изотопных пики, в которых предлагаемый нами иерархический метод дал бы большие практическая польза. К ним относятся максимум апостериорно Байесовский вывод о зависимости формы Y=X1+X2+⋯+Xm [7, 6] . Операции исследовательские приложения включают финансовые рынки, например. , извлечение k самых низких общих предложений в каждом секторе линий поставок для продукта.

Используя такой язык, как javascript, этот метод можно распараллелить легко за счет распараллеливания операций извлечения кучи в узлах на одном уровне дерева. Если доступно достаточно аппаратного параллелизма, среда выполнения полного распространения по дереву будет, таким образом, высота дерево, которое представляет собой ∈Θ(log(m)) всплывающие операции из края кучи. Каждая из этих краевых операций извлечения кучи равна ∈O(log(n)), и, таким образом, время выполнения будет ∈O(log(m)log(n)).

5 В наличии

Исходный код Python из этого метода доступен по адресу https://bitbucket.org/seranglab/theodolite/ (лицензия MIT, бесплатно как для академического, так и для коммерческого использования).

Ссылки

• [1] Д. Бремнер, Т. М. Чан., Э. Д. Демен, Дж. Эриксон, Ф. Уртадо, Дж. Яконо, С. Лангерман и П. Таслакян. Ожерелья, свертки и X+Y. В Алгоритмы-ESA 2006, страницы 160-171. Спрингер, 2006.
• [2] М. Бассик, Х. Хасслер, Г. Дж. Воегингер и У. Т. Циммерманн. Быстрые алгоритмы для задачи максимальной свертки. Письма об исследованиях операций, 15 (3): 133–141, 19.94.
• [3] Грег Фредериксон и Дональд Б. Джонсон. Обобщенный отбор и ранжирование: отсортированные матрицы. SIAM J. Comput., 13:14–30, 02, 1984.
• [4] Грег Н. Фредериксон и Дональд Б. Джонсон. Сложность выбора и ранжирования по x+y и матрицам с отсортированные столбцы. Журнал компьютерных и системных наук, 24(2):197–208, 1982.
• [5] М. К. Лацки, М.

  No related posts.