Я намереваюсь решить Ax = b, где A - сложная, разреженная, несимметричная и крайне плохо обусловленная (номер условия ~ 1E + 20) квадратная или прямоугольная матрица. Я смог точно решить систему с ZGELSS в LAPACK. Но по мере того, как степени свободы в моей системе растут, требуется много времени для решения системы на ПК с ZGELSS, поскольку разреженность не используется. Недавно я попробовал SuperLU (используя хранилище Harwell-Boeing) для той же системы, но результаты были неточными для номера условия> 1E + 12 (я не уверен, что это числовая проблема с поворотом).
Я более склонен к использованию уже разработанных решателей. Есть ли надежный решатель, который может решить систему, о которой я говорил, быстро (т.е. использовать разреженность) и надежно (с учетом чисел условий)?
__float128Ответы:
Когда вы используете ZGELSS для решения этой проблемы, вы используете усеченное разложение по сингулярным значениям, чтобы упорядочить эту крайне плохо обусловленную проблему. важно понимать, что эта библиотечная процедура не пытается найти решение для методом наименьших квадратов , а скорее пытается сбалансировать поиск решения, которое минимизируетпротив минимизации,Ax=b ∥ х ∥ ∥ A x - b ∥
Обратите внимание, что параметр RCOND, переданный в ZGELSS, может использоваться для указания того, какие особые значения должны быть включены и исключены из расчета решения. Любое единственное значение, меньшее RCOND * S (1) (S (1) является наибольшим единственным значением), будет игнорироваться. Вы не сказали нам, как вы установили параметр RCOND в ZGELSS, и мы ничего не знаем об уровне шума коэффициентов в вашей матрице или в правой части , поэтому трудно сказать, использовали ли вы соответствующее количество регуляризации.A б
Вы, кажется, довольны регуляризованными решениями, которые вы получаете с ZGELSS, поэтому кажется, что регуляризация осуществляется с помощью усеченного метода SVD (который находит минимальное решение среди решений наименьших квадратов, которые минимизируют в пространстве решений, охватываемых сингулярными векторами, ассоциированными с сингулярными значениями, большими, чем RCOND * S (1)), удовлетворительно для вас.∥ х ∥ ∥ A x - b ∥
Ваш вопрос можно переформулировать так: «Как я могу эффективно получить регуляризованные решения методом наименьших квадратов для этой большой, разреженной и очень плохо обусловленной линейной задачи наименьших квадратов?»
Я рекомендую использовать итерационный метод (такой как CGLS или LSQR), чтобы минимизировать явную регуляризованную проблему наименьших квадратов
где параметр регуляризации настраивается так, чтобы проблема демпфированных наименьших квадратов была хорошо обусловлена и чтобы вы были довольны полученными регуляризованными решениями.α
источник
Джед Браун уже указывал на это в комментариях к вопросу, но на самом деле вы не очень много можете сделать с обычной двойной точностью, если число условий велико: в большинстве случаев вы, скорее всего, не получите ни единой цифры точности. ваше решение и, что еще хуже, вы не можете даже сказать, потому что вы не можете точно оценить остаток, соответствующий вашему вектору решения. Другими словами: вопрос не в том, какой линейный решатель вы должны выбрать - никакой линейный решатель не может сделать что-то полезное для таких матриц.
Подобные ситуации обычно случаются, потому что вы выбираете неподходящую основу. Например, вы получаете такие плохо обусловленные матрицы, если вы выбрали функции в качестве основы метода Галеркина. (Это приводит к матрице Гильберта, которая, как известно, плохо обусловлена.) Решение в таких случаях состоит не в том, чтобы спросить, какой решатель может решить линейную систему, а в том, есть ли лучшие базы, которые можно использовать. Я бы посоветовал вам сделать то же самое: подумайте о переформулировании вашей проблемы, чтобы вы не столкнулись с такого рода матрицами.1 , х ,Икс2,Икс3, . , ,
источник
Самый простой / быстрый способ решения плохо обусловленных задач - повысить точность вычислений (методом грубой силы). Другой (но не всегда возможный) способ - переформулировать вашу проблему.
Возможно, вам придется использовать четверную точность (34 десятичных знака). Даже если в курсе будет потеряно 20 цифр (из-за номера условия), вы все равно получите 14 правильных цифр.
Если это представляет какой-либо интерес, то теперь в MATLAB также доступны разреженные решатели четверной точности .
(Я автор упомянутого набора инструментов).
источник