No label defined (Q3345694)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3880013
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3880013 |
Statements
1984
0 references
Kuhn's algorithm
0 references
Newton's method
0 references
cost estimate
0 references
polynomial
0 references
0.8309379816055298
0 references
In this paper, a comparison is made between S. Smale's cost estimate for Newton's method and the authors' cost estimate for Kuhn's algorithm, both in finding zeros of complex polynomials. Sec. 2 discusses the topological construction of Kuhn's algorithm and presents an improvement of Kuhn's error estimate as follows. Theorem 2.1 If \(\{z^ 1,z^ 2,z^ 3\}\) is a triple with \(\text{diam}\;\{z^ 1,z^ 2,z^ 3\}=\delta\) completely labelled by \(f\), then the distance between zeros of \(f\) and the triple is not greater than \(3n\delta/4\). The result on cost estimate is established in Sec. 3. The main results on cost are theorem 3.1 and corollary 3.1. Theorem 3.1. Suppose \(\varepsilon >0\) is given and stands for the accuracy demand for resulting zeros. Then the total number of \(f\)-evaluations needed to find all the zeros of the polynomial when Kuhn's algorithm is used, is at most \[ \pi [5M^ 2+28n(1+0.75n)^ 2\lceil \log_ 2(3\sqrt{2n}/4\varepsilon)\rceil], \] where \(M=\max \{3\sqrt{2}(2+\pi)n/4\pi,n/(n-1)\cdot \max | a_ K| +1\}+\sqrt{2}\) and \(f(z)=z^ n+a_ 1z^{n-1}+\ldots+a_ n.\) Corollary 3.1. The average cost of finding a zero is at most \[ \pi [5M^ 2/n+28(1+0.75n)^ 2\lceil \log_ 2(3\sqrt{2n}/4\varepsilon)\rceil]. \] Sec. 4 introduces some results to show the meaning and the existence of approximate zeros. The last section develops a comparison of costs of finding approximate zeros with Smale-applied Newton's method and Kuhn's algorithm. Conclusion: Kuhn's algorithm is much better than Newton's method both in finding zeros and in finding approximate zeros.
0 references