حساب جذور متعددات لاغير–سوبوليف بواسطة طريقة إيرليش–أبيرث Computation of the zeros of Laguerre–Sobolev polynomials by the Ehrlich–Aberth method

شارك:
المجلة: Numerical Algorithms
DOI: https://doi.org/10.1007/s11075-026-02495-5
تاريخ النشر: 2026-09-25
المؤلف: Teresa Laudadio وآخرون
الموضوع الرئيسي: الدوال الرياضية والمتعددات الحدود

نظرة عامة

تقدم هذه القسم خوارزمية جديدة لحساب جميع جذور متعددة الحدود لاغير-سوبوليف، باستخدام طريقة إيرليش-أبيرث، وهي نهج مشابه لنيوتن. تتطلب هذه الطريقة تقييم كل من متعددة الحدود ومشتقتها في كل تكرار بناءً على الجذور المقدرة. يتم تعريف متعددة الحدود لاغير-سوبوليف من خلال علاقة تكرارية مكونة من أربعة حدود تسهل حساب هذه متعددة الحدود ومشتقاتها عند نقاط معينة، والتي يتم الاستفادة منها في تنفيذ طريقة إيرليش-أبيرث.

تسلط الدراسة الضوء على أن متعددة الحدود لاغير-سوبوليف تشترك في خصائص نمو مشابهة مع متعددة الحدود لاغير الكلاسيكية، مما يؤدي إلى احتمال حدوث تجاوز في الحسابات العائمة عندما يتجاوز درجة متعددة الحدود 170. للتخفيف من هذه المشكلة، يقترح المؤلفون علاقات تكرارية جديدة تمكن من الحساب المتزامن للنسبة بين متعددة الحدود لاغير-سوبوليف ومشتقاتها. تظهر الخوارزمية الناتجة كفاءة عالية ودقة، حيث تحقق تعقيد حسابي قدره \(O(n^2)\) ومتطلبات ذاكرة قدرها \(O(n)\)، حيث \(n\) تشير إلى درجة متعددة الحدود.

مقدمة

تناقش مقدمة الورقة البحثية الاهتمام المتزايد في متعددة الحدود سوبوليف، خاصة في تطبيقاتها على الطرق الطيفية لمشاكل القيمة الحدودية في المعادلات التفاضلية وتقريبها السلس. يركز هذا العمل على حساب الجذور لمتعددة الحدود لاغير-سوبوليف، التي تتميز بأنها حقيقية وبسيطة. يقدم المؤلفون خوارزمية تعتمد على طريقة إيرليش-أبيرث، وهي نهج مشابه لنيوتن يتطلب تقييم متعددة الحدود ومشتقتها في كل تكرار.

تتمثل إحدى التحديات الكبيرة التي تم تناولها في هذه الدراسة في النمو السريع لمتعددة الحدود لاغير-سوبوليف مع زيادة الدرجة، مما يؤدي إلى احتمال حدوث تجاوز في الحسابات العائمة عندما تتجاوز الدرجة 170. للتخفيف من هذه المشكلة، يقترح المؤلفون علاقات تكرارية جديدة تسمح بالحساب المباشر للنسبة بين متعددة الحدود لاغير-سوبوليف ومشتقاتها، مما يعزز كل من الكفاءة والدقة مع تعقيد حسابي قدره \(O(n^2)\) واستخدام ذاكرة قدره \(O(n)\). يحدد المخطوط هيكل الورقة، موضحًا ميزات متعددة الحدود لاغير ولاغير-سوبوليف، وطريقة إيرليش-أبيرث، والاختبارات العددية التي تقارن الخوارزمية المقترحة بالطرق الحالية.

نقاش

في هذا القسم، يناقش المؤلفون خصائص متعددة الحدود لاغير المونك وعلاقتها مع متعددة الحدود لاغير-سوبوليف، والتي تعتبر أساسية لتطوير خوارزمية لحساب الجذور الأخيرة. تُعرف متعددة الحدود لاغير المونك، الممثلة بـ $L^{(\alpha)}_j(x)$، بأنها متعامدة بالنسبة لمنتج داخلي محدد وتفي بعلاقة تكرارية مكونة من ثلاثة حدود. يستنتج المؤلفون علاقة تكرارية مماثلة لمشتقات هذه متعددة الحدود، والتي تعتبر حاسمة لإقامة روابط مع متعددة الحدود لاغير-سوبوليف، $Q_j^{(\alpha)}(x)$. هذه متعددة الحدود متعامدة تحت منتج داخلي سوبوليف، ويبرز المؤلفون أن $Q_j^{(\alpha)}(x)$ لديها بالضبط $n$ جذور حقيقية متميزة، مع كون على الأقل $n-1$ إيجابية عندما تكون $\alpha \geq 0$.

يستعرض القسم أيضًا طريقة مشابهة لنيوتن، وتحديدًا طريقة إيرليش-أبيرث، لحساب الجذور لـ $Q_j^{(\alpha)}(x)$. تستفيد هذه الطريقة من خاصية التداخل لجذور متعددة الحدود لاغير ولاغير-سوبوليف، مما يسمح بتقديرات أولية فعالة. ومع ذلك، يشير المؤلفون إلى أن قيم $Q_j^{(\alpha)}(x)$ ومشتقتها تنمو بسرعة، مما يؤدي إلى تجاوز حسابي لـ $n > 170$. لمعالجة ذلك، يستنتجون علاقات تكرارية لنسب هذه متعددة الحدود، مما يسهل الحساب دون تقييم متعددة الحدود نفسها مباشرة. تظهر الخوارزمية المقترحة تعقيدًا حسابيًا قدره $O(n^2)$ وتظهر دقة محسنة مقارنة بالطرق الحالية، كما يتضح من الاختبارات العددية.

Journal: Numerical Algorithms
DOI: https://doi.org/10.1007/s11075-026-02495-5
Publication Date: 2026-09-25
Author(s): Teresa Laudadio et al.
Primary Topic: Mathematical functions and polynomials

Overview

This section presents a novel algorithm for calculating all zeros of Laguerre-Sobolev orthogonal polynomials, utilizing the Ehrlich-Aberth method, which is a Newton-like approach. This method necessitates the evaluation of both the polynomial and its derivative at each iteration based on the approximated zeros. The Laguerre-Sobolev polynomials are defined through a four-term recurrence relation that facilitates the computation of these polynomials and their derivatives at specific points, which is leveraged in the implementation of the Ehrlich-Aberth method.

The study highlights that Laguerre-Sobolev polynomials share similar growth characteristics with classical Laguerre polynomials, leading to potential overflow in floating-point arithmetic when the polynomial degree exceeds 170. To mitigate this issue, the authors propose new recurrence relations that enable the simultaneous computation of the ratio between the Laguerre-Sobolev polynomials and their derivatives. The resulting algorithm demonstrates high efficiency and accuracy, achieving a computational complexity of \(O(n^2)\) and a memory requirement of \(O(n)\), where \(n\) denotes the degree of the polynomial.

Introduction

The introduction of the paper discusses the growing interest in Sobolev polynomials, particularly in their applications to spectral methods for boundary value problems in differential equations and their smooth approximations. The focus of this work is on the computation of the zeros of Laguerre-Sobolev polynomials, which are characterized as real and simple. The authors present an algorithm based on the Ehrlich-Aberth method, which is a Newton-like approach that necessitates the evaluation of the polynomial and its derivative at each iteration.

A significant challenge addressed in this study is the rapid growth of Laguerre-Sobolev polynomials with increasing degree, leading to potential overflow in floating-point arithmetic when the degree exceeds 170. To mitigate this issue, the authors propose novel recurrence relations that allow for the direct computation of the ratio between the Laguerre-Sobolev polynomials and their derivatives, enhancing both efficiency and accuracy with a computational complexity of \(O(n^2)\) and memory usage of \(O(n)\). The manuscript outlines the structure of the paper, detailing the features of Laguerre and Laguerre-Sobolev polynomials, the Ehrlich-Aberth method, and numerical tests comparing the proposed algorithm to existing methods.

Discussion

In this section, the authors discuss the properties of monic Laguerre polynomials and their relationship with Laguerre-Sobolev polynomials, which are essential for developing an algorithm to compute the zeros of the latter. Monic Laguerre polynomials, denoted as $L^{(\alpha)}_j(x)$, are orthogonal with respect to a specific inner product and satisfy a three-term recurrence relation. The authors derive a similar recurrence relation for the derivatives of these polynomials, which is crucial for establishing connections with Laguerre-Sobolev polynomials, $Q_j^{(\alpha)}(x)$. These polynomials are orthogonal under a Sobolev inner product, and the authors highlight that $Q_j^{(\alpha)}(x)$ has exactly $n$ distinct real zeros, with at least $n-1$ being positive when $\alpha \geq 0$.

The section further details a Newton-like method, specifically the Ehrlich-Aberth method, for computing the zeros of $Q_j^{(\alpha)}(x)$. This method benefits from the interlacing property of the zeros of Laguerre and Laguerre-Sobolev polynomials, allowing for effective initial approximations. However, the authors note that the values of $Q_j^{(\alpha)}(x)$ and its derivative grow rapidly, leading to computational overflow for $n > 170$. To address this, they derive recurrence relations for the ratios of these polynomials, which facilitate the computation without directly evaluating the polynomials themselves. The proposed algorithm demonstrates a computational complexity of $O(n^2)$ and shows improved accuracy compared to existing methods, as evidenced by numerical tests.