Русская Википедия:Предобуславливание
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачиШаблон:Уточнить. Предобуславливаемая задача обычно затем решается итерационным методом.
Предобуславливание для систем линейных алгебраических уравнений
В линейной алгебре и вычислительной математике <math>P</math> предобуславливатель для матрицы <math>A</math> если у матрицы <math>P^{-1} A</math> число обусловленности меньше, чем у <math>A</math>. Также чаще говорят, что <math>T=P^{-1}</math> это предобуславливатель, чем просто <math>P</math>, так как точное значение <math>P</math> обычно требует больших затрат на вычисление. Поэтому под предобуславливанием часто понимают вычисление <math>T=P^{-1}</math>, точнее произведение вектора-столбца или матрицу векторов-столбцов на <math>T=P^{-1}</math>, что обычно выполняется сложными программными пакетами с использованием итерационных методов, где в конечном итоге не вычисляются точные значения ни для <math>P</math>, ни для <math>T=P^{-1}</math>.
Предобуславливание используется в итерационных методах при решении систем линейных алгебраических уравнений вида <math>Ax=b</math>, так как скорость сходимости для большинства итерационных линейных решателей увеличивается с уменьшением числа обусловленности в результате предобуславливания. Решатели с предобуславливанием обычно эффективнее, чем использование простых решателей, например, таких, как метод Гаусса в случае больших и особенно в случае разреженных матриц. Итерационные решатели с предобуславливанием могут использовать безматричные методы, в которых матрица коэффициентов <math>A</math> не хранится отдельно, а доступ к её элементам происходит через произведения матриц-векторов.
Определение
Вместо решения исходной системы линейных алгебраических уравнений можно решать предобусловленную систему <math> AP^{-1}Px = b</math>, которую можно решить через форму <math>AP^{-1}y=b</math>, где <math>y</math> удовлетворяет условию <math>Px=y</math>, или решить предобусловленную слева систему: <math> P^{-1}(Ax-b)=0</math>.
В результате получается то же решение, что и в исходной системе, до тех пор пока матрица-предобуславливатель <math>P</math> невырождена. Наиболее распространенным является предобуславливание слева. Целью предобуславливания является уменьшение числа обусловленности левой или правой предобусловленной системы — <math> P^{-1}A</math> или <math> AP^{-1}</math> соответственно. Предобусловленная матрица <math> P^{-1}A</math> или <math> AP^{-1}</math> почти никогда не формируется отдельно. Вместо этого операция предобуславливания <math> P^{-1}</math> выполняется только над уже готовыми векторами, которые получаются в результате расчета итерационными методами.
Использование <math> P</math> это всегда компромисс. Так как оператор <math> P^{-1}</math> применяется на каждом шаге итерационного линейного решателя, операция <math> P^{-1}</math> должна быть легко вычисляемой (по времени вычисления). Наиболее быстрым предобуславливателем в этом случае будет <math> P=I</math>, так как <math> P^{-1}=I</math>. Очевидно, что в результате работы такого предобуславливателя получается исходная система. Другая крайность — выбор <math> P=A</math>, что даст <math> P^{-1}A=AP^{-1}=I</math>, при этом будет получено оптимальное число обусловленности 1, требующее одной итерации для того, чтобы решение сошлось. Тем не менее в этом случае <math> P^{-1}=A^{-1}</math> и сложность вычисления предобуславливателя сравнима со сложностью решения исходной системы. Поэтому необходимо выбирать <math> P</math> где-то между двумя этими крайними случаями, пытаясь получить минимальное число итераций сохраняя легкость вычисления <math> P^{-1}</math>. Некоторые примеры основных подходов предобуславливания описаны ниже.
Итерационные методы с предобуславливанием
Итерационные методы с предобуславливанием для <math> Ax-b=0</math> в большинстве случаев математически эквивалентны стандартным итерационным методам, выполняемым над предобусловленной системой <math> P^{-1}(Ax-b)=0</math>. Например, стандартный метод итераций Ричардсона для решения <math> Ax-b=0</math> будет выглядеть как
- <math>\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n (A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.</math>
В случае предобусловленной системы <math> P^{-1}(Ax-b)=0</math>, предобусловленный метод будет выглядеть как
- <math>\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P^{-1}(A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.</math>
Примерами наиболее популярных итерационных методов с предобуславливанием для линейных систем являются метод сопряженных градиентов с предобуславливанием, метод бисопряженных градиентов и метод обобщенных минимальных невязок. В итерационных методах, которые вычисляют итерационные параметры через скалярные произведения, требуются соответствующие изменения в скалярном произведении вместе с заменой <math> P^{-1}(Ax-b)=0</math> на <math> Ax-b=0.</math>
Геометрическая интерпретация
Для симметричной положительно определенной матрицы <math> A</math> предобуславливатель <math> P</math> обычно выбирается также симметричный и положительно определенный. После этого оператор предобуславливания <math> P^{-1}A</math> также симметричный и положительно определенный. В этом случае желаемый эффект в применении предобуславливателя это придать квадратную форму оператору предобуславливания <math> P^{-1}A</math> и при этом сохранить сферическую форму скалярного произведения с <math> P</math>.
Шаблон:Rq Шаблон:Методы решения СЛАУ
