kostyl
Да что то я натупил с "периодичностью" но мне кажеться что минимум именно в точке |x|=y,где x->-oo,y->+oo.
Кстате о бумажке: трудновато однако строить поверхность!

Показывай свои рисунки

На худой конец в инете посмотри как выглядит ПАРАБОЛА, а параболоид - это фигура вращения от параболы.

Влад Колосов
Если численные методы подходят, тогда можно решить уравнение аналитически и определить точный минимум с целью опеределения пределов поиска.

Вот это - неплохая идея.

Цитата:

Потом простейшим методом деления отрезка пополам вычислить минимум для целых значений.

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

Нет, почему же? Просто наступит момент, когда мы интервал мельче дробить не сможем.
1 10
5 10
7 10
7 8
Потом выбираем нижнее или верхнее приближение.

PaulWist
а параболоид - это фигура вращения от параболы

Вовсе нет. В данном случае как раз получается эллиптический параболоид, который не является фигурой вращения.

Задача в принципе решается аналитически - сначала приведением системы координат в такой вид, чтобы получить каноническое уравнение параболоида (замены переменных x' = x+y+0.25, y'=x-y+50000, z'=z+31250)... Получаем уравнение 100000*x'^2+(1/100000)*y'^2=z'. По определению min(z) будет в точке (0,0,0) этой системы координат (вершина параболоида), откуда мы находим координаты этой точки в исходной системе координат - это (-25000.125;24999.875;-31250). Как видно это не целые числа. Анализируя форму параболоида можно довольно легко понять, что он очень сильно сплюснут (сечение плоскостями параллельными Oxy это эллипсы), причём длинная ось параллельна прямой проходящей между 2 и 4 координатыми плоскостями (не хочу углубляться в эту тему ). Наиболее близкая точка (с целыми x и y) к найденной вершине это (-25000;25000). Конечно это не значит что она и есть искомое решение. Я дополнительно построил сечение этого параболоида плоскостью x=-y - Сечение это очевидно парабола (проходящая при этом через множество целых x и y), анализируя ей, находим минимум - как и пердполагалось, он действительно находится в точке (-25000;25000;-25000).
Конечно это не строгое доказательство. Увы, я не знаю как тут строго доказать... Более того, если бы параболоид не был так хитро повёрнут и сплюснут, то вовсе не факт что ближаяшая "целая" точка была бы искомым решением... Тогда наверное надо было бы брать эту ближайщую точку, проводить через неё сечение параболоида (плосколстью параллельной Oxy), и смотреть не попадает ли в полученный эллипс (внутрь его) ещё какая-нить "целая" точка. Если попадает - то проводить сечение через неё и т.д. Получающиеся концентрические эллипсы (всё более и более мелкие) в конце концов и дали бы искомое решение - т.е. в итоге мы бы получили эллипс внутри котрого нет больше "целых" точек, а вот на границе есть как минимум одна такая точка...
Извиняюсь за некоторый сумбур...

Чет тут не то! А ну подставте в уравнение х=-25000 у=25000 скоко будет!
У меня получается,... блин закрыл уже...., короче гдето 85 кусков....

Hi, Igor!

Извиняюсь конечно, но при вычислении коэффициентов я что-то напутал и в результате идея задачи "поплыла". Мне хотелось сделать так, чтобы реальный минимум находился возле начала координат в точке (0.25, 0.25), а целочисленный далеко от него. Этого можно достичь, если повернуть параболоид на 135 градусов + эпсилон. Тогда в ближайших целых точках (0,0), (0,1), (1,0) значение будет велико за счет "узкой" параболы, а где-то достаточно далеко на целочисленную точку выйдет "широкая" парабола и даст минимум. Решать такие задачи очень не просто, думаю, что никаких стандартных способов здесь нет. Если решать численно, можно натолкнуться на очень большой перебор. Чисто аналитически - тоже не очень получается, в частности, в предложенной тобой схеме остается еще проблема найти целочисленные точки внутри эллипса. Мне кажется, здесь наиболее приемлемым является комплексный подход. Сначала надо исследовать задачу аналитически и, по возможности сузить область поиска решения, а уже в этой области перебрать все целочисленные точки и найти минимум. В этой задаче в качестве области получился бы очень узкий и очень длинный прямоугольник, повернутый под углом 135 градусов к оси х.

Igor Korolyov

PaulWist
а параболоид - это фигура вращения от параболы

Вовсе нет. В данном случае как раз получается эллиптический параболоид, который не является фигурой вращения.

...

Игорь, видишь противоречие в своих слова, ты выделил цитату о параболоиде, а начал рассматривать конкретную задачу об элептическом параболоиде, поэтому считаю твоё замечание не верным

Привет Костя!

х=-25000 у=25000 z=-25000

Считай в виндовом калькуляторе, но в инженерном режиме - там точность подходящая

В фоксе конечно тоже можно считать, но из-за округления ты не увидишь, что реально решение именно это - он даст z=-25000 и для пары x=-25001 у=25001 и ещё для ряда соседних... Хотя реально они уже будут чуть-чуть больше (25001 на 2 тысячных если не изменяет память).

2 Павел!

Речь шла про параболоид - а он как раз НЕ является фигурой вращения в общем случае - по аналогии - если говорить про прямоугольник, нельзя утверждать что у него ВСЕ стороны равны, хотя квадрат это тоже прямоугольник и у него действительно все стороны равны - но это лишь частный случай, не общий

Привет Леонид!

Да я понял чего ты хотел замутить Про то и писал - что далеко не всегда "ближайшая целая" даёт правильное решение...

Кстати работать лучше всё-же не с прямоугольником, а с эллипсом (конечно можно так вольно расширять область поиска, но вот нужно ли). Просто у тебя не получилось "довернуть" параболоид на тот самый эпсилон
Кстати тогда возможно не получилось бы провести такое (сравнительно простое) линейное преобразование системы координат - пришлось бы с синусами да косинусами разбираться
А вот задача поиска (без перебора) "целых точек" внутри заданного эллипса интересна уже сама по себе. Тут кстати ещё один сложный момент. Одно дело просто доказать что ЕСТЬ такие точки и совсем другое - найти их. Кажется это по умному называется NP и P проблемами... Но тут я совсем уж "не копенгаген"

P.S. Да, пришлось немного мозгами поскрипеть над этой задачкой. Спасибо

Hi, Игорь!

Igor Korolyov
Кстати работать лучше всё-же не с прямоугольником, а с эллипсом (конечно можно так вольно расширять область поиска, но вот нужно ли).

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

Цитата:

А вот задача поиска (без перебора) "целых точек" внутри заданного эллипса интересна уже сама по себе. Тут кстати ещё один сложный момент. Одно дело просто доказать что ЕСТЬ такие точки и совсем другое - найти их.

Думаю, не просто интересна - а совершенно нетривиальна. Честно говоря сомневаюсь, что даже в простом варианте (доказать что ЕСТЬ такие точки) кто-нибудь ее уже решил.

Цитата:

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

Там можно без косинусов обойтись, сделав афинное преобразование, что-то вроде
Но как раз в этом месте я что-то и напутал

Igor Korolyov
2 Павел!
Речь шла про параболоид - а он как раз НЕ является фигурой вращения в общем случае - по аналогии - если говорить про прямоугольник, нельзя утверждать что у него ВСЕ стороны равны, хотя квадрат это тоже прямоугольник и у него действительно все стороны равны - но это лишь частный случай, не общий

А-а-а, Семен Семеныч (с)

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

Цитата:

Честно говоря сомневаюсь, что даже в простом варианте (доказать что ЕСТЬ такие точки) кто-нибудь ее уже решил.

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





Исправлено 1 раз(а). Последнее : Влад Колосов, 19.12.07 12:55

Igor Korolyov
Привет Костя!
х=-25000 у=25000 z=-25000

Считай в виндовом калькуляторе, но в инженерном режиме - там точность подходящая

Да, ответ 85000 с чем то дал именно видновз калк в обычном режиме! Гы-Гы! Всё да вы знаете!

Привет Влад!

Речь вовсе не идёт о тройке - целыми должны быть лишь x и y - тройку подобрать наверное не всегда возможно... Просто тройку, даже не говоря о каком-то минимуме

2 Леонид

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

Кстати, а каков алгоритм поиска "целых" точек в случае такого вот "косого" прямоугольника можно использовать? Не отсечениями же от "правильно повёрнутых" прямоугольников

Igor Korolyov
Кстати, а каков алгоритм поиска "целых" точек в случае такого вот "косого" прямоугольника можно использовать?

Наверное даже проще брать не прямоугольник, а паралеллограмм с двумя косыми сторонами и двумя вертикальными, т.е это две прямые
y=a*x+b
y=a*x+c
при ограничении A<=x<=B.
Тогда перебор организуется достаточно легко: берется ceiling(a*A+b), а затем, если нужно, прибавляется к нему по единичке, пока не вылезет за int(a*A+c), и так далее. А как сделать это (определить, есть ли хоть одна пара целых х и у, удовлетворяющих указанным условиям) без перебора, я не знаю.

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

100000.00001*x*x+100000.00001*y*y+199999.99998*x*y+50001*x+49999*y
Найти минимальное значение, которое может принимать эта функция для целых значений x и y.

Итак имеем :
1. Необходимое условие экстремума,перелома - равенство нулю смешанной производной
следовательно таких точек нет
2. понятно что (при х->-00 и у->-00) и (при х->+00 и у->+00) и (при х->+00 и у->-00) и (при х->-00 и у->+00) z->+00 так как квадраты забивают рост линейной функции
3. понятно что что то меньшее нуля можно получить при отрицательных х и положительных у
проверим

f(-1,1)= -2.00004
f(-2,1)= много и больше 0

собственно в (-1,1) точка минимума
так?

на целых числах

а вообще ввиду линейности "линейных" операций
тут эту объемную фигуру подвинули сначала одной плоскостью а потом другой
так Леонид?