Teoria równań nieliniowych i metoda podziału na pół.

Metoda podziału na pół

Zakładamy, że oddzielenie pierwiastków równania f(x) = 0 jest również przeprowadzane na odcinku [ a, b] jest jeden pierwiastek, który należy uściślić z błędem ε. Jako wstępne przybliżenie pierwiastka przyjmujemy środek tego segmentu: c 0= (a+ b) / 2 (rys. 4):

Ryż. 4. Metoda dzielenia połówkowego.

Następnie badamy wartość funkcji f(x) na końcach segmentów [ a, c 0] oraz [ c 0, b] . To z segmentów, na końcach których f(x) przyjmuje wartości różnych znaków, zawiera pożądany korzeń; dlatego traktujemy to jako nowy segment [ 1, b 1] (na rys. 4 jest to odcinek [ a, c 0]). Druga połowa segmentu [ a, b], na którym f(x) nie zmienia znaku, odrzucamy go. Jako następne przybliżenie pierwiastka bierzemy środek nowego segmentu
c 1= (1+ b 1) / 2 itd. W ten sposób, k-te przybliżenie jest obliczane jako

Po każdej iteracji segment, na którym znajduje się korzeń, jest dzielony o połowę, a po k iteracje w 2 k raz:

Proces iteracyjny należy zakończyć po osiągnięciu określonej dokładności, tj. gdy warunek jest spełniony |x 0 – c k |< ε

Ponieważ korzeń x0 należy do segmentu [ K, b k], a c k jest środkiem tego odcinka, to wartość |x 0 – c k | zawsze będzie mniejsza niż połowa długości od cięcia [ K, b k] (patrz rys. 4):

Dlatego warunek |x 0 – c k |< ε zostanie wykonany, jeśli

| b k – a k |< 2ε

Zatem proces iteracyjny musi być kontynuowany aż do spełnienia warunku | b k – a k |< 2ε .

W przeciwieństwie do większości innych metod udoskonalania, metoda bisekcji zawsze jest zbieżna, tj. ma bezwarunkową zbieżność. Ponadto jest to niezwykle proste, ponieważ wymaga jedynie obliczenia wartości funkcji f(x), a zatem może być używany do rozwiązywania dowolnych równań.

Jednak metoda podziału na pół jest raczej powolna. Z każdym krokiem błąd przybliżonej wartości zmniejsza się o połowę, tj.

dlatego ta metoda jest metodą o liniowej zbieżności.

Uwaga. Metoda bisekcji nie wymaga znajomości dodatkowych informacji o funkcji na całym przedziale [ a, b]. Na przykład funkcja nie musi być różniczkowalna. Nawet dla funkcji nieciągłych rozważana metoda gwarantuje zbieżność. Jeśli w tym przedziale jest kilka pierwiastków równania, zostanie znaleziony jeden z pierwiastków.

metoda akordowa

