Сводной элемент

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

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

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

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

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

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

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

${\ displaystyle \ left [{\ begin {array} {ccc | c} 1 & -1 & 2 & 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]}$

Эта система имеет точное решение х ₁ = 10.00 и х ₂ = 1.000, но когда алгоритм ликвидации и замены в обратном направлении выполняются с использованием четырех цифр , арифметику, небольшое значение через ₁₁ причин небольшие ошибки округления , чтобы быть размножены. Алгоритм без поворота дает приближение х ₁ ≈ 9873.3 и х ₂ ≈ 4. В этом случае желательно, чтобы переставить две строки , так что ₂₁ находится в положении поворота

${\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]

Масштабируемое вращение [ править ]

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

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

Положение поворота [ править ]

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

Ссылки [ править ]

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

• RL Burden, JD Faires, Численный анализ , 8-е издание, Thomson Brooks / Cole, 2005. ISBN  0-534-39200-8
• GH Голуб, CF Loan, Matrix Computations , 3-е издание, Johns Hopkins, 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 . Руководство по ремонту  1464775 . Постскриптум препринт .
• Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Правила поворота для линейного программирования: обзор последних теоретических разработок». Анналы исследований операций . Вырождение в задачах оптимизации. 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658 . DOI : 10.1007 / BF02096264 . ISSN  0254-5330 . Руководство по ремонту  1260019 .