Господа!

Необходимо решить систему линейных уравнений, образующих плохо обусловленную матрицу, т.е. определитель близок к нулю.

Пытался решить методом Гаусса, но результат либо вообще не получается, либо получается очень неточный.

Слышал, что есть специальные алгоритмы для таких случаев. Видел ссылки на алгоритм Абрамова, Крейга, какие-то итерационные алгоритмы, но толком ничего не нашел .

Был бы признателен за любую инфу по данному вопросу.

Здравствуйте, Ignoramus, Вы писали:

I>Господа!

I>Необходимо решить систему линейных уравнений, образующих плохо обусловленную матрицу, т.е. определитель близок к нулю.

I>Пытался решить методом Гаусса, но результат либо вообще не получается, либо получается очень неточный.

I>Слышал, что есть специальные алгоритмы для таких случаев. Видел ссылки на алгоритм Абрамова, Крейга, какие-то итерационные алгоритмы, но толком ничего не нашел .

I>Был бы признателен за любую инфу по данному вопросу.

А точного решения у таких систем и быть не может. Если у вас есть уравнение Ax=b, где матрица A плохо обусловлена и вы начнете варьировать b, то вектор x начнет очень сильно дрожать в некоторых направлениях. Т.е., другими словами, множество | Ax-b |<epsilon будет представлять из себя эллипсоид, некоторые полуоси которого очень большие, а некоторые очень маленькие. Говорить о точности решения в этих условиях бессмысленно. Надо так или иначе уточнять задачу.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Шахтер, Вы писали:

Ш>А точного решения у таких систем и быть не может. Если у вас есть уравнение Ax=b, где матрица A плохо обусловлена и вы начнете варьировать b, то вектор x начнет очень сильно дрожать в некоторых направлениях. Т.е., другими словами, множество | Ax-b |<epsilon будет представлять из себя эллипсоид, некоторые полуоси которого очень большие, а некоторые очень маленькие. Говорить о точности решения в этих условиях бессмысленно. Надо так или иначе уточнять задачу.

Соглашусь с Вами лишь частично.

Насчет точного решения — очевидно, что если определитель матрицы не точный ноль, то формально точное решение существует. Например, для матрицы из одного элемента:

[ 1e-9 ] * x = [1]
x = 1e9

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

Другой вопрос, что это решение будет нестабильным, т.е. небольшие изменения b будут вызывать значительные изменения x. Тут Вы правы. Однако и в этом случае я бы не спешил выбрасывать решение. Дело в том, что иногда вариации b приводят к большой нестабильности не всех составляющих вектора x, а только некоторых, которые чудесным образом оказываются некритичными.

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

Проиллюстрирую сказанное примером, собственно откуда взялась моя задача

Нужно интерполировать функцию дробно-рациональной функцией вида y(x) = (a0 + a1 * x + a2 * x^2) / (1 + b1 * x + b2 * x^2). Заданы 5 точек (xi, yi), подставляя которые в y(x) получаем систему линейных уравнений относительно неизвестных коэффициентов (a0, a1, a2, b1, b2). В случае, если xi почти равно yi, иными словами y(x)~= x, а в моей задаче это часто встречающийся случай, получаем, что столбцы при а2 и b1 будут почти одинаковыми и определитель стремится к 0. Однако очевидно, что точное решение существует, а именно: a0 = 0, a1 = 1, a2 = 0, b1 = 0, b2 = 0, точнее a2 = b1 = любое число. Т.е. решение нестабильно по a2 = b1, т.к. одна из этих переменных становится свободной, однако ценность решения от этого не уменьшается.

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

Так что вопрос пока остается открытым. В сети я нашел довольно много упоминаний о решении плохообусловленных систем, в частности, итеративный метод Абрамса, метод градиента, однако не удалось найти внятного описания самих алгоритмов, только упоминания .

Здравствуйте, Ignoramus, Вы писали:

I>Здравствуйте, Шахтер, Вы писали:

