طريقة القاطع

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

طريقة القاطع هي طريقة عددية تكرارية لإيجاد جذر دالة f . بمعلومية قيمتين ابتدائيتين x₀ و x₁ _، تعمل الطريقة وفقًا للعلاقة التكرارية _.

${\displaystyle x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}={\frac {x_{n-2}f(x_{n-1})-x_{n-1}f(x_{n-2})}{f(x_{n-1})-f(x_{n-2})}}.}$

هذه علاقة تكرارية غير خطية من الدرجة الثانية، وهي معرفة جيدًا بمعلومية الدالة _f والقيمتين الابتدائيتين x₀ و x₁ _. من الناحية المثالية، ينبغي اختيار القيم الابتدائية قريبة من الصفر المطلوب.

انطلاقًا من القيمتين الابتدائيتين x₀ و x₁، نرسم خطًا مستقيمًا يمر بالنقطتين (x₀, f( x₀ ) ) _و ( x₁ , f ₍ x₁ ) ₎ ، كما هو موضح في الصورة أعلاه . _معادلة هذا _الخط ، بصيغة نقطة-نقطة ، _[ ^{2 ] هي}

${\displaystyle y={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}(x-x_{1})+f(x_{1}).}$

جذر هذه الدالة الخطية ، أي قيمة x التي تحقق y = 0، هو

${\displaystyle x=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}.}$

ثم نستخدم هذه القيمة الجديدة لـ x كـ x2 ونكرر العملية، باستخدام _x1 و x2 بدلاً من x0 و x1 . نستمر في هذه العملية، ونحل لإيجاد _x3 و _x4 ، _{وهكذا ، حتى} نصل إلى مستوى عالٍ من الدقة (فرق صغير بما فيه الكفاية _بين xn و _xn - _{1 )} .

$\begin{aligned}x_{2}=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}},\\[6pt]x_{3}=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}},\\[6pt]&\,\,\,\vdots \\[6pt]x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}.\end{aligned}}}$

التكرار${\displaystyle x_{n}}$تتقارب نتائج طريقة القاطع إلى جذر${\displaystyle f}$إذا كانت القيم الأولية${\displaystyle x_{0}}$و${\displaystyle x_{1}}$قريبة بما يكفي من الجذر و${\displaystyle f}$حسن السلوك. عندما${\displaystyle f}$الدالة قابلة للتفاضل مرتين بشكل مستمر، والجذر المعني هو جذر بسيط، أي أن له رتبة 1، ورتبة التقارب هي النسبة الذهبية.${\displaystyle \varphi =(1+{\sqrt {5}})/2\approx 1.618.}$^{[ 3 ]} هذا التقارب هو فوق الخطي ولكنه دون التربيعي.

