عرض مصدر استيفاء خطي

[[ملف:LinearInterpolation.svg|تصغير|يسار|300px|النقطتان الحمراوتان معلومتان. الخط المستقيم الأزرق هو الخط المستوفي بينهما. يمكن إيجاد قيمة y عند x باستعمال الاستيفاء الخطي.]]فِي [[رياضيات|الرِّياضيَّات]]، '''الاسْتيفاء الخطِّيّ''' ([[اللغة الإنجليزية|بالانجليزية]]:'''Linear interpolation''') هُو طَرِيقَة [[توفيق المنحنيات|لِتوْفِيق المنْحنيات]] بِاسْتخْدام [[متعددة الحدود|مُتعدِّدات اَلحُدود الخطِّيَّة]] لِبناء نِقَاط بيانَات جَدِيدَة ضِمْن نِطَاق مَجمُوعة مِن البيانات المعْروفة.

== الاستيفاء الخطي بين نقطتين معروفتين ==
[[ملف:Linear_interpolation_visualisation.svg|تصغير|في هذا التصوير الهندسي، يُضرب قيمة الدائرة الخضراء في المسافة الأفقية بين الدائرتين الحمراء والزرقاء، ويُعادل ذلك مجموع قيمة الدائرة الحمراء مضروبة في المسافة الأفقية بين الدائرة الخضراء والزرقاء، وقيمة الدائرة الزرقاء مضروبة في المسافة الأفقية بين الدائرة الحمراء والخضراء.]]
إذا كانتا النقطتين المعروفتين ممثلتين بالإحداثيات <math>(x_0,y_0)</math> وَ {{بدون لف|<math>(x_1,y_1)</math>,}} فإن '''الخط المستوفي''' هو الخط المستقيم بين هاتين النقطتين. لقيمة <math>x</math> في الفترة {{بدون لف|<math>(x_0, x_1)</math>,}} تُعطى القيمة <math>y</math> على طول الخط المستقيم من معادلة الميلات<math>\frac{y - y_0}{x - x_0} = \frac{y_1 - y_0}{x_1 - x_0},</math>والتي يمكن استنتاجها هندسياً من الشكل على اليسار. إنها حالة خاصة من [[استيفاء حدودي|استيفاء متعدد الحدود]] بقيمة {{بدون لف|<math>n = 1</math>.}}

حل هذه المعادلة لـ <math>y</math>, وهي القيمة المجهولة في <math>x</math>, يعطي<math>\begin{align} 
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_1x - y_1x_0-y_0x + y_0x_0 + y_0x_1-y_0x_0}{x_1 - x_0} \\
&= \frac{y_0(x_1 - x)+y_1(x - x_0)}{x_1 - x_0},
\end{align}
</math>وهو الصيغة للاستيفاء الخطي في الفترة {{بدون لف|<math>(x_0,x_1)</math>.}} خارج هذه الفترة، تكون الصيغة متطابقة مع [[استكمال خارجي]].

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

<math display="inline">1 - (x-x_0)/(x_1-x_0)</math> وَ <math display="inline">1 - (x_1-x)/(x_1-x_0)</math>, والتي تمثل المسافات الموحدة بين النقطة المجهولة وكل من النقاط النهائية. لأن هذه المجموعة تساوي 1،<math>\begin{align}
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{align}</math>مما يعطي الصيغة للاستيفاء الخطي المذكورة أعلاه.

