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

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

Предобуславливание для систем линейных алгебраических уравнений

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

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

Определение

Вместо решения исходной системы линейных алгебраических уравнений можно решать предобусловленную систему $A{P}^{-1}Px=b$, которую можно решить через форму $A{P}^{-1}y=b$, где $y$ удовлетворяет условию $Px=y$, или решить предобусловленную слева систему: $P^{-1}(Ax-b)=0$.

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

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

Итерационные методы с предобуславливанием

Итерационные методы с предобуславливанием для $Ax-b=0$ в большинстве случаев математически эквивалентны стандартным итерационным методам, выполняемым над предобусловленной системой $P^{-1}(Ax-b)=0$. Например, стандартный метод итераций Ричардсона для решения $Ax-b=0$ будет выглядеть как

${𝐱}_{n+1}={𝐱}_n-{\gamma }_n(A{𝐱}_n-𝐛),n\ge 0.$

В случае предобусловленной системы $P^{-1}(Ax-b)=0$, предобусловленный метод будет выглядеть как

${𝐱}_{n+1}={𝐱}_n-{\gamma }_n{P}^{-1}(A{𝐱}_n-𝐛),n\ge 0.$

Примерами наиболее популярных итерационных методов с предобуславливанием для линейных систем являются метод сопряженных градиентов с предобуславливанием, метод бисопряженных градиентов и метод обобщенных минимальных невязок. В итерационных методах, которые вычисляют итерационные параметры через скалярные произведения, требуются соответствующие изменения в скалярном произведении вместе с заменой $P^{-1}(Ax-b)=0$ на $Ax-b=0.$

Геометрическая интерпретация

Для симметричной положительно определённой матрицы $A$ предобуславливатель $P$ обычно выбирается также симметричный и положительно определённый. После этого оператор предобуславливания $P^{-1}A$ также симметричный и положительно определённый. В этом случае желаемый эффект в применении предобуславливателя это придать квадратную форму оператору предобуславливания $P^{-1}A$ и при этом сохранить сферическую форму скалярного произведения с $P$.