Metoda mitei

În matematică și în special în analiza numerică , metoda tangentă , numită și metoda Newton sau metoda Newton-Raphson , este una dintre metodele pentru calculul aproximativ al unei soluții a unei ecuații a formei $f(x)=0$ ${\ displaystyle f (x) = 0}$ $f (x) = 0$ . Se aplică după determinarea unui interval $[a,b]$ ${\ displaystyle [a, b]}$ $[a, b]$ care conține o singură rădăcină .

Exemplu de aplicare a metodei mitei

Metoda constă în înlocuirea curbei $y=f(x)$ ${\ displaystyle y = f (x)}$ $y = f (x)$ tangenta curbei în sine, începând din orice punct; pentru simplitate putem începe de la unul dintre cele două puncte care au ca abscisă extremele intervalului $[a,b]$ ${\ displaystyle [a, b]}$ $[a, b]$ și luați abscisa ca valoare aproximativă a rădăcinii $x_{t}$ ${\ displaystyle x_ {t}}$ $x_ {t}$ a punctului în care tangenta intersectează axa lui $X$ ${\ displaystyle x}$ $X$ intern la interval $[a,b]$ ${\ displaystyle [a, b]}$ $[a, b]$ .

Procedând iterativ, se arată că relația de recurență a metodei este

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}},

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

