[ تعرٌف على ] خوارزمية ريميز # اخر تحديث اليوم 2024-04-27

تم النشر اليوم 2024-04-27 | خوارزمية ريميز

المتغيرات

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

الإجراء

تبدأ خوارزمية ريميز بالدالة f
f لتقريب ومجموعة {\displaystyle X} ل n
+
2
{\displaystyle n+2} نقاط العينة
x 1
, x 2
,
.
.
.
, x n
+
2
{\displaystyle x_{1},x_{2},...,x_{n+2}} في الفاصل الزمني التقريبي ، عادةً ما يتم تعيين أقصى حدود تشيبيشيف متعدد الحدود خطيًا إلى الفترة. الخطوات هي: حل نظام المعادلات الخطي b 0
+ b 1 x i
+
.
.
.
+ b n x i
n
+
(
−
1 ) i
E
=
f
( x i
)
{\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})} (أين i
=
1
,
2
,
.
.
.
n
+
2
{\displaystyle i=1,2,...n+2} ) ،
للمجهولين
b 0
, b 1
.
.
. b n
{\displaystyle b_{0},b_{1}...b_{n}} و هـ .
استخدم ال
b i
{\displaystyle b_{i}} كمعامِلات لتشكيل كثير الحدود
P n
{\displaystyle P_{n}} .
ابحث عن المجموعة M
M من نقاط الحد الأقصى للخطأ المحلي
|
P n
(
x
)
−
f
(
x
) | {\displaystyle |P_{n}(x)-f(x)|} .
إذا كانت الأخطاء في كل مرة m
∈
M
{\displaystyle m\in M} متساوية في الحجم وعلامة تسجيل بديلة ، إذن
P n
{\displaystyle P_{n}} هو تقريب مينيماكس كثير الحدود. إذا لم يكن كذلك ، فاستبدل {\displaystyle X} مع M
M وكرر الخطوات أعلاه.
والنتيجة تسمى كثير الحدود لأفضل تقريب أو خوارزمية الحد الأدنى للتقريب . قدم دبليو فريزر مراجعة للجوانب الفنية في تنفيذ خوارزمية ريميز. اختيار التهيئة
تعتبر عقد تشيبيشيف خيارًا شائعًا للتقريب الأولي بسبب دورها في نظرية الاستيفاء متعدد الحدود. لتهيئة مشكلة التحسين للدالة f بواسطة متعدد حدود لاغرانج L n ( f ) ، يمكن إظهار أن هذا التقريب الأولي مقيد بـ ‖
f
− L n
(
f
) ‖ ∞
≤
(
1
+
‖ L n ‖ ∞
) inf p
∈ P n
‖
f
−
p
‖
{\displaystyle \lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert f-p\rVert }
مع القاعدة أو ثابت ليبيج لمشغل الاستيفاء لاغرانج L n للعقد ( t 1 ، ...، t n+1 ) يجري ‖ L n ‖ ∞
= Λ
¯ n
(
T
)
= max −
1
≤
x
≤
1 λ n
(
T
;
x
)
,
{\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),}
T كونها أصفار تشيبيشيف متعدد الحدود ، و ليبيج دالة كونها:
λ n
(
T
;
x
)
= ∑ j
=
1
n
+
1 |
l j
(
x
) | ,
l j
(
x
)
= ∏
i
≠
j
i
=
1 n
+
1 (
x
− t i
)
( t j
− t i
) .
{\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})}}.}
أثبت ثيودور إيه كيلجور ، وكارل دي بور ، وألان بينكوس وجود حرف t فريد لكل L n ، على الرغم من عدم معرفته صراحةً عن كثيرات الحدود (العادية). بصورة مماثلة،
Λ
_ n
(
T
)
= min −
1
≤
x
≤
1 λ n
(
T
;
x
)
{\displaystyle {\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)} ، ويمكن التعبير عن أمثلية اختيار العقد كـ
Λ
¯ n
− Λ
_ n
≥
0.
{\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.} بالنسبة لعقد تشيبيشيف ، التي توفر خيارًا دون المستوى الأمثل ، ولكن صريحًا من الناحية التحليلية ، يُعرف السلوك المقارب باسم
Λ
¯ n
(
T
)
=
2
π
log
⁡
(
n
+
1
)
+
2
π ( γ
+
log
⁡
8
π ) + α n
+
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
< α n
<
π 72 n 2 {\displaystyle 0<\alpha _{n}<{\frac {\pi }{72n^{2}}}} ل n
≥
1
,
{\displaystyle n\geq 1,}
والحد الأعلى
Λ
¯ n
(
T
)
≤
2
π
log
⁡
(
n
+
1
)
+
1
{\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1}
حصل ليف بروتمان على الحدود n
≥
3
{\displaystyle n\geq 3} ، و
T
^ {\displaystyle {\hat {T}}} كونها أصفار متعددات حدود تشيبيشيفالموسعة:
Λ
¯ n
( T
^ )
− Λ
_ n
( T
^ )
< Λ
¯ 3
−
1
6
cot
⁡
π
8
+
π
64
1
sin 2
⁡
(
3
π / 16
) −
2
π
(
γ
−
log
⁡
π
)
≈
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.}
حصل روديجر جونتنر على تقدير أكثر دقة لـ n
≥
40
{\displaystyle n\geq 40}
Λ
¯ n
( T
^ )
− Λ
_ n
( T
^ )
<
0.0196.
{\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}

