Разложить матрицу (МНК)

[mbaitoff]

Пусть есть матрица довольно больших размеров, 500х500 к примеру, структура матрицы - ленточная, ширина ленты около 100. Внутри ленты - положительные числа, выражающие результат эксперимента, вне ленты - нули, которые означают, что эксперимент не производился. Предполагается, что числа внутри ленты "в целом" подчиняются следующему закону:

$$A_{ij} = S_i \cdot R_j \cdot X_{\left| {i - j} \right|} + N_{ij} $$

, то есть числа внутри ленты мультипликативно зависят от трех функций - функции номера столбца, номера строки, и "расстояния" между ними, плюс некая "шумовая" часть, не вписывающаяся в мультипликативную модель. Известно, что функции S и R ведут себя непредсказуемо, а X - быстро убывающая с увеличением расстояния.
Нужно найти законы S, R, X. Подскажите, к какому классу задач относится эта, и как ее решать.

Первый шаг сделан такой - зануляем шумовую часть, и, логарифмируя, переходим от произведений к суммам. А дальше?

[нг]

Метод наименьших квадратов. Должно работать с молодецким посвистом.

[mbaitoff]

нг писал(а):

Метод наименьших квадратов. Должно работать с молодецким посвистом.

не понял. что к чему приближать методом НК? то есть, минимизировать разность между чем и чем? я пока даже не представляю, как начальные приближения для S, R, X получить.

[нг]

Мы имеем семейство $A_{i,j}$, которые мы хотим приравнять к произведению. То есть, минимизировапть $\sum_{i,j}(\ln S_i + \ln R_j + \ln X_{|i-j|} - \ln A_{i, j})^2$. В качестве искомых переменных выступают $\ln S_i$, $\ln R_j$ и $\ln X_{|i-j|}$, каждой по $n$ штук. Размерность, конечно, большая, но матрица имеет удобную структуру.

[mbaitoff]

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

[PAV]

Логарифмируя обе части, получается линейный МНК. Посмотрите внимательно на формулу, которую привел нг.

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

Очевидно, что такое разложение не однозначно, поскольку мы можем всегда умножить все S (или R) на константу, поделив при этом X на константу. То есть, если в лоб, получим сингулярную систему. Поэтому полезно положить $\sum S_i = \sum R_j = 0$. Или $S_1 = R_1 = 1$.

[mbaitoff]

так, допустим, мы прологарифмировали входящие в произведение члены. получили сумму логарифмов. теперь минимизируем сумму квадратов разностей. вопрос - как? при минимизации (как я это делаю в экселе) для "наклона" и "засечки" существуют явные формулы. а здесь-то как быть?

да, разложение неоднозначное, по крайней мере с точностью до константы. пусть тогда X(0)=1.

[нг]

похоже, надо разбираться с МНК. Перемещаю в «Помогите…»

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

mbaitoff писал(а):

да, разложение неоднозначное, по крайней мере с точностью до константы. пусть тогда X(0)=1.

Это хорошо, но мало. У Вас две лишних степени свободы, Вы зафиксировали пока одну. И я не уверен, что Вы выбрали лучший способ. Мне кажется (с вычислительной точки зрения), суммы удобнее.

mbaitoff писал(а):

вопрос - как?

Как обычно. Берёте производную по переменной и приравниваете её нулю. Ваши переменные — $s_i = \ln S_i$ и т.п. Вот по $s_i$ и дифференцируете.

Почитайте что-нибудь. Гугл в помощь Ваш случай прост до предела — все коэффициенты либо равны 0, либо 1.

И не вспоминайте про Excel. Он — не Богом данная сущность. Так, убыточное изделие редмондского завода ширпотреба от программирования. И в него вбиты те же формулы, что нужны Вам, только в простом варианте.

[mbaitoff]

незваный гость писал(а):

:evil:

mbaitoff писал(а):

да, разложение неоднозначное, по крайней мере с точностью до константы. пусть тогда X(0)=1.

