2.2. Модификации метода Гаусса. Сравнение прямых методов.

Метод оптимального исключения имеет ту же скорость, что и метод Гаусса,

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

Метод окаймления построен на последовательном рассмотрении матриц

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

Эскалаторный метод тесно связан с методом окаймления и был предложен

Дж. Морисом в 1947г. Существенным достоинством метода автор считает наличие надежного контроля, при помощи которого можно регулировать точность вычислений; в частности, метод дает довольно надежный результат, даже если определитель матрицы системы уравнений относительно мал /1/.

Хотя метод, по-видимому, применим для систем общего вида, в /1/ он

изложен для систем уравнений с симметричной матрицей коэффициентов при неизвестных в виде

(2.15)

или в матричном виде

Путем введения вспомогательной матрицы и замены неизвестных

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

Метод ортогонализации /3/ поначалу привлек внимание в надежде на то,

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

Метод Гаусса-Жордана /3, 4/ основан на преобразовании матрицы

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

Метод прогонки. Для решения хорошо обусловленных линейных

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

В дополнение к классификации п.1.1, в задачах механики часто встречаются

матрицы:

а) ленточные (ширина ленты элементов);

б) почти треугольные (ненулевые элементы есть не только в верхнем треугольнике, но и в примыкающей к нему побочной диагонали, то есть при )

в) квазидиагональные;

г) ящичные (клеточно-диагональные), и тому подобное:

При обходе нулевых элементов решение системы с почти треугольной

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

Наиболее важным частным случаем метода Гаусса, является метод

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

Такие системы записывают в каноническом виде

(2.16)

Формула (2.16) называется разностным уравнением 2-го порядка, или

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

(2.17)

Уменьшим в (2.17) индекс на 1 и подставим в уравнение (2.16)

откуда

Чтобы это выражение совпало с (2.17), необходимо, чтобы его дроби были

равны соответственно и . Отсюда следует удобная запись формул прямого хода

(2.18)

Попутно легко находится определитель исходной трехдиагональной

матрицы

(2.19) Формулы метода прогонки (2.18) и (2.17) требуют всего ячеек памяти и действий, т.е. гораздо экономичнее метода исключений в чистом виде.

Примечания:

1. Для начала счета удобно принять и , которые формально неизвестны, равными нулю;

2. Если выполнено условие преобладания диагональных элементов по модулю

(2.20)

то в формулах прямого хода (2.18) не возникает деления на нуль и тем самым исходная система (2.16) имеет единственное решение и устойчива относительно ошибок округления. Для хорошо обусловленных систем типа (2.16) прогонка достаточно устойчива даже при нарушении условия (2.20).

Метод квадратных корней применим только для линейных систем с

эрмитовой матрицей (то есть ; эрмитова матрица с вещественными элементами является симметричной). Метод основан на представлении исходной эрмитовой матрицы в виде произведения трех матриц

(2.21)

Здесь:

- диагональная матрица с элементами на главной диагонали то есть ,

- верхняя треугольная матрица ( при ),

- эрмитово сопряженная с ней нижняя треугольная матрица.

Для полной определенности разложения потребуем вещественности и

положительности диагональных элементов матрицы Развернув (2.21) по правилам п. 1.1 для , получим формулы для элементов матриц и , причем для диагональных элементов матрицы выражение будет под знаком радикала, что породило название метода.

Когда для всех все элементы матриц найдены, то решение

линейной системы сводится к последовательному решению трех систем (двух треугольных и одной диагональной):

(2.22)

что делается обычным обратным ходом. При необходимости вычисляется определитель матрицы

(2.23)

Метод квадратных корней требует меньше памяти и вдвое быстрей метода Гаусса, что понятно, так как метод использует информацию о симметрии матрицы.

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

Примечания:

1. Если эрмитова матрица вещественная и симметричная, то никаких комплексных чисел при вычислениях не возникает, и матрица также вещественная. Если к тому же матрица положительно определенная (см. п.1.1), то есть все ее главные миноры положительны, то все , и формулы для вычисления элементов матрицы могут быть несколько упрощены.

2. Метод квадратных корней эффективен и часто применяется для численного решения интегральных уравнений типа Фредгольма с симметричным ядром, так как эти задачи сводятся к линейной системе с симметричной матрицей, причем при регуляризации таких задач симметрия матрицы сохраняется /3/.