Сравнение методов триангуляризации

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

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

откуда

и опять здесь самое удовлетворительное состояние дела, так как спектральное число обусловленности матрицы равно квадратному корню из спектрального числа обусловленности матрицы А. Если А — ленточная матрица, т. е. если для то для так что данная форма используется полностью. Возможно, что единственное замечание, которое мы можем сделать не в пользу метода, состоит в том, что требуется операций извлечения квадратного корня тогда как в обычном методе Гаусса не требуется ни одной.

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

(I) Метод Гаусса с выбором главного элемента по столбцу или по всей матрице: умножении.

(II) Триангуляризация с матрицами типа умножений.

(III) Триангуляризация Хаусхолдера: умножений, квадратных корней.

(IV) Триангуляризация Гивенса; умножений, квадратных корней.

В отношении скорости методы (I) и (II) лучше, чем методы (III) и (IV), и, кроме этого, они несколько проще. На многих вычислительных машинах методы (I) и (II) могут выполняться с двойной точностью почти за то же

самое время, как метод (IV) с одинарной точностью. К сожалению, в отношении численной устойчивости методы (I) и (II) с теоретической точки зрения менее удовлетворительны. Мы видели, что если используем выбор главного элемента по столбцу, то последний ведущий элемент может быть в раз больше, чем максимальный элемент в исходной матрице и, следовательно, строгие априорные верхние оценки, которые мы можем получить для эквивалентного возмущения исходной матрицы, содержат этот множитель Однако на основе опыта можно заключить, что хотя такая оценка и достижима, она совсем нереальна для практических случаев. В действительности какое-либо возрастание вообще редко имеет место, и если может накапливаться скалярное произведение, то эквивалентные возмущения в исходной матрице исключительно малы.

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

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

58. Если подходить к решению систем несколько осторожно и иметь быстродействующую вычислительную машину, то можно склониться к использованию метода Хаусхолдера для общей триангуляризации. На практике я предпочитал использовать метод Гаусса с выбором главного элемента по столбцу, рискуя маловероятной возможностью большого роста опорных элементов. Искушение применять его было большое, потому что вычислительные машины, которыми я пользовался, имели устройства для накопления скалярных произведений. Результаты, полученные таким путем, вероятно, в общем случае были более точными, чем результаты, которые можно было бы получить по методу Хаусхолдера. Для матриц Хессенберга даже самые осторожные вычислители могут, наверное, отдать предпочтение методу Гаусса с выбором главного элемента по столбцу; для трехдиагональных матриц вообще нет больше никаких причин для того, чтобы отдать предпочтение методу Хаусхолдера.

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

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

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