کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952084 1442008 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Accelerated approximation of the complex roots and factors of a univariate polynomial
ترجمه فارسی عنوان
تقریب زدایی از ریشه های پیچیده و عوامل چندجملهای یکنواخت
کلمات کلیدی
معادله چند جمله ای، ریشه ها، پیدا کردن ریشه، پالایش ریشه، مبلغ برق، پیچیدگی،
ترجمه چکیده
الگوریتم های پان (1995) [20] و پان (2002) [22] ریشه های چندجملهای چندجملهای پیچیده را در زمان تقریبی بهینه و زمان بولی تقریب می یابند اما نیاز به دقت محاسباتی دارند که بیش از درجه چند جمله ای است. این مسئله سبب ایجاد مشکلات ثبات عددی می شود. با این وجود ما متوجه می شویم که چنین مشکل در مرحله اولیه الگوریتم ها ناپدید می شود و در مقاله حاضر ما این مرحله را به ریشهابی شدن در محدوده پیچیدگی ریاضی تقریبا مطلوب و پیچیدگی بولی گسترش می دهیم، در صورتی که برخی از جداسازی اولیه ریشه های چندجملهای ورودی تضمین شده است. علاوه بر این، الگوریتم ما برای تقریب ریشه های جدا شده در یک دیسک ثابت، مربع یا یک منطقه دیگر در فضای پیچیده تقریبا مطلوب است و نه همه ریشه های پیچیده یک چندجملهای. علاوه بر این الگوریتم را می توان به یک چندجملهای داده شده توسط یک جعبه سیاه برای ارزیابی آن (حتی اگر ضرایب آن شناخته شده نیست) استفاده شود. آن را وعده می دهد که ارزش عملی برای یافتن ریشه های چندجمله ای و فاکتور زدن باشد، وظیفه دوم که به نفع خودش است. ما با خلاصه الگوریتم های ما و گسترش آنها به تقریب ریشه های چندگانه جدا شده و خوشه های ریشه نتیجه می گیریم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
تقریب زدایی از ریشه های پیچیده و عوامل چندجملهای یکنواخت
چکیده انگلیسی
The algorithms of Pan (1995) [20] and Pan (2002) [22] approximate the roots of a complex univariate polynomial in nearly optimal arithmetic and Boolean time but require a precision of computing that exceeds the degree of the polynomial. This causes numerical stability problems when the degree is large. We observe, however, that such a difficulty disappears at the initial stage of the algorithms, and in our present paper we extend this stage to root-finding within a nearly optimal arithmetic and Boolean complexity bounds provided that some mild initial isolation of the roots of the input polynomial has been ensured. Furthermore our algorithm is nearly optimal for the approximation of the roots isolated in a fixed disc, square or another region on the complex plane rather than all complex roots of a polynomial. Moreover the algorithm can be applied to a polynomial given by a black box for its evaluation (even if its coefficients are not known); it promises to be of practical value for polynomial root-finding and factorization, the latter task being of interest on its own right. We conclude with summarizing our algorithms and their extension to the approximation of isolated multiple roots and root clusters.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 681, 12 June 2017, Pages 138-145
نویسندگان
, ,