Metoda acordurilor

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 15 octombrie 2019; verificările necesită 12 modificări .

Metoda acordurilor este o metodă numerică iterativă pentru găsirea rădăcinii aproximative a unei ecuații.

Descrierea geometrică a metodei secantei

Vom căuta zeroul funcției . Să alegem două puncte de plecare și să tragem o linie prin ele. Acesta va intersecta axa x în punctul . Acum să găsim valoarea funcției cu abscisa . Vom lua în considerare temporar rădăcina de pe segment . Fie punctul să aibă o abscisă și să se așeze pe grafic. Acum în loc de puncte și vom lua punct și punct . Acum cu aceste două puncte vom face aceeași operație și așa mai departe, adică vom obține două puncte și vom repeta operația cu ele. Segmentul care leagă ultimele două puncte intersectează axa absciselor într-un punct a cărui valoare a abscisei poate fi considerată aproximativ rădăcină. Aceste acțiuni trebuie repetate până când obținem valoarea rădăcină cu aproximarea dorită. $f(x)$ $C_{{1}}(x_{{1}};y_{{1}})$ $C_{{2}}(x_{{2}};y_{{2}})$ $(x_{{3}};0)$ $x_{{3}}$ $x_{{3}}$ $[x_{{1}};x_{{2}}]$ $C_{{3}}$ $x_{{3}}$ $C_{1}$ $C_{2}$ $C_{{3}}$ $C_{2}$ $C_{{n+1}}$ $C_{{n}}$

Descrierea algebrică a metodei secantei

Fie abscisele capetelor coardei, fie ecuația funcției rezolvată prin metoda secantei. Aflați coeficienții și din sistemul de ecuații $x_{1},x_{2}$ $f(x)=0$ $k$ $b$

