Обусловленность СЛАУ

[Fgolm]

Имеются некие очевидно плохо обусловленные СЛАУ, с низкими определителями матриц коэффициентов. К примеру, определитель матрицы $A$, размерностью $m \times n = 100 \times 100$ составляет $\det \left( A \right) = 2,5 \cdot 10^{ - 1575} $. Многие сразу считают, что такие СЛАУ сингулярны, определитель $2,5 \cdot 10^{ - 1575} $ - это ноль. Тем не менее с помощью некоторых прямых методов удается решать такие СЛАУ. Просьба указать ссылки (если таковые имеются) на хорошие издания, в которых можно встретить работы (современные, т.е. такие, в ко-торых $2,5 \cdot 10^{ - 1575} $ – это не ноль), посвященные решению подобных СЛАУ. Мне это надо для того, чтобы в свою очередь иметь соответствующую ссылку (дескать этим кто-то занимался).

[Руст]

Формально то можно решить с любой точностью, например с помощью пакета математика. Но какой смысл придать решению, когда при незначительном изменении (0.0000000001) одного параметра в правой части, само решение меняется на 100000000000000. Если бы определитель был малым только из-за большей степени при равномерно малых собственных значениях такой ситуации не возникло бы. Определить равен произведению собственных значений. Максимальная ошибка порядка 1/l0, где l0 абсолютная величина минимального (в абсолютном )собственного значения. Так как в вашем случае среднее геометрическое абсолютных величин собственных значений порядка 10^{-16}, а минимальное скорее гораздо меньше, формальное решение не представляет никакого смысла.

[Fgolm]

Исследование матрицы на собственные значения, к сожалению, пока не реализовывалось. Тем не менее, на мой взгляд, решение упомянутых СЛАУ являются довольно устойчивыми (во всяком случае, на столько, на сколько можно утверждать это, не проводя детального исследования матрицы). Ну, во-первых изменяя элементы свободного члена на малую величину например 0,000001 решение изменилось менее чем на 1%. Во-вторых, что мне кажется самым важным, исследуемые СЛАУ имеют физический смысл: их решение описывает дискретное распределение источников поля. Но «истинное» распределение источников (то к которому должно стремиться решение СЛАУ с увеличением размерности) заранее известно (найдено другими методами или решено аналитически, когда это возможно). Так вот, решение этих СЛАУ с увеличением размерности (дискретизации поверхности, излучаемой поле) вполне естественно стремится к «истинному».

[worm2]

Fgolm, а может быть у Вас элементы матрицы маленькие? Если любой элемент по модулю не превышает $10^{-16}$, то, скорее всего, матрица не так уж плохо обусловлена. Умножаем её на $10^{16}$ и получим $\det(A) = 2.5 \cdot 10^{25}$ :)

То есть близость определителя к нулю ещё не означает плохой обусловленности. Руст правильно сказал, что надо бы попробовать оценить, насколько модуль максимального собственного значения больше модуля минимального. Это, конечно, сложновато. Можно вычислить обратную матрицу $C=A^{-1}$ и вычислить $N(C) = \max\limits_i \sum\limits_j |c_{ij}|$. Это будет неплохой оценкой устойчивости. Точнее, мы можем сказать, что абсолютная погрешность решения не будет превышать абсолютной погрешности вектора правой части, умноженной на N(C). Чтобы то же самое сказать про относительную погрешность, нужно найти аналогичное N для исходной матрицы A и умножить N(C)*N(A). Это, не вдаваясь в детали, и есть число обусловленности матрицы $\nu(A)$. Относительная погрешность решения не будет превосходить относительной погрешности правой части, умноженной на $\nu(A)$. Если $\nu(A)$ < 1000, то считается, что матрица хорошо обусловлена.

[Fgolm]

Особенность матрицы такова, что элементы в разных столбцах различны по порядку. В частности, элементы нечетных столбцов на несколько порядков превышают элементы в четных столбцах (при этом элементы в каждом столбце мало отличаются по порядку друг от друга). Таким образом, получается, что при достижении определенного размера матрицы некоторые столбцы (в основном четные) могут быть довольно сильно приближены к нулевым (нулем считается $10^{ - 18} $), в то время как элементы нечетных столбцов еще довольно "большие". Может в этом и причина малости определителя. И даже, если я умножу всю матрицу на большое число, соотношение между элементами не изменится.

Дело в том, что эти СЛАУ берут только прямые методы. Ни один итерационный метод не дает нормального ответа (или расходится вообще, или сходится крайне медленно (например один метод СЛАУ 10*10 решил за 2000000 итераци1 с невязкой 0,1%)). То есть это все равно косвенно говорит о плохой обусловленности (во всяком случае с прикладной точки зрения).

Я конечно же попытаюсь рассчитать число обусловленности. Если оно окажется «хорошим», тогда – все отлично, и дела мне не будет никакого до определителей. А если оно окажется «плохим»?

[worm2]

Тогда можно умножить каждый столбец на своё число $m_j$ так, чтобы его элементы по порядку были бы (например) около единицы. В результате определитель матрицы умножится на произведение всех $m_j$ (хотя зачем мне сдался этот определитель?). Может случиться, что систему с модифицированной таким образом матрицей решить проще (хотя число обусловленности у неё будет точно такое же, как и у исходной матрицы). А потом от решения этой системы легко перейти к решению исходной, разделив каждое $x_i$ на $m_i$.

