Итерационные методы

УМЕНЬШЕНИЕ ОШИБОК ОКРУГЛЕНИЯ

Поменяем местами в системе (Пример 37.7.) второе и третье уравнения. Полученную систему решим методом Гаусса. В результате после исключения из третьего уравнения x2 получим систему треугольного вида

1,2357x1 + 2,1742x2 - 5,4834x3 = - 2,0735,

0,0007x2 + 10,727x3 = 10,727,

258 930x3 = 258 910.

Определяя из нее последовательно x3, x2, x1, найдем решение

x1 = 2,9021, x2 = 1,4286, x3 = 0,9992.

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

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

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

Рассмотрим итерационные методы решения систем линейных уравнений. Вообще говоря, эти методы не дают возможности найти точное решение за конечное число итераций даже при отсутствии ошибок округления. Суть метода состоит в построении векторной последовательности {Xk }, такой, что

где X - точное решение.

Указанные методы широко применяются при численном решении дифференциальных уравнений с частными производными. Матрицы их дискретных аналогов имеют большое число нулевых элементов. Итерационные методы в отличие от прямых методов сохраняют структуру исходной матрицы (не увеличивают число ненулевых элементов). Эффективность итерационных методов определяется скоростью сходимости последовательных приближений Xk к решению X.

Первым шагом в итерационном методе является преобразование исходной системы (Пример 37.4.) к виду

Пример 37.10.

A1X = A2X + B1.

Здесь матрицы A1, A2 и вектор B1 определяются по матрице A и вектору B. Системы (Пример 37.4.) и (Пример 37.10.) эквивалентные, то есть их решения совпадают.

Вторым шагом является расстановка индексов или номеров приближений в формуле (Пример 37.10.) и задание нулевого приближения. Например,

Пример 37.11.

A1Xk + 1 = A2Xk + B1, k = 0, 1, 2, _,

где X0 - заданный вектор (нулевое приближение).

Третьим шагом итерационного метода является обоснование сходимости последовательных приближений {Xk } (Пример 37.11.) к точному решению X системы (Пример 37.4.) и оценка погрешности k-го приближения

Пример 37.12.

|| Xk - X || # e.

Оценка такого типа при заданном e (точность решения) позволяет закончить итерационный процесс (Пример 37.11.).

Здесь также предполагается, что система (Пример 37.11.) решается относительно Xk + 1 гораздо легче, чем исходная система (Пример 37.4.) относительно X.

Разные итерационные методы различаются первыми двумя шагами, а выбор конкретного метода производится на основании оценки (Пример 37.12.).

Дата добавления: 2014-01-04