Euler-Chebyshev trial

The Euler-Tschebyschow method (after Leonhard Euler and Pafnuti Lwowitsch Tschebyschow ; also method of touching parabolas ) describes an iterative method in numerical mathematics for solving non-linear equations. It is comparable to Newton's method , but has the order of convergence 3.

description

You have a non-linear equation in zero form

{\ displaystyle F (x) = 0}

a function

{\ displaystyle F: D \ subset \ mathbb {R} ^ {n} \ to \ mathbb {R} ^ {n}}

and a sufficiently good starting value , an approximate calculation of the zero of the terminated Taylor expansion is obtained ${\ displaystyle x_ {0}}$

{\ displaystyle 0 = F (x_ {k}) + F '(x_ {k}) (x-x_ {k}) + {\ frac {1} {2}} F' '(x_ {k}) ( x-x_ {k}) ^ {2}}

the following procedure in each step. The exact derivation of the method is described in Halley's method in the section on the multi-dimensional case.

algorithm

Choose a start value , a , and sit ${\ displaystyle x_ {0} \ in \ mathbb {R} ^ {n}}$ $x_ {0} \ in {\ mathbb {R}} ^ {n}$ ${\ displaystyle \ varepsilon> 0}$ $\ varepsilon> 0$ ${\ displaystyle N \ in \ mathbb {N}}$ $N \ in \ mathbb {N}$ ${\ displaystyle k = 0}$ $k = 0$
1. If or stop ${\ displaystyle \ | F (x_ {k}) \ | <\ varepsilon}$ ${\ displaystyle k> N}$
2. Solve:, (Newton step) ${\ displaystyle F '(x_ {k}) s_ {k} = - F (x_ {k})}$
3. Solve:, (quadratic correction) ${\ displaystyle F '(x_ {k}) t_ {k} = - {\ frac {1} {2}} F' '(x_ {k}) (s_ {k}, s_ {k})}$
4. Set , ${\ displaystyle x_ {k + 1} = x_ {k} + s_ {k} + t_ {k}}$ ${\ displaystyle k = k + 1}$

properties

In contrast to Newton's method, one obviously needs the 2nd derivative of the function. Increasing the order of convergence is therefore only worthwhile if the calculation of the 2nd derivative is easy in comparison with the calculation of the function value and the first derivative. Other methods are obtained by approximating the zero of the Taylor expansion. An example of this would be the Halley process .

example

As a simple one-dimensional example, the calculation of the zero point with the starting value 0 should be taken. The first derivative is the second derivative ${\ displaystyle f (x) = x + e ^ {x}}$ ${\ displaystyle f '(x) = 1 + e ^ {x}}$ ${\ displaystyle f '' (x) = e ^ {x}}$

Step 1
- ${\ displaystyle f (0) = 1}$ , , ${\ displaystyle f '(0) = 2}$ ${\ displaystyle f '' (0) = 1}$
- ${\ displaystyle s_ {0} = - {\ frac {f (0)} {f '(0)}} = - 0.5}$
- ${\ displaystyle t_ {0} = - {\ frac {1} {2}} \ cdot {\ frac {f '' (0) \ cdot s_ {0} ^ {2}} {f '(0)}} = -0.0625}$
- ${\ displaystyle x_ {1} = x_ {0} + s_ {0} + t_ {0} = - 0.5625}$
step 2
- ${\ displaystyle f (-0.5625) = 0.0073}$ , , ${\ displaystyle f '(- 0.5625) = 1.5698}$ ${\ displaystyle f '' (- 0.5625) = 0.5698}$
- ${\ displaystyle s_ {1} = - {\ frac {f (-0.5625)} {f '(- 0.5625)}} = - 0.0046}$
- ${\ displaystyle t_ {1} = - {\ frac {1} {2}} \ cdot {\ frac {f '' (- 0.5625) \ cdot s_ {1} ^ {2}} {f '(- 0.5625) }} = - 3.9063 \ cdot 10 ^ {- 6}}$
- ${\ displaystyle x_ {2} = x_ {1} + s_ {1} + t_ {1} = - 0.5671}$