طريقة برنت

في التحليل العددي ، تُعدّ طريقة برنت خوارزمية هجينة لإيجاد الجذور، تجمع بين طريقة التنصيف ، وطريقة القاطع ، والاستيفاء التربيعي العكسي . تتميز هذه الطريقة بموثوقية التنصيف، ولكنها قد تكون سريعة كبعض الطرق الأقل موثوقية. تحاول الخوارزمية استخدام طريقة القاطع أو الاستيفاء التربيعي العكسي، نظرًا لتقاربهما السريع، إن أمكن، ولكنها تعود إلى طريقة التنصيف الأكثر موثوقية عند الضرورة. تُنسب طريقة برنت إلى ريتشارد برنت ^{[ 1 ]} ، وهي مبنية على خوارزمية سابقة لثيودوروس ديكر ^{[ 2 ]} . ولذلك، تُعرف هذه الطريقة أيضًا باسم طريقة برنت-ديكر .

تشمل التحسينات الحديثة على طريقة برنت طريقة تشاندرباتلا، وهي أبسط وأسرع للدوال المسطحة حول جذورها؛ ^{[ 3 ] [ 4 ]} طريقة ريدرز ، التي تقوم بعمليات استيفاء أسية بدلاً من التربيعية مما يوفر صيغة مغلقة أبسط للتكرارات؛ وطريقة ITP وهي طريقة هجينة بين regula-falsi و bisection والتي تحقق ضمانات مثلى في أسوأ الحالات والتقارب.

تعود فكرة الجمع بين طريقة التنصيف وطريقة القاطع إلى ديكر (1969) .

لنفترض أننا نريد حل المعادلة f ( x ) = 0. كما _{هو الحال} في طريقة التنصيف، نحتاج إلى تهيئة طريقة ديكر بنقطتين، ولتكن a₀ و b₀ _، بحيث تكون إشارات f ( a₀ ) و f ( b₀ ) متعاكسة. إذا _كانت f متصلة على _الفترة [ a₀ , b₀ ]، فإن نظرية _القيمة المتوسطة تضمن وجود حل بين a₀ و _{b₀ .}

تتضمن كل عملية تكرار ثلاث نقاط:

• b _k هو التكرار الحالي، أي التخمين الحالي لجذر f .
• النقطة a _{_k} هي "النقطة المقابلة"، أي النقطة التي يكون فيها لكل من f ( a _{_k} ) و f ( b_{_k} ) إشارتان متعاكستان، وبالتالي فإن الفترة [ a _{_k} , b_{_k} ] تحتوي على الحل. علاوة على ذلك، يجب أن تكون القيمة المطلقة لـ f ( b_{_k} ) أقل من أو تساوي القيمة المطلقة لـ f ( a _{_k} )|، مما يجعل b _{_k} تخمينًا أفضل للحل المجهول من a _{_k} .
• b _{k − 1} هو التكرار السابق (بالنسبة للتكرار الأول، يتم تعيين b _{k − 1} = a ₀ ).

يتم حساب قيمتين مؤقتتين للتكرار التالي. يتم الحصول على القيمة الأولى عن طريق الاستيفاء الخطي، المعروف أيضًا باسم طريقة القاطع:

${\displaystyle s={\begin{cases}b_{k}-{\frac {b_{k}-b_{k-1}}{f(b_{k})-f(b_{k-1})}}f(b_{k}),&{\mbox{if }}f(b_{k})\neq f(b_{k-1})\\m&{\mbox{otherwise }}\end{cases}}}$

أما الثانية فتُعطى بطريقة التنصيف.

${\displaystyle m={\frac {a_{k}+b_{k}}{2}}.}$

إذا كانت نتيجة طريقة القاطع، s ، تقع تمامًا بين b _k و m ، فإنها تصبح التكرار التالي ( b _{k +1} = s )، وإلا يتم استخدام نقطة المنتصف ( b _{k +1} = m ).

ثم، تُختار قيمة النقطة المقابلة الجديدة بحيث يكون لكل من _{f(ak+1) و f(bk+1) إشارتان متعاكستان. إذا كان لكل من f(ak} ) و f _{( bk} + 1 ) إشارتان _{متعاكستان ،} فإن النقطة المقابلة تبقى كما هي : ak _{+ 1} = ak _{. وإلا} ، فإن لكل _من f ₍ bk + 1 _{) و} f ( bk ) إشارتان متعاكستان، فتصبح النقطة المقابلة الجديدة ak _{+ 1} = bk _.