Это хорошо, но мало. У Вас две лишних степени свободы, Вы зафиксировали пока одну. И я не уверен, что Вы выбрали лучший способ. Мне кажется (с вычислительной точки зрения), суммы удобнее.

фиксировать суммы непригодно с точки зрения физического смысла проводимых экспериментов. пусть тогда S(1)=R(1)=1.

Цитата:

mbaitoff писал(а):

вопрос - как?

Как обычно. Берёте производную по переменной и приравниваете её нулю. Ваши переменные — $s_i = \ln S_i$ и т.п. Вот по $s_i$ и дифференцируете.

Почитайте что-нибудь. Гугл в помощь Ваш случай прост до предела — все коэффициенты либо равны 0, либо 1.

не согласен. ведь есть же возможность взять произвольные S(i), R(j), X(.) и при этом обратное разложение полученной матрицы А никак не должно давать нули и единицы. к тому же, как использовать факт того, что X(.) - быстро убывающая?

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

mbaitoff писал(а):

фиксировать суммы непригодно с точки зрения физического смысла проводимых экспериментов. пусть тогда S(1)=R(1)=1.

Это абсолютно пофигительно. Что Вы не зафиксируете, все результаты получатся пропорциональны.

mbaitoff писал(а):

не согласен.

Вы бы лучше воспользовались советом и почитали бы что-нибудь про МНК. А то Ваши рассуждения непонятно к чему относятся. (Или Вас смущает, что переменные называются $s_i$, а не $x_i$?)

[mbaitoff]

хорошо, начинаю минимизировать функцию

\[ U = \sum\limits_{ij} {\left( {s_i + r_i + x_{ij} - a_{ij} } \right)} ^2 \]

дифференцирую по каждому из

\[ s_i \]

, получаю

\[ \frac{{\partial U}} {{\partial s_i }} = 2Ms_i + 2\sum\limits_{j = 1}^M {\left( {r_j + x_{ij} - a_{ij} } \right)} \]

, дифференцирую по каждому из

\[ r_j \]

, получаю

\[ \frac{{\partial U}} {{\partial r_j }} = 2Nr_j + 2\sum\limits_{i = 1}^N {\left( {s_i + x_{ij} - a_{ij} } \right)} \]

, дифференцируя по

\[ x_{ij} \]

получаю

\[ \frac{{\partial U}} {{\partial x_{ij} }} = 2MNx_{ij} + 2\sum\limits_{ij}^{N,M} {\left( {s_i + r_j - a_{ij} } \right)} \]

.
если экстремум достигается, тогда все эти производные равны нулю (или многомерном случае это не так выражается?). допустим, приравняв к нулю, я выразил все s_i, r_j, x_{ij}, но что мне это дает? все они по-прежнему зависят друг от друга.

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

Во-первых, у Вас не $x_{i,j}$, а $x_{|i-j|}$. Соответственно, производную по $x$ Вы подсчитали неправильно. (Иначе Вы можете выбрать произвольные $S_i$, $R_j$, и положить $X_{i,j} = \frac{A_{i,j}}{S_iR_j}$.

Во-вторых, Вам не напоминает то, что у Вас получилось, систему линейных уравнений? Если Вы нормализуете на $\sum s_i =0$, $\sum r_j = 0$, она ещё более упростится: $ \frac{{\partial U}} {{\partial s_i }} = 2Ms_i + 2\sum\limits_{j = 1}^M {\left( {x_{|i-j|} - a_{ij} } \right)} $, $ \frac{{\partial U}} {{\partial r_j }} = 2Nr_j + 2\sum\limits_{i = 1}^N {\left( { x_{|i-j|} - a_{ij} } \right)} $

Добавлено спустя 6 минут 45 секунд:

mbaitoff писал(а):

опустим, приравняв к нулю, я выразил все s_i, r_j, x_{ij}, но что мне это дает? все они по-прежнему зависят друг от друга.

Что значит «я выразил»? Если Вы решили систему уравнений, Вы нашли Ваш ответ.