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

Preconditioner

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

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

В линейная алгебра и числовой анализ, а предварительный кондиционер матрицы матрица такая, что имеет меньший номер условия чем . Также принято называть прекондиционер, а не , поскольку сам редко доступен в явном виде. В современном предварительном кондиционировании применение , то есть умножение вектора-столбца или блока векторов-столбцов на , обычно выполняется довольно сложными пакетами компьютерного программного обеспечения в безматричная мода, т.е. где ни , ни (а часто даже не ) явно доступны в матричной форме.

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

Описание

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

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

за и

за .

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

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

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

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

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

Предварительно обусловленные итерационные методы для в большинстве случаев математически эквивалентны стандартным итерационным методам, применяемым к предварительно обусловленной системе Например, стандартный Итерация Ричардсона для решения является

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

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

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

Пусть линейный итерационный метод дается расщеплением матрицы , и матрица итераций .

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

Тогда уменьшение системного номер условия можно ограничить сверху

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

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

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

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

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

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

Примеры

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

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

ИСПАНИЯ

В Редкое приближенное обратное предварительный кондиционер минимизирует куда это Норма Фробениуса и из некоторого подходящего ограниченного набора разреженные матрицы. В соответствии с нормой Фробениуса это сводится к решению множества независимых задач наименьших квадратов (по одной для каждого столбца). Записи в должны быть ограничены некоторым шаблоном разреженности, иначе проблема останется такой же сложной и трудоемкой, как нахождение точного обратного . Этот метод был предложен M.J. Grote и T. Huckle вместе с подходом к выбору моделей разреженности.[2]

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

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

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

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

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

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

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

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

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

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

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

В Псевдообратная матрица Мура – ​​Пенроуза является предобуславливателем, который делает Итерация Ричардсона выше сходятся за один шаг с , поскольку , обозначаемый , - ортогональный проектор на собственное подпространство, соответствующий . Выбор нецелесообразно по трем независимым причинам. Первый, на самом деле неизвестно, хотя его можно заменить его приближением . Во-вторых, точный Псевдообратная матрица Мура – ​​Пенроуза требует знания собственного вектора, который мы пытаемся найти. Это можно в некоторой степени обойти, используя Предобуславливатель Якоби-Дэвидсона , куда приблизительно . Наконец, что не менее важно, этот подход требует точного численного решения линейной системы с системной матрицей , который становится таким же дорогостоящим для больших проблем, как описанный выше метод сдвига и инвертирования. Если решение недостаточно точное, второй шаг может быть излишним.

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

Сначала заменим теоретическое значение в Итерация Ричардсона выше с его текущим приближением получить практический алгоритм

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

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

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

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

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

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

Описание

Например, чтобы найти местный минимум действительной функции с помощью градиентный спуск, предпринимаются шаги, пропорциональные отрицательный из градиент (или приблизительного градиента) функции в текущей точке:

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

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

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

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

,

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

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

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

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

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

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

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

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

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

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

  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.

Источники