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

Ненулевой элемент матрицы, выбранный алгоритмом

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

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

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

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

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

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

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

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

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

${\displaystyle \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 11 _{приводит} к распространению небольших ошибок округления. Алгоритм без поворота дает аппроксимацию x ₁ ≈ 9873,3 и x ₂ ≈ 4. В этом случае желательно поменять местами две строки так, чтобы 21 находился в положении поворота _.

${\displaystyle \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.

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

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

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

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

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

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

${\displaystyle \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 .

1. Эдельман, Алан, 1992. Полная поворотная гипотеза исключения Гаусса неверна. Журнал Mathematica 2, вып. 2:58-61.
2. Пул, Джордж; Нил, Ларри (ноябрь 2000 г.). «Стратегия поворота ладьи». Журнал вычислительной и прикладной математики . 123 (1–2): 353–369. Бибкод : 2000JCoAM.123..353P. дои : 10.1016/S0377-0427(00)00406-4 .

• Р. Л. Берден, Дж. Д. Фейрес, Численный анализ , 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. MR  1464775. S2CID  2794181. Препринт постскриптума.
• Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Опорные правила линейного программирования: обзор последних теоретических разработок». Анналы исследования операций . Вырождение в задачах оптимизации. 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658 . дои : 10.1007/BF02096264. ISSN  0254-5330. MR  1260019. S2CID  6058077.