Wszyscy ludzie z natury dążą do wiedzy. (Arystoteles. Metafizyka)

Metody numeryczne: rozwiązywanie równań nieliniowych

Problemy z rozwiązywaniem równań stale pojawiają się w praktyce, np. w ekonomii, rozwijając biznes, chcesz wiedzieć, kiedy zyski osiągną określoną wartość, w medycynie, badając działanie leków, ważne jest, aby wiedzieć, kiedy stężenie substancja osiągnie określony poziom itp.

W zadaniach optymalizacyjnych często konieczne jest określenie punktów, w których pochodna funkcji osiąga wartość 0, co jest warunkiem koniecznym lokalny ekstremum.

W statystyce konstruując szacunki metodą najmniejszych kwadratów lub największej wiarygodności, trzeba także rozwiązywać równania nieliniowe i układy równań.

Powstaje więc cała klasa problemów związanych ze znalezieniem rozwiązań nieliniowy równania, takie jak równania lub równania itp.

W najprostszym przypadku mamy funkcję zdefiniowaną na przedziale ( A, b) i przyjmowanie określonych wartości.

Każda wartość X z tego segmentu możemy porównać liczbę, tj funkcjonalny zależność, kluczowe pojęcie w matematyce.

Musimy znaleźć wartość, przy której nazywane są one pierwiastkami funkcji

Wizualnie musimy wyznaczyć punkt przecięcia wykresu funkcjiz osią odciętej.

Metoda halvingu

Najprostszą metodą znajdowania pierwiastków równania jest metoda dzielenia na połowę lub dychotomia.

Metoda ta jest intuicyjna i każdy postąpiłby w podobny sposób przy rozwiązywaniu problemu.

Algorytm jest następujący.

Załóżmy, że znajdziemy dwa punkty i , takie, że mają różny znaków, to między tymi punktami znajduje się co najmniej jeden pierwiastek funkcji.

Podzielmy segment na pół i wejdźmy przeciętny punkt .

Wtedy albo , Lub .

Zostawmy tę połowę segmentu, dla której wartości na końcach mają różne znaki. Teraz dzielimy ten odcinek ponownie na pół i zostawiamy tę część na granicach, której funkcja ma różne znaki itd., aby osiągnąć wymaganą dokładność.

Oczywiście będziemy stopniowo zawężać obszar, w którym znajduje się pierwiastek funkcji, dlatego wyznaczymy go z pewną dokładnością.

Należy zauważyć, że opisany algorytm ma zastosowanie dla dowolnej funkcji ciągłej.

Zaletami metody halvingu są jej wysoka niezawodność i prostota.

Wadą tej metody jest to, że zanim zaczniesz z niej korzystać, musisz znaleźć dwa punkty, w których wartości funkcji mają różne znaki. Jest oczywiste, że metody tej nie można zastosować do pierwiastków o parzystej wielokrotności, a także nie można jej uogólniać na przypadek pierwiastków zespolonych i na układy równań.

Kolejność zbieżności metody jest liniowa, na każdym kroku dokładność podwaja się, im więcej iteracji zostanie wykonanych, tym dokładniej zostanie wyznaczony pierwiastek.

Metoda Newtona: podstawy teoretyczne

Klasyczna metoda Newtona Lub styczne jest to, że jeśli jest pewnym przybliżeniem pierwiastka równania , to kolejne przybliżenie definiuje się jako pierwiastek stycznej do funkcji narysowanej w punkcie .

Równanie styczne do funkcji w punkcie ma postać:

W równaniu stycznym umieszczamy i .

Wówczas algorytm obliczeń sekwencyjnych w metodzie Newtona wygląda następująco:

Zbieżność metody stycznej jest kwadratowa, rząd zbieżności wynosi 2.

Zatem zbieżność metody stycznej Newtona jest bardzo szybka.

Zapamiętaj ten wspaniały fakt!

Bez żadnych zmian metodę uogólnia się na przypadek złożony.

Jeśli pierwiastek jest pierwiastkiem drugiej wielokrotności lub wyższej, wówczas rząd zbieżności maleje i staje się liniowy.

Ćwiczenie 1. Metodą styczną znajdź rozwiązanie równania na odcinku (0, 2).

Ćwiczenie 2. Metodą styczną znajdź rozwiązanie równania na odcinku (1, 3).

Wadą metody Newtona jest jej lokalność, ponieważ gwarantuje ona zbieżność dla dowolnego przybliżenia początkowego tylko wtedy, gdy warunek jest spełniony wszędzie , w sytuacji odwrotnej zbieżność zachodzi tylko w pewnym sąsiedztwie pierwiastka.

Wadą metody Newtona jest konieczność obliczania pochodnych na każdym kroku.

Wizualizacja metody Newtona

Do równania stosowana jest metoda Newtona (metoda styczna). F(X) = 0 ma pierwiastek i spełnione są następujące warunki:

1) funkcja y= F(X) zdefiniowane i ciągłe w ;

2) F(A)· F(B) < 0 (funkcja przyjmuje wartości różnych znaków na końcach odcinka [ A; B]);

3) instrumenty pochodne F"(X) I F""(X) zachowaj znak na przedziale [ A; B] (tj. funkcja F(X) albo wzrasta, albo maleje w segmencie [ A; B], zachowując kierunek wypukłości);

Główna idea metody jest następująca: na segmencie [ A; B] taki numer został wybrany X 0 , w którym F(X 0 ) ma ten sam znak co F"" (X 0 ), czyli warunek jest spełniony F(X 0 )· F"" (X) > 0 . W ten sposób wybierany jest punkt z odciętą X 0 , w którym styczna do krzywej y= F(X) w segmencie [ A; B] przecina oś Wół. Za punkt X 0 Po pierwsze, wygodnie jest wybrać jeden z końców segmentu.

Rozważmy metodę Newtona na konkretnym przykładzie.

Przyjmijmy funkcję rosnącą y = f(x) =x 2 -2, ciągły w segmencie (0;2) i posiadający F"(x) = 2 X > 0 I F "" (x) = 2 > 0 .

Rysunek1 . f(x) =x 2 -2

Równanie styczne w postaci ogólnej ma następującą reprezentację:

