خوارزمية ريميز

خوارزمية ريميز أو خوارزمية تبادل ريميز، التي نشرها وجيني ياكوفليفيتش ريمز في عام 1934 ، هي خوارزمية تكرارية تستخدم لإيجاد تقريب بسيط للدالات وتحديدا التقريبات بواسطة الدوال في مساحة تشيبيشيف التي تكون الأفضل في المعيار الموحد _بمعنى L. يشار إليه أحيانًا باسم خوارزمية ريميس أو خوارزمية ريم. 

ويشكل مثالًا نموذجيًا لفضاء شيبيشيف الفرعي، الفضاء الفرعي للدوال الجزئية شيبيشيف من الرتبة n في فضاء الدوال المستمرة الحقيقية على فترة محددة، C [a، b]. يتم تحديد الدالة الجزئية الأفضل تقريبًا داخل الفضاء الفرعي المحدد بأنها تقلل الفرق المطلق الأقصى بين الدالة الجزئية والدالة المستهدفة. وفي هذه الحالة، يتم تحديد شكل الحل بدقة بواسطة نظرية التذبذب المتساوي.

الإجراء

تبدأ خوارزمية ريميز بالدالة $f$ لتقريب ومجموعة $X$ ل $n+2$ نقاط العينة $x_1,x_2,...,x_{n+2}$ في الفاصل الزمني التقريبي ، عادةً ما يتم تعيين أقصى حدود تشيبيشيف متعدد الحدود خطيًا إلى الفترة. الخطوات هي:

• حل نظام المعادلات الخطي

$b_0+b_1{x}_i+...+b_n{x}_i^n+(-1{)}^{i}E=f(x_i)$ (أين $i=1,2,...n+2$ ) ،

للمجهولين $b_0,b_1...b_n$ و هـ .

• استخدم ال $b_i$ كمعامِلات لتشكيل كثير الحدود $P_n$ .
• ابحث عن المجموعة $M$ من نقاط الحد الأقصى للخطأ المحلي $|P_n(x)-f(x)|$ .
• إذا كانت الأخطاء في كل مرة $m\in M$ متساوية في الحجم وعلامة تسجيل بديلة ، إذن $P_n$ هو تقريب مينيماكس كثير الحدود. إذا لم يكن كذلك ، فاستبدل $X$ مع $M$ وكرر الخطوات أعلاه.

والنتيجة تسمى كثير الحدود لأفضل تقريب أو خوارزمية الحد الأدنى للتقريب .

قدم دبليو فريزر مراجعة للجوانب الفنية في تنفيذ خوارزمية ريميز.

اختيار التهيئة

تعتبر عقد تشيبيشيف خيارًا شائعًا للتقريب الأولي بسبب دورها في نظرية الاستيفاء متعدد الحدود. لتهيئة مشكلة التحسين للدالة f بواسطة متعدد حدود لاغرانج L _n ( f ) ، يمكن إظهار أن هذا التقريب الأولي مقيد بـ

$\Vert f-L_n(f){\Vert }_{\mathrm{\infty }}\le (1+\Vert L_n{\Vert }_{\mathrm{\infty }}){inf}_{p\in P_n}\Vert f-p\Vert$

مع القاعدة أو ثابت ليبيج لمشغل الاستيفاء لاغرانج L _n للعقد ( t ₁ ، ...، t _n + 1 ) يجري

$\Vert L_n{\Vert }_{\mathrm{\infty }}={\overline{\mathrm{\Lambda }}}_n(T)={max}_{-1\le x\le 1}{\lambda }_n(T;x),$

T كونها أصفار تشيبيشيف متعدد الحدود ، و ليبيج دالة كونها:

${\lambda }_n(T;x)=\sum _{j=1}^{n+1}|l_j(x)|,l_j(x)=\prod _{\stackrel{i=1}{i\ne j}}^{n+1}\frac{(x-t_i)}{(t_j-t_i)}.$

أثبت ثيودور إيه كيلجور ، وكارل دي بور ، وألان بينكوس وجود _حرف t فريد لكل L _n ، على الرغم من عدم معرفته صراحةً عن كثيرات الحدود (العادية). بصورة مماثلة، ${\underset{\_}{\mathrm{\Lambda }}}_n(T)={min}_{-1\le x\le 1}{\lambda }_n(T;x)$ ، ويمكن التعبير عن أمثلية اختيار العقد كـ ${\overline{\mathrm{\Lambda }}}_n-{\underset{\_}{\mathrm{\Lambda }}}_n\ge 0.$

