Поворотный элемент

Эта статья о поворотах в матрицах. Информацию о повороте в алгоритме быстрой сортировки см. в разделе Быстрая сортировка .

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

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

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

Примеры систем, требующих поворота

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

$\left[{\begin{array}{ccc|c}1&-1&2&8\\0&0&-1&-11\\0&2&-1&-3\end{array}}\right]$

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

$\left[{\begin{array}{ccc|c}1&-1&2&8\\0&2&-1&-3\\0&0&-1&-11\end{array}}\right]$

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

$\left[{\begin{array}{cc|c}0.00300&59.14&59.17\\5.291&-6.130&46.78\\\end{array}}\right]$

Эта система имеет точное решение x ₁ = 10,00 и x ₂ = 1,000, но когда алгоритм исключения и обратная замена выполняются с использованием четырехзначной арифметики, небольшое значение a ₁₁ приводит к распространению небольших ошибок округления. Алгоритм без поворота дает аппроксимацию x ₁ ≈ 9873,3 и x ₂ ≈ 4. В этом случае желательно поменять местами две строки так, чтобы находился ₂₁ в положении поворота.

$\left[{\begin{array}{cc|c}5.291&-6.130&46.78\\0.00300&59.14&59.17\\\end{array}}\right].$

Учитывая эту систему, алгоритм исключения и обратная замена с использованием четырехзначной арифметики дают правильные значения x ₁ = 10,00 и x ₂ = 1,000.

Частичный, ладейный и полный поворот

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

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

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

Масштабированное вращение

Разновидностью стратегии частичного поворота является масштабируемый поворот. В этом подходе алгоритм выбирает в качестве элемента сводки запись, которая является самой большой по сравнению с записями в своей строке. Эта стратегия желательна, когда большие различия в величине записей приводят к распространению ошибки округления. Масштабированное вращение следует использовать в системе, подобной приведенной ниже, где записи строк сильно различаются по величине. В приведенном ниже примере было бы желательно поменять местами две строки, поскольку текущий поворотный элемент 30 больше 5,291, но он относительно мал по сравнению с другими записями в этой строке. Без перестановки строк в этом случае ошибки округления будут распространяться, как и в предыдущем примере.

$\left[{\begin{array}{cc|c}30&591400&591700\\5.291&-6.130&46.78\\\end{array}}\right]$

Поворотное положение

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

Ссылки

В эту статью включены материалы из сайта Pivoting on PlanetMath , который доступен под лицензией Creative Commons Attribution/Share-Alike License .

• Р. Л. Берден, Дж. Д. Фейрес, Численный анализ , 8-е издание, Thomson Brooks/Cole, 2005. ISBN   0-534-39200-8
• Г.Х. Голуб, Кредит CF, Матричные вычисления , 3-е издание, Джонс Хопкинс, 1996. ISBN   0-8018-5414-8 .
• Фукуда, Комей ; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота». Математическое программирование, серия Б. Материалы 16-го Международного симпозиума по математическому программированию, состоявшегося в Лозанне, 1997 г. 79 (1–3): 369–395. CiteSeerX   10.1.1.36.9373 . дои : 10.1007/BF02614325 . МР   1464775 . S2CID   2794181 . Препринт постскриптума .
• Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Опорные правила линейного программирования: обзор последних теоретических разработок». Анналы исследования операций . Вырождение в задачах оптимизации. 46–47 (1): 203–233. CiteSeerX   10.1.1.36.7658 . дои : 10.1007/BF02096264 . ISSN   0254-5330 . МР   1260019 . S2CID   6058077 .