Предобуславливание

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи[уточнить]. Предобуславливаемая задача обычно затем решается итерационным методом.

Предобуславливание для систем линейных алгебраических уравнений[править | править вики-текст]

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

Предобуславливание используется в итерационных методах при решении систем линейных алгебраических уравнений вида , так как скорость сходимости для большинства итерационных линейных решателей увеличивается с уменьшением числа обусловленности в результате предобуславливания. Решатели с предобуславливанием обычно эффективнее, чем использование простых решателей, например, таких как метод Гаусса в случае больших и особенно в случае разреженных матриц. Итерационные решатели с предобуславливанием могут использовать безматричные методы, в которых матрица коэффициентов не хранится отдельно, а доступ к её элементам происходит через произведения матриц-векторов.

Определение[править | править вики-текст]

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

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

Использование это всегда компромисс. Так как оператор применяется на каждом шаге итерационного линейного решателя, операция должна быть легко вычисляемой (по времени вычисления). Наиболее быстрым предобуславливателем в этом случае будет , так как . Очевидно, что в результате работы такого предобуславливателя получается исходная система. Другая крайность — выбор , что даст , при этом будет получено оптимальное число обусловленности 1, требующее одной итерации для того, чтобы решение сошлось. Тем не менее в этом случае и сложность вычисления предобуславливателя сравнима со сложностью решения исходной системы. Поэтому необходимо выбирать где-то между двумя этими крайними случаями, пытаясь получить минимальное число итераций сохраняя легкость вычисления . Некоторые примеры основных подходов предобуславливания описаны ниже.

Итерационные методы с предобуславливанием[править | править вики-текст]

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

В случае предобусловленной системы , предобусловленный метод будет выглядеть как

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

Геометрическая интерпретация[править | править вики-текст]

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