Решение системы линейных уравнений (стр. 2 из 3)

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 :

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

Если A - матрица с доминирующей диагональю, т.е.

, то метод Якоби сходится при любом начальном приближении x⁽⁰⁾.

Метод Якоби относится к одношаговым итерационным методам, когда для нахождения x⁽^k⁺¹⁾ требуется помнить только одну предыдущую итерацию x⁽^k⁾. Для исследования сходимости удобнее записывать итерационные методы не в координатной, а в матричной форме, придерживаясь стандартной формы записи итерационных методов.

Канонической формой одношагового итерационного метода решения СЛАУ называется его запись в виде

где B_k+1 - матрица, задающая тот или иной итерационный метод, t_k+1 - итерационный параметр. Числовые параметры t_kвводят для ускорения сходимости. Способ выбора итерационных параметров определяется при исследовании сходимости метода, когда выясняется при каких значениях параметров метод сходится и когда сходимость будет наиболее быстрой (соответствующие параметры называются оптимальными).

Итерационный метод называют явным, если B_k+1 - единичная матрица. Неявные итерационные методы имеет смысл применять лишь в том случае, когда решение системы уравнений с матрицей B_k требует меньше машинной памяти или времени или алгоритмически проще, чем решение исходной системы.

Методом простой итерации называют явный метод с постоянм параметром

, или
,

где r⁽^k⁾= Ax⁽^k⁾-b - вектор невязки. Метод сходится для симметричных положительно определенных матриц при

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

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

При втором способе вычисляют нормы невязки до начала итераций и на каждой итерации. Итерации прекращают при выполнении неравенства

При третьем способе предварительно оценивается число итераций, необходимое для получения заданной точности e. Если для погрешности итерационного метода выполняются оценки

где q (0,1), то метод сходится со скоростью геометрической прогрессии со знаменателем q. Можно определить, потребовав, чтобы qⁿ < e, число итераций n, достаточное для того, чтобы начальная погрешность уменьшилась в заданное число раз:

Целая часть числа n₀(e) является минимальным числом итераций, необходимым для получения заданной точности e.

Величина ln(1/q) является скоростью сходимости итерационного метода.

2. Описание используемого метода

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

или

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

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

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

Если A - матрица с доминирующей диагональю, т.е.

, то метод Зейделя сходится при любом начальном приближении x⁽⁰⁾.

Метод Зейделя сходится примерно так же, как геометрическая прогрессия со знаменателем ||G|| . Если норма матрицы G близка к 1, то скорость сходимости очень медленная. Для ускорения сходимости используется метод релаксации. Суть его в том, что полученное по методу Зейделя очередное значение пересчитывается по формуле:

Здесь 0<w£2 – параметр релаксации. Если w<1 - нижняя релаксация, если w>1 – верхняя релаксация. Параметр w подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.

Метод Зейделя является одношаговым итерационным методам, когда для нахождения x⁽^k⁺¹⁾ требуется помнить только одну предыдущую итерацию x⁽^k⁾.

Погрешность итерации вычисляется по формуле:

n - порядок матрицы A.

Если d меньше заданной точности e, то итерационный процесс прекращают.

Элементы главной диагонали называются главными. Заметим, что если в ходе расчётов по данному алгоритму на главной диагонали окажется нулевой элемент, то произойдет сбой программы. Для того, чтобы избежать этого, следует перестановку строк таким образом, чтобы на главной диагонали находились максимальные элементы строк. Т. е., если в k-й строке максимальным является i-й элемент, необходимо поменять местами k-ю и i-ю строки, и поменять местами соответствующие элементы вектора b. Такой выбор главного элемента необходим для сходимости итерационного процесса.