x _ {{n + 1}} = x_ {n} - {\ frac {f (x_ {n})} {f '(x_ {n})}},

care permite determinarea aproximărilor succesive ale rădăcinii ecuației $y=f(x)=0$ ${\ displaystyle y = f (x) = 0}$ $y = f (x) = 0$ . Cu ipotezele puse, se arată că succesiunea de $x_{n}$ ${\ displaystyle x_ {n}}$ $x_ {n}$ converge la rădăcină destul de repede.

Mai detaliat, demonstrează că dacă $f\in C^{2}(I)$ ${\ displaystyle f \ în C ^ {2} (I)}$ $f \ în C ^ {2} (I)$ unde este $THE$ ${\ displaystyle I}$ $THE$ este un cartier adecvat de zero $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ cu $f'(\alpha )\neq 0$ ${\ displaystyle f '(\ alpha) \ neq 0}$ $f '(\ alfa) \ neq 0$ si daca $x_{0}\in I,$ ${\ displaystyle x_ {0} \ în I,}$ $x_ {0} \ în I,$ asa de

\lim _{n\to +\infty }{\frac {\alpha -x_{n+1}}{(\alpha -x_{n})^{2}}}=-{\frac {f''(\alpha )}{2f'(\alpha )}},

{\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {\ alpha -x_ {n + 1}} {(\ alpha -x_ {n}) ^ {2}}} = - {\ frac { f '' (\ alpha)} {2f '(\ alpha)}},}

\ lim _ {{n \ to + \ infty}} {\ frac {\ alpha -x _ {{n + 1}}} {(\ alpha -x_ {n}) ^ {2}}} = - {\ frac {f '' (\ alpha)} {2f '(\ alpha)}},

adică convergența este pătratică (numărul de cifre semnificative se dublează aproximativ la fiecare iterație; în timp ce cu metoda de bisecție crește liniar), deși local (adică nu se menține pentru fiecare $THE$ ${\ displaystyle I}$ $THE$ ). Dacă, pe de altă parte, rădăcina este multiplă, adică $f'(\alpha )=0$ ${\ displaystyle f '(\ alpha) = 0}$ $f '(\ alfa) = 0$ atunci convergența este liniară (mai lentă). În practică, toleranța de aproximare permisă a fost stabilită $\tau$ ${\ displaystyle \ tau}$ $\ tau$ , procesul iterativ se termină când $\left|x_{n+1}-x_{n}\right|<\tau \cdot |x_{n+1}|.$ ${\ displaystyle \ left | x_ {n + 1} -x_ {n} \ right | <\ tau \ cdot | x_ {n + 1} |.}$ ${\ displaystyle \ left | x_ {n + 1} -x_ {n} \ right | <\ tau \ cdot | x_ {n + 1} |.}$

Problema cu această metodă este că convergența nu este garantată, mai ales atunci când $f'(x)$ ${\ displaystyle f '(x)}$ $f '(x)$ variază considerabil aproape de zero. Mai mult, metoda presupune că $f'(x)$ ${\ displaystyle f '(x)}$ $f '(x)$ este disponibil direct pentru o anumită dată $X$ ${\ displaystyle x}$ $X$ . În cazurile în care acest lucru nu se produce și este necesar să se calculeze derivata printr-o diferență finită, se recomandă utilizarea metodei secante .

Istorie

Matematicianul francez François Viète a prezentat în 1600 ^[1] o metodă, deja cunoscută în 1427 de al-Kashi , pentru căutarea zerourilor unui polinom printr-o perturbare a unei soluții aproximative. Patru ani mai târziu, Newton a aflat de metoda Vietè și în 1669 a descoperit independent o metodă pentru găsirea zerourilor unui polinom.

Ca exemplu, arătați următoarea ecuație $f(x)=x^{3}-2x-5=0$ ${\ displaystyle f (x) = x ^ {3} -2x-5 = 0}$ ${\ displaystyle f (x) = x ^ {3} -2x-5 = 0}$ a cărei soluție are o parte întreagă $x_{0}=2$ ${\ displaystyle x_ {0} = 2}$ ${\ displaystyle x_ {0} = 2}$ . Aplicarea înlocuitorului $x=2+p$ ${\ displaystyle x = 2 + p}$ ${\ displaystyle x = 2 + p}$ se obține polinomul $p^{3}+6p^{2}+10p-1=0$ ${\ displaystyle p ^ {3} + 6p ^ {2} + 10p-1 = 0}$ ${\ displaystyle p ^ {3} + 6p ^ {2} + 10p-1 = 0}$ și neglijând monomiile de grad mai mare decât primul, adică liniarizând polinomul, obținem $p=0{,}1$ ${\ displaystyle p = 0 {,} 1}$ ${\ displaystyle p = 0 {,} 1}$ . Prin care se aplică înlocuirea $p=0{,}1+q$ ${\ displaystyle p = 0 {,} 1 + q}$ ${\ displaystyle p = 0 {,} 1 + q}$ și ajungi la $q^{3}+6{,}3q^{2}+11{,}23q+0{,}061=0$ ${\ displaystyle q ^ {3} +6 {,} 3q ^ {2} +11 {,} 23q + 0 {,} 061 = 0}$ ${\ displaystyle q ^ {3} +6 {,} 3q ^ {2} +11 {,} 23q + 0 {,} 061 = 0}$ și prin liniarizare $q=-0{,}0054$ ${\ displaystyle q = -0 {,} 0054}$ ${\ displaystyle q = -0 {,} 0054}$ . Prin înlocuire $q=0{,}0054+r$ ${\ displaystyle q = 0 {,} 0054 + r}$ ${\ displaystyle q = 0 {,} 0054 + r}$ și făcând același raționament obținem $r=0{,}00004853$ ${\ displaystyle r = 0 {,} 00004853}$ ${\ displaystyle r = 0 {,} 00004853}$ . De la care $x_{3}=x_{0}+p+q+r=2{,}09455147.$ ${\ displaystyle x_ {3} = x_ {0} + p + q + r = 2 {,} 09455147.}$ ${\ displaystyle x_ {3} = x_ {0} + p + q + r = 2 {,} 09455147.}$

Se pot face două observații cu privire la metoda propusă:

$p=x_{1}-x_{0}=-{\frac {f(x_{0})}{f'(x_{0})}}$ ${\ displaystyle p = x_ {1} -x_ {0} = - {\ frac {f (x_ {0})} {f '(x_ {0})}}}$ ${\ displaystyle p = x_ {1} -x_ {0} = - {\ frac {f (x_ {0})} {f '(x_ {0})}}}$ Și $q=x_{2}-x_{1}=-{\frac {f(x_{1})}{f'(x_{1})}}$ ${\ displaystyle q = x_ {2} -x_ {1} = - {\ frac {f (x_ {1})} {f '(x_ {1})}}}$ ${\ displaystyle q = x_ {2} -x_ {1} = - {\ frac {f (x_ {1})} {f '(x_ {1})}}}$ deci metoda găsită de Newton corespunde metodei moderne a tangențelor;
respectând valorile $p$ ${\ displaystyle p}$ $p$ , $q$ ${\ displaystyle q}$ $q$ Și $r$ ${\ displaystyle r}$ $r$ se poate observa că numărul de zerouri după virgulă se dublează la fiecare pas, deci în exemplu există convergență pătratică.

În 1687, Newton a aplicat metoda unei ecuații non-polinomiale pentru prima dată în Philosophiae Naturalis Principia Mathematica . Acesta este cazul ecuației $x-e\sin(x)=M$ ${\ displaystyle xe \ sin (x) = M}$ ${\ displaystyle x-e \ sin (x) = M}$ unde este $M.$ ${\ displaystyle M}$ $M.$ indică anomalia medie e $X$ ${\ displaystyle x}$ $X$ anomalia excentrică. În acest caz, prin aproximarea sinusului ca sumă trunchiată a expansiunii lui Taylor în serie, Newton a obținut un polinom și, prin urmare, a putut aplica metoda pe care a găsit-o.

În 1690 matematicianul Joseph Raphson a reușit să obțină o metodă iterativă pentru actualizarea soluției aproximative $x_{k}$ ${\ displaystyle x_ {k}}$ ${\ displaystyle x_ {k}}$ fără a fi nevoie să calculeze puterea monomială completă și în 1740 Thomas Simpson , în cartea Eseuri despre mai multe subiecte curioase și utile în matematici speculative și mixte, ilustrate de o serie de exemple, a derivat metoda modernă a tangențelor care recunoaște rolul primelor derivate în actualizarea soluției.

Caz unidimensional

Să luăm în considerare o funcție unidimensională $f\in C^{2}[a,b]$ ${\ displaystyle f \ în C ^ {2} [a, b]}$ ${\ displaystyle f \ în C ^ {2} [a, b]}$ și, prin urmare, prin teorema lui Weierstrass, funcția admite un minim $X$ ${\ displaystyle x}$ $X$ a fi determinat.

Deci, ia un punct $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ în interval, profitând de seria Taylor a $f$ ${\ displaystyle f}$ $f$ , constatăm că

f(x)=f(x_{0})+(x-x_{0})f'(x_{0})+{\frac {(x-x_{0})^{2}}{2}}f''(r(x))

{\ displaystyle f (x) = f (x_ {0}) + (x-x_ {0}) f '(x_ {0}) + {\ frac {(x-x_ {0}) ^ {2}} {2}} f '' (r (x))}

{\ displaystyle f (x) = f (x_ {0}) + (x-x_ {0}) f '(x_ {0}) + {\ frac {(x-x_ {0}) ^ {2}} {2}} f '' (r (x))}

cu $r(x)$ ${\ displaystyle r (x)}$ $r (x)$ între $X$ ${\ displaystyle x}$ $X$ Și $x_{0}.$ ${\ displaystyle x_ {0}.}$ ${\ displaystyle x_ {0}.}$

Astfel, dacă $|x-x_{0}|$ ${\ displaystyle | x-x_ {0} |}$ ${\ displaystyle | x-x_ {0} |}$ este suficient de mic, adică $(x-x_{0})^{2}\approx 0$ ${\ displaystyle (x-x_ {0}) ^ {2} \ approx 0}$ ${\ displaystyle (x-x_ {0}) ^ {2} \ approx 0}$ , pozat $f(x)=0$ ${\ displaystyle f (x) = 0}$ $f (x) = 0$ pentru a găsi intersecția liniei tangente la punct $(x_{0},f(x_{0}))$ ${\ displaystyle (x_ {0}, f (x_ {0}))}$ ${\ displaystyle (x_ {0}, f (x_ {0}))}$ cu axa de $X$ ${\ displaystyle x}$ $X$ , se obține $x\approx x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}=x_{1}$ ${\ displaystyle x \ approx x_ {0} - {\ frac {f (x_ {0})} {f '(x_ {0})}} = x_ {1}}$ ${\ displaystyle x \ approx x_ {0} - {\ frac {f (x_ {0})} {f '(x_ {0})}} = x_ {1}}$ . Observați că ultima relație are sens numai dacă $f'(x_{0})$ ${\ displaystyle f '(x_ {0})}$ $f '(x_0)$ nu este nul. Odată găsit $x_{1}$ ${\ displaystyle x_ {1}}$ $x_ {1}$ procedura se repetă. S-a găsit următorul algoritm:

 Metoda unică a lui Newton
* Pasul 0 : alegeți un punct $x_{0}$  $X$   $0$   ${\ displaystyle x_ {0}}$   $x_0$  în interval $[a,b]$  $[$   $la$   $,$   $b$   $]$   ${\ displaystyle [a, b]}$   $[a, b]$  . Se ridică $k=0.$  $k$   $=$   $0.$   ${\ displaystyle k = 0.}$   ${\ displaystyle k = 0.}$ 
 Pentru $k=0,1,\ldots$  $k$   $=$   $0$   $,$   $1$   $,$   $...$   ${\ displaystyle k = 0,1, \ ldots}$   ${\ displaystyle k = 0,1, \ ldots}$  
* Pasul 1 : Este determinat  $x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}$  $X$   $k$   $+$   $1$   $=$   $X$   $k$   $-$   $f$   $($   $X$   $k$   $)$   $f$   $'$   $($   $X$   $k$   $)$   ${\ displaystyle x_ {k + 1} = x_ {k} - {\ frac {f (x_ {k})} {f '(x_ {k})}}}$   ${\ displaystyle x_ {k + 1} = x_ {k} - {\ frac {f (x_ {k})} {f '(x_ {k})}}}$  . 
* Pasul 2 : Poni $k=k+1$  $k$   $=$   $k$   $+$   $1$   ${\ displaystyle k = k + 1}$   ${\ displaystyle k = k + 1}$  și reveniți la Pasul 1.

După cum am văzut, o condiție necesară pentru ca metoda să fie aplicabilă este aceea că există un interval $I=[a,b]$ ${\ displaystyle I = [a, b]}$ $I = [a, b]$ in care $x_{0}\in I$ ${\ displaystyle x_ {0} \ în I}$ $x_ {0} \ în I$ este astfel încât $f'(x_{0})\neq 0$ ${\ displaystyle f '(x_ {0}) \ neq 0}$ ${\ displaystyle f '(x_ {0}) \ neq 0}$ Și $f''(x_{0})\neq 0$ ${\ displaystyle f '' (x_ {0}) \ neq 0}$ ${\ displaystyle f '' (x_ {0}) \ neq 0}$ . Prin teorema zero acest interval există dacă și numai dacă $f'(x_{0})\neq 0$ ${\ displaystyle f '(x_ {0}) \ neq 0}$ ${\ displaystyle f '(x_ {0}) \ neq 0}$ Și $f''(x_{0})\neq 0$ ${\ displaystyle f '' (x_ {0}) \ neq 0}$ ${\ displaystyle f '' (x_ {0}) \ neq 0}$ .

Caz multidimensional

Să luăm în considerare o funcție $f\in C^{2}(\mathbb {R} ^{n})$ ${\ displaystyle f \ în C ^ {2} (\ mathbb {R} ^ {n})}$ ${\ displaystyle f \ în C ^ {2} (\ mathbb {R} ^ {n})}$ și fie $x\in \mathbb {R} ^{n}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$ zero care urmează să fie determinat. Prin exploatarea dezvoltării seriei lui Taylor, avem un vector generic $h\in \mathbb {R} ^{n}$ ${\ displaystyle h \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle h \ in \ mathbb {R} ^ {n}}$ :

f(x+h)=f(x)+J(x)h+O(\|h\|^{2})

{\ displaystyle f (x + h) = f (x) + J (x) h + O (\ | h \ | ^ {2})}

{\ displaystyle f (x + h) = f (x) + J (x) h + O (\ | h \ | ^ {2})}

unde este $J(x)$ ${\ displaystyle J (x)}$ $J (x)$ indică matricea iacobiană a $f$ ${\ displaystyle f}$ $f$ calculat la punct $X$ ${\ displaystyle x}$ $X$ .

Astfel, dacă $J(x)$ ${\ displaystyle J (x)}$ $J (x)$ nu este singular să obții un punct nou $y=x+h_{1}$ ${\ displaystyle y = x + h_ {1}}$ ${\ displaystyle y = x + h_ {1}}$ unde este $h_{1}$ ${\ displaystyle h_ {1}}$ ${\ displaystyle h_ {1}}$ este soluția sistemului liniar $J(x)h=-f(x)$ ${\ displaystyle J (x) h = -f (x)}$ ${\ displaystyle J (x) h = -f (x)}$ .

S-a găsit următorul algoritm:

 Metoda multidimensională a lui Newton
* Pasul 0 : alegeți un punct $x_{0}$  $X$   $0$   ${\ displaystyle x_ {0}}$   $x_0$  . Se ridică $k=0$  $k$   $=$   $0$   ${\ displaystyle k = 0}$   ${\ displaystyle k = 0}$  .
 Pentru $k=0,1,...$  $k$   $=$   $0$   $,$   $1$   $,$   $.$   $.$   $.$   ${\ displaystyle k = 0,1, ...}$   ${\ displaystyle k = 0,1, ...}$  
* Pasul 1 : funcționează $J(x_{k})h=-f(x_{k})$  $J$   $($   $X$   $k$   $)$   $h$   $=$   $-$   $f$   $($   $X$   $k$   $)$   ${\ displaystyle J (x_ {k}) h = -f (x_ {k})}$   ${\ displaystyle J (x_ {k}) h = -f (x_ {k})}$  obținerea vectorului $h$  $h$   ${\ displaystyle h}$   $h$  . 
* Pasul 2 : Este determinat $x_{k+1}=x_{k}+h$  $X$   $k$   $+$   $1$   $=$   $X$   $k$   $+$   $h$   ${\ displaystyle x_ {k + 1} = x_ {k} + h}$   ${\ displaystyle x_ {k + 1} = x_ {k} + h}$  .
* Pasul 3 : apare $k=k+1$  $k$   $=$   $k$   $+$   $1$   ${\ displaystyle k = k + 1}$   ${\ displaystyle k = k + 1}$  și reveniți la Pasul 1.

$f\in C^{2}(I)$ ${\ displaystyle f \ în C ^ {2} (I)}$ $f \ în C ^ {2} (I)$ unde este $THE$ ${\ displaystyle I}$ $THE$ este un cartier adecvat al rădăcinii $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ cu $f'(\alpha )\neq 0$ ${\ displaystyle f '(\ alpha) \ neq 0}$ $f '(\ alfa) \ neq 0$ si daca $x_{0}\in I,$ ${\ displaystyle x_ {0} \ în I,}$ $x_ {0} \ în I,$