Simple rational approximation: Difference between revisions

Revision as of 22:13, 3 May 2006

Revision as of 00:38, 4 May 2006

Line 3:

The main application of SRA lies in finding the [[Root (mathematics)|zeros]] of [[secular function|secular functions]]. A divide-and-conquer algorithm to find the [[eigenvalues]] and [[eigenvectors]] for various kinds of [[matrices]] is well-known in [[numerical analysis]]. In a strict sense, SRA implies a specific [[interpolation]] using simple rational functions as a part of the divide-and-conquer algorithm. Since such secular functions consist of a series of rational functions with simple poles, SRA is the best candidate to interpolate the zeros of the secular function. Moreover, based on previous researches, a simple zero that lies between two adjacent poles can be considerably well interpolated by using a two-dominant-pole rational function as an approximating function.

==Halley's formularformula==

The origin of the interpolation with rational functions can be found in the previous work done by [[Edmond Halley]]. The Helley's formularformula is known as one-point third-order iterative method to solve <math>\,f(x)=0</math> by means of approximating a rational function defined by

:<math>h(z)=\frac{a}{z+b}+c.</math>

We can determine a, b, and c so that

Line 10:

Then solving <math>\,h(z)=0</math> yields the iteration

:<math>x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)} \left({\frac{1}{1-\frac{f(x_n)f''(x_n)}{2(f'(x_n))^2}}}\right).</math>

This is referred to as Helley's formularformula.

This ''geometrical interpretation'' was derived by Gander(1978), where the equivalent iteration also was derived by apply Newton's method to

:<math>g(x)=\frac{f(x)}{\sqrt{f'(x)}}=0.</math>

We call this ''algebraic interpretation'' of Halley's formula.

Similarly, we can obtainderive a variation of Halley's formula based on a one-point ''second-order'' iterative method to solve <math>\,f(x)=\alpha(\neq 0)</math> using simple rational approximation by

:<math>h(z)=\frac{a}{z+b}.</math>

Then we need to evaluate