بالنسبة لعقد تشيبيشيف ، التي توفر خيارًا دون المستوى الأمثل ، ولكن صريحًا من الناحية التحليلية ، يُعرف السلوك المقارب باسم

${\overline{\mathrm{\Lambda }}}_n(T)=\frac{2}{\pi }\log (n+1)+\frac{2}{\pi }(\gamma +\log \frac{8}{\pi })+{\alpha }_{n+1}$

( γ كونه ثابت أويلر-ماسكيروني ) مع

$0<{\alpha }_n<\frac{\pi }{72n^2}$ ل $n\ge 1,$

والحد الأعلى

${\overline{\mathrm{\Lambda }}}_n(T)\le \frac{2}{\pi }\log (n+1)+1$

حصل ليف بروتمان على الحدود $n\ge 3$ ، و $\hat{T}$ كونها أصفار متعددات حدود تشيبيشيفالموسعة:

${\overline{\mathrm{\Lambda }}}_n(\hat{T})-{\underset{\_}{\mathrm{\Lambda }}}_n(\hat{T})<{\overline{\mathrm{\Lambda }}}_3-\frac{1}{6}\cot \frac{\pi }{8}+\frac{\pi }{64}\frac{1}{{\sin }^2(3\pi /16)}-\frac{2}{\pi }(\gamma -\log \pi )\approx 0.201.$

حصل روديجر جونتنر على تقدير أكثر دقة لـ $n\ge 40$

${\overline{\mathrm{\Lambda }}}_n(\hat{T})-{\underset{\_}{\mathrm{\Lambda }}}_n(\hat{T})<0.0196.$

مناقشة مفصلة

يوفر هذا القسم مزيدًا من المعلومات حول الخطوات الموضحة أعلاه. في هذا القسم ، يتم تشغيل الفهرس i من 0 إلى n +1.

الخطوة 1: معطى $x_0,x_1,...x_{n+1}$ ، حل النظام الخطي من المعادلات n +2

$b_0+b_1{x}_i+...+b_n{x}_i^n+(-1{)}^{i}E=f(x_i)$ (أين $i=0,1,...n+1$ ) ،

للمجهولين $b_0,b_1,...b_n$ و هـ .

يجب أن يكون واضحا ذلك $(-1{)}^{i}E$ في هذه المعادلة يكون منطقيًا فقط إذا كانت العقد $x_0,...,x_{n+1}$ يتم طلبها ، إما زيادة صارمة أو تناقص صارم. ثم هذا النظام الخطي لديه حل فريد. (كما هو معروف ، ليس لكل نظام خطي حل. ) أيضًا ، يمكن الحصول على الحل فقط باستخدام $O(n^2)$ العمليات الحسابية في حين أن الحل القياسي من المكتبة سوف يستغرق $O(n^3)$ عمليات. هذا هو الدليل البسيط:

حساب التداخل القياسي من الدرجة n $p_1(x)$ ل $f(x)$ في العقد الأول n +1 وأيضًا المقحم القياسي من الدرجة n $p_2(x)$ على الاحداثيات $(-1{)}^i$

$p_1(x_i)=f(x_i),p_2(x_i)=(-1{)}^i,i=0,...,n.$

تحقيقا لهذه الغاية ، استخدم في كل مرة صيغة الاستيفاء لنيوتن مع الفروق المقسمة في الترتيب $0,...,n$ و $O(n^2)$ عمليات حسابية.

كثير الحدود $p_2(x)$ له رقم i -th صفر بين $x_{i-1}$ و $x_i,i=1,...,n$ ، وبالتالي لا مزيد من الأصفار بين $x_n$ و $x_{n+1}$ : $p_2(x_n)$ و $p_2(x_{n+1})$ لها نفس العلامة $(-1{)}^n$ .

التركيبة الخطية $p(x):=p_1(x)-p_2(x)\cdot E$ هي أيضًا كثيرة حدود من الدرجة n و