y-y 0 = f" (x 0)·(x-x 0).

W naszym przypadku: y-y 0 =2x 0 ·(x-x 0). Dla punktu x 0 wybieramy punkt B 1 (b; f(b)) = (2,2). Narysuj styczną do funkcji y = f(x) w punkcie B 1 i oznacz punkt przecięcia stycznej i osi Wół kropka x 1. Otrzymujemy równanie pierwszej stycznej: y-2=2·2(x-2), y=4x-6.

Wół: x 1 =

Rysunek2. Wynik pierwszej iteracji

y=f(x) Wół przez punkt x 1, rozumiemy o co chodzi B2 =(1,5; 0,25). Narysuj ponownie styczną do funkcji y = f(x) w punkcie B 2 i oznacz punkt przecięcia stycznej i osi Wół kropka x 2.

Równanie drugiej stycznej: y-0.25=2*1.5(X-1.5), y = 3 X - 4.25.

Punkt przecięcia stycznej i osi Wół: x 2 =.

Rysunek3. Druga iteracja metody Newtona

Następnie znajdujemy punkt przecięcia funkcji y=f(x) i prostopadłą poprowadzoną do osi Wół przez punkt x 2 otrzymamy punkt B 3 i tak dalej.

Rysunek4. Trzeci krok metody stycznej

Pierwsze przybliżenie pierwiastka określa wzór:

= 1.5.

Drugie przybliżenie pierwiastka określa wzór:

Trzecie przybliżenie pierwiastka określa wzór:

Zatem , I Przybliżenie pierwiastka określa się ze wzoru:

Obliczenia przeprowadza się do momentu uzyskania miejsc po przecinku potrzebnych do dopasowania odpowiedzi lub osiągnięcia określonej precyzji e – do momentu spełnienia nierówności | xi- xi-1 | < mi.

W naszym przypadku porównajmy przybliżenie uzyskane w kroku trzecim z rzeczywistą odpowiedzią obliczoną na kalkulatorze:

Rysunek 5. Pierwiastek z 2 obliczony na kalkulatorze

Jak widać już w trzecim kroku otrzymaliśmy błąd mniejszy niż 0,000002.

W ten sposób można obliczyć wartość „pierwiastka kwadratowego z 2” z dowolną dokładnością. Ta niezwykła metoda została wynaleziona przez Newtona i pozwala bardzo łatwo znaleźć korzenie złożone równania.

Metoda Newtona: zastosowanie w C++

W tym artykule zautomatyzujemy proces obliczania pierwiastków równań pisząc aplikację konsolową w C++. Będziemy go rozwijać w Visual C++ 2010 Express, jest to darmowe i bardzo wygodne środowisko programistyczne C++.

Najpierw uruchommy Visual C++ 2010 Express. Pojawi się okno startu programu. W lewym rogu kliknij „Utwórz projekt”.

Ryż. 1. strona główna Visual C++ 2010 Express

W wyświetlonym menu wybierz „Win32 Console Application” i wpisz nazwę aplikacji „Newton_Method”.

Ryż. 2. Utwórz projekt

// Metoda Newton.cpp: definiuje punkt wejścia dla aplikacji konsolowej

#include „stdafx.h”

#włączać

używając przestrzeni nazw std;

float f(double x) //zwraca wartość funkcji f(x) = x^2-2

float df(float x) //zwraca wartość pochodnej

float d2f(float x) // wartość drugiej pochodnej

int _tmain(int argc, _TCHAR* argv)

int wyjście = 0, i=0;//zmienne dla wyjścia i pętli

double x0,xn;//obliczone przybliżenia pierwiastka

double a, b, eps; // granice segmentu i wymagana dokładność

cout<<"Please input \n=>";

cin>>a>>b; // podaj granice segmentu, na którym będziemy szukać pierwiastka

cout<<"\nPlease input epsilon\n=>";

cin>>eps; // wprowadź wymaganą dokładność obliczeń

if (a > b) // jeśli użytkownik pomylił granice segmentu, zamień je

if (f(a)*f(b)>0) // jeśli znaki funkcji na krawędziach odcinka są takie same, to nie ma tu pierwiastka

cout<<"\nError! No roots in this interval\n";

jeśli (f(a)*d2f(a)>0) x0 = a; // aby wybrać punkt początkowy, sprawdź f(x0)*d2f(x0)>0 ?

xn = x0-f(x0)/df(x0); // rozważ pierwsze przybliżenie

cout<<++i<<"-th iteration = "<

while(fabs(x0-xn) > eps) // będziemy kontynuować obliczenia, aż osiągniemy wymaganą dokładność

xn = x0-f(x0)/df(x0); // bezpośrednio wzór Newtona

cout<<++i<<"-th iteration = "<

cout<<"\nRoot = "<

cout<<"\nExit?=>";

) podczas (wyjście!=1); // dopóki użytkownik nie wpisze exit = 1

Zobaczmy jak to działa. Kliknij zielony trójkąt w lewym górnym rogu ekranu lub naciśnij klawisz F5.

Jeśli pojawi się błąd kompilacji „Błąd błędu LNK1123: błąd konwersji do COFF: plik jest nieprawidłowy lub uszkodzony”, można go naprawić instalując pierwszy dodatek Service Pack 1 lub w ustawieniach projektu Właściwości -> Linker wyłączając łączenie przyrostowe.

Ryż. 4. Rozwiązanie błędu kompilacji projektu

Będziemy szukać pierwiastków funkcji F(x) =x2-2.

Najpierw sprawdźmy wydajność aplikacji na „złych” danych wejściowych. W segmencie nie ma korzeni, nasz program powinien wyświetlić komunikat o błędzie.

Mamy teraz okno aplikacji:

Ryż. 5. Wprowadzanie danych wejściowych

Wprowadźmy granice odcinka 3 i 5, a dokładność wynosi 0,05. Program, zgodnie z oczekiwaniami, wygenerował komunikat o błędzie informujący, że w tym segmencie nie ma korzeni.

Ryż. 6. Błąd „W tym segmencie nie ma korzeni!”

Nie zamierzamy jeszcze wychodzić, więc co z komunikatem „Wyjdź?” wpisz „0”.

