Неполная LU-факторизация

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

Введение

Рассмотрим разреженную линейную систему $Ax=b$. Их часто решают путем вычисления факторизации $A=LU$, с L нижним унитреугольным и U. треугольным верхним Затем один решает $Ly=b$, $Ux=y$, что можно сделать эффективно, поскольку матрицы треугольные.

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

Вместо этого неполная факторизация ищет треугольные матрицы L , U такие, что $A\approx LU$ скорее, чем $A=LU$. Решение для $LUx=b$ можно сделать быстро, но не дает точного решения $Ax=b$. Итак, вместо этого мы используем матрицу $M=LU$ в качестве предварительного обусловливателя в другом итерационном алгоритме решения, таком как метод сопряженных градиентов или GMRES .

Определение

Для данной матрицы $A\in \mathbb {R} ^{n\times n}$ один определяет график $G(A)$ как

$G(A):=\left\lbrace (i,j)\in \mathbb {N} ^{2}:A_{ij}\neq 0\right\rbrace \,,$

который используется для определения условий шаблонов разреженности $S$ необходимо выполнить

$S\subset \left\lbrace 1,\dots ,n\right\rbrace ^{2}\,,\quad \left\lbrace (i,i):1\leq i\leq n\right\rbrace \subset S\,,\quad G(A)\subset S\,.$

Разложение формы $A=LU-R$ где выполняются следующие условия

• $L\in \mathbb {R} ^{n\times n}$ представляет собой нижнюю унитреугольную матрицу
• $U\in \mathbb {R} ^{n\times n}$ представляет собой верхнетреугольную матрицу
• $L,U$ равны нулю вне шаблона разреженности: $L_{ij}=U_{ij}=0\quad \forall \;(i,j)\notin S$
• $R\in \mathbb {R} ^{n\times n}$ равен нулю в пределах шаблона разреженности: $R_{ij}=0\quad \forall \;(i,j)\in S$

называется неполным LU-разложением (относительно шаблона разреженности $S$).

Шаблон разреженности L и U часто выбирается таким же, как шаблон разреженности исходной A. матрицы а не копировать, единственная необходимая дополнительная память предназначена для записей L и U. Если на базовую матричную структуру можно ссылаться с помощью указателей , Этот предобуславливатель называется ILU(0).

Стабильность

Что касается устойчивости ILU, Мейеринком и ван дер Ворстом была доказана следующая теорема.

Позволять $A$ быть M-матрицей , (полное) LU-разложение, заданное формулой $A={\hat {L}}{\hat {U}}$и ILU $A=LU-R$.Затем

$|L_{ij}|\leq |{\hat {L}}_{ij}|\quad \forall \;i,j$

держит.Таким образом, ILU по крайней мере так же стабилен, как и (полное) разложение LU.

Обобщения

Можно получить более точный предобуславливатель, допустив некоторый уровень дополнительного заполнения факторизации. Распространенным выбором является использование шаблона разреженности A ² вместо А ; эта матрица заметно более плотна, чем A , но все еще разрежена во всем. Этот предобуславливатель называется ILU(1). Затем можно обобщить эту процедуру; предобуславливатель ILU(k) матрицы A представляет собой неполную LU-факторизацию с шаблоном разреженности матрицы A. ^к+1 .

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

Факторизация ILU может выполняться как итерация с фиксированной запятой высокопараллельным способом.

См. также

• Неполная факторизация Холецкого

Ссылки

• Саад, Юсеф (1996), Итеративные методы для разреженных линейных систем (1-е изд.), Бостон: PWS, ISBN  978-0-534-94776-7 . См. раздел 10.3 и далее.

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

• Неполная LU-факторизация на CFD Wiki