Модификации метода Гаусса
При решении системы уравнений
простейшим вариантом метода Гаусса имеют место большие погрешности. Причина заключается в появлении больших коэффициентов, при округлении которых получается большая абсолютная погрешность D ~ 0.5. В свою очередь, большие коэффициенты получаются после деления на маленький ведущий коэффициент .
Вывод: для уменьшения влияния ошибок округления надо выбирать ведущий элемент не просто отличный от 0, но и достаточно большой.
Первая модификация метода Гаусса – поиск по строкам. В алгоритме ведущий элемент надо выбирать из условия .
Недостаток модификации. Предположим хi найден с погрешностью D. Тогда при поиске какого-либо хs надо, согласно формуле обратного хода, умножать . При этом погрешность D также умножится на . Если значение велико, то погрешность возрастет.
Вывод: надо обеспечить, чтобы ведущий элемент был не просто большим, а самым большим по модулю в своей строке. Тогда при нормировке ведущей строки все прочие коэффициенты, согласно формуле (5), будут по модулю меньше 1, и ошибки будут уменьшаться.
Вторая модификация метода Гаусса – поиск по столбцам. Указанное требование можно обеспечить, если неизвестные хi исключаются в произвольном порядке, а в ведущей строке ищется , доставляющий . Это и будет очередной ведущий элемент. После определения ведущего элемента меняем местами k-й и r-й столбцы.
Внимание. При такой замене меняется нумерация неизвестных xi. Чтобы обеспечить такую замену, надо при программировании ввести массив p1,…pn с настоящими номерами неизвестных. В начале прямого хода все pi = i – обычная нумерация. После нахождения ведущего элемента меняем местами pk и pr. При обратном ходе по формуле (7) вычисляются перенумерованные xi. После вычисления всех неизвестных надо положить y[p[i]]:=x[i], и массив y[i] будет окончательным решением задачи.
Третья модификация метода Гаусса – полный поиск. В качестве ведущего выбирается элемент , доставляющий . При этом меняются местами k-й и r-й столбцы, pk и pr, а также m-я и k-я строки. Эта модификация обеспечивает максимальную точность, но и наиболее сложна.
Применение метода Гаусса для решения различных задач линейной алгебры
1. Обращение матриц.Пусть необходимо вычислить обратную матрицу к квадратной матрице А. Обозначим Х = А–1. Как известно АХ = I, где I – единичная матрица, в которой по диагонали расположены 1, а остальные элементы – 0. Иными словами, i-й столбец матрицы I равен
(1 стоит на i-м месте). Пусть х(i) – i-й столбец матрицы Х. Тогда, в силу правила умножения матриц (строка умножается на столбец) имеем А х(i) = e(i). Значит, для обращения матрицы надо решить n систем линейных уравнений с одинаковыми матрицами и разными правыми частями:
Ах = е(1); Ах = е(2); …; Ах = е(n). (2.1)
Решив эти системы, получим, что найденные решения х(1), х(2), …, х(n) являются столбцами матрицы А–1.
2. Вычисление определителей.В процессе преобразования матрицы А к треугольному виду методом Гаусса мы выполняли с ней следующие действия:
1) переставляли строки или столбцы в зависимости от модификации метода;
2) делили ведущую строку на ненулевой ведущий элемент;
3) к строкам матрицы прибавляли ведущую строку, умноженную на некоторое число.
Как известно, при таких преобразованиях определитель матрицы претерпевает соответствующие изменения:
1) изменяет знак;
2) делится на тот же элемент;
3) не меняется.
После прямого хода матрица А будет приведена к верхнему треугольному виду с единицами на главной диагонали. Определитель такой матрицы равен, очевидно, 1. С учетом тех изменений, которые претерпевал определитель матрицы А в процессе преобразований, имеем следующую формулу:
det A = (–1)s × a11 × a22 ×…× an n,
где aj 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.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|