\left\{{\begin{aligned}f(x_{1})&=kx_{1}+b,\\f(x_{2})&=kx_{2}+b.\\\ sfârşit{aliniat}}\dreapta.

Scădeți a doua din prima ecuație:

f(x_{1})-f(x_{2})=k(x_{1}-x_{2}),

atunci găsim coeficienții și : $k$ $b$

k={\frac {f(x_{2})-f(x_{1})}{x_{2}-x_{1))},

apoi

b=f(x_{1})-{\frac {(f(x_{2})-f(x_{1}))x_{1}}{x_{2}-x_{1}} }.

Ecuația ia forma

y={\frac {f(x_{2})-f(x_{1})}{x_{2}-x_{1}}}(x-x_{1})+f(x_{ unu}).

Astfel, acum putem găsi prima aproximare a rădăcinii obținută prin metoda secantei:

x_{3}=x_{1}-{\frac {(x_{2}-x_{1})f(x_{1})}{f(x_{2})-f(x_{1 })}}.

Acum să luăm coordonatele și să repetăm toate operațiunile făcute, găsind o nouă aproximare a rădăcinii. Astfel, formula iterativă a metodei secantei are forma: $x_{2}$ $x_{3}$

x_{i+1}=x_{i-1}-{\dfrac {f(x_{i-1})\cdot (x_{i}-x_{i-1})}{f(x_ {i})-f(x_{i-1})}}.

Operația trebuie repetată până când este mai mică sau egală cu valoarea de eroare specificată. $|x_{i}-x_{i-1}|$

Metoda acordurilor cu formulă iterativă

Uneori metoda secantei se numește metoda cu formula iterativă

x_{i+1}=x_{i}-{\dfrac {f(x_{i})\cdot (x_{i}-x_{0})}{f(x_{i})-f (x_{0})}}.

Această metodă poate fi considerată o variație a metodei iterației simple și are o rată de convergență mai lentă. Mai mult, pentru certitudine, această metodă va fi numită metoda acordurilor, iar metoda descrisă în secțiunea anterioară, metoda secantelor.

Un exemplu de utilizare a metodei secantei

Rezolvăm ecuația prin metoda secantei. Să setăm precizia ε=0.001 și să luăm ca aproximări inițiale capetele segmentului pe care este separată rădăcina: și , valorile numerice și sunt alese arbitrar. Calculele sunt efectuate până când inegalitatea este îndeplinită . $x^{3}-18x-83=0$ $x_0$ $x_{1}$ $x_{0}=8$ $x_{1}=3$ $x_{0}=8$ $x_{1}=3$ $|x_{i+1}-x_{i}|<\varepsilon$

În exemplul nostru, valoarea este înlocuită , iar valoarea este înlocuită . Valoarea va fi valoarea numerică obținută prin această formulă. În viitor, înlocuim în formulă valoarea , și valoarea . $x_{{i-1}}$ $x_{0}=8$ $x_{i}$ $x_{1}=3$ $x_{{i+1}}$ $x_{2}=\subliniați {}4,3924051$ $x_{2}=\subliniați {}4,3924051$ $x_{i}$ $x_{1}=3$ $x_{{i-1}}$

Folosind această formulă, obținem în mod constant (sunt subliniate cifrele semnificative corecte): (imaginea din metoda acordurilor, dar nu secantelor, vă rugăm să separați secțiunile)

x_{2}=\subliniați {}4,3924051

; ; ; ; ; ; ; ; ; ;

x_{3}=\subliniați {5},1622721

x_{4}=\subliniați {5}.4988422

x_{5}=\subliniază {5,6}295040

x_{6}=\subliniați {5.6}777792

x_{7}=\subliniați {5.6}952826

x_{8}=\subliniază {5,70}15852

x_{9}=\subliniază {5,70}38490

x_{{10}}=\subliniază {5.704}6613

x_{{11}}=\subliniază {5.704}9528

Să verificăm că metoda funcționează chiar dacă și sunt alese pe aceeași parte a rădăcinii (adică dacă rădăcina nu este separată pe segmentul dintre aproximările inițiale). Luați pentru aceeași ecuație și . Apoi: (imaginea nu mai este din metoda secantei, ci din metoda dihotomiei ) $x_0$ $x_{1}$ $x_{0}=8$ $x_{1}=7$

x_{2}=\subliniază {}6.1125828

; ; ; ; ; ; ; ;

x_{3}=\subliniați {5}.8452240

x_{4}=\subliniază {5.7}546403

x_{5}=\subliniază {5.7}227874

x_{6}=\subline {5.7}114425

x_{7}=\subliniază {5,70}73836

x_{8}=\subliniați {5.705}9290

x_{9}=\subliniază {5.705}4075

Avem aceeași valoare a rădăcinii în același număr de iterații.

Convergența metodei secantei

Iterațiile metodei secante converg către rădăcină dacă valorile inițiale și sunt suficient de aproape de rădăcină. Metoda secantei este rapidă. Ordinea de convergență α este egală cu raportul de aur : $f(x)$ $x_{0}$ $x_{1}$

\alpha ={\frac {1+{\sqrt {5}}}{2}}\aprox 1{,}618...

Astfel, ordinea de convergență este mai mare decât liniară, dar nu pătratică, ca în cazul metodei aferente lui Newton .

Acest rezultat este valid dacă este de două ori diferențiabil și rădăcina nu este un multiplu - . $f(x)$ $\xi$ $f'(\xi )\neq 0$

Ca și în cazul majorității metodelor rapide, este dificil să se formuleze condiții de convergență pentru metoda secantei. Dacă punctele de pornire sunt suficient de aproape de rădăcină, atunci metoda converge, dar nu există o definiție generală a „suficient de aproape”. Convergența metodei este determinată de cât de „ondulată” este funcția în . De exemplu, dacă există un punct în intervalul în care , atunci procesul poate să nu convergă. $[x_{0},x_{1}]$ $f'(x)=0$

Criteriul și rata de convergență a metodei acordurilor

Dacă este o funcție de două ori diferențiabilă continuu, iar semnul este păstrat pe intervalul luat în considerare, atunci aproximările obținute vor converge monoton către rădăcină. Dacă rădăcina ecuației este pe intervalul , derivatele și pe acest interval sunt continue și rețin semnele constante și , atunci se poate demonstra [1] că eroarea soluției aproximative tinde spre zero la , adică metoda converge și converge la viteza unei progresii geometrice (în acest caz, spun ei, că are o rată de convergență liniară ). $f(x)$ $f''(x)$ $\xi$ $f(\xi )=0$ $[a,b]$ $f'(x)$ $f''(x)$ $f''(b)f(b)>0$ $n\rightarrow\infty$

Context istoric

Primul care a reușit să găsească soluții aproximative pentru ecuațiile cubice a fost Diophantus , punând astfel bazele metodei acordurilor. Lucrările supraviețuitoare ale lui Diophantus raportează acest lucru. Cu toate acestea, primul care a înțeles metodele sale a fost Fermat în secolul al XVII-lea, iar primul care a explicat metoda acordurilor a fost Newton (1670). [2]

Implementare

C++

#include <iostream> #include <math.h> dublu f ( dublu x ) { returnează sqrt ( fabs ( cos ( x ))) - x ; // Înlocuiește cu funcția ale cărei rădăcini le căutăm } // a, b - limitele acordurilor, epsilon - eroare necesară double findRoot ( double a , double b , double epsilon ) { în timp ce ( fabs ( b - a ) > epsilon ) { a = b - ( b - a ) * f ( b ) / ( f ( b ) - f ( a )); b = a - ( a - b ) * f ( a ) / ( f ( a ) - f ( b )); } // a, b — (i - 1)-lea și i-lea membri returnează b ; }

Python

din math import sin din tastarea import Callable import unittest def secant ( f : Callable [[ float ], float ], x0 : float , eps : float = 1e-7 , kmax : int = 1e3 ) -> float : """ rezolvă f(x) = 0 prin metoda secantei cu precizie eps :param f: f :param x0: punct de plecare :param eps: precizie dorită :return: rădăcină f(x) = 0 """ x , x_prev , i = x0 , x0 + 2 * eps , 0 în timp ce abs ( x - x_prev ) >= eps și i < kmax : x , x_prev , i = x - f ( x ) / ( f ( x ) - f ( x_prev )) * ( x - x_prev ), x , i + unu întoarce x clasa TestSecant ( unittest . TestCase ): def test_0 ( self ): def f ( x : float ) -> float : return x ** 2 - 20 * sin ( x ) x0 , x_star = 2 , 2,7529466338187049383 sine . assertAlmostEqual ( secant ( f , x0 ), x_star ) if __name__ == '__main__' : unittest . principal ()

Modificări

Metoda poziției false diferă de metoda secantei doar prin aceea că de fiecare dată nu se iau ultimele 2 puncte, ci acele puncte care se află în jurul rădăcinii.

Vezi și

Literatură

Demidovich B. P. și Maron I. A. Fundamentele matematicii computaționale. - Știință, 1970. - S. 664.
Bakhvalov, Jidkov, Kobelkov. Metode numerice. - Știința. — ISBN 5-94774-060-5 .

Note

↑ Algebră (link inaccesibil) . Consultat la 24 noiembrie 2009. Arhivat din original pe 3 decembrie 2007. (nedefinit)
↑ Matematica și istoria ei. John Stillwell

Link -uri

Rezolvarea ecuațiilor prin metoda acordurilor online
„Metode pentru rezolvarea ecuațiilor algebrice” pe site-ul www.petrsu.ru Copie de arhivă din 8 ianuarie 2018 pe Wayback Machine
„Metode de dihotomie” pe site-ul www.epikoiros.narod.ru
Yu. Gubar, Curs „Introducere în modelarea matematică” Cursul 4: Metode numerice de rezolvare a ecuațiilor neliniare // Intuit.ru , 15.03.2007