Как распознать вырожденную матрицу?

По какому критерию можно достоверно установить, что матрица вырожденная?
По определению, матрица является вырожденной, если ее строки являются линейно зависимыми. Т.е. их линейная комбинация равна нулю.
Реально же, если посчитать эту линейную комбинацию, то из-за ошибки округления она будет ровняться не нулю, а какому-то числу. Обозначим его 'a'.
Вопрос в том, как оценить чему должна быть равна 'a', чтобы матрицу можно было назвать вырожденной?

Если хотя бы одно собственное число равно нулю

Или детерминант матрицы равен нулю - если строки линейно зависимые, то можно сделать одну строку нулевой и по ней считать дискриминант.

Так разве это не усложнит задачу?
Пока посчитаешь это собственное значение... Одна головная боль.
Просто возникает вопрос зачем искать с.з., если проще посчитать линейную комбинацию строк.
А с определителем вообще не ясно. Допустим получил я определитель порядка 10^-20. И что из этого следует?
У Extended, например, пределы составляют: 3.6 x 10^-4951 .. 1.1 x 10^4932. Число 10^-20 на много больше, чем 10^-4951. Значит это не ноль.

Цитата Telc @ 31.05.07, 08:26

Пока посчитаешь это собственное значение... Одна головная боль.

Фактически утверждения "детерминант равен нулю" и "имеется нулевое собственное значения" эквивалентны

Цитата Telc @ 31.05.07, 08:26

А с определителем вообще не ясно. Допустим получил я определитель порядка 10^-20. И что из этого следует?

Это уже вычислительный вопрос, как бы ты не определял независимость строк все равно проблемы с точностью могут возникнуть.

Telc, обычно в задаче должна указываеться точность, с которой ведуться подсчеты.

Цитата Swindler @ 31.05.07, 07:45

Или детерминант матрицы равен нулю - если строки линейно зависимые, то можно сделать одну строку нулевой и по ней считать дискриминант.

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

Лучшая мера близости матрицы к вырожденной - это число обусловленности. Если оно по своей величине близко к 1/epsilon (где epsilon - машинная точность, около 1E-16 для типа double) или больше, то матрицу можно считать вырожденной. Более подробно об этом можно посмореть http://alglib.sources.ru/matrixops/general/svd.php и http://alglib.sources.ru/matrixops/general/rcond.php

Сообщение отредактировано: shadeofgray - 31.05.07, 10:17

Ну да, можно и так

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

Цитата Swindler @ 31.05.07, 08:37

Telc, обычно в задаче должна указываеться точность, с которой ведуться подсчеты.

Все переменные, которые учавствуют в вычисленеии коэффициентов матрицы - элементы массива, заданы в типе Extended.

Дело в том, что задача исследования матрицы на собственные значения или число обусловленности носит обобщенный характер. Ее предназначение - исследовать любую заданную матрицу. То есть, берется матрица о которой ничего не известно и по числу обусловленности мы судим о ее свойствах.
У меня же более узкая задача.
Берется вырожденная матрица (вырожденная на бумаге). Известна линейная комбинация строк, которая должна быть равна нулю. Но при численной реализации она нулю не рана. За счет округления.
Поэтому я повторяю вопрос: как оценить чему должна быть равна эта линейная комбинация, чтобы матрицу можно было назвать вырожденной?
Можно ответить так: если линейная комбинация строк по порядку равна численному нулю, значит матрица вырожденная. Можно обозначить это так: Апороговая=10^-18 (допустим 10^-18 - это численный ноль).
Но меня беспокоит следующее: ведь
1) коэффициенты матрицы вычисляются с некоторой погрешностью
2) упомянутая линейная комбинация строк тоже вычисляется с погрешностью
3) имеются еще каке-нибудь там погрешности
Если учесть все эти погрешности не получится ли так, что эта Апороговая как-то изменится? Например станет больше чем 10^-18 .

Цитата Telc @ 31.05.07, 13:02

Поэтому я повторяю вопрос: как оценить чему должна быть равна эта линейная комбинация, чтобы матрицу можно было назвать вырожденной?

Я думаю, можно задать границу так: (максимальный элемент строках)*(количество строк в наборе)*10*epsilon (здесь epsilon - машинная точность, десятка играет роль "страховочного" коэффициента). Если максимальный коэффициент линейной комбинации не превосходит этой границы, то можно считать, что она не отличается от 0. Это в отсутствие погрешностей в исходных данных.

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

Цитата shadeofgray @ 31.05.07, 13:45

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

Конечно лучше с учетом погрешности вычислений.
Но для начала, я толком-то не знаю как эти погрешности вычислить.
Я пишу на Delhi.
Коэффициенты матрицы вычисляются по аналитическим формулам (arctg(х) и ln(х) в основном).
В общем, если возможно, подскажите по вычислениям погрешности.

Если элементы матрицы числа с плавающей точкой, то, скорее всего, уже сама матрица задана с пограшностью, а, следовательно, нельзя определить, вырождена ли исходная матрица (точно также, как вы не можете отпределить равны ли два числа с плавающей точкой, их разность может быть и не равна нулю, хотя они сами могут быть формально равны, например, попробуйте посчитать какую-нибудь сумму, например, 100/n для n от 1 до 10000 --- один раз ничиная складивать сначала, а второй --- с конца. Вы получите разные результаты. При этом, кстати, более точным будет тот способ, у которого вначале складываются меньшие числа).

Я думаю, наиболее подходящий для вас метод --- вычислить определитель методом Гаусса (он даёт очень хорошую точность). При этом, перед каждой итерацией (вычитание какой-то строки из остальных с коэфициентом) выбирете строку так, чтобы её лидер (то есть первый ненулевой элемент, на который, собственно вы и будете делить) был наибольшем в столбце (из тех, которые можно выбрать). Это с одной стороны повышает точность (у меня получалось около трёх порядков), а с другой стороны, если этот наибольший лидер оказался маленьким (<1e-19), то можно с уверенностью (я думаю что порядок -19 это как раз то, что нужно) сказать, что матрица была вырождена. Невырожденность, как я уже говорил, установить невозможно (однако если у вас матрица с интами, или формальными выражениями, то всё упрощается и можно наверняка сказать, вырождена она, или нет. Тут на помощь снова приходит метод Гаусса, только <1e-19 надо заменить на =0), но если такая программа сказала, что матрица вырождена, то она, значит, либо вырождена, либо почти вырождена, то есть на самом деле почти наверняка вырождена.

И ещё несколько слов о точности. Если решать систему уравнений 1000x1000 методом Гаусса (так, как я скзазал, выбирая наибольшего лидера), с настоящим решением (1,1,1,....,1) и случайными коэффициентами (то есть они могут быть и очень большими), и, получив решение, вычислить сумму квадратов ражностей этого решения с настоящим, то у меня получалось 1e-22 (время работы --- 4 сек.), при этом, если не производить выбор наибольшего лидера, то эта оценка возрастает до 1e-19. Я думаю, что из этого, наверное, следует, что уж диагональные элементы, точно вычисляются с точностью, не меньше 1e-19 (и даже, почти наверняка 1e-22 или 1e-23).

Сообщение отредактировано: d06osipov - 04.06.07, 04:43