Sprawdźmy teraz aplikację korzystając z poprawnych danych wejściowych. Wprowadźmy segment i dokładność 0,0001.

Ryż. 7. Obliczanie pierwiastka z wymaganą dokładnością

Jak widać wymaganą dokładność uzyskano już w czwartej iteracji.

Aby wyjść z aplikacji, wpisz „Wyjdź?” => 1.

Metoda sieczna

Aby uniknąć obliczania pochodnej, metodę Newtona można uprościć, zastępując pochodną przybliżeniem obliczonym z dwóch poprzednich punktów:

Proces iteracyjny wygląda następująco:

Jest to dwuetapowy proces iteracyjny, ponieważ wykorzystuje dwa poprzednie do znalezienia następnego przybliżenia.

Rząd zbieżności metody siecznej jest niższy niż metody stycznej i jest równy w przypadku pojedynczego pierwiastka.

Ta niezwykła wielkość nazywana jest złotym podziałem:

Zweryfikujmy to, zakładając dla wygody, że .

Zatem aż do nieskończoności wyższego rzędu

Pomijając resztę członu, otrzymujemy relację rekurencji, której rozwiązania naturalnie szukamy w postaci .

Po podstawieniu mamy: i

Dlatego dla zbieżności konieczne jest, aby była dodatnia.

Ponieważ nie jest wymagana znajomość pochodnej, przy tej samej liczbie obliczeń w metodzie siecznej (mimo niższego rzędu zbieżności) można uzyskać większą dokładność niż w metodzie stycznej.

Pamiętaj, że w pobliżu pierwiastka musisz podzielić przez małą liczbę, a to prowadzi do utraty dokładności (szczególnie w przypadku pierwiastków wielokrotnych), dlatego wybierając stosunkowo małą liczbę, wykonaj obliczenia przed wykonaniem i kontynuuj je, aż moduł różnicy między sąsiednimi przybliżeniami zmniejszy się.

Gdy tylko rozpocznie się wzrost, obliczenia zostaną zatrzymane i ostatnia iteracja nie zostanie wykorzystana.

Ta procedura służąca do określenia końca iteracji nazywana jest techniką Garvika.

Metoda paraboli

Rozważmy metodę trójetapową, w której przybliżenie jest określane przez trzy poprzednie punkty , i .

W tym celu zastępujemy, podobnie jak w metodzie siecznej, funkcję parabolą interpolacyjną przechodzącą przez punkty , i .

W postaci Newtona wygląda to następująco:

Punkt definiuje się jako jeden z pierwiastków tego wielomianu, który jest bliżej tego punktu w wartości bezwzględnej.

Rząd zbieżności metody paraboli jest wyższy niż w przypadku metody siecznych, ale niższy niż w przypadku metody Newtona.

Istotną różnicą w stosunku do wcześniej rozważanych metod jest fakt, że nawet jeśli rzeczywista jest rzeczywista i początkowe przybliżenia zostaną wybrane jako rzeczywiste, metoda paraboli może prowadzić do złożonego pierwiastka pierwotnego problemu.

Metoda ta jest bardzo wygodna do znajdowania pierwiastków wielomianów wysokiego stopnia.

Prosta metoda iteracyjna

Problem znalezienia rozwiązań równań można sformułować jako problem znalezienia pierwiastków: , lub jako problem znalezienia punktu stałego.

Pozwalać oraz - kompresja: (w szczególności fakt, że - kompresja, jak łatwo zauważyć, oznacza to).

Zgodnie z twierdzeniem Banacha istnieje unikalny punkt stały

Można go znaleźć jako granicę prostej procedury iteracyjnej

gdzie początkowym przybliżeniem jest dowolny punkt w przedziale.

Jeśli funkcja jest różniczkowalna, wygodnym kryterium kompresji jest liczba . Rzeczywiście, zgodnie z twierdzeniem Lagrange’a

Zatem, jeśli pochodna jest mniejsza niż jeden, to jest to kompresja.

Stan jest istotne, bo jeśli np. na , to nie ma punktu stałego, chociaż pochodna jest równa zeru. Szybkość zbieżności zależy od wartości . Im mniejsze, tym szybsza zbieżność.

Niech pierwiastek równania f(x)=0 zostanie rozdzielony na odcinku , z pierwszą i drugą pochodną f’(x) oraz f""(x) są ciągłe i mają stały znak dla xÎ.

Niech na pewnym etapie doprecyzowania pierwiastka otrzymane zostanie kolejne przybliżenie pierwiastka x n (wybrane) . Następnie załóżmy, że kolejne przybliżenie uzyskane przy użyciu poprawki h n , prowadzi do dokładnej wartości pierwiastka

x = xn + hn. (1.2.3-6)

Rachunkowość h n małą wartość, f(х n + h n) przedstawiamy w postaci szeregu Taylora, ograniczając się do wyrazów liniowych

f(x n + h n) »f(x n) + h n f’(x n). (1.2.3-7)

Biorąc pod uwagę, że f(x) = f(x n + h n) = 0, otrzymujemy f(x n) + h n f ’(x n) » 0.

Stąd h n » - f(x n)/ f’(x n). Zastąpmy tę wartość h n w (1.2.3-6) i zamiast dokładnej wartości pierwiastka X otrzymujemy kolejne przybliżenie

Wzór (1.2.3-8) pozwala nam uzyskać ciąg przybliżeń x 1, x 2, x 3 ..., który pod pewnymi warunkami zbiega się do dokładnej wartości pierwiastka X, to jest

Interpretacja geometryczna metody Newtona następująco
(Rys. 1.2.3-6). Przyjmijmy prawy koniec odcinka b jako początkowe przybliżenie x 0 i skonstruujmy styczną w odpowiednim punkcie B 0 na wykresie funkcji y = f(x). Punkt przecięcia stycznej z osią x przyjmuje się jako nowe, dokładniejsze przybliżenie x 1. Wielokrotne powtarzanie tej procedury pozwala uzyskać ciąg przybliżeń x 0, x 1, x 2 , . . ., co ma tendencję do dokładnej wartości pierwiastka X.