إذا لم تكن القيم الأولية قريبة بما يكفي من الجذر أو${\displaystyle f}$إذا لم يكن سلوك الدالة منتظمًا، فلا يوجد ضمان لتقارب طريقة القاطع على الإطلاق. لا يوجد تعريف عام لعبارة "قريب بما فيه الكفاية"، ولكن معيار التقارب يتعلق بمدى "تذبذب" الدالة على الفترة بين القيم الابتدائية. على سبيل المثال، إذا${\displaystyle f}$تكون قابلة للتفاضل على تلك الفترة، وهناك نقطة حيث${\displaystyle f'=0}$في هذه الفترة، قد لا تتقارب الخوارزمية.

لا تتطلب طريقة القاطع، ولا تضمن، بقاء الجذر محصورًا بين تكرارات متسلسلة، كما هو الحال في طريقة التنصيف ، ولذلك فهي لا تتقارب دائمًا. تستخدم طريقة الوضع الخاطئ (أو القاعدة الخاطئة ) نفس صيغة طريقة القاطع، ولكنها لا تطبق الصيغة على الجذر.${\displaystyle x_{n-1}}$و${\displaystyle x_{n-2}}$، مثل طريقة القاطع، ولكن على${\displaystyle x_{n-1}}$وفي التكرار الأخير${\displaystyle x_{k}}$بحيث${\displaystyle f(x_{k})}$و${\displaystyle f(x_{n-1})}$لها إشارة مختلفة. هذا يعني أن طريقة الوضع الخاطئ تتقارب دائمًا؛ ولكن فقط بترتيب تقارب خطي. يمكن تحقيق التقارب بترتيب تقارب فوق الخطي، كما هو الحال في طريقة القاطع، من خلال تحسينات على طريقة الوضع الخاطئ (انظر Regula falsi § تحسينات في Regula falsi ) مثل طريقة ITP أو طريقة إلينوي .

يمكن اشتقاق صيغة التكرار لطريقة القاطع من صيغة طريقة نيوتن

${\displaystyle x_{n}=x_{n-1}-{\frac {f(x_{n-1})}{f'(x_{n-1})}}}$

باستخدام تقريب الفروق المحدودة ، لقيمة صغيرة${\displaystyle \epsilon =x_{n-1}-x_{n-2}}$:

${\displaystyle f'(x_{n-1})=\lim _{\epsilon \rightarrow 0}{\frac {f(x_{n-1})-f(x_{n-1}-\epsilon )}{\epsilon }}\approx {\frac {f(x_{n-1})-f(x_{n-2})}{x_{n-1}-x_{n-2}}}}$

يمكن تفسير طريقة القاطع على أنها طريقة يتم فيها استبدال المشتقة بتقريب، وبالتالي فهي طريقة شبه نيوتن .

إذا قارنا طريقة نيوتن بطريقة القاطع، نلاحظ أن طريقة نيوتن تتقارب أسرع (من الرتبة 2 مقابل الرتبة φ ≈ 1.6 للنسبة الذهبية ). ^{[ 3 ]} مع ذلك، تتطلب طريقة نيوتن حساب كليهما  ${\displaystyle f}$ومشتقاته${\displaystyle f'}$في كل خطوة، بينما تتطلب طريقة القاطع فقط تقييم${\displaystyle f}$لذلك، قد تكون طريقة القاطع أسرع في بعض الأحيان من الناحية العملية. على سبيل المثال، إذا افترضنا أن تقييم${\displaystyle f}$^{إذا استغرق حساب المشتقة نفس الوقت اللازم لحساب المشتقة ،} وتجاهلنا جميع التكاليف الأخرى، فيمكننا تنفيذ خطوتين من طريقة القاطع (تقليل لوغاريتم الخطأ بمعامل φ² ≈ 2.6) بنفس تكلفة خطوة واحدة من طريقة نيوتن (تقليل لوغاريتم الخطأ بمعامل 2)، لذا فإن طريقة القاطع أسرع. في الأبعاد الأعلى، قد يصبح حساب المجموعة الكاملة من المشتقات الجزئية المطلوبة لطريقة نيوتن، أي مصفوفة جاكوبي ، أكثر تكلفة بكثير من حساب الدالة نفسها. مع ذلك، إذا أخذنا في الاعتبار المعالجة المتوازية لحساب المشتقة أو المشتقات، فقد تكون طريقة نيوتن أسرع من حيث وقت المعالجة، على الرغم من أنها لا تزال تتطلب عمليات حسابية أكثر إجمالاً.   

رياضياً، فإن الشكلين التاليين لطريقة القاطع متكافئان: $${\displaystyle x_{n+1}=x_{n}-f(x_{n})\left[{\frac {x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}}\right]}$$ و $${\displaystyle x_{n+1}={\frac {x_{n-1}f(x_{n})-x_{n}f(x_{n-1})}{f(x_{n})-f(x_{n-1})}}.}$$

عند استخدام الحساب التقريبي، على سبيل المثال الحساب اليدوي الذي يتم إجراؤه لعدد ثابت من المنازل العشرية أو الحساب الثنائي ذي الفاصلة العائمة المتاح على أجهزة الكمبيوتر، فإن الإصدار الأول هو الأفضل لسببين:

• وهو على شكل${\displaystyle x_{n+1}=x_{n}-f(x_{n})\Delta }$، لعدد ما${\displaystyle \Delta }$حتى لو${\displaystyle \Delta }$إذا كانت القيمة غير دقيقة، فسيكون التغيير في تقدير الجذر صغيرًا عند التقارب لأن${\displaystyle f(x_{n})}$سيكون صغيرًا أيضًا.
• أما الشكل الثاني فهو عرضة للإلغاء الكارثي ، لأن${\displaystyle f(x_{n})\to f(x_{n-1})}$مع اقتراب التقارب، يمكن أن يكون خطأ الإلغاء في المقام كبيرًا.

تُعد طريقة برودن تعميمًا لطريقة القاطع لأكثر من بُعد واحد.

يُظهر الرسم البياني التالي الدالة f باللون الأحمر وخط القاطع الأخير باللون الأزرق الغامق. في الرسم البياني، يبدو أن نقطة تقاطع خط القاطع مع المحور السيني تُقارب جذر الدالة f بشكل جيد .

لنفترض أننا نبحث عن حل لكثير الحدود

${\displaystyle f(x)=2x^{3}-x-3\,.}$

تطبيق طريقة القاطع مع التخمينات الأولية${\displaystyle x_{0}=1}$و${\displaystyle x_{1}=2}$يعطي التقريبات التالية:

التكرار	${\displaystyle x_{n}}$	${\displaystyle f(x_{n})}$
2	${\displaystyle 1.153846153846153}$	${\displaystyle -1.0814747382794727}$
3	${\displaystyle 1.334985133795837}$	${\displaystyle 0.4233966484501184}$
4	${\displaystyle 1.284021551332461}$	${\displaystyle -5.00597\times 10^{-2}}$
5	${\displaystyle 1.289410061128775}$	${\displaystyle -1.91967\times 10^{-3}}$
6	${\displaystyle 1.289624937539790}$	${\displaystyle 9.30251\times 10^{-6}}$
7	${\displaystyle 1.289623901294108}$	${\displaystyle -1.77635\times 10^{-15}}$

يصف الكود الزائف التالي طريقة القاطع لتقريب جذر المعادلة${\displaystyle f(x)=0}$. يُعيد تقديرًا${\displaystyle x_{2}}$ذلك يرضي${\displaystyle |x_{2}-x_{1}|<\varepsilon }$، أين${\displaystyle \varepsilon }$هو هامش سماحية يحدده المستخدم.

المدخلات: الدالة f ، التقريبات الأولية x0 و x1 ، التسامح ε ، الحد الأقصى للتكرارات Nmax. من أجل n = 0 إلى Nmax، نفّذ ما يلي: x2 ← x1 - f ( x1 )·( x1 - x0 ) / ( f ( x1 ) - f ( x0 )). إذا كان | x2 − x1 | < ε ، فأرجع x2 . نهاية الحلقة. x0 ، x1 ← x1 ، x2. نهاية الحلقة. أرجع x2.

• طريقة الوضع الخاطئ

• أفرييل، موردخاي (1976). البرمجة غير الخطية: التحليل والأساليب . برنتيس هول. ص 220-221 . ISBN  0-13-623603-0.
• ألين، مايرون ب.؛ إسحاقسون، إيلي ل. (1998). التحليل العددي للعلوم التطبيقية . جون وايلي وأولاده . ص 188-195 . ISBN  978-0-471-55266-6.

• ملاحظات حول طريقة القاطع ، عرض تقديمي، ماثكاد، مابل، ماثيماتيكا، ماتلاب في معهد الأساليب العددية الشاملة
• وايسشتاين، إريك دبليو. "طريقة القاطع" . عالم الرياضيات .