Вырожденность матриц

[Fgolm]

Рассмотрим СЛАУ:

$Cx = b$ (1)

$ C=\left\| {c_{ij} } \right\| = \left\{ \begin{array}{l} 1,\quad i = j \\ {{a_{ij} } \over {\Delta l_i }} ,\quad i \ne j, \end{array} \right. $ (2)
Здесь: $\Delta l_i $ - шаг дискретизации; $a_{ij} $ - вычисляемые по аналитическим формулам числа (пока рассматриваем чисто математическую проблему, игнорируя вопросы, связанные с округлением).
Каждую строку в (1) умножим на $\Delta l_i $ ($i$ - номер строки):

$ C'=\left\| {c'_{ij} } \right\| = \left\{ \begin{array}{l} \Delta l_i ,\quad i = j \\ a_{ij} ,\quad i \ne j, \end{array} \right. $ (3) (связь межу $C'$ и $C$ видна)

Установлено, что коэффициенты любой строки матрицы (3) представимы в виде следующей линейной комбинации:

$c'_{Ni} = \alpha \cdot \Delta l_i - \sum\limits_{s = 1}^{N - 1} {c'_{si} } $ (4)
(здесь в качестве такой «любой» строки рассмотрена последняя - $N$-я, для определенности).
$\alpha $ - постоянная.
Постоянная $\alpha $ не зависит ни от числа разбиений, ни от геометрии задачи. Однако, при изменении вводных негеометрических данных, можем менять ее значения в диапазоне [0;1].
1) Рассмотрим случай, когда $\alpha = 0$. Тогда, как видно из (4), матрица $C'$ становится вырожденной (последняя строка равна сумме предыдущих со знаком минус).
Матрица $C$ при этом также будет вырожденной. Однако линейная комбинация тут будет уже не просто сумма со знаком минус, а какой-то другой.
2) Рассмотрим, теперь случай, когда $\alpha \ne 0$, но мала (Здесь уже от чисто математической проблемы плавно переходим к вычислительной). Тогда матрица $C'$ становится почти вырожденной.
Вопрос в том будет ли при этом почти вырожденной и матрица $C$ ?

[незваный гость]

1) Конечно, другой. А в чем вопрос? Каковы коэффициенты?

2) $C$ будет столь же «почти вырождена», сколь и $C'$.

Я думаю, что у Вас очень неформальное определение «почти вырожденности.» Позвольте посоветовать Вам посмотреть понятие обусловленности матрицы. (Впрочем, для малых $\alpha$ Ваша матрица будет плохо обусловленной.)

[Fgolm]

Да, оно действительно неформальное.
Ситуация такая: «на бумаге» матрица получается вырожденной, а при численной реализации, почти ни один из методов даже не «замечает» эту вырожденность, и преспокойно такие СЛАУ решает.
Так, я подбирал параметры, определяющие величину постоянной $\alpha $, таким образом, что $\alpha $ должна быть равна нулю, и, тем не мене, СЛАУ решается (даже методом простой итерации). Т.е. тут сказывается округление.
Однако такому решению доверять нельзя. Необходимо каким-то образом от этой вырожденности уходить. Но, в принципе, меня ни это интересует.
А вот, как можно оценить предельно допустимую малость постоянной $\alpha $ ? С учетом, в том числе, погрешности вычислений. Т.е. при каких значениях $\alpha $ необходимо преобразовывать матрицу к невырожденной, а при каких – это не обязательно?
В качестве конкретного примера приведу первый столбец матрицы $C'$ размерностью $10 \times 10$:

 
 0.090000000000000000
-0.024102492197366990
-0.013143635552786980
 0.001587533293751220
-0.018502990899899650
 0.003179364449816860
 0.022938005590383900
-0.004319594276310640
-0.025092560629645450
-0.032363809593502330

Здесь, как видно: $\Delta l_1 = $ c_{11} $ = 0.09$, $\alpha = {1 \over {500.5}}$.
Как Вы оцениваете малось такой постоянной?

[Fgolm]

