روش نویل

Neville's Algorithm
nevilleالگوریتم نویل در میانیابی نقاط
معرفی

روش نویل یک الگوریتم ریاضی جهت محاسبه ی درونیابی چندجمله ای است که توسط ریاضی دان برجسته Eric Harold Neville استخراج گردیده است. با داشتن n+1 نقطه، تنها یک چندجمله ای منحصربفرد با درجه ی حداکثر n می توان یافت که از تمام این نقاط عبور می نماید. الگوریتم نویل این چندجمله ای را می یابد.

در این الگوریتم ابتدا یک چندجمله ای از درجه ی صفر از نقاط مختلف (x_k,y_k) به ازای k=1, ..., n به صورت P_k(x)=y_k عبور می دهد. در تکرار بعدی مقادیر P_i و P_{i+1} به گونه ای با هم ترکیب می شوند که دو نقطه ی مربوط را میانیابی نمایند، که منجر به محاسبه ی مقادیر P_{12}, P_{23}, ... می گردد:

P_{i~j}(x)={(x_j-x)p_{i,j-1}(x)+(x-x_i)p_{i+1,j}(x)}/{x_j-x_i}, ~~ i<j

این روند به صورت تکراری انجام می گردد تا یک هرم از مقادیر تقریبی ایجاد گردد و در نهایت دقیقترین مقدار در قله ی هرم بدست بیاید:

matrix{4}{1}{P_1 P_2 P_3 P_4}~~matrix{3}{1}{P_{12} P_{23} P_{34}}~~matrix{2}{1}{P_{123} P_{234}}~~P_{1234}~

    برنامه نویسی با MATLAB

    در اینجا با استفاده از نرم افزار متلب (MATLAB) برنامه ای جهت محاسبه ی مقدار عرض از مبداء یک نقطه ی طولی مشخص در بازه ی نقاط داده شده با استفاده از الگوریتم نویل (Neville) ارائه گردیده است. کدی که برای این منظورنوشته شده است با دریافت نقاط ورودی، جدول کامل الگوریتم نویل و همچنین پاسخ نهایی را در خروجی نمایش می دهد.

    لازم به ذکر است که برنامه ی ارائه شده قادر به حل تمامی مثال های قابل حل با این روش عددی و دریافت هر تعداد ورودی مورد نظر کاربران گرامی بوده و به صورت کاملا عمومی (general) کدنویسی شده اند.

    ورودی ها و خروجی ها

    ورودی:

    1. طول از مبداء نقاط داده ی ورودی به شکل [x3  x2  x1  …]
    2. عرض از مبداء نقاط داده ی ورودی به شکل [y3  y2  y1  …]

    خروجی:

    1. جدول مقادیر الگوریتم نویل
    2. پاسخ نهایی مقدار درونیابی شده

    تصاویر اجرای برنامه

    مشاهده ی ورودی و خروجی برنامه در یک مثال نمونه

    این برنامه با نسخه های متلب/MATLAB سال های 2010-2013 تست شده است. در صورت استفاده از نسخه ی سال های دیگر لایبریکا تضمین کننده ی اجرای صحیح برنامه نمی باشد.