Wzór obliczeniowy metody Newtona (1.2.3-8) można wyprowadzić z konstrukcji geometrycznej. Zatem w trójkącie prostokątnym x 0 B 0 x 1 noga
x 0 x 1 = x 0 V 0 /tga. Biorąc pod uwagę, że punkt B 0 znajduje się na wykresie funkcji f(x), a przeciwprostokątną tworzy styczna do wykresu f(x) w punkcie B 0, otrzymujemy

(1.2.3-9)

(1.2.3-10)

Wzór ten pokrywa się z (1.2.3-8) dla n-tego przybliżenia.

Z rys. 1.2.3-6 jasno wynika, że wybranie punktu a jako przybliżenia początkowego może prowadzić do tego, że kolejne przybliżenie x 1 będzie znajdować się poza odcinkiem, na którym rozdzielony jest pierwiastek X. W takim przypadku zbieżność procesu nie jest gwarantowana. W ogólnym przypadku wyboru przybliżenia początkowego dokonuje się zgodnie z następującą zasadą: za przybliżenie początkowe należy przyjąć punkt x 0 О, w którym f(x 0)×f''(x 0)>0 , czyli znaki funkcji i jej drugiej pochodnej pasują do siebie.

Warunki zbieżności metody Newtona formułuje następujące twierdzenie.

Jeśli pierwiastek równania zostanie rozdzielony na segmencie, I f’(x 0) i f’’(x) są różne od zera i zachowują swoje znaki, gdy xО, to jeśli wybierzemy taki punkt jako przybliżenie początkowe x 0 O , Co f(x 0).f¢¢(x 0)>0 , a następnie pierwiastek równania f(x)=0 można obliczyć z dowolną dokładnością.

Oszacowanie błędu metody Newtona określa się za pomocą następującego wyrażenia:

(1.2.3-11)

gdzie jest najmniejsza wartość Na

Najwyższa wartość Na

Proces obliczeń zatrzymuje się, jeśli ,

gdzie jest określona dokładność.

Ponadto poniższe wyrażenia mogą służyć jako warunek osiągnięcia zadanej dokładności przy udoskonalaniu pierwiastka metodą Newtona:

Schemat algorytmu metody Newtona pokazano na ryc. 1.2.3-7.

Lewa strona pierwotnego równania f(x) i jego pochodna f’(x) w algorytmie zostały zaprojektowane jako osobne moduły oprogramowania.

Ryż. 1.2.3-7. Schemat algorytmu metody Newtona

Przykład 1.2.3-3 Doprecyzuj pierwiastki równania x-ln(x+2) = 0 metodą Newtona, pod warunkiem, że pierwiastki tego równania zostaną rozdzielone na odcinkach x 1 О[-1,9;-1,1] i x 2 О [-0,9;2 ].

Pierwsza pochodna f’(x) = 1 – 1/(x+2) zachowuje swój znak na każdym z odcinków:

f'(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 przy xО [-0,9; 2].

Druga pochodna f"(x) = 1/(x+2) 2 > 0 dla dowolnego x.

Zatem warunki zbieżności są spełnione. Ponieważ f""(x)>0 w całym zakresie wartości dopuszczalnych, to w celu wyjaśnienia pierwiastka z przybliżenia początkowego x 1 wybierz x 0 = -1,9 (ponieważ f(-1,9)×f”(-1,9)>0). Otrzymujemy ciąg przybliżeń:

Kontynuując obliczenia, otrzymujemy następującą sekwencję pierwszych czterech przybliżeń: -1,9; –1,8552, -1,8421; -1,8414 . Wartość funkcji f(x) w punkcie x=-1,8414 jest równa f(-1,8414)=-0,00003 .

Aby wyjaśnić pierwiastek x 2 О[-0,9;2], jako początkowe przybliżenie wybieramy 0 =2 (f(2)×f”(2)>0). Bazując na x 0 = 2 otrzymujemy ciąg przybliżeń: 2,0;1,1817; 1,1462; 1.1461. Wartość funkcji f(x) w punkcie x=1,1461 wynosi f(1,1461)= -0,00006.

Metoda Newtona charakteryzuje się dużym współczynnikiem zbieżności, jednak na każdym kroku wymaga obliczenia nie tylko wartości funkcji, ale także jej pochodnej.

Metoda akordowa

Interpretacja geometryczna metody akordowej następująco
(Rys. 1.2.3-8).

Narysujmy odcinek przechodzący przez punkty A i B. Kolejne przybliżenie x 1 to odcięta punktu przecięcia cięciwy z osią 0x. Skonstruujmy równanie odcinka prostej:

Ustawmy y=0 i znajdźmy wartość x=x 1 (następne przybliżenie):

Powtórzmy proces obliczeń, aby uzyskać kolejne przybliżenie pierwiastka - x 2 :

W naszym przypadku (ryc. 1.2.11) i będzie wyglądał wzór obliczeniowy dla metody akordów

Wzór ten obowiązuje, gdy punkt b przyjmuje się jako punkt stały, a punkt a działa jako przybliżenie początkowe.

Rozważmy inny przypadek (ryc. 1.2.3-9), kiedy .

Równanie linii prostej dla tego przypadku ma postać

Następne przybliżenie x 1 przy y = 0

Wtedy powtarzający się wzór metody akordów dla tego przypadku ma postać

Należy zauważyć, że w metodzie cięciwowej za punkt stały wybiera się koniec odcinka, dla którego spełniony jest warunek f (x)∙f¢¢ (x)>0.

Zatem, jeśli punkt a zostanie przyjęty jako punkt stały , wówczas x 0 = b pełni rolę przybliżenia początkowego i odwrotnie.

Warunki wystarczające zapewniające obliczenie pierwiastka równania f(x) = 0 ze wzoru na cięciwę będą takie same jak dla metody stycznej (metoda Newtona), tyle że zamiast wstępnego przybliżenia wybierany jest punkt stały. Metoda akordów jest modyfikacją metody Newtona. Różnica polega na tym, że kolejnym przybliżeniem w metodzie Newtona jest punkt przecięcia stycznej z osią 0X, a w metodzie cięciwy – punkt przecięcia cięciwy z osią 0X – przybliżenia zbiegają się do pierwiastka z różnych stron .

Oszacowanie błędu dla metody akordów jest podane przez wyrażenie

(1.2.3-15)

Warunek zakończenia procesu iteracji metodą akordową

(1.2.3-16)

W przypadku M1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£mi.

Przykład 1.2.3-4. Wyjaśnij pierwiastek równania e x – 3x = 0, rozdzielony na odcinku z dokładnością 10 -4.

Sprawdźmy warunek zbieżności:

W związku z tym za punkt stały należy przyjąć a=0, a za przybliżenie początkowe przyjąć x 0 =1, gdyż f(0)=1>0 i f(0)*f"(0)>0.

Zmagając się w szkole z rozwiązywaniem równań na lekcjach matematyki, wielu uczniów często jest przekonanych, że zupełnie na próżno marnują swój czas, a przecież taka umiejętność przyda się w życiu nie tylko tym, którzy zdecydują się podążać śladami Kartezjusza, Eulera czy Łobaczewskiego.

W praktyce, np. w medycynie czy ekonomii, często zdarzają się sytuacje, gdy specjalista musi dowiedzieć się, kiedy następuje koncentracja substancja aktywna danego leku osiągnie wymagany poziom we krwi pacjenta lub konieczne jest obliczenie czasu potrzebnego, aby dany biznes stał się rentowny.

Najczęściej mówimy o rozwiązywaniu równań nieliniowych różne rodzaje. Metody numeryczne pozwalają to zrobić tak szybko, jak to możliwe, zwłaszcza przy użyciu komputera. Zostały dobrze przebadane i od dawna udowodniły swoją skuteczność. Należą do nich metoda styczna Newtona, która jest tematem tego artykułu.

Sformułowanie problemu

W tym przypadku istnieje funkcja g, która jest zdefiniowana na odcinku (a, b) i przyjmuje na nim określone wartości, tj. każdemu x należącemu do (a, b) można skojarzyć z określoną liczbą g (X).

Należy wyznaczyć wszystkie pierwiastki równania z przedziału punktów aib (łącznie z końcami), dla których funkcja jest ustawiona na zero. Będą to oczywiście punkty przecięcia y = g(x) z OX.

W niektórych przypadkach wygodniej jest zastąpić g(x)=0 podobnym, np. g 1 (x) = g 2 (x). W tym przypadku odcięte (wartość x) punktów przecięcia wykresów g 1 (x) i g 2 (x) działają jak pierwiastki.

Rozwiązanie równania nieliniowego jest również ważne w przypadku problemów optymalizacyjnych, dla których warunkiem ekstremum lokalnego jest to, że pochodna funkcji dąży do 0. Innymi słowy, taki problem można sprowadzić do znalezienia pierwiastków równania p(x) = 0, gdzie p(x) jest identyczne z g"(x).

Metody rozwiązania

W przypadku niektórych typów równań nieliniowych, takich jak równania kwadratowe lub proste równania trygonometryczne, pierwiastki można znaleźć w dość prosty sposób. W szczególności każdy uczeń zna wzory, za pomocą których można łatwo znaleźć wartości argumentu punktów, w których znika trójmian kwadratowy.

Metody wydobywania pierwiastków równań nieliniowych dzieli się zwykle na analityczne (bezpośrednie) i iteracyjne. W pierwszym przypadku pożądane rozwiązanie ma postać wzoru, za pomocą którego w określonej liczbie operacji arytmetycznych można znaleźć wartość pożądanych pierwiastków. Podobne metody zostały opracowane dla obliczeń wykładniczych, trygonometrycznych, logarytmicznych i prostych równania algebraiczne. W pozostałych przypadkach należy zastosować specjalne metody numeryczne. Można je łatwo wdrożyć za pomocą komputerów, co pozwala znaleźć korzenie z wymaganą dokładnością.

Należą do nich tzw metoda numeryczna styczne.To drugie zaproponował wielki naukowiec Izaak Newton pod koniec XVII wieku. W kolejnych stuleciach metodę wielokrotnie udoskonalano.

Lokalizacja

Metody numeryczne rozwiązywania złożonych równań, które nie mają rozwiązań analitycznych, przeprowadza się zwykle w 2 etapach. Najpierw musisz je zlokalizować. Operacja ta polega na znalezieniu takich odcinków na OX, na których znajduje się jeden pierwiastek rozwiązywanego równania.

Rozważmy segment. Jeśli g(x) nie ma na sobie nieciągłości i przyjmuje na końcach wartości różnych znaków, to pomiędzy a i b lub w nich jest przynajmniej 1 pierwiastek równania g(x) = 0. Aby to było być unikalne, wymagane jest, aby g(x) nie było monotoniczne. Jak wiadomo, będzie miał tę własność pod warunkiem, że znak g’(x) będzie stały.

Innymi słowy, jeśli g(x) nie ma nieciągłości i monotonicznie rośnie lub maleje, a jego wartości na końcach nie mają tych samych znaków, to istnieje 1 i tylko 1 pierwiastek z g(x).

Powinieneś jednak wiedzieć, że to kryterium nie będzie miało zastosowania do pierwiastków równań, które są wielokrotne.

Rozwiązywanie równania poprzez dzielenie na pół

Zanim zaczniemy rozważać bardziej złożone styczne numeryczne i ich odmiany, warto zapoznać się z nimi jak najbardziej w prosty sposób identyfikowanie korzeni. Nazywa się to dychotomią i odnosi się do intuicyjnego sposobu znajdowania pierwiastków, opartego na twierdzeniu, że jeśli dla g(x), ciągłego, spełniony jest warunek różnych znaków, to na rozpatrywanym odcinku znajduje się co najmniej 1 pierwiastek g( x) = 0.

Aby go znaleźć, musisz podzielić odcinek na pół i oznaczyć jego środek jako x 2. Wtedy możliwe są dwie opcje: g(x 0) * g(x 2) lub g(x 2) * g(x 1) są równe lub mniejsze od 0. Wybieramy tę, dla której jedna z nierówności jest prawdziwa. Opisaną powyżej procedurę powtarzamy, aż długość będzie mniejsza od pewnej wcześniej wybranej wartości, która określa dokładność wyznaczenia pierwiastka równania na .

