Навигация
Модификации метода Гаусса
18618
знаков
0
таблиц
16
изображений
2. Модификации метода Гаусса
Метод Гаусса с выбором главного элемента. Основным ограничением метода Гаусса является предположение о том, что все элементы 
, на которые производится деление на каждом шаге прямого хода, не равны нулю. Эти элементы называются главными элементами и располагаются на главной диагонали матрицы A.
Если на некотором шаге прямого хода главный элемент = 0, то дальнейшее решение системы невозможно. Если главный элемент имеет малое значение, близкое к нулю, то возможен сильный рост погрешности из-за резкого возрастания абсолютной величины получаемых в результате деления коэффициентов. В таких ситуациях метод Гаусса становится неустойчивым.
Исключить возникновение подобных случаев позволяет метод Гаусса с выбором главного элемента.
Идея этого метода состоит в следующем. На некотором k-м шаге прямого хода из уравнений исключается не следующая по номеру переменная xk, а такая переменная, коэффициент при которой является наибольшим по абсолютной величине. Этим гарантируется отсутствие деления на нуль и сохранение устойчивости метода.
Если на k-м шаге в качестве главного элемента выбирается 
¹ , то в матрице A¢ должны быть переставлены местами строки c номерами k и p и столбцы с номерами k и q.
Перестановка строк не влияет на решение, так как соответствует перестановке местами уравнений в системе, но перестановка столбцов означает изменение нумерации переменных. Поэтому информация обо всех переставляемых столбцах должна сохраняться, чтобы после завершения обратного хода можно было бы восстановить исходную нумерацию переменных.
Существуют две более простые модификации метода Гаусса:
- с выбором главного элемента по столбцу;
- с выбором главного элемента по строке.
В первом случае в качестве главного элемента выбирается наибольший по абсолютной величине элемент k-й строки (среди элементов 
, i = 
). Во втором - наибольший по абсолютной величине элемент k-го столбца (среди элементов 
, i = ). Наибольшее распространение получила первый подход, поскольку здесь не изменяется нумерация переменных.
Следует заметить, что указанные модификации касаются только прямого хода метода Гаусса. Обратный ход выполняется без изменений, но после получения решения может потребоваться восстановить исходную нумерацию переменных.
LU-разложение. В современном математическом обеспечении ЭВМ метод Гаусса реализуется с использованием LU-разложения, под которым понимают представление матрицы коэффициентов A в виде произведения A = LU двух матриц L и U, где L – нижняя треугольная матрица, U - верхняя треугольная матрица
Если LU-разложение получено, то решение исходной системы уравнений (2) сводится к последовательному решению двух следующих систем уравнений с треугольными матрицами коэффициентов
L Y = B; (6)
U X = Y (7)
линейный алгебраический уравнение численный
где Y = 
- вектор вспомогательных переменных.
Такой подход позволяет многократно решать системы линейных уравнений с разными правыми частями B. При этом наиболее трудоемкая часть (LU-разложение матрицы A) выполняется только один раз. Эта процедура соответствует прямому ходу метода Гаусса и имеет оценку трудоемкости O(n3). Дальнейшее решение систем уравнений (6) и (7) может выполняться многократно (для различных B), причем решение каждой из них соответствует обратному ходу метода Гаусса и имеет оценку вычислительной сложности O(n2).
Для получения LU-разложения можно воспользоваться следующим алгоритмом.
1. Для исходной системы (1) выполнить прямой ход метода Гаусса и получить систему уравнений треугольного вида (5).
2. Определить элементы матрицы U по правилу
uij = Cij (i = 
; j = 
)
3. Вычислить элементы матрицы L по правилам
Расчетные формулы для решения системы (6) имеют следующий вид:
y1 = b1 / l11;
Расчетные формулы для решения системы (7)
xn = yn;
(i = n - 1, n - 2, …, 1).
Похожие работы
... . При этом собственно нахождение обратной матрицы – процесс достаточно трудоемкий и его программирование вряд ли можно назвать элементарной задачей. Поэтому на практике чаще применяют численные методы решения систем линейных уравнений. К численным методам решения систем линейных уравнений относят такие как: метод Гаусса, метод Крамера, итеративные методы. В методе Гаусса, например, работают над ...
... 35437 x4=0.58554 5 x1=1.3179137 x2=-1.59467 x3=0.35371 x4=0.58462 6 x1=1.3181515 x2=-1.59506 x3=0.35455 x4=0.58557 5. Сравнительный анализ различных методов численного дифференцирования и интегрирования 5.1 Методы численного дифференцирования 5.1.1 Описание метода Предположим, что в окрестности точки xiфункция F (x) дифференцируема достаточное число раз. ...
... на языке Turbo Pascal 7.0 для решении систем линейных алгебраических уравнений, используя метод простой итерации. 1.2 Математическая формулировка задачи Пусть А – невырожденная матрица и нужно решить систему где диагональные элементы матрицы А ненулевые. 1.3 Обзор существующих численных методов решения задачи Метод Гаусса В методе Гаусса матрица СЛАУ с помощью равносильных ...
... числа). Далее по формулам (2) последовательно находятся xn-1 , xn-2 ,…, x1 при i=n-1, n-2,...,1 соответственно. Таким образом, решение уравнений вида (1) описываем способом, называемым методом прогонки, сводится к вычислениям по трём простым формулам: нахождение так называемых прогоночных коэффициентов δi, λiпо формулам (3) при i=1,2,…,n (прямая прогонка) и затем неизвестных xi по ...
0 комментариев