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

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

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

Предобуславливание СЛАУ[править | править вики-текст]

В линейной алгебре и вычислительной математике \,\! 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 и при этом сохранить сферическую форму скалярного произведения с  P.