§ 34. Сравнительная характеристика разложений

Разложение матрицы на множители является основой построения большинства численных методов линейной алгебры. Чем эффективнее осуществляется разложение, тем лучшими характеристиками обычно обладает и метод. Нельзя дать однозначный ответ на вопрос «Какое из разложений лучше?» так как разные задачи предъявляют к разложениям различные требования. Тем не менее по некоторым характеристикам не только можно, но и нужно проводить сравнение. Для исследованных нами разложений такие характеристики приведены в табл. 34.1. Предполагается, что все матрицы квадратные и имеют один и тот же порядок, равный

Скорость. Общее время, затрачиваемое на получение разложения, по существу, определяется числом арифметических операций, которые необходимо при этом выполнить. В графе «Число операций» табл. 34.1 приведены главные члены числа арифметических операций для всех разложений. В случае использования преобразований вращения одну треть от общего числа операций составляют операции сложения, две трети — операции умножения. Для остальных разложений число операций сложения и

Таблица 34.1 (см. скан)Сравнительная характеристика разложений

умножения примерно одинаково. Операции деления и извлечения квадратного корня главный член не определяют.

Самым быстрым разложением является треугольное. Есть некоторые основания предполагать, что ни для какога содержательного разложения, основанного на исключении элементов или процессах ортогонализации, общее число необходимых арифметических операций не может быть меньше, чем у треугольного разложения. Однако другие разложения, получаемые за такое же число операций, существуют. Мы уже отмечали разложение, определяемое методом оптимального исключения [2]. Самое медленное из рассмотренных разложений выполняется в 15 раз дольше, чем самое быстрое.

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

достаточно этого места, нередко требуется дополнительная память. В графе «Дополнительная память» табл. 34.1 приведены главные члены числа полных слов памяти ЭВМ, которые необходимо добавить для размещения сомножителей. При этом предполагается, что вся память, отведенная для исходной матрицы, также используется для сомножителей.

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

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

где функция зависит только от и способа получения разложения.

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

Режим вычислений. Оценки точности, которые приведены в табл. 34.1, гарантируются лишь в том случае, когда разложения осуществляются по рассмотренным выше вычислительным схемам. Любое изменение вычислительной схемы должно обосновываться соответствующим анализом ошибок, так как иначе возможна катастрофическая потеря точности.

Символ в графе «Режим» табл. 34.1 означает, что для достижения соответствующей точности можно ограничиться вычислениями с одинарной точностью. Символ означает, что для достижения указанной точности использование операций накопления обязательно.

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

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

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

3. При выполнении преобразований отражения невозможен значительный рост величин элементов промежуточных вычислений.

4. Информация о сомножителях может быть практически размещена на месте исходной матрицы. Требуется лишь небольшая дополнительная память.

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

УПРАЖНЕНИЯ

(см. скан)