Выбор главного элемента по всей матрице

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

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

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

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

так как произведение множителей между и х равно единичной матрице. Поэтому решение есть

Здесь мы используем двухсторонние эквивалентные преобразования но правые множители суть просто матрицы перестановок.

Назовем эту модификацию выбором главного элемента по всей матрице, в отличие от прежнего процесса, который назовем выбором главного элемента по столбцу. Уилкинсон (1961b) показал, что в этом случае

где . В табл. 2 даны значения для некоторых значений

Таблица 2 (см. скан)

Функция много меньше, чем для больших а метод доказательства (27.3) показывает, что достижимая верхняя оценка существенно меньше. В действительности до сих пор не найдено ни одной матрицы, для которой Для матриц вида (26.2) любого порядка максимальный элемент при выборе главного элемента по всей матрице равен 2.

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

(I) На вычислительных машинах с двухступенчатой памятью легче организовать выбор главного элемента по столбцу, чем по всей матрице.

(II) Если матрица имеет значительное число нулевых элементов, то некоторые структуры их расположения сохраняются при выборе

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

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