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

07.12.2021

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

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

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

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

Определение

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

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

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

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

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

x n + 1 = x n − γ n ( A x n − b ) ,   n ≥ 0. {displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-gamma _{n}(Amathbf {x} _{n}-mathbf {b} ), ngeq 0.}

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

x n + 1 = x n − γ n P − 1 ( A x n − b ) ,   n ≥ 0. {displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-gamma _{n}P^{-1}(Amathbf {x} _{n}-mathbf {b} ), ngeq 0.}

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

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

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



Имя:*
E-Mail:
Комментарий: