Re: Минимум функции | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
Показывай свои рисунки На худой конец в инете посмотри как выглядит ПАРАБОЛА, а параболоид - это фигура вращения от параболы. ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Минимум функции | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Вот это - неплохая идея. Цитата:А вот метод наверное нужно выбрать другой, поскольку, во-первых, метод деления пополам используется для нахождения корней функции, а не минимумов, во-вторых, для функций одного аргумента, а не двух, а в третьих, для непрерывных функций, а не заданных на дискретной сетке. |
Re: Минимум функции | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
Нет, почему же? Просто наступит момент, когда мы интервал мельче дробить не сможем.
1 10 5 10 7 10 7 8 Потом выбираем нижнее или верхнее приближение. ------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. |
Re: Минимум функции | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Вовсе нет. В данном случае как раз получается эллиптический параболоид, который не является фигурой вращения. Задача в принципе решается аналитически - сначала приведением системы координат в такой вид, чтобы получить каноническое уравнение параболоида (замены переменных 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), и смотреть не попадает ли в полученный эллипс (внутрь его) ещё какая-нить "целая" точка. Если попадает - то проводить сечение через неё и т.д. Получающиеся концентрические эллипсы (всё более и более мелкие) в конце концов и дали бы искомое решение - т.е. в итоге мы бы получили эллипс внутри котрого нет больше "целых" точек, а вот на границе есть как минимум одна такая точка... Извиняюсь за некоторый сумбур... ------------------ WBR, Igor |
Re: Минимум функции | |
---|---|
kostyl Сообщений: 231 Откуда: Кременчуг Дата регистрации: 28.09.2007 |
Чет тут не то! А ну подставте в уравнение х=-25000 у=25000 скоко будет!
У меня получается,... блин закрыл уже...., короче гдето 85 кусков.... |
Re: Минимум функции | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Hi, Igor!
Извиняюсь конечно, но при вычислении коэффициентов я что-то напутал и в результате идея задачи "поплыла". Мне хотелось сделать так, чтобы реальный минимум находился возле начала координат в точке (0.25, 0.25), а целочисленный далеко от него. Этого можно достичь, если повернуть параболоид на 135 градусов + эпсилон. Тогда в ближайших целых точках (0,0), (0,1), (1,0) значение будет велико за счет "узкой" параболы, а где-то достаточно далеко на целочисленную точку выйдет "широкая" парабола и даст минимум. Решать такие задачи очень не просто, думаю, что никаких стандартных способов здесь нет. Если решать численно, можно натолкнуться на очень большой перебор. Чисто аналитически - тоже не очень получается, в частности, в предложенной тобой схеме остается еще проблема найти целочисленные точки внутри эллипса. Мне кажется, здесь наиболее приемлемым является комплексный подход. Сначала надо исследовать задачу аналитически и, по возможности сузить область поиска решения, а уже в этой области перебрать все целочисленные точки и найти минимум. В этой задаче в качестве области получился бы очень узкий и очень длинный прямоугольник, повернутый под углом 135 градусов к оси х. |
Re: Минимум функции | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
Игорь, видишь противоречие в своих слова, ты выделил цитату о параболоиде, а начал рассматривать конкретную задачу об элептическом параболоиде, поэтому считаю твоё замечание не верным ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Минимум функции | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Костя!
х=-25000 у=25000 z=-25000 Считай в виндовом калькуляторе, но в инженерном режиме - там точность подходящая В фоксе конечно тоже можно считать, но из-за округления ты не увидишь, что реально решение именно это - он даст z=-25000 и для пары x=-25001 у=25001 и ещё для ряда соседних... Хотя реально они уже будут чуть-чуть больше (25001 на 2 тысячных если не изменяет память). 2 Павел! Речь шла про параболоид - а он как раз НЕ является фигурой вращения в общем случае - по аналогии - если говорить про прямоугольник, нельзя утверждать что у него ВСЕ стороны равны, хотя квадрат это тоже прямоугольник и у него действительно все стороны равны - но это лишь частный случай, не общий ------------------ WBR, Igor |
Re: Минимум функции | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Леонид!
Да я понял чего ты хотел замутить Про то и писал - что далеко не всегда "ближайшая целая" даёт правильное решение... Кстати работать лучше всё-же не с прямоугольником, а с эллипсом (конечно можно так вольно расширять область поиска, но вот нужно ли). Просто у тебя не получилось "довернуть" параболоид на тот самый эпсилон Кстати тогда возможно не получилось бы провести такое (сравнительно простое) линейное преобразование системы координат - пришлось бы с синусами да косинусами разбираться А вот задача поиска (без перебора) "целых точек" внутри заданного эллипса интересна уже сама по себе. Тут кстати ещё один сложный момент. Одно дело просто доказать что ЕСТЬ такие точки и совсем другое - найти их. Кажется это по умному называется NP и P проблемами... Но тут я совсем уж "не копенгаген" P.S. Да, пришлось немного мозгами поскрипеть над этой задачкой. Спасибо ------------------ WBR, Igor |
Re: Минимум функции | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Hi, Игорь!
Сколько ни думал, не могу придумать ничего проще, чем "обернуть" эллипс прямоугольником, найти целочисленные точки попадающие в прямоугольник, а затем проверить, какие из них попадут в эллипс, подставив их координаты в уравнение эллипса. Цитата:Думаю, не просто интересна - а совершенно нетривиальна. Честно говоря сомневаюсь, что даже в простом варианте (доказать что ЕСТЬ такие точки) кто-нибудь ее уже решил. Цитата:Там можно без косинусов обойтись, сделав афинное преобразование, что-то вроде
|
Re: Минимум функции | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
А-а-а, Семен Семеныч (с) Да, действительно - это я напутал с параболоидами (они же элиптические, гиперболические ) ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Минимум функции | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
Цитата:Да, вовсе не факт, что есть тройка целых чисел, которая удовлетворяет уровнению. Но всегда есть тройка, которая максимально приближена к поверхности. Это и будет решением. ------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. Исправлено 1 раз(а). Последнее : Влад Колосов, 19.12.07 12:55 |
Re: Минимум функции | |
---|---|
kostyl Сообщений: 231 Откуда: Кременчуг Дата регистрации: 28.09.2007 |
Да, ответ 85000 с чем то дал именно видновз калк в обычном режиме! Гы-Гы! Всё да вы знаете! |
Re: Минимум функции | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Влад!
Речь вовсе не идёт о тройке - целыми должны быть лишь x и y - тройку подобрать наверное не всегда возможно... Просто тройку, даже не говоря о каком-то минимуме 2 Леонид Да, я совершенно согласен что вариант с прямоугольником есть наиболее простой и понятный - но он влечёт за собой полный перебор, а это не очень красиво... Кстати, а каков алгоритм поиска "целых" точек в случае такого вот "косого" прямоугольника можно использовать? Не отсечениями же от "правильно повёрнутых" прямоугольников ------------------ WBR, Igor |
Re: Минимум функции | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Наверное даже проще брать не прямоугольник, а паралеллограмм с двумя косыми сторонами и двумя вертикальными, т.е это две прямые y=a*x+b y=a*x+c при ограничении A<=x<=B. Тогда перебор организуется достаточно легко: берется ceiling(a*A+b), а затем, если нужно, прибавляется к нему по единичке, пока не вылезет за int(a*A+c), и так далее. А как сделать это (определить, есть ли хоть одна пара целых х и у, удовлетворяющих указанным условиям) без перебора, я не знаю. В моей задаче это как раз было просто за счет того, что угол был очень близок к 135 град. Поэтому можно было просчитывать только "прямую" х=-у и еще две-три соседних целочисленных "прямых" |
Re: Минимум функции | |
---|---|
leaf Автор Сообщений: 445 Откуда: Ростов-на-Дону Дата регистрации: 30.05.2005 |
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) точка минимума так? |
Re: Минимум функции | |
---|---|
leaf Автор Сообщений: 445 Откуда: Ростов-на-Дону Дата регистрации: 30.05.2005 |
на целых числах
|
Re: Минимум функции | |
---|---|
leaf Автор Сообщений: 445 Откуда: Ростов-на-Дону Дата регистрации: 30.05.2005 |
а вообще ввиду линейности "линейных" операций
тут эту объемную фигуру подвинули сначала одной плоскостью а потом другой так Леонид? |
© 2000-2024 Fox Club  |