Предобуславливатель

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

• 1 Предварительное кондиционирование для линейных систем
  • 1.1 Описание
  • 1.2 Итерационные методы с предварительным условием
    • 1.2.1 Линейное предварительное кондиционирование
  • 1.3 Геометрическая интерпретация
  • 1.4 Переменное и нелинейное предварительное кондиционирование
  • 1.5 Спектрально эквивалентное предварительное кондиционирование
  • 1.6 Примеры
    • 1.6.1 Предварительное кондиционирование Якоби (или диагональное)
    • 1.6.2 SPAI
    • 1.6.3 Другое предварительные кондиционеры
  • 1.7 Внешние ссылки
• 2 Предварительное кондиционирование для задач на собственные значения
  • 2.1 Спектральные преобразования
  • 2.2 Общее предварительное кондиционирование
    • 2.2.1 Идеальное предварительное кондиционирование
    • 2.2.2 Практическое предварительное кондиционирование
  • 2.3 Внешние ссылки
• 3 Предварительная подготовка в оптимизации
  • 3.1 Описание
  • 3.2 Связь с линейными системами
  • 3.3 Связь с проблемами собственных значений
  • 3.4 Предварительная подготовка переменных
• 4 Ссылки
• 5 Источники

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

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

Описание

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

$AP\; -\; 1\; P\; x\; =\; b\; \{\backslash \; displaystyle\; AP\; ^\; \{-\; 1\}\; Px\; =\; b\}$

путем решения

$AP\; -\; 1\; y\; =\; b\; \{\backslash \; displaystyle\; AP\; ^\; \{-\; 1\}\; y\; =\; b\}$

для $y\; \{\backslash \; displaystyle\; y\}$и

$P\; x\; =\; y\; \{\backslash \; displaystyle\; Px\; =\; y\}$

для $x\; \{\backslash \; displaystyle\; x\}$.

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

$P\; -\; 1\; (A\; x\; -\; б)\; =\; 0.\; \{\backslash \; displaystyle\; P\; ^\; \{-\; 1\}\; (Ax-b)\; =\; 0.\}$

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

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

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

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

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

$xn\; +\; 1\; =\; xn\; -\; \gamma \; n\; (A\; xn\; -\; b),\; n\; \ge \; 0.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +\; 1\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; gamma\; \_\; \{n\}\; (A\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; mathbf\; \{b\}),\; \backslash \; n\; \backslash \; geq\; 0.\}$

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

$xn\; +\; 1\; =\; xn\; -\; \gamma \; n\; P\; -\; 1\; (A\; xn\; -\; b),\; n\; \ge \; 0.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +\; 1\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; gamma\; \_\; \{n\}\; P\; ^\; \{-\; 1\}\; (A\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; mathbf\; \{b\}),\; \backslash \; n\; \backslash \; geq\; 0.\}$

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

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

Пусть линейный итерационный метод задается разделением матрицы $A\; =\; M\; -\; N\; \{\backslash \; displaystyle\; A\; =\; MN\}$и матрицей итераций $C\; =\; I\; -\; M\; -\; 1\; A\; \{\backslash \; displaystyle\; C\; =\; IM\; ^\; \{-\; 1\}\; A\}$.

Предположим, что следующая

• матрица системы $A\; \{\backslash \; displaystyle\; A\}$symmetric положительно-определенная
• матрица разбиения $M\; \{\backslash \; displaystyle\; M\}$является симметричной положительно определенной
• линейный итерационный метод сходится: .

Тогда сокращение числа состояния системы $\kappa \; (M\; -\; 1\; A)\; \{\backslash \; displaystyle\; \backslash \; kappa\; (M\; ^\; \{-\; 1\}\; A)\}$ограничивается сверху соотношением

$\kappa \; (M\; -\; 1\; A)\; \le \; 1\; +\; \rho \; (C)\; 1\; -\; \rho \; (C).\; \{\backslash \; displaystyle\; \backslash \; kappa\; (M\; ^\; \{-\; 1\}\; A)\; \backslash \; leq\; \{\backslash \; frac\; \{1+\; \backslash \; rho\; (C)\}\; \{1-\; \backslash \; rho\; (C)\}\}\; \backslash ,.\}$

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

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

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

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

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

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

Примеры

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

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

SPAI

Преобразователь Sparse Approximate Inverse минимизирует $\Vert \; AT\; -\; I\; \Vert \; F,\; \{\backslash \; displaystyle\; \backslash \; |\; AT-\; I\; \backslash \; |\; \_\; \{F\},\}$где $\Vert \; \cdot \; \Vert \; F\; \{\backslash \; displaystyle\; \backslash \; |\; \backslash \; cdot\; \backslash \; |\; \_\; \{F\}\}$- норма Фробениуса и $T\; =\; P\; -\; 1\; \{\backslash \; displaystyle\; T\; =\; P\; ^\; \{-\; 1\}\}$взяты из некоторого подходящим образом ограниченного набора разреженных матриц. В соответствии с нормой Фробениуса это сводится к решению множества независимых задач наименьших квадратов (по одной для каждого столбца). Записи в $T\; \{\backslash \; displaystyle\; T\}$должны быть ограничены некоторым шаблоном разреженности, иначе проблема останется такой же сложной и трудоемкой, как нахождение точной инверсии $A\; \{\backslash \; displaystyle\; A\}$. Метод был предложен MJ Grote и T. Huckle вместе с подходом к выбору паттернов разреженности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$xn\; +\; 1\; =\; xn\; -\; \gamma \; n\; T\; (A\; -\; \lambda \; п\; I)\; xn,\; n\; \ge \; 0.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +\; 1\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; gamma\; \_\; \{n\}\; T\; (A-\; \backslash \; lambda\; \_\; \{n\}\; I)\; \backslash \; mathbf\; \{x\}\; \_\; \{n\},\; \backslash \; n\; \backslash \; geq\; 0.\}$

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

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

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

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

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

