Введение перестановок

12. Процесс § 11 формально совпадает с процессом § 8, но без учета перестановок. Их использование весьма просто, и лучше всего описывается на алгорифмическом языке. Имеется основных шагов; на шаге мы определяем столбец столбец Проиллюстрируем конфигурацию непосредственно перед началом шага для случая :

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

(i) Для всех значений от 1 до вычисляем накапливая, если возможно, скалярные произведения. Округляем окончательное значение до одинарной точности и записываем на место (Если верхний предел какой-либо суммы меньше нижнего,

то этой суммой пренебрегаем. Помним, что Если приведение завершено.

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

(iii) Переставляем строки (включая столбцы Округляем текущее до одинарной точности, получаем и записываем на место Это ведущий элемент.

(iv) Для всех значений от до вычисляем и записываем на место

Некоторые пункты требуют специального комментария. Если на каком-либо этапе

то не определены, и мы можем взять любые значения, по модулю меньшие единицы. При этом сохранится численная устойчивость. Наиболее просто взять соответствующие равными нулю. Если используется арифметика с плавающей запятой и накоплением скалярных произведений, то мы мало теряем, если округляются до одинарной точности сразу после вычисления. Тогда каждое а временно может храниться на месте соответствующего до тех пор, пока оно не понадобится для вычисления . В этом случае мы можем обойтись без ячеек, обозначенных При использовании накопления с фиксированной запятой мы должны запоминать с двойной точностью, если желательно получить полную выгоду. Однако, так как таких на на шаге только то в ячейках всегда есть место для величин Надо подчеркнуть, что, за исключением ошибок округления, процесс, который мы сейчас описали, совпадает с процессом в §§ 8, 9. При точных вычислениях перестановки одинаковы.