Четыре числовых ряда

qimer · 15 Окт 2014

Четыре числовых ряда

есть 4 числовых ряда с N элементами каждый.
Пример:

Ряд1 57 -25 -74 -47 -73 16 41
Ряд2 -43 -81 90 -79 -73 32 -29
Ряд3 -71 -9 76 -50 34 52 -19
Ряд4 54 98 69 70 93 -31 14

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

(Basic, Pascal, C++)

qimer · 15 Окт 2014

Да, кстати.. Коэффициент для первого ряда принимаем за 1. А остальные коэффициент нужно подобрать в соответствии с условием задачи

Gruvi · 17 Окт 2014

Эххх.... А вы что-нибудь сами делали уже ?

qimer · 17 Окт 2014

Gruvi написал(а):
Эххх.... А вы что-нибудь сами делали уже ?

С математикой сложно. Если бы там была элементарщина, не спрашивал бы
Один математик мне написал как это решается математически, но разобрать эти иероглифы сложно.
Вот ссылка на решение: http: // xn---------wofcfaecydkcaaiblreklarvcgpbbehpd8bv9bi7cxk3a4nb2a3c.xn--p1ai/science/z141015-00.xml

Vladimir_S · 17 Окт 2014

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

Vladimir_S · 17 Окт 2014

qimer написал(а):
Вот ссылка на решение:

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

qimer · 17 Окт 2014

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

Vladimir_S · 17 Окт 2014

qimer написал(а):
Владимир, я наверное немного ошибся с постановкой задачи. Только щас понял. Два скрина во вложении. Для начала, я точно знаю, из этих рядов надо вычесть средние их числа. Только в таком случае получится сделать некое подобие канала (2-й рисунок), путем умножения рядов на коэффициенты. Надо получить в итоге самый "узкий канал" (ряд)

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

qimer · 18 Окт 2014

Vladimir_S написал(а):
Не, ну тогда я совсем ничего не понимаю. Вы уж изложите условие задачи максимально подробно и внятно.

Задание остается прежним, как и было изначально. Коэффициенты должны быть положительными и отличными от 0. Любому ряду даем коэфф. 1, а остальные подбираются так, чтобы элементы получившегося ряда (который является суммой этих рядов) находились в некоем минимальном диапазоне, т.е. фактически максимально были приближены к 0. По той ссылке задача была решена математически, а мне нужно, чтобы мне помогли перевести эту задачу в алгоритм, по которому я сам потом напишу программу

Vladimir_S · 19 Окт 2014

В общем, на текущий момент так.
Я рассмотрел аналитическое решение задачи по МНК. К сожалению, это решение не удовлетворило поставленному искусственному ограничению положительности коэффициентов, ибо один из них оказался-таки, сволочь, отрицательным. Тем не менее, я всё-таки решил выложить программу (на ТурбоПаскале) - мало ли, вдруг всё-таки пригодится.
Если же принять это дурацкое условие, то, во-первых, решать придется численно, во-вторых, требуется оговорить точность как самих коэффициентов, так и минимального "расстояния" до нуля, а в третьих - программа будет считать тройной цикл ужасно долго (если шаг задать хотя бы 0.01, а если еще меньше - то и вовсе до потери пульса). Аналитическое же решение проходит мгновенно и выдает истинный minimum minimorum, т.е. координаты направленной вниз "попы" четырехмерного параболоида.
Все пояснения по расчету - в приложенном вордовском файле.

Код:

Const
 M:Array[1..4,1..7] of Real=(( 57, -25, -74, -47, -73,  16,  41),
                             (-43, -81,  90, -79, -73,  32, -29),
                             (-71,  -9,  76, -50,  34,  52, -19),
                             ( 54,  98,  69,  70,  93, -31,  14));
 eps=0.00001;

type
 matr=array [1..3,1..3] of real;
 mas=array [1..3] of real;
