Как определить якобиан при решении нелинейной системы методом Ньютона-Рафсона

Я пытаюсь решить некоторые нелинейные системы методом Ньютона, и точность решения очень важна для моей задачи.

  1. без использования программного обеспечения для символьных вычислений, как я могу вычислить якобиан общей нелинейной системы полиномов с помощью C++ или других подобных языков программирования? Трудности для меня в основном следующие:

    • as accurate as symbolic Jacobian
    • алгоритм, подходящий для общих случаев нелинейной системы
    • зависит только от C++ или подобных языков программирования;

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


floating-accuracy nonlinear-functions newtons-method
person LCFactorization    schedule 12.11.2013    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Ознакомьтесь с идеей двойных чисел, существует несколько примеров реализации на C++. Оценка функций с использованием соответствующим образом инициализированных двойных чисел приводит к оценке одной производной по направлению. Повторите это для всех направлений координат.

Для хорошего введения см. Piponi: AD, C++ and Photogrammetry (http://el.mdu.edu.tw/datacos/09820722022O/paper.pdf)

Если L — усилия по вычислению функций, то одна производная по направлению стоит около 3*L, а полный якобиан — 3n*L. Если объединить все направления в одну оценку, это сведется к (1+2n)*L. Но к тому времени мы уже вошли в область автоматической или алгоритмической дифференциации.

Ищите FADBAD/TADIFF для простой реализации, для действительно быстрых кодов используются преобразования кода, предусмотренные проектом Tapenade. ADOL-C занимает промежуточное положение, более автоматический, чем Tapenade, и более быстрый, чем FADBAD.

person Lutz Lehmann    schedule 13.12.2013

arrow_upward
0
arrow_downward

Я сам решил проблему, используя конечно-разностную аппроксимацию якобиана;

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

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

person LCFactorization    schedule 03.12.2013
comment
Есть и другие преимущества. В слепых схемах с конечными разностями может быть трудно воспользоваться преимуществами разреженности (например, много вычислений функций впустую), тогда как, если доступен символический якобиан, он, очевидно, напрямую выявит разреженность. - person Caleb Hattingh; 27.02.2014