Predictive iteration method

yuiop

Hi,

I came up with a predictive iterative method that converges very rapidly, when writing a java simulation. It turns out that this method can be used for a wide variety of problems and is very simple because unlike the bijective method it does not require upper and lower bounds to be found initially and unlike the Newton-Raphson method it does not require that the derivative of the equation be found first. This predictive method is conceptually simple, so I am almost certain this method is already well known and has a name, but here it is anyway in Liberty basic (free):

Code:

T=63 ' <Target output value>
x1 = 5 ' <Initial input guess - (very bad guess in this example)>
epsilon=0.0000000000001 ' <Acceptable error margin>
x0 = x1+0.1 ' <First guess plus increment - Can be optimised for a given problem>

' <Initial first two guesses:>
t1 = ComplicatedFunction(x1)
print"guess1 = ";x1;" result1 = ";t1
t0 = ComplicatedFunction(x0)
print"guess0 = ";x0;" result0 = ";t0

do ' <Iterative loop>
x2=x1
t2=t1
x1=x0
t1=t0
x0 = (x1-x2)*(T-t2)/(t1-t2)+x2 ' < *Key iterative predictive step* >
t0 = ComplicatedFunction(x0)
print"guess = ";x0;" result = ";t0
loop while (abs(T-t0)>epsilon)
end

function ComplicatedFunction(x)
ComplicatedFunction = 56+x^2+2^(x+5)-3*x^4 ' <Insert function to be solved here>
end function

Example output:

Code:

guess1 = 5 result1 = -770
guess0 = 5.1 result0 = -850.054274
guess = 3.95945594 result = -167.843532
guess = 3.57352355 result = -39.4866854
guess = 3.26537535 result = 33.2835597
guess = 3.13954002 result = 56.390209
guess = 3.1035441 result = 62.355382
guess = 3.09965425 result = 62.9833978
guess = 3.09955142 result = 62.9999564
guess = 3.09955115 result = 63.0

Does anyone know if this method already has a name? It takes significantly less iteration steps than the bijective iteration method, for almost any none trivial function. It does require that the initial guess is somewhere close to the final solution (with a fair degree of latitude), but this is not a big problem for simulations with small time increments where the last solution provides the basis for the next step. I think it would compare well with the Newton-Raphson method (although I have not tested that yet) and is simpler to set up for a random function.

{EDIT} It may be that the above method is in fact the Newton-Raphson method in disguise. Would anyone agree?

torquil

Yes, I believe it is the same thing, using a discrete derivative. It basically constructs a straight line, and then jumps to the x-value where that line crosses the function value T.

AlephZero

The standard name for this is the secant method.

There are several versons of exactly how to do it, depending on exactly which points you use to estimate the derivative. For example you can use the last two you calculated, or the two that have the smallest function value, or keep the same value for every iteration, etc.

It behaves very similar to Newton's method, but when the two points are close together you can lose accuracy because the slope is calculated from the difference of numbers that are almost equal. If you find the derivative directly as in Newton's method, you avoid that problem.

Similar Threads for: Predictive iteration method
Thread	Forum	Replies
Looking for simple iteration method	General Math	3
Variational Iteration Method	Differential Equations	3
Iteration: Newton-Raphson Method	Engineering, Comp Sci, & Technology Homework	20
Fixed-Point iteration Method	Calculus & Beyond Homework	4
Newton-Raphson Method for derivation of iteration formula	Calculus	3

torquil	Yes, I believe it is the same thing, using a discrete derivative. It basically constructs a straight line, and then jumps to the x-value where that line crosses the function value T.