Как оптимизировать решение нелинейных уравнений?

Question

У меня есть нелинейные уравнения, такие как:

Y = f1 (X)

Y = f2 (X)

...

Y = п (X)

В общем, у них нет точного решения, поэтому я использую Newton's method для их решения. Метод основан на итерации, и я ищу способ оптимизации вычислений. Каковы способы минимизации времени вычисления? Избегайте вычисления квадратных корней или других математических функций? Может быть, я должен использовать сборку внутри кода C++ (решение написано на C++)?

Answer 1

Популярным подходом для нелинейных проблем наименьших квадратов является алгоритм Левенберга-Марквардта. Это своего рода смесь между методами Гаусса-Ньютона и градиента-спуска. Он сочетает в себе лучшее из обоих миров (хорошо просматривает пространство поиска для некорректных задач и быстро сходится). Но есть много возможностей для маневра в плане реализации. Например, если квадратная матрица J^TJ (где J - матрица якобиана, содержащая все производные для всех уравнений), разрежена, вы можете использовать итеративный алгоритм CG для быстрого решения систем уравнений вместо прямого метода, такого как факторизация Cholesky J^TJ или QR-разложение J.

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

Answer 2

Вы говорите о ряде функций одного параметра для решения по одному или системы многопараметрических уравнений для решения вместе?

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