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ł , 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 i . 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 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:
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:
Reguła falsi
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:
Jak powiedzieliśmy wcześniej znajdujemy taką wartość x, dla której w równaniu 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 :
Mając już wyznaczoną wartość x możemy przeprowadzić następną sieczną, którego za miejsce "a' we wzorze podstawiamy x a za x podstawiamy x, w ten sposób otrzymujemy rekurencję, która jest napisana wzorem dla k=1,2,..n:
Jeśli dla uproszczenia rozważań będziemy przyjmować f'(x)>0 i f''(x)>0, to można udowodnić, że ciąg 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:
W równości przyjęliśmy, że zachodzi warunek graniczny dla ciągu x, który to zapisujemy wzorem: , 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:
Z równości możemy napisać oszacowanie błędu, korzystając z faktu, że liczba α jest pierwiastkiem równania f(x):
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 liczymy ze wzoru, do którego będzie nam potrzebne czemu jest równe f(x), 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:
Jeśli przyjmować będziemy, że f(α) jest równe zero, a α jest pierwiastkiem tego równana, to wtedy równość możemy przedstawić w postaci wzoru:
Korzystając z twierdzenia Lagrange'a dla prawej i lewej strony równości, wtedy wzór możemy przepisać robiąc te podstawienia wynikłe z podanego wcześniej twierdzenie Lagrange'a:
Możemy wykonać potrzebne wymnażania w równości i dodać na samym końcu wyraz , zatem dokonując te wskazane operacje na tym wspomnianym równaniu, otrzymujemy:
Po krótkich przekształceniach we wzorze 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:
Jeśli wprowadzimy minimalną wartość funkcji f(x) w naszym przedziale i oznaczymy przez m, a maksymalną wartość tej samej funkcji w tym samym przedziale oznaczymy przez M, co te wartości zapisujemy wzorami:
To końcowy wynik zapisany przy tożsamościach i możemy wykorzystać do końcowych obliczeń zapisanej w punkcie , zatem w końcowych perypetiach otrzymujemy następującą równość, którą to piszemy wzorem:
Jeśli dodatkowo założymy, że zachodzi warunek , to wtedy równość możemy przepisać do postaci:
Inny wzór na błąd bezwzględny oszacowania wartości dokładnej pierwiastka funkcji f(x) Oszacowanie zapisane wzorem 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-x|, 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 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:
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 , w która powstaje po zastąpieniu w nim parametru b przez kolejne przybliżenia pierwiastka funkcji f(x), czyli przez x, zatem na podstawie tych rozważań możemy podać iteracje, dzięki której będziemy liczyli kolejne przybliżenia x pierwiastka α funkcji f(x), mamy:
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 dokładność różnicy x-x 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)| 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)
Przybliżoną wartość pierwiastka możemy obliczyć na przedziale , 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:
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:
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.
Jeśli wykorzystamy do ostatecznej równości , w ten sposób otrzymujemy równość, która jest różnicą pierwiastką α i liczby x, którą to ostatecznie piszemy:
Z równości otrzymaliśmy tożsamość na α-x przy przyjętych założeniach f''(c)>0 i f'(b)>0· Z równości możemy otrzymać równość przy dodatnich znakach funkcji i pierwszej pochodnej w punkcie b, stąd dostajemy wniosek:
Stąd z nierówności 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ć:
Na podstawie końcowej tożsamości , 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:
Jesli we wzorze przyjmować będziemy y=0, to x=x 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.
Jeśli we wzorze przejdziemy do granicy dla n nieskończonego takiego, by zachodziło , zatem na podstawie tego możemy powiedzieć:
To z równości 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 , 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 , zatem na tej podstawie piszemy:
Jeśli napiszemy , to końcowy wynik wedle obliczeń możemy zapisać:
Jeśli wykorzystamy wzór, który jest również słuszny na metody stycznych, czyli , to otrzymamy nierówność wynikającą z :
Jeśli przyjmować będziemy tak jak przy regule falsi, że , to wtedy nierówność przyjmuje postać:
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 ε:
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":
Znajdowanie liczby miejsc zerowych rzeczywistych dla wielomianu o współczynnikach rzeczywistych Twierdzenie Sturma