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

Transforms equations for numerical solution

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

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

В линейной алгебре и численном анализе предобуславливателем матрицы является матрица, имеющая меньшее число обусловленности , чем . Также принято называть предобуславливателем , а не , поскольку само по себе редко доступно явно. В современной предварительной обработке применение , т. е. умножение вектора - столбца или блока векторов-столбцов на , обычно выполняется безматричным способом , т. е. когда ни , ни (а часто даже и ) явно не доступны в матричной форме. ${\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 Ax=b}$ ${\displaystyle x}$ $${\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 QAP^{-1}(Px)=Qb}$$ ${\displaystyle A}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle Q^{T}=P^{-1}}$ ${\displaystyle QAP^{-1}}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle A}$

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

Предварительно обусловленная матрица или редко формируется явно. Может потребоваться вычислить только действие применения операции preconditioner resolve к заданному вектору. ${\displaystyle P^{-1}A}$ ${\displaystyle AP^{-1}}$ ${\displaystyle P^{-1}}$

Обычно существует компромисс при выборе . Поскольку оператор должен применяться на каждом шаге итеративного линейного решателя, он должен иметь небольшую стоимость (время вычислений) применения операции . Поэтому самым дешевым предобуславливателем будет , поскольку тогда Очевидно, что это приводит к исходной линейной системе, а предобуславливатель ничего не делает. С другой стороны, выбор дает , который имеет оптимальное число условий 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,}$ ${\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}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

Применительно к предварительно обусловленной системе он превращается в предварительно обусловленный метод. ${\displaystyle P^{-1}(Ax-b)=0,}$ $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 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 \rho (C)<1}$

число условий ограничено сверху ${\displaystyle \kappa (M^{-1}A)}$ $${\displaystyle \kappa (M^{-1}A)\leq {\frac {1+\rho (C)}{1-\rho (C)}}\,.}$$

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

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

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

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

Случайная предварительная подготовка

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

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

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

Примеры

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

Предварительный обуславливатель Якоби является одной из простейших форм предварительной обработки, в которой предварительный обуславливатель выбирается как диагональ матрицы Предполагая , мы получаем Он эффективен для диагонально доминирующих матриц . Он используется в программном обеспечении для анализа балочных задач или одномерных задач (НАПРИМЕР:- STAAD.Pro ) ${\displaystyle P=\mathrm {diag} (A).}$ ${\displaystyle A_{ii}\neq 0,\forall i}$ ${\displaystyle P_{ij}^{-1}={\frac {\delta _{ij}}{A_{ij}}}.}$ ${\displaystyle A}$

ИСПАЙ

Предварительный обуславливатель Sparse Approximate Inverse минимизирует , где — норма Фробениуса , а — из некоторого подходящим образом ограниченного набора разреженных матриц . При норме Фробениуса это сводится к решению многочисленных независимых задач наименьших квадратов (по одной для каждого столбца). Элементы в должны быть ограничены некоторым шаблоном разреженности, иначе задача останется такой же сложной и трудоемкой, как поиск точного обратного . Метод был введен М. Дж. Гротом и Т. Хаклом вместе с подходом к выбору шаблонов разреженности. ^[3] ${\displaystyle \|AT-I\|_{F},}$ ${\displaystyle \|\cdot \|_{F}}$ ${\displaystyle T=P^{-1}}$ ${\displaystyle T}$ ${\displaystyle A}$

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

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

Внешние ссылки

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

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

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

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

По аналогии с линейными системами, для задачи на собственные значения может возникнуть соблазн заменить матрицу на матрицу с использованием предобуславливателя . Однако это имеет смысл только в том случае, если искомые собственные векторы и одинаковы . Это касается спектральных преобразований. ${\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},\ n\geq 0.}$$

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

