Metoda sieczna

Pierwsze dwie iteracje metody siecznej. Czerwona krzywa przedstawia funkcję f , a niebieskie linie to sieczne. W tym konkretnym przypadku metoda siecznej nie będzie zbieżna do widocznego pierwiastka.

W analizie numerycznej metoda siecznych jest algorytmem znajdowania pierwiastków , który wykorzystuje kolejne pierwiastki siecznych linii , aby lepiej przybliżyć pierwiastek funkcji f . Metodę sieczną można traktować jako przybliżenie metody Newtona metodą różnic skończonych . Jednak metoda sieczna jest starsza niż metoda Newtona o ponad 3000 lat.

Metoda

Aby znaleźć zero funkcji f , metoda siecznych jest zdefiniowana przez relację powtarzalności .

${\ 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})}}.}$

Jak widać z tego wzoru, wymagane są dwie wartości początkowe x ₀ i x _{1 .} Idealnie powinny być wybrane blisko pożądanego zera.

Wyprowadzenie metody

Zaczynając od wartości początkowych x ₀ i x ₁ , konstruujemy prostą przechodzącą przez punkty ₀₀ ( x , f ( x )) i ( x ₁ , f ( x ₁ )) , jak pokazano na powyższym rysunku. W postaci nachylenia i punktu przecięcia równanie tej linii ma postać

${\ Displaystyle y = {\ Frac {f (x_ {1}) -f (x_ {0})} {x_ {1} -x_ {0}}} (xx_ {1}) + f (x_ { 1}).}$

Pierwiastek tej funkcji liniowej, czyli wartość x taka, że ​​y = 0 wynosi

${\ Displaystyle x = x_ {1} -f (x_ {1}) {\ Frac {x_ {1} -x_ {0}} {f (x_ {1}) -f (x_ {0})}}. }$

Następnie używamy tej nowej wartości x jako x ₂ i powtarzamy proces, używając x ₁ i x ₂ zamiast x ₀ i x ₁ . Kontynuujemy ten proces, rozwiązując dla x ₃ , x ₄ itd., aż osiągniemy wystarczająco wysoki poziom precyzji (wystarczająco mała różnica między x _n i x _{n −1} ):

${\ Displaystyle {\ rozpocząć {wyrównane} 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 {wyrównany}}}$

Konwergencja

Iteracje metody siecznych zbiegają się do pierwiastka z , jeśli wartości początkowe $x_ {0}}$$\$$displaystyle$ i $\ displaystyle x_ {1} }$ są wystarczająco blisko korzenia. Kolejność zbieżności to , gdzie ${\ displaystyle \ varphi}$

${\ Displaystyle \ varphi = {\ Frac {1 + {\ sqrt {5}}} {2}} \ około 1,618}$

jest złoty podział . W szczególności zbieżność jest superliniowa, ale nie całkiem kwadratowa .

Wynik ten obowiązuje tylko pod pewnymi warunkami technicznymi, a mianowicie, aby był dwukrotnie różniczkowalny w sposób ciągły, a pierwiastek, o którym mowa, był prosty (tj. Z krotnością 1 $)$

Jeśli wartości początkowe nie są wystarczająco bliskie pierwiastkowi, nie ma gwarancji, że metoda sieczna jest zbieżna. Nie ma ogólnej definicji „wystarczająco blisko”, ale kryterium dotyczy tego, jak „falująca” jest funkcja w przedziale. ${\ Displaystyle [x_ {0}, x_ {1}]}$ . Na przykład, jeśli $zbieżny$$różniczkowalna w$ przedziale i istnieje punkt, w którym przedziale, to algorytm może nie być

Porównanie z innymi metodami wyszukiwania korzeni

Metoda siecznych nie wymaga, aby pierwiastek pozostawał w nawiasach, tak jak robi to metoda bisekcji , a zatem nie zawsze jest zbieżny. Metoda fałszywej pozycji (lub regula falsi ) wykorzystuje ten sam wzór, co metoda siecznych. $Jednak$ nie stosuje ${\ displaystyle x_ {n-1}}$$podobnie$ jak na i na ostatniej iteracji tak, że $Displaystyle f (x_ {k})}$$\$$\ Displaystyle f (x_ {n- 1})}$ mają inny znak. Oznacza to, że metoda fałszywej pozycji zawsze jest zbieżna; jednak tylko z liniowym rzędem zbieżności. Bracketing z superliniowym rzędem zbieżności jako metodą sieczną można osiągnąć dzięki ulepszeniom metody fałszywej pozycji (zob. Regula falsi § Ulepszenia w regula falsi ), takie jak metoda ITP lub metoda Illinois .