Ш>>А точного решения у таких систем и быть не может. Если у вас есть уравнение Ax=b, где матрица A плохо обусловлена и вы начнете варьировать b, то вектор x начнет очень сильно дрожать в некоторых направлениях. Т.е., другими словами, множество | Ax-b |<epsilon будет представлять из себя эллипсоид, некоторые полуоси которого очень большие, а некоторые очень маленькие. Говорить о точности решения в этих условиях бессмысленно. Надо так или иначе уточнять задачу.

I>Соглашусь с Вами лишь частично.

I>Насчет точного решения — очевидно, что если определитель матрицы не точный ноль, то формально точное решение существует. Например, для матрицы из одного элемента:

I>[ 1e-9 ] * x = [1]
I>x = 1e9

I>Однако, при очень малых значениях определителя, количества разрядов не хватает для необходимой точности, при использовании обычных алгоритмов, так что даже погрешность при выполнении сложений и умножений уводит резальтат сколь угодно далеко от настоящего. Меня интересует, как перестроить алгоритм таким образом, чтобы хватало разрядов и погрешности не влияли. Мне кажется, это возможно

Проблема не в "малых" значениях определителя (малых — по сравнению с чем?). А в точности вычислений. А конкретнее в том, что при сложении (вычитании) некоторых элементов определителя получаются значения очень малые по сравнению с самими этими элементами. То есть происходит потеря точности.
Решения есть. Лобовое — увеличить разрядность плавающей точки. Но это долго и не весело.
Другое — использовать метод сортировки. То есть при выполнении таких операций как сложение и вычитание множества элементов, отсортировать эти элементы так, что бы минимизировать погрешность (и тем самым увеличить точность).

С Уважением, Андрей

Здравствуйте, AndreyFedotov, Вы писали:

AF>Проблема не в "малых" значениях определителя (малых — по сравнению с чем?). А в точности вычислений. А конкретнее в том, что при сложении (вычитании) некоторых элементов определителя получаются значения очень малые по сравнению с самими этими элементами. То есть происходит потеря точности.

Вот именно .

AF>Решения есть. Лобовое — увеличить разрядность плавающей точки. Но это долго и не весело.

Не будем.

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

А подробнее можно?

Здравствуйте, Ignoramus, Вы писали:

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

I>А подробнее можно?

Можно. Метод прост.
Допустим точность чисел — 2 разряда и складываются:
30 + 0.4 + 80 + 1.4 = 91.8
Что получится?
30 + 0.4 = 30
30 + 60 = 90
90 + 1.4 = 91 (два разряда)
Ошибка 0.8

Теперь отсортируем числа так, что бы операция шла над наиболее близкими числами:
0.4 + 1.4 + 30 + 80 = 91.8
0.4 + 1.4 = 1.8
1.8 + 30 = 32
32 + 60 = 92
Ошибка 0.2

Другой пример.
Пусть 100 раз складывается 0.2 с той же точностью — 2 разряда.
Результат?
10, если складывать как обычно, а не 20, как следовало бы ожидать...
Почему?
9.8 + 0.2 = 10.0
10.0 + 0.2 = 10.0
....

Теперь, если воспользоваться технологией сложения ближайших чисел:
50 сложений:
0.2 + 0.2 = 0.4
25 сложений:
0.4 + 0.4 = 0.8
12 сложений:
0.8 + 0.8 = 1.6
и одно:
0.8 + 0.4 = 1.2
...

А теперь главный вопрос. Ты определитель для решения системы уравнений вычисляешь?

С Уважением, Андрей

Здравствуйте, Аноним, Вы писали:

А>Теперь, если воспользоваться технологией сложения ближайших чисел:
А>50 сложений:
А>0.2 + 0.2 = 0.4
А>25 сложений:
А>0.4 + 0.4 = 0.8
А>12 сложений:
А>0.8 + 0.8 = 1.6
А>и одно:
А>0.8 + 0.4 = 1.2
А>...

Мне кажется это не поможет, если речь идет о сравнении чисел, например, 1.23456789012345е15 и 1.23456789012345е0.

А>А теперь главный вопрос. Ты определитель для решения системы уравнений вычисляешь?

Боже упаси! (Хотя с меня сталось бы ). Я использую метод исключения Гаусса.

