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

Я хочу знать , какие из классических линейных решателей (например , Гаусс-Зейделя, Jacobi, SOR) гарантированно сходятся для задачи , где положительно полу определена и, конечно $Ax=b$ $A$ $b \in im(A)$

(Примечание является полуопределенным и не определенным) $A$

linear-algebra iterative-method convergence linear-solver olamundo
источник

Вы имеете в виду положительные полуопределенные матрицы?

Meawoppl

Какой смысл решать линейную систему с такой матрицей? Если я не ошибаюсь, если ваша положительная полуопределенная матрица неособа, то она просто положительно определена.

фалейчик

Да, я уверен. Я должен освежить свою память относительно фактического доказательства, но согласно тому, что вы говорили, - если знаменатель в расчете равен нулю, это означает, что равен нулю, что означает, что все «направления поиска», в которых A не единственное число было исчерпано, и остаток, который вы оставили в не в пределах A (и, следовательно, это «оптимальное» решение). В случае, если на самом деле , этого не произойдет, так как остаток достигнет нуля как раз перед первым временем

α

$\alpha$

A P_{k}

$A P_k$

b \in s p a n (A)

$b \in span(A)$

A P_{k} = 0

$AP_k=0$

olamundo

Установите . Тогда . CG будет сходиться из-за для всех . Другими словами, вы никогда не оставляете для которого , положительно определен.

x_{0} = b

$x_0=b$

A^{n} b \in I m (A)

$A^nb\in Im(A)$

x_{n}^{*} A x_{n} > 0

$x_n^\ast Ax_n> 0$

0 \neq x_{n} \in I m (A)

$0\ne x_n\in Im(A)$

I m (A)

$Im(A)$

A

$A$

Смертельное дыхание

@faleichik: матрицы пониженной плотности в квантовой механике во многих случаях положительны полуопределены.

Смертельное дыхание

Ответы:

Алгоритм сопряженного градиента работает для полуопределенных задач и дает минимальное решение нормы.

Арнольд Ноймайер
источник

Спасибо. Любая идея об "архаичных" решателях, например, SOR Gauss-Seidel и т. Д.

olamundo

Они почти никогда не используются, и я не знаю, как они себя ведут.

Арнольд Ноймайер

Чтобы уточнить: CG, безусловно, не работает в ванильной форме для полуопределенных матриц; это может сработать в теории, если B по образу A; но это вряд ли хорошо закончится в численной практике. Очень похожие MINRES на основе Крылова - намного лучший выбор здесь. Кроме того, эти «архаичные» решатели широко используются в решателях многосеточного типа, чтобы назвать один пример.

Eelco Hoogendoorn

Вот доказательство того, что Гаусс-Зейделя соответствует вашим требованиям, учитывая , что в образе . $b$ $A$

То же самое очень не относится к Якоби; что стыдно, так как кто хочет беспокоиться о Gauss-Seidel на современном компьютерном оборудовании? Если ваша проблема может быть разбита на блоки по диагонали, вам повезло; Вы можете применять обновления Якоби к этим блокам инкрементным образом Гаусса-Зейделя и получать лучшее из обоих для таких полуопределенных задач.

Eelco Hoogendoorn
источник