Wzór na powtarzalność metody siecznej można wyprowadzić ze wzoru na metodę Newtona

${\ Displaystyle x_ {n} = x_ {n-1} - {\ Frac {f (x_ {n-1} )}{f'(x_{n-1})}}}$

stosując przybliżenie różnic skończonych , dla małego: ${\ displaystyle \ epsilon}$ :

${\ Displaystyle f '(x_ {n-1}) \ około {\ Frac {f (x_ {n-1}) -f (x_ {n-2})} {x_ {n-1} - x_ {n-2}}}\około {\frac {f(x_{n-1}+{\frac {\epsilon}{2}})-f(x_{n-1}-{\frac {\ epsilon }{2}})}{\epsilon }}}$

Metodę siecznych można interpretować jako metodę, w której pochodna jest zastępowana przybliżeniem, a zatem jest metodą quasi-Newtona .

Jeśli porównamy metodę Newtona z metodą sieczną, to zobaczymy, że metoda Newtona jest zbieżna szybciej (rząd 2 wobec φ ≈ 1,6). Jednak metoda Newtona wymaga oceny zarówno jej $,$ jak i jej pochodnej $displaystyle$ metoda siecznych wymaga jedynie oceny $f}$ . Dlatego metoda siecznej może czasami być szybsza w praktyce. Na przykład, jeśli założymy, że ocena ${\ displaystyle f}$ zajmuje tyle samo czasu, co obliczenie jego pochodnej i pomijamy wszystkie inne koszty, możemy wykonać dwa kroki metody siecznej (zmniejszając logarytm błędu o współczynnik φ 2 ≈ 2,6 ) ^za ten sam koszt, co jeden krok metody Newtona ( zmniejszając logarytm błędu o współczynnik 2), więc metoda siecznej jest szybsza. Jeśli jednak weźmiemy pod uwagę przetwarzanie równoległe do wyznaczania pochodnej, metoda Newtona sprawdza się, ponieważ jest szybsza w czasie, choć wciąż wymaga większej liczby kroków.

Uogólnienie

Metoda Broydena jest uogólnieniem metody siecznej na więcej niż jeden wymiar.

Poniższy wykres przedstawia funkcję f na czerwono, a ostatnią sieczną pogrubioną na niebiesko. Na wykresie sieczną wydaje się być dobrym przybliżeniem pierwiastka z f .

Przykład obliczeniowy

Poniżej przedstawiono metodę sieczną zaimplementowaną w języku programowania Python .

Następnie stosuje się go do znalezienia pierwiastka funkcji fa ( x ) = x ² - 612 z początkowymi punktami i ${\ Displaystyle x_ {0} = 10}$ i ${\ Displaystyle x_ {1} = 30 }$

    
    
       
                     def  secant_method  (  f  ,  x0  ,  x1  ,  iteracje  ):  """Zwróć pierwiastek obliczony metodą siecznych."""  dla  i  w  zakresie  (  iteracje  ):  x2  =  x1  -  f  (  x1  )  *  (  x1  -  x0  )  /  pływak  (  fa  (  x1  )  -  fa  ( 
            
        
     

 
         

     

 x0  ))  x0  ,  x1  =  x1  ,  x2  # Zastosuj tutaj kryterium zatrzymania (patrz poniżej)  return  x2  def  f_example  (  x  ):  return  x  **  2  -  612  root  =  secant_method  (  f_example  ,  10  ,  30  ,  5  )  print  (  f  "Root:  {  root  }  "  )    # Korzeń: 24.738633748750722 

Bardzo ważne jest, aby mieć dobre kryterium zatrzymania powyżej, w przeciwnym razie, ze względu na ograniczoną precyzję numeryczną liczb zmiennoprzecinkowych, algorytm może zwracać niedokładne wyniki, jeśli działa przez zbyt wiele iteracji. Na przykład powyższa pętla może się zatrzymać, gdy jedno z poniższych zostanie osiągnięte jako pierwsze: abs(x0 - x1) < tol lub abs(x0-x1)/abs(x1) < tol lub abs(f(x1)) < tol .

Zobacz też

• Metoda fałszywych pozycji

•   Avriel, Mordechaj (1976). Programowanie nieliniowe: analiza i metody . Sala Prentice'a. s. 220–221. ISBN 0-13-623603-0 .
•   Allen, Myron B.; Isaacson, Eli L. (1998). Analiza numeryczna dla nauk stosowanych . John Wiley & Synowie . s. 188–195. ISBN 978-0-471-55266-6 .

Linki zewnętrzne

• Secant Method Notes, PPT, Mathcad, Maple, Mathematica, Matlab w Holistic Numerical Methods Institute
• Weisstein, Eric W. „Metoda sieczna” . MathWorld .