== استيفاء مجموعة بيانات ==
[[ملف:Interpolation_example_linear.svg|تصغير|300x300بك|يتكون الاستيفاء الخطي على مجموعة بيانات (النقاط الحمراء) من قطع من الملمخات الخطية (الخطوط الزرقاء).]]
يتكون الاستيفاء الخطي على مجموعة من نقاط البيانات (النقاط الحمراء) من قطع الاستيفاء الخطي (الخطوط الزرقاء). الاستيفاء الخطي على مجموعة من نقاط البيانات {{تعبير رياضي|(''x''<sub>0</sub>, ''y''<sub>0</sub>), (''x''<sub>1</sub>, ''y''<sub>1</sub>), ..., (''x''<sub>n</sub>, ''y''<sub>n</sub>)}} يُعرَّف كخطي قطعة قطعة، ناتج عن اتحاد [[قطعة مستقيمة|قطع مستقيمة]] الاستيفاء بين كل زوج من نقاط البيانات. وينتج عن ذلك [[دالة مستمرة|منحنى مستمر]]، ولكنه يكون له تفاضل متقطع (بشكل عام)، وبالتالي من [[نعومة دالة|الفصل التفاضلي]] <math>C^0
</math>.

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

<math>R_T = f(x) - p(x),
</math>

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

<math>p(x) = f(x_0) + \frac{f(x_1) - f(x_0)}{x_1 - x_0}(x - x_0).

</math>

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

<math>|R_T| \leq \frac{(x_1 - x_0)^2}{8} \max_{x_0 \leq x \leq x_1} \left|f''(x)\right|.

</math>

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

