Metody numeryczne fizyki/Rozwiązywanie równań nieliniowych w sposób przybliżony

Rozwiązywanie równań nieliniowych w sposób przybliżony

---

Licencja

Autor: Mirosław Makowiecki Absolwent UMCS Fizyki Komputerowej Uniwersytetu Marii Curie-Skłodowskiej w Lublinie Email: miroslaw(kropka)makowiecki(małpa)gmail(kropka)pl Dotyczy: książki, do której należy ta strona, oraz w niej zawartych stron i w nich podstron, a także w nich kolumn, wraz z zawartościami. Użytkownika książki, do której należy ta strona, oraz w niej zawartych stron i w nich podstron, a także w nich kolumn, wraz z zawartościami nie zwalnia z odpowiedzialności prawnoautorskiej nieprzeczytanie warunków licencjonowania. Umowa prawna: Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Autor tej książki dołożył wszelką staranność, aby informacje zawarte w książce były poprawne i najwyższej jakości, jednakże nie udzielana jest żadna gwarancja, czy też rękojma. Autor nie jest odpowiedzialny za wykorzystanie informacji zawarte w książce, nawet jeśli wywołaby jakąś szkodę, straty w zyskach, zastoju w prowadzeniu firmy, przedsiębiorstwa lub spółki bądź utraty informacji, niezależnie czy autor (a nawet Wikibooks) został powiadomiony o możliwości wystąpienie szkód. Informacje zawarte w książce mogą być wykorzystane tylko na własną odpowiedzialność.

---

---

Będziemy się tutaj zajmować przybliżonym rozwiązywaniem równań, które dotyczy w sposób szczególny rozwiązań przestępnych. Wiadomo jednak, że z równania algebraiczne stopnia większego niż cztery nie da się w ogólności rozwiązać, tzn. nie istnieją ogólne metody rozwiązywania tego typu równań. Najlepszą i najcenniejszą informacją jest znanie przedziału, w której dana funkcja przyjmuje wartość zero.

Metoda znajdowania pierwiastków metodą połowienia

Mamy sobie równanie f(x)=0, którą to będziemy rozwiązywać metodą połowienia. Załóżmy, że mamy przedział $\langle a;b\rangle \;$, w której funkcja f(x) ma dokładnie jeden pierwiastek, w których na końcach tego przedziału funkcja f(x) przyjmuje przeciwne znaki, tzn. spełniona jest nierówność f(a)f(b)<0. Podany przedział dzielimy na dwie połówki, tzn. na przedziały, które to określamy następującymi przedziałami $\langle a;x_{i}\rangle$ i $\langle x_{i}\;b\rangle \;$. Jeśli w punkcie x₁ funkcja ma pierwiastek, to zakończony jest sposób znajdowania pierwiastków w naszej metodzie połowienia. Jeśli w tym miejscu ta funkcja w punkcie x₁ nie ma pierwiastka, to wybieramy ten podprzedział, w której na końcach iloczyn funkcji wartości na tych końcach maja przeciwne znaki, to w tym przedziale dzielimy ten nasz przedział na dwa podprzedziały, w ten sposób otrzymamy punkt, w której punkt x_i dzieli te przedziały na dwa. Jeśli w tak otrzymanym w punkcie x₂ funkcja f(x) ma pierwiastek, to tą metodą został zakończony sposób liczenia pierwiastka w tej metodzie, a jeśli nie ma, to znów wybieramy mówiąc ogólnie przedział, dla której zachodzi:

$f(x_{i})f(x_{i+1})<0\;$

(3.1)

a podany przedział znów dzielimy na połowę. Ten proces wyznaczania pierwiastków powtarzamy dopóki nie znajdziemy pierwiastka, której dokładność przy każdym kroku jest zwiększana i wynosi:

$|x_{i}-x_{i+1}|={{1} \over {2^{i}}}(b-a)\;$

(3.2)

Reguła falsi

(Rys. 3.1) Ilustracja metody siecznych

Tą metodą wyznaczamy pierwiastki pewnej funkcji f(x), którą tą metodę stosuje się, gdy wartości funkcji w punktach a, i b miały przeciwne znaki, zatem prowadzimy sieczną przechodzącą przez punkty (a,f(a)) i b(b,f(b)), znajdujemy stąd dla jakiej wartości x następuje przecięcie z osią OX. Równanie tej siecznej przestawiamy jako:

$y-f(a)={{f(b)-f(a)} \over {b-a}}(x-a)\;$

(3.3)

Jak powiedzieliśmy wcześniej znajdujemy taką wartość x, dla której w równaniu (3.3) mamy y=0, wtedy dostajemy pierwsze przybliżenie pierwiastka funkcji f(x) w postaci liczby x, które to piszemy wzorem wyznaczając jednocześnie z równości (3.3):

$-{{f(a)} \over {f(b)-f(a)}}(b-a)=x_{1}-a\Rightarrow x_{1}=a-{{f(a)} \over {f(b)-f(a)}}(b-a)\;$

(3.4)

Mając już wyznaczoną wartość x₁ możemy przeprowadzić następną sieczną, którego za miejsce "a' we wzorze podstawiamy x_k a za x₁ podstawiamy x_k+1, w ten sposób otrzymujemy rekurencję, która jest napisana wzorem dla k=1,2,..n:

$x_{0}=a,x_{k+1}=x_{k}-{{f(x_{k})} \over {f(b)-f(x_{k})}}(b-x_{k})\;$

(3.5)

Jeśli dla uproszczenia rozważań będziemy przyjmować f'(x)>0 i f''(x)>0, to można udowodnić, że ciąg (3.5) jest ciągiem rosnącym i zbieżnym do pierwiastka x, której jest rozwiązaniem równania f(x)=0.

Wartość graniczna zespołu przybliżeń

Można udowodnić w przypadku granicznych, gdy n dąży do nieskończoności, to biorąc granicę obu jego stron dostajemy następujący warunek graniczny:

$g=g-{{f(g)} \over {f(b)-f(g)}}(b-g)\;$

(3.6)

W równości (3.6) przyjęliśmy, że zachodzi warunek graniczny dla ciągu x_n, który to zapisujemy wzorem: $g=\lim _{n\rightarrow \infty }x_{n}(a<g<b)\;$, zatem wtedy z wspomnianej równości otrzymujemy od razu f(g)=0.

Oszacowanie błędu bezwzględnego w tym przybliżeniu

Błąd n-tego przybliżenia możemy ocenić korzystając z twierdzenia Lagrange'a, napiszmy:

$f(x_{n})-f(\alpha )=f^{'}(c)(x_{n}-\alpha )\;$

(3.7)

Z równości (3.7) możemy napisać oszacowanie błędu, korzystając z faktu, że liczba α jest pierwiastkiem równania f(x):

$|x_{n}-\alpha |\leq {{|f(x_{n})|} \over {m}}{\mbox{, gdzie: }}m=\inf _{x\in \langle a;\rangle b>}|f^{'}(x)|\;$

(3.8)

Błędy bezwzględne przybliżonej wartości regułą falsi przy kolejnych przybliżeniach wartości miejsca zerowego funkcji f(x)

Załóżmy, że kolejne przybliżenie pierwiastka funkcji f(x), czyli x_k liczymy ze wzoru, do którego będzie nam potrzebne czemu jest równe f(x_k), które to wzór obliczający to wskazane przybliżenie wyznaczamy ze wzoru znanego z własności funkcji liniowych znanej ze szkolnej matematyki:

$0-f(x_{k})={{f(x_{k})-f(b)} \over {x_{k}-b}}(x_{k+1}-a)\;$

(3.9)

Jeśli przyjmować będziemy, że f(α) jest równe zero, a α jest pierwiastkiem tego równana, to wtedy równość (3.9) możemy przedstawić w postaci wzoru:

$f(\alpha )-f(x_{k})={{f(x_{k})-f(b)} \over {x_{k}-b}}(x_{k+1}-x_{k})\;$

(3.10)

Korzystając z twierdzenia Lagrange'a dla prawej i lewej strony równości, wtedy wzór (3.10) możemy przepisać robiąc te podstawienia wynikłe z podanego wcześniej twierdzenie Lagrange'a:

$(\alpha -x_{k})f^{'}(\xi _{k})={{(x_{k}-b)f^{'}({\overline {x}}_{k})} \over {x_{k}-b}}(x_{k+1}-x_{k})\Rightarrow (\alpha -x_{k})f^{'}(\xi _{k})=(x_{k+1}-x_{k})f^{'}({\overline {x}}_{k})\;$

(3.11)