Я тут нашел прикольный рецепт в Numerical Recipes C. Оказывается матрица подобная моей имеет специальное название — матрица Вандермонда, и она часто бывает плохо обусловленная. Поэтому рекомендуется для полиномиальной/рациональной интерполяции функции по точкам не искать коэффициенты полиномов через эту матрицу, а вычислять значение полинома непосредственно, через алгоритм Невиля, тогда коэффициенты вычисляются в неявной форме, и плохая обусловленность проходит мимо.

Вот так Так что прав был Шахтер, когда говорил, что нужно переформулировать задачу .

Здравствуйте, Ignoramus, Вы писали:

I>Господа!

I>Необходимо решить систему линейных уравнений, образующих плохо обусловленную матрицу, т.е. определитель близок к нулю.

Где-то я читал такой метод:

Допустим, у нас есть система:

Ax=B

Решаем ее, получаем значения x1. Потом вычисляем значения B1 и определяем разность B-B1.

Решаем систему второй раз, уже для B-B1:

Ax=B-B1

Получаем поправку, которую потом добавляем к x1 и получаем x2. Повторяем до тех пор, пока поправки не станут маленькими.

Здравствуйте, Socrat, Вы писали:

S>Где-то я читал такой метод:

S>Допустим, у нас есть система:

S>Ax=B

S>Решаем ее, получаем значения x1.
S>Потом вычисляем значения B1 и определяем разность B-B1.

S>Решаем систему второй раз, уже для B-B1:

S>Ax=B-B1

S>Получаем поправку, которую потом добавляем к x1 и получаем x2. Повторяем до тех пор, пока поправки не станут маленькими.

А если не станут?

Здравствуйте, Шахтер, Вы писали:


I>>Необходимо решить систему линейных уравнений, образующих плохо обусловленную матрицу, т.е. определитель близок к нулю.

I>>Слышал, что есть специальные алгоритмы для таких случаев. Видел ссылки на алгоритм Абрамова, Крейга, какие-то итерационные алгоритмы, но толком ничего не нашел .

Ш>А точного решения у таких систем и быть не может.


Ага. Щаз.

Вот простой пример

X/10001 — Y = 0
X/10001 + Y/10000 = 1

Заменяя 10001 на 100000001, 1000...0000001 итд,
а 10000 на соответственно то же самое -1
можно получить определитель матрицы сколь угодно
близким к 0. Тем не менее, решение всегда есть.

Прежде всего, с точки зрения строгой математики, плохо определенных
систем не бывает вообще. Как не бывает больших и маленьких чисел.
Бывают : системы, плохо определенные с точки зрения выбранного
представления чисел; с точки зрения выбранного алгоритма.

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

Во втором — можно использовать итерационные алгоритмы.
Вообще по этому поводу имеет смысл посмотреть книгу Голуба и Ван Лоуна
Матричные вычисления. Там много на эту тему.

Здравствуйте, Ignoramus, Вы писали:

I>Необходимо решить систему линейных уравнений, образующих плохо обусловленную матрицу, т.е. определитель близок к нулю.

I>Пытался решить методом Гаусса, но результат либо вообще не получается, либо получается очень неточный.

I>Слышал, что есть специальные алгоритмы для таких случаев. Видел ссылки на алгоритм Абрамова, Крейга, какие-то итерационные алгоритмы, но толком ничего не нашел .

Можно воспользоваться методом регуляризации (Тихонова). Берешь априорную информацию (типа, вектор решения должен быть не очень большой), "добавляешь" к задаче и решаешь. Априорная информация берется из физ.смысла условий. Подробности см., например, в http://www.applmat.ru/comma/html/inverse/regular.html. Компьютерная томография так устроена.

Здравствуйте, Аноним, Вы писали:

А>Прежде всего, с точки зрения строгой математики, плохо определенных
А>систем не бывает вообще. Как не бывает больших и маленьких чисел.

Неверно. Плохо определнные системы — это такие, которые при малом изменении исходных данных (правой части, например) дают большое изменение решения. Типичный пример малого изменения исходных данных — погрешность вычислений, а в результате решение дребезжит.