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

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 70 صور
الموسوعة الحرة

خوارزمية ريمز، أو خوارزمية تبادل ريمز ، التي نشرها يفغيني ياكوفليفيتش ريمز عام 1934، هي خوارزمية تكرارية تُستخدم لإيجاد تقريبات بسيطة للدوال، وتحديدًا تقريبات باستخدام دوال في فضاء تشيبيشيف تكون الأفضل وفقًا لمعيار L∞ الموحد . [ 1 ] ويُشار إليها أحيانًا باسم خوارزمية ريمس أو خوارزمية ريمي . [ 2 ]

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

إجراء

تبدأ خوارزمية ريميز بالدالةو{\displaystyle f}يتم تقريبها ومجموعةX{\displaystyle X}لن+2{\displaystyle n+2}نقاط العينةx1،x2،...،xن+2{\displaystyle x_{1},x_{2},...,x_{n+2}}في فترة التقريب، عادةً ما تكون القيم القصوى لكثير حدود تشيبيشيف مُحولة خطيًا إلى تلك الفترة. الخطوات هي:

  • حل نظام المعادلات الخطية
ب0+ب1xأنا+...+بنxأنان+(-1)أناهـ=و(xأنا){\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}(أينأنا=1،2،...ن+2{\displaystyle i=1,2,...n+2})
للمجهولينب0،ب1...بن{\displaystyle b_{0},b_{1}...b_{n}}و E.​
  • استخدمبأنا{\displaystyle b_{i}}كمعاملات لتشكيل متعددة الحدودPن{\displaystyle P_{n}}.
  • أوجد المجموعةم{\displaystyle M}نقاط الخطأ الأقصى المحلي|Pن(x)-و(x)|{\displaystyle |P_{n}(x)-f(x)|}.
  • إذا كانت الأخطاء في كلم∈م{\displaystyle m\in M}إذا كانت متساوية في المقدار ومتبادلة في الإشارة، فإنPن{\displaystyle P_{n}}هي متعددة الحدود التقريبية الدنيا القصوى. إذا لم تكن كذلك، فاستبدلهاX{\displaystyle X}معم{\displaystyle M}وكرر الخطوات المذكورة أعلاه.

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

يقدم دبليو فريزر مراجعة للجوانب التقنية في تطبيق خوارزمية ريميز. [ 3 ]

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

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

‖و-لن(و)‖∞≤(1+‖لن‖∞)معلوماتص∈Pن‖و-ص‖{\displaystyle \lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert fp\rVert }

حيث يكون معيار أو ثابت ليبيغ لمؤثر استيفاء لاغرانج L n للعقد ( t 1 ، ...، t n  +  1 ) هو

‖لن‖∞=Λ¯ن(تي)=الأعلى-1≤x≤1λن(تي؛x)،{\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),}

T هي أصفار كثيرات حدود تشيبيشيف، ودوال ليبيغ هي

λن(تي؛x)=∑ج=1ن+1|لج(x)|،لج(x)=∏أنا≠جأنا=1ن+1(x-تأنا)(تج-تأنا).{\displaystyle \lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}(x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i})}}.}

أثبت كلٌّ من ثيودور أ. كيلغور [ 4 ] ، وكارل دي بور، وآلان بينكوس [ 5 ] وجود قيمة فريدة لـ t<sub> i</sub> لكل L <sub>n</sub> ، على الرغم من أنها غير معروفة صراحةً بالنسبة لكثيرات الحدود (العادية). وبالمثل،Λ_ن(تي)=مين-1≤x≤1λن(تي؛x){\displaystyle {\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)}ويمكن التعبير عن أمثلية اختيار العقد على النحو التالي:Λ¯ن-Λ_ن≥0.{\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.}

بالنسبة لعقد تشيبيشيف، والتي توفر خيارًا دون المستوى الأمثل، ولكنه صريح تحليليًا، فإن السلوك التقاربي معروف باسم [ 6 ].

