Метод ньютона рафсона питон

Python Program Newton Raphson (NR) Method (with Output)

In this python program, x0 is initial guess, e is tolerable error, f(x) is non-linear function whose root is being obtained using Newton Raphson method.

Python Source Code: Newton Raphson Method

 # Defining Function def f(x): return x**3 - 5*x - 9 # Defining derivative of function def g(x): return 3*x**2 - 5 # Implementing Newton Raphson Method def newtonRaphson(x0,e,N): print('\n\n*** NEWTON RAPHSON METHOD IMPLEMENTATION ***') step = 1 flag = 1 condition = True while condition: if g(x0) == 0.0: print('Divide by zero error!') break x1 = x0 - f(x0)/g(x0) print('Iteration-%d, x1 = %0.6f and f(x1) = %0.6f' % (step, x1, f(x1))) x0 = x1 step = step + 1 if step > N: flag = 0 break condition = abs(f(x1)) > e if flag==1: print('\nRequired root is: %0.8f' % x1) else: print('\nNot Convergent.') # Input Section x0 = input('Enter Guess: ') e = input('Tolerable Error: ') N = input('Maximum Step: ') # Converting x0 and e to float x0 = float(x0) e = float(e) # Converting N to integer N = int(N) #Note: You can combine above three section like this # x0 = float(input('Enter Guess: ')) # e = float(input('Tolerable Error: ')) # N = int(input('Maximum Step: ')) # Starting Newton Raphson Method newtonRaphson(x0,e,N) 

Newton Raphson Python Output

Enter Guess: 2 Tolerable Error: 0.000001 Maximum Step: 10 *** NEWTON RAPHSON METHOD IMPLEMENTATION *** Iteration-1, x1 = 3.571429 and f(x1) = 18.696793 Iteration-2, x1 = 3.009378 and f(x1) = 3.207103 Iteration-3, x1 = 2.864712 and f(x1) = 0.185915 Iteration-4, x1 = 2.855236 and f(x1) = 0.000771 Iteration-5, x1 = 2.855197 and f(x1) = 0.000000 Required root is: 2.85519654

Example

In this program we will solve f(x) = 3*cos(x) — e x using python. Everything is similar as above python program for Newton Raphson method. The difference here is import math and use of mathematical functions.

 import math # Defining Function def f(x): return 3*math.cos(x) - math.exp(x) # Defining derivative of function def g(x): return -3*math.sin(x) - math.exp(x) # Implementing Newton Raphson Method def newtonRaphson(x0,e,N): print('\n\n*** NEWTON RAPHSON METHOD IMPLEMENTATION ***') step = 1 flag = 1 condition = True while condition: if g(x0) == 0.0: print('Divide by zero error!') break x1 = x0 - f(x0)/g(x0) print('Iteration-%d, x1 = %0.6f, f(x1) = %0.6f and g(x1) = %0.6f' % (step, x1, f(x1), g(x1))) x0 = x1 step = step + 1 if step > N: flag = 0 break condition = abs(f(x1)) > e if flag==1: print('\nRequired root is: %0.8f' % x1) else: print('\nNot Convergent.') # Input Section x0 = input('Enter Guess: ') e = input('Tolerable Error: ') N = input('Maximum Step: ') # Converting x0 and e to float x0 = float(x0) e = float(e) # Converting N to integer N = int(N) #Note: You can combine above three section like this # x0 = float(input('Enter Guess: ')) # e = float(input('Tolerable Error: ')) # N = int(input('Maximum Step: ')) # Starting Newton Raphson Method newtonRaphson(x0,e,N) 

The output of the above program is:

Enter Guess: 0.5 Tolerable Error: 0.00001 Maximum Step: 10 *** NEWTON RAPHSON METHOD IMPLEMENTATION *** Iteration-1, x1 = 0.818765, f(x1) = -0.218326 and g(x1) = -4.458605 Iteration-2, x1 = 0.769798, f(x1) = -0.005174 and g(x1) = -4.247299 Iteration-3, x1 = 0.768579, f(x1) = -0.000003 and g(x1) = -4.242044 Required root is: 0.76857930

