Syntactic predicate: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
en>Paul Foxworthy
m Added link to production
 
en>אסף רזון
Line 1: Line 1:
The title of the author is Nestor. He presently lives in Idaho and his parents reside close by. My occupation is a messenger. One of my favorite hobbies is camping and now I'm attempting to earn cash with it.<br><br>Here is my site - [http://529design.net/UserProfile/tabid/61/userId/27197/Default.aspx extended auto warranty]
In [[numerical analysis]], '''Aitken's delta-squared process''' is a [[series acceleration]] method, used for accelerating the [[rate of convergence]] of a sequence. It is named after [[Alexander Aitken]], who introduced this method in 1926.<ref>Alexander Aitken, "On Bernoulli's numerical solution of algebraic equations", ''Proceedings of the Royal Society of Edinburgh'' (1926) '''46''' pp. 289&ndash;305.</ref> Its early form was known to [[Seki Kōwa]] (end of 17th century) and was found for rectification of the circle, i.e. the calculation of π. It is most useful for accelerating the convergence of a sequence that is converging linearly.
 
==Definition==
Given a sequence <math>x={(x_n)}_{n\in\N}</math>, one associates to this sequence the new sequence
 
:<math>A(x)={\left(\frac{x_{n+2}\,x_n-(x_{n+1})^2}{x_{n+2}-2\,x_{n+1}+x_n}\right)}_{n\in\Z^*},</math>
 
which can, with improved [[numerical stability]], also be written as
 
:<math> A(x_n)=x_n-\frac{(\Delta x_n)^2}{\Delta^2 x_n},</math>
 
where
 
:<math>\Delta x_{n}={(x_{n+1}-x_{n})},\ </math>
 
and
 
:<math>\Delta^2 x_n=x_n -2x_{n+1} + x_{n+2},\ </math>
 
for <math>n = 0, 1, 2, 3, \dots \, </math>
 
(To use this nice operator notation, one has to allow for the indices to start from ''n'' = 2 on, or apply a translation operator which first shifts the sequence indices by two, or to adopt the convention that ''x<sub>n</sub>''&nbsp;=&nbsp;0 for all ''n''&nbsp;<&nbsp;0.)
 
Obviously, ''Ax'' is ill-defined if Δ<sup>2</sup>x contains a zero element, or equivalently, if the sequence of [[first difference]]s has a repeating term. From a theoretical point of view, assuming that this occurs only for a finite number of indices, one could easily agree to consider the sequence ''Ax'' restricted to indices ''n>n<sub>0</sub>'' with a sufficiently large ''n<sub>0</sub>''. From a practical point of view, one does in general rather consider only the first few terms of the sequence, which usually provide the needed precision. Moreover, when numerically computing the sequence, one has to take care to stop the computation when [[rounding error]]s become too important in the denominator, where the Δ² operation may cancel too many [[significant digit]]s.
 
==Properties==
Aitken's delta-squared process is a method of [[acceleration of convergence]], and a particular case of a nonlinear [[sequence transformation]].
 
<math>x</math> will [[rate of convergence|converge linearly]] to <math>\ell</math> if there exists a number μ ∈ (0, 1) such that
:<math> \lim_{n\to \infty} \frac{|x_{n+1}-\ell|}{|x_n-\ell|} = \mu.</math>
 
Aitken's method will accelerate the sequence <math>x_n</math> if <math>\lim_{n \to \infty}\frac{A_n-\ell}{x_n-\ell}=0.</math>
 
<math>A</math> is not a linear operator, but a constant term drops out, viz: <math>A[x-\ell] = Ax - \ell</math>, if  <math>\ell</math> is a constant. This is clear from the expression of <math>Ax</math> in terms of the [[finite difference]] operator <math>\Delta</math>.
 
