Как я могу проверить, сколько раз итераций требует метод Ньютона?

Question

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

так вот мой код

from numpy import *
import pylab as pl
def myffp(x):
    return x**3 - 1, 3*(x**2)    
def newton( ffp, x, nits):
    for i in range(nits):
        #print i,x
        f,fp = ffp(x)
        x = x - f/fp
    return x    
q = sqrt(3)/2
def leggo(xmin=-1,xmax=1,jmin=-1,jmax=1,pts=1000,nits=30):
    x = linspace(xmin, xmax, pts)
    y = linspace(jmin, jmax, pts)*complex(0,1)
    x1,y1 = meshgrid(x,y)                   
    n = newton(myffp,x1+y1,nits)                  #**here is where i wanna see the number of iterations newton's method takes to find my root** 
    r1 = complex(1,0)  
    r2 = complex(-.5, q)
    r3 = complex(-.5,-q)
    data = zeros((pts,pts,3))   
    data[:,:,0] = abs(n-r1)         #**and apply it here**
    data[:,:,2] = abs(n-r2)
    data[:,:,1] = abs(n-r3)
    pl.show(pl.imshow(data))    
leggo() 

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

Answer 1

Пожалуй, самый простой способ - просто реорганизовать функцию ньютон , чтобы она отслеживала общее количество итераций и затем возвращала ее (вместе с результатом, конечно), например,

def newton( ffp, x, nits):
    c = 0                   # initialize iteration counter
    for i in range(nits):
        c += 1              # increment counter for each iteration 
        f, fp = ffp(x)
        x = x - f/fp
    return x, c             # return the counter when the function is called

поэтому в основной части вашего кода измените ваш вызов на ньютон , например так:

res, tot_iter = newton(myffp, x, nits)

количество итераций в последнейвызов ньютона хранится в tot_iter

---

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

,в нем отсутствует критерий против какого-либо критерия сходимости.

Вот простая реализация на python, которая работает:

def newtons_method(x_init, fn, max_iter=100):
    """
    returns: approx. val of root of the function passed in, fn;
    pass in: x_init, initial value for the root; 
    max_iter, total iteration count not exceeded;
    fn, a function of the form: 
    def f(x): return x**3 - 2*x
    """
    x = x_init
    eps = .0001
    # set initial value different from x_init so at lesat 1 loop
    x_old = x + 10 * eps        
    step = .1
    c = 0
    # (x - x_old) is convergence criterion
    while (abs(x - x_old) > eps) and (c < max_iter):
        c += 1
        fval = fn(x)
        dfdx = (fn(x + step)) - fn(x) / step
        x_old = x
        x = x_old - fval / dfdx
    return x, c

Answer 2

Код, который вы в настоящее время используете для newton(), имеет фиксированное количество итераций (nits - которое передается как 30), поэтому результаты будут несколько тривиальными и неинтересными.

Похоже, вы пытаетесь сгенерировать фрактал Ньютона - неверный метод, который вы пытаетесь использовать;Типичный режим раскраски основан на выводе функции, а не на количестве итераций.См. статью в Википедии для полного объяснения.