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

Если A - матрица с доминирующей диагональю, т.е. , то метод Якоби сходится при любом начальном приближении x ^{(0 )} .

Метод Якоби относится к одношаговым итерационным методам , когда для нахождения x ^{( k +1)} требуется помнить только одну предыдущую итерацию 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 были по абсолютной величине меньше единицы. На практике это трудно проверить, и обычно пользуются достаточными условиями сходимости - итерации сходятся, если какая-нибудь норма матрицы меньше единицы, т.е.

или .

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

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

.

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