ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   06 Jun 2002  10:40:18
 To : Michael Ryazanov
 Subject : Re: три прямых
 -------------------------------------------------------------------------------- 
 

 Wed Jun 05 2002 20:47, Michael Ryazanov wrote to Evgenij Masherov:
 
  
 
  DS>>> Есть набор точек. Считается, что через него можно провести три прямые:
  DS>>>                  /
  DS>>>                 /
  DS>>>                /
  DS>>>               /
  DS>>>     ,--------'
  DS>>>    /
  DS>>>   /
  DS>>>  /
  DS>>> /
  DS>>> (прощу прощения за корявую псевдографику; "плато" необязательно
  DS>>> горизонтальное).
  DS>>> Точек много, шаг по абсциссе не фиксирован.
  DS>>> Как "угадать", где кончается один и ноачинается другой участок?
  DS>>> (интуитивно понятно: проводим какую-либо прямую и смотрим, н-p,
  DS>>> хи-квадрат.
  DS>>> Hо что дальше?
  DS>>> М.б., есть критерии более подходящие в данном случае?)
  EM>>  Переходим ко вторым разностям
  EM>> y(i)=-y(i-1)+2*y(i)-y(i+1)
  EM>> Hа прямой они должны быть нулевыми, а в точке излома - нет.
  EM>> Hаходим два максимальных по абсолютному значению отсчета - они и дают
  EM>> соответствующие точки.
 
  MR>    Только он забыл сказать, что точки -- экспериментальные, потому могут
  MR> иметь какой угодно разброс (условие Липшица точно не выполняется :) ), и
  MR> разности сами по себе мало что скажут...
 
  Полагаю, что оценку разброса можно найти?
 Если он не столь велик, используем приведенный подход. Возможно, вместо
 простейшей аппроксимации второй производной используя полином второго порядка,
 проведенный методом наименьших квадратов по более чем трем точкам. 
 Скажем, аппроксимацию, приведенную у Ланцоша
 (4; 4; 1; -4; -10; -4; 1; 4; 4) - это коэффициенты при последовательных членах
 ряда.
 В противном случае алгоритм кубической по числу точек сложности:
 X1(i)=i
 X2(i)=(0| i<k; i-k| i>=k)
 X3(i)=(0| i<l; i-l| i>=l)
 Перебирая возможные пары k, l k<l
 строим возможные регрессии y на матрицу (X1|X2|X3)
 Там, где коэффициент корреляции (или что нравится) максимален - там угаданы
 точки перелома.
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    три прямых   Dmitry Syrkin   04 Jun 2002 08:07:00   три прямых   Evgenij Masherov   04 Jun 2002 11:01:28   Re: три прямых   Michael Ryazanov   05 Jun 2002 20:47:00   Re: три прямых   Evgenij Masherov   06 Jun 2002 10:40:18   Re: тpи пpямых   Vlad Bespalov   04 Jun 2002 12:48:42