var
 i,j,p:integer;
 b,x:mas;
 a:matr;

procedure Gauss(ag:matr; bg:mas; var xg:mas; Ng:integer);
 Var
  k,ig,jg:byte;
  m,s:real;
  blg:boolean;
  c:mas;
 begin
  for k:=1 to Ng-1 do
   begin
    if ABS(ag[k,k])<eps then
     begin
      ig:=k;
      blg:=false;
      repeat
       Inc(ig);
       if ABS(ag[ig,k])>eps then
        begin
         blg:=true;
         c:=ag[k];
         ag[k]:=ag[ig];
         ag[ig]:=c;
         s:=bg[k];
         bg[k]:=bg[ig];
         bg[ig]:=s;
        end;
      until blg;
     end;
    m:=ag[k,k];
    for jg:=k to Ng do
     ag[k,jg]:=ag[k,jg]/m;
    bg[k]:=bg[k]/m;
    for ig:=k+1 to Ng do
     if ABS(ag[ig,k])>eps then
      begin
       m:=ag[ig,k];
       for jg:=k to Ng do
        ag[ig,jg]:=ag[k,jg]-ag[ig,jg]/m;
       bg[ig]:=bg[k]-bg[ig]/m;
      end
     else
      ag[ig,k]:=0;
   end;
 xg[Ng]:=bg[Ng]/ag[Ng,Ng] ;
 for ig:=(Ng-1) downto 1 do
  begin
   s:=0;
   For jg:=ig+1 to Ng do
    s:=s+ag[ig,jg]*xg[jg] ;
   xg[ig]:=bg[ig]-s;
  end;
end;

Begin
 for i:=1 to 3 do
  begin
   for j:=1 to 3 do a[i,j]:=0;
   b[i]:=0;
  end;
 for i:=1 to 3 do
  for j:=1 to 3 do
   for p:=1 to 7 do
    a[i,j]:=a[i,j]+M[j+1,p]*M[i+1,p];
 for i:=1 to 3 do
  begin
   for p:=1 to 7 do b[i]:=b[i]+M[1,p]*M[i+1,p];
   b[i]:=-b[i];
  end;
 Gauss(a,b,x,3);

 writeln('C[1] =  1.00000');
 for i:=1 to 3 do
  writeln('C[',i+1,'] = ',x[i]:8:5);
 readln
End.

Результат:

Код:

C1 =  1.00000
C2 = -0.10954
C3 =  0.67048
C4 =  0.42719

qimer · 20 Окт 2014

Владимир, аплодирую стоя! Спасибо за Ваш труд! Реально разжевали математику! Прошу прощение за не верное условие задачи с только положительными коэффициентами. На самом деле, как я позже выяснил, это не существенный фактор. Не могли бы мы с вами обсудить тонкости этой задачи через скайп (если вас не затруднит)?

Vladimir_S · 20 Окт 2014

qimer написал(а):
Не могли бы мы с вами обсудить тонкости этой задачи через скайп (если вас не затруднит)?

Затруднит. Ввиду полного отсутствия скайпа. Так что уж давайте здесь.

qimer · 20 Окт 2014

Vladimir_S написал(а):
Затруднит. Ввиду полного отсутствия скайпа. Так что уж давайте здесь.

Хорошо.

Первое, что хотел уточнить относительно этого метода решения. Это самые оптимальные коэффициенты?
Второе. Как мне поменять код, чтобы кол-во рядов и их длину я задавал сам?
Правильно ли я понимаю, что надо 7 заменить на переменную длины, например lengh, а 3 заменить на кол-во рядов - 1, т.е. например n=4 и соответственно n-1?

qimer · 20 Окт 2014

И еще, имеет ли смысл решать задачу попеременно принимая за 1 коэффициент 1,2,...,n ряда?

Vladimir_S · 20 Окт 2014

qimer написал(а):
Первое, что хотел уточнить относительно этого метода решения. Это самые оптимальные коэффициенты?

