Ackordsmetod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 oktober 2019; kontroller kräver 12 redigeringar .

Ackordmetoden är en iterativ numerisk metod för att hitta den ungefärliga roten av en ekvation.

Geometrisk beskrivning av sekantmetoden

Vi kommer att leta efter nollpunkten för funktionen . Låt oss välja två startpunkter och dra en linje genom dem. Den kommer att skära x- axeln vid punkten . Låt oss nu hitta värdet på funktionen med abskissan . Tillfälligt kommer vi att överväga roten på segmentet . Låt punkten ha en abskissa och ligga på grafen. Nu istället för poäng och vi tar punkt och punkt . Nu med dessa två punkter kommer vi att göra samma operation och så vidare, det vill säga vi kommer att få två poäng och och upprepa operationen med dem. Segmentet som förbinder de två sista punkterna skär abskissaxeln vid en punkt vars abskissvärde ungefär kan betraktas som roten. Dessa åtgärder måste upprepas tills vi får rotvärdet med önskad approximation. $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}}$

Algebraisk beskrivning av sekantmetoden

Låt vara abskissan av ändarna av ackordet, vara ekvationen för funktionen löst med sekantmetoden. Hitta koefficienterna och från ekvationssystemet $x_{1},x_{2}$ $f(x)=0$ $k$ $b$

\left\{{\begin{aligned}f(x_{1})&=kx_{1}+b,\\f(x_{2})&=kx_{2}+b.\\\ end{aligned}}\right.

Subtrahera den andra från den första ekvationen:

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

då hittar vi koefficienterna och : $k$ $b$

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

sedan

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

Ekvationen tar formen

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

Så nu kan vi hitta den första approximationen till roten som erhålls med sekantmetoden:

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

Låt oss nu ta koordinaterna och upprepa alla operationer som gjorts och hitta en ny approximation till roten. Således har den iterativa formeln för sekantmetoden formen: $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})}}.

Operationen bör upprepas tills den är mindre än eller lika med det angivna felvärdet. $|x_{i}-x_{i-1}|$

Ackordmetod med iterativ formel

Ibland kallas sekantmetoden metoden med den iterativa formeln

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

Denna metod kan betraktas som en variant av den enkla iterationsmetoden och har en långsammare konvergenshastighet. Vidare, för tydlighetens skull, kommer denna metod att kallas metoden för ackord, och metoden som beskrivs i föregående avsnitt, metoden för sekanter.

Ett exempel på att använda sekantmetoden

Vi löser ekvationen med sekantmetoden. Låt oss ställa in noggrannheten ε=0,001 och ta som initiala approximationer ändarna på segmentet där roten är separerad: och , numeriska värden och väljs godtyckligt. Beräkningarna utförs tills ojämlikheten är uppfylld . $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$

I vårt exempel är värdet ersatt , och värdet ersätts . Värdet kommer att vara det numeriska värdet som erhålls med denna formel. I framtiden byter vi in i formeln i värdet och i värdet . $x_{{i-1}}$ $x_{0}=8$ $x_{i}$ $x_{1}=3$ $x_{{i+1}}$ $x_{2}=\underline {}4.3924051$ $x_{2}=\underline {}4.3924051$ $x_{i}$ $x_{1}=3$ $x_{{i-1}}$

Genom att använda denna formel får vi konsekvent (korrekta signifikanta siffror är understrukna): (bild från metoden för ackord, men inte sekanter, separera avsnitten)

x_{2}=\underline {}4.3924051

; ; ; ; ; ; ; ; ; ;

x_{3}=\underline {5},1622721

x_{4}=\underline {5}.4988422

x_{5}=\underline {5,6}295040

x_{6}=\underline {5.6}777792

x_{7}=\underline {5.6}952826

x_{8}=\underline {5.70}15852

x_{9}=\underline {5.70}38490

x_{{10}}=\underline {5.704}6613

x_{{11}}=\underline {5.704}9528

Låt oss kontrollera att metoden fungerar även om och väljs på samma sida av roten (det vill säga om roten inte är separerad på segmentet mellan de initiala approximationerna). Ta för samma ekvation och . Sedan: (bilden är inte längre från sekantmetoden, utan från dikotomimetoden ) $x_0$ $x_{1}$ $x_{0}=8$ $x_{1}=7$

x_{2}=\underline {}6.1125828

; ; ; ; ; ; ; ;

x_{3}=\underline {5}.8452240

x_{4}=\underline {5.7}546403

x_{5}=\underline {5.7}227874

