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

15

У меня есть линейная система уравнений размером mxm, где m большое. Однако интересующие меня переменные - это только первые n переменных (n мало по сравнению с m). Есть ли способ, которым я могу приблизить решение для первых значений m без необходимости решения всей системы? Если это так, будет ли это приближение быстрее, чем решение полной линейной системы?

linear-algebra approximation Пол
источник

2

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

Джек Поулсон

1

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

Дан

4

@ OscarB: Пожалуйста, нет. Правило Крамера - это злодеяние в арифметике с плавающей точкой. Я никогда не слышал о том, чтобы он использовался для серьезных вычислений, и требуется немало усилий, чтобы избежать факторной сложности , где он все еще не конкурирует с устранением Гаусса.

Джек Поулсон

1

@Paul: Большая часть сокращения порядка моделей используется в контексте больших систем ODE или DAE. Иногда методологии сокращения мотивируются системами ODE или DAE, которые возникают в результате дискретизации PDE. Я не видел редукцию модели, используемую в чисто алгебраических уравнениях. (Если у вас есть, пожалуйста, пришлите мне ссылки, потому что я делаю свою диссертацию о методах сокращения модели и мне было бы очень интересно увидеть это.) Если вы хотите, я мог бы набросать, как может выглядеть сокращение модели, если мы будем рассматривать алгебраические уравнения как вырожденный случай системы дифференциально-алгебраических уравнений.

Джефф Оксберри

1

@JackPoulson - вы не возражаете обобщить свой комментарий в качестве ответа? Я думаю, что это самое правильное решение, и я не хочу, чтобы оно было потеряно в комментариях.

Арон Ахмадиа

13

Как уже отмечали другие, это трудно сделать с прямым решателем. Тем не менее, это не так сложно сделать с итеративными решателями. Для этого отметим, что большинство итерационных решателей так или иначе сводят к минимуму ошибку по отношению к некоторой норме. Часто эта норма либо индуцируется самой матрицей, но иногда она также является векторной нормой l2. Но это не обязательно так: вы можете выбрать, в какой норме вы хотите минимизировать ошибку (или остаточную величину), и вы можете, например, выбрать норму, в которой вы взвешиваете компоненты, которые вам нужны, с 1 и все остальные с 1e-12, то есть, например, что-то вроде (1e-24) и соответствующее скалярное произведение. Затем запишите все шаги итерационного решателя относительно этой нормы и скалярного произведения, и вы получите итерационный решатель, который уделяет значительно больше внимания интересующим вас векторным элементам, чем другим. $|| x ||^2 = \sum_{i=1}^5 x_i^2 +$ $\sum_{i=6}^N x_i^2$

Вопрос, конечно, заключается в том, нужно ли вам меньше итераций, чем при использовании скалярного продукта, который взвешивает все компоненты одинаково. Но это действительно должно быть так: допустим, вы заботитесь только о пяти первых векторных элементах. Тогда вам нужно не более пяти итераций, чтобы уменьшить ошибку в 1e12 раз, поскольку для описывающей их системы 5x5 требуется пять итераций. Это не доказательство, но я вполне уверен, что вам действительно следует избегать гораздо меньшего числа итераций, если вес в норме (1e-12 выше) меньше, чем допуск, с которым вы хотите решить линейную систему итеративно ,

Вольфганг Бангерт
источник

2

Хм, хорошая мысль. Мне было бы интересно увидеть реальный пример, так как я немного беспокоюсь о последствиях лишь попыток разрешить несколько степеней свободы; даже если остаток может быть небольшим, возможно, норма ошибки все еще достаточно велика (чтобы эффективно игнорировать большинство операторов).

Джек Полсон

Интуитивно понятно, что это работает только в том случае, если компоненты очень маленькой системы действительно доминируют над ответом в L2 (или нормой, в которой вы понимаете, что ваша ошибка должна измеряться). В противном случае, я думаю, что беспокойство Джека действительно, но я определенно был бы заинтересован даже увидеть числовое доказательство этого ...

Арон Ахмадиа

Нужно убедиться, что вы используете метод, который минимизирует ошибку , а не остаточный. Я думаю, что MinErr может быть хорошей отправной точкой.

Вольфганг Бангерт

@WolfgangBangerth: я не знаком с MINERR: это основная ссылка?

Джек Полсон

1

Даже этого недостаточно, потому что вы будете неточными. Вы не можете получить несколько компонентов точно, используя это взвешивание.

Мэтт Кнепли

17

Формирование дополнения Шура

Предположим, что вы переставили и разбили свою матрицу на форму

A знак равно (\begin{array}{cc} A_{11} & A_{12} \\ A_{21} & A_{22} \end{array}),

$A=\left(\begin{array}{cc}A_{11} & A_{12} \\ A_{21} & A_{22}\end{array}\right),$