Zaletami tej metody są jej niezawodność i prostota, wadą jest konieczność wstępnego zidentyfikowania punktów, w których g(x) przyjmuje różne znaki, przez co nie można jej stosować do pierwiastków o parzystej krotności. Ponadto nie uogólnia się na przypadek układu równań lub jeśli mówimy o pierwiastkach złożonych.

Przykład 1

Chcielibyśmy rozwiązać równanie g(x) = 2x 5 + x - 1 = 0. Aby nie tracić dużo czasu na szukanie odpowiedniego segmentu budujemy wykres korzystając np. ze znanego programu Excel . Widzimy, że lepiej jest przyjmować wartości z przedziału jako segmentu do lokalizacji korzenia. Możemy być pewni, że istnieje na nim co najmniej jeden pierwiastek wymaganego równania.

g"(x) = 10x 4 + 1, czyli jest to funkcja rosnąca monotonicznie, więc na wybranym odcinku jest tylko 1 pierwiastek.

Podstawiamy punkty końcowe do równania. Mamy odpowiednio 0 i 1. W pierwszym kroku za rozwiązanie przyjmujemy punkt 0,5. Wtedy g(0,5) = -0,4375. Oznacza to, że następnym segmentem halvingu będzie . Jego punkt środkowy- 0,75. W nim wartość funkcji wynosi 0,226. Bierzemy pod uwagę odcinek i jego środek, który znajduje się w punkcie 0,625. Obliczamy, że wartość g(x) wynosi 0,625. Jest równy -0,11, czyli ujemny. Na podstawie tego wyniku wybieramy segment. Otrzymujemy x = 0,6875. Wtedy g(x) = -0,00532. Jeżeli dokładność rozwiązania wynosi 0,01, to możemy założyć, że pożądany wynik to 0,6875.

Podstawy teoretyczne

Ta metoda znajdowania pierwiastków metodą styczną Newtona jest popularna ze względu na bardzo szybką zbieżność.

Opiera się na udowodnionym fakcie, że jeśli x n jest przybliżeniem pierwiastka f(x) = 0 takim, że f” C 1, to kolejne przybliżenie będzie w punkcie, w którym równanie stycznej do f(x) jest zerowany, tj.

Podstaw x = x n+1 i ustaw y na zero.

Wtedy tangensy wyglądają następująco:

Przykład 2

Spróbujmy zastosować klasyczną metodę styczną Newtona i znaleźć rozwiązanie jakiegoś równania nieliniowego, które jest trudne lub niemożliwe do znalezienia analitycznie.

Niech będzie konieczne określenie pierwiastków dla x 3 + 4x - 3 = 0 z pewną dokładnością, na przykład 0,001. Jak wiadomo wykres dowolnej funkcji w postaci wielomianu stopnia nieparzystego musi przynajmniej raz przeciąć oś OX, czyli nie ma wątpliwości co do istnienia pierwiastków.

Przed rozwiązaniem naszego przykładu metodą styczną budujemy graf f(x) = x 3 + 4x - 3 punktowo. Można to bardzo łatwo zrobić, na przykład za pomocą edytora arkuszy kalkulacyjnych Excel. Z powstałego wykresu będzie jasne, że nie przecina się on z osią OX i funkcja y = x 3 + 4x - 3 rośnie monotonicznie. Możemy być pewni, że równanie x 3 + 4x - 3 = 0 ma rozwiązanie i jest jedyne w swoim rodzaju.

Algorytm

Każde rozwiązanie równań metodą styczną rozpoczyna się od obliczenia f "(x). Mamy:

Wtedy drugą pochodną będzie x * 6.

Korzystając z tych wyrażeń, możemy napisać wzór na identyfikację pierwiastków równania metodą styczną w postaci:

Następnie należy wybrać wstępne przybliżenie, tj. zdecydować, który punkt uznać za punkt początkowy (objętość x 0) w procesie iteracyjnym. Rozważamy końce segmentu. Użyjemy tej, dla której spełniony jest warunek, że funkcja i jej druga pochodna przy x 0 mają różne znaki. Jak widać, przy podstawieniu x 0 = 0 jest to zepsute, ale x 0 = 1 jest całkiem odpowiednie.

wówczas jeśli interesuje nas rozwiązanie metody stycznej z dokładnością e, to wartość x n można uznać za spełniającą wymagania zadania, pod warunkiem, że nierówność |f(x n) / f’(x n)|< e.

W pierwszym kroku stycznym mamy:

x 1 = x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) = 1- 0,2857 = 0,71429;
ponieważ warunek nie jest spełniony, przechodzimy dalej;
otrzymujemy nową wartość dla x 2, która jest równa 0,674;
zauważamy, że stosunek wartości funkcji do jej pochodnej w x 2 jest mniejszy niż 0,0063, zatrzymujemy proces.

Metoda styczna w Excelu

Poprzedni przykład możesz rozwiązać znacznie łatwiej i szybciej, jeśli nie wykonasz obliczeń ręcznie (na kalkulatorze), ale skorzystasz z możliwości procesora arkusza kalkulacyjnego firmy Microsoft.

Aby to zrobić, musisz utworzyć nową stronę w programie Excel i wypełnić jej komórki następującymi formułami:

w C7 piszemy „= STOPIEŃ (B7;3) + 4 * B7 - 3”;
w D7 wpisujemy „= 4 + 3 * STOPIEŃ (B7;2)”;
w E7 piszemy „= (STOP (B7;3)- 3 + 4 * B7) / (3* STOPNIE (B7;2) + 4)”;
w D7 wpisujemy wyrażenie „=B7 - E7”;
w B8 wpisujemy formułę warunku „=JEŻELI(E7< 0,001;"Завершение итераций"; D7)».

W przypadku konkretnego problemu w komórce B10 pojawi się napis „Zakończenie iteracji”, a do rozwiązania problemu należy wziąć liczbę wpisaną w komórkę znajdującą się wiersz powyżej. Można także wybrać dla niej oddzielną „rozciągliwą” kolumnę, wpisując tam warunek-formułę, zgodnie z którym zostanie tam zapisany wynik, jeśli zawartość w tej czy innej komórce kolumny B przyjmie postać „Zakończenie iteracji”.

Implementacja w Pascalu

Spróbujmy znaleźć rozwiązanie równania nieliniowego y = x 4 - 4 - 2 * x metodą styczną w Pascalu.

