Прекондиционер - Preconditioner

«Предварительная подготовка» перенаправляется сюда. Для использования в других целях см. Предварительная подготовка (значения).

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

Предварительная подготовка для линейных систем

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

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

Описание

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

${displaystyle AP^{-1}Px=b}$

через решение

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

за ${displaystyle y}$ и

${displaystyle Px=y}$

за ${displaystyle x}$.

В качестве альтернативы можно решить левую предварительно подготовленную систему:

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

Обе системы дают то же решение, что и исходная система, пока матрица предобуславливателя ${displaystyle P}$ является неособый. Левое предварительное кондиционирование встречается чаще.

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

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

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

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

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

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

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

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

Линейное предварительное кондиционирование

Пусть линейный итерационный метод дается расщеплением матрицы ${displaystyle A=M-N}$, и матрица итераций ${displaystyle C=I-M^{-1}A}$.

Предположим следующее

• матрица системы ${displaystyle A}$ является симметричный положительно определенный
• матрица расщепления ${displaystyle M}$ является симметричный положительно определенный
• линейный итерационный метод сходится: ${displaystyle ho (C)<1}$.

Тогда уменьшение системного номер условия ${displaystyle kappa (M^{-1}A)}$ можно ограничить сверху

${displaystyle kappa (M^{-1}A)leq {frac {1+ho (C)}{1-ho (C)}},.}$

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

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

Переменное и нелинейное предварительное кондиционирование

Обозначение ${displaystyle T=P^{-1}}$, подчеркнем, что предварительное кондиционирование практически реализовано как умножение некоторого вектора ${displaystyle r}$ к ${displaystyle T}$, т.е. вычисление продукта ${displaystyle Tr.}$ Во многих приложениях ${displaystyle T}$ дается не как матрица, а как оператор ${displaystyle T(r)}$ действуя на вектор ${displaystyle r}$. Однако некоторые популярные прекондиционеры меняются с ${displaystyle r}$ и зависимость от ${displaystyle r}$ не может быть линейным. Типичные примеры включают использование нелинейных итерационные методы, например, метод сопряженных градиентов, как часть конструкции прекондиционера. Такие предварительные кондиционеры могут быть практически очень эффективными, однако их поведение трудно предсказать теоретически.

Спектрально эквивалентное предварительное кондиционирование

Чаще всего предварительное кондиционирование используется для итеративного решения линейных систем в результате приближений уравнения в частных производных. Чем лучше качество аппроксимации, тем больше размер матрицы. В таком случае цель оптимального предварительного кондиционирования, с одной стороны, состоит в том, чтобы сделать спектральное число обусловленности ${displaystyle P^{-1}A}$ быть ограниченным сверху константой, не зависящей от размера матрицы, которая называется спектрально эквивалентный предварительное кондиционирование Дьяконов. С другой стороны, стоимость применения ${displaystyle P^{-1}}$ в идеале должно быть пропорционально (также независимо от размера матрицы) стоимости умножения ${displaystyle A}$ вектором.

Примеры

Предобуславливатель Якоби (или диагональный)

В Прекондиционер Якоби - одна из простейших форм предобусловливания, в которой предобуславливателем выбирается диагональ матрицы ${displaystyle P=mathrm {diag} (A).}$ Предполагая ${displaystyle A_{ii}eq 0,forall i}$, мы получили ${displaystyle P_{ij}^{-1}={frac {delta _{ij}}{A_{ij}}}.}$ Это эффективно для матрицы с диагональным преобладанием ${displaystyle A}$.

ИСПАНИЯ

В Редкое приближенное обратное предварительный кондиционер минимизирует ${displaystyle |AT-I|_{F},}$ куда ${displaystyle |cdot |_{F}}$ это Норма Фробениуса и ${displaystyle T=P^{-1}}$ из некоторого подходящего ограниченного набора разреженные матрицы. В соответствии с нормой Фробениуса это сводится к решению множества независимых задач наименьших квадратов (по одной для каждого столбца). Записи в ${displaystyle T}$ должны быть ограничены некоторым шаблоном разреженности, иначе проблема останется такой же сложной и трудоемкой, как нахождение точного обратного ${displaystyle A}$. Этот метод был предложен M.J. Grote и T. Huckle вместе с подходом к выбору моделей разреженности.^[2]

Другие прекондиционеры

• Неполная факторизация Холецкого
• Неполная факторизация LU
• Последовательное чрезмерное расслабление
  • Симметричное последовательное чрезмерное расслабление
• Предварительная подготовка многосеточных сетей

внешняя ссылка

• Предварительно обусловленный сопряженный градиент - math-linux.com
• Шаблоны для решения линейных систем: строительные блоки для итерационных методов

Предварительная подготовка для задач на собственные значения