== التاريخ والتطبيقات ==
الاستيفاء الخطي قد استُخدم منذ العصور القديمة لملء الفجوات في الجداول. لنفترض أن لدينا جدول يُدرج فيهِ تعداد سكان بلد ما في 1970 وَ1980 وَ1990 وَ2000، وَنريدُ تقدير تعداد السكان في عام 1994. يأتي دور الاستيفاء الخطي كوسيلة سهلة للقيامِ بذلك. يُعتقد أنه تم استخدامه في [[سلوقيون|الإمبراطورية السلوقية]] (ثلاثة قرون الأخيرة قبلَ الميلاد) ومِن قِبَل عالم الفلك وَالرياضي اليُوناني [[أبرخش]] (القرن الثاني قبلَ الميلاد). يمكن العثور على تفسير للاستيفاء الخطي في النص [[الرياضيات في الصين|الرياضي الصيني]] القديم المسمى "{{وإو|الفصول التسعة في الفن الرياضي|The Nine Chapters on the Mathematical Art|en}}" (九章算術)،<ref name="Needham19592">{{استشهاد بكتاب|مؤلف=Joseph Needham|مسار= https://books.google.com/books?id=jfQ9E0u4pLAC&pg=PA147|عنوان=Science and Civilisation in China: Volume 3, Mathematics and the Sciences of the Heavens and the Earth|تاريخ=1 January 1959|ناشر=Cambridge University Press|صفحات=147–|isbn=978-0-521-05801-8|مسار أرشيف= https://web.archive.org/web/20230326164820/https://books.google.com/books?id=jfQ9E0u4pLAC&pg=PA147|تاريخ أرشيف=2023-03-26}}</ref> المؤرخ مابين 200 قبل الميلاد وَ100 ميلادي، وفي "[[المجسطي]]" (القرن الثاني الميلادي) [[بطليموس|لبطليموس]].

غالبًا ما تُستَعملُ العملية الأساسية للاستيفاء الخطي في [[رسوميات حاسوبية|الرسومات الحاسوبية]]. في هذا المجال، يُطلق عليها أحيانًا مصطلح "'''ليرب'''" {{إنج|'''Lerp''' مِن '''L'''inear Int'''erp'''olation}}. يمكن استخدام المصطلح كفعل أو اسم للعملية. مثلاً، "[[خوارزمية بريزنهام لرسم مستقيم|خوارزمية بريسنهام]] تقوم بِليرب بمنحى تصاعُديّ بين نقطتي نهاية الخط".

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

== إضافات ==
{{مقارنة بين الاستيفاء أحادي البعد وثنائي البعدين}}

=== الدقة ===
إذا كانت الدالة {{تعبير رياضي|''C''<sup>0</sup>}} غير كافية، على سبيل المثال إذا كانَ الإجراء الذي أنتجَ نقاط البيانات معلوم بأنهُ أكثرَ [[نعومة دالة|نعومة]] مِن {{تعبير رياضي|''C''<sup>0</sup>}}، فمن الشائِع استبدال الاستيفاء الخطي ب[[استيفاء شريحة]] أو في بعض الحالات، [[استيفاء حدودي]].
=== متعدد المتغيرات ===
الاستيفاء الخطي كما هوَ موضّح هنا يتعلق بنقاط البيانات في بُعْدٍ مكانيّ واحد. بالنسبة لبُعْدَيْن مكانِيَين، يُطلَق على امتداد الاستيفاء الخطي مصطلحَ [[استيفاء خطي ثنائي]]، وفي الأبعاد الثلاثة، يُطلَق عليه {{وإو|استيفاء ثلاثي الخط|Trilinear interpolation|en}}. لاحظ، على الرغم من ذلك، أن هذه الاستيفاءات لم تعد دوال خطية للإحداثيات المكانية، بقدر ما هيَ جداءات للدوال الخطية، هذا مُوضّح من خلال المثال غير الخطي بشكل ظاهِر عبرَ الاستيفاء الخطي الثنائي الشكل أدناه. يُمكن تطبيق امتدادات أخرى للاستيفاء الخطي على أنواع أخرى من [[شبكة مضلعية|الشبكات]] مثل الشبكات المثلثية وَرباعية السطوح، بما في ذلك [[سطح بيزييه|أسطُح بيزييه]]. يُمكن تحديد هذه كدوال خطية قطعية فعلاً بأبعاد أعلى (انظر الشكل الثاني أدناه).
[[ملف:Bilininterp.png|تصغير|مثال على [[استيفاء خطي ثنائي]] على مربع الوحدة مع قيم <bdo>{{mvar|z}}</bdo> 0,1,1، وَ 0.5 كما هو موضح. القيم المستيفأة بينها تُمثل باللون.]]
[[ملف:Piecewise_linear_function2D.svg|تصغير|دالة خطية قطعية في بُعدَيْن (أعلى) وَ[[نوني الأبعاد|المتعددات السطحية النونية]] الخطية (أسفل).]]

== في البرمجة ==
العديد من المكتبات ولغات [[مظلل|التظليل]] تحتوي على وظيفة ليرب مساعدة "lerp" (التي تعرف في [[جي إل إس إل]] بـِ mix)، والتي تقوم بإرجاع استيفاء بين مدخلين <code>(v0, v1)</code> للعامل t في فترة الوحدة المغلقة <bdo dir="ltr>[0, 1]</bdo>. تُنفّذ توقيعات وظائف lerp بأشكال مختلفة بين <code>(v0, v1, t)</code> وَ <code>(t, v0, v1)</code>.
<syntaxhighlight lang="c">
// 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;
}
</syntaxhighlight>

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

== انظر أيضا ==
* [[استيفاء]]
* [[استيفاء شريحة]]
* [[استيفاء الجار الأقرب]]
* [[استيفاء خطي ثنائي]]
* [[استيفاء الدرج]]
* [[خوارزم دوكاستلجو|خوارزمية دوكاستلجو]]
* [[استيفاء حدودي]]
* [[منحنى بيزيه]]

== المراجع ==
{{مراجع}}
* {{استشهاد | الأخير1=Meijering | الأول1=Erik | عنوان=A chronology of interpolation: from ancient astronomy to modern signal and image processing | doi=10.1109/5.993400 | سنة=2002 | صحيفة=Proceedings of the IEEE | المجلد=90 | العدد=3 | صفحات=319–342| مسار= http://infoscience.epfl.ch/record/63085 |مسار أرشيف= https://web.archive.org/web/20240428032830/https://infoscience.epfl.ch/record/63085|تاريخ أرشيف=2024-04-28}}.

== وصلات خارجية ==
{{شريط بوابات|الرسوميات الحاسوبية|تحليل رياضي|رياضيات}}

[[تصنيف:استيفاء]]