Recommended Readings

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

okiochan/Nonlinear-regression

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

линейная регрессия не подходит

Модель для выборки подбирает эксперт. Данная выборка похожа на синус

Запустим алгоритм на нашей выборке; Минимизируем градиентным спуском.

код программы non_linear_stanrard.py

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

Пусть необходимо найти минимум функции многих переменных Эта задача равносильна задаче нахождения нуля градиента

Применим метод Ньютона, и запишем в удобном итеративном виде (Н — гессиан, матрица Гёссе):

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

Метод Ньютона — Рафсона является улучшением метода Ньютона нахождения экстремума, описанного выше. Основное отличие заключается в том, что на очередной итерации каким-либо из методов одномерной оптимизации выбирается оптимальный шаг:

Реализуем метод Ньютона-Рафсона

Для нахождения матрицы Гёссе, запишем нашу функцию так:

Посчитаем матрицу Гессе вторых производных сначала в общем виде: по первой производной по второй производной

Эту часть вычислим в математике

Реализуем Hessian(полученные формулы) на python

def Hess(p,x,y): a, b, c, d = p g = dU(p,x,y) u = F(p,x) h = np.zeros((4,4)) h[0,1]=h[1,0]=x*np.cos(c+b*x) h[0,2]=h[2,0]=np.cos(c+b*x) h[1,1]= -a*x*x*np.sin(c+b*x) h[1,2]=h[2,1]= -a*x*np.sin(c+b*x) h[2,2]=-a*np.sin(c+b*x) for i in range(4): for j in range(4): h[i,j]=g[i]*g[j] + (u - y)*h[i,j] return h 

Теперь сделаем нужный спуск, не забудем про лямбду (длину вектора)

 for i in range(n): G += dF(x, X[i],Y[i]) H += Hess(x, X[i],Y[i]) #направление вектора d = -np.linalg.pinv(H).dot(G) def Qalpha(alpha): return Error(x + alpha * d, X, Y) #ищем длину вектора alpha_best = Golden(Qalpha, 0, 10) x = x + alpha_best * d 

Лямбду найдем методом золотого сечения, в программме — Golden, принимает функцию (функционал качества), границы, эпсилон и кол-во итераций

Golden(f, l, r, EPS=1e-9, maxiter=100) 

код программы в non_linear_hessian.py

Вот как отработают оба алгоритма: Градиентный спуск с шагом 0.002 и Метод Ньютона — Рафсона. Мы видим, что оба сошлись к одному результату. По скорости, Метод Ньютона — Рафсона гораздо быстрее.

Сравним ошибки. Мы видимЮ что у Ньютона — Рафсона SSE меньше и он быстрее сходится.

С применением метода Ньютона — Рафсона, функция сходится в разы быстрее (сошелся за 3 итерации в данном примере), при этом квадратичная ошибка не ухудшается.

Можно также заметить, что стандартный метод Ньютона (без лямбды) не всегда сходится. На данном примере, при начальном x0 = (1,1,1,1) метод не сошелся

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Newton-Raphson Method Algorithm in Python

License

Toktom/Newton-Raphson-Method

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Newton-Raphson Method Algorithm in Python

The project here contains the Newton-Raphson Algorithm made in Python as a homework in the beginning of the course of Computational Numerical Methods (MTM224 — UFSM).

In numerical analysis, the Newton’s Method (or Method of Newton-Raphson), developed by Isaac Newton and Joseph Raphson, aims at estimating the roots of a function. For this purpose, an initial approximation is chosen, after this, the equation of the tangent line of the function at this point and the intersection of it with the axis of the abscissa, in order to find a better approximation for the root, is calculated. By repeating the process, an iterative method is created to find the root of the function.

In mathematical notation the method is described in the following formula:

This code is licensed under the Beerware license. Feel free to use and do whatever you wish.

Источник