4.2 Вычислительная устойчивость методов решения слау

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

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

4.3 Методы исключения

4.3.1 Схема единственного деления

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

, , (4.3)

, (4.4)

, (4.5)

, , . (4.6)

После -го шага матрица системы принимает вид

. (4.7)

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

, , . (4.8)

Подсчитаем число арифметических операций, необходимых для решения системы (4.1) по схеме единственного деления. Так как выполнение операций умножения и деления на ЭВМ требует гораздо больше времени, чем выполнение сложений и вычитаний, то подсчитаем только число умножений и делений.

1. Вычисление коэффициентов , , по формулам (4.3) требует

делений.

2. Вычисление всех коэффициентов по формулам (4.5) требует

умножений.

Таким образом, вычисление элементов верхней треугольной матрицы требует

операций умножения и деления.

3. Вычисление правых частей по формулам (4.4) требует делений, а нахождение по формулам (6)

умножений.

Следовательно, для вычисления правых частей необходимо

операций умножения и деления.

В итоге для осуществления прямого хода метода Гаусса необходимо выполнить

действий.

4. Для осуществления обратного хода метода Гаусса по формулам (4.8) необходимо выполнить

умножений.

Окончательно получаем, что для реализации схемы единственного деления метода Гаусса необходимо выполнить

операций умножения и деления.

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

ЛЕКЦИЯ № 8