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

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

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

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

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

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

В случае исключения Гаусса алгоритм требует, чтобы опорные элементы не были нулевыми. Перестановка строк или столбцов в случае нулевого опорного элемента необходима. Система ниже требует перестановки строк 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 ₁₁ приводит к распространению небольших ошибок округления. Алгоритм без поворота дает приближение x ₁ ≈ 9873,3 и x ₂ ≈ 4. В этом случае желательно, чтобы мы поменяли местами две строки так, чтобы a ₂₁ оказалась в позиции поворота

${\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 Journal 2, № 2: 58-61.
2. Пул, Джордж; Нил, Ларри (ноябрь 2000 г.). «Стратегия поворота ладьи». Журнал вычислительной и прикладной математики . 123 (1–2): 353–369. Bibcode : 2000JCoAM.123..353P. doi : 10.1016/S0377-0427(00)00406-4 .

• RL Burden, JD Faires, Numerical Analysis , 8-е издание, Thomson Brooks/Cole, 2005. ISBN 0-534-39200-8 
• GH Golub, CF Loan, Матричные вычисления , 3-е издание, Университет Джонса Хопкинса, 1996. ISBN 0-8018-5414-8 . 
• Фукуда, Комей ; Терлаки, Тамас (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота». Математическое программирование, серия B. Статьи 16-го Международного симпозиума по математическому программированию, состоявшегося в Лозанне, 1997. 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373 . doi :10.1007/BF02614325. MR  1464775. S2CID  2794181. Препринт Postscript.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on latest theory developments". Annals of Operations Research . Вырожденность в задачах оптимизации. 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658 . doi :10.1007/BF02096264. ISSN  0254-5330. MR  1260019. S2CID  6058077.