Korzystamy z funkcji pomocniczej, która pomoże w przeprowadzeniu przybliżonego obliczenia f"(x) = (f(x + delta) - f(x)) / delta. Jako warunek zakończenia procesu iteracyjnego wybieramy spełnienie nierówność |x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

Program wyróżnia się tym, że nie wymaga ręcznego obliczania pochodnej.

Metoda akordowa

Rozważmy inny sposób identyfikacji pierwiastków równań nieliniowych. Proces iteracyjny polega na tym, że w miarę kolejnych przybliżeń do pożądanego pierwiastka dla f(x) = 0 przyjmuje się wartości punktów przecięcia cięciwy z odciętymi punktów końcowych a i b z OX, oznaczone jako x 1, ..., x n. Mamy:

Dla punktu przecięcia cięciwy z osią OX wyrażenie zostanie zapisane jako:

Niech druga pochodna będzie dodatnia dla x £ (przypadek odwrotny zostanie zredukowany do rozpatrywanego, jeśli napiszemy f(x) = 0). W tym przypadku wykres y = f(x) jest krzywą wypukłą u dołu i umieszczoną poniżej cięciwy AB. Mogą być 2 przypadki: gdy funkcja ma wartość dodatnią w punkcie a lub jest ujemna w punkcie b.

W pierwszym przypadku wybieramy koniec a jako stały, a punkt b przyjmujemy jako x 0. Następnie kolejne przybliżenia według przedstawionego wzoru tworzą ciąg malejący monotonicznie.

W drugim przypadku koniec b jest ustalony w x 0 = a. Wartości x uzyskane na każdym etapie iteracji tworzą sekwencję, która rośnie monotonicznie.

Możemy zatem stwierdzić, że:

w metodzie akordów stałym końcem odcinka jest ten, w którym znaki funkcji i jej drugiej pochodnej nie pokrywają się;
przybliżenia pierwiastka x - x m - leżą od niego po stronie, gdzie f(x) ma znak niezgodny ze znakiem f"" (x).

Iteracje można kontynuować aż do spełnienia warunków bliskości pierwiastków w tym i poprzednim kroku iteracji modulo abs(x m - x m - 1)< e.

Zmodyfikowana metoda

Połączona metoda akordów i stycznych pozwala ustalić pierwiastki równania, podchodząc do nich z różnych stron. Wartość ta, przy której wykres f(x) przecina OX, pozwala na doprecyzowanie rozwiązania znacznie szybciej, niż przy zastosowaniu każdej z metod osobno.

Załóżmy, że musimy znaleźć pierwiastki f(x)=0, jeśli istnieją na . Możesz zastosować dowolną z metod opisanych powyżej. Lepiej jednak wypróbować ich kombinację, co znacznie poprawi dokładność korzenia.

Rozważamy przypadek z przybliżeniem początkowym odpowiadającym warunkowi, że pierwsza i druga pochodna mają różne znaki w określonym punkcie x.

W takich warunkach rozwiązywanie równań nieliniowych metodą styczną pozwala znaleźć pierwiastek z nadmiarem, jeśli x 0 = b, a metoda wykorzystująca cięciwy z ustalonym końcem b prowadzi do znalezienia pierwiastka przybliżonego z niedoborem.

Stosowane formuły:

Teraz wymagany pierwiastek x musi zostać przeszukany w przedziale. W kolejnym kroku należy zastosować do tego segmentu metodę łączoną. Postępując w ten sposób otrzymujemy wzory postaci:

Jeżeli pierwsza i druga pochodna mają różne znaki, to rozumując w podobny sposób, aby wyjaśnić pierwiastek, otrzymujemy następujące powtarzające się wzory:

Zastosowanym warunkiem jest szacowana nierówność| b n +1 - za n +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

Jeżeli powyższa nierówność jest prawdziwa, to jako pierwiastek równania nieliniowego na danym odcinku należy przyjąć punkt znajdujący się dokładnie w połowie drogi pomiędzy rozwiązaniami znalezionymi w konkretnym kroku iteracji.

Połączoną metodę można łatwo wdrożyć w środowisku TURBO PASCAL. Jeśli naprawdę chcesz, możesz spróbować przeprowadzić wszystkie obliczenia metodą tabelaryczną w Excelu.

W tym drugim przypadku przydzielono kilka kolumn do rozwiązania problemu za pomocą akordów i osobno dla metody zaproponowanej przez Izaaka Newtona.

W tym przypadku każda linia służy do zapisywania obliczeń na określonym etapie iteracji przy użyciu dwóch metod. Następnie po lewej stronie obszaru rozwiązań na aktywnej stronie roboczej podświetlona jest kolumna, w której wpisywany jest wynik obliczenia modułu różnicy wartości kolejnego kroku iteracyjnego dla każdej z metod. Drugim można wprowadzić wyniki obliczeń na podstawie wzoru na obliczenie konstrukcji logicznej „JEŚLI”, służącej do sprawdzenia, czy warunek jest prawdziwy, czy nie.

Teraz wiesz, jak rozwiązywać złożone równania. Metodę styczną, jak już widzieliście, można wdrożyć w prosty sposób, zarówno w Pascalu, jak i Excelu. Dlatego zawsze możesz wyznaczyć pierwiastki równania, które jest trudne lub niemożliwe do rozwiązania za pomocą wzorów.

To samo co przybliżenie. Termin P. jest czasami używany w znaczeniu przybliżenia obiektu (na przykład początkowego P.) ... Encyklopedia matematyczna

Metoda Newtona- Metoda Newtona, algorytm Newtona (znany również jako metoda styczna) to iteracyjna metoda numeryczna służąca do znajdowania pierwiastka (zera) danej funkcji. Metodę tę po raz pierwszy zaproponował angielski fizyk, matematyk i astronom Izaak Newton... ... Wikipedia

Metoda jednej stycznej

Metoda Gaussa-Newtona- Metoda Newtona (znana również jako metoda styczna) jest iteracyjną metodą numeryczną służącą do znajdowania pierwiastka (zera) danej funkcji. Metodę tę po raz pierwszy zaproponował angielski fizyk, matematyk i astronom Izaak Newton (1643–1727) pod nazwą… ... Wikipedia