مناقشة مفصلة

يوفر هذا القسم مزيدًا من المعلومات حول الخطوات الموضحة أعلاه. في هذا القسم ، يتم تشغيل الفهرس i من 0 إلى n +1. الخطوة 1: معطى
x 0
, x 1
,
.
.
. x n
+
1
{\displaystyle 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
)
{\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})} (أين i
=
0
,
1
,
.
.
.
n
+
1
{\displaystyle i=0,1,...n+1} ) ،
للمجهولين
b 0
, b 1
,
.
.
. b n
{\displaystyle b_{0},b_{1},...b_{n}} و هـ .
يجب أن يكون واضحا ذلك (
−
1 ) i
E
{\displaystyle (-1)^{i}E} في هذه المعادلة يكون منطقيًا فقط إذا كانت العقد
x 0
,
.
.
.
, x n
+
1
{\displaystyle x_{0},...,x_{n+1}} يتم طلبها ، إما زيادة صارمة أو تناقص صارم. ثم هذا النظام الخطي لديه حل فريد. (كما هو معروف ، ليس لكل نظام خطي حل. ) أيضًا ، يمكن الحصول على الحل فقط باستخدام O
( n 2
)
{\displaystyle O(n^{2})} العمليات الحسابية في حين أن الحل القياسي من المكتبة سوف يستغرق O
( n 3
)
{\displaystyle O(n^{3})} عمليات. هذا هو الدليل البسيط: حساب التداخل القياسي من الدرجة n
p 1
(
x
)
{\displaystyle p_{1}(x)} ل f
(
x
)
{\displaystyle f(x)} في العقد الأول n +1 وأيضًا المقحم القياسي من الدرجة n
p 2
(
x
)
{\displaystyle p_{2}(x)} على الاحداثيات (
−
1 ) i
{\displaystyle (-1)^{i}}
p 1
( x i
)
=
f
( x i
)
, p 2
( x i
)
=
(
−
1 ) i
,
i
=
0
,
.
.
.
,
n
.
{\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.}
تحقيقا لهذه الغاية ، استخدم في كل مرة صيغة الاستيفاء لنيوتن مع الفروق المقسمة في الترتيب 0
,
.
.
.
,
n
{\displaystyle 0,...,n} و O
( n 2
)
{\displaystyle O(n^{2})} عمليات حسابية. كثير الحدود
p 2
(
x
)
{\displaystyle p_{2}(x)} له رقم i -th صفر بين
x i
−
1
{\displaystyle x_{i-1}} و
x i
,

i
=
1
,
.
.
.
,
n
{\displaystyle x_{i},\ i=1,...,n} ، وبالتالي لا مزيد من الأصفار بين
x n
{\displaystyle x_{n}} و
x n
+
1
{\displaystyle x_{n+1}} :
p 2
( x n
)
{\displaystyle p_{2}(x_{n})} و
p 2
( x n
+
1
)
{\displaystyle p_{2}(x_{n+1})} لها نفس العلامة (
−
1 ) n
{\displaystyle (-1)^{n}} . التركيبة الخطية p
(
x
)
:= p 1
(
x
)
− p 2
(
x
) ⋅ E
{\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E} هي أيضًا كثيرة حدود من الدرجة n و p
( x i
)
= p 1
( x i
)
− p 2
( x i
) ⋅ E

=

f
( x i
)
−
(
−
1 ) i
E
,




i
=
0
,
…
,
n
.
{\displaystyle p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.}
هذه هي نفس المعادلة أعلاه لـ i
=
0
,
.
.
.
,
n
{\displaystyle i=0,...,n} ولأي اختيار من E. نفس المعادلة لـ i = n +1 هي p
( x n
+
1
)

=
p 1
( x n
+
1
)
− p 2
( x n
+
1
) ⋅ E

=

f
( x n
+
1
)
−
(
−
1 ) n
+
1
E
{\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:
E

:=

p 1
( x n
+
1
)
−
f
( x n
+
1
) p 2
( x n
+
1
)
+
(
−
1 ) n .
{\displaystyle E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.}
كما ذكر أعلاه ، فإن المصطلحين في المقام لهما نفس العلامة: E وبالتالي p
(
x
)
≡ b 0
+ b 1
x
+
…
+ b n x n
{\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}} دائمًا ما تكون محددة جيدًا. الخطأ في العقد المحددة n +2 موجب وسالب بدوره لأن p
( x i
)
−
f
( x i
)

=

−
(
−
1 ) i
E
,


i
=
0
,
.
.
.
,
n + 1.
{\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.}
تنص نظرية شارل جون دو لا فالي بوسان على أنه في ظل هذه الحالة لا يوجد كثير حدود من الدرجة n مع وجود خطأ أقل من E. في الواقع ، إذا وجدت مثل هذه كثيرة الحدود ، فسمها
p
~ (
x
)
{\displaystyle {\tilde {p}}(x)} ثم الاختلاف p
(
x
)
− p
~ (
x
)
=
(
p
(
x
)
−
f
(
x
)
)
−
( p
~ (
x
)
−
f
(
x
)
)
{\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))} سيظل موجبًا / سلبيًا عند n +2 عقد
x i
{\displaystyle x_{i}} وبالتالي تحتوي على n +1 أصفار على الأقل وهو أمر مستحيل بالنسبة لكثيرات الحدود من الدرجة n . وبالتالي ، فإن هذا E هو الحد الأدنى للحد الأدنى للخطأ الذي يمكن تحقيقه مع كثيرات الحدود من الدرجة n . الخطوة 2 تغير التدوين من
b 0
+ b 1
x
+
.
.
.
+ b n x n
{\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}} ل p
(
x
)
{\displaystyle p(x)} . الخطوة 3 تعمل على تحسين عقد الإدخال
x 0
,
.
.
.
, x n
+
1
{\displaystyle x_{0},...,x_{n+1}} وأخطائهم ±
E
{\displaystyle \pm E} على النحو التالي. في كل منطقة P ، العقدة الحالية
x i
{\displaystyle x_{i}} يتم استبداله بالمكبر المحلي x
¯
i
{\displaystyle {\bar {x}}_{i}} وفي كل منطقة N
x i
{\displaystyle x_{i}} مع المصغر المحلي. (يتوقع x
¯
0
{\displaystyle {\bar {x}}_{0}} في A ، و x
¯
i
{\displaystyle {\bar {x}}_{i}} قريب
x i
{\displaystyle x_{i}} ، و x
¯
n
+
1
{\displaystyle {\bar {x}}_{n+1}} عند B. ) ليست هناك حاجة إلى دقة عالية هنا ، يجب أن يكون البحث القياسي عن الخط مع بضع نوبات تربيعية كافياً. (انظر ) يترك
z i
:=
p
(
x
¯
i
)
−
f
(
x
¯
i
)
{\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})} . كل سعة
|
z i | {\displaystyle |z_{i}|} أكبر من أو يساوي E. تنطبق أيضًا نظرية شارل جون دو لا فالي بوسان وإثباتها
z 0
,
.
.
.
, z n
+
1
{\displaystyle z_{0},...,z_{n+1}} مع min
{ |
z i | }
≥
E
{\displaystyle \min\{|z_{i}|\}\geq E} كالحد الأدنى الجديد لأفضل خطأ ممكن مع كثيرات الحدود من الدرجة n . علاوة على ذلك، max
{ |
z i | }
{\displaystyle \max\{|z_{i}|\}} يأتي في متناول اليد باعتباره حدًا أعلى واضحًا لأفضل خطأ ممكن. الخطوة 4: مع min { |
z i | }
{\displaystyle \min \,\{|z_{i}|\}} و max { |
z i | }
{\displaystyle \max \,\{|z_{i}|\}} كحد أدنى وأعلى لأفضل خطأ تقريب ممكن ، لدى المرء معيار إيقاف موثوق: كرر الخطوات حتى max
{ |
z i | }
−
min
{ |
z i | }
{\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}} صغير بما فيه الكفاية أو لم يعد يتناقص. تشير هذه الحدود إلى التقدم.

شرح مبسط

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