так что содержит ваши степени свободы интересов и намного меньше, чем , тогда можно сформировать дополнение Шура $A_{22}$ $A_{11}$

S_{22} знак равно A_{22} - A_{21} A_{11}^{- 1} A_{12},

$S_{22} := A_{22} - A_{21} A_{11}^{-1} A_{12},$

либо с помощью частичной правосторонней факторизации LU, либо с помощью явной формулы, а затем можно понять в следующем смысле: $S_{22}$

S_{22} Икс знак равно Y \to (\begin{array}{cc} A_{11} & A_{12} \\ A_{21} & A_{22} \end{array}) (\begin{matrix} ⋆ \\ Икс \end{matrix}) знак равно (\begin{matrix} 0 \\ Y \end{matrix}),

$S_{22} x = y \;\;\rightarrow\;\; \left(\begin{array}{cc}A_{11} & A_{12}\\ A_{21} & A_{22}\end{array}\right) \left(\begin{array}{c}\star\\ x\end{array}\right)=\left(\begin{array}{c}0\\ y\end{array}\right),$

где представляет «неинтересную» часть решения. Таким образом, обеспечивается правая часть, которая является ненулевой в степенях свободы дополнения Шура $\star$ , нам нужно только решить против $S_{22}$ , чтобы получить часть решения, соответствующую этим степеням свободы. $S_{22}$

Вычислительная сложность в неструктурированном плотном случае

Установка на высоту и на высоту , затем стандартный метод для вычисления $N$ $A$ $n$ $A_{22}$ $S_{22}$ является первый множитель (давайте пока проигнорируем поворот) примерно в $L_{11} U_{11} := A_{11}$ работы, чтобы потом сформировать $2/3 (N-n)^3$

S_{22} знак равно A_{22} - (A_{21} U_{11}^{- 1}) (L_{11}^{- 1} A_{12}) знак равно A_{22} - A_{21} A_{11}^{- 1} A_{12}

$S_{22} := A_{22} - (A_{21} U_{11}^{-1})(L_{11}^{-1} A_{12}) = A_{22} - A_{21} A_{11}^{-1} A_{12}$

используя два треугольных решения, требующих работы каждый, а затем выполняя обновление до в $n(N-n)^2$ $A_{22}$ работы. $2n^2 (N-n)$

Таким образом, общая работа составляет примерно . Когда очень мало, $2/3 (N-n)^3 + 2n(N-n)^2 + 2n^2 (N-n)$ $n$ $N-n \approx N$ , так что стоимость может быть видно, что примерно , который является стоимость полного разложения. $2/3 N^3$

Преимущество состоит в том, что, если существует очень большое количество правых частей, которые должны быть решены с помощью одной и той же системы уравнений, то потенциально может быть многократно использован много раз, где для каждого решения потребуется только работы. (а не работают), если учтено. $S_{22}$ $2n^2$ $2N^2$ $S_{22}$

Вычислительная сложность в (типичном) разреженном случае

Если ваша разреженная система возникла из некоторого типа конечно-разностного или конечно-элементного приближения, то решатели разреженного прямого порядка почти наверняка смогут использовать некоторые структуры; 2d системы могут быть решены с помощью работы и хранения, в то время как 3D - системы могут быть решены с помощью работы и для хранения. Факторизованные системы могут быть решены с тем же объемом работы, что и требования к хранилищу. $O(N^{3/2})$ $O(N \log N)$ $O(N^2)$ $O(N^{4/3})$

Смысл воспитания вычислительных сложностей заключается в том, что если и у вас есть двумерная система, тогда, поскольку дополнение Шура, вероятно, будет плотным, сложность решения с учетом факторизованного дополнения Шура будет $n \approx \sqrt{N}$ , в котором отсутствует только логарифмический фактор по сравнению с решением полного система! В 3d, она требует работу вместо . $O(n^2) = O(N)$ $O(N)$ $O(N^{4/3})$

Поэтому важно иметь в виду, что в вашем случае, когда $n=\sqrt{N}$ , будет существенная экономия только в том случае, если вы работаете в нескольких измерениях и вам нужно решить множество правых сторон.

Джек Полсон
источник

1

Это отличная сводка по методу дополнения Шура, и когда он эффективен в вычислительном отношении!

Павел

6

Модельный подход сокращения

Поскольку Павел спросил, я расскажу о том, что произойдет, если вы воспользуетесь методами сокращения проекционных моделей для этой проблемы. Предположим, что вы могли бы придумать проектор такой, что диапазон , обозначаемый $\mathbf{P}$ $\mathbf{P}$ $\mathcal{R}(\mathbf{P})$ , содержит решение вашей линейной системы и имеет размерность , где $\mathbf{Ax} = \mathbf{b}$ $k$ $k$ - число неизвестных, для которых вы хотите решить в линейной системе.

Разложение по сингулярному значению даст следующую секционированную матрицу: $\mathbf{P}$

