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

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

Предобуславливание СЛАУ

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

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

Определение

Вместо решения исходной СЛАУ, описанной выше, можно решать предобусловленную систему:

$AP^{-1}Px = b$

которую можно решить через

$AP^{-1}y=b$,

где $y$ удовлетворяет

$Px=y$

или решить предобусловленную слева систему:

$P^{-1}(Ax-b)=0$

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

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

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

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

$\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n (A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.$

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

$\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P^{-1}(A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.$

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

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

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