Курсовая работа: Решение системы линейных уравнений

Первое уравнение в дальнейших преобразования не участвует. Описанный выше процесс исключения неизвестных применим к матрице размерами (n -1) n . После k аналогичных шагов получим k приведенных уравнений с коэффициентами

и матрицу размерами (n - k ) ( n - k +1), элементы которой вычисляются по формулам

.

Элементы , на которые осуществляется деление, называются ведущими элементами метода Гаусса и не должны равняться нулю. Прямой ход метода Гаусса заканчивается после n шагов определением .

Обратный ход метода Гаусса заключается в последовательном определении компонент решения, начиная с х_n и заканчивая х₁ , по следующим формулам:

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

Метод оптимального исключения. В целях экономии оперативной памяти (примерно в 4 раза) операции прямого и обратного хода метода Гаусса выполняются попеременно. На первом шаге после приведения первого уравнения исключается неизвестное x₁ из второго уравнения, а затем с помощью приведенного второго уравнения - неизвестное x₂ из первого. После ( k -1) таких шагов матрица системы имеет вид

.

На k - м шаге, используя первые k уравнений, исключаем неизвестные x₁ ,..,x _k из ( k +1) -го уравнения. Затем посредством этого уравнения исключается неизвестное x_k+1 из первых k уравнений и т.д. В результате прямого хода матрица системы приводится к диагональному виду с единицами на главной диагонали. При этом отпадает необходимость обратного хода, поскольку столбец правой части приведенной матрицы и является вектором решения.

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

.

Как и в методе оптимального исключения, матрица системы приводится к диагональному виду и вектором решения является столбец .

LU - разложение. Матрицу A можно представить в виде произведения нижней треугольной матрицы (включая диагональ) L (lower) и верхней треугольной матрицы U ( upper ) , т.е. A = LU . Это равенство равносильно n² числовым равенствам

.

Разложение матрицы A на множители обычно получают посредством алгоритма, который называется компактной схемой метода Гаусса. Элементы l_{i m} и U _{m i} могут быть вычислены по формулам

Тогда решение системы Ax=b сводится к последовательному решению двух систем - Ly=b и Ux=y.

Рассмотренный метод можно применять к решению серии систем с одной и той же матрицей.

Метод простых итераций (Якоби).

Для решения итерационным методом система линейных алгебраических уравнений Ax = b должна быть приведена к виду x = Gx + f , где G - некоторая матрица, f - преобразованный вектор свободных членов. Затем выбирается начальное приближение - произвольный вектор x ⁽⁰⁾ - и строится рекуррентная последовательность векторов x ⁽¹⁾ , x ⁽²⁾ ,..., x ^{( k )} ,... по формуле

.

Для сходимости этой последовательности при любом начальном приближении необходимо и достаточно , чтобы все собственные значения матрицы G были по абсолютной величине меньше единицы. На практике это трудно проверить, и обычно пользуются достаточными условиями сходимости - итерации сходятся, если какая-нибудь норма матрицы меньше единицы, т.е.

или .

Чем меньше норма матрицы G , тем быстрее сходится итерационный процесс.

Преобразование системы можно осуществить, просто решая каждое i -е уравнение относительно x_i :

.

Метод Якоби использует следующий алгоритм построения приближений: