Помогите придумать решение задачи.

Есть двумерный массив (или таблица) размера N * N
В каждой ячейке таблицы с координатами (индексами) X, Y записано значение Z
Нужно придумать алгоритм аппроксимации этого массива, чтобы можно было его заменить на простую двумерную функцию F(X, Y) которая возвращает Z

Важно!!!
1. Функция должна быть линейная во всех направлениях
2. Алгоритм должен быть ОЧЕНЬ простой, потому что рассчитываться он будет на компьютере, а мы с вами знаем на сколько прожорливое сейчас программное обеспечение до ресурсов. Поэтому если алгоритм будет сложный, но начнутся тормоза.

Какие есть идеи?

МНК. Чмы, второй курс.

Смотря какое применение будет в итоге. Я бы через нейронные сети прогнал бы )

(1)+ в 95м году считали на 386 на матлабе матрицы до 1000х1000. Вроде не тормозило.

(1) Вообще не годится. Медленно

(3) Сравнил или какие тогда были быстрые языки программирования (ассемблер) или какие сейчас (1С, макросы...).

(2) Зачем? Линейное же все по условию. Мне кажется решение должно быть очень простое.

(4) да на фортране считали, на СМ1420...
(5) решение и правда простое - см.(1)

(6) см (4)

хотя фраза "линейная во всех направлениях" - понравилась...

(8) Это необходимое условие

(0) А если в excel'е эти данные проанализировать, то линейность видно полученных значений? Почему линейная функция, а не полином?

(10) Потому что в итоге должна быть линейная. Если у значений нет линейности, значит ее все равно нужно сделать.

Я один не понял фразу "двумерной линейной функцией"?

Я знаю слов :
1. "функция первого порядка" и график еЯ - прямая.
2. "функция второго порядка" и график еЯ - кривая второго порядка (парабола, гипербола ...)
...
гармоническая функция
...

(11) ну тогда (конечное-начальное)/количество шагов - вот тебе и коэфициент

(12) ну ты что, про "семь красных линий" не слышал?

(12) Не только лишь все не поняли. Большинство поняли.

(13) Конечное и начальное могут быть случайными числами не отражающими общей тенденции

(15) зачем мэру линейная аппроксимация массива? он же в голову ест...

(16) тогда МНК для минимизации ошибки :-)

(12) Похоже это какое-то институтское задание для заочников с заведомо кривой постановкой, либо перевратое от непонимания. Двумерность в (0), скорее всего, имелось в виду про массив.

(0) Позабавило:
2. Алгоритм должен быть ОЧЕНЬ простой, потому что рассчитываться он будет на компьютере, а мы с вами знаем на сколько прожорливое сейчас программное обеспечение до ресурсов.

(18) Точно! Спасибо!

(19) Там так и написано вообще-то.

(22) там написано "двумерной линейной функцией", об этом сказано в (12). Линейная функция на то и линейная, потому что не двумерная :)

(18) МНК - функция ОДНОЙ переменной. А у ТСа - две.
Ему нужно получить коэффициенты для уравнения плоскости.

(23) У него функция двух переменных.
Это имелось ввиду.

(23) Ты наверное с одномерной спутал.

(24) МНК и для двух переменных можно применить, но сильно долго считает. Нужно ускорить

Напиши на чем-нибудь быстром.

(27) Какой размер матрицы? Порядок хотя бы?

(28) Медленное писать на быстром? А если быстрое написать на быстром будет ведь еще быстрее?

(30) напиши быстрое на быстром. кто мешает?

(24) ну так и минимизируется квадрат отклонений от плоскости.

(25) Я хз, кто чего имел ввиду, но мне в школе и ВУЗе преподавали линейную функцию такую: https://ru.wikipedia.org/wiki/Линейная_функция

(29) например 4096*4096 нужно сто матриц посчитать максимум за 1 секунду на слабом железе на чем-нибудь кросплатформенном (EcmaScript, Java)

(31) Хорошо. Только придумаю сначала алгоритм, и сразу напишу

Гугли уже. Скармливай ему матрицу-картинку грейскейлом, обратно получай жпег минимального качества, читай параметры самого крупного элемента жпега.

Кусочно-линейная или плоская? Картинку давай!

(34) "EcmaScript, Java"
А в Нью-Йорк на воздушном змее тебе слетать не надо?
Тут уж или крестик, или трусики. Т.е. или быстро, или кроссплатформено и универсально

(34) Видео надо на DSP распознавать, а не жаваскриптом.

(33) дык https://ru.wikipedia.org/wiki/Линейная_функция#.D0.9B.D0.B8.D0.BD.D0.B5.D0.B9.D0.BD.D0.B0.D1.8F_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D1.8F_.D0.BD.D0.B5.D1.81.D0.BA.D0.BE.D0.BB.D1.8C.D0.BA.D0.B8.D1.85_.D0.BF.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D0.BD.D0.BD.D1.8B.D1.85

(36) Как вариант можно. Спасибо за совет. Но не жпег конечно, а блур какой-нибудь применить, и получить градиент в итоге.
Не кусочно линейная. Просто линейная одним куском. Да плоская

(36) ну можно тупо выровнять уровни  методом сеток в  несколько итераций, и получим практически готовую линейную

(38) Не каждый юзер захочет себе покупать DSP

Вот тут http://www.delphikingdom.com/asp/viewitem.asp?catalogid=1368 , п.7 — готовый код на паскале.

(41) Щас посмотрю что это за метод сеток такой

(43) МНК уже кто-то предлагал, ты опоздал

(45) вообще-то, он как раз успел. ибо он и предлагал. см.(1)

4096*4096 даблов — это, на секундочку, 128 мегабайт.
На haskell алгоритм перепиши. Он как раз для таких случаев.

вообще для многомерных массивов применяют двухуровневые алгоритмы, типа "строй и перестраивай", "разделяй и властвуй" и подобное...

хотя я задачу нифига не понял, чего надо можешь простым языкам расписать?

Если пофиг на точность, а главное — скорость, то возьми произвольные три точки в матрице, не лежащие на одной прямой, и натяни на них плоскость.

(49) Если бы было пофиг на точность, он бы наверное уменьшил размерность для начала, не?

лет 10 натягивал на подобный массив 3д сеть, на 1с массив 10к * 10к считался около часа...

Самое интересное всегда - фактура задачи. Что за данные в матрице? И сколько их? - От этого будет зависеть метод.

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

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

http://www.cyberforum.ru/matlab/thread831030.html

(52) Можно разбить на куски и посчитать среднее арифметическое на каждом куске. Дальше решать задачу апроксимации на полученном массиве меньшей размерности.

Согласен, что самое интересное - информация о контексте, которая у нас отсутствует.

https://ru.wikipedia.org/wiki/Триангуляция_Делоне

оно? (только для 3х мерной сети)

Короче сам придумал решение пока спал. Точнее под утро, когда уже почти проснулся, и голова отдохнула.

Итак, разделяем таблицу вертикально на две равные части: левая и правая. Считаем среднее арифметическое для каждой половины. Получаем две точки с координатами x,y в центрах этих половин, z у них равен средним арифметическим. Уже можно построить прямую проходящую через 2 точки.

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

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

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

А точно прямые пересекаются?

(57) Да

(56) Скорее всего тут плоскость можно построить по паре-тройке сечений.

(56) И какое отношение это имеет к исходной задаче?
В МНК хоть понятно, что делается.
Я бы попробовал реализовать МНК, как положено (получится система линейных уравнений 3х3 (если F(x,y)=A*x+B*y+C), либо 2х2 (если F(x,y)=A*x+B*y)).
Решение самой системы не трудоемко: основное время уйдет на вычисление коэффициентов матрицы и значений правых частей (навскидку будет пропорционально числу точек (N^2)).
Если получится неприемлимо долго, можно попробовать "проредить" исходную матрицу (уменьшить размерность).

(56) или у тебя с точками какой то условия. Но в 56 ты строишь дичь)

(60) N^2 не вариант вообще
(61) таки почему дичь?

Если (56) не годится, то можно решать задачу влоб:

уравнение плоскости z = A*x + B*y + C

Если взять начало координат за центр таблицы, то плоскость будет проходить через точку 0, 0, Zсред. Zсред = среднее значение по всей таблице.
получается C = Zсред! Осталось найти А и В.
Из уравнения следует что Ax = z - By - C
там где y=0, A = (z - C) / x, то есть просто считаем среднее значение для всех точек по формуле (z - C) / x, находим А.
"В" находим по той же схеме: среднее от (z - C) / y
Так как матрица симметричная, "x" и "y" в диапазоне -N/2 .. N/2, то -C/x и -C/y сокращается, нужно будет считать только среднее от z, z/x и z/y. Это можно сделать за один проход по массиву

(62) конечно дичь, причем полная...

представь, в твою четверть попало 10 точек, из которых имеют значение от 9 до 10, и одна точка (дребезг измерения) имеет значение 10000, то есть у тебя будет средняя в районе 1000, хотя и дебилу понятно, что средняя должна быть где-то около 10...

я множество подобных алгоритмов перерешал и на практике внедрил... и знаю о чем говорю...

(62) Я тебе еще проще решение скажу: бери три случайные точки и натягивай на них плоскость. Тебе ж похер на точность.

(63) +

вот например мой проект с апрксимацией http://arduino.ru/forum/proekty/kontroller-mufelnoi-pechi

(63) То есть если например тебе платили 11 месяцев по 10 тысяч зарплату, и дали годовую премию 10 миллионов, то ты считаешь что в среднем зарабатываешь 10 тысяч в месяц? У тебя явно проблемы с математикой

(64) Вообще не годится.

(63) Попробуй реши свой пример по МНК, удивишься.

(66) я привел пример, что среднее далеко не всегда правильное решение...

пример есть ряд 8, 9, 8, 12, 10, 6, 50, 8, 10, 9

в моем примере (65) есть несколько путей решения
например: отбрасываем 10% самых= больших и 10% самых маленьких значений, остальное считам по среднему, х = (8+9+8+12+10+8+10+9) / 8 = 10.25

(69) +

или еще вариант, строишь гистограмму по точкам 8, 9, 8, 12, 10, 6, 50, 8, 10, 9

потом считаешь площадь фигуры и делишь на 10

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

(69) У тебя совсем другая задача. У меня случайные большие отклонения сильно ограничены, их можно не выискивать отдельно. И так как я считаю среднее арифметическое, а не квадратическое, то влияние выбросов еще меньше.

(0) Нормально так.
Постановка задачи (именно в том виде, в котором озвучена) - это пара разделов вышки на 4-5 курсе мехмата/вычмата.
Численные методы, разностные схемы, функциональный анализ - вот это все.

И вы хотите, чтоб вам за 5 минут накидали УНИВЕРСАЛЬНЫЙ алгоритм? Ничего так, что студентов целый семестр учат составлять разностные схемы под конкретные граничные условия? И даже к концу семестра студентов, понявший суть - пара человек со всего курса.

(60)+. Можно попробовать "усреднение":
- разбиваем исходную матрицу на блоки, скажем 16х16 блоков;
- в качестве "представителя" блока берем его центр тяжести (средние по x и y);
- применяем МНК к задаче 16х16.
Я бы попробовал, сравнивая отклонение для "усредненного" решения (для разного количества блоков) с отклонением для МНК в исходной задаче (4096х4096).

(72) то есть у Вас есть модель измерений и их погрешностей, которой Вы не делитесь, но применяете. Это чтобы ни кто не предложил решения? в (56) бред, возьмите (74), но перед усреднением обязательно надо заменить большие выбросы. т.е. два прохода 1 убираем выбросы на блоке 2 усредняем блок

(73) Универсальный алгоритм есть.
Это метод наименьших квадратов (МНК).
Его трудоемкость будет не намного больше, чем "самый простой метод", приведенный в (56).
Трудоемкость (56) также пропорциональна числу точек в матрице, как и МНК.
В МНК для этой задачи вычислений чуточку больше, но больше на некоторый постоянный коэффициент.
И такая же линейная (кажется) зависимость от числа точек (N^2) в матрице.

Что смущает в методе (56). Фактически он решает другую задачу. Задачу не линейной, а кусочно-линейной ("ступенчатой") аппроксимации.
То есть на плоскости определения функции определяюся четыре ступеньки (по числу квадрантов) и описанным методом определяется высота каждой ступеньки.
То есть для того, чтобы ошибка аппроксимации была минимальной, найденные параметры должны использоваться как высоты ступенек такой нелинейной функции.
Проводить через центры ступенек плоскость - значит увеличивать ошибку аппроксимации.

Проще всего это увидеть для случая функции одной переменной:
Вот такая функция v----^v----^ методом (56) будет аппроксимирована горизонтальной линией, а при использовании МНК - наклонной.
Вот такая функция -----^v-----
и такая           v----------^ методом (56) будет аппроксимирована одинаково, а МНК - по-разному.
Фактически, используя (56) мы игнорируем информацию о расположении точек внутри каждого квадрата,
из-за чего точность линейной аппроксимации неизбежно снижается.

Поэтому все же нужно поднапрячься и вывести не такие уж сложные формулы расчета коэффициентов А, B, С для этой задачи.
Кажется, это не сложнее, чем обоснование в (62).
Тогда же станет окончательно понятной вычислительная сложность.

На самом деле задача легко сводится к линейной.
А именно т.к. у нас всегда элементы в матрице нумеруются с 1 по N, то то можно взять ряд от 1 до N в квадрате и присвоить каждому элементу массива соотвествующий номер.
Итого имеем некоторую последовательность П(т) = Z(t)
Далее по МНК получаем, что нужно минимизировать сумму
(а*i+n*j+c - A(i,j))^2. Согласно МНК экстеремум функции достигается при первой производной равной нулю. Дифференцируем - получаем систему уравнений:
a*n*(2(n+1)^3+(n+1)-3(n+1)^2)/6 +b*n^2*(n+1)^2/4+n^2*c = Сумма по i от 1 до n i*(Сумма по j a(i,j))
b*n*(2(n+1)^3+(n+1)-3(n+1)^2)/6 +a*n^2*(n+1)^2/4+n^2*c = Сумма по j от 1 до n j*(Сумма по i a(i,j))
a*n^2*(n+1)/2 + b*n^2*(n+1)/2 + n^2*c = сумма всех элементов матрицы

Естественно такие уравнения получились потому, что в нашем случае x и y - это идентификаторы элементов матрицы.
Как видим - мы получили три уравнения с тремя неизвестными, в которых мы легко можем посчитать правую часть за один проход, причем просто суммированием элементов. Назовем эти суммы (сократив на n^2) соотвественно Среднее(i), Среднее(j) и просто среднее - получим три линейных уравнения , которые можно решить простыми вычислениями. Причем к-во уравнений не зависит от N

(76) (77) Для ТС это слишком сложно. МНК не помещается в его голове.

(78)  
- У тебя есть простой карандаш?
-- Есть синий!
- Не, мне нужен простой...
-- А что, синий для тебя слишком сложный???
©

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

(76) прикол еще в том, что отдельных при усреднениях по горизонтали и по вертикали мы получим минимум две прямых , котрые могут и не пересекаться.а при усреднении по  квадрантам - получим 4 точки, на которые совсем не обязательно ляжет плоскость

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

ТС хочет "линейную" функцию, по сути аппроксимация поверхности плоскостью.

https://toster.ru/q/87470

(82) ну, вообще, можно усреднять рекурсией, спускаясь по квадратм... по идее, тогда сложность будет меньше квадратичной... хотя и усреднение будет "другое"

(83) в (77) уже решены первые три пункта совета
Осталось посчитать суммы и решить систему линейных уравнений

(84) Решение, которое обращается ко всем элементам данных не может иметь сложность меньше, чем O(N), в нашем случае N -это к-во элементов матрицы, т.е. n^2.
Рекурсия, с передачей подобной области данных уже имеет другой, НЕ МЕНЬШИЙ , порядок сложности.
Только отбрасывание данных (т.е. пропуск элементов) может уменьшить сложность задачи.
И, как уже я писал, сложность линейная, а не квадратичная
Для данной задачи квадратичная сложность, это O(N*N) = O(n^4)

(77) У меня получилось так:
solve
a n m      + b (n+1)n m/2          + c n(m+1)m/2         = p;
a (n+1)n/2 + b (n(n+1(2n+1)/6)-1)m + c (n+1)n(m+1)m/4    = q;
a (m+1)m/2 + b (n+1)n(m+1)m/4      + c (m(m+1)(2m+1)/6-1)n = s
for a,b,c

можно решить в общем виде.
Здесь p = Сумма(Zij); q = Сумма(i * Zij); s = Сумма(j * Zij).

+(87) n - число строк, m - число столбцов в матрице

(87) Если под уравнением имеется в виду а*i+b*j+с - то не правильно, видимо a+b*x+c*y - но и тогда что-то не сходится
Кстати, в (77) - неправильное дифференцирование
для функции a*i+b*j+c должно получиться такие ураdнения
а*Сумма(квадратов i)/n+b(n+1)(m+1)/4+c(n+1)/2 = Сумма(i*Zij)/(m*n)
a*(n+1)(m+1)/4+b*Сумма(квадратов j)/m+c*(m+1)/2 = Сумма(j*Zij)/(m*n)
a/2*(n+1)+b/2*(m+1)+c = Сумма(Zij)/(m*n)

Формула для суммы квадратов
Сумма квадратов от 1 до n это (2*(n+1)^3+n+1-3(n+1)^2)/6
Или
((n+1)^3+n^3+n+2)/6)

(89) У меня было а + i*b + j*c; Сумма(квадратов i) = n(n+1 )(2n+1)/6) - 1.

Сейчас понял, что в общем виде считать нет смысла, достаточно задать n = m = КонкретноеЗначение, получим числа, которые нужно подставить в решение ЛУ по формуле Крамера.

Там вполне обозримые выражения, которые собственно и показывают, что к элементам матрицы приходится обращаться трижды, находя суммы с весом 1, с весом i и с весом j. То есть примерно в три раза больше время, чем усреднение в квадрантах (56).

(81) всё еще хуже ) https://ru.wikipedia.org/wiki/Сапог_Шварца сходиться тоже надо уметь, потому в (56) и бред

(90) ((n+1)^3+n^3+n+2)/6) = 6,5 при n = 2, а формулу из (91) я проверял

(93) Сорри - 2-й вариант не правильно упростил
Правильно : ((n+1)^3+n^3-2n-1)/6

(94) Да, а у меня -1 был лишний. Так что уравнения одни и те же.

Думаю, это все, что было нужно.

+(52) +(95) ...а мы так и не узнали, в чем был смысл аппроксимации и был ли он вообще...

(86) При "усреднении" по блокам экономия будет за счет меньшего числа умножений (число блоков х число блоков). А координаты "центра тяжести" в блоке - это сложения. Так что при "усреднении" число умножений меньше N^2.

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

(98) Давайте на одномерном примере. Пусть нужно построить одномерный тренд для 100 точек. Коэффициенты f(i) = a*i+b вычисляются так:
Процедура ВычислитьКоэффициентыТренда(Y, a, b)
    N = Y.Количество();
    Sx = 0; Sy = 0; Sxy = 0; Sxx = 0;
    ДЛЯ i = 0 ПО N-1 Цикл
        Sx = Sx+i;
        Sy = Sy+Y[i];
        Sxy = Sxy+Y[i]*i;
        Sxx = Sxx+i*i;
    КонецЦикла;
    b = (N*Sxy-Sx*Sy)/(N*Sxx-Sx*Sx);
    a = (Sy-b*Sx)/N;
КонецПроцедуры

Как видим, это O(N) умножений.
Если разобъем на 10 блоков по 10 точек, то:
- для усреднения в каждом блоке понадобится 10 сложений + 1 деление - итого 10 делений;
- для вычисления тренда по усредненным - O(10) умножений.

В крайнем случае (1 блок):
- для усреднения - 100 сложений + 1 деление;
- для тренда - 0 умножений.

z=A(х+у), где а - коэффициент наклона прямой к плоскости координат х,у.
Т.к. ф-я линейна во всех направлениях, т.е. линия в 3-мерном пространстве, то она проходит через начало координат, а поскольку есть пары координат с одинаковыми индексами (х=1,у=1; х=10,у=10...), то проекция линии на плоскость ху - это биссектриса.
Тебе остается взять любую координату в массиве и вычислить
А=z/(х+у)

(76) Да, есть такой недостаток  в (56), поэтому я написал (62) в котором этого недостатка нет.

(77) Вычисления ты пишешь те же самые что я делаю в (62).

(78) Ты выглядишь как гопник в компании интеллигентов ))))

(81) >> прикол еще в том, что отдельных при усреднениях по горизонтали и по вертикали мы получим минимум две прямых , котрые могут и не пересекаться.
Только в твоих фантазиях. В реальной жизни они не могут не пересекаться.


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

(79) Молодец! В тему

(99) Оценка сложность задачи определеяется кол-вом повторов в цикле вне зависимости от вычислений внутри цикла
В первом примере ты обращаешся к элементу 1 раз
А во втором ты дельшь элементы по 10 а потом работаешь с сокращенной задачей. Итого оценка второго примера O(N)+O(N/10) явно больше оценки O(N)
Что касается сложности вычислений внутри цикла, то я согласен, что для маленьких массивов( о которых речь НЕ идет) общее к-во умножений может вывести алгоритм назад, но в нашем случае, когда массив очень большой - накапливание даже одной сотой элементов в отдельном месте - основные потери будут именно на запись/чтение промежуточных результатов и к-во умножений (относительное ) не будет иметь значения.

Сравнил результаты по МНК со своим методом. Оба решения дают приемлемый по значению результат. По скорости нужно очень много оптимизировать. Тормозит в любом случае не приемлемо.

(101) Ты ошибаешься, алгоритмы разные
Кроме того идея приведения 3-х мерной задачи к двумерной не выполнена, значит все вычисления ошибочны.
Снимаю свое решение (77) и (87)

(105) Заполни массив по формуле
f(i,j) = 5i+7j-12
Проверь свои методы, получаешь ли ты указанную плоскость?

(105) надеюсь не на 1с пишешь )))

(104) "Итого оценка второго примера O(N)+O(N/10)" - а O(N) для умножений откуда взялось?

O(N) = O(N/10)

Интересно а автора не смущает что попытка перевести в математическую функцию в результате приведет к настоящим тормозам?

Если есть двумерный массив то почему данные в этом виде и не оставить, если там размеры не десятки миллионов х десятки миллионов.

И при необходимости получить "высоту" для неких координат банально берем значения из массива слева и справа по X и по Y и высчитываем требуемое Z как среднее арифметическое...

(111)+ Не хочется хранить точки и хочется еще быстрее то у тебя же по сути "аппроксимация полигонами" и можно даже заюзать GPU

(111) Смущает, читай внимательно (0). Поэтому и ищу более быстрый вариант.

(113) Гм а пробовал? Предвижу что взять 4 числа из массива и вычислить среднее шустрее чем все прочее ))

F(x,y) = (Z(x-,y-)+Z(x-,y+)+Z(x+,y-)+Z(x+,y+))/4

Кста задачка напоминает некий изврат похожий на распознавание/авторизацию по фейсу с камеры.

Причем распознавать/авторизовывать будет чип на карточке или даже симка в телефоне...

(114) Среднее по 4096х4096 считать шустрее чем ax + by + c???
Ну ты математик! )))

(117) Скажи прикидываешься или и правда не можешь смотреть чуть шире?

Зачем тебе "всего одна плоскость"?

Когда можно более точно и намного более быстро для конкретной "пары координат" значение высоты получать?

(118) По четырем соседним значением по-твоему более точно чем по всем?
Похоже ты не прикидываешься

(119) Мдя... Только не говори что автопилот для летающего чего то пишешь...

(120)+ В курсе что "твоя плоскость" будет через горы насквозь проходить?

(121) КО, тебя что в этом смущает? Расскажи что у тебя в голове, а то вообще не по теме что-то пишешь.

(122) Меня смущает практическое применение.

Если задача чисто теоретическая то есть или МНК или нечто вроде алгоритмов сжатия изображений с потерей информации.

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

(123)+ *группы из 4 точек

был массив 4096Х4096, стал 2048Х2048, затем 1024х1024 и т.д. до 2х2

(125) У этого есть недостатки которые уже в теме обсуждались

(0) если у тебя есть общие соображения из физической модели - тупо выкинь ненужные точки. Оставь три матрицы доверительно достаточной размерности, усредни .. .. профит

(107) Проверил оба своих метода, плоскость получается та же самая.

(127) Да, уже было, в (56)

МНК еще не предлагали? Как верно выше было замечено, сложность МНК "О" большое от количества точек, при этом с небольшой константой, и естественно легко доказывается что меньшая сложность невозможна (просто на чтение точек потребуется такая сложность).
Что обсуждается уже вторую страницу ИМХО непонятно.

(130) Предлагали сразу же в (1) :)

(131) а что делали в остальных 130 постах?

(132) Дурью маялись

Вплоть до предложения взять 3 случайные точки с помощью ГЧС и по ним построить плоскость...

(134) *ГСЧ

(4) такие задачи на ассемблере не решали тогда, не решают и сейчас на 1с...
ну не нравится наименьшие квадраты, что-бы не сплайн-метод?

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

(137) >более лучшее

Великий и Могучий изучали не в Иваново?

(138) Нет, троллей кормлю, которым не хватает знаний ни к чему придраться кроме как к правописанию )))

(139) ну (0) показывает, что знаний не хватает у вас, а в (137) проблема отнюдь не в правописании

(140) Это может любой глупый тролль написать. А ты попробуй напиши что-то умное.
Вот например Ildarovich, ovrfox и еще двое других человек на предыдущей странице показали что разбираются в вопросе, молодцы.

(140) Ты придрался к слову "правописание". Я знал что так будет, и специально его написал.