По идее - да.

qimer написал(а):
Второе. Как мне поменять код, чтобы кол-во рядов и их длину я задавал сам? Правильно ли я понимаю, что надо 7 заменить на переменную длины, например lengh, а 3 заменить на кол-во рядов - 1, т.е. например n=4 и соответственно n-1?

Правильно. Только не перепутайте параметры исходной матрицы и матрицы системы уравнений для коэффициентов.

qimer написал(а):
И еще, имеет ли смысл решать задачу попеременно принимая за 1 коэффициент 1,2,...,n ряда?

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

qimer · 20 Окт 2014

Vladimir_S написал(а):
Только не перепутайте параметры исходной матрицы и матрицы системы уравнений для коэффициентов.

Вы меня, конечно, извините, но не могли бы вы наглядно показать что исправить, а то я точно запутаюсь. Т.к. тут где-то массив, а где-то матрица. Не понятно где надо 3 оставлять, а где заменять на переменную

Vladimir_S · 20 Окт 2014

qimer написал(а):
Вы меня, конечно, извините, но не могли бы вы наглядно показать что исправить, а то я точно запутаюсь. Т.к. тут где-то массив, а где-то матрица. Не понятно где надо 3 оставлять, а где заменять на переменную

Хорошо, посмотрю. Но не прямо сейчас.

Vladimir_S · 20 Окт 2014

Нарисовал вариантик программы. Изменения:
1. Введены (константами) число строк (Nl) и столбцов (Nc) исходной матрицы. Явные тройки и семерки убраны.
2. Вычисляются суммы квадратов отклонений от нуля при:
а) простом суммировании рядов, т.е. когда все коэффициенты равны 1;
б) после нахождения минимизирующих коэффициентов;
в) после нахождения минимизирующих коэффициентов при обмене местами первой и второй строк, т.е. когда второй массив становится "базовым", а первый занимает его место. Как показал расчет, результат при этом меняется, так что, возможно, есть смысл еще и перебрать массивы, поочередно каждый из них делая "базовым".
Осталось только организовать ввод массивов из файла или с клавиатуры, ну это уж Вы сами. У меня для тестирования массив задан в виде константы, что, конечно, в универсальной программе не годится.

Код:

Const
 Nl=4;
 Nc=7;

Type
 matr=array [1..Nl-1,1..Nl-1] of real;
 matr_S=array [1..Nl,1..Nc] of real;
 mas=array [1..Nl-1] of real;
 vect=array [1..Nl] of real;

Const
 M1:Matr_S=(( 57, -25, -74, -47, -73,  16,  41),
            (-43, -81,  90, -79, -73,  32, -29),
            (-71,  -9,  76, -50,  34,  52, -19),
            ( 54,  98,  69,  70,  93, -31,  14));
 eps=0.00001;

Var
 M:Matr_S;
 i,j,p:integer;
 b,x:mas;
 C:vect;
 a:matr;
 Dummy:real;

function Sum(MS:Matr_S;CS:vect):real;
var
 f,g:integer;
 SS,SL:real;
begin
 SS:=0;
 for g:=1 to Nc do
  begin
   SL:=0;
   for f:=1 to Nl do SL:=SL+CS[f]*MS[f,g];
   SS:=SS+Sqr(SL);
  end;
 Sum:=SS;
end;

