Исторически первые итерационные методы основывались на циклическом покомпонентном изменении вектора решения, осуществляемом обнулением соответствующих коэффициентов вектора невязки. Подобная методика уточнения решения получила название релаксация.

В настоящее время такие методы в их классической формулировке практически не применяются, существуют определенные классы задач, для которых разработаны их модификации.

Прямые методы решения СЛАУ.

К прямым (или точным) методам решения СЛАУ относятся алгоритмы, которые позволяют получить точное решение системы за конечное число арифметических действий. Решение задач такими методами осуществляется поэтапно: на первом этапе систему преобразуют к тому или иному простому виду, на втором - решают упрощенную систему и получают значения неизвестных.

Запишем систему линейных алгебраических уравнений в развернутом виде:

где x₁, x₂,., x_n - неизвестные величины, b₁, b₂,., b_{n -} элементы правой части. Если определитель системы отличен от нуля, то она имеет единственное решение. Для удобства дальнейших преобразований обозначим элементы правой части а_{i (n+1)} и запишем расширенную матрицу размерами n (n+1), которая содержит всю информацию о системе:

1.2 Анализ существующих методов решения СЛАУ

Наиболее известным способом решения линейных систем вида (1) является метод последовательного исключения неизвестных - метод Гаусса (GE).

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

Треугольная структура системы позволяет последовательно одно за другим вычислять значения неизвестных, начиная с последнего. Этот процесс последовательного вычисления значений неизвестных называют обратным ходом метода Гаусса [1].

На каждом этапе прямого хода уравнения системы переставляют так, чтобы деление производилось на наибольший по модулю в данном столбце элемент. Числа, на которые производится деление в методе Гаусса, называются ведущими или главными элементами. Отсюда название рассматриваемой модификации метода, исключающей деление на нуль и уменьшающей вычислительные погрешности.

Упорядочивание по столбцам требует внесение в алгоритм следующих изменений: между строками 1 и 2 нужно сделать вставку (перед этим целесообразно произвести масштабирование системы, разделить все числа каждой строки на наибольшее число строки): найти m k такое, что; если a_mk=0, остановить работу алгоритма ("однозначного решения нет"), иначе поменять местами b_k и b_m, a_kj и a_mj при всех j = k, …, N.

LU-разложение матриц

Если все главные миноры квадратной матрицы A отличны от нуля, то существуют такие нижняя L и верхняя U треугольные матрицы, что A = LU. Если элементы диагонали одной из матриц L или U фиксированы (ненулевые), то такое разложение единственно.

Реализация LU-разложения с фиксированием диагонали верхней треугольной матрицы называется методом Краута. Рассмотрим разложение матриц при фиксировании диагонали нижней треугольной матрицы (l_ij = 1 при i = j) - метод Дулитла. Далее находят l_ij при i j (l_ij = 0 при i j) и u_ij при i j (u_ij = 0 при i j) такие, что

Выполнив перемножение матриц, на основе поэлементного приравнивания левых и правых частей приходим к N N матрице уравнений

относительно N N-матрицы неизвестных

u₁₁, u₁₂, …, u_1N

l₂₁, u₂₂, …, u_2N

……………….

l_N1, l_N2, …, u_{NN (}3)

Все отличные от 0 и 1 элементы матриц L и U могут быть однозначно вычислены с помощью всего двух формул

(где i j), (4)

(i j). (5)

Для реализации LU-разложения по данным формулам существует большое количество различных методов, например, построчное вычисление, т.е. пока не вычислена i-ая строка матриц L и U, алгоритм не модернизирует i+1 строку.

Решение СЛАУ с помощью LU-разложения матриц

Если матрица A исходной системы (1) разложена в произведение треугольных матриц L и U, то вместо (2) можно записать эквивалентное уравнение

LUx=b.

Введя вектор вспомогательных переменных y, последнее выражение можно переписать в виде системы

Решение данной системы с квадратной матрицей коэффициентов свелось к последовательному решению двух систем с треугольными матрицами коэффициентов [1].

Все y_i могут быть найдены из системы Ly=b при i=1, 2,…, N по формуле

( (6)

Значения неизвестных x_i находятся из системы Ux=y в обратном порядке, т.е. при i=N, N-1,…, 1, по формуле (обратный ход)

(7)

Решение СЛАУ посредством LU-факторизации сводится к организации вычислений по четырем формулам: совокупности формул (4) - (5) для получения матрицы L+U-I (3) ненулевых и неединичных элементов матриц для L и U, формулы (6) для получения вектора свободных членов треугольной системы Ux=y и формулы (7), генерирующей решение исходной системы (1).

Решение линейных систем с помощью LU-разложения - это просто другая схема реализации метода Гаусса.

Подход, предложенный Жорданом, позволяет получить решения с помощью только прямого хода. При реализации этого метода элементы матрицы обнуляются как под, так и над главной диагональю. В результате данного подхода вектор-решение находится на месте вектора свободных членов, а на месте исходной матрицы находится единичная [2].

Рассмотрим данный метод без выбора ведущего элемента.

Пусть a₁₁ ведущий элемент. На первом этапе первая строка подвергается нормировке ведущим элементом, а затем происходит обнуление поддиагональных элементов. В результате первого этапа получаем эквивалентную систему.

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

Прямые методы приводят к точному решению СЛАУ при точном выполнении соответствующих арифметических операций (без округлений). Реальные вычисления базируются на арифметики усеченных до определенного количества разрядов, чисел. Как отражается на результатах решения системы подмена арифметики действительных чисел машинной арифметикой, зависит от самой решаемой системы, параметров компьютера, системы представления данных, способов реализации алгоритмов.

Вместо точного решения СЛАУ (1) прямой метод дает приближенное решение x₀. Метод Гаусса порождает относительную ошибку решения порядка N2^-lсondA, где l-число двоичных разрядов, выделяемых компьютером под мантиссу вещественного числа, а condA число обусловленности condA=||A||||A^-1|||_max|/|_min|. Подставив x₀ в выражение невязки полученного вектора-значения r₀=b-Ax_0, можно судить о близости найденного решения x₀ к точному решению x. Если ||r₀||₂-недостаточно малая величина, то следует искать вектор-поправку p такой, что x₀+p=x есть точное решение системы (1), т.е.

A (x₀+p) =b,

которое равносильно векторно-матричному уравнению

Ap=r₀.

Нахождение поправки сводится к решению такой же системы, как и (1), где в качестве вектора свободных членов взят вектор невязок. Делают не более двух-трех шагов уточнения, рекомендуется производить вычисление невязок в режиме накопления. Если в этом процессе не происходит сближения x_k при k=2, 3, то данная система плохо обусловлена и ее решение не может быть найдено с требуемой точностью без привлечения дополнительной информации об исходной задаче.

Применяемые на практике численные методы решения СЛАУ делятся на две группы - прямые и итерационные.

В прямых или точных методах решение системы получают за конечное число арифметических действий. К ним относятся известное правило Крамера нахождения решения с помощью определителей, метод последовательного исключения неизвестных (метод Гаусса) и его модификации, метод прогонки и другие. Сопоставление различных прямых методов проводится обычно по числу арифметических действий, необходимых для получения решения.

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

Итерационные или приближенные методы являются бесконечными и находят решение системы как предел при k последовательных приближений x ^(k), где k - номер итерации. Число итераций n, которое необходимо провести для получения заданной точности, для многих методов можно найти из теоретических рассмотрений [2].

Метод оптимального исключения.

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

.

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

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

2. Итерационный метод Якоби решения систем линейных алгебраических уравнений

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