خوارزمية جاوس-ليجندر

الموسوعة الحرة

خوارزمية غاوس -ليجندر هي خوارزمية لحساب أرقام العدد π . وتتميز بسرعة تقاربها، حيث تنتج 45 مليون رقم صحيح للعدد π في 25 تكرارًا فقط . مع ذلك، لها بعض العيوب (على سبيل المثال، تستهلك ذاكرة حاسوبية كبيرة)، ولذلك استخدمت جميع الحسابات القياسية لسنوات عديدة طرقًا أخرى، وغالبًا ما كانت خوارزمية تشودنوفسكي . لمزيد من التفاصيل، انظر التسلسل الزمني لحساب π . 

تعتمد هذه الطريقة على أعمال كارل فريدريش غاوس (1777-1855) وأدريان ماري ليجندر (1752-1833) بالإضافة إلى خوارزميات حديثة للضرب والجذور التربيعية . وتقوم هذه الطريقة باستبدال عددين بشكل متكرر بمتوسطهما الحسابي والهندسي ، وذلك لتقريب المتوسط ​​الحسابي الهندسي لهما .

النسخة المعروضة أدناه تُعرف أيضًا باسم خوارزمية جاوس-أويلر ، برنت-سلامين (أو سلامين-برنت ) ؛ [ 1 ] وقد اكتشفها بشكل مستقل في عام 1975 كل من ريتشارد برنت ويوجين سلامين . استُخدمت هذه الخوارزمية في عام 1999 لحساب أول 200 مليار رقم عشري من π ، وتم التحقق من النتائج باستخدام خوارزمية بورفين .

الخوارزمية

  1. ضبط القيمة الأولية:أ0=1ب0=12ص0=1ت0=14.{\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad p_{0}=1\qquad t_{0}={\frac {1}{4}}.}
  2. كرر التعليمات التالية حتى يظهر الفرق بينأن+1{\displaystyle a_{n+1}}وبن+1{\displaystyle b_{n+1}}ضمن الدقة المطلوبة:أن+1=أن+بن2،بن+1=أنبن،صن+1=2صن،تن+1=تن-صن(أن+1-أن)2.{\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\\\b_{n+1}&={\sqrt {a_{n}b_{n}}},\\\\p_{n+1}&=2p_{n},\\\\t_{n+1}&=t_{n}-p_{n}(a_{n+1}-a_{n})^{2}.\\\end{aligned}}}
  3. ثم يتم تقريب قيمة π على النحو التالي:π≈(أن+1+بن+1)24تن+1.{\displaystyle \pi \approx {\frac {(a_{n+1}+b_{n+1})^{2}}{4t_{n+1}}}.}

تعطي التكرارات الخمس الأولى (التقريبات المعطاة حتى الرقم غير الصحيح الأول):

3.140...{\displaystyle 3.140\dots }
3.14159264...{\displaystyle 3.14159264\dots }
3.1415926535897932382...{\displaystyle 3.1415926535897932382\dots }
3.14159265358979323846264338327950288419711...{\displaystyle 3.14159265358979323846264338327950288419711\dots }
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998625...{\displaystyle 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998625\dots }

تتمتع الخوارزمية بتقارب تربيعي ، مما يعني أساسًا أن عدد الأرقام الصحيحة يتضاعف مع كل تكرار للخوارزمية.

الخلفية الرياضية

حدود المتوسط ​​الحسابي الهندسي

يُحسب المتوسط ​​الحسابي الهندسي لعددين، a₀ و b₀ ، عن طريق حساب نهاية المتتابعات

أن+1=أن+بن2،بن+1=أنبن،{\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\[6pt]b_{n+1}&={\sqrt {a_{n}b_{n}}},\end{aligned}}}

وكلاهما يتقاربان إلى نفس النهاية. إذاأ0=1{\displaystyle a_{0}=1}وب0=كوس⁡φ{\displaystyle b_{0}=\cos \varphi }إذن الحد هوπ2ك(الخطيئة⁡φ){\textstyle {\pi \over 2K(\sin \varphi )}}أينك(ك){\displaystyle K(k)}هو التكامل الإهليلجي الكامل من النوع الأول

ك(ك)=∫0π/2دθ1-ك2الخطيئة2⁡θ.{\displaystyle K(k)=\int _{0}^{\pi /2}{\frac {d\theta }{\sqrt {1-k^{2}\sin ^{2}\theta }}}.}

لوج0=الخطيئة⁡φ{\displaystyle c_{0}=\sin \varphi }،جأنا+1=أأنا-أأنا+1{\displaystyle c_{i+1}=a_{i}-a_{i+1}}، ثم

∑أنا=0∞2أنا-1جأنا2=1-هـ(الخطيئة⁡φ)ك(الخطيئة⁡φ){\displaystyle \sum _{i=0}^{\infty }2^{i-1}c_{i}^{2}=1-{E(\sin \varphi ) \over K(\sin \varphi )}}

أينهـ(ك){\displaystyle E(k)}هو التكامل الإهليلجي الكامل من النوع الثاني :

هـ(ك)=∫0π/21-ك2الخطيئة2⁡θدθ{\displaystyle E(k)=\int _{0}^{\pi /2}{\sqrt {1-k^{2}\sin ^{2}\theta }}\;d\theta }

كان غاوس على علم بهاتين النتيجتين. [ 2 ] [ 3 ] [ 4 ]

هوية ليجندر

أثبت ليجيندر الهوية التالية:

ك(كوس⁡θ)هـ(الخطيئة⁡θ)+ك(الخطيئة⁡θ)هـ(كوس⁡θ)-ك(كوس⁡θ)ك(الخطيئة⁡θ)=π2،{\displaystyle K(\cos \theta )E(\sin \theta )+K(\sin \theta )E(\cos \theta )-K(\cos \theta )K(\sin \theta )={\pi \over 2},}

للجميعθ{\displaystyle \theta }[ 2 ]​

برهان ابتدائي باستخدام حساب التكامل

يمكن إثبات أن خوارزمية جاوس-ليجندر تعطي نتائج تتقارب إلىπ{\displaystyle \pi }باستخدام حساب التكامل فقط. وقد تم ذلك هنا [ 5 ] وهنا [ 6 ] .

انظر أيضاً

مراجع

  1. ↑ برنت، ريتشارد ، خوارزميات قديمة وجديدة لحساب باي ، رسائل إلى المحرر، إشعارات الجمعية الرياضية الأمريكية 60(1)، ص 7
  2. 1 2 برنت، ريتشارد (1975)، تراوب، جيه إف (محرر)، "طرق إيجاد الأصفار متعددة الدقة وتعقيد تقييم الدوال الأولية" ، التعقيد الحسابي التحليلي ، نيويورك: أكاديميك برس، ص 151-176 ، مؤرشف من الأصل في 23 يوليو 2008 ، تم استرجاعه في 8 سبتمبر 2007 
  3. ↑ سلامين، يوجين ، حساب باي ، مذكرة مختبر تشارلز ستارك درابر ISS رقم 74-19، 30 يناير 1974، كامبريدج، ماساتشوستس
  4. ↑ سلامين، يوجين (1976)، "حساب باي باستخدام المتوسط ​​الحسابي الهندسي"، رياضيات الحساب ، المجلد 30، العدد 135، الصفحات 565-570 ، doi : 10.2307/2005327 ، ISSN 0025-5718 ، JSTOR 2005327     
  5. ↑ لورد، نيك (1992)، "حسابات حديثة لـ π: خوارزمية جاوس-سلامين"، المجلة الرياضية ، 76 (476): 231-242 ، doi : 10.2307/3619132 ، JSTOR 3619132 ، S2CID 125865215  
  6. ↑ ميلا، لورنز (2019)، برهان سهل لثلاث خوارزميات π تكرارية ، arXiv : 1907.04110