В приведенном примере последний элемент столбца отличается от разности предыдущих на величину:
$\alpha \cdot \Delta l_1 = {{0.09} \over {500.5}} = 1.798 \cdot 10^{ - 4} $, что составляеет 0.55% от него.
Шаг разбиения для матрицы размерностью $10 \times 10$ в данной задаче меняется от 0.03 до 0.09. Т.о. для других столбцов произведение $\alpha \cdot \Delta l_i$ еще меньше, чем для первого (по некоторым столбцам - совпадает).

[drob]

Fgolm писал(а):

Установлено, что коэффициенты любой строки матрицы (3) представимы в виде следующей линейной комбинации:

$c'_{Ni} = \alpha \cdot \Delta l_i - \sum\limits_{s = 1}^{N - 1} {c'_{si} } $ (4)
(здесь в качестве такой «любой» строки рассмотрена последняя - $N$-я, для определенности).
$\alpha $ - постоянная.
Постоянная $\alpha $ не зависит ни от числа разбиений, ни от геометрии задачи.

Я невижу здесь содержательного утверждения. То что вы написали эквивалентно $ \alpha \cdot \Delta l_i = \sum\limits_{s = 1}^{N } {c'_{si} } $ , тоесть сумма столбов чемуто равна

[Fgolm]

Это вопрос последовательности рассуждений:
$c'_{Ni} = f\left( {x,y} \right)$, при фиксированных параметрах $x$ и$y$. В свою очередь, оказалось, что $f\left( {x,y} \right) = \alpha \cdot \Delta l_i - \sum\limits_{s = 1}^{N - 1} {c'_{si} } $. Далее следует, что $\alpha \cdot \Delta l_i = \sum\limits_{s = 1}^N {c'_{si} } $.
Сути вопроса это не меняет.
А вопрос в основном состоит в том, как интерпретировать понятие вырожденности матрицы с т.з. вычислений на ЭВМ.

[drob]

Fgolm писал(а):

А вопрос в основном состоит в том, как интерпретировать понятие вырожденности матрицы с т.з. вычислений на ЭВМ.

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

Как мы знаем x86 обладает очень точной математикой. Результат всех операций отличается не больше чем на пол разряда, причем в сторону, которая оговорена стандартом. Если взять числа, помножить, поделить, вычесть или корень возвести в квадрат и т.п., то получим 0 примерно в половине случаев. А вот матрицами это не так. Если помножить на обратную матрицу, то вместо единичной матрицы мы получим значения где-то $10^{-13}$ в тех местах где должен быть 0, а 0 будет появляться в исключительных случаях. И никакие итерации здесь не помогают. Наверно это и есть половина какого-нибудь 50-го разряда.

Интересно рассмотреть умножение строки на $2^N$ , в том пределе насколько допускает порядок. Вроде бы ничего не изменилось, деление на $2^N$ восстанавливается исходное, но на выбор ведущего элемента это скажется.

Значит, рассматривать матрицу как двоичный код не совсем правомерено и нужно исходить из физики. Предполагать, что все элементы имеют одну физическую размерность, и епсилон это величина заведомо меньше точности исходных данных. У меня есть простой алгоритм обращения матриц, который и всем рекомендую.http://www.drobotenko.com/code_rus.html В общих чертах код выглядит так

for(k=0;k<N;k++)
 for(i=0;i<N;i++)
   for(j=0;j<N;j++)
     A[i][j]-=A[k][j]*vvv;

В тройном цикле из строки вычитается другая строка умноженная на число меньше 1. Еслибы это vvv было точное, то можно былобы говорить что точность N*исходная_точность , но vvv это отношение соответствующего к ведущему и если они малы, то vvv просто теряет смысл. Я попутно вычисляю детерминант. Интересно что если взять матрицу 300х300 близкую к диагональной и диагональные элементы будут значения около 10 (или 0.1) , то матрица прекрасно обратится, но детерминант выйдет за диапазон чисел с двойной точностью. Значит детерминант не может служить критерием вырожденности напрямую

[abc_qmost]

drob писал(а):

...У меня есть простой алгоритм обращения матриц, который и всем рекомендую...?

Все это (и не только) бред "сивой кобылы". Вы что-нибудь про сингулярный анализ знаете ?

[abc_qmost]

Fgolm писал(а):

Рассмотрим СЛАУ:
.....
.....

Советую почитать книгу авторов Дж. Форсайт, ... "Машинные методы математических вычислений" 1980 г (издательство "Мир"). Именно 1980 г., т.к. она переиздавалась в составе других авторов. И Форсайта там уже не было. А он - самая крупная фигура в компании авторов.

[Fgolm]

И что, там есть ответ на мой вопрос?
С чего Вы взяли, что я его не читал?

[abc_qmost]

Fgolm писал(а):

И что, там есть ответ на мой вопрос?
С чего Вы взяли, что я его не читал?

Из Вашего ответа "незваному гостю" я окончательно в этом утвердился.

[Fgolm]

А это не ответ. Это вопрос:

Fgolm писал(а):

Как Вы оцениваете малось такой постоянной?

Но я Форсайта почитаю, про вырожденные матрицы, может поможет.

[drob]

abc_qmost писал(а):

drob писал(а):

...У меня есть простой алгоритм обращения матриц, который и всем рекомендую...?

Все это (и не только) бред "сивой кобылы".

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

Цитата:

Вы что-нибудь про сингулярный анализ знаете ?

А Вы сами понимаете об чем говорите? Человек спрашивал про критерий вырожденности с т.з. вычислений на ЭВМ., а Вы ему про критерии в метрическом пространстве. Не поинтересовались в его случае одно имеет отношение к другому? Если у меня в уравнениях углы, расстояния, отсчеты АЦП, при этом точность данных определяется по разному, а для чегото определить вообще проблематично, то какая может быть норма? Или если хотите на пальцах - половина вектора в миллиардах , а половина в тысячных. Не использую я ортогонализацию - вычислений больше а оснований для этого какихто геометрических как правило нет. А погрешность вычислений можно определить и както попроще возьмите интервальную арифметику , например boost::interval и считайте

[abc_qmost]

drob писал(а):

abc_qmost писал(а):

drob писал(а):

...У меня есть простой алгоритм обращения матриц, который и всем рекомендую...?

Все это (и не только) бред "сивой кобылы".

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

Цитата:

Вы что-нибудь про сингулярный анализ знаете ?

А Вы сами понимаете об чем говорите? Человек спрашивал про критерий вырожденности с т.з. вычислений на ЭВМ., а Вы ему про критерии в метрическом пространстве. Не поинтересовались в его случае одно имеет отношение к другому? Если у меня в уравнениях углы, расстояния, отсчеты АЦП, при этом точность данных определяется по разному, а для чегото определить вообще проблематично, то какая может быть норма? Или если хотите на пальцах - половина вектора в миллиардах , а половина в тысячных. Не использую я ортогонализацию - вычислений больше а оснований для этого какихто геометрических как правило нет. А погрешность вычислений можно определить и както попроще возьмите интервальную арифметику , например boost::interval и считайте

К сожалению, более крепкие выражения к написанному Вами, чем я уже применил, не позволяют правила форума. Для начала почитайте книгу Дж. Форсайта "Машинные методы математических вычислений". Если справитесь, посоветую Вам более серьезную литературу.
Что касается интервальной арифметики, то я ее использую (пакет Intel MKL), но для задач совсем другого рода.

[drob]

abc_qmost писал(а):

Для начала почитайте книгу Дж. Форсайта "Машинные методы математических вычислений". .

И какой там ответ на поставленный вопрос? Если Вы думаете, что сингулярные числа помогают судить об обращаемости матрицы, то Вы ошибаетесь. Если взять диагональную матицу 2х2 со значениями 2^100 , 2^-200 , то судя по сингулярным числам ее вообще не стоит решать, хотя она решается с абсолютной точностью . Ваши советы воспользоваться сингулярным анализом, как я выше указал, ограниченной годности.

Дело в том что некоторые утверждения подходят действительные числа, кои являются математической абстракцией, местами под фиксированную точку, а местами под плавающую. Понять какая аксиоматика имеется ввиду действительно непросто. Но думаю Вам следует вернутся к упомянутой книге и перечитать ее более вдумчиво