Предобуславливание
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи[уточнить]. Предобуславливаемая задача обычно затем решается итерационным методом.
Предобуславливание для систем линейных алгебраических уравнений
[править | править код]В линейной алгебре и вычислительной математике предобуславливатель для матрицы если у матрицы число обусловленности меньше, чем у . Также чаще говорят, что это предобуславливатель, чем просто , так как точное значение обычно требует больших затрат на вычисление. Поэтому под предобуславливанием часто понимают вычисление , точнее произведение вектора-столбца или матрицу векторов-столбцов на , что обычно выполняется сложными программными пакетами с использованием итерационных методов, где в конечном итоге не вычисляются точные значения ни для , ни для .
Предобуславливание используется в итерационных методах при решении систем линейных алгебраических уравнений вида , так как скорость сходимости для большинства итерационных линейных решателей увеличивается с уменьшением числа обусловленности в результате предобуславливания. Решатели с предобуславливанием обычно эффективнее, чем использование простых решателей, например, таких как метод Гаусса в случае больших и особенно в случае разреженных матриц. Итерационные решатели с предобуславливанием могут использовать безматричные методы, в которых матрица коэффициентов не хранится отдельно, а доступ к её элементам происходит через произведения матриц-векторов.
Определение
[править | править код]Вместо решения исходной системы линейных алгебраических уравнений можно решать предобусловленную систему , которую можно решить через форму , где удовлетворяет условию , или решить предобусловленную слева систему: .
В результате получается то же решение, что и в исходной системе, до тех пор пока матрица-предобуславливатель невырождена. Наиболее распространенным является предобуславливание слева. Целью предобуславливания является уменьшение числа обусловленности левой или правой предобусловленной системы — или соответственно. Предобусловленная матрица или почти никогда не формируется отдельно. Вместо этого операция предобуславливания выполняется только над уже готовыми векторами, которые получаются в результате расчета итерационными методами.
Использование это всегда компромисс. Так как оператор применяется на каждом шаге итерационного линейного решателя, операция должна быть легко вычисляемой (по времени вычисления). Наиболее быстрым предобуславливателем в этом случае будет , так как . Очевидно, что в результате работы такого предобуславливателя получается исходная система. Другая крайность — выбор , что даст , при этом будет получено оптимальное число обусловленности 1, требующее одной итерации для того, чтобы решение сошлось. Тем не менее в этом случае и сложность вычисления предобуславливателя сравнима со сложностью решения исходной системы. Поэтому необходимо выбирать где-то между двумя этими крайними случаями, пытаясь получить минимальное число итераций сохраняя легкость вычисления . Некоторые примеры основных подходов предобуславливания описаны ниже.
Итерационные методы с предобуславливанием
[править | править код]Итерационные методы с предобуславливанием для в большинстве случаев математически эквивалентны стандартным итерационным методам, выполняемым над предобусловленной системой . Например, стандартный метод итераций Ричардсона для решения будет выглядеть как
В случае предобусловленной системы , предобусловленный метод будет выглядеть как
Примерами наиболее популярных итерационных методов с предобуславливанием для линейных систем являются метод сопряженных градиентов с предобуславливанием, метод бисопряженных градиентов и метод обобщенных минимальных невязок. В итерационных методах, которые вычисляют итерационные параметры через скалярные произведения, требуются соответствующие изменения в скалярном произведении вместе с заменой на
Геометрическая интерпретация
[править | править код]Для симметричной положительно определённой матрицы предобуславливатель обычно выбирается также симметричный и положительно определённый. После этого оператор предобуславливания также симметричный и положительно определённый. В этом случае желаемый эффект в применении предобуславливателя это придать квадратную форму оператору предобуславливания и при этом сохранить сферическую форму скалярного произведения с .
В статье не хватает ссылок на источники (см. рекомендации по поиску). |