secans methode - Secant method

De eerste twee iteraties van de secansmethode. De rode curve toont de functie f , en de blauwe lijnen zijn de secans. Voor dit specifieke geval zal de secansmethode niet convergeren naar de zichtbare wortel.

In numerieke analyse is de secansmethode een wortelzoekalgoritme dat een opeenvolging van wortels van secanslijnen gebruikt om een ​​wortel van een functie f beter te benaderen . De secansmethode kan worden gezien als een eindige-verschilbenadering van de methode van Newton . De secansmethode is echter meer dan 3000 jaar ouder dan de methode van Newton.

De methode

De secansmethode wordt gedefinieerd door de herhalingsrelatie

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

Zoals blijkt uit de recursierelatie, vereist de secansmethode twee beginwaarden, x ₀ en x ₁ , die idealiter dicht bij de wortel moeten worden gekozen.

Afleiding van de methode

Beginnend met de beginwaarden x ₀ en x ₁ construeren we een lijn door de punten ( x ₀ , f ( x ₀ )) en ( x ₁ , f ( x ₁ )) , zoals weergegeven in de afbeelding hierboven. In helling-snijvorm is de vergelijking van deze lijn

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

De wortel van deze lineaire functie, dat is de waarde van x zodat y = 0 is

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

We gebruiken dan deze nieuwe waarde van x als x ₂ en herhalen het proces, met x ₁ en x _{2 in} plaats van x ₀ en x ₁ . We gaan door met dit proces, waarbij we oplossen voor x ₃ , x ₄ , enz., totdat we een voldoende hoog niveau van precisie bereiken (een voldoende klein verschil tussen x _n en x _{n −1} ):

${\displaystyle {\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 {uitgelijnd}}}$

Convergentie

De iteraties van de secansmethode convergeren naar een wortel van als de beginwaarden en zijn voldoende dicht bij de wortel. De volgorde van convergentie is φ , waarbij ${\displaystyle x_{n}}$${\displaystyle f}$${\displaystyle x_{0}}$${\displaystyle x_{1}}$

${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\circa 1.618}$

is de gulden snede . In het bijzonder is de convergentie superlineair, maar niet helemaal kwadratisch .

Dit resultaat geldt alleen onder bepaalde technische voorwaarden, namelijk dat twee keer continu differentieerbaar is en dat de betreffende wortel eenvoudig is (dwz met veelvoud 1). ${\displaystyle f}$

Als de beginwaarden niet dicht genoeg bij de wortel liggen, is er geen garantie dat de secansmethode convergeert. Er is geen algemene definitie van "dichtbij genoeg", maar het criterium heeft te maken met hoe "wiggly" de functie op het interval is . Als bijvoorbeeld differentieerbaar is op dat interval en er is een punt waar op het interval, dan kan het algoritme niet convergeren. ${\displaystyle [x_{0},x_{1}]}$${\displaystyle f}$${\displaystyle f'=0}$

Vergelijking met andere methoden om root te vinden

De secansmethode vereist niet dat de wortel tussen haakjes blijft, zoals de bisectiemethode doet, en daarom convergeert deze niet altijd. De valse positiemethode (of regula falsi ) gebruikt dezelfde formule als de secansmethode. Het past echter niet de formule op en toe , zoals de secansmethode, maar op en op de laatste iteratie zodat en een ander teken hebben. Dit betekent dat de valse-positiemethode altijd convergeert; echter alleen met een lineaire volgorde van convergentie. Bracketing met een superlineaire convergentievolgorde als de secansmethode kan worden bereikt met verbeteringen aan de valse positiemethode (zie Regula falsi § Verbeteringen in regula falsi ) zoals de ITP-methode of de Illinois-methode . ${\displaystyle x_{n-1}}$${\displaystyle x_{n-2}}$${\displaystyle x_{n-1}}$${\displaystyle x_{k}}$${\displaystyle f(x_{k})}$${\displaystyle f(x_{n-1})}$

De herhalingsformule van de secansmethode kan worden afgeleid uit de formule voor de methode van Newton

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

met behulp van de eindige-verschil benadering

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

De secansmethode kan worden geïnterpreteerd als een methode waarbij de afgeleide wordt vervangen door een benadering en is dus een quasi-Newtonmethode .

Als we de methode van Newton vergelijken met de secansmethode, zien we dat de methode van Newton sneller convergeert (orde 2 tegen φ  ≈ 1.6). De methode van Newton vereist echter de evaluatie van beide en de afgeleide bij elke stap, terwijl de secansmethode alleen de evaluatie van . Daarom kan de secansmethode in de praktijk soms sneller zijn. Als we bijvoorbeeld aannemen dat evalueren net zoveel tijd kost als het evalueren van de afgeleide en we alle andere kosten verwaarlozen, kunnen we twee stappen van de secansmethode uitvoeren (de logaritme van de fout met een factor φ ²  ≈ 2,6 verlagen ) voor hetzelfde kosten als één stap van de methode van Newton (waardoor de logaritme van de fout met een factor 2 wordt verlaagd), dus de secansmethode is sneller. Als we echter parallelle verwerking overwegen voor de evaluatie van de afgeleide, bewijst de methode van Newton zijn waarde, omdat hij sneller is in de tijd, maar toch meer stappen kost. ${\displaystyle f}$${\displaystyle f'}$${\displaystyle f}$${\displaystyle f}$

generalisaties

De methode van Broyden is een generalisatie van de secansmethode naar meer dan één dimensie.

De volgende grafiek toont de functie f in rood en de laatste secanslijn in vet blauw. In de grafiek lijkt het x- snijpunt van de secanslijn een goede benadering te zijn van de wortel van f .

rekenvoorbeeld

Hieronder wordt de secansmethode geïmplementeerd in de programmeertaal Python .

Het wordt dan toegepast om een ​​wortel te vinden van de functie f ( x ) = x ² − 612 met beginpunten en${\displaystyle x_{0}=10}$${\displaystyle x_{1}=30}$

def secant_method(f, x0, x1, iterations):
    """Return the root calculated using the secant method."""
    for i in range(iterations):
        x2 = x1 - f(x1) * (x1 - x0) / float(f(x1) - f(x0))
        x0, x1 = x1, x2
    return x2

def f_example(x):
    return x ** 2 - 612

root = secant_method(f_example, 10, 30, 5)

print("Root: {}".format(root))  # Root: 24.738633748750722

Opmerkingen:

Zie ook

• Valse positie methode:

Referenties

• Avriel, Mordechai (1976). Niet-lineair programmeren: analyse en methoden . Prentenzaal. blz. 220-221. ISBN 0-13-623603-0.
• Allen, Myron B.; Isaacson, Eli L. (1998). Numerieke analyse voor toegepaste wetenschap . John Wiley & zonen . blz. 188-195. ISBN 978-0-471-55266-6.

Externe links

• Secant Method Notes, PPT, Mathcad, Maple, Mathematica, Matlab bij Holistic Numerical Methods Institute
• Weisstein, Eric W. "Secant-methode" . MathWereld .