Możemy wykonać potrzebne wymnażania w równości (3.11) i dodać na samym końcu wyraz $-x_{k+1}f^{'}(\xi _{k})\;$, zatem dokonując te wskazane operacje na tym wspomnianym równaniu, otrzymujemy:

$\alpha f^{'}(\xi _{k})-x_{k}f^{'}(\xi _{k})-x_{k+1}f^{'}(\xi _{k})=(x_{k+1}-x_{k})f^{'}({\overline {x}}_{k})-x_{k+1}f^{'}(\xi _{k})\Rightarrow \;$
$(\alpha -x_{k+1})f^{'}(\xi _{k})=(x_{k+1}-x_{k})f^{'}({\overline {x}}_{k})-(x_{k+1}-x_{k})f^{'}(\xi _{k})\Rightarrow \;$
$(\alpha -x_{k+1})f^{'}(\xi _{k})=(x_{k+1}-x_{k})(f^{'}({\overline {x}}_{k})-f^{'}(\xi _{k}))\;$

(3.12)

Po krótkich przekształceniach we wzorze (3.12) możemy dojść do wniosku, że możemy napisać równość, którą przepiszemy ponownie działając wartością bezwzględną na obie jego strony:

$(\alpha -x_{k+1})={{f^{'}({\overline {x}}_{k})-f^{'}(\xi _{k})} \over {f^{'}(\xi _{k})}}(x_{k+1}-x_{k})\Rightarrow |\alpha -x_{k+1}|={{|f^{'}({\overline {x}}_{k})-f^{'}(\xi _{k})|} \over {|f^{'}(\xi _{k})|}}|x_{k+1}-x_{k}|\;$

(3.13)

Jeśli wprowadzimy minimalną wartość funkcji f(x) w naszym przedziale <a,b> i oznaczymy przez m, a maksymalną wartość tej samej funkcji w tym samym przedziale oznaczymy przez M, co te wartości zapisujemy wzorami:

$m=\inf _{x\in \langle a,b\rangle }|f^{'}(x)|\;$

(3.14)

$M=\sup _{x\in \langle a,b\rangle }|f^{'}(x)|\;$

(3.15)

To końcowy wynik zapisany przy tożsamościach (3.14) i (3.15) możemy wykorzystać do końcowych obliczeń zapisanej w punkcie (3.13), zatem w końcowych perypetiach otrzymujemy następującą równość, którą to piszemy wzorem:

$|\alpha -x_{k+1}|\leq {{M-m} \over {m}}|x_{k+1}-x_{k}|\;$

(3.16)

Jeśli dodatkowo założymy, że zachodzi warunek $M\leq 2m\;$, to wtedy równość (3.16) możemy przepisać do postaci:

$|\alpha -x_{k+1}|\leq |x_{k+1}-x_{k}|\;$

(3.17)

Inny wzór na błąd bezwzględny oszacowania wartości dokładnej pierwiastka funkcji f(x)

Oszacowanie zapisane wzorem (3.16) jest oszacowaniem niezbyt dobrym, ponieważ wymaga ona obliczenia wartości kolejnych przybliżeń α, która jest pierwiastkiem funkcji f(x), która wymaga znajomości stałych m i M, a także nie wiadomo jak duża liczba występuje przy czynniku |x_k+1-x_k|, zatem tutaj dokonamy innego przybliżenia wartości dokładnej pierwiastka pierwiastka funkcji f(x). W celu obliczenia wartości błędu bezwzględnego wartości dokładnej α, który jest pierwiastkiem funkcji f(x), którą liczymy w małym otoczeniu tej wartości, zatem pierwszą pochodną funkcji w punkcie x_k+1 możemy policzyć zastępując tą wartość pochodnej ilorazem różnicowym, z którego wyliczymy błąd bezwzględny oszacowania wartości uzyskanej z iteracji x_n+1:

${{f(\alpha )-f(x_{n+1})} \over {\alpha -x_{n+1}}}\simeq f^{'}(x_{n+1})\Rightarrow |\alpha -x_{n+1}|\simeq \left|{{f(x_{n+1})} \over {f^{'}(x_{n+1})}}\right|\simeq \left|{{x_{k+1}-x_{k}} \over {f(x_{k+1})-f(x_{k})}}\right||f(x_{k+1})|\;$

(3.18)

Metoda siecznych

Regułę falsi stosowaliśmy, gdy punkty a i b powinny być takie, by wartości funkcji f(x) policzonych z tychże argumentów nie powinna być mieć tych samych znaków, i to jest właściwy problem reguły falsi. Lepszą metodą jest metoda siecznych, którą to piszemy wzorem uzyskanym z (3.5), w która powstaje po zastąpieniu w nim parametru b przez kolejne przybliżenia pierwiastka funkcji f(x), czyli przez x_n-1, zatem na podstawie tych rozważań możemy podać iteracje, dzięki której będziemy liczyli kolejne przybliżenia x_k pierwiastka α funkcji f(x), mamy:

$x_{n+1}=x_{n}-{{f(x_{n})} \over {f(x_{n})-f(x_{n-1})}}(x_{n}-x_{n-1})\;$

(3.19)

Ta metoda jest znacznie szybsza niż reguła falsi, ale może zdarzyć się, że jeśli początkowe przybliżenia pierwiastka leżą daleko od poszukiwanego pierwiastka, ta metoda może być niezbieżna do tego poszukiwanego pierwiastka. Może zdarzyć się, że według metody (3.19) dokładność różnicy x_n+1-x_n jest takiego samego rzędu co oszacowanie, którego błędem jest obarczona, to następne przybliżenia są mało wiarygodne. Bardzo ważnym kryterium jest, że ciąg wartości funkcji |f(x_k)| stanowią ciąg wartości malejący, w końcowej fazie obliczeń, a jeśli wartości bezwzględne różnic wartości kolejnych wartości przybliżeń są wartościami niemalejącymi w dalszym kroku obliczeń, tzn. zamiast maleć, to szybko rośną, to należy takie obliczenia przerwać i w takim przypadku należy powtórzyć lokalizację pierwiastka zmniejszając zawężenia początkowe przedziały iteracji, tzn. zmniejszamy przedziały, dla którego poszukujemy dane pierwiastki naszej funkcji f(x) w danym przedziałach zmienności funkcji f(x).

Metoda Newtona (stycznych)

(Rys. 3.2)

Przybliżoną wartość pierwiastka możemy obliczyć na przedziale <a,b>, gdy pierwsza i druga pochodna mają stały znak, to wtedy możemy zastosować metodę Newtona, którą także nazywamy metodą stycznych. Polega ona na tym, że prowadzimy styczną do wykresu w danym punkcie funkcji y=f(x), i punkt, w którym ona przecina oś OX nazywamy pierwszym przybliżeniem pierwiastka. Następnym krokiem znając pierwsze przybliżenie pierwiastka, to w punkcie pierwszego przybliżenia możemy przeprowadzić styczną naszej funkcji, i punkt, której ta styczna przecina os OX nazywamy drugiem przybliżeniem pierwiastka. Równanie które opisuje tą właśnie styczną nazywamy równanie, które piszemy wzorem:

$y-f(b)=f'(b)(x-b)\;$

(3.20)

jeśli we wzorze przyjmować będziemy y=0, bo badamy punkt przecięcia stycznej z osią OX, zatem pierwsze przybliżenie naszego pierwiastka nazywamy liczbę, którą opisujemy wzorem:

$x_{1}=b-{{f(b)} \over {f'(b)}}\;$

(3.21)

Dalszym krokiem jest pokazanie, że x₁, leży bliżej α niż b od liczby α, która jest pierwiastkiem równania f(x). Z twierdzenia Taylora możemy napisać tożsamość w postaci wzoru, z którego wyznaczymy zmienną α, która jest miejscem zerowej naszej rozpatrywanej funkcji, czyli zachodzi f(α)=0.

$f(\alpha )=f(b)+f'(b)(\alpha -b)+{{1} \over {2}}f^{''}(c)(\alpha -b)^{2}\Rightarrow \alpha =b-{{f(b)} \over {f'(b)}}-{{1} \over {2}}{{f^{''}(c)} \over {f'(b)}}(\alpha -b)^{2}\;$

(3.22)

Jeśli wykorzystamy (3.21) do ostatecznej równości (3.22), w ten sposób otrzymujemy równość, która jest różnicą pierwiastką α i liczby x₁, którą to ostatecznie piszemy:

$\alpha -x_{1}=-{{1} \over {2}}{{f^{''}(c)} \over {f'(b)}}(\alpha -b)^{2}\leq 0\;$

(3.23)

Z równości (3.23) otrzymaliśmy tożsamość na α-x₁ przy przyjętych założeniach f''(c)>0 i f'(b)>0· Z równości (3.21) możemy otrzymać równość przy dodatnich znakach funkcji i pierwszej pochodnej w punkcie b, stąd dostajemy wniosek:

$x_{1}-b=-{{f(b)} \over {f'(b)}}<0\;$

(3.24)

Stąd z nierówności (3.24) możemy napisać nierówność x₁. Patrząc na rysunek obok dostajemy wniosek, że liczba x₁ przybliża się coraz bliżej α i coraz dalej od liczby b dla funkcji f(x) przy liczeniu przybliżonych wartości pierwiastka α. Jeśli napiszemy z twierdzenia Lagrange'a, którego to przepisz podajemy względem punktu α i x₁ i wiedząc, że punkcie α funkcja f(x) przyjmuje wartość zerową, zatem na podstawie tego możemy napisać:

$f(x_{1})-f(\alpha )=f'(c)(x_{1}-\alpha )\Rightarrow f(x_{1})=f'(c)(x_{1}-c)\;$

(3.25)

Na podstawie końcowej tożsamości (3.25), możemy napisać, że kolejne przybliżenia pierwiastką będą się zbliżały do liczby α, ale wartości funkcji f(x) z tych przybliżonych miejsc zerowych będą miały nadal ten sam znak. Ostateczne równanie z tej n-tej stycznej piszemy wedle schematu:

$y-f(x_{n})=f'(x_{n})(x-x_{n})\;$

(3.26)

Jesli we wzorze (3.26) przyjmować będziemy y=0, to x=x_n+1 będzie n+1 przybliżeniem pierwiastka α, dla której funkcja f(x) przyjmuje wartość funkcji równą zero. Zatem na podstawie tego możemy napisać równość na n+1 na przybliżony pierwiastek α rozważanej funkcji.

$x_{n+1}=x_{n}-{{f(x_{n})} \over {f'(x_{n})}}\;$

(3.27)

Jeśli we wzorze (3.26) przejdziemy do granicy dla n nieskończonego takiego, by zachodziło $\lim _{n\rightarrow \infty }x_{n}=g\;$, zatem na podstawie tego możemy powiedzieć:

$g=g-{{f(g)} \over {f'(g)}}\;$

(3.28)

To z równości (3.28) możemy otrzymać równość f(g)=0, co potwierdza, ze g jest pierwiastkiem funkcji f(x), który jest liczbą α. Błąd n-tego przybliżenia możemy policzyć ze wzoru, który wyprowadziliśmy w punkcie (3.8), który jest również słuszny dla metody stycznych Newtona. Zgodnie z twierdzeniem Taylora możemy napisać równość przy wykorzystaniu równości (3.26), zatem na tej podstawie piszemy:

$f(x_{n})=f\left[x_{n-1}+(x_{n}-x_{n+1})\right]=\;$
$=f(x_{x-1})+f'(x_{n-1})(x_{n}-x_{n-1})+{{1} \over {2}}f^{''}(\xi _{n-1})(x_{n}-x_{n-1})^{2}={{1} \over {2}}f^{''}(\xi _{n-1})(x_{n}-x_{n-1})^{2}\;$

(3.29)

Jeśli napiszemy $M=\sup _{x\in \langle a;b\rangle }|f^{''}(x)|\;$, to końcowy wynik wedle obliczeń (3.28) możemy zapisać:

$|f(x_{n})|\leq {{1} \over {2}}M(x_{n}-x_{n-1})\;$

(3.30)

Jeśli wykorzystamy wzór, który jest również słuszny na metody stycznych, czyli (3.8), to otrzymamy nierówność wynikającą z (3.30):

$|x_{n}-\alpha |m\leq |f(x_{n})|\leq {{1} \over {2}}M(x_{n}-x_{n-1})\Rightarrow |x_{n}-\alpha |\leq {{M} \over {2m}}(x_{n}-x_{n-1})^{2}={{M} \over {2m}}\left({{f(x_{n})} \over {f'(x_{n})}}\right)^{2}\;$

(3.31)

Jeśli przyjmować będziemy tak jak przy regule falsi, że $M\leq 2m\;$, to wtedy nierówność (3.31) przyjmuje postać:

$|\alpha -x_{n}|\simeq \left|{{f(x_{n})} \over {f'(x_{n})}}\right|^{2}\;$

(3.32)

Co pozwala na przerwanie iteracji, jeśli wyniku procedury iteracyjnej błąd bezwzględny kolejnych przybliżonych pierwiastków pewnego y=f(x) jest mniejszy od bardzo małej liczby ε:

$|x_{n+1}-x_{n}|<\epsilon \;$

(3.33)

Poszukiwanie pierwiastków wielomianów o dziedzinie zespolonej

Będziemy opisywać metody poszukiwania miejsc zerowych wielomianów należące do dziedziny zespolonej za wyjątkiem reguły falsi, i to wszystko będziemy robili dla wielomianu, których argument będziemy oznaczali przez "z":

$f(z)=a_{0}z^{n}+a_{1}z^{n-1}+...+a_{n-1}z+a_{n}=0\;$

(3.34)

Znajdowanie liczby miejsc zerowych rzeczywistych dla wielomianu o współczynnikach rzeczywistych

Twierdzenie Sturma

Orientacyjną liczbę miejsc zerowych można uzyskać przez naszkicowanie wykresu funkcji rzeczywistego wielomianu y=f(x). Dokładną liczbę pierwiastków można uzyskać metodą Sturna. Obierzmy sobie ciąg Sturma f₀(x),f₁(x),f₂(x),...,f_p(x), w których poszczególne elementy sa takie, że f₀(x) jest to zwykła rzeczywista funkcja f(x), a funkcja f₁(x) jest to pierwsza pochodna funkcji f(x). A f₂(x) jest to reszta z dzielenia funkcji f₀(x) przez funkcję f₁(x) wzietej ze znakiem przeciwnym, element f₃(x) jest to reszta z dzielenia funkcji f₁(x) przez f₂(x) wziętej ze znakiem przeciwnym. Takie postępowanie powtarzamy, aż uzyskamy wielomian f_p+1(x), który jest tożsamościowo równy zero, wtedy mamy wielomian f_p, który jest największym dzielnikiem wielomianu f(x). Jeśli wielomian f_p jest stopnia k i największy wspólny dzielnik jest liczbą rzeczywistą, i ten wielomian nie ma zer wielokrotnych, to znaczy, że jego miejscem zerowym jest k+1-krotnym miejscem zerowym wielomianu f(x). Oznaczmy przez N(x₀) liczbę zmian znaków ciągu Sturna w punkcie x=x₀. Mając na uwadze wszystko o twierdzeniu Sturna zdefiniujmy twierdzenie Sturna:

Twierdzenie Sturma
Jeśli mamy ciąg Sturma {f_i(x)} dla i=0,1,2,..,p określonego w przedziale (a,b), i zachodzi f₀(a)f₀(b)≠0, to liczba pierwiastków rzeczywistych wielomianu rzeczywistego w tymże przedziale jest równa liczbie N(a)-N(b).

Przy zastosowaniu twierdzenia Sturma otrzymujemy czysto ułamkowe współczynniki, ale ponieważ interesują nas tylko znaki wielomianów, więc należy je pomnożyć przez liczbę naturalna różną od zera. Określmy sobie wielomian f(x)=x³+x²-x-1, to wtedy możemy określić sobie ciąg Sturma:

• f₀(x)=x³+x²-x-1
• f₁(x)=3x²+2x-1
• f₂(x)=x+1

Ale f₃ jest tożsamościowo równy zero, więc to wielomian f(x) ma pierwiastek podwójny równy -1. Podzielmy wielomian f₀(x) przez x+1, to otrzymamy wielomian o pojedynczych pierwiastkach:

• f₀(x)=x²-1
• f₁(x)=2x
• f₂(x)=1

Powyższy wielomian ma trzy pierwiastki, jeden pojedynczy i jeden podwójny pierwiastek. Rozważmy sobie teraz tabelkę zmian znaków dla wielomianu ostatniego f₀(x).

	-∞	+∞	0	+1	-1
f0	+	+	-	0	0
f1	-	+	0	+	-
f2	+	+	+	+	+
N(x)	2	0	1	0	1

Według tablicy zmiany znaków w przedziale nieskończonym wielomian f₀(x) ma N(-∞)-N(∞)=2-0=2 pierwiastków.

Twierdzenie Fouriera

Twierdzenie Sturna chociaż pozwala wyznaczyć dokładnie liczbę miejsc zerowych pierwiastków, to kolejne rachunki przy wyznaczaniu kolejnych miejsc zerowych pierwiastków może nastręczać trudności ze względu na skomplikowane rachunki. Określmy sobie teraz inną metodę liczenia miejsc zerowych, zatem obierzmy sobie ciąg kolejnych pochodnych f(x), f'(x),f''(x),...,f⁽ⁿ⁾(x). A przez M(x₀) oznaczmy liczbę zmian znaków ciągu {f⁽ⁱ⁾(x)} dla i=0,1,2,,n w punkcie x=x₀. Mając to twierdzenie możemy określić twierdzenie Fouriera:

Twierdzenie Fouriera
Jeśli f(x) jest wielomianem stopnia n-tego określonych na przedziale (a,b), gdy zachodzi f(a)f(b)≠0, to liczba miejsc zerowych wielomianu f(x) jest M(a)-M(b) lub jest od niej mniejsza o liczbę parzystą.

Określmy sobie wielomian f(x)=x³-2x²-5x+5, wtedy sobie tworzymy ciąg czterech pochodnych:

• f(x)=x³-2x²-5x+5
• f'(x)=3x²-4x-5
• f''(x)=6x-4
• f'''(x)=0

to tablicę zmiany znaków określamy:

	-∞	+∞	0	1	3
f	-	+	+	-	+
f'	+	+	-	-	+
f''	-	+	-	+	+
f'''	+	+	+	+	+
M(x)	3	0	2	1	0

Na podstawie powyższej tablicy stwierdzamy, że wielomian f(x) ma jeden albo trzy pierwiastki, bo M(-∞)-M(∞)=3. Z warunku M(-∞)-M(1)=1 wynika, że istnieje jeden pierwiastek ujemny, a z M(0)-M(1)=1 wynika, że istnieje jeden pierwiastek z przedziału (0,1), a z M(1)-M(3)=1, stąd wynika, że przedziale (1,3) mamy też jeden pierwiastek, czyli ogólnie wielomian f(x) ma trzy pierwiastki w przedziale nieskończonym.

Twierdzenie Laguerre'a

Weźmy sobie wielomian f(x)=a₀xⁿ+a₁x^n-1+...+a_n-1x+a_n, dla a₀≠0, to wtedy sobie tworzymy ciąg wielomianów:

• f₀(x)=a₀
• f₁(x)=a₀x+a₁
• f₂(x)=a₀x²+a₁x+a₂

 -------------

• f_n=f(x)

Oznaczmy przez liczbę L(x₀) liczbę zmian znaków powyższego ciągu wielomianów {f_k(x)} dla k=0,1,2,..,n w punkcie x=x₀.

Twierdzenie Laguerre'a
Jeśli f(x) jest wielomianem stopnia n określonych na przedziale (a,b), takim, że f(a)f(b)≠0, to liczba miejsc zerowych wielomianu f(x) w tym przedziale jest równa L(a)-L(b) lub jest od tej liczby mniejsza o liczbę parzystą.

Reguła Kartezjusza

Szczególnym przypadkiem twierdzenia Laguerre'a jest reguła Kartezjusza mówiąca, że liczba dodatnich miejsc zerowych wielomianu f(x) jest równa zmianie znaków współczynników a₀,a₁,...,a_n lub od niej jest mniejsza o parzystą liczbę.

Lokalizowanie miejsc zerowych rzeczywistych wielomianów rzeczywistych

Dla nas istotnym problem jest znalezienie przedziału miejsc zerowych, w których mieszczą się miejsca zerowe, w tym celu określmy wielomiany wynikające z wielomianu f(x) przez proste przekształcenie go:

$f_{1}(x)=x^{n}f\left({{1} \over {x}}\right)=0\;$

(3.35)

$f_{2}(x)=f(-x)=0\;$

(3.36)

$f_{3}(x)=x^{n}f\left(-{{1} \over {x}}\right)=0\;$

(3.37)

Dla wielomianów (3.35), (3.36) i (3.37) kresy górne zer dodatnich są R₁,R₂,R₃. Wszystkie dodatnie miejsca zerowe wielomianu f(x) mieszczą się zatem dla przedziału (1/R₁,R), a ujemne w przedziale (-R₂,-1/R₃). Bardzo ważnym twierdzeniem jest twierdzenie Lagrange'a mówiące:

Twierdzenie Lagrange'a
Niech a₀≠0 i a_k będzie pierwszym ujemnym współczynnikiem wielomianu f(x), to wszystkie dodatnie miejsca zerowe tegoż wielomianu są mniejsze niż:

$R=1+{\sqrt[{k}]{{A} \over {|a_{0}|}}}\;$

(3.38)

• gdzie A jest maksimum modułów ujemnych współczynników wielomianu f(x). Jeśli wielomian ma tylko dodatnie współczynniki, to on nie ma miejsc zerowych dodatnich.

Metoda znajdowania przybliżonych miejsc zerowych wielomianu rzeczywistego

Weźmy sobie pod ostrzał wielomian o współczynnikach i argumencie rzeczywistym:

$f(x)=a_{0}x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+..+a_{n}\;$

(3.39)

Gdy wielomian (3.39) podzielimy przez jednomian x-x_j, wtedy wielomian (3.39) z resztą dzielenia R_j piszemy jako:

$f(x)=(x-x_{j})(b_{n}x^{n-1}+b_{1}x^{n-2}+...+b_{n-1})+R_{j}\;$

(3.40)

By stwierdzić jaka jest zależność pomiędzy współczynnikami a_k i b_k, należy w wielomianie (3.40) wykonać mnożenie przez x-x_j:

$f(x)=x(b_{0}x^{n-1}+b_{1}x^{n-2}+...+b_{n-1})-x_{j}((b_{0}x^{n-1}+b_{1}x^{n-2}+...+b_{n-1}))+R_{j}=\;$
$=b_{0}x^{n}+(b_{1}-x_{j}b_{0})x^{n-1}+(b_{2}-x_{j}b_{1})x^{n-2}+..+(b_{k}-x_{j}b_{k-1})x^{n-k}+..-x_{j}b_{n-1}+R_{j}\;$

(3.41)

Zależność pomiędzy współczynnikami możemy wyedukować ze wzoru (3.41) patrząc jednocześnie na wzór (3.39), a także w tej samej linijce podamy wzór na resztę z dzielenia R_j:

$b_{0}=a_{0}\;$

(3.42)

$b_{k}=a_{k}+x_{j}b_{k-1}{\mbox{, dla }}k=1,2,...,n\;$

(3.43)

$R_{j}=b_{n}=a_{n}+x_{j}b_{n-1}\;$

(3.44)

Jeśli powtórnie dokonamy dzielenia wielomianu występującego w nawiasie (3.40) przez wielomian x-x_j, wtedy wielomian f(x) piszemy przy pomocy reszty z dzielenia $R_{j}^{'}\;$ wychodząc od wzoru (3.40) jako wzór:

$f(x)=(x-x_{j})^{2}(c_{0}x^{n-1}+..+c_{n-2})+(x-x_{j})R_{j}^{'}+R_{j}\;$

(3.45)

Patrząc na wzory rekurencyjne (3.42), (3.43) i (3.44) dla wielomianu (3.45), piszemy:

$c_{0}=b_{0}=a_{0}\;$

(3.46)

$c_{k}=b_{k}+x_{j}c_{k-1}{\mbox{ dla }}k=1,2,..,n-1\;$

(3.47)

$R_{j}^{'}=c_{n-1}=b_{n-1}+x_{j}c_{n-2}\;$

(3.48)

Wzory na f(x) (3.41) i (3.45) pozwalają napisać dwie bardzo ważne tożsamości, z których będziemy korzystali, tzn. f(x_j)=R_j i f'(x_j)=R'_j. Przy pomocy metody siecznych (3.19) i metody Newtona (3.27) możemy wyedukować dwa wzory, przy pomocy której będziemy liczyli pierwiastki wielomianu rzeczywistego:

$x_{j+1}=x_{j}-{{R_{j}(x_{j}-x_{j-1})} \over {R_{j}-R_{j-1}}}\;$

(3.49)

$x_{j+1}=x_{j}-{{R_{j}} \over {R_{j}^{'}}}\;$

(3.50)

Umieszczanie zer wielomianów ogólnie zespolonych

Warunki na miejsca zerowe zespolone wielomianów zespolonych

Podamy poniżej kilka twierdzeń pozwalające określić położenie miejsc zerowych zespolonych wielomianów zespolonych.

Twierdzenie Cauchy'ego pierwsze
Niech mamy dwa wielomiany o argumentach zespolonych, który przedstawiamy:

$f(z)=a_{0}z^{n}+a_{1}z^{n-1}+...+a_{n}{\mbox{, }}a_{0}\neq 0\;$

(3.51)

$F(z)=|a_{0}|z^{n}-\sum _{k=1}^{n}|a_{k}|z^{n-k}\;$

(3.52)

Oznaczmy przez α jako jedyne dodatnie miejsce zerowe rzeczywiste wielomianu F(z) (3.52), to miejsca zerowe wielomianu f(z) (3.51), czyli z₁, z₂,...,z_n, spełniają następujące właściwości:

$|z_{k}|\leq \alpha {\mbox{ dla }}k=1,2,...,n\;$

(3.53)

Twierdzenie drugie
Napiszmy wielomian o współczynnikach i argumentach zespolonych:

$f(z)=\sum _{k=0}^{n}a_{k}z^{n-k}{\mbox{, }}a_{0}=1\;$

(3.54)

i określmy przesz β dowolną liczbą rzeczywistą dodatnią i określmy liczbę rzeczywistą γ, którą napiszemy według jego definicji poprzez parametr β:

$\gamma =\max \left({{1} \over {\beta }},\sum _{k=1}^{n}|a_{k}|\beta ^{k-1}\right)\;$

(3.55)

to wtedy wszystkie miejsca zerowe wielomianu (3.51) spełniają nierówność:

$|z_{k}|\leq \gamma {\mbox{, }}k=1,2,..,n\;$

(3.56)

Twierdzenie trzecie
Napiszmy wielomian f(z) o współczynnikach zespolonych i o argumentach zespolonych, którego zerowy współczynnik jest nierówny zero, pisząc go według definicji:

$f(z)=\sum _{k=0}^{n}a_{k}z^{n-k}{\mbox{, }}a_{0}\neq 0\;$

(3.57)

wtedy wszystkie miejsca zerowe wielomianu f(z) (3.57) spełniają nierówność określoną:

$|z_{k}|\leq 1+\max _{1\leq k\leq n}\left|{{a_{k}} \over {a_{0}}}\right|{\mbox{, }}k=1,2,..,n\;$

(3.58)

Twierdzenie czwarte
Moduły wszystkich miejsc zerowych zespolonych wielomianu o współczynnikach rzeczywistych $f(z)=\sum _{k=0}^{n}a_{k}z^{n-k}\;$ spełniają nierówność:

$\min \left({{a_{1}} \over {a_{0}}},{{a_{2}} \over {a_{1}}},...,{{a_{n}} \over {a_{n-1}}}\right)\leq |z_{k}|\leq \max \left({{a_{1}} \over {a_{0}}},{{a_{2}} \over {a_{1}}},...,{{a_{n}} \over {a_{n-1}}}\right)\;$

(3.59)

Twierdzenie piąte
Dla wielomianu o współczynnikach rzeczywistych $f(z)=\sum _{k=0}^{n}a_{k}z^{n-k}\;$, jeśli wszystkie współczynniki spełniają warunek a₀>a₁...>a_n>0, to moduły wszystkich miejsc zerowych są mniejsze niż jeden, a jeśli a_n>a_n-1...>a₀>0, to moduły wszystkich miejsc zerowych są większe niż jeden.

Określmy teraz wielomian zespolony o współczynnikach i argumentach zespolonych:

$f(z)=\sum _{k=0}^{n}a_{k}z^{n-k}=a_{0}z^{n}+a_{1}z^{n-1}+...+a_{0}\;$

(3.60)

Zbudujmy dla niego wielomian, którego argumentem jest odwrotność liczby zespolonej "z" dla wielomianu (3.60), który tak powstały wielomian pomnożymy przez n-tą potęgę z liczby "z", w ten sposób otrzymujemy wielomian po sprzężeniu zespolonym jego współczynników:

$f^{*}(z)=z^{n}{\overline {f}}\left({{1} \over {z}}\right)=\sum _{k=0}^{n}{\overline {a}}_{k}z^{k}={\overline {a}}_{0}+{\overline {a}}_{1}z+...+{\overline {a}}_{n}z^{n}\;$

(3.61)

Tworzymy teraz ciąg wielomianów f₀(z), f₁(z), f₂(z),..., f_n(z), przy czym zerowy element tego ciągu jest taki sam jak funkcja f(z), dla którego chcemy udowodnić, ile jest miejsc zerowych leżących w kole jednostkowym, czyli mamy f₀(z)=f(z). Utwórzmy sobie teraz funkcję $f_{0}^{*}(z)\;$ z funkcji f₀(z) w taki sam sposób w jaki tworzyliśmy funkcję (3.58), i na podstawie jej i funkcji f₀(z) tworzymy funkcję f₁(z) , przy pomocy współczynników z podkreśleniem górnym, które są współczynnikami wielomianu $f_{0}^{*}(z)\;$, i przy pomocy współczynników bez podkreślenia, które są współczynnikami wielomianu f₀(z) przy pomocy schematu:

$f_{1}(z)={\overline {a}}_{n}f_{0}(z)-a_{0}f_{0}^{*}(z)\;$

(3.62)

Możemy stworzyć teraz funkcję $f_{1}^{*}(z)\;$ w taki sam w sposób jaki tworzyliśmy funkcję (3.58), ale tym razem z wielomianu f₁(z). W podobnym sposobem tworzymy funkcję f₂(z) ze współczynników wielomianu f₁(z) i $f_{1}^{*}(z)\;$ i tychże funkcji, czyli według:

$f_{2}(z)={\overline {a}}_{n-1}^{(1)}f_{1}(z)-a_{0}^{(1)}f_{1}^{*}(z)\;$

(3.63)

i w ogólności na podstawie sposobu tworzenia funkcji f₁(z) i f₂(z) tworzymy pewną funkcje o wskaźniku j+1:

$f_{j+1}(z)={\overline {a}}_{n-1}^{(j)}f_{j}(z)-a_{0}f_{j}^{*}(z){\mbox{ dla }}j=0,1,2,..,n-1\;$

(3.64)

Co w ogólności przy sposobie tworzenia funkcji f_j+1(z) (3.64) możemy napisać ją w ogólności:

$f_{j}(z)=\sum _{k=0}^{n-j}a_{k}^{(j)}z^{n-j-k}{\mbox{ dla }}j=0,1,2,..,n\;$

(3.65)

Na podstawie ciągu wielomianów {f_j(z)}, którego elementy są napisane według (3.65), tworzymy ciąg δ_k zbudowanych ze współczynników tych wielomianów, którego elementami są:

$\delta _{j+1}=\left|a_{n-j}^{(j)}\right|^{2}-\left|a_{0}^{(j)}\right|^{2}\;$

(3.66)

i na samym końcu tworzymy ciąg powstałe z wymnożenia k elementów początkowych liczb δ_j (3.66) według:

$P_{k}=\delta _{1}\delta _{2}...\delta _{k}\;$

(3.67)

W ten sposób na samym końcu możemy napisać twierdzenie szóste:

Twierdzenie szóste
Dla wielomianu stopnia n (3.60) tworzymy ciąg liczb sposobem P_k (3.67), których jest s liczb ujemnych i n-s liczb dodatnich, to liczba miejsc zerowych wielomianów mieszczące się wewnątrz koła jednostkowego jest s.

Kryterium Michajłowa

Kryterium Michajłowa
Warunkiem koniecznym i dostatecznym, by wielomian $f(z)=\sum _{k=0}^{n}a_{k}z^{n-k}\;$ o współczynnikach rzeczywistych miał miejsca zerowe o ujemnych częściach rzeczywistych, jest by wektor w płaszczyźnie zespolonej o początku w punkcie (0,0) i o końcu w punkcie f(it) zatoczył kąt nπ/2 przy zmianie t od zera do +∞, przy którym wiadomo, że krzywa f(it) nie może mieć punktów wspólnych z początkiem układu współrzędnych.

Kryterium Routha

Określmy sobie wielomian o współczynnikach a_k i b_k przy pomocy których możemy napisać wielomian o argumentach zespolonych w sposób:

$f(z)=a_{0}z^{n}+b_{0}z^{n-1}+a_{1}z^{n-2}+b_{1}z^{n-3}+...\;$

(3.68)

wtedy określmy sobie współczynniki z alfabetu łacińskiego poczynając od c, które możemy zapisać wraz z odpowiednimi indeksami:

$c_{k}=a_{k+1}-{{a_{0}} \over {b_{0}}}b_{k+1}{\mbox{, }}k=0,1,2,..,r-1{\mbox{, }}b_{0}\neq 0\;$

$d_{k}=b_{k+1}-{{b_{0}} \over {c_{0}}}c_{k+1}{\mbox{, }}k=0,1,2,...,r-1{\mbox{, }}c_{0}\neq 0\;$
$e_{k}=b_{k+1}-{{b_{0}} \over {d_{0}}}d_{k+1}{\mbox{, }}k=0,1,2,...,r-2{\mbox{, }}d_{0}\neq 0\;$

 --------------------------------

(3.69)

Liczby (3.69) ustawmy w tablicy:

$a_{0},a_{1},a_{2},...,a_{r}$

$b_{0},b_{1},b_{2},...,b_{r}$
$c_{0},c_{1},c_{2},...,c_{r-1}$
$d_{0},d_{1},d_{2},...,d_{r-1}$
$e_{0},e_{1},e_{2},...,e_{r-2}$

 --------------------------------

(3.70)

Teraz możemy napisać odpowiednie kryterium dla liczb w tablicy (3.70):

Kryterium Routha
Warunkiem koniecznym i dostatecznym, by wszystkie miejsca zerowe miały części rzeczywiste ujemne dla wielomianu rzeczywistego (3.68), to muszą być elementy pierwszej kolumny (3.70) różne od zera i mieć jednakowy znak.

Kryterium Hurwitza

Kryterium Hurwitza
Warunkiem koniecznym i dostatecznym, by wszystkie miejsca zerowe wielomianu $f(z)=\sum _{k=0}^{n}a_{k}z^{n-k}\;$ o a_n>0 i o współczynnikach rzeczywistych były o ujemnych częściach rzeczywistych, jest by poniższe wyznaczniki miały wartość dodatnią, przy którym wiadomo, że a_j=0 dla j<0.

$D_{1}=a_{n-1}{\mbox{, }}D_{2}={\begin{vmatrix}a_{n-1}&a_{n}\\a_{n-3}&a_{n-2}\end{vmatrix}}{\mbox{, }}D_{3}={\begin{vmatrix}a_{n-1}&a_{n}&0\\a_{n-3}&a_{n-2}&a_{n-1}\\a_{n-5}&a_{n-4}&a_{n-3}\end{vmatrix}}{\mbox{,...,}}\;$
$D_{n}={\begin{vmatrix}a_{n-1}&a_{n}&0&\cdots &0\\a_{n-3}&a_{n-2}&a_{n-1}&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\a_{1-n}&a_{2-n}&a_{3-n}&\cdots &a_{0}\end{vmatrix}}$

(3.71)

Poszukiwanie miejsc zerowych wielomianu zespolonego

Aby znaleźć miejsce zerowe wielomianu zespolonego należy użyć metody siecznych (3.47) lub metody Newtona (3.48), które te metody są zbieżne do jego miejsca zerowego, nawet dla zer zespolonych, nie tylko dla zer rzeczywistych. Wprowadźmy oznaczenia zamiast "x" będziemy oznaczali przez "z", która wraz z częścią rzeczywistą i zespoloną piszemy go:

$z_{i}=x_{i}+jy_{i}\;$

(3.72)

Wprowadźmy oznaczenia współczynników b_k i c_k występujące w (3.40) i (3.45) zapisanych jako liczby zespolone:

$b_{k}=\gamma _{k}+j\delta _{k}\;$

(3.73)

$c_{k}=\epsilon _{k}+j\eta _{k}\;$

(3.74)

Według wzoru (3.42) możemy zapisać γ₀=a₀ i γ₀=0, jeśli podstawimy argument zespolony z_k (3.73), a także za współczynnik (3.74) do (3.43), w wyniku czego otrzymujemy:

$\underbrace {\gamma _{k}+j\delta _{k}} _{b_{k}}=a_{k}+\underbrace {(x_{k}+jy_{k})} _{z_{k}}\underbrace {(\gamma _{k-1}+j\delta _{k-1})} _{b_{k-1}}=a_{k}+(x_{i}\gamma _{k-1}-y_{i}\delta _{i})+j(\gamma _{k-1}y_{k}+\delta _{k-1}x_{k})\;$

(3.75)

Patrząc na wzór (3.72) możemy porównać obie strony tego równania do siebie jej części rzeczywiste i zespolone, w ten sposób otrzymujemy dwa wzory:

$\gamma _{k}=a_{k}+x_{i}y_{k-1}-y_{i}\delta _{k-1}{\mbox{ dla }}k=1,2,..,n\;$

(3.76)

$\delta _{k}=x_{i}\delta _{k-1}+y_{i}\gamma _{k-1}{\mbox{ dla }}k=1,2,..,n\;$

(3.77)

Patrząc na wzór (3.46) możemy napisać, że ε₀=b₀=γ₀ i η₀=0. Wykorzystując wzór (3.43) możemy podobnie liczyć c_k jak w punkcie (3.75) b_k:

$\underbrace {\epsilon _{k}+j\eta _{k}} _{c_{k}}=\gamma _{k}+i\delta _{k}+\underbrace {(x_{k}+jy_{k})} _{z_{k}}\underbrace {(\epsilon _{k-1}+j\eta _{k-1})} _{c_{k-1}}=\;$
$=(\gamma _{k}+x_{k}\epsilon _{k-1}-y_{k}\eta _{k-1})+j(\delta _{k}+x_{k}\eta _{k-1}+\epsilon _{k-1}y_{k})\;$

(3.78)

Oglądając się na obliczenia (3.78) możemy napisać dwie bardzo ważne wzory na ε_k i η_k dla k=1,2,..,n-1:

$\epsilon _{k}=\gamma _{k}+x_{k}\epsilon _{k-1}-y_{k}\eta _{k-1}\;$

(3.79)

$\eta _{k}=\delta _{k}+x_{k}\eta _{k-1}+\epsilon _{k-1}y_{k}\;$

(3.80)

Reszty z dzielenia, tzn. wzory R_i (3.44) i R'_i(3.48) możemy napisać przy pomocy wzorów na b_k (3.73) i c_k (3.74) wedle:

$R_{i}=b_{n}=\gamma _{n}+j\delta _{n}\;$

(3.81)

$R_{i}^{'}=c_{n-1}=\epsilon _{n-1}+j\eta _{n-1}\;$

(3.82)

Mając wzory na metodę stycznych (3.50) możemy podstawić do niego wzór (3.81), a także (3.82), otrzymując:

$\underbrace {x_{i+1}+jy_{i+1}} _{z_{k+1}}=\underbrace {x_{i}+jy_{i}} _{z_{k}}-{{\overbrace {\gamma _{n}+j\delta _{n}} ^{R_{j}}} \over {\underbrace {\epsilon _{n-1}+j\eta _{n-1}} _{R_{j}^{'}}}}=x_{i}+jy_{i}-{{(\gamma _{n}+j\delta _{n})(\epsilon _{n-1}-j\eta _{n-1})} \over {(\epsilon _{n-1}+j\eta _{n-1})(\epsilon _{n-1}-j\eta _{n-1})}}=\;$
$=x_{i}+jy_{i}-{{(\gamma _{n}\epsilon _{n-1}+\delta _{n}\eta _{n-1})+j(-\gamma _{n}\eta _{n-1}+\epsilon _{n-1}\delta _{n})} \over {\epsilon _{n-1}^{2}+\eta _{n-1}^{2}}}\;$

(3.83)

Patrząc na wzór (3.82) możemy napisać dwie tożsamości na część rzeczywistą x_k+1 i urojoną y_k+1 liczby zespolonej z_k+1 wedle:

$x_{i+1}=x_{i}-{{\gamma _{n}\epsilon _{n-1}+\delta _{n}\eta _{n-1}} \over {\epsilon _{n-1}^{2}+\eta _{n-1}^{2}}}\;$

(3.84)

$y_{i+1}=y_{i}-{{\delta _{n}\epsilon _{n-1}-\gamma _{n}\eta _{n-1}} \over {\epsilon _{n-1}^{2}+\eta _{n-1}^{2}}}\;$

(3.85)

Wprowadzenie do układów równań nieliniowych

Szukamy takiego rozwiązania $\mathbf {\alpha } \in \mathbf {R} ^{n}\;$, dla którego odwzorowanie $\mathbf {F} :\mathbf {R} ^{n}\rightarrow \mathbf {R} ^{n}\;$ przyjmuje wartość zero $\mathbf {F} (\alpha )=0\;$. Jeśli szczególnym odwzorowaniem jest funkcja afiniczna $\mathbf {F} (\mathbf {x} )=\mathbf {A} \mathbf {x} -\mathbf {b} \;$, to szukamy rozwiązania $\mathbf {A} \mathbf {x} =\mathbf {b} \;$, gdzie $\mathbf {x} \;$ jest wektorem szukanych wielkości, a $\mathbf {b} \;$ jest wektorem wyrazów wolnych. W obliczeniach numerycznych będziemy szukali ciągu wektorów $\mathbf {x} ^{(0)},\mathbf {x} ^{(1)},...$, które są zbieżne do wartości $\mathbf {\alpha } \;$, który jest rozwiązaniem równania $\mathbf {F} (\mathbf {\alpha } )=0\;$. Zbudujmy odwzorowanie $\mathbf {x} ^{(i)}=G(\mathbf {x} ^{(i-1)},\mathbf {x} ^{(i-2)}...\mathbf {x} ^{(i-p)})\;$, to takie odwzorowanie nazywamy metodą stacjonarną p-punktową, jeśli mamy w szczególnym przypadku $\mathbf {x} ^{(i)}=G(\mathbf {x} ^{i-1})\;$, to tą metodę nazywamy stacjonarną. Jesli operator G ulega modyfikacją podczas iteracji, to taka metodę nazywamy niestacjonarną lub metodą zmiennego operatora.

Definicja Ostrowskiego
Napiszmy odwzorowanie $G:\mathbf {D} \in \mathbf {R} ^{n}\times \mathbf {R} ^{n}\times ...\times \mathbf {R} ^{n}\rightarrow \mathbf {R} ^{n}\;$ i określmy tzw. punkt przyciągania metody iteracyjnej, jeśli mamy takie otoczenie U_α naszego punktu, że zbierając punkty $\mathbf {x} ^{(-p+1)},\mathbf {x} ^{(-p+2)},\mathbf {x} ^{-p+3},...,\mathbf {x} ^{(0)}\;$, co z tego otoczenia uzyskamy ciąg punktów dążącej do wektora $\mathbf {\alpha } \;$, tzn. ciąg $\mathbf {x} ^{(1)},\mathbf {x} ^{(2)},...\in \mathbf {D} \;$, który jest zbieżny do wektora $\mathbf {\alpha } \;$, które największe z tych otoczeń nazywamy obszarem przeciągania punktu $\mathbf {x} \;$ w n-wymiarowej przestrzeni.

Lemat
Niech mamy odwzorowanie $G:\mathbf {D} \in \mathbf {R} ^{n}\rightarrow \mathbf {R} ^{n}\;$, jeśli istnieje takie c<1, dla którego zachodzi:

$||\mathbf {G} \mathbf {x} -\mathbf {\alpha } ||<c||\mathbf {x} -\mathbf {\alpha } ||\;$

(3.86)

dla której istnieje kula $\mathbf {K} (\mathbf {\alpha } ,r)\subset \mathbf {D} \;$, to ciąg punktów $\mathbf {x} ^{(0)},\mathbf {x} ^{(1)},...\;$ jest zawarty wewnątrz tej kuli. Ta zbieżność jest conaj mniej liniowa, bo według $\mathbf {x} ^{(i+1)}=\mathbf {G} (\mathbf {x} ^{(i)})\;$ zachodzi $||\mathbf {x} ^{(i+1)}-\mathbf {\alpha } ||\leq c||\mathbf {x} ^{(i)}-\mathbf {\alpha } ||\;$ dla "i" naturalnego z zerem.

Definicja
Niech mamy odwzorowanie $G:\mathbf {R} ^{n}\rightarrow \mathbf {R} ^{n}\;$, to różniczkowanie w sensie Fricheta w punkcie $\mathbf {x} \;$ nazywamy odwzorowanie dla którego istnieje macierz $\mathbf {A} :\mathbf {R} ^{n}\rightarrow \mathbf {R} ^{n}\;$, dla której zachodzi:

$\lim _{h\rightarrow 0}{{||G(\mathbf {x} +\mathbf {h} )-G(\mathbf {x} )-\mathbf {A} \mathbf {h} ||} \over {||\mathbf {h} ||}}=0\;$

(3.87)

wtedy macierz $\mathbf {A} \;$ nazywamy pochodną odwzorowania G w punkcie $\mathbf {x} \;$ i oznaczać je będziemy przez $G^{'}(\mathbf {x} )\;$.

Twierdzenie Ostrowskiego
Weźmy sobie pochodną Frecheta zwana inaczej F-pochodną odwzorowania $G:\mathbf {R} ^{n}\rightarrow \mathbf {R} ^{n}\;$ w punkcie $\mathbf {\alpha } \;$, w którym F-pochodna ma promień spektralny równy $\varphi (G'(\mathbf {\alpha } ))=\beta \;$, oraz oczywiście zachodzi $G(\mathbf {\alpha } )=\mathbf {\alpha } \;$, to punkt $\mathbf {\alpha } \;$ jest punktem przyciągania metody iteracyjnej $\mathbf {x} ^{(i+1)}=G(\mathbf {x} ^{(i)})\;$, z którego uzyskujemy kolejne przybliżenia wektora $\mathbf {\alpha } \;$.

Dowód twierdzenia Ostrowskiego
Ponad wszelką wątpliwość można napisać $G^{'}(\alpha )\leq \beta +\epsilon \;$ dla promienia spektralnego β. Z określenia pochodnej Frecheta możemy napisać, że istnieje kula $\mathbf {K} (\mathbf {\alpha } ,r)\;$ taka, że zachodzi:

$||G(\mathbf {x} )-G(\mathbf {\alpha } )-G^{'}(\mathbf {\alpha } )(\mathbf {x} -\mathbf {\alpha } )||\leq \epsilon ||\mathbf {x} -\mathbf {\alpha } ||\;$

(3.88)

dla $\mathbf {x} \;$ należącego do kuli. Wtedy na podstawie tychże warunków możemy napisać

$||G(\mathbf {x} )-\mathbf {\alpha } ||=||G(\mathbf {x} )-\mathbf {\alpha } -G^{'}(\mathbf {\alpha } )(\mathbf {x} -\mathbf {\alpha } )+G^{'}(\mathbf {\alpha } )(\mathbf {x} -\mathbf {\alpha } )||\leq \;$
$\leq ||G^{'}(\mathbf {\alpha } )(\mathbf {x} -\mathbf {\alpha } )||+\epsilon ||\mathbf {x} -\mathbf {\alpha } ||\leq (\beta +2\epsilon )||\mathbf {x} -\mathbf {\alpha } ||\;$

(3.89)

wtedy możemy wybrać ε dostatecznie małe, by zachodziło β+2ε<1, co stąd wynika, że ciąg generowany przez funkcję wektorową $\mathbf {x} ^{(i)}=G(\mathbf {x} ^{(i)})\;$ jest ciągiem zbieżnym do wektora $\mathbf {\alpha } \;$.

Metoda Newtona a rozwiązywanie układu równań wielu zmiennych

Twierdzenie pierwsze
Niech istnieje F-pochodna funkcji wektorowej $F(\mathbf {x} )\;$ zwarta w pewnym otoczeniu $\mathbf {K} (\mathbf {\alpha } ,r)\;$ taki, że wektor $\mathbf {\alpha } \;$ spełnia równanie $F(\mathbf {\alpha } )=0\;$ i w punkcie $\mathbf {\alpha } \;$ jest nieosobliwa, wtedy punkt $\mathbf {\alpha } \;$ nazywamy punktem przyciągania metody iteracyjnej:

$\mathbf {x} ^{(i+1)}=\mathbf {x} ^{(i)}-[F'(\mathbf {x} ^{(i)})]^{-1}F(\mathbf {x} ^{(i)})\;$

(3.90)

Dowód twierdzenia pierwszego
Z warunku nieosobliwości F-pochodnej funkcji wektorowej $F(\mathbf {x} )\;$ możemy napisać funkcję:

$G(\mathbf {x} )=\mathbf {x} -[F'(\mathbf {x} )]^{-1}F(\mathbf {x} )\;$

(3.91)

dla której pochodna powyższej funkcji w punkcie $\mathbf {\alpha } \;$ jest równa zero, zatem z twierdzenie Ostrowskiego podaną w poprzednim rozdziale istnieje metoda iteracyjna (3.90), która pozwala wyliczyć kolejne przybliżenia rozwiązania równania $F(\mathbf {x} )=0\;$, czyli kolejne przybliżenia rozwiązania $\mathbf {\alpha } \;$.

Za każdym razem w metodzie Newtona należy liczyć F-pochodną funkcji $F^{'}(\mathbf {x} )\;$, i jego odwrotność, a także wartości funkcji $F(\mathbf {x} )\;$, co jest szczególnym utrudnieniem tejże metody, ale należy pamiętać, że ta metoda jest szybko zbieżna, w tym celu napiszmy twierdzenie drugie.

Twierdzenie drugie
Jeśli odwzorowanie spełnia wszystkie warunki twierdzenia Ostrowskiego podanego w poprzednim rozdziale, i ciągłość funkcji $F'(\mathbf {x} )\;$ w punkcie $\mathbf {\alpha } \;$ jest typu Höldera, tzn. spełnia warunek:

$||F^{'}(\mathbf {x} )-F^{'}(\mathbf {\alpha } )||\leq H||\mathbf {x} -\mathbf {\alpha } ||^{p}\;$

(3.92)

to wtedy jest spełniony warunek:

$||\mathbf {x} ^{(i+1)}-\mathbf {\alpha } ||\leq C||\mathbf {x} ^{(i)}-\mathbf {\alpha } ||^{p+1}{\mbox{ gdzie: }}C=4H||F^{'}(\mathbf {\alpha } )^{-1}||\;$

(3.93)

Według powyższego twierdzenia zbieżność metody Newtona jest bardzo szybka, bo bowiem można napisać:

${{||\mathbf {x} ^{(i+1)}-\mathbf {\alpha } ||} \over {||\mathbf {x} ^{(i)}-\mathbf {\alpha } ||}}\leq C||\mathbf {x} ^{(i)}-\mathbf {\alpha } ||^{p}\;$

(3.94)

Widzimy, że według (3.94) w ciągu wektorów $\mathbf {x} ^{(i)}\;$, w których odległość pomiędzy nimi dąży do zero wraz ze wzrastającym "i". W szczególnym przypadku, gdy mamy p=2, to wtedy mamy zbieżność kwadratową, tzn. zachodzi:

$||\mathbf {x} ^{(i+1)}-\mathbf {\alpha } ||\leq C||\mathbf {x} ^{(i)}-\mathbf {\alpha } ||^{2}\;$

(3.95)

Metoda kolejnych poprawek trójmianu kwadratowego - metoda Bairstowa

Weźmy sobie wielomian f(z), którym wszystkie współczynniki oznaczmy przez a_k, w którym przy najwyższej potędze jest a₀ i wskaźnik wzrasta wraz z maleniem wykładnika potęgi przy z^k, który dzielimy przez trójmian kwadratowy x²+p_iz+q_i, w ten sposób otrzymujemy wynik wraz z resztą z dzielenia równą R_iz+S_i, zatem na podstawie tego wielomian f(x) zapisujemy:

$f(x)=(z^{2}+p_{i}z+q_{i})(b_{0}z^{n-2}+b_{1}z^{n-3}+...+b_{n-2})+R_{i}z+S_{i}\;$

(3.96)

Mnożenie występujące w pierwszym składniku wykonujemy, otrzymujemy:

$f(x)=b_{0}z^{n}+b_{1}z^{n-1}+...+b_{n-2}z^{2}+p_{i}z(b_{0}z^{n-2}+b_{1}z^{n-3}+...+b_{n-2})+\;$
$+q_{i}(b_{0}z^{n-2}+b_{1}z^{n-3}+...+b_{n-2})+R_{i}z+S_{i}=\;$
$=b_{0}z^{n}+(b_{1}+p_{i}b_{0})z^{n-1}+(b_{2}+p_{i}b_{1}+q_{i}b_{0})z^{n-2}+...+(b_{k}+p_{i}b_{k-1}+q_{i}b_{k-2})z^{n-k}+....+\;$
$+(p_{i}b_{n-2}+q_{i}b_{n-3})z+q_{i}b_{n-2}+R_{i}z+S_{i}\;$

(3.97)

Wiedząc, że początkowe współczynniki wielomianu f(x) oznaczmy przez a_k, wtedy iteracyjne wzory na b_k na podstawie (3.87) wyrażamy poprzez dwa wzory:

$b_{0}=a_{0}\;$

(3.98)

$b_{k}=a_{k}-p_{i}b_{k-1}-q_{i}b_{n-2}{\mbox{ dla }}k=1,2,..,n\;$

(3.99)

Wzory na współczynniki R_i i S_i na podstawie (3.97) są:

$R_{i}=a_{n-1}-p_{i}b_{n-2}-q_{i}b_{n-3}\equiv b_{n-1}\;$

(3.100)

$S_{i}=a_{n}-q_{i}b_{n-2}\equiv a_{n}-p_{i}b_{n-1}-q_{i}b_{n-2}+p_{i}b_{n-1}\equiv b_{n}+p_{i}b_{n-1}\;$

(3.101)

Jeszcze raz dzielimy przez ten sam trójmian kwadratowy występujący we wielomianie przedstawionym w punkcie (3.96), otrzymujemy:

$f(z)=(z^{2}+p_{i}z+q_{i})^{2}(c_{0}z^{n-4}+c_{1}z^{n-3}+...+c_{n-4})+(R_{i}^{'}z+S_{i}^{'})(z^{2}+p_{i}z+q_{i})+R_{i}z+S_{i}\;$

(3.102)

Patrząc na wzory (3.96), (3.102) otrzymujemy wzory na współczynniki c_k dla k=1,2,..,n-2 zamieniając a_k na b_k i b_k na c_k:

$c_{0}=b_{0}\;$

(3.103)

$c_{k}=b_{k}-p_{i}c_{k-1}-q_{i}c_{k-2}\;$

(3.104)

A współczynniki R'_i i S'_i wedle (3.100) i (3.101) możemy napisać zamieniając a_k na b_k i b_k na c_k:

$R_{i}^{'}=b_{n-3}-p_{i}c_{n-4}-q_{i}c_{n-5}\equiv c_{n-3}\;$

(3.105)

$S_{i}^{'}=b_{n-2}-q_{i}c_{n-4}\equiv c_{n-2}+p_{k}c_{n-3}\;$

(3.106)

Mamy znaleźć takie p_i i q_i, by w wielomianie (3.96) parametry R_i i S_i w granicy dążyły do zera, zatem najpierw policzmy pierwsze pochodne cząstkową wyrazów b_k względem p_i i q_i, wtedy:

${{\partial b_{1}} \over {\partial p_{k}}}=-b_{0}-p_{k}{{\partial b_{0}} \over {\partial p_{k}}}=-b_{0}=-c_{0}\;$

${{\partial b_{2}} \over {\partial p_{k}}}=-b_{1}-p_{k}{{\partial b_{1}} \over {\partial p_{k}}}=-b_{1}-p_{k}(-c_{0})=-b_{1}+p_{k}c_{0}=-c_{1}\;$
${{\partial b_{3}} \over {\partial p_{k}}}=-b_{2}-p_{k}{{\partial b_{2}} \over {\partial p}}-q_{k}{{\partial b_{1}} \over {\partial p}}=-b_{2}+p_{k}c_{1}+q_{k}c_{0}=-c_{2}\;$
 -----------------------
${{\partial b_{k}} \over {\partial p_{k}}}=-b_{k-1}-p_{k}c_{k-2}+qc_{k-3}=-c_{k-1}\;$
${{\partial b_{1}} \over {\partial q_{k}}}=-p_{k}{{\partial b_{0}} \over {\partial q}}=0\;$
${{\partial b_{2}} \over {\partial q_{k}}}=-p_{k}{{\partial b_{1}} \over {\partial q}}-b_{0}-q_{k}{{\partial b_{0}} \over {\partial q}}=-b_{0}=-c_{0}\;$
${{\partial b_{3}} \over {\partial q_{k}}}=-p_{k}{{\partial b_{2}} \over {\partial q}}-b_{1}-q_{k}{{\partial b_{1}} \over {\partial q_{k}}}=-p_{k}(-c_{0})-b_{1}=p_{k}c_{0}-(c_{1}+p_{k}c_{0})=-c_{1}\;$
 -------

${{\partial b_{k}} \over {\partial q_{k}}}=-c_{k-2}\;$

(3.107)

Policzmy teraz F-pochodną funkcji wektorowej składającej się z funkcji R_i (3.100) i S_i (3.101):

$F'(p_{k},q_{k})={\begin{bmatrix}{{\partial R_{k}} \over {\partial p_{k}}}&{{\partial R_{k}} \over {\partial q_{k}}}\\{{\partial S_{k}} \over {\partial p_{k}}}&{{\partial R_{k}} \over {\partial S_{k}}}\end{bmatrix}}={\begin{bmatrix}-c_{n-2}&-c_{n-3}\\-c_{n-1}+b_{n-1}-p_{k}c_{n-2}&-c_{n-2}-p_{k}c_{n-3}\end{bmatrix}}=\;$
$={\begin{bmatrix}-c_{n-2}&-c_{n-3}\\-c_{n-1}+c_{n-1}+pc_{n-2}+q_{k}c_{n-3}-p_{k}c_{n-2}&-c_{n-2}-p_{k}c_{n-3}\end{bmatrix}}={\begin{bmatrix}-c_{n-2}&-c_{n-3}\\q_{k}c_{n-3}&-c_{n-2}-p_{k}c_{n-3}\end{bmatrix}}\;$

(3.108)

Wyznaczmy teraz wyznacznik macierzy F'(p_k,q_k) (3.108):

$\operatorname {det} F^{'}(p_{k},q_{k})=c_{n-2}^{2}+pc_{n-2}c_{n-3}+q_{k}c_{n-3}^{2}=c_{n-2}^{2}+c_{n-3}\left(\underbrace {p_{k}c_{n-2}+q_{k}c_{n-3}} _{r}\right)=c_{n-2}^{2}+c_{n-3}r\;$

(3.109)

Wyznaczmy teraz elementy odwrotności macierzy (3.108) z dokładnością do pewnego czynnika, tzn. odwrotność wyrazu detF'(p_k,q_k), który pomnożymy jednocześnie przez wektor pionowy składająca się z R_k (3.100) i S_k (3.101):

$\underbrace {\begin{bmatrix}-c_{n-2}-p_{k}c_{n-3}&c_{n-3}\\-q_{k}c_{n-3}&-c_{n-2}\end{bmatrix}} _{\operatorname {det} F^{'}(p_{k},q_{k})F^{'}(p_{k},q_{k})^{-1}}{\begin{bmatrix}b_{n-1}\\b_{n}+p_{k}b_{n-1}\end{bmatrix}}=\;$
$={\begin{bmatrix}-c_{n-2}b_{n-1}-p_{k}c_{n-3}b_{n-1}+c_{n-3}b_{n}+p_{k}c_{k-3}b_{n-1}\\-q_{k}c_{n-3}b_{n-1}-c_{k-2}b_{n}-p_{k}c_{k-2}b_{n-1}\end{bmatrix}}=\;$
$={\begin{bmatrix}c_{n-3}b_{n}-c_{n-2}b_{n-1}\\-b_{n-1}(p_{k}c_{n-2}+q_{k}c_{n-3})-c_{n-2}b_{n}\end{bmatrix}}$

(3.110)

Stosując dwuwymiarową metodę Newtona (3.90) możemy powiedzieć stosując obliczenia napisane w punkcie (3.110) uwzględniając policzony wyznacznik macierzy detF'(p_k,q_k) policzonej w punkcie (3.109):

${\begin{bmatrix}p_{k+1}\\q_{k+1}\end{bmatrix}}={\begin{bmatrix}p_{k}\\q_{k}\end{bmatrix}}-{{1} \over {c_{n-2}^{2}+c_{n-3}\left(p_{k}c_{n-2}+q_{k}c_{n-3}\right)}}{\begin{bmatrix}c_{n-3}b_{n}-c_{n-2}b_{n-1}\\-b_{n-1}(p_{k}c_{n-2}+q_{k}c_{n-3})-c_{n-2}b_{n}\end{bmatrix}}\;$

(3.111)

Z równości macierzowej (3.111) możemy wyedukować dwie bardzo ważne tożsamości w metodze Bairstowa na iterację współczynników p_k i q_k:

$p_{k+1}=p_{k}-{{c_{n-3}b_{n}-c_{n-2}b_{n-1}} \over {c_{n-2}^{2}+c_{n-3}r}}\;$ (3.112)

$q_{k+1}=q_{k}-{{-b_{n-1}r-c_{n-2}b_{n}} \over {c_{n-2}^{2}+c_{n-3}r}}\;$ (3.113)

Metoda siecznych jako metoda n+1 punktowa

Metoda ta polega na odwzorowaniu liniowym (afinicznym) funkcji $f(\mathbf {y} )\;$ w odwzorowaniu $F:\mathbf {R} ^{n}\rightarrow \mathbf {R} ^{n}\;$, tzn.:

$F(\mathbf {y} ^{(i)})=A\mathbf {y} ^{(i)}+\mathbf {b} {\mbox{ dla }}j=0,1,2,..,n\;$

(3.114)

Oznaczmy przez $_{\Delta \mathbf {Y} }\;$ jako różnice elementów argumentów (3.114) o kolumnach $\mathbf {y} ^{(1)}-\mathbf {y} ^{(0)}\;$, $\mathbf {y} ^{(2)}-\mathbf {y} ^{(1)}\;$,..., a przez $\Delta \mathbf {F} \;$ o kolumnach $F(\mathbf {y} ^{(1)})-F(\mathbf {y} ^{(0)})\;$, $F(\mathbf {y} ^{(2)})-F(\mathbf {y} ^{(1)})\;$,..., wtedy możemy napisać:

$\Delta \mathbf {F} =\mathbf {A} \cdot \Delta \mathbf {Y} \;$

(3.115)

Szunanym punktem rozwiązania $\mathbf {A} \mathbf {x} +\mathbf {b} =0\;$ przy wykorzystaniu wzoru (3.114) jest rozwiązanie:

$\mathbf {x} =-\mathbf {A} ^{-1}\mathbf {b} =-\mathbf {A} ^{-1}\left(F(\mathbf {y} -\mathbf {A} \mathbf {y} \right)=\mathbf {y} -\mathbf {A} ^{-1}F(\mathbf {y} )\;$

(3.116)

Jeśli zastosujemy wzór (3.115) do tożsamości (3.116) podstawiając za macierz $\mathbf {A} \;$, wtedy kolejne przybliżenie miejsca zerowego funkcji $F(\mathbf {x} )\;$ możemy napisać przyjmując we wspomnianym wzorze jako $\mathbf {x} ^{(i)}\;$:

$\mathbf {x} ^{(i+1)}=\mathbf {x} ^{(i)}-\Delta \mathbf {Y} ^{(i)}[\Delta F^{(i)}]^{-1}F(\mathbf {x} ^{(i)})\;$

(3.117)

W powyższym odwzorowaniu wybieramy n+1 punktów $\mathbf {x} ^{(-n)}\;$, $\mathbf {x} ^{(-n+1)}\;$,..,$\mathbf {x} ^{(0)}\;$, wtedy obliczamy kolejno macierze $\Delta \mathbf {F} ^{(i)}\;$ i $\Delta \mathbf {Y} ^{(i)}\;$, oczywiście przyjmując w takim razie:

$\mathbf {y} ^{(0)}=\mathbf {x} ^{(i-n)}{\mbox{, }}\mathbf {y} ^{(1)}=\mathbf {x} ^{(i-n+1)}{\mbox{, }}...{\mbox{, }}\mathbf {y} ^{(n)}=\mathbf {x} ^{(i)}\;$

(3.118)

Metodę (3.117) nazywamy n+1 punktową metodą siecznych, ponieważ do wyznaczania kolejno punktów $\mathbf {x} ^{(0)}\;$, $\mathbf {x} ^{(1)}\;$,... potrzebne jest n+1 poprzednich punktów i wartości odwzorowania obiektu F w tychże punktach, przy czym należy pamiętać, że macierz $\Delta \mathbf {F} ^{(i)}\;$ musi być macierzą niesosobliwą, tzn. jego wyznacznik nie powinien być równy zero. Metoda Newtona (3.90) sprowadza się do metody dyskretnej siecznych przez proste zastąpienie kolejnych kolummn macierzy F-pochodnej przez:

$\left[{{F(\mathbf {x} ^{(i)}+h\mathbf {e} ^{(1))})} \over {h}},...,{{F(\mathbf {x} ^{(i)}+h\mathbf {e} ^{(n)})} \over {h}}\right]\;$

(3.119)

W powyższym, wzorze przyjęto, że mamy n+1 punktów, tzn. $\mathbf {x} ^{(i)}{\mbox{, }}\mathbf {x} ^{(i-1)}{\mbox{,..., }}\mathbf {x} ^{(i-n)}\;$, wtedy przyjmujemy $\mathbf {y} ^{(n)}=\mathbf {x} ^{(i)}\;$, a także możemy napisać brakujące punkty $\mathbf {y} ^{(n-1)},...,\mathbf {y} ^{(0)}\;$,. wtedy te punkty dobieramy na w sposób:

$\mathbf {y} ^{(n-j)}=\mathbf {x} ^{(i)}+h\mathbf {e} ^{(i)}\;$

(3.120)

i dlatego we wzorze (3.119) argumenty są określone wzorem (3.120). Jeśli macierz $\mathbf {B} \;$ jest macierzą osobliwą, to macierz $\Delta \mathbf {F} =\mathbf {B} \Delta \mathbf {Y} \;$ w odwzorowaniu ${F}(\mathbf {x} )=\mathbf {B} \mathbf {x} +\mathbf {c} \;$ jest również macierzą osobliwą, wtedy stosowanie metody (3.117) (metody siecznych) nie ma sensu, wtedy metoda siecznych jest stosowana przy założeniu dodatkowych warunków warunkujących niezawodność tejże metody.

Poszukiwanie wartości minimalnej funkcji jednej zmiennej

Aby znaleźć wartość funkcji w odwzorowaniu $f:\mathbf {R} ^{1}\rightarrow \mathbf {R} ^{1}\;$ należy znaleźć miejsca zerowe pochodnej funkcji f(x), ale może się zdarzyć, że policzenie pochodnej funkcji jest kłopotliwe, lub nawet niemożliwe, że względu na nieznajomość funkcji obiegającej pewne punkty w przedziale <a,b>, w tym celu zdefiniujmy lemat, dla której funkcja w przedziale (a,α) jest funkcją malejącą, a dla (α,b) jest funkcją rosnąca:

Lemat
W celu zlokalizowania punktu α w przedziale <a,b>, należy policzyć dwie wartości funkcji dla dwóch argumentów w tymże przedziale

Dowód powyższego twierdzenia
Weźmy dwa dowolne punktu t₁ i t₂, takie, że spełniony jest warunek a<t₁<t₂<b, wtedy jeśli jest spełniony warunek f(t₁)≤f(t₂) to minimum funkcji leży w przedziale α∈<α,t₂>, a jeśli f(t₁)>f(t₂), to minimum funkcji f(t) leży w przedziale α∈<t₁,b>

Dwie metody podziału na równe przedziały

Będziemy szukali minimum funkcji przy przedziałach dążących do zera powstająca w wyniku podziału na coraz mniejsze przedziały w wyniku kolejnych kroków, wtedy w wyniku twierdzenia Cantora w przypadku granicznym punkty a⁽ⁱ⁾ i b⁽ⁱ⁾ dążą do α.

Podział na trzy równe części w wyniku kolejnych przedziałów w wyniku iteracji

Wybierzmy sobie dwa punkty, które należą do przedziału <a,b>, które przedstawimy w zależności od liczb a i b:

$t_{1}^{(i)}={{2} \over {3}}a+{{1} \over {3}}b\;$

(3.121)

$t_{2}^{(i)}={{1} \over {3}}a+{{2} \over {3}}b\;$

(3.122)

W wyniku iteracji każdy kolejny przedział w zależności od przedziału poprzedniego jest mniejszy 3/2 razy, to wyniku iteracji przy I-tej iteracji końcowy przedział jest krótszy (3/2)^I razy w 2I obliczeniach wartości funkcji, i wyniku iteracji końcowy przedział ma długość nie większą niż:

$b-a=\left({{2} \over {3}}\right)^{I}(b^{(0)}-a^{(0)})\;$

(3.123)

Aby uzasadnić powyższy wzór to dla I=1 można go uzyskać odejmując od (3.122) liczbę "a" lub od b liczbę (3.121), dalej wyniku czego uzyskujemy wzór iteracyjny i w zależności "i", i wyniku czego po rozwiązaniu iteracji uzyskujemy wzór (3.123).

Podział na cztery równe części wyniku kolejnych podziałów w wyniku iteracji - metoda połowienia

W przedziale pomiędzy punktami "a" i "b" wybierzmy trzy kolejne punkty podziału, w którym będziemy liczyli wartość funkcji:

$t_{1}^{(i)}={{3} \over {4}}a+{{1} \over {4}}b\;$

(3.124)

$t_{2}^{(i)}={{1} \over {2}}a+{{1} \over {2}}b\;$

(3.125)

$t_{3}^{(i)}={{1} \over {4}}a+{{3} \over {4}}b\;$

(3.126)

Wyniku kolejnych i-tej iteracji końcowy przedział końcowy przedział ma długość nie większą niż:

$b-a=\left({{1} \over {2}}\right)^{I}(b^{(0)}-a^{(0)})\;$

(3.127)

uzyskamy to w wyniku 2I+1 obliczeniach wartości w I iteracjach. Metoda połowienia dzieli podany przedział na cztery części, a metoda podziału na trzy części, i wyniku czego można powiedzieć, ze metoda połowienia jest metodą bardziej efektywną, bo metoda podziału dzieli przedziały na większe elementy niż metoda połowienia przy tym samym kroku iteracji, bo ta ostatnia dzieli jeszcze na mniejsza części niż ta metoda ta przedostatnia przy tej samej ilości iteracji.

Metoda Johnsona optymalnych podziałów

Do tej metody korzystamy z liczb Fibonacciego, którego definicję przypominamy dla przejrzystości wykładu:

$F_{0}=F_{1}=1{\mbox{, }}F_{i}=F_{i-1}+F_{i-2}{\mbox{ dla }}i=2,3,...\;$

(3.128)

Wybieramy dwa punkty, którego będziemy podawali dla i=1,2,..,N-2 przy pomocy liczb Fibonacciego (3.128), w takim wypadku:

$t_{1}^{(i)}={{F_{N-i-1}} \over {F_{N-1+i}}}(b-a)+a\;$

(3.129)

$t_{2}^{(i)}={{F_{N-i}} \over {F_{N-i+1}}}(b-a)+a\;$

(3.130)

Podyskutujmy teraz o punktach "a" i "b", tzn. jeśli mamy $f(t_{1}^{(i)})\leq f(t_{2}^{(i)})\;$, to liczba "a" jest taka sama, a liczba "b" staje się liczbą $t_{2}^{(i)}\;$, w drugim przypadku $f(t_{1}^{(i)})>f(t_{2}^{(i)})\;$, to wtedy "b" jest bez zmian a "a" jest liczbą $t_{1}^{(i)}\;$. Po i-tej iteracji końcowy przedział ma długość poniżej, do którego wykorzystamy obliczenia dla punktu (3.130), od którego odejmować będziemy liczbę "a", co wyniki czego otrzymujemy maksymalna długość jaki może mieć przedział w i-tej operacji:

$b-a={{F_{N-1}} \over {F_{N}}}{{F_{N-2}} \over {F_{N-1}}}\cdot {\mbox{...}}\cdot {{F_{2}} \over {F_{3}}}(b^{(0)}-a^{(0)})={{F_{2}} \over {F_{N}}}{{b^{(0)}-a^{(0)}} \over {F_{N}}}(b^{(0)}-a^{(0)})={{2(b^{(0)}-a^{(0)})} \over {F_{N}}}\;$

(3.131)

Aby uzyskać przedział końcowy, w którym będziemy poszukiwali minimum funkcji uzyskujemy w N-1 obliczeniach wartości funkcji.

Efektywna metoda złotego podziału

Metoda ta polega by w następnej iteracji przedział zmniejszał się o taką sama długość przy wyborze punktów $t_{1}^{(i)}\;$ i $t_{1}^{(i)}\;$, w taki sposób jeden z punktów pokrywał się z punktem powstałej w poprzednim kroku iteracji. Algorytm ten wymaga by był spełniony warunek:

$t_{2}^{(i)}-a=b-t_{1}^{(i)}=\tau (b-a){\mbox{ dla }}\tau \in (0,1)\;$

(3.132)

$b-t_{2}^{(i)}=\tau (b-t_{1}^{(i)})\;$

(3.133)

Wyznaczmy liczby $t_{1}^{(i)}\;$ i $t_{1}^{(i)}\;$ z równania (3.132) i podstawmy je do wzoru (3.133), w ten sposób otrzymujemy:

$b-a-\tau (b-a)=\tau \tau (b-a)\Rightarrow 1-\tau =\tau ^{2}\Rightarrow \tau ^{2}+\tau -1=0\;$

(3.134)

Końcowe równanie (3.134) jest równaniem kwadratowym, którego rozwiązaniem jest liczba:

$\tau ={{{\sqrt {5}}-1} \over {2}}\simeq 0,62\;$

(3.135)

Jeszcze raz wykorzystując wzór (3.132) by otrzymać później wzory na punkty $t_{1}^{(i)}\;$ i $t_{1}^{(i)}\;$ jako punkty, w którym chcemy policzyć wartości funkcji i potem było można znaleźć wartości funkcji, w takim wypadku:

$t_{1}^{(1)}=a+\tau (b-a)\;$

(3.136)

$t_{2}^{(1)}=b-\tau (b-a)\;$

(3.137)

Rozważmy przypadek, gdy $f(t_{1}^{(i)})\leq f(t_{2}^{(i)})\;$, to wtedy punkt "a" pozostaje bez zmian, to wybieramy przedział w następnym kroku iteracji jako $\langle a,t_{1}^{(i)})\rangle \;$ lub gdy $f(t_{1}^{(i)})>f(t_{2}^{(i)})\;$ w następnym kroku iteracji przyjmujemy przedział $\langle t_{2}^{(i)},b\rangle \;$.

Interesuje nas efektywność metody złotego podziału w porównaniu z metodą optymalnych podziałów Johnsona, i jeśli w opisywanej tutaj metodzie mamy K obliczeń wartości funkcji, to w metodzie Johnsona mamy N=K+1 obliczeń wartości funkcji. Jeśli mamy w metodzie Johnsona $|t-\alpha |\leq 2{{b^{(0)-a^{(0)}}} \over {F_{K+1}}}\;$, to w metodzie złotego podziału mamy iteracji $|t-\alpha |\leq {{b^{(0)}-a^{(0)}} \over {G_{K+1}}}\;$, dla którego mamy $G_{i}=\left({{1} \over {\tau }}\right)^{i-1}\;$ Z powyższych oszacowań możemy napisać:

$2{{b^{(0)}-a^{(0)}} \over {F_{K+1}}}\leq {{b^{(0)}-a^{(0)}} \over {G_{K-1}}}{\mbox{ i }}{{b^{(0)}-a^{(0)}} \over {G_{K}}}\leq 2{{b^{(0)}-a^{(0)}} \over {F_{K+1}}}\Rightarrow 2G_{K-1}\leq F_{K+1}\leq 2G_{K}\;$

(3.138)

Aby mieć dokładność w metodzie złotego podziału zbliżoną do metody optymalnych podziałów Johnsona należy w tej przedostatniej metodzie wykonać dodatkowy krok obliczeń, gdy mamy wykonane K-1 kroków.