استيفاء خطي

النقطتان الحمراوتان معلومتان. الخط المستقيم الأزرق هو الخط المستوفي بينهما. يمكن إيجاد قيمة y عند x باستعمال الاستيفاء الخطي.

فِي الرِّياضيَّات، الاسْتيفاء الخطِّيّ (بالانجليزية:Linear interpolation) هُو طَرِيقَة لِتوْفِيق المنْحنيات بِاسْتخْدام مُتعدِّدات اَلحُدود الخطِّيَّة لِبناء نِقَاط بيانَات جَدِيدَة ضِمْن نِطَاق مَجمُوعة مِن البيانات المعْروفة.

الاستيفاء الخطي بين نقطتين معروفتين[عدل]

إذا كانتا النقطتين المعروفتين ممثلتين بالإحداثيات $(x_{0},y_{0})$ وَ $(x_{1},y_{1})$ , فإن الخط المستوفي هو الخط المستقيم بين هاتين النقطتين. لقيمة $x$ في الفترة $(x_{0},x_{1})$ , تُعطى القيمة $y$ على طول الخط المستقيم من معادلة الميلات ${\frac {y-y_{0}}{x-x_{0}}}={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}},$ والتي يمكن استنتاجها هندسياً من الشكل على اليسار. إنها حالة خاصة من استيفاء متعدد الحدود بقيمة $n=1$ .