Rozważana metoda, a także metoda dzielenia połówkowego, mają na celu udoskonalenie pierwiastka na przedziale [ a, b f(x) przyjmuje wartości różnych znaków. Kolejne przybliżenie, w przeciwieństwie do metody dzielenia na pół, odbywa się nie w środku odcinka, ale w punkcie x, gdzie prosta (cięciwa) przecina oś odciętych, poprowadzona przez punkty ALE oraz W(rys. 5).

Ryż. 5. Metoda akordów.

Piszemy równanie prostej przechodzącej przez punkty ALE oraz W:

Dla punktu przecięcia prostej z osią odciętych ( x= x0, tak= 0) otrzymujemy równanie

Jako nowy interwał do kontynuowania procesu iteracyjnego wybieramy jeden z dwóch [ a, x0] oraz [ x 0 , b], na końcach których funkcja f(x) przyjmuje wartości różnych znaków. Dla rozpatrywanego przypadku (rys. 5) wybieramy odcinek [ a, x0], dlatego
f(a) × f(x0)< 0 . Kolejna iteracja polega na zdefiniowaniu nowego przybliżenia x 1 jako punkty przecięcia cięciwy AB 1 z osią odciętych itp.

Proces dopracowywania korzenia kończymy, gdy odległość między kolejnymi przybliżeniami staje się mniejsza niż określona dokładność, tj.

x k+1 – x k< ε

Uwaga. Metoda akordowa i metoda bisekcji są bardzo podobne. Co więcej, drugi z nich w niektórych przypadkach daje szybszą zbieżność procesu iteracyjnego. Obie metody nie wymagają znajomości dodatkowych informacji o funkcji na całym przedziale [ a, b]. Na przykład funkcja nie musi być różniczkowalna. Nawet dla funkcji nieciągłych rozważane metody gwarantują zbieżność.

metoda Newtona (metoda styczna)

Metoda Newtona ma również na celu udoskonalenie pierwiastka na przedziale [ a, b], na końcach których funkcja f(x) przyjmuje wartości różnych znaków. Ale ta metoda wykorzystuje dodatkowe informacje o funkcji f(x). W rezultacie mają szybszą zbieżność, ale jednocześnie mają zastosowanie do węższej klasy funkcji, a ich zbieżność nie zawsze jest gwarantowana.

Rozdzielając pierwiastki funkcji, należy wziąć pod uwagę, że zastosowanie metody Newtona wymaga, aby funkcja była monotoniczna i dwukrotnie różniczkowalna, a druga pochodna f''(x) w tym przedziale nie powinien zmieniać znaku.

Zbieżność ciągu iteracyjnego otrzymanego metodą Newtona zależy od wyboru aproksymacji początkowej x0. Ogólnie, jeśli przedział [ a, b] zawierający pierwiastek i wiadomo, że funkcja f(x) jest monotoniczne na tym przedziale, a następnie jako wstępne przybliżenie x0 możesz wybrać granicę odcinka [ a, b], gdzie znaki funkcji pokrywają się f(x) i druga pochodna f''(x). Taki wybór aproksymacji początkowej gwarantuje zbieżność metody Newtona pod warunkiem, że funkcja jest monotoniczna na przedziale lokalizacji pierwiastków.

Daj nam znać początkowe przybliżenie do pierwiastka x0. Narysuj styczną do krzywej w tym punkcie tak= f(x) (rys. 6). Ta styczna przetnie oś x w punkcie, który uznamy za następne przybliżenie.

Praca laboratoryjna

NUMERYCZNE WYZNACZANIE WYIZOLOWANEGO KORZENIA RÓWNANIA NIELINIOWEGO

Rozwiązywanie równań - algebraicznych lub transcendentalnych - jest jednym z podstawowych zadań analizy stosowanej, którego potrzeba pojawia się w wielu i różnorodnych działach fizyki, mechaniki, technologii i innych dziedzinach.

Niech równanie

f (x) = 0. (1)

Jakikolwiek numer X*, odwrócenie funkcji f(x) do zera, tj. taki, w którym f(X*) = 0, nazywamy pierwiastkiem równania (1) lub zerem funkcji f(x).

Problem liczbowego znalezienia pierwiastków rzeczywistych równania (1) zwykle polega na znalezieniu pierwiastków przybliżonych, tj. znalezienie wystarczająco małych sąsiedztw rozpatrywanego obszaru, który zawiera jedną wartość pierwiastka, a następnie obliczenie pierwiastków z określonym stopniem dokładności.

1. Funkcjonować f(x) jest ciągła na odcinku [ a, b] wraz z jego instrumentami pochodnymi pierwszego i drugiego rzędu;
2. Wartości f(x) na końcach segmentu mają różne znaki ( f(a) * f(b) < 0).

3. Pochodna pierwsza i druga f"(x) oraz f ""(x) zachowują pewien znak w całym przedziale.

Warunki 1) i 2) gwarantują, że na interwale [ a, b] jest co najmniej jeden korzeń, a z 3) wynika, że f(x) jest monotoniczny w tym przedziale, a zatem pierwiastek będzie unikalny.

Problem znalezienia pierwiastka równania f(x) = 0 metodą iteracyjną składa się z dwóch etapów:

1. separacja korzeni- znalezienie przybliżonej wartości pierwiastka lub zawierającego go segmentu;

2. dopracowanie przybliżonych korzeni- doprowadzenie ich do określonego stopnia dokładności.

Proces oddzielania korzeni zaczyna się od ustalenia znaków funkcji f(x) w granicy x=a oraz x=b punktów w obszarze jego istnienia.

Przykład 1 . Oddziel pierwiastki równania:

x 3 – 6x + 2 = 0 (2)

Zróbmy przybliżony diagram:

X	- ∞	- 3	- 1				+ ∞
f(x)	–	–	+	+	–	+	+

Zatem równanie (2) ma trzy pierwiastki rzeczywiste leżące w przedziałach [-3, -1] i .

