Lipid IVA 4-amino-4-deoxy-L-arabinosyltransferase

From formulasearchengine
Jump to navigation Jump to search

Sidi's generalized secant method is a root-finding algorithm, that is, a numerical method for solving equations of the form f(x)=0 . The method was published by Avram Sidi.[1][2]

The method is a generalization of the secant method. Like the secant method, it is an iterative method which requires one evaluation of f in each iteration and no derivatives of f. The method can converge much faster though, with an order which approaches 2 provided that f satisfies the regularity conditions described below.

Algorithm

We call α the root of f, that is, f(α)=0. Sidi's method is an iterative method which generates a sequence {xi} of approximations of α. Starting with k + 1 initial approximations x1,…,xk+1, the approximation xk+2 is calculated in the first iteration, the approximation xk+3 is calculated in the second iteration, etc. Each iteration takes as input the last k + 1 approximations and the value of f at those approximations. Hence the nth iteration takes as input the approximations xn,…,xn+k and the values f(xn),…,f(xn+k).

The number k must be 1 or larger: k = 1, 2, 3, .... It remains fixed during the execution of the algorithm. In order to obtain the starting approximations x1,…,xk+1 one could carry out a few initializing iterations with a lower value of k.

The approximation xn+k+1 is calculated as follows in the nth iteration. A polynomial of interpolation pn,k(x) of degree k is fitted to the k + 1 points (xn,f(xn)),…(xn+k,f(xn+k)). With this polynomial, the next approximation xn+k+1 of α is calculated as

Template:NumBlk

with pn′,k′(xn+k) the derivative of pn,k at xn+k. Having calculated xn+k+1 one calculates f(xn+k+1) and the algorithm can continue with the (n + 1)th iteration. Clearly, this method requires the function f to be evaluated only once per iteration; it requires no derivatives of f.

The iterative cycle is stopped if an appropriate stop-criterion is met. Typically the criterion is that the last calculated approximation is close enough to the sought-after root α.

To execute the algorithm effectively, Sidi's method calculates the interpolating polynomial pn,k(x) in its Newton form.

Convergence

Sidi showed that if the function f is (k + 1)-times continuously differentiable in an open interval I containing α (that is, f∈Ck+1(I)), α is a simple root of f (that is, f′(α)≠0) and the initial approximations x1,…,xk+1 are chosen close enough to α, then the sequence {xi} converges to α, meaning that the following limit holds: limn→∞xn=α.

Sidi furthermore showed that

limn→∞xn+1−α∏i=0k(xn−i−α)=L=(−1)k+1(k+1)!f(k+1)(α)f′(α),

and that the sequence converges to α of order ψk, i.e.

limn→∞|xn+1−α||xn−α|ψk=|L|(ψk−1)/k

The order of convergence ψk is the only positive root of the polynomial

sk+1−sk−sk−1−⋯−s−1

We have e.g. ψ1=(1+5)/2 ≈ 1.6180, ψ2 ≈ 1.8393 and ψ3 ≈ 1.9276. The order approaches 2 from below if k becomes large: limk→∞ψk=2 [3] [4]

Sidi's method reduces to the secant method if we take k = 1. In this case the polynomial pn,1(x) is the linear approximation of f around α which is used in the nth iteration of the secant method.

We can expect that the larger we choose k, the better pn,k(x) is an approximation of f(x) around x=α. Also, the better pn′,k′(x) is an approximation of f′(x) around x=α. If we replace pn′,k′ with f′ in (Template:EquationNote) we obtain that the next approximation in each iteration is calculated as

Template:NumBlk

This is the Newton–Raphson method. It starts off with a single approximation x1 so we can take k = 0 in (Template:EquationNote). It does not require an interpolating polynomial but instead one has to evaluate the derivative f′ in each iteration. Depending on the nature of f this may not be possible or practical.

Once the interpolating polynomial pn,k(x) has been calculated, one can also calculate the next approximation xn+k+1 as a solution of pn,k(x)=0 instead of using (Template:EquationNote). For k = 1 these two methods are identical: it is the secant method. For k = 2 this method is known as Muller's method.[4] For k = 3 this approach involves finding the roots of a cubic function, which is unattractively complicated. This problem becomes worse for even larger values of k. An additional complication is that the equation pn,k(x)=0 will in general have multiple solutions and a prescription has to be given which of these solutions is the next approximation xn+k+1. Muller does this for the case k = 2 but no such prescriptions appear to exist for k > 2.

References

  1. ↑ Sidi, Avram, "Generalization Of The Secant Method For Nonlinear Equations", Applied Mathematics E-notes 8 (2008), 115–123, http://www.math.nthu.edu.tw/~amen/2008/070227-1.pdf
  2. ↑ The home page of Avram Sidi at the Israel Institute of Technology is at Avraham Sidi
  3. ↑ Traub, J.F., "Iterative Methods for the Solution of Equations", Prentice Hall, Englewood Cliffs, N.J. (1964)
  4. 1 2 Muller, David E., "A Method for Solving Algebraic Equations Using an Automatic Computer", Mathematical Tables and Other Aids to Computation 10 (1956), 208–215
Retrieved from "https://en.formulasearchengine.com/w/index.php?title=Lipid_IVA_4-amino-4-deoxy-L-arabinosyltransferase&oldid=29103"