Описание

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

$xn\; +\; 1\; =\; xn\; -\; \gamma \; n\; \nabla \; F\; (xn),\; n\; \ge \; 0.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +\; 1\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; gamma\; \_\; \{n\}\; \backslash \; nabla\; F\; (\backslash \; mathbf\; \{x\}\; \_\; \{n\}),\; \backslash \; n\; \backslash \; geq\; 0.\}$

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

$xn\; +\; 1\; =\; xn\; -\; \gamma \; n\; P\; -\; 1\; \nabla \; F\; (xn),\; n\; \ge \; 0.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +\; 1\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; gamma\; \_\; \{n\}\; P\; ^\; \{-\; 1\}\; \backslash \; nabla\; F\; (\backslash \; mathbf\; \{x\}\; \_\; \{n\}),\; \backslash \; n\; \backslash \; geq\; 0.\}$

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

Связь с линейными системами

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

$F\; (x)\; =\; 1\; 2\; x\; TA\; x\; -\; x\; T\; b\; \{\backslash \; displaystyle\; F\; (\backslash \; mathbf\; \{x\})\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \backslash \; mathbf\; \{x\}\; ^\; \{T\}\; A\; \backslash \; mathbf\; \{x\}\; -\; \backslash \; mathbf\; \{x\}\; ^\; \{T\}\; \backslash \; mathbf\; \{b\}\}$,

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

$xn\; +\; 1\; =\; xn\; -\; \gamma \; n\; P\; -\; 1\; (A\; xn\; -\; b),\; n\; \ge \; 0.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +\; 1\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; gamma\; \_\; \{n\}\; P\; ^\; \{-\; 1\}\; (\; A\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; mathbf\; \{b\}),\; \backslash \; n\; \backslash \; geq\; 0.\}$

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

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

Минимум отношения Рэлея

$\rho \; (x)\; =\; x\; TA\; xx\; T\; x,\; \{\backslash \; displaystyle\; \backslash \; rho\; (\backslash \; mathbf\; \{x\})\; =\; \{\; \backslash \; frac\; \{\backslash \; mathbf\; \{x\}\; ^\; \{T\}\; A\; \backslash \; mathbf\; \{x\}\}\; \{\backslash \; mathbf\; \{x\}\; ^\; \{T\}\; \backslash \; mathbf\; \{x\}\}\},\}$

где $x\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\}$- вещественный ненулевой вектор-столбец, а $A\; \{\backslash \; displaystyle\; A\}$- действительный симметричный положительный -определенная матрица, является наименьшим собственным значением из $A\; \{\backslash \; displaystyle\; A\}$, а минимизатор - соответствующий собственный вектор. Поскольку $\nabla \; \rho \; (x)\; \{\backslash \; displaystyle\; \backslash \; nabla\; \backslash \; rho\; (\backslash \; mathbf\; \{x\})\}$пропорционально $A\; x\; -\; \rho \; (x)\; x\; \{\backslash \; displaystyle\; A\; \backslash \; mathbf\; \{x\}\; -\; \backslash \; rho\; (\backslash \; mathbf\; \{x\})\; \backslash \; mathbf\; \{x\}\}$, предварительно подготовленный градиентный спуск метод минимизации $\rho \; (x)\; \{\backslash \; displaystyle\; \backslash \; rho\; (\backslash \; mathbf\; \{x\})\}$равно

$xn\; +\; 1\; =\; xn\; -\; \gamma \; n\; P\; -\; 1\; (A\; xn\; -\; \rho \; (xn)\; xn),\; n\; \ge \; 0.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +\; 1\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; gamma\; \_\; \{n\}\; P\; ^\; \{-\; 1\}\; (A\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; -\; \backslash \; rho\; (\backslash \; mathbf\; \{\; x\_\; \{n\}\})\; \backslash \; mathbf\; \{x\_\; \{n\}\}),\; \backslash \; n\; \backslash \; geq\; 0.\}$

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

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

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

$xn\; +\; 1\; =\; xn\; -\; \gamma \; n\; P\; n\; -\; 1\; \nabla \; F\; (xn),\; n\; \ge \; 0.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +\; 1\}\; =\; \backslash \; mathbf\; \{\; x\}\; \_\; \{n\}\; -\; \backslash \; gamma\; \_\; \{n\}\; P\_\; \{n\}\; ^\; \{-\; 1\}\; \backslash \; nabla\; F\; (\backslash \; mathbf\; \{x\}\; \_\; \{n\}),\; \backslash \; n\; \backslash \; geq\; 0.\}$

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

• Axelsson, Owe (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.
• ван дер Ворст, Х.А. (2003). Итерационные методы Крылова для больших линейных систем. Издательство Кембриджского университета, Кембридж. ISBN 0-521-81828-1.