Secant method

The secant method is a numerical method known since the Middle Ages for the approximate solution of an equation of the type . It corresponds to a simplification of Newton's method , since the derivative of the function does not have to be calculated. ${\displaystyle f(x)=0}$

Procedure

A secant is placed between two points and the function . The intersection of the secant with the axis is used as an improved starting value for the iteration . Using the new function value is calculated. This step is repeated with and the old value and a secant is applied again. This step is repeated until a sufficient approximation of the searched zero has been achieved. ${\displaystyle P(x_{1}|f(x_{1}))}$ ${\displaystyle Q(x_{2}|f(x_{2}))}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle x_{3}}$ ${\displaystyle x_{3}}$ ${\displaystyle f(x_{3})}$ ${\displaystyle f(x_{3})}$ ${\displaystyle f(x_{2})}$

Construction on the graph

The following animation shows how the starting values and other points are constructed. ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$

The procedure uses the following iteration rule :

${\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}}\cdot f(x_{n})}$

It starts with two approximate values . ${\displaystyle x_{0},x_{1}}$

In contrast to the regular falsi method, with the secant method it can occur that the zero point is no longer between and for some iteration steps . ${\displaystyle x_{n}}$ ${\displaystyle x_{n+1}}$

Connection with the Newton method

The method can be described as a modification of Newton's approximation method with the iteration rule

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}$

understand it by taking the derivative by the difference quotient ${\displaystyle f'(x_{n})}$

${\displaystyle f'(x_{n})\approx {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}}$

replaced.

convergence

Due to the relationship with Newton's method, similar conditions apply to the convergence of the secant method:

• The secant method converges superlinearly with the order of convergence (this corresponds to the ratio of the golden section ), i.e. H. the number of correct digits of the approximate value increases approximately by the factor per pass . This is due to the fact that the difference quotient is only an approximation for the derivative; The speed of convergence is correspondingly lower compared to the quadratic convergent Newton method. ${\displaystyle \Phi ={\tfrac {1+{\sqrt {5}}}{2}}\approx 1{,}618}$ ${\displaystyle \Phi }$

• It is sufficient that the function is continuous in the definition range and has exactly one zero . ${\displaystyle f}$

• The method loses accuracy and speed of convergence when the derivative at the zero point becomes 0, since the calculation results in an expression of the shape . Especially with polynomials this corresponds to a multiple zero. ${\displaystyle f'(x)}$ ${\displaystyle x_{n+1}=x_{n}-{\tfrac {0}{0}}\cdot f(x_{n})}$

• In the numerical calculation the problem arises that the difference quotient

${\displaystyle {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}}$

changes into the form 0/0 as the number approaches the zero by deleting the digits. While the method itself could continue to improve the estimate for the zero point, in the actual calculation this gain is overcompensated in the vicinity of the zero point by increasing rounding errors. As a result, on computers with a finite number of digits, the accuracy of Newton's method cannot be achieved with the secant method.

Advantages of the procedure

There are several advantages over Newton's method:

• Only the function values ​​have to be calculated. In contrast to the Newton iteration, the zeros of any desired, sufficiently smooth function can be calculated without knowledge or calculation of the derivatives.

• Only the function value has to be calculated once for each iteration step . With the Newton method, the function value of the derivative must also be determined. ${\displaystyle f(x)}$ ${\displaystyle f'(x)}$

• By specifying two starting values, the method can be better focused on a specific interval, since the direction of the secant is given by the two starting values. However, this cannot force convergence.

The secant method in the multi-dimensional

Analogous to the multi-dimensional Newton method , a multi-dimensional secant method can also be defined to determine the zeros of functions . ${\displaystyle f\colon D\subset \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$

If in the one-dimensional the derivative was approximated by the difference quotient, in the multi-dimensional the Jacobi matrix is approximated:

${\displaystyle J(x):={\frac {\partial f_{i}}{\partial x_{j}}}={\begin{pmatrix}{\frac {\partial f_{1}}{\partial x_{1}}}&{\frac {\partial f_{1}}{\partial x_{2}}}&\ldots &{\frac {\partial f_{1}}{\partial x_{n}}}\\{\frac {\partial f_{2}}{\partial x_{1}}}&{\frac {\partial f_{2}}{\partial x_{2}}}&\ldots &{\frac {\partial f_{2}}{\partial x_{n}}}\\\vdots &\vdots &\ddots &\vdots \\{\frac {\partial f_{n}}{\partial x_{1}}}&{\frac {\partial f_{n}}{\partial x_{2}}}&\ldots &{\frac {\partial f_{n}}{\partial x_{n}}}\end{pmatrix}}\approx {\tilde {J}}(x,h)=(F(x,h)_{jk})_{j,k\in \{1,\dotsc ,n\}}}$,

where for a given step size matrix is defined by: ${\displaystyle F(x,h)_{jk}}$ ${\displaystyle h\in \mathbb {R} ^{n\times n}}$

${\displaystyle F(x,h)_{jk}:={\begin{cases}{\frac {\partial f_{j}}{\partial x_{k}(x)}},&{\text{falls }}h_{jk}=0\\{\frac {f_{j}(x+h_{jk}e_{k})-f_{j}(x)}{h_{jk}}},&{\text{sonst}}\end{cases}}}$, provided is. ${\displaystyle x,x+h_{jk}e_{k}\in D}$

Analogous to the Newton method, the following iteration rule now results:

${\displaystyle x_{n+1}=x_{n}-({\tilde {J}}(x_{n},h))^{-1}\cdot f(x_{n})}$

Since solving

${\displaystyle \Delta x_{n}:=({\tilde {J}}(x_{n},h))^{-1}f(x_{n})\;,}$

via the calculation of the inverse of a matrix and subsequent multiplication with more time- consuming and numerically less favorable, the linear system of equations is used instead ${\displaystyle f(x_{n})}$

${\displaystyle {\tilde {J}}(x_{n},h)\;\Delta x_{n}=f(x_{n})}$

solved. Then we get from: ${\displaystyle x_{n+1}}$

${\displaystyle x_{n+1}=x_{n}-\Delta x_{n}.}$

literature

• Martin Hanke-Bourgeois: Fundamentals of numerical mathematics and scientific computing. 1st edition. Teubner, Stuttgart 2002, ISBN 3-519-00356-2 , chapter 18.2.

Web links

• Explanation of the math nexus
• Brief description