procedure Gauss(ag:matr; bg:mas; var xg:mas; Ng:integer);
 Var
  k,ig,jg:byte;
  m,s:real;
  blg:boolean;
  c:mas;
 begin
  for k:=1 to Ng-1 do
   begin
    if ABS(ag[k,k])<eps then
     begin
      ig:=k;
      blg:=false;
      repeat
       Inc(ig);
       if ABS(ag[ig,k])>eps then
        begin
         blg:=true;
         c:=ag[k];
         ag[k]:=ag[ig];
         ag[ig]:=c;
         s:=bg[k];
         bg[k]:=bg[ig];
         bg[ig]:=s;
        end;
      until blg;
     end;
    m:=ag[k,k];
    for jg:=k to Ng do
     ag[k,jg]:=ag[k,jg]/m;
    bg[k]:=bg[k]/m;
    for ig:=k+1 to Ng do
     if ABS(ag[ig,k])>eps then
      begin
       m:=ag[ig,k];
       for jg:=k to Ng do
        ag[ig,jg]:=ag[k,jg]-ag[ig,jg]/m;
       bg[ig]:=bg[k]-bg[ig]/m;
      end
     else
      ag[ig,k]:=0;
   end;
 xg[Ng]:=bg[Ng]/ag[Ng,Ng] ;
 for ig:=(Ng-1) downto 1 do
  begin
   s:=0;
   For jg:=ig+1 to Ng do
    s:=s+ag[ig,jg]*xg[jg] ;
   xg[ig]:=bg[ig]-s;
  end;
end;

Begin
 M:=M1;
 for i:=1 to Nl-1 do
  begin
   for j:=1 to Nl-1 do a[i,j]:=0;
   b[i]:=0;
  end;
 for i:=1 to Nl-1 do
  for j:=1 to Nl-1 do
   for p:=1 to Nc do
    a[i,j]:=a[i,j]+M[j+1,p]*M[i+1,p];
 for i:=1 to Nl-1 do
  begin
   for p:=1 to Nc do b[i]:=b[i]+M[1,p]*M[i+1,p];
   b[i]:=-b[i];
  end;

 for i:=1 to Nl do C[i]:=1;
 Writeln('Mean square sum with Ci=1 (i=1..4): ',Sum(M,C):0:3);
 Writeln;
 Gauss(a,b,x,Nl-1);
 Writeln('Result of calculation:');
 for i:=1 to Nl do
  begin
   if i>1 then C[i]:=x[i-1];
   writeln('C[',i,'] = ',C[i]:8:5);
  end;
 Writeln('Mean square sum with calculated Ci (i=1..4): ',Sum(M,C):0:3);
 Writeln;
 for j:=1 to Nc do
  begin
   Dummy:=M[1,j];
   M[1,j]:=M[2,j];
   M[2,j]:=Dummy;
  end;
 Writeln('After exchanging of first and second lines:');
 for i:=1 to Nl-1 do
  begin
   for j:=1 to Nl-1 do a[i,j]:=0;
   b[i]:=0;
  end;
 for i:=1 to Nl-1 do
  for j:=1 to Nl-1 do
   for p:=1 to Nc do
    a[i,j]:=a[i,j]+M[j+1,p]*M[i+1,p];
 for i:=1 to Nl-1 do
  begin
   for p:=1 to Nc do b[i]:=b[i]+M[1,p]*M[i+1,p];
   b[i]:=-b[i];
  end;
 Gauss(a,b,x,Nl-1);
 Writeln('Result of calculation:');
 for i:=1 to Nl do
  begin
   if i>1 then C[i]:=x[i-1];
   writeln('C[',i,'] = ',C[i]:8:5);
  end;
 Writeln('Mean square sum with calculated Ci (i=1..4): ',Sum(M,C):0:3);
 Readln
End.

qimer · 20 Окт 2014

Спасибо большое, Владимир!

qimer · 20 Окт 2014

И все-таки что-то не то. Ведь если мы ищем наименьшую сумму квадратов, то должен получиться лишь 1 набор коэффициентов. А как мы видим 2-е коэффициенты даже не пропорциональны первым.

Четыре числовых ряда

Новые

Новые

VIP user

Новые

Супермодераторы

Супермодераторы

Новые

Вложения

Супермодераторы

Новые

Супермодераторы

Вложения

Новые

Супермодераторы

Новые

Новые

Супермодераторы

Новые

Супермодераторы

Супермодераторы

Новые

Новые

Похожие темы