Orientacyjne wartości korzeni ( wstępne przybliżenia) można również poznać z fizycznego znaczenia problemu, z rozwiązania podobnego problemu z różnymi danymi początkowymi lub można je znaleźć graficznie.

Powszechne w praktyce inżynierskiej graficzny sposób określenie przybliżonych korzeni.

Biorąc pod uwagę, że pierwiastki rzeczywiste równania (1) są punktami przecięcia wykresu funkcji f(x) z osią x wystarczy wykreślić funkcję f(x) i zaznacz punkty przecięcia f(x) z osią Oh, lub zaznacz na osi Oh segmenty zawierające jeden korzeń.

Niech pierwiastek równania (1) będzie izolowany na przedziale [ a, b]. Iteracyjny proces dopracowywania wstępnego przybliżenia X 0 do dokładnego rozwiązania polega na sekwencyjnym uzyskiwaniu kolejnego przybliżenia z poprzedniego (poprzednich). Każdy taki krok nazywa się iteracja. Zastosowanie takiej czy innej metody zależy od dostępnego wstępnego przybliżenia X 0 do pierwiastka, istnienie i gładkość pochodnych funkcji f(x). W wyniku iteracji zostaje znaleziony ciąg przybliżonych wartości korzenia X 1 , X 2 , ..., x n . Jeśli te wartości przy wzroście liczby iteracji n zbliżyć się do prawdziwej wartości pierwiastka, a następnie mówią, że proces iteracyjny zbiega się.

W metodach iteracyjnych ważne jest, aby wybrać kryterium końca liczenia. Jeśli funkcja f(x) w rozpatrywanym regionie zmienia się powoli, tj. pochodna w wartości bezwzględnej jest mniejsza od jedności, to proces iteracyjny należy zakończyć spełnieniem warunku

| x k +1 – x k |< ε ,

gdzie x k , x k+1 - kolejne przybliżenia do pierwiastka, ε > 0 to określona dokładność końca procesu iteracyjnego. Jeśli funkcja zmienia się szybko, tj.

| f(x) | ≥ 1, to proces iteracyjny należy zakończyć, gdy warunek

| f(x k) | < ε .

Metoda podziału na pół

Metoda ta jest jedną z najprostszych iteracyjnych metod obliczania pierwiastka rzeczywistego równania (1) na odcinku [ α , β ]. Jest stosowany, gdy f(x) jest ciągłe w dniu [ α , β ] i na końcach tego segmentu przyjmuje wartości różnych znaków, tj.

f(α )f(β ) < 0.

Schemat obliczeniowy metody. Odcinek [ α , β ] dzieli się na pół i jeśli f≠ 0, następnie wybierz jedną z połówek , , na końcach których funkcja f(x) przyjmuje wartości różnych znaków (w nim jest korzeń). Powstały segment jest ponownie dzielony na pół i opisane czynności są powtarzane aż do uzyskania pierwiastka z określoną dokładnością procesu iteracyjnego. Proces kończy się, gdy warunek zostanie spełniony

| x k +1 – x k |< ε .

Liczba iteracji k w metodzie bisekcji określa wzór

k≈ .

Przykład 1. Użyj metody bisekcji, aby obliczyć pierwiastek równania

X 3 + 3X 2 – 1 = 0 (2)

z dokładnością 0,01 na odcinku.

Sprawdzamy warunki zastosowania metody. Funkcjonować f(x) jest wielomianem trzeciego stopnia (ciągły) i f(0)f(1) < 0.

Kolejno obliczamy przybliżenia do pierwiastka i sprawdzamy je pod kątem dokładności:

x 0 = 0		f(0)= – 1	[ –, + ]
x 1 = 1	|0 – 1| > 0,01	f(1)=3
x 2 = 0,5	|1 – 0,5|> 0,01	f(0,5)= – 0,125
x 3 = 0,75	|0,5 – 0,75|> 0,01	f(0,75)≈1,109
x 4 = 0,625	|0,5 – 0,625|> 0,01	f(0,625)≈0,416
x 5 = 0,5625	|0,5 – 0,5625|> 0,01	f(0,5625)≈0,127
x 6 = 0,53125	|0,5 – 0,53125|> 0,01	f(0,53125)≈ – 0,0034
x 7 = 0,546875	|0,53125 – 0,546875|> 0,01	f(0, 546875)≈0,0608
x 8 = 0,5390625	|0,53125 – 0,5390625|≤ 0,01	f(0, 5390625)≈0,0284