وأخيرًا، إذا كان | f ( a _{k +1} )| < | f ( b _{k +1} )|، فمن المحتمل أن يكون a _{k +1} تخمينًا أفضل للحل من b _{k +1} ، وبالتالي يتم تبديل قيم a _{k +1} و b _{k +1 .}

بهذا ينتهي وصف دورة واحدة من طريقة ديكر.

تُحقق طريقة ديكر أداءً جيدًا إذا كانت الدالة f ذات سلوك جيد نسبيًا. مع ذلك، توجد حالات تستخدم فيها كل تكرار طريقة القاطع، لكن التكرارات b_{_k} تتقارب ببطء شديد (على وجه الخصوص، قد تكون قيمة | b _{_k} - b _{_k - 1} | صغيرة جدًا). ​​في هذه الحالة، تتطلب طريقة ديكر عددًا أكبر بكثير من التكرارات مقارنةً بطريقة التنصيف.

اقترح برنت (1973) تعديلًا بسيطًا لتجنب مشكلة طريقة ديكر. أضاف اختبارًا إضافيًا يجب تحقيقه قبل قبول نتيجة طريقة القاطع كقيمة تكرارية تالية. يجب تحقيق متباينتين في آن واحد:

مع مراعاة التفاوت العددي المحدد${\displaystyle \delta }$إذا استخدمت الخطوة السابقة طريقة التنصيف، فإن المتباينة${\textstyle |\delta |<|b_{ك}-b_{k-1}|}$يجب تثبيت الشرط لإجراء الاستيفاء، وإلا فسيتم تنفيذ طريقة التنصيف واستخدام نتيجتها في التكرار التالي.

إذا كانت الخطوة السابقة قد أجرت عملية استيفاء، فإن المتباينة${\textstyle |\delta |<|b_{k-1}-b_{k-2}|}$يتم استخدامها بدلاً من ذلك لتنفيذ الإجراء التالي (لاختيار) الاستيفاء (عندما تكون المتباينة صحيحة) أو طريقة التنصيف (عندما لا تكون المتباينة صحيحة).

أيضًا، إذا استخدمت الخطوة السابقة طريقة التنصيف، فإن المتباينة${\textstyle |s-b_{ك}|<{\begin{matrix}{\frac {1}{2}}\end{matrix}}|b_{k}-b_{k-1}|}$ يجب أن يتحقق الشرط، وإلا فسيتم تطبيق طريقة التنصيف واستخدام نتيجتها في التكرار التالي. إذا تم إجراء الاستيفاء في الخطوة السابقة، فإن المتباينة${\textstyle |s-b_{k}|<{\begin{matrix}{\frac {1}{2}}\end{matrix}}|b_{k-1}-b_{k-2}|}$ يتم استخدام بدلاً من ذلك.

يضمن هذا التعديل أنه في التكرار رقم k ، سيتم تنفيذ خطوة التنصيف في أكثر من${\displaystyle 2\log _{2}(|b_{k-1}-b_{k-2}|/\delta )}$تكرارات إضافية، لأن الشروط المذكورة أعلاه تجبر أحجام خطوات الاستيفاء المتتالية على الانخفاض إلى النصف كل تكرارين، وبعد ذلك على الأكثر${\displaystyle 2\log _{2}(|b_{k-1}-b_{k-2}|/\delta )}$في عدد التكرارات، سيكون حجم الخطوة أصغر من${\displaystyle \delta }$وهذا يستدعي خطوة التنصيف. أثبت برنت أن طريقته تتطلب على الأكثر N² ^{تكرارًا} ، حيث N يرمز إلى عدد التكرارات لطريقة التنصيف. إذا كانت الدالة f منتظمة، فإن طريقة برنت ستعتمد عادةً على الاستيفاء التربيعي العكسي أو الاستيفاء الخطي، وفي هذه الحالة ستتقارب بشكل أسرع من الخطي .

