Модификации метода Гаусса

При решении системы уравнений

простейшим вариантом метода Гаусса имеют место большие погрешности. Причина заключается в появлении больших коэффициентов, при округлении которых получается большая абсолютная погрешность D ~ 0.5. В свою очередь, большие коэффициенты получаются после деления на маленький ведущий коэффициент .

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

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

Недостаток модификации. Предположим х_i найден с погрешностью D. Тогда при поиске какого-либо х_s надо, согласно формуле обратного хода, умножать . При этом погрешность D также умножится на . Если значение велико, то погрешность возрастет.

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

Вторая модификация метода Гаусса – поиск по столбцам. Указанное требование можно обеспечить, если неизвестные х_i исключаются в произвольном порядке, а в ведущей строке ищется , доставляющий . Это и будет очередной ведущий элемент. После определения ведущего элемента меняем местами k-й и r-й столбцы.

Внимание. При такой замене меняется нумерация неизвестных x_i. Чтобы обеспечить такую замену, надо при программировании ввести массив p₁,…p_n с настоящими номерами неизвестных. В начале прямого хода все p_i = i – обычная нумерация. После нахождения ведущего элемента меняем местами p_k и p_r. При обратном ходе по формуле (7) вычисляются перенумерованные x_i. После вычисления всех неизвестных надо положить y[p[i]]:=x[i], и массив y[i] будет окончательным решением задачи.

Третья модификация метода Гаусса – полный поиск. В качестве ведущего выбирается элемент , доставляющий . При этом меняются местами k-й и r-й столбцы, p_k и p_r, а также m-я и k-я строки. Эта модификация обеспечивает максимальную точность, но и наиболее сложна.

Применение метода Гаусса для решения различных задач линейной алгебры

1. Обращение матриц.Пусть необходимо вычислить обратную матрицу к квадратной матрице А. Обозначим Х = А^–1. Как известно АХ = I, где I – единичная матрица, в которой по диагонали расположены 1, а остальные элементы – 0. Иными словами, i-й столбец матрицы I равен

(1 стоит на i-м месте). Пусть х⁽ⁱ⁾ – i-й столбец матрицы Х. Тогда, в силу правила умножения матриц (строка умножается на столбец) имеем А х⁽ⁱ⁾ = e⁽ⁱ⁾. Значит, для обращения матрицы надо решить n систем линейных уравнений с одинаковыми матрицами и разными правыми частями:

Ах = е⁽¹⁾; Ах = е⁽²⁾; …; Ах = е⁽ⁿ⁾. (2.1)

Решив эти системы, получим, что найденные решения х⁽¹⁾, х⁽²⁾, …, х⁽ⁿ⁾ являются столбцами матрицы А^–1.

2. Вычисление определителей.В процессе преобразования матрицы А к треугольному виду методом Гаусса мы выполняли с ней следующие действия:

1) переставляли строки или столбцы в зависимости от модификации метода;

2) делили ведущую строку на ненулевой ведущий элемент;

3) к строкам матрицы прибавляли ведущую строку, умноженную на некоторое число.

Как известно, при таких преобразованиях определитель матрицы претерпевает соответствующие изменения:

1) изменяет знак;

2) делится на тот же элемент;

3) не меняется.

После прямого хода матрица А будет приведена к верхнему треугольному виду с единицами на главной диагонали. Определитель такой матрицы равен, очевидно, 1. С учетом тех изменений, которые претерпевал определитель матрицы А в процессе преобразований, имеем следующую формулу:

det A = (–1)^s × a₁₁ × a₂₂ ×…× a_{n n},

где a_{j j} – ведущие элементы, s – число перестановок строк и/или столбцов при поиске ведущих элементов.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Вручную реализовать метод Гаусса (с поиском по строкам, по столбцам, по всей матрице – в зависимости от варианта задания) для данной системы уравнений

и выполнить следующие задания

1) Решить эту систему уравнений

2) Вычислить определитель матрицы данной системы (методом Гаусса – см. п 2).

3) Обратить матрицу этой системы (методом Гаусса – см. п 1).

В дальнейшем используйте результат решения данной задачи в качестве тестового примера.

2. Составить программу решения линейной системы методом Гаусса (с поиском по строкам, по столбцам, по всей матрице – в зависимости от варианта задания) и выполнить обращение матриц с использованием этой программы.

1. 6. 11.

2. 7. 12.

3. 8. 13.

4. 9. 14.

5. 10. 15.

16.

Не нашли, что искали? Воспользуйтесь поиском по сайту: