محاسبه‌ی چندجمله‌ای‌های لاگرانژ به روش بازگشتی با استفاده از نقاط گرهی چبیشف

در مباحث مربوط به تئوری تقریب، برای تقریب زدن یک تابع پیچیده با استفاده از یک چندجمله‌ای، از درون‌یابی استفاده‌می‌شود. برای به‌دست‌آوردن ضابطه‌ی چندجمله‌ای مورد نظر از روش‌های مختلفی می‌توان استفاده‌کرد. یکی از روش‌های مرسوم در محاسبه‌ی چندجمله‌های درون‌یاب، روش درون‌یابی لاگرانژ است. به علاوه در این نوع مسائل نحوه‌ی توزیع نقاط گرهی یکی از عوامل تاثیرگذار بر دقت درون‌یابی است؛ به عنوان مثال اگر برای تقریب‌زدن یک تابع با استفاده از چندجمله‌ای‌ها، از نقاط گرهی هم‌فاصله استفاده‌شود، دقت درون‌یابی در ابتدا و انتهای بازه‌ی نمونه‌برداری مطلوب‌نخواهدبود. برای غلبه بر این مشکل باید نحوه‌ی توزیع نقاط گرهی به گونه‌ای باشد که در ابتدا و انتهای بازه‌ی درون‌یابی نسبت به مرکز بازه از تراکم بیشتری برخوردار باشند. یک نمونه از مجموعه‌ نقاطی با این شرایط، مجموعه‌ی ریشه‌های چندجمله‌ای‌های چبیشف هستند که به نقاط گرهی چبیشف معروف‌اند. با استفاده از این نقاط به عنوان نقاط گرهی، دامنه‌ی نوسان‌های چندجمله‌ای در دو طرف بازه‌ی درون‌یابی بسیار کوچک‌ خواهدبود که این مساله موجب افزایش دقت درون‌یابی می‌شود. با توجه به کاربردهای ذکرشده برای استفاده از نقاط چبیشف در این نوع مسائل درون‌یابی، در این مقاله یک رابطه‌ی بازگشتی برای محاسبه‌ی توابع پایه‌ی لاگرانژ با استفاده از این نقاط ارائه‌می‌شود. با استفاده از این روش تعداد عملگرهای محاسباتی مورد نیاز جهت به‌دست‌آوردن توابع پایه‌ی لاگرانژ، تا حد قابل‌توجهی کاهش‌می‌یابد. از این رو انتظار می‌رود که با به‌کارگیری این روش ، سرعت انجام محاسبات در فرآیند درون‌یابی افزایش‌یابد. برای بررسی این مساله در ادامه‌ی مقاله، توابع پایه‌ی لاگرانژ در یک مساله‌ی درون‌یابی با استفاده از هر دو روش محاسبه‌شدند. پس از محاسبه‌ی این توابع برای تمام اعداد صحیح در بازه‌ی ]1000,1[ و برای چندجمله‌ای‌های از درجه‌ی 1 تا 10، مشخص‌شد که استفاده از روش بازگشتی در محاسبات، تا چند برابر سریع‌تر از روش معمولی است؛ به گونه‌ای که برای چندجمله‌ای درجه‌ی 1 روش بازگشتی 1.3 برابر سریع‌تر از روش معمولی بوده‌است. با افزایش درجه‌ی چندجمله‌ای این اختلاف افزایش‌یافته و برای چندجمله‌ای درجه‌ی 10 روش بازگشتی تا 3 برابر سریع‌تر از الگوریتم معمولی عمل‌کرده‌است؛ بنابراین استفاده از روش ارائه‌شده به خصوص در مواردی که از چندجمله‌ای‌های با درجات بالا برای درون‌یابی استفاده‌می‌شود، کاملاً توجیه‌پذیر است.

A Recursive Algorithm to Determining Lagrange Basis Polynomial Using Chebyshev Nodes

Interpolation is the process of estimating unknown values that are located between known values. Usually this process is done using different kinds of continuous functions. One of the most common types of continuous functions which can be used for interpolation, are polynomials. In approximation theory polynomial interpolation is utilized to approximating a complex function using a polynomial. In this issue polynomial coefficients can be determined using different computing methods. The basic procedure to determining the coefficients, is solution of vandermonde system. The system however, has only theoretical significance, since its solution by numerical methods is illadvised on all counts (computational effort, storage requirement, accuracy). This is the reason to using some alternative methods such as Newton and Lagrange. These methods are two wellknown representations of the unique interpolation polynomial. Newton representation is based on determining divided differences, while the other one is a very elegant alternative representation of Newtons general formula that does not require the computation of finite or divided differences. Lagrange representation can be utilized for any sets of interpolating points. In some cases Lagrange representation is used for interpolating between equidistant nodes. For example in GNSS positioning it is a common issue to find the satellites position using the coordinates are given in 15 minutes constant interval. generally computing Lagrange basis polynomial using current method requires O(n2) operations. So when we use polynomials with high degrees for interpolation, we expect a significant increase of computational effort. According to this issue in the last article we introduced a recursive algorithm to obtaining Lagrange coefficients using equidistant nodes. By the use of this algorithm, we had a significant improvement in computations speed. Despite the usage of equidistant interpolation, it is not a good idea to use evenly spaced points to approximating a function. Because in such a situation interpolated polynomial has wild oscillations near the edges of interpolation interval and does not converge to the main function, specially in high order polynomials. This nonconvergence is called Runge phenomenon. To avoiding this problem, other sets of interpolating points should be used, with more density at the end points of interval. The simplest examples of such a point sets, are the families of Chebyshev points. These points are set of zeros of the Chebyshev polynomial. By using Chebyshev nodes, interpolation will be more accurate. Since unwanted oscillations are gone. Due to the mentioned advantages of Chebyshev nodes, in this paper we are going to introduce a recursive algorithm to obtaining Lagrange coefficients using these sets of points. computing Lagrange basis polynomial using this method requires O(n) operations unlike the current method. So by the use of recursive algorithm, we expect speed increase in computations process. To investigating this issue we obtained Lagrange basis polynomial for all integer numbers within [1,1000] interval. All of coefficients were computed for different polynomial degrees from 1 to 10 using MATLAB. In the following we recorded calculating times for both of computing algorithms and also for different polynomial degrees. After checking computing times we found a significant increase in processing speed by the use of recursive method. Although this method reduces processing time for all polynomial degrees, it is more effective when we use polynomials with high degrees. In other words when we use a polynomial with degree of one, the recursive algorithm is 1/3 times faster in comparison with usual algorithm; But when we use a polynomial in degree of 10, it is 3 times faster. So we conclude that it is logical to use this algorithm specially when we use high degree polynomials for interpolation.