_{علاوة على} ذلك، تستخدم طريقة برنت الاستيفاء التربيعي العكسي بدلاً من الاستيفاء الخطي (كما هو مستخدم في طريقة القاطع). إذا كانت f ( k ) و f ( _{ak )} و f ( bk _{- 1} ) قيمًا مختلفة، فإن ذلك يزيد الكفاءة قليلاً. ونتيجة لذلك، يجب تغيير شرط قبول _s (القيمة المقترحة إما عن طريق الاستيفاء الخطي أو الاستيفاء التربيعي العكسي): يجب أن تقع s بين ( 3ak + bk ₎ / 4 و bk _.

أدخل a و b و (مؤشر إلى) دالة لـ f، ثم احسب f ( a ). احسب f ( b ) إذا كانت f ( a ) + f ( b ) ≥ 0 دالة الخروج لأن الجذر غير محاط بأقواس. إذا كان | f ( a )| < | f ( b )|، فقم بتبديل ( a , b ). إذا كان c := a، فقم بتعيين mflag. كرر حتى f ( b أو s ) = 0 أو | b - a | صغير بما يكفي (التقارب). إذا كان f ( a ) ≠ f ( c ) و f ( b ) ≠ f ( c ) ،${\textstyle s:={\frac {af(b)f(c)}{(f(a)-f(b))(f(a)-f(c))}}+{\frac {bf(a)f(c)}{(f(b)-f(a))(f(b)-f(c))}}+{\frac {cf(a)f(b)}{(f(c)-f(a))(f(c)-f(b))}}}$( استيفاء تربيعي عكسي ) وإلا${\textstyle s:=b-f(b){\frac {b-a}{f(b)-f(a)}}}$( طريقة القاطع ) نهاية الشرط إذا ( الشرط 1) s ليس بين${\displaystyle (3a+b)/4}$و ب أو (الشرط 2) ( تم تعيين mflag و | s − b | ≥ | b − c |/2) أو (الشرط 3) ( تم مسح mflag و | s − b | ≥ | c − d |/2) أو (الشرط 4) ( تم تعيين mflag و | b − c | < | δ |) أو (الشرط 5) ( تم مسح mflag و | c − d | < | δ |) ثم${\textstyle s:={\frac {a+b}{2}}}$( طريقة التنصيف ) عيّن mflag وإلا امسح mflag نهاية الشرط احسب f ( s ) d : = c (يتم تعيين d لأول مرة هنا؛ لن يتم استخدامه أعلاه في التكرار الأول لأن mflag مُعيّن) c := b إذا كان f ( a ) f ( s ) < 0 فإن b := s وإلا a := s نهاية الشرط إذا كان | f ( a )| < | f ( b )| فإن تبديل ( a , b ) نهاية الشرط نهاية التكرار أخرج b أو s (أرجع الجذر)

لنفترض أننا نبحث عن صفر للدالة المعرفة بواسطة f ( x ) = ( x + 3)( x − 1) ² .

نأخذ [ a ₀ , b ₀ ] = [ − 4, 4/3] كفترة أولية لدينا.

لدينا f ( a ₀ ) = − 25 و f ( b ₀ ) = 0.48148 (جميع الأرقام في هذا القسم مقربة)، لذلك يتم استيفاء الشروط f ( a ₀ ) f ( b ₀ ) < 0 و | f ( b ₀ )| ≤ | f ( a ₀ )|.

1. في التكرار الأول، نستخدم الاستيفاء الخطي بين ( _b - _{1 ,} f ( b - _{1 )} ) = ( _a₀ , f ( a₀ ) ) = ( -4 , -25 ) و( b₀ , f ( b₀ )) = ( _{1.33333 , 0.48148 )} ، ما ينتج عنه s = 1.23256. تقع هذه القيمة بين (3a₀ + b₀ ₎ / 4 و _b₀ ، _لذا فهي مقبولة. علاوة على ذلك، f ( 1.23256 ) = 0.22891، لذا نُعيّن a₁ ₌ a₀ _و b₁ = _{s =} 1.23256 .
2. في التكرار الثاني ، نستخدم الاستيفاء التربيعي العكسي بين ( a1 _, f ( a1 ₎ ) = ( -4 , -25 ) و( b0 _, f ( b0 ₎ ) = (1.33333, 0.48148) و( b1 , f ( b1 _{) ) = ( 1.23256} , 0.22891). ينتج عن ذلك القيمة 1.14205، وهي تقع بين (3a1 ₊ b1 ) / ₄ و b1 _. علاوة على ذلك، تتحقق المتباينة |1.14205 - b1 | ≤ | _b0 - b _{- 1 |} / 2 _، لذا تُقبل هذه القيمة. علاوة على ذلك، f (1.14205) = 0.083582، لذلك نضع a ₂ = a ₁ و b ₂ = 1.14205.
3. في التكرار الثالث ، نستخدم الاستيفاء التربيعي العكسي بين ( a₂ _, f ( a₂ ₎ ) = ( -4 , -25 ) و( b₁ _, f ( b₁ ₎ ) = (1.23256, 0.22891) و( b₂ , f ( b₂ _{) ) = ( 1.14205} , 0.083582). ينتج عن ذلك القيمة 1.09032، والتي تقع بين (3a₂ _{+ b₂} ) / 4 و b₂ _. ولكن هنا يتدخل شرط برنت الإضافي: المتباينة |1.09032 − b₂ _| ≤ | b₁ − _b₀ | / ₂ غير محققة، لذا تُرفض هذه القيمة. بدلاً من ذلك، يتم حساب نقطة المنتصف m = − 1.42897 للفترة [ a ₂ , b ₂ ]. لدينا f ( m ) = 9.26891، لذا نضع a ₃ = a ₂ و b ₃ = − 1.42897.
4. _{في التكرار الرابع} ، نستخدم الاستيفاء التربيعي العكسي بين ( a₃ _, f ( a₃ ₎ ) = (-4, -25) و(b₂, f ( b₂ ) ) = ( _1.14205 , 0.083582 ) _و ( _{b₃, f(b₃} ) ) = ( -1.42897 , 9.26891 ). ينتج عن ذلك القيمة 1.15448، وهي ليست ضمن الفترة بين (3a₃ + b₃ ₎ / 4 و _b₃ . _لذا ، نستبدلها بنقطة المنتصف m = -2.71449 . لدينا f ( m ) = 3.93934، لذلك نُعيّن a₄ ₌ a₃ _و b₄ = _-2.71449 .
5. في التكرار الخامس، ينتج عن الاستيفاء التربيعي العكسي القيمة −3.45500، والتي تقع ضمن الفترة المطلوبة. مع ذلك، كان التكرار السابق خطوة تنصيف، لذا يجب أن تتحقق المتباينة |−3.45500 − b₄| ≤ |b₄ − b₃ _| / 2. _هذه المتباينة خاطئة ، لذا نستخدم نقطة المنتصف _m = −3.35724 . لدينا f ( m ) = −6.78239 ، لذا تصبح m نقطة التقابل الجديدة ( a₅ = −3.35724 ) ويبقى التكرار كما هو _{( b₅} = b₄ ₎ .
6. في التكرار السادس، لا يمكننا استخدام الاستيفاء التربيعي العكسي لأن b₅ = b₄ . لذا، نستخدم الاستيفاء الخطي بين ( a₅ _{, f} ( a₅ ) ₎ = ( -3.35724 , -6.78239 ) و( b₅ _, f ₍ b₅ ₎ ) = ( -2.71449 , 3.93934 ) . والنتيجة هي s = -2.95064 ، والتي تحقق جميع الشروط . ولكن بما أن قيمة التكرار لم تتغير في الخطوة السابقة، فإننا نرفض هذه النتيجة ونعود إلى طريقة التنصيف. نقوم بتحديث s = -3.03587 ، و f ( s ) = -0.58418 .
7. في التكرار السابع، يمكننا استخدام الاستيفاء التربيعي العكسي مرة أخرى. والنتيجة هي s = −3.00219 ، والتي تحقق جميع الشروط. الآن، f ( s ) = −0.03515 ، لذا نضع a₇ = b₆ و _b₇ = _−3.00219 ( يتم تبديل _a₇ و b₇ بحيث يتحقق الشرط |f ( b₇ ) | ≤ | _f(a₇ ) | ) _{. ( صحيح} : الاستيفاء الخطي ) ${\displaystyle s=-2.99436,f(s)=0.089961}$)​
8. في التكرار الثامن، لا يمكننا استخدام الاستيفاء التربيعي العكسي لأن a _≠ b ≠ _6. الاستيفاء الخطي يعطي s = − 2.99994، وهو مقبول. ( صحيح  : ⁠${\displaystyle s=-2.9999,f(s)=0.0016}$)​
9. في التكرارات التالية، يتم الاقتراب بسرعة من الجذر x = − 3: b ₉ = − 3 + 6 × 10 ^{− 8} و b ₁₀ = − 3 − 3 × 10 ^{− 15.} ( صحيح  : التكرار 9  : f ( s ) = −1.4 × 10 ⁻⁷ ، التكرار 10  : f ( s ) = 6.96 × 10 ⁻¹² )

• نشر برنت (1973) تطبيقًا بلغة Algol 60 .
• تحتوي مكتبة Netlib على ترجمة Fortran لهذا التطبيق مع تعديلات طفيفة.
• تُنفذ طريقة PARI /GPsolve هذه الطريقة.
• يمكن العثور على تطبيقات أخرى للخوارزمية (في لغات C++ و C و Fortran) في كتب الوصفات العددية .
• تقوم مكتبة Apache Commons Math بتنفيذ الخوارزمية بلغة Java .
• تقوم وحدة التحسين في SciPy بتنفيذ الخوارزمية بلغة بايثون (لغة البرمجة).
• تقوم مكتبة Modelica القياسية بتنفيذ الخوارزمية في لغة Modelica .
• تقوم هذه unirootالدالة بتنفيذ الخوارزمية في لغة البرمجة R.
• تقوم هذه fzeroالدالة بتنفيذ الخوارزمية في MATLAB .
• تُنفذ مكتبة Boost (مكتبات C++) خوارزميتين تعتمدان على طريقة برنت في لغة C++ ضمن مجموعة أدوات الرياضيات:
  1. تصغير الدوال في minima.hpp مع مثال لتحديد موقع الدالة minima .
  2. يقوم البحث عن الجذور بتنفيذ TOMS748 الأحدث، وهي خوارزمية أكثر حداثة وكفاءة من خوارزمية برنت الأصلية، في TOMS748 ، والبحث عن الجذور في Boost.Math الذي يستخدم TOMS748 داخليًا مع أمثلة .
• تقوم حزمة Optim.jl بتنفيذ الخوارزمية في لغة البرمجة جوليا (Julia).
• يقوم نظام الجبر الحاسوبي Emmy (المكتوب بلغة البرمجة Clojure ) بتنفيذ نسخة معدلة من الخوارزمية المصممة لتقليل الدوال أحادية المتغير .
• البحث عن الجذر في مكتبة C# المستضافة في مشروع الكود .

• برنت، آر بي (1973)، "الفصل 4: خوارزمية ذات تقارب مضمون لإيجاد صفر دالة"، خوارزميات للتصغير بدون مشتقات ، إنجلوود كليفس، نيوجيرسي: برنتيس هول، ISBN 0-13-022335-2
• ديكر، تي جيه (1969)، "إيجاد الصفر باستخدام الاستيفاء الخطي المتتالي"، في ديجون، ب.؛ هنريسي، ب. (محرران)، الجوانب البنائية للنظرية الأساسية للجبر ، لندن: وايلي-إنترساينس، ISBN 978-0-471-20300-1

• أتكينسون، كيندال إي. (1989). "القسم 2.8". مقدمة في التحليل العددي (  الطبعة الثانية). جون وايلي وأولاده. ISBN 0-471-50023-2.
• بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007). "القسم 9.3. طريقة فان وينغاردن-ديكر-برنت" . وصفات عددية: فن الحوسبة العلمية (  الطبعة الثالثة). نيويورك: مطبعة جامعة كامبريدج. ISBN 978-0-521-88068-8أُرشف من المصدر الأصلي بتاريخ 11 أغسطس 2011. تم الاطلاع عليه بتاريخ 28 فبراير 2012 .
• ألفيلد، جنرال إلكتريك؛ بوترا، FA؛ شي ، ييكسون (سبتمبر 1995). "الخوارزمية 748: إحاطة أصفار الدوال المستمرة" . معاملات ACM على البرامج الرياضية . 21 (3): 327-344 . دوى : 10.1145 / 210089.210111 . S2CID 207192624 . 

• zeroin.f في Netlib .
• وحدة برنت بلغة C++ (وأيضًا C و Fortran و Matlab) مؤرشفة بتاريخ 5 أبريل 2018 على موقع Wayback Machine بواسطة جون بوركاردت
• تطبيق GSL .
• تطبيق Boost C++ .
• تطبيق بايثون (Scipy)