Although the new process does not in general converge quadratically, it can be shown that for a [[Fixed point (mathematics)|fixed point]] process, that is, for an [[iterated function]] sequence <math>x_{n+1}=f(x_n)</math> for some function <math>f</math>, converging to a fixed point, the convergence is quadratic. In this case, the technique is known as [[Steffensen's method]].
 
Empirically, the ''A''-operation eliminates the "most important error term". One can check this by considering a sequence of the form <math>x_n=\ell+a^n+b^n</math>, where <math>0<b<a<1</math>:
The sequence <math>Ax</math> will then go to the limit like <math>b^n</math> goes to zero.
 
One can also show that if <math>x</math> goes to its limit <math>\ell</math> at a rate strictly greater than 1, <math>Ax</math> does not have a better rate of convergence. (In practice, one rarely has e.g. quadratic convergence which would mean over 30 resp. 100 correct decimal places after 5 resp. 7 iterations (starting with 1 correct digit); usually no acceleration is needed in that case.)
 
In practice, <math>Ax</math> converges much faster to the limit than <math>x</math> does, as demonstrated by the example calculations below.
Usually, it is much cheaper to calculate <math>Ax</math> (involving only calculation of differences, one multiplication and one division) than to calculate many more terms of the sequence <math>x</math>. Care must be taken, however, to avoid introducing errors due to insufficient precision when calculating the ''differences'' in the numerator and denominator of the expression.
 
==Example calculations==
 
:The value of <math>\sqrt{2} \approx 1.4142136</math> can be approximated by assuming an initial value for <math>a_n</math> and iterating the following:
::<math>a_{n+1} = \frac{a_n + \frac{2}{a_n}}{2}. </math>
Starting with <math>a_0 = 1:</math>
{| class="wikitable"
|-
| ''n''
| ''x'' = iterated value
| ''Ax''
|-
| 0
| 1
| 1.4285714
|-
| 1
| 1.5
| 1.4141414
|-
| 2
| 1.4166667
| 1.4142136
|-
| 3
| 1.4142157
| --
|-
| 4
| 1.4142136
| --
|}
 
:The value of <math>\frac{\pi}{4}</math> may be calculated as an infinite sum:
 
:: <math>\frac{\pi}{4} = \sum_{n=0}^\infty \frac{(-1)^n}{2n+1} \approx 0.785398</math>
 
{| class="wikitable"
|-
| ''n''
| term
| ''x'' = partial sum
| ''Ax''
|-
| 0
| 1
| 1
| 0.79166667
|-
| 1
| &minus;0.33333333
| 0.66666667
| 0.78333333
|-
| 2
| 0.2
| 0.86666667
| 0.78630952
|-
| 3
| &minus;0.14285714
| 0.72380952
| 0.78492063
|-
| 4
| 0.11111111
| 0.83492063
| 0.78567821
|-
| 5
| &minus;9.0909091&times;10<sup>&minus;2</sup>
| 0.74401154
| 0.78522034
|-
| 6
| 7.6923077&times;10<sup>&minus;2</sup>
| 0.82093462
| 0.78551795
|-
| 7
| -6.6666667&times;10<sup>&minus;2</sup>
| 0.75426795
| --
|-
| 8
| 5.8823529&times;10<sup>&minus;2</sup>
| 0.81309148
| --
|}
 
==Example Pseudocode For Aitken Extrapolation==
 
The following is an example of using the Aitken extrapolation to help find the limit of the sequence <math>x_{n+1} = f(x_n)</math> when given <math>x_0</math>, which we assume to be the fixed point <math> \alpha = f(\alpha)</math>. For instance, we could have <math>x_{n+1} = \frac{1}{2}(x_n + \frac{2}{x_n})</math> with <math>x_0 = 1</math> which has the fixed point <math>\sqrt{2}</math> so that <math>f(x) = \frac{1}{2}(x + \frac{2}{x})</math> (see [[Methods of computing square roots]]).
 
This pseudo code also computes the Aitken approximation to <math>f'(\alpha)</math>. The Aitken extrapolates will be denoted by <code>aitkenX</code>. We must check if during the computation of the extrapolate the denominator becomes too small, which could happen if we already have a large amount of accuracy, since otherwise a large amount of error could be introduced. We denote this small number by <code>epsilon</code>.
 
<source lang="matlab">
%These choices depend on the problem being solved
x0 = 1                      %The initial value
f(x) = (1/2)*(x + 2/x)      %The function that find the next element in the sequence
tolerance = 10^-10          %10 digit accuracy is desired
epsilon = 10^-16            %Don't want to divide by a number smaller than this
 
maxIterations = 20          %Don't allow the iterations to continue indefinitely
haveWeFoundSolution = false %Were we able to find the solution to the desired tolerance? not yet.
 
for i = 1 : maxIterations
    x1 = f(x0)
    x2 = f(x1)
 
    lambda = absoluteValue((x2 - x1)/(x1 - x0));      %OPTIONAL: computes an approximation of |f'(fixedPoint)|, which is denoted by lambda
 
    denominator = x2 - 2*x1 + x0
 
    if(absoluteValue(denominator) < epsilon)          %Don't want to divide by too small of a number
        print('WARNING: denominator is too small')
        break;                                        %Leave the loop
    end
 
    aitkenX = x2 - ( (x2 - x1)^2 )/denominator
   
    if(absoluteValue(aitkenX - x2) < tolerance)      %If the result is within tolerance
        print("The fixed point is", aitkenX))        %Display the result of the Aitken extrapolation
        haveWeFoundSolution = true
        break;                                        %Done, so leave the loop
    end
 
    x0 = aitkenX                                      %Update x0 to start again                 
   
end
 
if(haveWeFoundSolution == false)  %If we weren't able to find a solution to within the desired tolerance
    print("Warning: Not able to find solution to within the desired tolerance of ", tolerance);
    print("The last computed extrapolate was ", aitkenX)
end
</source>
 
==See also==
* [[Rate of convergence]]
* [[Limit of a sequence]]
* [[Fixed point iteration]]
* [[Richardson extrapolation]]
* [[Sequence transformation]]
* [[Shanks transformation]]
* [[Steffensen's method]]
 
==Notes==
<references/>
 
==References==
* William H. Press, ''et al.'', ''Numerical Recipes in C'', (1987) Cambridge University Press, ISBN 0-521-43108-5 ''(See [http://apps.nrbook.com/c/index.html section 5.1])''
* Abramowitz and Stegun, ''[[Abramowitz and Stegun|Handbook of Mathematical Functions]]'', section 3.9.7
* Kendall E. Atkinson, ''An Introduction to Numerical Analysis'', (1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6
 
{{DEFAULTSORT:Aitken's Delta-Squared Process}}
[[Category:Numerical analysis]]

Revision as of 11:53, 26 June 2013

In numerical analysis, Aitken's delta-squared process is a series acceleration method, used for accelerating the rate of convergence of a sequence. It is named after Alexander Aitken, who introduced this method in 1926.[1] Its early form was known to Seki Kōwa (end of 17th century) and was found for rectification of the circle, i.e. the calculation of π. It is most useful for accelerating the convergence of a sequence that is converging linearly.

Definition

Given a sequence x=(xn)n, one associates to this sequence the new sequence

A(x)=(xn+2xn(xn+1)2xn+22xn+1+xn)n*,

which can, with improved numerical stability, also be written as

A(xn)=xn(Δxn)2Δ2xn,

where

Δxn=(xn+1xn),

and

Δ2xn=xn2xn+1+xn+2,

for n=0,1,2,3,

(To use this nice operator notation, one has to allow for the indices to start from n = 2 on, or apply a translation operator which first shifts the sequence indices by two, or to adopt the convention that xn = 0 for all n < 0.)

Obviously, Ax is ill-defined if Δ2x contains a zero element, or equivalently, if the sequence of first differences has a repeating term. From a theoretical point of view, assuming that this occurs only for a finite number of indices, one could easily agree to consider the sequence Ax restricted to indices n>n0 with a sufficiently large n0. From a practical point of view, one does in general rather consider only the first few terms of the sequence, which usually provide the needed precision. Moreover, when numerically computing the sequence, one has to take care to stop the computation when rounding errors become too important in the denominator, where the Δ² operation may cancel too many significant digits.

Properties

Aitken's delta-squared process is a method of acceleration of convergence, and a particular case of a nonlinear sequence transformation.

x will converge linearly to if there exists a number μ ∈ (0, 1) such that

limn|xn+1||xn|=μ.

Aitken's method will accelerate the sequence xn if limnAnxn=0.

A is not a linear operator, but a constant term drops out, viz: A[x]=Ax, if is a constant. This is clear from the expression of Ax in terms of the finite difference operator Δ.

Although the new process does not in general converge quadratically, it can be shown that for a fixed point process, that is, for an iterated function sequence xn+1=f(xn) for some function f, converging to a fixed point, the convergence is quadratic. In this case, the technique is known as Steffensen's method.

Empirically, the A-operation eliminates the "most important error term". One can check this by considering a sequence of the form xn=+an+bn, where 0<b<a<1: The sequence Ax will then go to the limit like bn goes to zero.

One can also show that if x goes to its limit at a rate strictly greater than 1, Ax does not have a better rate of convergence. (In practice, one rarely has e.g. quadratic convergence which would mean over 30 resp. 100 correct decimal places after 5 resp. 7 iterations (starting with 1 correct digit); usually no acceleration is needed in that case.)

In practice, Ax converges much faster to the limit than x does, as demonstrated by the example calculations below. Usually, it is much cheaper to calculate Ax (involving only calculation of differences, one multiplication and one division) than to calculate many more terms of the sequence x. Care must be taken, however, to avoid introducing errors due to insufficient precision when calculating the differences in the numerator and denominator of the expression.

Example calculations

The value of 21.4142136 can be approximated by assuming an initial value for an and iterating the following:
an+1=an+2an2.

Starting with a0=1:

n x = iterated value Ax
0 1 1.4285714
1 1.5 1.4141414
2 1.4166667 1.4142136
3 1.4142157 --
4 1.4142136 --
The value of π4 may be calculated as an infinite sum:
π4=n=0(1)n2n+10.785398
n term x = partial sum Ax
0 1 1 0.79166667
1 −0.33333333 0.66666667 0.78333333
2 0.2 0.86666667 0.78630952
3 −0.14285714 0.72380952 0.78492063
4 0.11111111 0.83492063 0.78567821
5 −9.0909091×10−2 0.74401154 0.78522034
6 7.6923077×10−2 0.82093462 0.78551795
7 -6.6666667×10−2 0.75426795 --
8 5.8823529×10−2 0.81309148 --

Example Pseudocode For Aitken Extrapolation

The following is an example of using the Aitken extrapolation to help find the limit of the sequence xn+1=f(xn) when given x0, which we assume to be the fixed point α=f(α). For instance, we could have xn+1=12(xn+2xn) with x0=1 which has the fixed point 2 so that f(x)=12(x+2x) (see Methods of computing square roots).

This pseudo code also computes the Aitken approximation to f(α). The Aitken extrapolates will be denoted by aitkenX. We must check if during the computation of the extrapolate the denominator becomes too small, which could happen if we already have a large amount of accuracy, since otherwise a large amount of error could be introduced. We denote this small number by epsilon.

%These choices depend on the problem being solved
x0 = 1                      %The initial value
f(x) = (1/2)*(x + 2/x)      %The function that find the next element in the sequence
tolerance = 10^-10          %10 digit accuracy is desired
epsilon = 10^-16            %Don't want to divide by a number smaller than this

maxIterations = 20          %Don't allow the iterations to continue indefinitely
haveWeFoundSolution = false %Were we able to find the solution to the desired tolerance? not yet.

for i = 1 : maxIterations 
    x1 = f(x0)
    x2 = f(x1)

    lambda = absoluteValue((x2 - x1)/(x1 - x0));      %OPTIONAL: computes an approximation of |f'(fixedPoint)|, which is denoted by lambda

    denominator = x2 - 2*x1 + x0

    if(absoluteValue(denominator) < epsilon)          %Don't want to divide by too small of a number
        print('WARNING: denominator is too small')
        break;                                        %Leave the loop
    end

    aitkenX = x2 - ( (x2 - x1)^2 )/denominator
    
    if(absoluteValue(aitkenX - x2) < tolerance)       %If the result is within tolerance
        print("The fixed point is", aitkenX))         %Display the result of the Aitken extrapolation
        haveWeFoundSolution = true
        break;                                        %Done, so leave the loop
    end

    x0 = aitkenX                                      %Update x0 to start again                  
    
end

if(haveWeFoundSolution == false)   %If we weren't able to find a solution to within the desired tolerance
    print("Warning: Not able to find solution to within the desired tolerance of ", tolerance);
    print("The last computed extrapolate was ", aitkenX)
end

See also

Notes

  1. Alexander Aitken, "On Bernoulli's numerical solution of algebraic equations", Proceedings of the Royal Society of Edinburgh (1926) 46 pp. 289–305.

References

  • William H. Press, et al., Numerical Recipes in C, (1987) Cambridge University Press, ISBN 0-521-43108-5 (See section 5.1)
  • Abramowitz and Stegun, Handbook of Mathematical Functions, section 3.9.7
  • Kendall E. Atkinson, An Introduction to Numerical Analysis, (1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6