P = [\begin{array}{cc} V & * \end{array}] [\begin{array}{cc} d i a g (1_{k}) & 0 \\ 0 & 0 \end{array}] [\begin{matrix} W^{T} \\ * \end{matrix}] .

$\mathbf{P} = \left[ \begin{array}{cc}\mathbf{V} & * \end{array} \right]\left[\begin{array}{cc}\mathrm{diag}(\mathbf{1}_{k}) & \mathbf{0} \\ \mathbf{0} & \mathbf{0}\end{array}\right]\left[\begin{array}{c} \mathbf{W}^{T} \\ *\end{array}\right].$

Матрицы, скрытые звездами, имеют значение для других вещей (например, для оценки ошибки и т. Д.), Но пока мы будем избегать посторонних деталей. Это следует из того

P = {V W}^{T}

$\mathbf{P} = \mathbf{VW}^{T}$

является полным рангом разложение . $\mathbf{P}$

По сути, вы решите систему

P A x = P b

$\mathbf{PAx} = \mathbf{Pb}$

в умном способе, так как и также имеет свойство , что . Умножение обеих сторон $\mathbf{V}$ $\mathbf{W}$ $\mathbf{W}^{T}\mathbf{V} = \mathbf{I}$ от и позволяя $\mathbf{PAx} = \mathbf{Pb}$ $\mathbf{W}^{T}$ $\mathbf{y} = \mathbf{V}\widehat{\mathbf{x}}$ быть приближение для выходов $\mathbf{x}$

W^{T} A \hat{x} = W^{T} b .

$\mathbf{W}^{T}\mathbf{A}\widehat{\mathbf{x}} = \mathbf{W}^{T}\mathbf{b}.$

Решите для , предварительного умножения его на , и у вас есть , ваше приближение для $\widehat{\mathbf{x}}$ $\mathbf{V}$ $\mathbf{y}$ $\mathbf{x}$ .

Почему метод дополнения Шура, вероятно, лучше

Для начала, вы должны выбрать как-то. Если решение находится в , то $\mathbf{P}$ $\mathbf{Ax} = \mathbf{b}$ $\mathcal{R}(\mathbf{P})$ , а не является приближением. В противном случае , и вы вводите некоторую ошибку аппроксимации. Этот подход на самом деле не использует всю структуру, которую вы упомянули, желая использовать. Если мы выберем , чтобы его диапазон был стандартной единицей измерения в координатах вы хотите вычислить, соответствующие координаты будут содержать ошибки. Непонятно, как вы хотите выбрать $\mathbf{y} = \mathbf{x}$ $\mathbf{y}$ $\mathbf{y} \neq \mathbf{x}$ $\mathbf{P}$ $\mathbf{x}$ $\mathbf{y}$ . Вы могли бы использовать SVD $\mathbf{P}$ $\mathbf{A}$ , например, и выбрать как произведение первых левых сингулярных векторов и присоединения первых правых сингулярных векторов , предполагая, что сингулярные векторы расположены в убывающем порядке единственное значение. Этот выбор проектора был бы эквивалентен выполнению правильного ортогонального разложения на , и это минимизировало бы ошибку L в приближенном решении. $\mathbf{P}$ $k$ $\mathbf{A}$ $k$ $\mathbf{A}$ $\mathbf{A}$ $_{2}$

В дополнении к внедрению ошибки аппроксимации, этот подход также вводит три дополнительных матричные умножает на верхней часть линейного решения меньшей системы и работы , необходимую для вычисления , и . Если вы не решаете одну и ту же линейную систему много, меняя только правую сторону, и $\mathbf{V}$ $\mathbf{W}$ $\mathbf{P}$ по-прежнему является «хорошей» проекционной матрицей для всех этих систем, эти дополнительные затраты, вероятно, сделают решение сокращенной системы более дорогим, чем решение вашей оригинальная система.

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

Джефф Оксберри
источник

4

Длинный ответ ... вроде.

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

Шаг 1. Выполните исключение Гаусса, чтобы матрица была верхней треугольной. Шаг 2: решить путем обратной замены только первого (последнего) $k$ переменных, которые вас интересуют

Это избавит вас от вычислительной сложности, связанной с необходимостью поиска последних переменных с помощью обратной подстановки, что может стоить того, если будет таким большим, как вы говорите. Имейте в виду, что для шага 1 еще предстоит проделать значительную работу. $n-k$ $n$

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

drjrm3
источник

O (n^{3})

$O(n^3)$

O (n^{2})

$O(n^2)$

n

$n$

вот почему ответ «вроде» вместо «да» =)

drjrm3

Имеет смысл, что это может быть сделано таким образом ... Однако основная часть вычислений в исключении Гаусса находится в фазе прямого исключения, что приводит к сложности O (n ^ 3), несмотря на усеченную фазу обратной замены. Я надеялся, что был более быстрый метод ...

Пол