$p(x_i)=p_1(x_i)-p_2(x_i)\cdot E=f(x_i)-(-1{)}^{i}E,i=0,\dots ,n.$

هذه هي نفس المعادلة أعلاه لـ $i=0,...,n$ ولأي اختيار من E. نفس المعادلة لـ i = n +1 هي

$p(x_{n+1})=p_1(x_{n+1})-p_2(x_{n+1})\cdot E=f(x_{n+1})-(-1{)}^{n+1}E$ ويحتاج إلى تفكير خاص: حل للمتغير E ، هو تعريف E :

$E:=\frac{p_1(x_{n+1})-f(x_{n+1})}{p_2(x_{n+1})+(-1{)}^n}.$

كما ذكر أعلاه ، فإن المصطلحين في المقام لهما نفس العلامة: E وبالتالي $p(x)\equiv b_0+b_{1}x+\dots +b_n{x}^n$ دائمًا ما تكون محددة جيدًا.

الخطأ في العقد المحددة n +2 موجب وسالب بدوره لأن

$p(x_i)-f(x_i)=-(-1{)}^{i}E,i=0,...,n+1.$

تنص نظرية شارل جون دو لا فالي بوسان على أنه في ظل هذه الحالة لا يوجد كثير حدود من الدرجة n مع وجود خطأ أقل من E. في الواقع ، إذا وجدت مثل هذه كثيرة الحدود ، فسمها $\tilde{p}(x)$ ثم الاختلاف $p(x)-\tilde{p}(x)=(p(x)-f(x))-(\tilde{p}(x)-f(x))$ سيظل موجبًا / سلبيًا عند n +2 عقد $x_i$ وبالتالي تحتوي على n +1 أصفار على الأقل وهو أمر مستحيل بالنسبة لكثيرات الحدود من الدرجة n . وبالتالي ، فإن هذا E هو الحد الأدنى للحد الأدنى للخطأ الذي يمكن تحقيقه مع كثيرات الحدود من الدرجة n .

الخطوة 2 تغير التدوين من $b_0+b_{1}x+...+b_n{x}^n$ ل $p(x)$ .

الخطوة 3 تعمل على تحسين عقد الإدخال $x_0,...,x_{n+1}$ وأخطائهم $\pm E$ على النحو التالي.

في كل منطقة P ، العقدة الحالية $x_i$ يتم استبداله بالمكبر المحلي ${\overline{x}}_i$ وفي كل منطقة N $x_i$ مع المصغر المحلي. (يتوقع ${\overline{x}}_0$ في A ، و ${\overline{x}}_i$ قريب $x_i$ ، و ${\overline{x}}_{n+1}$ عند B. ) ليست هناك حاجة إلى دقة عالية هنا ، يجب أن يكون البحث القياسي عن الخط مع بضع نوبات تربيعية كافياً. (انظر )

يترك $z_i:=p({\overline{x}}_i)-f({\overline{x}}_i)$ . كل سعة $\left|z_i\right|$ أكبر من أو يساوي E. تنطبق أيضًا نظرية شارل جون دو لا فالي بوسان وإثباتها $z_0,...,z_{n+1}$ مع $min\{|z_i|\}\ge E$ كالحد الأدنى الجديد لأفضل خطأ ممكن مع كثيرات الحدود من الدرجة n .

علاوة على ذلك، $max\{|z_i|\}$ يأتي في متناول اليد باعتباره حدًا أعلى واضحًا لأفضل خطأ ممكن.

الخطوة 4: مع $min\{|z_i|\}$ و $max\{|z_i|\}$ كحد أدنى وأعلى لأفضل خطأ تقريب ممكن ، لدى المرء معيار إيقاف موثوق: كرر الخطوات حتى $max\{|z_i|\}-min\{|z_i|\}$ صغير بما فيه الكفاية أو لم يعد يتناقص. تشير هذه الحدود إلى التقدم.

المتغيرات

بعض التعديلات على الخوارزمية موجودة في الأدبيات. وتشمل هذه:

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

أنظر أيضا

• نظرية التقريب

روابط خارجية

• Minimax Approximations and the Remez Algorithm ، فصل الخلفية في وثائق Boost Math Tools ، مع ارتباط إلى تنفيذ في C ++
• مقدمة إلى DSP