Нахождение корней в n-мерии

[ogronom]

Всем известно как обычно предлагают решать задачу

f: [a,b] \subset R \rightarrow R
найти хотя бы один корень

Это делется методом деления пополам (наверное его все знают ), конечно, у него есть свои недостатки, но это сейчас не важно.

А вот я столкнулся недавно с обобщением проблемы. Есть
f: [a_1,b_1]\times ...\times [a_n,b_n] \subset R^n \rightarrow R
надо найти здесь хотя бы одно (x_1,..., x_n) обращающее f в ноль (т.е. точно известно, что где-то она в ноль обращается).

Может кто-нить сможет предложить алгоритм для решения этой задачи?

Если кто-то придумает не для любого n, а только для n=2,4 тоже приветствуется.
Заранее благодарен


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

[ogronom]

Так же интересно
может кто знает, как находить корень, если на концах промежутка [a,b] (одномерный случай) функция принимает одинаковые значения, но при этом точно известно что корень есть.

[Егор]

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

Хотелось бы подробнее узнать ситуацию. Откуда именно известно, что функция обязательно имеет корень? В каком виде дана функция?

Нужно ещё уточнить, что именно требуется найти. Вот два варианта.

Задача 1. На вход подаются равномерно непрерывная функция $f$ (пусть даже меняющая знак на отрезке) и число $\delta>0$. Найти точку, которая отличается менее чем на $\delta$ от истинного корня.

Задача 1 алгоритмически неразрешима.

Задача 2. На вход подаются равномерно непрерывная функция $f$, которая обязана иметь корень, и число $\varepsilon>0$. Нужно найти такую точку $x$, что $|f(x)|<\varepsilon$.

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

Конечно, есть эвристические приёмы, которые обычно ускоряют поиск:
1) сначала брать крупную сетку, потом в первую очередь измельчать ячейки с малыми значениями функции;
2) пытаться двигаться по направлению убывания функции (метод градиентного спуска), и т. д.

[bugmaker]

Метод градиентного спуска ИМХО может помочь, не без проблем однако.

[ogronom]

Егор писал(а):

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

Угу, спасибо. Возможно это дествительно, то что надо.

Егор писал(а):

Хотелось бы подробнее узнать ситуацию. Откуда именно известно, что функция обязательно имеет корень? В каком виде дана функция?

Это задача у меня возникла в квантовой физики. Функция обязана иметь корень... так сказать из общей теории. Если корня нету... то это будет катастрофа, атом водорода перестанет существовать, настанет Апокалипсис, ну или по крайней мере что-то плохое точно случится

Егор писал(а):

Нужно ещё уточнить, что именно требуется найти. Вот два варианта.

Задача 1. На вход подаются равномерно непрерывная функция $f$ (пусть даже меняющая знак на отрезке) и число $\delta>0$. Найти точку, которая отличается менее чем на $\delta$ от истинного корня.

Задача 1 алгоритмически неразрешима.

Задача 2. На вход подаются равномерно непрерывная функция $f$, которая обязана иметь корень, и число $\varepsilon>0$. Нужно найти такую точку $x$, что $|f(x)|<\varepsilon$.

Можно ли тут поподробнее. В чем эти две ситуации, принципиально отличаются?
Наверное все же второй случай, с очень малой \varepsilon

Егор писал(а):

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

Конечно, есть эвристические приёмы, которые обычно ускоряют поиск:
1) сначала брать крупную сетку, потом в первую очередь измельчать ячейки с малыми значениями функции;
2) пытаться двигаться по направлению убывания функции (метод градиентного спуска), и т. д.

bugmaker писал(а):

Метод градиентного спуска ИМХО может помочь, не без проблем однако.

Мда... боюсь как бы не было проблем, что все это надо посчитать за конечный промежуток времени, ограниченный моей продолжительностью учебы %)
Время вычисления значения функции в данной точке является весьма продолжительным.

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

Спасибо всем

[незваный гость]

Ваша задача поставлена не плохо, а из рук вон плохо. Предположим, мы ограничимся непрерывными и даже проще — полиномиальными функциями. В одномерном случае все известно — $n$ корней, все пьют пиво. В m-мерном же корни образуют многообразия степени $m-1$, причудливо расположенные. Поэтому поиск корней, это вопрос, до которого надо ответить на другой — как мы собираемся описывать корни.

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

