|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
П 3.1 Метод Гаусса решения систем линейных алгебраических уравнений
Рассмотрим метод Гаусса. Имеем систему линейных алгебраических уравнений:
или в матричном виде AX = f, (2) где А – вещественная квадратная матрица порядка n, f – заданный Метод Гаусса решения системы (1) реализуется в два этапа: прямой и обратный ход. Первый этап состоит в последовательном исключении неизвестных
где
Рассмотрим теперь оставшиеся уравнения системы (1):
Умножим (3) на
где
Тем самым осуществили первый шаг метода Гаусса и получили систему (5), в которой матрица системы имеет вид:
т.е. неизвестное Если
При этом первое уравнение полученной системы остается без изменения. Исключая аналогичным образом неизвестные
Матрица системы (7) будет иметь вид верхней треугольной матрицы с единичными элементами на главной диагонали
Получение системы (7) составляет прямой ход метода Гаусса, в котором коэффициенты уравнений преобразуются по следующему правилу [18]:
Вычисление правых частей системы (7) осуществляется по формулам
Второй этап, т.е. обратный ход, заключается в нахождении неизвестных
Пример 1. Решить систему уравнений методом Гаусса. Решение: Прямой ход. Разделим первое уравнение на 3, получим систему: Умножим первое уравнение на 2 и сложим со вторым уравнением системы, получим: Умножим первое уравнение на –2 и сложим с третьим уравнением системы, получим: Разделим второе уравнение на 1/3, получим: Умножим второе уравнение на 1/3 и сложим с третьим уравнением системы, получим: Разделим третье уравнение на 5, получим:
Обратный ход. Из третьего уравнения находим Из второго уравнения находим Из первого уравнения получаем Установим связь метода Гаусса с LU-разложением. Прямой ход метода Гаусса преобразует исходную систему уравнений (1) в эквивалентную систему
UX = g,(11)
где U – верхняя треугольная матрица с единицами на главной диагонали. Проанализировав соотношения (9), можно записать: f = Lg, (12)
где L – нижняя треугольная матрица с ненулевыми элементами
Подставляя (13) в (11), получаем
UX = или LUX = f. (14)
Сопоставляя (14) и уравнение (2), приходим к выводу, что в результате применения метода Гаусса получено разложение исходной матрицы А в произведение Значения элементов матрицы L и U находятся по рекуррентным соотношениям [19]
Таким образом, метод Гаусса можно трактовать следующим образом. Сначала производится разложение матрицы А в произведение двух треугольных матриц L и U, т.е.
Lg = f, UX = g.
Решая первую систему (прямой ход), находим вектор g. Одновременно происходит разложение В результате решения второй системы (обратный ход) находим решение задачи – вектор X.
Пример 2. Решить систему методом Гаусса, используя LU-разложение:
Решение: Выполним операцию факторизации. Представим матрицу системы При k =1: При k =2:
При k =3:
В результате получены две треугольные матрицы:
Решим систему линейных уравнений Lg = f. Найдем вектор g: Решим систему линейных уравнений UX =g. Найдем искомый вектор X:
Пример 3. Реализовать алгоритм LU-разложения для произвольной матрицы. При описании алгоритма используются объекты класса «SquareMatrix» и методы данного класса: getRowCount (количество строк матрицы), getElement (получение значения элемента) и setElement (установка значения). Реализация на языке программирования С++ может иметь следующий вид:
void FactorizationAlgorithms:: LU_decomposition (SquareMatrix A, SquareMatrix LU){ int n = A. getRowCount (); /*Нахождение первого столбца матрицы L и первой строки матрицы U*/ for (int i = 0; i < n; i++){ LU.setElement(i, 0, A.getElement(i, 0)); if ((i+1)<n) LU.setElement(0,i+1,A.getElement(0,i+1)/LU.getElement(0, 0)); } /*Вычисление по формулам (15)*/ for (int i = 1; i < n; i++){ for (int j = 1; j < n; j++){ if (i >= j) /*Нижняя треугольная матрица*/ { double sum = 0; for (int k = 0; k < j; k++) sum += LU.getElement(i, k)*LU.getElement(k, j); LU.setElement(i, j, A.getElement(i, j) - sum); } else /*Верхняя треугольная матрица*/ { sum = 0; for (int k = 0; k < i; k++) sum += LU.getElement(i, k)*LU.getElement(k, j); LU.setElement(i,j,(A.getElement(i,j)-sum)/LU.getElement(i,i)); } } }
В результате факторизации имеем квадратную матрицу, в которой на главной диагонали и ниже расположены элементы матрицы L, выше главной диагонали расположены элементы матрицы U. Использование памяти при такой структуре полученной матрицы является оптимальным.
Пример 4. Сформировать на языке программирования С++ алгоритм метода Гаусса на основе факторизации. При описании алгоритма используются объекты и методы классов «SquareMatrix», «Vector» и «FactorizationAlgorithms».
void DirectMethodsFactorization:: gaussMethod(SquareMatrix A, Vector f){
/*Создание матрицы LU, векторов g и x */ int n = A.getColCount(); SquareMatrix LU = SquareMatrix(n); Vector x = Vector(n); Vector g = Vector(n); /* LU – факторизация. */ FactorizationAlgorithms FA; FA.LU_decomposition(A, LU); /* Решение системы Lg = f (прямой ход метода Гаусса), где L – нижняя треугольная матрица с ненулевыми элементами на главной диагонали */ ................................................. /* Решение системы Ux = g (обратный ход метода Гаусса), где U– верхняя треугольная матрица с единичной главной диагональю */ ................................................. /* Вывод вектора - решения */ } Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.014 сек.) |