Za wyrafinowaną wartość pierwiastka weźmy wartość

Metoda podziału na pół(inne nazwy: metoda bisekcji, metoda dychotomii) rozwiązać równanie f(x) = 0 jest następujący. Niech wiadomo, że funkcja jest ciągła i przyjmuje końce odcinka
[a, b] wartości różnych znaków, to korzeń jest zawarty w przedziale ( a, b). Przedział dzielimy na dwie połowy, a następnie rozważymy połowę, na końcach której funkcja przyjmuje wartości różnych znaków. Ponownie dzielimy ten nowy segment na dwie równe części i wybieramy z nich ten, który zawiera pierwiastek. Proces ten trwa, dopóki długość następnego segmentu nie będzie mniejsza niż wymagana wartość błędu. Bardziej rygorystyczne przedstawienie algorytmu metody bisekcji:

1) Oblicz x = (a+ b)/2; obliczać f(x);

2) Jeśli f(x) = 0, następnie przejdź do punktu 5;

3) Jeśli f(x)∙f(a) < 0, то b = x, Inaczej a = x;

4) Jeżeli | b – a| > ε, przejdź do kroku 1;

5) Wartość wyjściowa x;

Przykład 2.4. Udoskonal metodą bisekcji z dokładnością 0,01 pierwiastka równania ( x– 1) 3 = 0, należące do segmentu .

Rozwiązanie w programie przewyższać:

1) W komórkach A 1:F 4 wprowadzamy notację, wartości początkowe i wzory, jak pokazano w tabeli 2.3.

2) Kopiujemy każdą formułę do dolnych komórek za pomocą znacznika wypełnienia do dziesiątej linii, tj. B 4 - przed B 10, C 4 - przed C 10, D 3 - przed D 10, mi 4 - przed mi 10, F 3 - przed F 10.

Tabela 2.3

	A	B	C	D	mi	F
		f(a)=	=(1-B3)^3
	k	a	x	f(x)	b	b-a
		0,95	=(B3+E3)/2	=(1-C3)^3	1,1	=E3-B3
		=JEŻELI(D3=0,C3;JEŻELI(C$1*D3<0;B3;C3))			=JEŻELI(C$1*D3>0, E3;C3)

Wyniki obliczeń podano w tabeli. 2.4. W kolumnie F sprawdzanie wartości długości interwałów b – a. Jeżeli wartość jest mniejsza niż 0,01, to w tym wierszu znaleziono przybliżoną wartość pierwiastka z danym błędem. Osiągnięcie wymaganej dokładności wymagało 5 iteracji. Przybliżona wartość pierwiastka z dokładnością do 0,01 po zaokrągleniu do trzech miejsc po przecinku wynosi 1.0015625 ≈ 1,00.

Tabela 2.4

	A	B	C	D	mi	F
		f(a)=	0,000125
	k	a	x	f(x)	b	b-a
		0,95	1,025	-2E-05	1,1	0,15
		0,95	0,9875	2E-06	1,025	0,075
		0,9875	1,00625	-2E-07	1,025	0,0375
		0,9875	0,996875	3.1E-08	1,00625	0,0187
		0,996875	1,0015625	-4E-09	1,00625	0,0094
		0,996875	0,9992188	4.8E-10	1,0015625	0,0047
		0,99921875	1,0003906	-6E-11	1,0015625	0,0023
		0,99921875	0,9998047	7.5E-12	1,000390625	0,0012

Powyższy algorytm uwzględnia możliwy przypadek „uderzenia w root”, tj. równość f(x) do zera na następnym etapie. Jeśli w przykładzie 2.3 weźmiemy segment , to w pierwszym kroku dojdziemy do korzenia x= 1. Rzeczywiście piszemy w komórce B 3 wartość 0,9. Wtedy tabela wyników przyjmie postać 2.5 (podane są tylko 2 iteracje).

Tabela 2.5

	A	B	C	D	mi	F
		f(a)=	0,001
	k	a	x	f(x)	b	b-a
		0,9			1,1	0,2

Stwórzmy w programie przewyższać zdefiniowane przez użytkownika funkcje f(x) i bisect(a, b, eps) do rozwiązania równania metodą dzielenia połówkowego przy użyciu wbudowanego języka Visual Basic. Ich opisy znajdują się poniżej:

Funkcja f(Byval x)