Задачи на собственные значения могут быть сформулированы несколькими альтернативными способами, каждый из которых приводит к собственной предварительной обработке. Традиционное предварительное кондиционирование основано на так называемом спектральные преобразования. Зная (приблизительно) целевое собственное значение, можно вычислить соответствующий собственный вектор, решив связанную однородную линейную систему, что позволяет использовать предварительное кондиционирование для линейной системы. Наконец, формулируя проблему собственных значений как оптимизацию Фактор Рэлея приносит на сцену заранее подготовленные методы оптимизации.^[3]

Спектральные преобразования

По аналогии с линейными системами для собственное значение проблема ${displaystyle Ax=lambda x}$ может возникнуть соблазн заменить матрицу ${displaystyle A}$ с матрицей ${displaystyle P^{-1}A}$ с использованием прекондиционера ${displaystyle P}$. Однако это имеет смысл, только если ищущий собственные векторы из ${displaystyle A}$ и ${displaystyle P^{-1}A}$ одинаковые. Это случай спектральных преобразований.

Наиболее популярным спектральным преобразованием является так называемое сдвиг-и-инвертировать преобразование, где для данного скаляра ${displaystyle alpha }$, называется сдвиг, исходная задача на собственные значения ${displaystyle Ax=lambda x}$ заменяется задачей сдвига и инвертирования ${displaystyle (A-alpha I)^{-1}x=mu x}$. Собственные векторы сохраняются, и можно решить проблему сдвига и инвертирования с помощью итеративного решателя, например, итерация мощности. Это дает Обратная итерация, который обычно сходится к собственному вектору, соответствующему собственному значению, ближайшему к сдвигу ${displaystyle alpha }$. В Итерация фактора Рэлея это метод сдвига и инвертирования с переменным сдвигом.

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

Общая предварительная подготовка

Чтобы установить тесную связь с линейными системами, предположим, что целевое собственное значение ${displaystyle lambda _{star }}$ известно (приблизительно). Тогда можно вычислить соответствующий собственный вектор из однородной линейной системы ${displaystyle (A-lambda _{star }I)x=0}$. Используя понятие левого предобуславливания линейных систем, получаем ${displaystyle T(A-lambda _{star }I)x=0}$, куда ${displaystyle T}$ является предобуславливателем, который мы можем попытаться решить с помощью Итерация Ричардсона

${displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-gamma _{n}T(A-lambda _{star }I))mathbf {x} _{n}, ngeq 0.}$

В идеальный предварительная подготовка^[3]

В Псевдообратная матрица Мура – ​​Пенроуза ${displaystyle T=(A-lambda _{star }I)^{+}}$ является предобуславливателем, который делает Итерация Ричардсона выше сходятся за один шаг с ${displaystyle gamma _{n}=1}$, поскольку ${displaystyle I-(A-lambda _{star }I)^{+}(A-lambda _{star }I)}$, обозначаемый ${displaystyle P_{star }}$, - ортогональный проектор на собственное подпространство, соответствующий ${displaystyle lambda _{star }}$. Выбор ${displaystyle T=(A-lambda _{star }I)^{+}}$ нецелесообразно по трем независимым причинам. Первый, ${displaystyle lambda _{star }}$ на самом деле неизвестно, хотя его можно заменить его приближением ${displaystyle { ilde {lambda }}_{star }}$. Во-вторых, точный Псевдообратная матрица Мура – ​​Пенроуза требует знания собственного вектора, который мы пытаемся найти. Это можно в некоторой степени обойти, используя Предобуславливатель Якоби-Дэвидсона ${displaystyle T=(I-{ ilde {P}}_{star })(A-{ ilde {lambda }}_{star }I)^{-1}(I-{ ilde {P}}_{star })}$, куда ${displaystyle { ilde {P}}_{star }}$ приблизительно ${displaystyle P_{star }}$. Наконец, что не менее важно, этот подход требует точного численного решения линейной системы с системной матрицей ${displaystyle (A-{ ilde {lambda }}_{star }I)}$, который становится таким же дорогостоящим для больших проблем, как описанный выше метод сдвига и инвертирования. Если решение недостаточно точное, второй шаг может быть излишним.

Практическое предварительное кондиционирование

Сначала заменим теоретическое значение ${displaystyle lambda _{star }}$ в Итерация Ричардсона выше с его текущим приближением ${displaystyle lambda _{n}}$ получить практический алгоритм

${displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-gamma _{n}T(A-lambda _{n}I)mathbf {x} _{n}, ngeq 0.}$

Популярный выбор - ${displaystyle lambda _{n}=ho (x_{n})}$ с использованием Фактор Рэлея функция ${displaystyle ho (cdot )}$. Практическая предварительная подготовка может быть такой же тривиальной, как простое использование ${displaystyle T=(diag(A))^{-1}}$ или же ${displaystyle T=(diag(A-lambda _{n}I))^{-1}.}$ Для некоторых классов задач на собственные значения эффективность ${displaystyle Tapprox A^{-1}}$ было продемонстрировано как численно, так и теоретически. Выбор ${displaystyle Tapprox A^{-1}}$ позволяет легко использовать для задач на собственные значения огромное количество предобуславливателей, разработанных для линейных систем.