[ogronom]

незваный гость писал(а):

:evil:
Ваша задача поставлена не плохо, а из рук вон плохо. Предположим, мы ограничимся непрерывными и даже проще — полиномиальными функциями. В одномерном случае все известно — $n$ корней, все пьют пиво. В m-мерном же корни образуют многообразия степени $m-1$, причудливо расположенные. Поэтому поиск корней, это вопрос, до которого надо ответить на другой — как мы собираемся описывать корни.

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

Задача уж какая есть... И это только часть задачи. %)

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

[ogronom]

незваный гость писал(а):

:evil:
Ваша задача поставлена не плохо, а из рук вон плохо. Предположим, мы ограничимся непрерывными и даже проще — полиномиальными функциями. В одномерном случае все известно — $n$ корней, все пьют пиво.

Нам нафиг не нужны все корни. Нам бы хотя бы один.

[Егор]

А почему бы не применить Maple или Matlab?

ogronom писал(а):

Это задача у меня возникла в квантовой физики. Функция обязана иметь корень... так сказать из общей теории. Если корня нету... то это будет катастрофа, атом водорода перестанет существовать, настанет Апокалипсис, ну или по крайней мере что-то плохое точно случится

Возможно, есть и математические аргументы...

ogronom писал(а):

Можно ли тут поподробнее. В чем эти две ситуации, принципиально отличаются?
Наверное все же второй случай, с очень малой $\varepsilon$

Доказано, что первая задача в общем случае алгоритмически неразрешима: нет никакого общего алгоритма для вычисления корня непрерывной функции. Можно лишь решать вторую задачу, т. е. находить точку, в которой значение функции мало. Если повезёт, то такая точка будет близка к настоящему корню. В прикладных задачах везёт почти всегда.

[bugmaker]

Цитата:

Мда... боюсь как бы не было проблем, что все это надо посчитать за конечный промежуток времени, ограниченный моей продолжительностью учебы %)
Время вычисления значения функции в данной точке является весьма продолжительным.

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

[незваный гость]

ogronom писал(а):

Время вычисления значения функции в данной точке является весьма продолжительным.

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

[reader_st]

Уважаемый ogronom.
Согласен, что Ваша задача поставлена некорректно:

1) Если это физическая задача, то существуют ограничения на значения независимых переменных и у Вас получится оптимизационная задача.

2) Решать ее действительно надо числ. методами (но вот что-то не понял почему точка экстремума есть решение уравнения).

3) Выпишите задачу в явном виде с ограничениями на переменные --- тогда есть смысл подбирать метод решения.

А так для успокоения души --- посчитайте в Maple.

[Dan_Te]

ogronom писал(а):

Нам нафиг не нужны все корни. Нам бы хотя бы один.

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

[Yuri Gendelman]

Хочу повторить совет Егора: воспользуйтесь методами поиска экстремумов.

Что известно о задаче:
- "Если кто-то придумает не для любого n, а только для n=2,4 тоже приветствуется."
Значит задача в принципе - невысокой размерности. По крайней мере даже низкоразмерный (2-4) вариант задачи представляет интерес.
- "Время вычисления значения функции в данной точке является весьма продолжительным."
Значит методы с численным вычислением градиента и матрицы Якоби будут малоэффективны.

Предлагаю воспользоваться неградиентными методами поиска экстремума. Например, методом симплексов (не путать с симплексным методом ЛП). Я лично пользовался методом Нелдера-Мида - модификацией метода симплексов, описанной в книге Химмельблау Д. "Прикладное нелинейное программирование" Мир, 1975.

Посмотрите тексты подпрограмм на сайте Netlib:
http://www.netlib.org/master/expanded_liblist.html

Ну и одну из этих книг посмотреть не мешает:
Numerical Recipes in C: The Art of Scientific Computing
Numerical Recipes in Fortran 77: The Art of Scientific Computing
Numerical Recipes in Fortran 90: The Art of Parallel Scientific Computing

И помните, на Вас смотрит вся Вселенная! Ведь

ogronom писал(а):

Если корня нету... то это будет катастрофа, атом водорода перестанет существовать, настанет Апокалипсис, ну или по крайней мере что-то плохое точно случится