Если число обусловленности окажется большим, то Вам, как минимум, нужно будет обеспечить, чтобы относительная погрешность элементов матрицы и правой части была бы не меньше желаемой относительной погрешности решения, делённой на $\nu(A)$. Кроме того, нужно будет вести вычисления с точностью, не менее чем на $\lceil \lg \nu(A) \rceil$ десятичных разрядов превосходящей желаемую точность результата. Например, если Вас устраивает точность 5 знаков после запятой, а число обусловленности равно $10^{32}$, то вычисления нужно вести с точностью минимум 37 знаков после запятой (на самом деле ещё больше, т.к. погрешность накапливается в ходе вычислений). Напомню, что тип float обеспечивает точность около 7 знаков после запятой, double --- 14-15, long double (x86) --- 18. Может статься, точности стандартных типов Вам не хватит, и тогда придётся пользоваться специальными библиотеками.

Добавлено спустя 23 минуты 50 секунд:

Fgolm писал(а):

Дело в том, что эти СЛАУ берут только прямые методы. Ни один итерационный метод не дает нормального ответа (или расходится вообще, или сходится крайне медленно (например один метод СЛАУ 10*10 решил за 2000000 итераци1 с невязкой 0,1%)). То есть это все равно косвенно говорит о плохой обусловленности (во всяком случае с прикладной точки зрения).

Большинству итерационных методов нужна ещё симметричность и положительная определённость матрицы. У Вас эти условия выполняются? Если нет --- то действительно, такие методы не подходят. Но вот обусловленность тут ни при чём. Эта характеристика матрицы не зависит от того, каким методом мы будем решать систему.

[Fgolm]

А Вы не могли бы указать где можно почитать об этом в большем объеме?

[worm2]

Это элементарные сведения из линейной алгебры и теории численных методов. Поэтому их можно почерпнуть практически из любого учебника по этим дисциплинам.
У меня поблизости оказалась лишь книжка:
Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. "Численные методы". М: --- Наука, 1987.
В ней целый параграф посвящён погрешности численных методов решения СЛАУ.

[Fgolm]

Я, ведь, тоже просмотрел ни одну такую книгу, в которых проводится целая куча каких-то оценок, а затем решается СЛАУ размерностью максимум 5*5. Мне все это не подходит. Я не математик, и все эти определители, числа обусловленности интересуют меня постольку-поскольку.
Мне не нужны общие сведения из курса вычислительной математики, это, в конце, концов, я и сам могу прочесть.
А вопрос задавался с единственной целью – вдруг кто-то когда-то сталкивался на практике с подобной проблемой (желательно кто-то из специалистов в этой области).
А те критерии, которые Вы указали для выбора точности расчетов мне показались сомнительными. Я решал с точностью 10 знаков, затем то же с точностью 18 и разницы нет.

[worm2]

Если у Вас нет проблем с решением такой системы прямыми методами --- что ж, замечательно. Тогда никакие теоретические оценки Вам, по большому счёту, и не нужны. Зачем мучаться и во что-то вникать, если и так всё отлично работает? Тем более, что приведённые Вами расчёты действительно свидетельствуют в пользу того, что Ваша матрица хорошо обусловлена.
А вот если это попытаться обосновать теоретически, то вряд ли можно придумать метод проще, чем я привёл. Всего и делов-то --- решить 100 систем с векторами (0, 0, ..., 0, 1, 0, ..., 0), из полученных решений-столбцов составить обратную матрицу, посчитать суммы модулей по строкам и найти из них максимальную.
Все остальные методы оценки числа обусловленности сложнее.

[Lyoha]

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

[Fgolm]

Единственную ссылку на Хаусхольдера, которую я встречал – это при описании метода сведения матрицы к треугольной (исключениями), основанного на использовании ортогональной матрицы отражения от n-1 мерной плоскости.
Вы этот метод имеете в виду?
Этот метод – один из тех методов которыми я решаю данные СЛАУ, а также рассчитываю определители их матриц.

[ГАЗ-67]

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

[ГАЗ-67]

Можно дать весьма точную нижнюю оценку для числа обусловленности .
Если обозначить число обусловленности через $\epsilon$ , то
$\epsilon\approx \max\limits_i {||a_i||}*\frac{||u||}{||v||}$ , где
u и v векторы такие , что $\frac{||u||}{||v||}\approx ||A^{-1}||$.

Для этого решаются две системы :
$A^{T}v=e$ ,
$Au=v$
$A^{T}$- транспонированная для $A$ , а e- вектор состоящий из $\pm 1$ выбираемый так чтобы обеспечить максим. рост при обратной подстановке для V , а $||a_i||$ -норма столбца матрицы $A$.
Хотелось бы заметить , что для сходимости итерационных методов не требуется симметричность и положительная определённость . Необходимо выполнение принципа сжимающих отображений применительно к СЛАУ . Данный
вопрос изложен в книге Колмогорова и Фомина по Ф.анализу.
Если у Вас есть желание , могу через пару-тройку дней шлёпнуть программу на BASIC'е и разъяснить принцип сж.отобр.

[Fgolm]

Буду Вам очень признателен!

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