Псевдообратная матрица Мура –Пенроуза является предобуславливателем, который заставляет итерацию Ричардсона выше сходиться за один шаг с , поскольку , обозначенный как , является ортогональным проектором на собственное пространство, соответствующим . Выбор нецелесообразен по трем независимым причинам. Во-первых, на самом деле неизвестно, хотя его можно заменить его приближением . Во-вторых, точная псевдообратная матрица Мура–Пенроуза требует знания собственного вектора, который мы пытаемся найти. Это можно несколько обойти, используя предобуславливатель Якоби–Дэвидсона , где приближает . Наконец, но не в последнюю очередь, этот подход требует точного численного решения линейной системы с системной матрицей , что становится таким же дорогим для больших задач, как и метод сдвига и инвертирования выше. Если решение недостаточно точное, шаг два может быть излишним. ${\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 {\tilde {\lambda }}_{\star }}$ ${\displaystyle T=(I-{\tilde {P}}_{\star })(A-{\tilde {\lambda }}_{\star }I)^{-1}(I-{\tilde {P}}_{\star })}$ ${\displaystyle {\tilde {P}}_{\star }}$ ${\displaystyle P_{\star }}$ ${\displaystyle (A-{\tilde {\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},\ n\geq 0.}$$

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

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

Внешние ссылки

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

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

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

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

Описание

Например, чтобы найти локальный минимум действительной функции с помощью градиентного спуска , нужно выполнить шаги, пропорциональные отрицательному значению градиента ( или приближенного градиента) функции в текущей точке: ${\displaystyle F(\mathbf {x} )}$ ${\displaystyle -\nabla F(\mathbf {a} )}$ $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

К градиенту применяется предварительный обуславливатель: $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

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

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

Минимум квадратичной функции , где и являются действительными векторами-столбцами, а является действительной симметричной положительно определенной матрицей , является в точности решением линейного уравнения . Поскольку , предобусловленный метод градиентного спуска минимизации имеет вид $${\displaystyle F(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{T}A\mathbf {x} -\mathbf {x} ^{T}\mathbf {b} ,}$$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {b} }$ ${\displaystyle A}$ ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle \nabla F(\mathbf {x} )=A\mathbf {x} -\mathbf {b} }$ ${\displaystyle F(\mathbf {x} )}$ $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

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

Связь с задачами на собственные значения

Минимум отношения Рэлея , где — действительный ненулевой вектор-столбец, а — действительная симметричная положительно определенная матрица , — наименьшее собственное значение , тогда как минимизатор — соответствующий собственный вектор . Поскольку пропорционально , ​​предобусловленный метод градиентного спуска минимизации — это $${\displaystyle \rho (\mathbf {x} )={\frac {\mathbf {x} ^{T}A\mathbf {x} }{\mathbf {x} ^{T}\mathbf {x} }},}$$ ${\displaystyle \mathbf {x} }$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \nabla \rho (\mathbf {x} )}$ ${\displaystyle A\mathbf {x} -\rho (\mathbf {x} )\mathbf {x} }$ ${\displaystyle \rho (\mathbf {x} )}$ $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\rho (\mathbf {x_{n}} )\mathbf {x_{n}} ),\ n\geq 0.}$$

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

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

Во многих случаях может быть полезно изменить предобуславливатель на каком-то или даже на каждом шаге итеративного алгоритма , чтобы приспособиться к изменяющейся форме множеств уровня, как в $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P_{n}^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

Однако следует иметь в виду, что построение эффективного предобуславливателя очень часто является вычислительно затратным. Увеличение стоимости обновления предобуславливателя может легко перекрыть положительный эффект более быстрой сходимости. Если , BFGS -приближение обратной матрицы Гессе, этот метод называется квазиньютоновским методом . ${\displaystyle P_{n}^{-1}=H_{n}}$

Ссылки

1. Шевчук, Джонатан Ричард (4 августа 1994 г.). «Введение в метод сопряженных градиентов без мучительной боли» (PDF) .
2. Хенрикус Боумистер, Эндрю Догерти, Эндрю В. Князев. Несимметричное предварительное обусловливание для методов сопряженного градиента и наискорейшего спуска. Procedia Computer Science, том 51, страницы 276-285, Elsevier, 2015. https://doi.org/10.1016/j.procs.2015.05.241
3. Гроте, М. Дж. и Хакл, Т. (1997). «Параллельная предобуславливание с разреженными приближенными обратными». Журнал SIAM по научным вычислениям . 18 (3): 838–53. doi :10.1137/S1064827594276552.
4. Князев, Эндрю В. (1998). «Предобусловленные собственные решатели — оксюморон?». Electronic Transactions on Numerical Analysis . 7 : 104–123.
5. Химмельблау, Дэвид М. (1972). Прикладное нелинейное программирование . Нью-Йорк: МакГроу-Хилл. стр. 78–83. ISBN 0-07-028921-2.

Источники

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