Контроль точности и уточнение приближенного решения в рамках прямого метода

Как отмечалось во введении, прямые методы приводят к точному решению СЛАУ при точном выполнении предусматриваемых соответствующими алгоритмами арифметических операций (без округлений). Реальные же вычисления базируются на арифметики машинных (т.е. усеченных до определенного количества разрядов) чисел. Как отражается на результате решения системы подмена арифметики действительных чисел машинной арифметикой, зависит от самой решаемой системы, параметров применяемого компьютера, системы представления данных, способов реализации алгоритмов. В любом случае, практически вместо точного решения СЛАУ (1.1) прямой метод дает приближенное решение x ₀. Метод Гаусса порождает относительную ошибку решения порядка N ×2^–l×сond A, где l–число двоичных разрядов, выделяемых компьютером под мантиссу вещественного числа, а cond A число обусловленности cond A =|| A ||×|| A ^–1||»|l _max |/|l _min |. Подставив x ₀ в выражение невязки, по малости полученного вектора-значения r ₀= b – Ax ₀ можно с осторожностью судить о близости найденного решения x ₀ к точному решению x_*. Если, например, || r ₀||₂–недостаточно малая величина, то следует искать вектор-поправку p такой, что x ₀+ p = x_* есть точное решение системы (1.1), т.е.

A(x₀+p)=b.

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

Ap=r₀.

Как видно, нахождение поправки сводится к решению такой же системы, как и (1.1), где в качестве вектора свободных членов должен быть взят вектор невязок. Поскольку матрица коэффициентов осталась той же, что и у исходной системы, нет надобности в выполнении прямого хода преобразований коэффициентов при неизвестных (иначе, LU-разложения); достаточно выполнить только, действия, касающиеся новых свободных членов (решить две треугольные системы: Lz = r ₀и Up = z). Прибавив найденную поправку p = p ₀ к x ₀, получаем уточненное приближенное решение x ₁= x ₀+ p ₀.В случае, если величина || p ₀||₂(или || p ₀||₂/|| x ₁||₂, если контролируется относительная, а не абсолютная погрешность) окажется недостаточно малой, процесс уточнения может быть повторен: ищется поправка p ₁ как приближенное решение уравнения Ap = r ₁, где r ₁= b–Ax ₁; тогда более точным должно быть решение x ₂= x ₁+ p ₁. Cходимость к нулю невязок в таком процессе уточнения решения может не наблюдаться, т.е. следить нужно за установлением знаков самого решения. Обычно делают не более двух-трех шагов уточнения, причем рекомендуется производить вычисление невязок в режиме накопления. Если в этом процессе не происходит сближения x _k при k =2, 3, то это говорит, скорее всего, о том, что данная система плохо обусловлена и ее решение не может быть найдено с требуемой точностью без привлечения дополнительной информации об исходной задаче. В таких случаях закономерно ставить вопрос о том, что понимать под точным решением системы и, возможно, обращаться к методам нахождения ее.

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

Дата добавления: 2014-12-27