Przejdź do zawartości

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

Z Wikibooks, biblioteki wolnych podręczników.
Metody numeryczne fizyki
Metody numeryczne fizyki
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ść.


Następny rozdział: Całkowanie numeryczne funkcji interpolacyjnej. Poprzedni rozdział: Aproksymacja.

Podręcznik: Metody numeryczne fizyki.

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

[edytuj]

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 x1 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 x1 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 xi dzieli te przedziały na dwa. Jeśli w tak otrzymanym w punkcie x2 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:

(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:

(3.2)

Reguła falsi

[edytuj]
(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:

(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):

(3.4)

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

(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ń

[edytuj]

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:

(3.6)

W równości (3.6) przyjęliśmy, że zachodzi warunek graniczny dla ciągu xn, 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

[edytuj]

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

(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):

(3.8)

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

[edytuj]

Załóżmy, że kolejne przybliżenie pierwiastka funkcji f(x), czyli xk liczymy ze wzoru, do którego będzie nam potrzebne czemu jest równe f(xk), 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:

(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:

(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:

(3.11)

Możemy wykonać potrzebne wymnażania w równości (3.11) i dodać na samym końcu wyraz , zatem dokonując te wskazane operacje na tym wspomnianym równaniu, otrzymujemy:



(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:

(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:

(3.14)
(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:

(3.16)

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

(3.17)

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

[edytuj]

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 |xk+1-xk|, 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 xk+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 xn+1:

(3.18)

Metoda siecznych

[edytuj]

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 xn-1, zatem na podstawie tych rozważań możemy podać iteracje, dzięki której będziemy liczyli kolejne przybliżenia xk pierwiastka α funkcji f(x), mamy:

(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 xn+1-xn 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(xk)| 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)

[edytuj]
(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:

(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:

(3.21)

Dalszym krokiem jest pokazanie, że x1, 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.

(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 x1, którą to ostatecznie piszemy:

(3.23)

Z równości (3.23) otrzymaliśmy tożsamość na α-x1 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:

(3.24)

Stąd z nierówności (3.24) możemy napisać nierówność x1. Patrząc na rysunek obok dostajemy wniosek, że liczba x1 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 x1 i wiedząc, że punkcie α funkcja f(x) przyjmuje wartość zerową, zatem na podstawie tego możemy napisać:

(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:

(3.26)

Jesli we wzorze (3.26) przyjmować będziemy y=0, to x=xn+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.

(3.27)

Jeśli we wzorze (3.26) przejdziemy do granicy dla n nieskończonego takiego, by zachodziło , zatem na podstawie tego możemy powiedzieć:

(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:


(3.29)

Jeśli napiszemy , to końcowy wynik wedle obliczeń (3.28) możemy zapisać:

(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):

(3.31)

Jeśli przyjmować będziemy tak jak przy regule falsi, że , to wtedy nierówność (3.31) przyjmuje postać:

(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 ε:

(3.33)

Poszukiwanie pierwiastków wielomianów o dziedzinie zespolonej

[edytuj]

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":

(3.34)

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

[edytuj]

Twierdzenie Sturma

[edytuj]

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 f0(x),f1(x),f2(x),...,fp(x), w których poszczególne elementy sa takie, że f0(x) jest to zwykła rzeczywista funkcja f(x), a funkcja f1(x) jest to pierwsza pochodna funkcji f(x). A f2(x) jest to reszta z dzielenia funkcji f0(x) przez funkcję f1(x) wzietej ze znakiem przeciwnym, element f3(x) jest to reszta z dzielenia funkcji f1(x) przez f2(x) wziętej ze znakiem przeciwnym. Takie postępowanie powtarzamy, aż uzyskamy wielomian fp+1(x), który jest tożsamościowo równy zero, wtedy mamy wielomian fp, który jest największym dzielnikiem wielomianu f(x). Jeśli wielomian fp 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(x0) liczbę zmian znaków ciągu Sturna w punkcie x=x0. Mając na uwadze wszystko o twierdzeniu Sturna zdefiniujmy twierdzenie Sturna:

Twierdzenie Sturma
Jeśli mamy ciąg Sturma {fi(x)} dla i=0,1,2,..,p określonego w przedziale (a,b), i zachodzi f0(a)f0(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)=x3+x2-x-1, to wtedy możemy określić sobie ciąg Sturma:

  • f0(x)=x3+x2-x-1
  • f1(x)=3x2+2x-1
  • f2(x)=x+1

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

  • f0(x)=x2-1
  • f1(x)=2x
  • f2(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 f0(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 f0(x) ma N(-∞)-N(∞)=2-0=2 pierwiastków.

Twierdzenie Fouriera

[edytuj]

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(n)(x). A przez M(x0) oznaczmy liczbę zmian znaków ciągu {f(i)(x)} dla i=0,1,2,,n w punkcie x=x0. 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)=x3-2x2-5x+5, wtedy sobie tworzymy ciąg czterech pochodnych:

  • f(x)=x3-2x2-5x+5
  • f'(x)=3x2-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

[edytuj]

Weźmy sobie wielomian f(x)=a0xn+a1xn-1+...+an-1x+an, dla a0≠0, to wtedy sobie tworzymy ciąg wielomianów:

  • f0(x)=a0
  • f1(x)=a0x+a1
  • f2(x)=a0x2+a1x+a2

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

  • fn=f(x)

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

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

[edytuj]

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 a0,a1,...,an lub od niej jest mniejsza o parzystą liczbę.

Lokalizowanie miejsc zerowych rzeczywistych wielomianów rzeczywistych

[edytuj]

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:

(3.35)
(3.36)
(3.37)

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

Twierdzenie Lagrange'a
Niech a0≠0 i ak będzie pierwszym ujemnym współczynnikiem wielomianu f(x), to wszystkie dodatnie miejsca zerowe tegoż wielomianu są mniejsze niż:
(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

[edytuj]

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

(3.39)

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

(3.40)

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


(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 Rj:

(3.42)
(3.43)
(3.44)

Jeśli powtórnie dokonamy dzielenia wielomianu występującego w nawiasie (3.40) przez wielomian x-xj, wtedy wielomian f(x) piszemy przy pomocy reszty z dzielenia wychodząc od wzoru (3.40) jako wzór:

(3.45)

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

(3.46)
(3.47)
(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(xj)=Rj i f'(xj)=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:

(3.49)
(3.50)

Umieszczanie zer wielomianów ogólnie zespolonych

[edytuj]

Warunki na miejsca zerowe zespolone wielomianów zespolonych

[edytuj]

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:
(3.51)
(3.52)

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

(3.53)
Twierdzenie drugie
Napiszmy wielomian o współczynnikach i argumentach zespolonych:
(3.54)

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

(3.55)

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

(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:
(3.57)

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

(3.58)
Twierdzenie czwarte
Moduły wszystkich miejsc zerowych zespolonych wielomianu o współczynnikach rzeczywistych spełniają nierówność:
(3.59)
Twierdzenie piąte
Dla wielomianu o współczynnikach rzeczywistych , jeśli wszystkie współczynniki spełniają warunek a0>a1...>an>0, to moduły wszystkich miejsc zerowych są mniejsze niż jeden, a jeśli an>an-1...>a0>0, to moduły wszystkich miejsc zerowych są większe niż jeden.

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

(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:

(3.61)

Tworzymy teraz ciąg wielomianów f0(z), f1(z), f2(z),..., fn(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 f0(z)=f(z). Utwórzmy sobie teraz funkcję z funkcji f0(z) w taki sam sposób w jaki tworzyliśmy funkcję (3.58), i na podstawie jej i funkcji f0(z) tworzymy funkcję f1(z) , przy pomocy współczynników z podkreśleniem górnym, które są współczynnikami wielomianu , i przy pomocy współczynników bez podkreślenia, które są współczynnikami wielomianu f0(z) przy pomocy schematu:

(3.62)

Możemy stworzyć teraz funkcję w taki sam w sposób jaki tworzyliśmy funkcję (3.58), ale tym razem z wielomianu f1(z). W podobnym sposobem tworzymy funkcję f2(z) ze współczynników wielomianu f1(z) i i tychże funkcji, czyli według:

(3.63)

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

(3.64)

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

(3.65)

Na podstawie ciągu wielomianów {fj(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ą:

(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:

(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 Pk (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

[edytuj]
Kryterium Michajłowa
Warunkiem koniecznym i dostatecznym, by wielomian 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

[edytuj]

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

(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:




 --------------------------------
(3.69)

Liczby (3.69) ustawmy w tablicy:






 --------------------------------
(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

[edytuj]
Kryterium Hurwitza
Warunkiem koniecznym i dostatecznym, by wszystkie miejsca zerowe wielomianu o an>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 aj=0 dla j<0.

(3.71)

Poszukiwanie miejsc zerowych wielomianu zespolonego

[edytuj]

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:

(3.72)

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

(3.73)
(3.74)

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

(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:

(3.76)
(3.77)

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


(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:

(3.79)
(3.80)

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

(3.81)
(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:


(3.83)

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

(3.84)
(3.85)

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

[edytuj]

Szukamy takiego rozwiązania , dla którego odwzorowanie przyjmuje wartość zero . Jeśli szczególnym odwzorowaniem jest funkcja afiniczna , to szukamy rozwiązania , gdzie jest wektorem szukanych wielkości, a jest wektorem wyrazów wolnych. W obliczeniach numerycznych będziemy szukali ciągu wektorów , które są zbieżne do wartości , który jest rozwiązaniem równania . Zbudujmy odwzorowanie , to takie odwzorowanie nazywamy metodą stacjonarną p-punktową, jeśli mamy w szczególnym przypadku , 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 i określmy tzw. punkt przyciągania metody iteracyjnej, jeśli mamy takie otoczenie Uα naszego punktu, że zbierając punkty , co z tego otoczenia uzyskamy ciąg punktów dążącej do wektora , tzn. ciąg , który jest zbieżny do wektora , które największe z tych otoczeń nazywamy obszarem przeciągania punktu w n-wymiarowej przestrzeni.
Lemat
Niech mamy odwzorowanie , jeśli istnieje takie c<1, dla którego zachodzi:
(3.86)
dla której istnieje kula , to ciąg punktów jest zawarty wewnątrz tej kuli. Ta zbieżność jest conaj mniej liniowa, bo według zachodzi dla "i" naturalnego z zerem.
Definicja
Niech mamy odwzorowanie , to różniczkowanie w sensie Fricheta w punkcie nazywamy odwzorowanie dla którego istnieje macierz , dla której zachodzi:
(3.87)
wtedy macierz nazywamy pochodną odwzorowania G w punkcie i oznaczać je będziemy przez .
Twierdzenie Ostrowskiego
Weźmy sobie pochodną Frecheta zwana inaczej F-pochodną odwzorowania w punkcie , w którym F-pochodna ma promień spektralny równy , oraz oczywiście zachodzi , to punkt jest punktem przyciągania metody iteracyjnej , z którego uzyskujemy kolejne przybliżenia wektora .
Dowód twierdzenia Ostrowskiego
Ponad wszelką wątpliwość można napisać dla promienia spektralnego β. Z określenia pochodnej Frecheta możemy napisać, że istnieje kula taka, że zachodzi:
(3.88)
dla należącego do kuli. Wtedy na podstawie tychże warunków możemy napisać

(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ą jest ciągiem zbieżnym do wektora .

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

[edytuj]
Twierdzenie pierwsze
Niech istnieje F-pochodna funkcji wektorowej zwarta w pewnym otoczeniu taki, że wektor spełnia równanie i w punkcie jest nieosobliwa, wtedy punkt nazywamy punktem przyciągania metody iteracyjnej:
(3.90)
Dowód twierdzenia pierwszego
Z warunku nieosobliwości F-pochodnej funkcji wektorowej możemy napisać funkcję:
(3.91)
dla której pochodna powyższej funkcji w punkcie 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 , czyli kolejne przybliżenia rozwiązania .

Za każdym razem w metodzie Newtona należy liczyć F-pochodną funkcji , i jego odwrotność, a także wartości funkcji , 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 w punkcie jest typu Höldera, tzn. spełnia warunek:
(3.92)

to wtedy jest spełniony warunek:

(3.93)

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

(3.94)

Widzimy, że według (3.94) w ciągu wektorów , 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:

(3.95)

Metoda kolejnych poprawek trójmianu kwadratowego - metoda Bairstowa

[edytuj]

Weźmy sobie wielomian f(z), którym wszystkie współczynniki oznaczmy przez ak, w którym przy najwyższej potędze jest a0 i wskaźnik wzrasta wraz z maleniem wykładnika potęgi przy zk, który dzielimy przez trójmian kwadratowy x2+piz+qi, w ten sposób otrzymujemy wynik wraz z resztą z dzielenia równą Riz+Si, zatem na podstawie tego wielomian f(x) zapisujemy:

(3.96)

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




(3.97)

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

(3.98)
(3.99)

Wzory na współczynniki Ri i Si na podstawie (3.97) są:

(3.100)
(3.101)

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

(3.102)

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

(3.103)
(3.104)

A współczynniki R'i i S'i wedle (3.100) i (3.101) możemy napisać zamieniając ak na bk i bk na ck:

(3.105)
(3.106)

Mamy znaleźć takie pi i qi, by w wielomianie (3.96) parametry Ri i Si w granicy dążyły do zera, zatem najpierw policzmy pierwsze pochodne cząstkową wyrazów bk względem pi i qi, wtedy:




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




 -------

(3.107)

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


(3.108)

Wyznaczmy teraz wyznacznik macierzy F'(pk,qk) (3.108):

(3.109)

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



(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'(pk,qk) policzonej w punkcie (3.109):

(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 pk i qk:

(3.112)
(3.113)

Metoda siecznych jako metoda n+1 punktowa

[edytuj]

Metoda ta polega na odwzorowaniu liniowym (afinicznym) funkcji w odwzorowaniu , tzn.:

(3.114)

Oznaczmy przez jako różnice elementów argumentów (3.114) o kolumnach , ,..., a przez o kolumnach , ,..., wtedy możemy napisać:

(3.115)

Szunanym punktem rozwiązania przy wykorzystaniu wzoru (3.114) jest rozwiązanie:

(3.116)

Jeśli zastosujemy wzór (3.115) do tożsamości (3.116) podstawiając za macierz , wtedy kolejne przybliżenie miejsca zerowego funkcji możemy napisać przyjmując we wspomnianym wzorze jako :

(3.117)

W powyższym odwzorowaniu wybieramy n+1 punktów , ,..,, wtedy obliczamy kolejno macierze i , oczywiście przyjmując w takim razie:

(3.118)

Metodę (3.117) nazywamy n+1 punktową metodą siecznych, ponieważ do wyznaczania kolejno punktów , ,... 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 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:

(3.119)

W powyższym, wzorze przyjęto, że mamy n+1 punktów, tzn. , wtedy przyjmujemy , a także możemy napisać brakujące punkty ,. wtedy te punkty dobieramy na w sposób:

(3.120)

i dlatego we wzorze (3.119) argumenty są określone wzorem (3.120). Jeśli macierz jest macierzą osobliwą, to macierz w odwzorowaniu 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

[edytuj]

Aby znaleźć wartość funkcji w odwzorowaniu 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 t1 i t2, takie, że spełniony jest warunek a<t1<t2<b, wtedy jeśli jest spełniony warunek f(t1)≤f(t2) to minimum funkcji leży w przedziale α∈<α,t2>, a jeśli f(t1)>f(t2), to minimum funkcji f(t) leży w przedziale α∈<t1,b>

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

[edytuj]

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) i b(i) dążą do α.

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

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

(3.121)
(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ż:

(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
[edytuj]

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

(3.124)
(3.125)
(3.126)

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

(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

[edytuj]

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

(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:

(3.129)
(3.130)

Podyskutujmy teraz o punktach "a" i "b", tzn. jeśli mamy , to liczba "a" jest taka sama, a liczba "b" staje się liczbą , w drugim przypadku , to wtedy "b" jest bez zmian a "a" jest liczbą . 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:

(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

[edytuj]

Metoda ta polega by w następnej iteracji przedział zmniejszał się o taką sama długość przy wyborze punktów 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:

(3.132)
(3.133)

Wyznaczmy liczby i z równania (3.132) i podstawmy je do wzoru (3.133), w ten sposób otrzymujemy:

(3.134)

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

(3.135)

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

(3.136)
(3.137)

Rozważmy przypadek, gdy , to wtedy punkt "a" pozostaje bez zmian, to wybieramy przedział w następnym kroku iteracji jako lub gdy w następnym kroku iteracji przyjmujemy przedział .

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 , to w metodzie złotego podziału mamy iteracji , dla którego mamy Z powyższych oszacowań możemy napisać:

(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.