Из-за меняющегося значения ${displaystyle lambda _{n}}$, комплексный теоретический анализ сходимости намного сложнее, чем в случае линейных систем, даже для простейших методов, таких как Итерация Ричардсона.

внешняя ссылка

• Шаблоны для решения алгебраических задач на собственные значения: Практическое руководство

Предварительная подготовка в оптимизации

Иллюстрация градиентного спуска

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

Описание

Например, чтобы найти местный минимум действительной функции ${displaystyle F(mathbf {x} )}$ с помощью градиентный спуск, предпринимаются шаги, пропорциональные отрицательный из градиент ${displaystyle -abla F(mathbf {a} )}$ (или приблизительного градиента) функции в текущей точке:

${displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-gamma _{n}abla F(mathbf {x} _{n}), ngeq 0.}$

К градиенту применяется предварительный кондиционер:

${displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-gamma _{n}P^{-1}abla F(mathbf {x} _{n}), ngeq 0.}$

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

Подключение к линейным системам

Минимум квадратичной функции

${displaystyle F(mathbf {x} )={frac {1}{2}}mathbf {x} ^{T}Amathbf {x} -mathbf {x} ^{T}mathbf {b} }$,

куда ${displaystyle mathbf {x} }$ и ${displaystyle mathbf {b} }$ являются действительными векторами-столбцами и ${displaystyle A}$ настоящий симметричный положительно определенная матрица, является в точности решением линейного уравнения ${displaystyle Amathbf {x} =mathbf {b} }$. С ${displaystyle abla F(mathbf {x} )=Amathbf {x} -mathbf {b} }$, предварительно подготовленные градиентный спуск метод минимизации ${displaystyle F(mathbf {x} )}$ является

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

Это предварительная Итерация Ричардсона для решения система линейных уравнений.

Связь с проблемами собственных значений

Минимум Фактор Рэлея

${displaystyle ho (mathbf {x} )={frac {mathbf {x} ^{T}Amathbf {x} }{mathbf {x} ^{T}mathbf {x} }},}$

куда ${displaystyle mathbf {x} }$ является вещественным ненулевым вектор-столбцом и ${displaystyle A}$ настоящий симметричный положительно определенная матрица, самый маленький собственное значение из ${displaystyle A}$, а минимизатор - соответствующий собственный вектор. С ${displaystyle abla ho (mathbf {x} )}$ пропорционально ${displaystyle Amathbf {x} -ho (mathbf {x} )mathbf {x} }$, предварительно подготовленные градиентный спуск метод минимизации ${displaystyle ho (mathbf {x} )}$ является

${displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-gamma _{n}P^{-1}(Amathbf {x} _{n}-ho (mathbf {x_{n}} )mathbf {x_{n}} ), ngeq 0.}$

Это аналог предобусловленного Итерация Ричардсона для решения задач на собственные значения.

Предварительная подготовка переменных

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

${displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-gamma _{n}P_{n}^{-1}abla F(mathbf {x} _{n}), ngeq 0.}$

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

Рекомендации

1. Шевчук, Джонатан Ричард (4 августа 1994 г.). «Введение в метод сопряженных градиентов без мучительной боли» (PDF).
2. Гроте, М. Дж. И Хакл, Т. (1997). «Параллельная предварительная подготовка с разреженными приближенными инверсиями». Журнал SIAM по научным вычислениям. 18 (3): 838–53. Дои:10.1137 / S1064827594276552.
3. Князев, Андрей В. (1998). «Прекондиционированные собственные средства - оксюморон?». Электронные транзакции по численному анализу. 7: 104–123.
4. Химмельблау, Дэвид М. (1972). Прикладное нелинейное программирование. Нью-Йорк: Макгроу-Хилл. С. 78–83. ISBN  0-07-028921-2.

Источники

• Аксельссон, Долж (1996). Итерационные методы решения. Издательство Кембриджского университета. п. 6722. ISBN  978-0-521-55569-2.
• Дьяконов, Э. Г. (1996). Оптимизация при решении эллиптических задач. CRC-Press. п. 592. ISBN  978-0-8493-2872-5.
• Саад, Юсеф & ван дер Ворст, Хенк (2001). «Итерационное решение линейных систем в ХХ веке». В Brezinski, C. & Wuytack, L. (ред.). Численный анализ: исторические события ХХ века. Издательство Elsevier Science. §8 Методы прекондиционирования, стр. 193–8. ISBN  0-444-50617-9.
• ван дер Ворст, Х.А. (2003). Итерационные методы Крылова для больших линейных систем.. Издательство Кембриджского университета, Кембридж. ISBN  0-521-81828-1.