Funkcja bisect(a, b, eps)

1 x = (a + b) / 2

Jeśli f(x) = 0 to przejdź do 5

Jeśli f(x) * f(a)< 0 Then

Jeśli Abs(a - b) > eps, to przejdź do 1

Funkcja f(x) definiuje lewą stronę równania, a funkcja
bisect(a, b, eps) przecina pierwiastek równania f(x) = 0. Zauważ, że funkcja bisect(a, b, eps) używa wywołania funkcji f(x). Oto algorytm tworzenia funkcji zdefiniowanej przez użytkownika:

1) Wykonaj polecenie menu „Narzędzia – Makro – Edytor Visual Basic”. Okno " Microsoft Visual Basic”. Jeśli w tym pliku programu przewyższać makra lub funkcje lub procedury zdefiniowane przez użytkownika nie zostały jeszcze utworzone, to okno będzie wyglądać tak, jak pokazano na rysunku 2.4.

2) Wykonać polecenie menu „Wstaw - Moduł” i wprowadzić teksty programów funkcyjnych, jak pokazano na rysunku 2.5.

Teraz w komórkach arkusza programu przewyższać możesz wykorzystać stworzone funkcje w formułach. Na przykład wpiszmy komórkę D Formuła 18

Dwudzielna (0,95;1;0,00001),

wtedy otrzymujemy wartość 0,9999993896.

Aby rozwiązać kolejne równanie (z inną lewą stroną), należy przejść do okna edytora za pomocą polecenia „Narzędzia – Makro – Edytor Visual Basic» i po prostu przepisz opis funkcji f(x). Na przykład znajdźmy pierwiastek równania sin5 . z dokładnością 0,001 x+x 2 - 1 = 0, należące do przedziału (0,4; 0,5). Aby to zrobić, zmień opis funkcji

do nowego opisu

f = Sin(5 * x) + x^2 - 1

Następnie w celi D 18 otrzymujemy wartość 0.441009521 (porównaj ten wynik z wartością pierwiastka przedziału (0,4; 0,5) z przykładu 2,3!).

Aby rozwiązać równanie metodą dzielenia na pół w programie Mathcad utwórz podprogram funkcji bisec(f, a, b, ε), gdzie:

f- nazwa funkcji odpowiadająca lewej stronie równania f(x) = 0;

a, b- lewy i prawy koniec segmentu [ a, b];

ε jest dokładnością przybliżonej wartości pierwiastka.

Rozwiązanie przykładu w programie Mathcad:

1) Uruchom program Mathcad. Wprowadzamy definicję funkcji bisec(f, a, b, ε). Aby to zrobić, korzystając z klawiatury i paska narzędzi Symbole greckie, wpisujemy bisec(f, a, b, ε):=. Po znaku przypisania ":=" na pasku narzędzi "Programowanie" kliknij lewym przyciskiem "Dodaj linię" wskaźnikiem myszy. Po znaku przypisania pojawi się pionowa linia. Następnie wprowadź tekst programu, który pokazano poniżej, korzystając z paska narzędzi „Programowanie” wpisz znak „←”, operator pętli podczas gdy, operator przerwanie i operator warunkowy jeśli inaczej.

2) Wprowadzamy definicję funkcji f(x):=sin(5*x)+x^2–1, a następnie oblicz wartość pierwiastka za pomocą funkcji bisec dla podanych wartości:
bisec(f, –0,8,–0,7,0,0001)=. Po znaku „=” obliczona przez program wartość pierwiastkowa automatycznie pojawi się -0,7266601563. W ten sam sposób obliczamy resztę pierwiastków.

Poniżej znajduje się arkusz Mathcad z definicją funkcji bisec(f, a, b, ε) i obliczenia:

Prezentujemy program w języku C++ rozwiązać równanie f(x) = 0 metodą bisekcji:

#włączać

#włączać

podwójne f(podwójne x);

typedef double (*PF)(double);

podwójna bisec(PF f,podwójne a,podwójne b,podwójne eps);

podwójne a, b, x, eps;PF pf;

Cout<< "\n a = "; cin >>a;

Cout<< "\n b = "; cin >>b;

Cout<< "\n eps = "; cin >>eps;

x = bisec(pf,a,b,eps); Cout<< "\n x = " << x;

Cout<< "\n Press any key & Enter "; cin >>a;

