В математике , прекондиционирование является применением преобразования, называется предобуславливателем , что условия данной проблема в форму , которая является более подходящей для численных методов решающих. Предварительная подготовка обычно связана с уменьшением числа условий проблемы. Предварительно обусловленная задача затем обычно решается итерационным методом .
Предварительная подготовка для линейных систем
В линейной алгебре и численный анализ , переобусловливатель матрицы матрица такая, что имеет меньшее число обусловленности, чем. Также принято называть прекондиционер, а не , поскольку сам редко доступен в явном виде. В современном предварительном кондиционировании применение, т. е. умножение вектора-столбца или блока векторов-столбцов на , обычно выполняется довольно сложными пакетами компьютерных программ без использования матриц , т.е., ни (а часто даже не ) явно доступны в матричной форме.
Предобуславливатели полезны в итерационных методах решения линейной системы. для поскольку скорость сходимости для большинства итерационных линейных решателей увеличивается, потому что число обусловленности матрицы уменьшается в результате предварительной обработки. Итерационные решатели с предварительным условием обычно превосходят прямые решатели, например, метод исключения Гаусса , для больших, особенно разреженных , матриц. Итерационные решатели могут использоваться как безматричные методы , т.е. стать единственным выбором, если матрица коэффициентов не сохраняется явно, но доступ к нему осуществляется путем оценки произведения матрица-вектор.
Описание
Вместо решения исходной линейной системы, описанной выше, можно решить правильную предварительно обусловленную систему:
через решение
для а также
для .
В качестве альтернативы можно решить левую предварительно подготовленную систему:
Обе системы дают то же решение, что и исходная система, пока матрица предобуславливателя это неособо . Левое предварительное кондиционирование встречается чаще.
Целью этой предварительно обусловленной системы является уменьшение числа обусловленности левой или правой предварительно обусловленной системной матрицы. или же соответственно. Предварительно обусловленная матрица или же почти никогда не формируется явно. Только действие применения операции решения предобуславливателя к заданному вектору необходимо вычислить итерационными методами.
Обычно при выборе . Поскольку оператор должен применяться на каждом шаге итеративного линейного решателя, он должен иметь небольшую стоимость (время вычислений) применения операция. Поэтому самый дешевый предварительный кондиционер будет с того времени Ясно, что это приводит к исходной линейной системе, а предобуславливатель ничего не делает. С другой стороны, выбор дает которое имеет оптимальное число обусловленности 1, требующее одной итерации для сходимости; однако в этом случаеа применение предобуславливателя так же сложно, как решение исходной системы. Поэтому выбирают как нечто среднее между этими двумя крайностями, в попытке достичь минимального количества линейных итераций, сохраняя при этом оператор как можно проще. Некоторые примеры типичных подходов к предварительному кондиционированию подробно описаны ниже.
Предварительно обусловленные итерационные методы
Предварительно обусловленные итерационные методы для в большинстве случаев математически эквивалентны стандартным итерационным методам, применяемым к предварительно обусловленной системе. Например, стандартная итерация Ричардсона для решения является
Применяется к предварительно подготовленной системе он превращается в метод с предварительным условием
Примеры популярных выдержано итерационных методов для линейных систем включают в себя предварительно сопряженные градиентах метод , то метод бисопряженного градиента и обобщенный минимальный остаточный метод . Итерационные методы, которые используют скалярные произведения для вычисления итерационных параметров, требуют соответствующих изменений в скалярном произведении вместе с заменой для
Линейное предварительное кондиционирование
Пусть линейный итерационный метод задается разбиением матрицы, и матрица итераций .
Предположим следующее
- матрица системы является симметричным положительно определенным
- матрица расщепления является симметричным положительно определенным
- линейный итерационный метод сходится: .
Тогда уменьшение числа обусловленности системы можно ограничить сверху
Геометрическая интерпретация
Для симметричной положительно определенной матрицы предварительный кондиционер обычно также выбирается симметричным положительно определенным. Предварительно обусловленный оператор тогда также симметрично положительно определено, но относительно -основное скалярное произведение . В этом случае желаемый эффект от применения предобуславливателя состоит в том, чтобы сделать квадратичную форму предобусловленного оператора с уважением к -основанное скалярное произведение должно быть почти сферическим. [1]
Переменное и нелинейное предварительное кондиционирование
Обозначение , подчеркнем, что предобусловливание практически реализовано как умножение некоторого вектора от , т.е. вычисление продукта Во многих приложениях дается не как матрица, а как оператор действуя по вектору . Однако некоторые популярные прекондиционеры меняются с и зависимость от не может быть линейным. Типичные примеры включают использование нелинейных итерационных методов , например метода сопряженных градиентов , как части конструкции предобуславливателя. Такие предварительные кондиционеры могут быть практически очень эффективными, однако их поведение трудно предсказать теоретически.
Случайная предварительная подготовка
Один интересный частный случай предварительной обработки переменных - это случайная предварительная подготовка, например многосеточная предварительная подготовка в случайных сетках курсов. [2] При использовании в методах градиентного спуска случайное предварительное кондиционирование можно рассматривать как реализацию стохастического градиентного спуска и может привести к более быстрой сходимости по сравнению с фиксированным предварительным кондиционированием, поскольку оно нарушает асимптотический «зигзагообразный» шаблон градиентного спуска .
Спектрально эквивалентное предварительное кондиционирование
Чаще всего предварительное кондиционирование используется для итеративного решения линейных систем, полученных в результате аппроксимации уравнений в частных производных . Чем лучше качество аппроксимации, тем больше размер матрицы. В таком случае цель оптимального предварительного кондиционирования, с одной стороны, состоит в том, чтобы сделать спектральное число обусловленности равнымбыть ограниченным сверху константой, не зависящей от размера матрицы, что Дьяконов назвал спектрально эквивалентным предобуславливанием . С другой стороны, стоимость применения в идеале должно быть пропорционально (также независимо от размера матрицы) стоимости умножения вектором.
Примеры
Предобуславливатель Якоби (или диагональный)
Предобуславливатель Якоби является одной из простейших форм предобусловливания, в которых предобуславливатель выбирается так, чтобы быть диагоналями матрицы Предполагая , мы получили Эффективен для диагонально доминирующих матриц. .
ИСПАНИЯ
В разреженном Примерных Обратные переобусловливателя сводит к минимуму где - норма Фробениуса иявляется из некоторого подходящим образом ограниченного набора разреженных матриц . По норме Фробениуса это сводится к решению множества независимых задач наименьших квадратов (по одной для каждого столбца). Записи в должны быть ограничены некоторым шаблоном разреженности, иначе проблема останется такой же сложной и требующей много времени, как нахождение точной инверсии . Метод был предложен MJ Grote и T. Huckle вместе с подходом к выбору моделей разреженности. [3]
Другие прекондиционеры
- Неполная факторизация Холецкого
- Неполная факторизация LU
- Последовательное чрезмерное расслабление
- Симметричное последовательное чрезмерное расслабление
- Предварительное кондиционирование многосеточных сетей
Внешние ссылки
- Предварительно подготовленный сопряженный градиент - math-linux.com
- Шаблоны для решения линейных систем: строительные блоки для итерационных методов
Предварительная подготовка для задач на собственные значения
Задачи на собственные значения могут быть сформулированы несколькими альтернативными способами, каждый из которых ведет к собственной предварительной обработке. Традиционное предварительное кондиционирование основано на так называемых спектральных преобразованиях. Зная (приблизительно) целевое собственное значение, можно вычислить соответствующий собственный вектор, решив связанную однородную линейную систему, что позволяет использовать предварительное кондиционирование для линейной системы. Наконец, формулировка проблемы собственных значений как оптимизации коэффициента Рэлея выводит на сцену заранее подготовленные методы оптимизации. [4]
Спектральные преобразования
По аналогии с линейными системами для задачи на собственные значения может возникнуть соблазн заменить матрицу с матрицей с использованием прекондиционера . Тем не менее, это имеет смысл только в том случае , если ищущие собственные векторы из а также одинаковы. Это случай спектральных преобразований.
Самым популярным спектральным преобразованием является так называемое преобразование сдвига и инвертирования , когда для заданного скаляра, называемая сдвигом , исходная проблема собственных значений заменяется задачей сдвига и инвертирования . Собственные векторы сохраняются, и можно решить проблему сдвига и инвертирования с помощью итеративного решателя, например, степенной итерации . Это дает обратную итерацию , которая обычно сходится к собственному вектору, соответствующему собственному значению, ближайшему к сдвигу.. Фактор Рэлея итерация является методом сдвига и-инвертным с переменным сдвигом.
Спектральные преобразования специфичны для задач на собственные значения и не имеют аналогов для линейных систем. Они требуют точного численного расчета задействованного преобразования, которое становится основным узким местом для больших проблем.
Общая предварительная подготовка
Чтобы установить тесную связь с линейными системами, предположим, что целевое собственное значение известно (приблизительно). Тогда можно вычислить соответствующий собственный вектор из однородной линейной системы. Используя понятие левого предобуславливания для линейных систем, получаем, где является предобуславливателем, который мы можем попытаться решить, используя итерацию Ричардсона
Идеал прекондиционирование [4]
Псевдообратная матрица является предобуславливателем, благодаря которому итерация Ричардсона, приведенная выше, сходится за один шаг с, поскольку , обозначаемый , - ортогональный проектор на собственное подпространство, соответствующий . Выборнецелесообразно по трем независимым причинам. Первый, на самом деле неизвестно, хотя его можно заменить его приближением . Во-вторых, точная псевдообратная матрица Мура – Пенроуза требует знания собственного вектора, который мы пытаемся найти. Этого можно несколько избежать, используя предобуславливатель Якоби – Дэвидсона. , где приблизительно . Наконец, что не менее важно, этот подход требует точного численного решения линейной системы с системной матрицей, который становится таким же дорогостоящим для больших проблем, как описанный выше метод сдвига и инвертирования. Если решение недостаточно точное, второй шаг может быть излишним.
Практическая подготовка
Сначала заменим теоретическое значение в итерации Ричардсона выше с ее текущим приближением получить практический алгоритм
Популярный выбор - с использованием функции частного Рэлея. Практическое предварительное кондиционирование может быть таким же тривиальным, как простое использование или же Для некоторых классов задач на собственные значения эффективность было продемонстрировано как численно, так и теоретически. Выбор позволяет легко использовать для задач на собственные значения огромное количество предобуславливателей, разработанных для линейных систем.
Из-за меняющегося значения , всесторонний теоретический анализ сходимости намного сложнее, по сравнению со случаем линейных систем, даже для простейших методов, таких как итерация Ричардсона .
Внешние ссылки
- Шаблоны для решения алгебраических задач на собственные значения: практическое руководство
Предварительная подготовка в оптимизации
В оптимизации предварительное кондиционирование обычно используется для ускорения алгоритмов оптимизации первого порядка .
Описание
Например, чтобы найти локальный минимум вещественной функциис использованием градиентного спуска , один принимают меры , пропорциональные отрицательную часть градиента (или приблизительного градиента) функции в текущей точке:
К градиенту применяется предварительный кондиционер:
Предварительное кондиционирование здесь можно рассматривать как изменение геометрии векторного пространства с целью сделать наборы уровней похожими на круги. [5] В этом случае предварительно обусловленный градиент стремится ближе к точке экстремумов, как на рисунке, что ускоряет сходимость.
Подключение к линейным системам
Минимум квадратичной функции
- ,
где а также являются действительными векторами-столбцами и является вещественной симметричной положительно определенной матрицей , является в точности решением линейного уравнения. С, метод предобусловленного градиентного спуска минимизации является
Это итерация Ричардсона с предварительными условиями для решения системы линейных уравнений .
Связь с проблемами собственных значений
Минимум фактора Рэлея
где является вещественным ненулевым вектор-столбцом и является реальным симметричная положительно определенная матрица , наименьшее собственное значение из, а минимизатор - соответствующий собственный вектор . С пропорционально , метод предобусловленного градиентного спуска минимизации является
Это аналог итерации Ричардсона с предварительными условиями для решения задач на собственные значения.
Предварительная подготовка переменных
Во многих случаях может быть полезно изменить предварительное кондиционирование на некотором или даже на каждом шаге итеративного алгоритма , чтобы приспособиться к изменяющейся форме наборов уровней, как в
Однако следует иметь в виду, что создание эффективного предобуславливателя очень часто требует больших вычислительных ресурсов. Повышенная стоимость обновления предобуславливателя может легко перекрыть положительный эффект от более быстрой сходимости.
Рекомендации
- ^ Шевчук, Джонатан Ричард (4 августа 1994). «Введение в метод сопряженных градиентов без мучительной боли» (PDF) .
- ^ Хенрикус Bouwmeester, Эндрю Догерти, Andrew V Князев. Несимметричное предварительное кондиционирование для методов сопряженного градиента и наискорейшего спуска. Процедуры информатики, том 51, страницы 276-285, Elsevier, 2015. https://doi.org/10.1016/j.procs.2015.05.241
- ^ Гроте, М.Дж. и Хакл, Т. (1997). «Параллельная предварительная подготовка с разреженными приближенными инверсиями». Журнал СИАМ по научным вычислениям . 18 (3): 838–53. DOI : 10,1137 / S1064827594276552 .
- ^ а б Князев, Андрей В. (1998). "Предварительно подготовленные собственные средства - оксюморон?" . Электронные транзакции по численному анализу . 7 : 104–123.
- ^ Химмельблау, Дэвид М. (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. (ред.). Численный анализ: исторические события в 20 веке . Издательство Elsevier Science . §8 Методы прекондиционирования, стр. 193–8. ISBN 0-444-50617-9.
- ван дер Ворст, HA (2003). Итерационные методы Крылова для больших линейных систем . Издательство Кембриджского университета, Кембридж. ISBN 0-521-81828-1.
- Ке Чен: "Методы и приложения предварительной обработки матриц", Cambridge University Press, ISBN 978-0521838283 (2005).