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

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

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

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

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

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

Описание

Вместо решения исходной линейной системы $Ax=b$ для $x$, можно рассмотреть правильную предобусловленную систему $$AP^{-1}(Px)=b$$ и решить $$AP^{-1}y=b$$ для $y$ и $$Px=y$$ для $x$.

Альтернативно можно решить левую предобусловленную систему $$P^{-1}(Ax-b)=0.$$

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

Двусторонняя система предварительной подготовки $$QAP^{-1}(Px)=Qb$$ может быть полезно, например, для сохранения симметрии матрицы: если исходная матрица $A$ действительно симметричны и действительные предобуславливатели $Q$ и $P$ удовлетворить $Q^{T}=P^{-1}$ тогда предварительно обусловленная матрица $QAP^{-1}$ также симметричен. Двусторонняя предобусловливание обычно используется для диагонального масштабирования , где предобуславливатели $Q$ и $P$ являются диагональными, и масштабирование применяется как к столбцам, так и к строкам исходной матрицы. $A$, например, для уменьшения динамического диапазона элементов матрицы.

Целью предварительной обработки является уменьшение числа обусловленности , например, левой или правой предварительно подготовленной системной матрицы. $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\geq 0.$$

Применяется к предварительно подготовленной системе $P^{-1}(Ax-b)=0,$ это превращается в заранее обусловленный метод $$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.$$

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

Расщепление матрицы

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

• системная матрица $A$ является симметричным положительно определенным ,
• матрица расщепления $M$ является симметричным положительно определенным ,
• стационарный итерационный метод сходится, что определяется соотношением $\rho (C)<1$,

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

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

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

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

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

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

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

Спектрально эквивалентная предобуславливание

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

Примеры

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

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

СПАИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сначала заменим теоретическое значение $\lambda _{\star }$ в итерации Ричардсона выше с ее текущим приближением $\lambda _{n}$ получить практический алгоритм $$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}T(A-\lambda _{n}I)\mathbf {x} _{n},\ n\geq 0.$$

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

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

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

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

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

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

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

Описание

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

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

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

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

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

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

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

Минимум коэффициента Рэлея $$\rho (\mathbf {x} )={\frac {\mathbf {x} ^{T}A\mathbf {x} }{\mathbf {x} ^{T}\mathbf {x} }},$$ где $\mathbf {x}$ является действительным ненулевым вектором-столбцом и $A$ — действительная симметричная положительно определенная матрица , — наименьшее собственное значение $A$, а минимизатор — соответствующий собственный вектор . С $\nabla \rho (\mathbf {x} )$ пропорционально $A\mathbf {x} -\rho (\mathbf {x} )\mathbf {x}$, предварительно обусловленный метод градиентного спуска для минимизации $\rho (\mathbf {x} )$ является $$\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.$$

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

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

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

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

Источники

• Аксельссон, Оу (1996). Итерационные методы решения . Издательство Кембриджского университета. п. 6722. ИСБН  978-0-521-55569-2 .
• Дьяконов Е.Г. (1996). Оптимизация при решении эллиптических задач . ЦРК-Пресс. п. 592. ИСБН  978-0-8493-2872-5 .
• Саад, Юсеф и ван дер Ворст, Хенк (2001). «Итерационное решение линейных систем в ХХ веке». В Брезински, К. и Вуйтеке, Л. (ред.). Численный анализ: историческое развитие в 20 веке . Издательство Elsevier Science . §8 Методы предварительной подготовки, стр. 193–8. ISBN  0-444-50617-9 .
• ван дер Ворст, HA (2003). Итерационные методы Крылова для больших линейных систем . Издательство Кембриджского университета, Кембридж. ISBN  0-521-81828-1 .
• Чен, Кэ (2005). Методы и приложения матричной предварительной подготовки . Кембридж: Издательство Кембриджского университета. ISBN  978-0521838283 . OCLC   61410324 .