Λ¯ن(تي)=2πسجل⁡(ن+1)+2π(γ+سجل⁡8π)+αن+1{\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}}

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

0<αن<π72ن2{\displaystyle 0<\alpha _{n}<{\frac {\pi }{72n^{2}}}}لن≥1،{\displaystyle n\geq 1,}

والحد الأعلى [ 7 ]

Λ¯ن(تي)≤2πسجل⁡(ن+1)+1{\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1}

حصل ليف بروتمن [ 8 ] على الحد لـن≥3{\displaystyle n\geq 3}، وتي^{\displaystyle {\hat {T}}}كونها أصفار كثيرات حدود تشيبيشيف الموسعة:

Λ¯ن(تي^)-Λ_ن(تي^)<Λ¯3-16سرير أطفال⁡π8+π641الخطيئة2⁡(3π/16)-2π(γ-سجل⁡π)≈0.201.{\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<{\overline {\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.}

حصل روديجر غونتنر [ 9 ] على تقدير أكثر دقة لـن≥40{\displaystyle n\geq 40}

Λ¯ن(تي^)-Λ_ن(تي^)<0.0196.{\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}

مناقشة مفصلة

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

الخطوة 1: معطىx0،x1،...xن+1{\displaystyle x_{0},x_{1},...x_{n+1}}حل النظام الخطي المكون من n + 2 معادلة

ب0+ب1xأنا+...+بنxأنان+(-1)أناهـ=و(xأنا){\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}(أينأنا=0،1،...ن+1{\displaystyle i=0,1,...n+1})
للمجهولينب0،ب1،...بن{\displaystyle b_{0},b_{1},...b_{n}}و E.​

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

احسب الدالة الاستيفائية القياسية من الدرجة nص1(x){\displaystyle p_{1}(x)}لو(x){\displaystyle f(x)}عند أول n + 1 عقدة وأيضًا الاستيفاء القياسي من الدرجة nص2(x){\displaystyle p_{2}(x)}إلى الإحداثيات(-1)أنا{\displaystyle (-1)^{i}}

ص1(xأنا)=و(xأنا)،ص2(xأنا)=(-1)أنا،أنا=0،...،ن.{\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.}

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

متعددة الحدودص2(x){\displaystyle p_{2}(x)}له الصفر رقم i بينxأنا-1{\displaystyle x_{i-1}}وxأنا، أنا=1،...،ن{\displaystyle x_{i},\ i=1,...,n}وبالتالي لا توجد أصفار أخرى بينهماxن{\displaystyle x_{n}}وxن+1{\displaystyle x_{n+1}}:ص2(xن){\displaystyle p_{2}(x_{n})}وص2(xن+1){\displaystyle p_{2}(x_{n+1})}لها نفس العلامة(-1)ن{\displaystyle (-1)^{n}}.

التركيبة الخطية ص(x):=ص1(x)-ص2(x)⋅هـ{\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E}وهي أيضًا متعددة حدود من الدرجة n و

ص(xأنا)=ص1(xأنا)-ص2(xأنا)⋅هـ = و(xأنا)-(-1)أناهـ،    أنا=0،...،ن.{\displaystyle p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.}

وهذا هو نفس المعادلة أعلاه لـأنا=0،...،ن{\displaystyle i=0,...,n}ولأي اختيار لـ E ، تكون المعادلة نفسها لـ i = n + 1 هي

ص(xن+1) = ص1(xن+1)-ص2(xن+1)⋅هـ = و(xن+1)-(-1)ن+1هـ{\displaystyle 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 :
هـ := ص1(xن+1)-و(xن+1)ص2(xن+1)+(-1)ن.{\displaystyle E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.}

كما ذكرنا سابقًا، فإن الحدين في المقام لهما نفس الإشارة: E وبالتاليص(x)≡ب0+ب1x+...+بنxن{\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}دائماً ما تكون محددة بشكل جيد.

الخطأ عند العقد المرتبة n + 2 المعطاة يكون موجبًا وسالبًا بالتناوب لأن

ص(xأنا)-و(xأنا) = -(-1)أناهـ،  أنا=0،...،ن+1.{\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.}

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

الخطوة الثانية تغير الترميز من ب0+ب1x+...+بنxن{\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}}لص(x){\displaystyle p(x)}.

الخطوة الثالثة تُحسّن من عقد الإدخالx0،...،xن+1{\displaystyle x_{0},...,x_{n+1}}وأخطائهم±هـ{\displaystyle \pm E}على النحو التالي.

في كل منطقة P، العقدة الحاليةxأنا{\displaystyle x_{i}}يتم استبدالها بالمُعظِّم المحليx¯أنا{\displaystyle {\bar {x}}_{i}}وفي كل منطقة من المناطق Nxأنا{\displaystyle x_{i}}يتم استبدالها بالمُصغِّر المحلي. (توقع)x¯0{\displaystyle {\bar {x}}_{0}}في النقطة أ ،x¯أنا{\displaystyle {\bar {x}}_{i}}قريبxأنا{\displaystyle x_{i}}، وx¯ن+1{\displaystyle {\bar {x}}_{n+1}}عند النقطة B. ) لا تتطلب هذه الحالة دقة عالية، فالبحث الخطي القياسي مع بعض عمليات التوفيق التربيعي يكفي. (انظر [ 10 ] )

يتركzأنا:=ص(x¯أنا)-و(x¯أنا){\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})}كل سعة|zأنا|{\displaystyle |z_{i}|}أكبر من أو يساوي E. تنطبق نظرية دي لا فالي بوسان وبرهانها أيضًا علىz0،...،zن+1{\displaystyle z_{0},...,z_{n+1}}معمين{|zأنا|}≥هـ{\displaystyle \min\{|z_{i}|\}\geq E}باعتبارها الحد الأدنى الجديد لأفضل خطأ ممكن مع كثيرات الحدود من الدرجة n .

علاوة على ذلك،الأعلى{|zأنا|}{\displaystyle \max\{|z_{i}|\}}يُعدّ هذا مفيدًا كحدّ أعلى واضح لأفضل خطأ ممكن.

الخطوة الرابعة: معمين{|zأنا|}{\displaystyle \min \,\{|z_{i}|\}}والأعلى{|zأنا|}{\displaystyle \max \,\{|z_{i}|\}}كحدود دنيا وعليا لأفضل خطأ تقريبي ممكن ، يكون لدينا معيار توقف موثوق: كرر الخطوات حتىالأعلى{|zأنا|}-مين{|zأنا|}{\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}تكون صغيرة بما يكفي أو لم تعد تتناقص. تشير هذه الحدود إلى التقدم المحرز.

المتغيرات

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

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

انظر أيضاً

مراجع

  1. ↑ ريمز، إي.يا. (1934). "Sur la déternation des polynômes d'approximation de degré donnée". إتصالات. شركة نفط الجنوب. الرياضيات. خاركوف . 10 : 41.— (1934). "Sur un procédé convergent d'approximations المتعاقبة لتحديد متعددات التقريب" . كومبت. مزق. أكاد. الخيال العلمي. (باللغة الفرنسية). 198 : 2063– 5.— (1934). "Sur le calcul Effectif des polynomes d'approximation de Tschebyschef" . كومبت. مزق. أكاد. الخيال العلمي. (باللغة الفرنسية). 199 : 337 – 340.
  2. ↑ تشيانغ، يي-لينغ ف. (نوفمبر 1988). "خوارزمية ريمس المعدلة" . مجلة SIAM للحوسبة العلمية والإحصائية . 9 (6): 1058-1072 . doi : 10.1137/0909072 . ISSN 0196-5204 . 
  3. ↑ فريزر، و. (1965). "دراسة استقصائية لطرق حساب تقريبات كثيرات الحدود من نوع مينيمكس وشبه مينيمكس لدوال ذات متغير مستقل واحد" . مجلة ACM . 12 (3): 295-314 . doi : 10.1145/321281.321282 . S2CID 2736060 . 
  4. ↑ كيلغور، تي. أ. (1978). "توصيف إسقاط لاغرانج الاستيفائي بمعيار تشيبيشيف الأدنى". مجلة نظرية التقريب . 24 (4): 273-288 . doi : 10.1016/0021-9045(78)90013-8 .
  5. ↑ دي بور، سي.؛ بينكوس، أ. (1978). "إثبات تخمينات برنشتاين وإردوش بشأن العقد المثلى للاستيفاء متعدد الحدود" . مجلة نظرية التقريب . 24 (4): 289-303 . doi : 10.1016/0021-9045(78)90014-X .
  6. ↑ لوتمان، ف. و.؛ ريفلين، ت. ج. (1965). "بعض التجارب العددية في نظرية الاستيفاء متعدد الحدود". مجلة آي بي إم للبحوث والتطوير 9 ( 3): 187-191 . doi : 10.1147/rd.93.0187 .
  7. ↑ ريفلين، تي جيه (1974). "ثوابت ليبيغ لاستيفاء كثيرات الحدود" . في: غارنير، إتش جي؛ أوني، كيه آر؛ ويليامسون، جيه إتش (محررون). التحليل الوظيفي وتطبيقاته . سلسلة محاضرات في الرياضيات. المجلد 399. سبرينغر. الصفحات 422-437 . doi : 10.1007/BFb0063594 . ISBN   978-3-540-37827-3.
  8. ↑ بروتمن، ل. (1978). "حول دالة ليبيغ للاستيفاء متعدد الحدود". مجلة SIAM للتحليل العددي . 15 (4): 694-704 . Bibcode : 1978SJNA...15..694B . doi : 10.1137/0715046 .
  9. ↑ غونتنر، ر. (1980). "تقييم ثوابت لوبيغ". مجلة SIAM للتحليل العددي . 17 (4): 512-520 . Bibcode : 1980SJNA...17..512G . doi : 10.1137/0717043 .
  10. ↑ لونبرغر، دي جي؛ يي، واي. (2008). "طرق الهبوط الأساسية" . البرمجة الخطية وغير الخطية . السلسلة الدولية في بحوث العمليات وعلوم الإدارة. المجلد 116 ( الطبعة الثالثة). سبرينغر. الصفحات 215-262 . doi : 10.1007/978-0-387-74503-9_8 . ISBN    978-0-387-74503-9.
  11. ^ إيجيدي، نادانييلا؛ فاتون، لوريلا؛ ميسيسي، لوتشيانو (2020)، "خوارزمية جديدة من نوع ريميز لأفضل تقريب متعدد الحدود" ، في سيرجيف، ياروسلاف د.؛ Kvasov، Dmitri E. (eds.)، الحسابات العددية: النظرية والخوارزميات ، المجلد. 11973، شام: سبرينغر، ص 56-69 ، دوى : 10.1007 / 978-3-030-39081-5_7 ، ISBN   978-3-030-39080-8، S2CID 211159177 
  12. تيمس ، جي سي؛ بارسيلون، في؛ مارشال، إف سي (1973). "تحسين الأنظمة محدودة النطاق". وقائع معهد مهندسي الكهرباء والإلكترونيات . 61 (2): 196-234 . رمز Bibcode : 1973IEEEP..61..196T . doi : 10.1109/PROC.1973.9004 . ISSN 0018-9219 . 
  13. ↑ دونهام، تشارلز ب. (1975). "تقارب خوارزمية فريزر-هارت لتقريب تشيبيشيف العقلاني" . رياضيات الحساب . 29 (132): 1078-1082 . doi : 10.1090/S0025-5718-1975-0388732-9 . ISSN 0025-5718 .