Metoda Newtona-Raphsona- Metoda Newtona (znana również jako metoda styczna) jest iteracyjną metodą numeryczną służącą do znajdowania pierwiastka (zera) danej funkcji. Metodę tę po raz pierwszy zaproponował angielski fizyk, matematyk i astronom Izaak Newton (1643–1727) pod nazwą… ... Wikipedia

Metoda styczna- Metoda Newtona (znana również jako metoda styczna) jest iteracyjną metodą numeryczną służącą do znajdowania pierwiastka (zera) danej funkcji. Metodę tę po raz pierwszy zaproponował angielski fizyk, matematyk i astronom Izaak Newton (1643–1727) pod nazwą… ... Wikipedia

Metoda styczna (metoda Newtona)- Metoda Newtona (znana również jako metoda styczna) jest iteracyjną metodą numeryczną służącą do znajdowania pierwiastka (zera) danej funkcji. Metodę tę po raz pierwszy zaproponował angielski fizyk, matematyk i astronom Izaak Newton (1643–1727) pod nazwą… ... Wikipedia

Numeryczne rozwiązywanie równań- a ich układy polegają na przybliżonym określeniu pierwiastka lub pierwiastków równania lub układu równań i są stosowane w przypadkach, gdy obliczenie dokładnej wartości jest niemożliwe lub bardzo pracochłonne. Spis treści 1 Opis problemu 2 Metody numeryczne... Wikipedia

Metoda kolejnych aproksymacji- metoda rozwiązywania problemów matematycznych wykorzystująca ciąg przybliżeń, który zbiega się do rozwiązania i jest konstruowany rekurencyjnie (tzn. każde nowe przybliżenie obliczane jest na podstawie poprzedniego; przybliżenie początkowe wybierane jest w ... ... Wielka encyklopedia radziecka

W problematyce minimalizacji funkcji istotny jest trafny wybór przybliżenia początkowego.Oczywiście nie da się ustalić ogólnej reguły, która byłaby zadowalająca dla wszystkich przypadków, czyli dla wszystkich możliwych funkcji nieliniowych. Za każdym razem trzeba szukać własnego rozwiązania. Poniżej proponujemy zestaw kilku metod znajdowania zgrubnych przybliżeń początkowych, które w praktyce mogą służyć jako punkt wyjścia do poszukiwania zadowalających przybliżeń w konkretnym problemie.

9.6.1. Wyszukiwanie siatki. Metoda ta jest szczególnie efektywna przy małej liczbie rzeczywistych parametrów nieliniowych. Często funkcje są projektowane w taki sposób, że gdy wartości niektórych parametrów (które nazywamy nieliniowymi) są stałe, reszta parametrów staje się liniowa.

Po określeniu dolnej i górnej granicy parametrów nieliniowych, w pewnym kroku można wyliczyć opcje na wynikowej siatce wartości samych parametrów nieliniowych i zidentyfikować regresję liniową prowadzącą do minimalnej sumy kwadratów .

Jako przykład rozważmy funkcję

Tutaj rzeczywistym parametrem nieliniowym będzie . Powiedzmy, że to wiadomo. Niech h będzie krokiem dla parametru. Obliczmy regresję liniową

gdzie znajdujemy minimalną sumę kwadratów dla każdego z nich. Najmniejszy z nich odpowiada optymalnemu przybliżeniu początkowemu. W zasadzie krok, od którego zależy „gęstość” siatki, może się zmieniać, tak że zmniejszając wartość h, można znaleźć wartości parametrów z dowolną dokładnością.

9.6.2. Transformacja modelu.

Czasami, poprzez jakąś transformację, model można sprowadzić do liniowego lub zmniejszyć liczbę rzeczywistych parametrów nieliniowych (patrz rozdział 6.2.3). Pokażmy, jak można to osiągnąć na przykładzie krzywej logistycznej

Wykonując odwrotną transformację odpowiednich równań regresji, otrzymujemy

Oznaczając, dochodzimy do nowej funkcji, której liczba parametrów liniowych wzrosła z jednego do dwóch. Oszacowanie parametru w nowym modelu można znaleźć np. korzystając z poprzedniej metody.

W tym miejscu wypada poczynić następującą uwagę dotyczącą przekształceń modeli regresji. Należy pamiętać, że błąd, który w pierwotnym równaniu był addytywny, po przekształceniu, ogólnie rzecz biorąc, nie będzie już addytywny.

Korzystając z rozwinięcia szeregu Taylora i oznaczając transformację przez, otrzymujemy, zaniedbując warunki porządku

Wynika, że

Ostatnią równość można przyjąć jako podstawę do analizy problemu z przekształconym modelem.

9.6.3. Podział próbki na podpróbki.

Aby znaleźć początkowe przybliżenie, możesz podzielić całą próbkę na podpróbki (o mniej więcej równych objętościach), gdzie jest liczba nieznanych parametrów. Dla każdej podpróbki znajdujemy średnie z y i z X, które oznaczamy odpowiednio przez m. Rozwiążmy układ równań nieliniowych dla

Rozwiązaniem tego układu będzie wstępne przybliżenie parametrów. Oczywiście, aby ta metoda „zadziałała”, konieczne jest, aby ten układ równań nieliniowych był w miarę łatwy do rozwiązania, na przykład analitycznie.

9.6.4. Rozwinięcie szeregu Taylora w zmiennych niezależnych.

Podstawą iteracyjnej minimalizacji sumy kwadratów jest rozwinięcie funkcji regresji w szeregu Taylora do wyrazów liniowych w parametrach. Aby znaleźć przybliżone przybliżenie początkowe, czasami przydatna jest procedura aproksymacji regresji poprzez rozwinięcie jej do szeregu Taylora w zmiennych niezależnych. Dla uproszczenia założymy, że jest on jednowymiarowy. Niech będzie wartością średnią, a następnie w przybliżeniu

Oznaczamy , w ten sposób dochodzimy do modelu liniowego

Niech będą szacunkami najmniejszych kwadratów parametrów tej regresji liniowej. Jako wstępne przybliżenia przyjmiemy rozwiązanie nieliniowego układu równań względem