حل هذه المعادلة لـ $y$ , وهي القيمة المجهولة في $x$ , يعطي ${\begin{aligned}y&=y_{0}+(x-x_{0}){\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\\&={\frac {y_{0}(x_{1}-x_{0})}{x_{1}-x_{0}}}+{\frac {y_{1}(x-x_{0})-y_{0}(x-x_{0})}{x_{1}-x_{0}}}\\&={\frac {y_{1}x-y_{1}x_{0}-y_{0}x+y_{0}x_{0}+y_{0}x_{1}-y_{0}x_{0}}{x_{1}-x_{0}}}\\&={\frac {y_{0}(x_{1}-x)+y_{1}(x-x_{0})}{x_{1}-x_{0}}},\end{aligned}}$ وهو الصيغة للاستيفاء الخطي في الفترة $(x_{0},x_{1})$ . خارج هذه الفترة، تكون الصيغة متطابقة مع استكمال خارجي.

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

${\textstyle 1-(x-x_{0})/(x_{1}-x_{0})}$ وَ ${\textstyle 1-(x_{1}-x)/(x_{1}-x_{0})}$ , والتي تمثل المسافات الموحدة بين النقطة المجهولة وكل من النقاط النهائية. لأن هذه المجموعة تساوي 1، ${\begin{aligned}y&=y_{0}\left(1-{\frac {x-x_{0}}{x_{1}-x_{0}}}\right)+y_{1}\left(1-{\frac {x_{1}-x}{x_{1}-x_{0}}}\right)\\&=y_{0}\left(1-{\frac {x-x_{0}}{x_{1}-x_{0}}}\right)+y_{1}\left({\frac {x-x_{0}}{x_{1}-x_{0}}}\right)\\&=y_{0}\left({\frac {x_{1}-x}{x_{1}-x_{0}}}\right)+y_{1}\left({\frac {x-x_{0}}{x_{1}-x_{0}}}\right)\end{aligned}}$ مما يعطي الصيغة للاستيفاء الخطي المذكورة أعلاه.

استيفاء مجموعة بيانات[عدل]

يتكون الاستيفاء الخطي على مجموعة من نقاط البيانات (النقاط الحمراء) من قطع الاستيفاء الخطي (الخطوط الزرقاء). الاستيفاء الخطي على مجموعة من نقاط البيانات $(x 0, y 0), (x 1, y 1), ..., (x n, y n)$ يُعرَّف كخطي قطعة قطعة، ناتج عن اتحاد قطع مستقيمة الاستيفاء بين كل زوج من نقاط البيانات. وينتج عن ذلك منحنى مستمر، ولكنه يكون له تفاضل متقطع (بشكل عام)، وبالتالي من الفصل التفاضلي $C^{0}$ .

الاستيفاء الخطي كتقريب[عدل]

الاستيفاء الخطي يستخدم غالبا لتقريب قيمة دالة $f$ باستخدام قيمتين معروفتين لتلك الدالة في نقاط أخرى. يتم تعريف خطأ هذا التقريب كما يلي.

$R_{T}=f(x)-p(x),$

حَيْث يُمثِّل $p$ متعدد الحدود لِلاسْتيفاء الخطِّيِّ اَلمُعرف أَعلَاه:

$p(x)=f(x_{0})+{\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}(x-x_{0}).$

يُمْكِن أن يَتِم إِثْباته بِاسْتخْدام مُبَرهنَة رُول أَنَّه إِذَا كان لَدى الدَّالَّة $f$ مُشْتقَّة ثَانِية مُسْتمِرَّة ، فَإِن الخطأ مَحصُور بِواسِطة

$|R_{T}|\leq {\frac {(x_{1}-x_{0})^{2}}{8}}\max _{x_{0}\leq x\leq x_{1}}\left|f''(x)\right|.$

صحيح ، يُصْبِح التَّقْريب بَيْن نُقْطتَيْنِ على دَالَّة مُعَينَة أَسوَأ مع تَزايُد المشْتقَّة الثَّانية لِلدَّالَّة المقرَّبة وَهذَا مَنطقِي أيْضًا : كُلمَا كَانَت الدَّالَّة أَكثَر اِنحِناء ، زاد سُوء التَّقْريبات اَلتِي يَتِم إِجْراؤهَا بِاسْتخْدام الاسْتيفاء الخطِّيِّ اَلبسِيط . . .

التاريخ والتطبيقات[عدل]

الاستيفاء الخطي قد استُخدم منذ العصور القديمة لملء الفجوات في الجداول. لنفترض أن لدينا جدول يُدرج فيهِ تعداد سكان بلد ما في 1970 وَ1980 وَ1990 وَ2000، وَنريدُ تقدير تعداد السكان في عام 1994. يأتي دور الاستيفاء الخطي كوسيلة سهلة للقيامِ بذلك. يُعتقد أنه تم استخدامه في الإمبراطورية السلوقية (ثلاثة قرون الأخيرة قبلَ الميلاد) ومِن قِبَل عالم الفلك وَالرياضي اليُوناني أبرخش (القرن الثاني قبلَ الميلاد). يمكن العثور على تفسير للاستيفاء الخطي في النص الرياضي الصيني القديم المسمى "الفصول التسعة في الفن الرياضي ^{[الإنجليزية]}" (九章算術)،^[1] المؤرخ مابين 200 قبل الميلاد وَ100 ميلادي، وفي "المجسطي" (القرن الثاني الميلادي) لبطليموس.

غالبًا ما تُستَعملُ العملية الأساسية للاستيفاء الخطي في الرسومات الحاسوبية. في هذا المجال، يُطلق عليها أحيانًا مصطلح "ليرب" (بالإنجليزية: Lerp مِن Linear Interpolation)‏. يمكن استخدام المصطلح كفعل أو اسم للعملية. مثلاً، "خوارزمية بريسنهام تقوم بِليرب بمنحى تصاعُديّ بين نقطتي نهاية الخط".

صارت عمليات الاستيفاء (ليرب) مدمجة بجميع معالجات الرسوميات للحواسيب الحديثة. وغالباً ما يتم استخدامها كقطع بناء لعمليات أكثر تعقيدًا: على سبيل المثال، يمكن تحقيق استيفاء خطي ثنائي في ثلاث عمليات ليرب. وبما أن هذه العملية هيّنة، فإنها أيضًا طريقة جيدة لتنفيذ جداول بحث دقيقة مع بحث سريع للدوال الناعمة دون الحاجة إلى الكثير من مداخيل الجدول.

إضافات[عدل]

الدقة[عدل]

إذا كانت الدالة $C 0$ غير كافية، على سبيل المثال إذا كانَ الإجراء الذي أنتجَ نقاط البيانات معلوم بأنهُ أكثرَ نعومة مِن $C 0$ ، فمن الشائِع استبدال الاستيفاء الخطي باستيفاء شريحة أو في بعض الحالات، استيفاء حدودي.

متعدد المتغيرات[عدل]

الاستيفاء الخطي كما هوَ موضّح هنا يتعلق بنقاط البيانات في بُعْدٍ مكانيّ واحد. بالنسبة لبُعْدَيْن مكانِيَين، يُطلَق على امتداد الاستيفاء الخطي مصطلحَ استيفاء خطي ثنائي، وفي الأبعاد الثلاثة، يُطلَق عليه استيفاء ثلاثي الخط ^{[الإنجليزية]}. لاحظ، على الرغم من ذلك، أن هذه الاستيفاءات لم تعد دوال خطية للإحداثيات المكانية، بقدر ما هيَ جداءات للدوال الخطية، هذا مُوضّح من خلال المثال غير الخطي بشكل ظاهِر عبرَ الاستيفاء الخطي الثنائي الشكل أدناه. يُمكن تطبيق امتدادات أخرى للاستيفاء الخطي على أنواع أخرى من الشبكات مثل الشبكات المثلثية وَرباعية السطوح، بما في ذلك أسطُح بيزييه. يُمكن تحديد هذه كدوال خطية قطعية فعلاً بأبعاد أعلى (انظر الشكل الثاني أدناه).

مثال على استيفاء خطي ثنائي على مربع الوحدة مع قيم $z$ 0,1,1، وَ 0.5 كما هو موضح. القيم المستيفأة بينها تُمثل باللون.

في البرمجة[عدل]

العديد من المكتبات ولغات التظليل تحتوي على وظيفة ليرب مساعدة "lerp" (التي تعرف في جي إل إس إل بـِ mix)، والتي تقوم بإرجاع استيفاء بين مدخلين (v0, v1) للعامل t في فترة الوحدة المغلقة [0, 1]. تُنفّذ توقيعات وظائف lerp بأشكال مختلفة بين (v0, v1, t) وَ (t, v0, v1).

// Imprecise method, which does not guarantee v = v1 when t = 1, due to floating-point arithmetic error.
// This method is monotonic. This form may be used when the hardware has a native fused multiply-add instruction.
float lerp(float v0, float v1, float t) {
  return v0 + t * (v1 - v0);
}

// Precise method, which guarantees v = v1 when t = 1. This method is monotonic only when v0 * v1 < 0.
// Lerping between same values might not produce the same value
float lerp(float v0, float v1, float t) {
  return (1 - t) * v0 + t * v1;
}

تُستخدَم وظيفة "lerp" بشكل شائع لتجميع ألفا (المُعامل "t" هو قيمة "ألفا")، يمكن توسيع الصيغة لدمج مكونات متعددة من مُتجه (مثل المحاور س وَ ع وَ ص أو مكونات الألوان ح خ ز) بشكل متوازي.

انظر أيضا[عدل]

المراجع[عدل]

^ Joseph Needham (1 يناير 1959). Science and Civilisation in China: Volume 3, Mathematics and the Sciences of the Heavens and the Earth. Cambridge University Press. ص. 147–. ISBN:978-0-521-05801-8. مؤرشف من الأصل في 2023-03-26.

Meijering، Erik (2002)، "A chronology of interpolation: from ancient astronomy to modern signal and image processing"، Proceedings of the IEEE، ج. 90، ص. 319–342، DOI:10.1109/5.993400، مؤرشف من الأصل في 2024-04-28.

وصلات خارجية[عدل]

[Needham19592-1] Joseph Needham (1 يناير 1959). Science and Civilisation in China: Volume 3, Mathematics and the Sciences of the Heavens and the Earth. Cambridge University Press. ص. 147–. ISBN:978-0-521-05801-8. مؤرشف من الأصل في 2023-03-26.

[1]