x_{6}=\underline {5.7}114425

x_{7}=\underline {5.70}73836

x_{8}=\underline {5.705}9290

x_{9}=\underline {5.705}4075

Vi fick samma rotvärde i samma antal iterationer.

Konvergens av sekantmetoden

Iterationer av sekantmetoden konvergerar till roten om de initiala värdena och är tillräckligt nära roten. Sekantmetoden är snabb. Konvergensordningen α är lika med det gyllene snittet : $f(x)$ $x_{0}$ $x_{1}$

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

Således är konvergensordningen större än linjär, men inte kvadratisk, som med den relaterade Newtons metod .

Detta resultat är giltigt om det är dubbelt differentierbart och roten inte är en multipel - . $f(x)$ $\xi$ $f'(\xi )\neq 0$

Som med de flesta snabba metoder är det svårt att formulera konvergensvillkor för sekantmetoden. Om startpunkterna är tillräckligt nära roten så konvergerar metoden, men det finns ingen generell definition av "nära nog". Metodens konvergens bestäms av hur "vågig" funktionen är i . Till exempel, om det finns en punkt i intervallet där , då kanske processen inte konvergerar. $[x_{0},x_{1}]$ $f'(x)=0$

Kriterium och konvergenshastighet för metoden för ackord

Om är en två gånger kontinuerligt differentierbar funktion, och tecknet bevaras på det aktuella intervallet, kommer de erhållna approximationerna att konvergera monotont till roten. Om roten av ekvationen är på intervallet , derivatorna och på detta intervall är kontinuerliga och behåller konstanta tecken och , då kan det bevisas [1] att felet i den ungefärliga lösningen tenderar att nollställas vid , det vill säga metoden konvergerar och konvergerar i takt med en geometrisk progression (i det här fallet säger de att den har en linjär konvergenshastighet ). $f(x)$ $f''(x)$ $\xi$ $f(\xi )=0$ $[a,b]$ $f'(x)$ $f''(x)$ $f''(b)f(b)>0$ $n\högerpil\infty$

Historisk bakgrund

Den första som kunde hitta ungefärliga lösningar på kubiska ekvationer var Diophantus , och därigenom lade grunden för ackordmetoden. De överlevande verken av Diophantus rapporterar detta. Den första som förstod hans metoder var dock Fermat på 1600-talet, och den första som förklarade ackordsmetoden var Newton (1670-talet). [2]

Implementering

C++

#include <iostream> #inkludera <math.h> dubbel f ( dubbel x ) { returnera sqrt ( fabs ( cos ( x ))) - x ; // Ersätt med funktionen vars rötter vi letar efter } // a, b - ackordsgränser, epsilon - obligatoriskt fel double findRoot ( dubbel a , dubbel b , dubbel epsilon ) { while ( 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)-th och i-th medlemmar returnera b ; }

Python

från matte import synd från skrivning import Anropsbar import enhetstest def secant ( f : Callable [[ float ], float ], x0 : float , eps : float = 1e-7 , kmax : int = 1e3 ) -> float : """ löser f(x) = 0 med sekantmetod med precision eps :param f: f :param x0: startpunkt :param eps: precision önskad :return: roten av f(x) = 0 """ x , x_prev , i = x0 , x0 + 2 * eps , 0 medan abs ( x - x_prev ) >= eps och i < kmax : x , x_prev , i = x - f ( x ) / ( f ( x ) - f ( x_prev )) * ( x - x_prev ), x , i + ett tillbaka x klass TestSecant ( unittest . TestCase ): def test_0 ( self ) : def f ( x : float ) -> float : return x ** 2 - 20 * sin ( x ) x0 , x_star = 2 , 2,7529466338187049383 själv . assertAlmostEqual ( secant ( f , x0 ), x_star ) if __name__ == '__main__' : unittest . huvud ()

Ändringar

Den falska positionsmetoden skiljer sig från sekantmetoden endast genom att varje gång inte de sista 2 punkterna tas, utan de punkter som ligger runt roten.

Se även

Litteratur

Demidovich B. P. och Maron I. A. Fundamentals of Computational Mathematics. - Vetenskap, 1970. - S. 664.
Bakhvalov, Zhidkov, Kobelkov. Numeriska metoder. - Vetenskapen. — ISBN 5-94774-060-5 .

Anteckningar

↑ Algebra (otillgänglig länk) . Hämtad 24 november 2009. Arkiverad från originalet 3 december 2007. (obestämd)
↑ Matematik och dess historia. John Stillwell