کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
473171 698775 2012 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient polynomial root-refiners: A survey and new record efficiency estimates
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Efficient polynomial root-refiners: A survey and new record efficiency estimates
چکیده انگلیسی

A typical iterative polynomial root-finder begins with a relatively slow process of computing a crude but sufficiently close initial approximation to a root and then rapidly refines it. The policy of using the same iterative process at both stages of computing an initial approximation and refining it, however, is neither necessary nor most effective. The efficiency of an iteration at the former stage resists formal study and is usually decided empirically, whereas formal study of the efficiency at the latter stage of refinement is not hard and is the subject of the current paper. We define this local efficiency as log10qd=log10(q1/d) (qq is the convergence order, and dd is the number of function evaluations per iteration); it is inversely proportional to the number of flops involved. Assuming that about 2n2n flops are needed per evaluation of a polynomial of a degree nn at a single point, we extend the definition to cover the recent matrix methods for polynomial root-finding as well as some methods that combine nn approximations to all nn roots to refine them simultaneously. For the approximation of a single root of a polynomial of degree nn, the maximum local efficiency achieved so far is log102≈0.301…log102≈0.301…, but we show its growth to infinity for simultaneous approximation of all nn roots as nn grows to infinity.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Mathematics with Applications - Volume 63, Issue 1, January 2012, Pages 239–254
نویسندگان
, ,