podwójne f(podwójne x)(

r = grzech(5*x)+x*x-1;

podwójna bis(PF f, podwójna a, podwójna b, podwójna eps)(

zrób( x = (a + b)/2;

if (f(x) == 0) przerwa;

jeśli (f(x)*f(a)<0) b = x;

) while (fabs(b-a) > eps);

Funkcja w programie f(x) jest zdefiniowany w celu rozwiązania równania

grzech5 x+x 2 – 1 = 0

z przykładu 2.3. Poniżej przedstawiono wynik programu do wyznaczania pierwiastka przedziału (0,4; 0,5) z dokładnością do 0,00001 (ekran komputera):

Naciśnij dowolny klawisz i Enter

Ostatnia linia jest potrzebna, aby zatrzymać się, aby zobaczyć wynik.

Wynajmować f(x) jest funkcją ciągłą na [ a; b], .

metoda Newtona (metoda styczna)

Wynajmować f(x) jest funkcją podwójnie różniczkowalną w sposób ciągły na przedziale [ a; b],
,
oraz
nie zmieniaj znaku na [ a; b].

Oznacz przez koniec segmentu, w którym znaki
oraz
mecz. Kolejne przybliżenia do dokładnego pierwiastka c znajdź według wzoru

dla
.

Następnie
jest dokładnym pierwiastkiem równania (1).

Proces obliczeniowy zwykle zatrzymuje się, gdy
okazuje się być mniejsza niż określona dokładność ε . Jednak warunek ten nie może ściśle zagwarantować osiągnięcia określonej dokładności. Aby uzyskać pełną pewność, możesz przeprowadzić kontrolę dokładności, jak wspomniano na początku sekcji. Jeśli dokładność nie zostanie osiągnięta, musisz powtórzyć iteracje jeszcze kilka razy.

Metoda siecznych

Niech będzie jakieś wstępne przybliżenie . Ze wzoru otrzymujemy jeszcze jeden punkt
, gdzie h- mała liczba. Założymy, że wykonaliśmy kilka kroków metody i w tym momencie mamy dwa kolejne przybliżenia oraz
do dokładnego korzenia (na początkowym etapie jest to oraz ). Następnie następne przybliżenie znajduje się we wzorze

,

Proces zatrzymuje się według tego samego kryterium, co w metodzie Newtona.

Metoda iteracji

W metodzie iteracyjnej pierwotne równanie (1) jest przekształcane w równanie równoważne
. Wybierz wstępne przypuszczenie . Każde następne przybliżenie otrzymujemy ze wzoru
,
Proces zatrzymuje się według tego samego kryterium, co w metodzie Newtona. Metoda będzie zbieżna, tj. limit jest równa dokładnej wartości pierwiastka, jeśli nierówność
a początkowe przybliżenie jest wystarczająco blisko korzenia.

Zalety i wady metod

Metoda bisekcji wymaga wyciągnięcia pierwiastka, a aby osiągnąć dużą dokładność, funkcję trzeba obliczać wielokrotnie. Osiągnięcie określonej dokładności w tej metodzie jest gwarantowane.

Metoda Newtona ma bardzo szybką zbieżność (zbieżność kwadratową), tj.

,

gdzie c- dokładna wartość korzenia; M jest pewną stałą w zależności od funkcji. Z grubsza mówiąc, począwszy od pewnej iteracji, liczba poprawnych miejsc dziesiętnych podwoi się w każdej iteracji.

Aby zagwarantować zbieżność metody Newtona, wymagane jest kilka warunków. Ogólnie rzecz biorąc, można rozpocząć obliczenia metodą Newtona bez sprawdzenia tych warunków, ale wówczas zbieżność może nie być obserwowana.

Metoda siecznych zapewnia dla funkcji gładkich stopień zbieżności zbliżony do metody Newtona. Nie wymaga obliczania pochodnej funkcji. Jeśli punkt początkowy jest daleko od korzenia, może nie być zbieżności.

Metoda iteracyjna daje znacznie niższy współczynnik zbieżności niż metoda Newtona. W przypadku zbieżności oszacowanie
, gdzie
- liczby,
,
;c jest dokładną wartością korzenia. Wielkie ilości M, q zależą od funkcji i nie zależą od numeru iteracji. Jeśli
blisko 1, to q jest również bliski 1, a zbieżność metody będzie powolna. Możesz rozpocząć liczenie iteracji bez sprawdzania warunków
oraz . W takim przypadku proces może być rozbieżny, a wtedy odpowiedź nie zostanie otrzymana.

Istnieje wiele metod znajdowania pierwiastków równania nieliniowego, innych niż wymienione. W MATHCAD funkcja root ma format
wykorzystuje metodę siecznych, a jeśli nie prowadzi do pożądanych rezultatów, to metoda Mullera. W tym ostatnim, w przeciwieństwie do metody siecznych, na każdym kroku pobierane są dwa dodatkowe punkty, wykres funkcji zastępuje parabola przechodząca przez trzy punkty, a punkt przecięcia paraboli z osią Wół. W funkcji root w formacie root( f(x), x, a, b) stosuje się metody Riddera i Brenta. Aby znaleźć pierwiastki wielomianu w MATHCAD, stosuje się metodę Laguerre'a.

Metoda podziału na pół (metoda znana jest również jako metoda Bolzano lub metoda dychotomii) jeden metod rozwiązywania równań nieliniowych i opiera się na sukcesywnym zawężaniu przedziału zawierającego pojedynczy pierwiastek równania . Proces iteracyjny jest prowadzony aż do osiągnięcia określonej dokładności.

Niech zostanie podane równanie i segment zdefiniowany tak, że ten segment zawiera jeden pierwiastek z równania . Następnie na końcach danego segmentu funkcja ma wartości o przeciwnych znakach: . Przeciwieństwo znaków wartości funkcji na końcach segmentu można określić na wiele sposobów. Jednym z wielu tych sposobów jest pomnożenie wartości funkcji na końcach segmentu i wyznaczenie znaku produktu poprzez porównanie wyniku mnożenia z zerem:

.

Odcinek nazywamy początkowym przedziałem niepewności, ponieważ wiadomo, że należy do niego pierwiastek, ale jego położenie nie zostało określone z wymaganą dokładnością.

Procedura doprecyzowania położenia pierwiastka polega na skonstruowaniu sekwencji zagnieżdżonych w sobie segmentów, z których każdy zawiera pierwiastek równania. W tym celu znajduje się środek bieżącego przedziału niepewności , , a jako następny przedział niepewności wybierany jest ten, na którego końcach funkcja ma różne znaki.

Proces kończy się, gdy długość bieżącego przedziału niepewności jest mniejsza niż określona wartość , która określa dokładność znalezienia pierwiastka. Jako przybliżoną wartość pierwiastka przyjmuje się środek ostatniego przedziału niepewności.

Metoda ma liniową, ale bezwarunkową zbieżność, a jej błąd dla każdej iteracji jest zmniejszony o połowę:

Z tej zależności możemy oszacować liczbę iteracji k aby osiągnąć określoną dokładność:

Z otrzymanego wzoru możemy wywnioskować, że aby uzyskać dokładność z długości szczeliny początkowej, konieczne jest wykonanie około dziesięciu iteracji.

Do zalet metody należy również zaliczyć fakt, że pozwala ona na znalezienie prostego pierwiastka równania dowolnych funkcji ciągłych dla dowolnych wartości takich, że .

Wadą metody jest to, że nie można jej uogólniać na układy równań nieliniowych i nie można jej używać do znajdowania pierwiastków nawet wielokrotności.

Algorytm znajdowania pierwiastka nieliniowego równania metodą bisekcji.

1. Znajdź początkowy przedział niepewności za pomocą jednej z metod separacji pierwiastków.Ustaw błąd obliczeń (mała liczba dodatnia) ) i początkowy krok iteracji () .

2. Znajdź środek bieżącego przedziału niepewności:

3. Konieczne jest znalezienie wartości funkcji w punktach , i . Następnie musisz sprawdzić dwa warunki:

Jeśli warunek jest spełniony , to żądany korzeń znajduje się w lewym segmencie umieścić, ;

Jeśli warunek jest spełniony , to żądany korzeń znajduje się w prawym segmencie, weź , .

W rezultacie znajduje się nowy przedział niepewności, na którym znajduje się pożądany pierwiastek równania:

4. Nowy segment sprawdzamy pod kątem określonej dokładności w przypadku:

Jeśli długość nowego segmentu jest mniejsza niż określona dokładność , iteracyjny proces kończy się. Przybliżoną wartość korzenia określa wzór:

Jeżeli długość nowego segmentu nie osiąga wymaganej dokładności, należy kontynuować proces iteracyjny i przejść do kroku 2 rozpatrywanego algorytmu.