Rozwiązywanie równań nieliniowych i ich układów.
Wyznaczanie zer wielomianów.
Plan wykładu:
1. Wyznaczanie pojedynczych pierwiastków rzeczywistych
równań nieliniowych metodami
a) połowienia (bisekcji)
b) Regula Falsi
c) siecznych
d) Newtona
2. Wyznaczanie zer wielokrotnych
a) modyfikacja metod przy znajomości krotności pierwiastka
b) modyfikacja metod siecznych i Newtona dla przypadku ogólnego
c) Proces d�2 Aitkena
3. Rozwiązywanie układów równań nieliniowych
4. Wyznaczanie zer rzeczywistych i zespolonych wielomianów
a) metoda Lehmera-Schura
b) metoda A
obaczewskiego
c) dzielenie wielomianów
d) metoda iterowanego dzielenia
1
Równanie nieliniowe z jedną niewiadomą
Poszukujemy zera rzeczywistego ciągłej
funkcji f(x), czyli szukamy rozwiązania równania:
f(x) = 0 , x 2 fx1; x2; : : : ; xkg; x 2 R
2
Uwagi: Założenia:
1) w przedziale [a,b] znajduje się dokładnie
1) Nie istnieją wzory pozwalające obliczyć jeden pierwiastek
dokładnie pierwiastki równania  trzeba 2) Na końcach przedziału wartosci funkcji
używać schematów iteracyjnych. Często mają różne znaki tj.
w obliczeniach inżynierskich nie jest znana
f(a) ó f(b) < 0
postać równania nieliniowego.
2) Rozwiązanie problemu uzyskane metodą
iteracyjną będzie przybliżone Algorytm
(z zadaną dokładnością)
3) Jak w każdej metodzie iteracyjnej, o tym 1. Dzielimy przdział izolacji na pół
jak szybko znajdziemy zadowalające
b + a
przybliżenie pierwiastka zależeć będzie od
x1 =
samej metody, od przybliżenia założonego
2
na starcie oraz od postaci funkcyjnej 2. Sprawdzamy czy spełniony jest warunek
równania.
f(x1) = 0
jeśli tak to mamy rozwiązanie, jeśli nie to
Metoda połowienia (bisekcji) przechodzimy do kolejnego puntu
3. z dwóch przedziałów [a,x1] oraz [x1,b]
Rozwiązania szukamy w przedziale, w którym
wybieramy ten, w którym wartości funkcji
znajduje się miejsce zerowe funkcji, w tzw.
na krańcach przedziałów mają różne znaki
przedziale izolacji pierwiastka (wewnątrz
tego przedziału pierwsza pochodna funkcji nie
f(xi) ó f(xi+1) < 0
zmienia znaku). Przedział wyznacza się na
podstawie wykresu funkcji lub w przypadku
4. Powtarzamy kroki 1-3, co powduje że
wielomianów algebraicznych  analitycznie.
długości kolejnych przedziałów maleją
1
jxi Ą xi+1j = (b Ą a)
3
2i
Lewe krańce przedziałów tworzą ciąg niemalejący
Wyniki kolejnych przybliżeń rozwiązania
ograniczony z góry. Natomiast prawe tworzą ciąg nie
x f(x)
rosnący ograniczony z dołu. Istnieje ich wspólna
1.0 -4
granica w punkcie a�. Punkt ten jest poszukiwanym
2.0 3
rozwiązaniem równania nieliniowego.
1.5 -1.874
Przykład. Znalez
ć w przedziale [1,2] metodą
1.75 0.17187
połowienia pierwiastek równania
1.625 -0.94335
1.6875 -0.40942
x3 + x2 Ą 3x Ą 3 = 0
1.71875 -0.12487
f(x) = x3 + x2 Ą 3x Ą 3
1.73437 0.02198
.............. .............
f(1) = Ą4
1.73205 0.0000000
f(2) = 3
f(a) ó f(b) = f(1)f(2) = Ą12 < 0
Wadą metody wolna zbieżność w otoczeniu
punktu stanowiącego rozwiązanie. Zaletą jest
natomiast niezawodność metody.
Wewnątrz przedziału wartość pierwszej pochodnej
funkcji jest dodatnia (nie zmienia znaku)  więc jest to
przedział izolacji pierwiastka.
4
Wzór iteracyjny. Wzór ten można zapisać w bardziej ogólnej
postaci
Jeżeli g(y) stanowi funkcję odwrotną do f(x)
xi+1 = F (xi; xiĄ1; : : : ; xiĄn+1)
to dla zbioru punktów
fy1; y2; : : : ; yng
który jest n-punktowym wzorem
funkcję g(y) można przybliżyć (aproksymować) iteracyjnym.
wielomianem Lagrange'a Szczególnym przypadkiem są metody
n jednopunktowe wykorzystujące do
X
znalezienia przybliżenia w i+1 iteracji przy
g(y) ź lj(y)g(yj)
znajomości przybliżenia wyznaczonego w i-
j=1
tym kroku
Oznaczmy
xi+1Ąj = g(yj)
xi+1 = F (xi)
Jeśli x=a jest rozwiązaniem (pierwiastkiem)
to wówczas y=0 Zbieżność metody iteracyjnej
n
X
Ciąg przybliżeń jest zbieżny gdy
xi+1 = lj(0)xi+1Ąj
j=1
lim xi = a
i!1
(xi+1-j  to wcześniej wyznaczone przybliżenia)
Błąd rozwiązania w i-tej iteracji
gdzie wielomian lj ma postać
"i+1 = a Ą xi+1
(y Ą y1) : : : (y Ą yjĄ1)(y Ą yj+1) : : : (y Ą yn)
lj =
W punkcie x=a metoda jest rzędu p, jeśli
(yj Ą y1) : : : (yj Ą yjĄ1)(yj Ą yj+1) : : : (yj Ą yn)
istnieje liczba rzeczywista
p � 1
Wzór na xi+1 określa metodę iteracyjną rozwiązywania
równania nieliniowego.
5
dla której zachodzi
jxi+1 Ą aj j"i+1j
lim = lim = C = 0
6
i!1 i!1
jxi Ą ajp j"ijp
Liczbę C nazywamy stałą asymptotyczną
błędu
j"i+1j = Cj"ijp
j"j < 1 ) j"i+1j << j"ijp
Metoda Regula Falsi
W metodzie tej wykorzystuje się założenie
istnienia lokalnej liniowości funkcji (fałszywe,
stąd nazwa). Zakładamy ponadto:
Rys. Idea metody Regula Falsi dla funkcji wypukłej
1) w przedziale [a,b] funkcja ma tylko jeden
pierwiastek pojedynczy
2) f(a)f(b)<0
3) funkcja jest klasy C2
4) pierwsza i druga pochodna nie zmieniają
znaku w przedziale [a,b]
6
Sposób postępowania:
Błąd przybliżenia szacujemy korzystając z tw.
Lagrange'a o przyrostach:
1. przez punkty A i B prowadzimy prostą o
0
f(xk) Ą f(�) = f (c)(xk Ą �)
równaniu:
f(b) Ą f(a)
y Ą f(a) = (x Ą a)
gdzie: c 2 [xk; �]
b Ą a
2. punkt x1 w którym prosta przecina oś 0x
Ponieważ
f(�) = 0
przyjmuje się za pierwsze przybliżenie
więc dostajemy oszacowanie
szukanego pierwiastka równania:
jf(xk)j
f(a)
jxk Ą �j �
x1 = a Ą (b Ą a)
m
f(b) Ą f(a)
gdzie 0
m = inf jf (x)j
3. sprawdzamy warunek, czy: f(x1)=0, jeśli tak
x2[a;b]
to przerywamy oblicznia
m -oznacza kres dolny pierwszej pochodnej
f(x1) = 0
6
4. jeśli to sprawdzamy na końcach
Błąd bezwzględny można oszacować znając
którego przedziału ([A,x1], [x1,B]) wartości
wartości dwóch kolejnych przybliżeń xk i xk+1.
funkcji mają różne znaki  przez te punkty
Przekształcając wzór rekurencyjny otrzymujemy:
prowadzimy kolejną prostą powtarzając kroki
1-4
f(xk) Ą f(b)
Ąf(xk) = (xk+1 Ą xk)
xk Ą b
Jeśli w przedziale [A,B]
I dodajemy z lewej strony wyraz
a) f(1)(x)>0 oraz f(2)(x)>0 to B jest punktem
stacjonarnym (prawy brzeg ustalony)
b) f(1)(x)>0 oraz f(2)(x)<0 to A jest punktem
f(�) = 0
stacjonarnym
Metoda generuje ciąg przybliżeń. Elementy ciągu f(xk) Ą f(b)
f(�) Ą f(xk) = (xk+1 Ą xk)
można wyznaczyć rekurencyjnie
xk Ą b
k = 1; 2; 3; : : :
x0 = a
7
f(xk)
xk+1 = xk Ą (b Ą xk)
f(b) Ą f(xk)
Nie znamy wartości m i M. W niewielkim otoczeniu
Po zastosowaniu tw. Lagrange'a otrzymujemy:
pierwiastka można pochodną można zastąpić
0 0
ilorazem różnicowym:
(� Ą xk)f (k) = (xk+1 Ą xk)f (xk)
ą
Ż Ż
Ż Ż
f(xk+1)
Ż Ż
k 2 (xk; �) xk 2 (xk; b)
ą
j� Ą xk+1j
0
Żf (xk+1)Ż
Ż Ż
Ż
xk+1 Ą xk Ż
Ż Żjf(xk+1)j

Następnie przekształcamy do postaci
Żf(xk+1) Ą f(xk) Ż
0 0 Metoda Regula Falsi jest zbieżna do dowolnej funkcji
jf (xk) Ą f (k)j
ą
ciągłej w przedziale [a,b] jeśli wartość pierwszej
j� Ą xk+1j = jxk+1 Ą xkj
0
pochodnej jest ograniczona i różna od zera w
jf (k)j
otoczeniu pierwiastka. Obliczenia przerywa się jeśli
Dla
dwa kolejne przybliżenia różnią się o mniej niż
0 0 założone e�. Wadą jest wolna zbieżność ciągu
jf (xk) Ą f (k)j � M Ą m
przybliżeń  rząd metody p=1.
gdzie:
kres dolny
0
m = inf jf (x)j
x2[a;b]
kres górny
0
M = sup jf (x)j
x2[a;b]
oszacowanie błędu bezwględnego ma postać
M Ą m
j� Ą xk+1j � jxk+1 Ą xkj
8
m
Metoda siecznych
Jest modyfikacją metody Regula Falsi. Prostą
Regula Falsi Metoda
przeprowadza się przez dwa ostatnie
siecznych
przybliżenia xk i xk-1 (metoda dwupunktowa).
x3 1.75960 1.75960
Kolejne przybliżenia w metodzie siecznych
wyznacza się według relacji rekurencyjnej:
1.84420 1.93200
x4
f(xk)(xk Ą xkĄ1)
1.87701 1.89242
x5
xk+1 = xk Ą
f(xk) Ą f(xkĄ1)
1.88895 1.89543
x6
Zbieżność metody jest znacznie szybsza niż w
1.89320 1.89549
x7
metodzie RF. Rząd metody
1.89469
x8
p
1
p = (1 + 5) ź 1:618
1.89521
2 x9
Należy dodatkowo przyjąć, że |f(xk)| mają
x10 1.89540
tworzyć ciąg wartości malejących. Jeśli w
kolejnej iteracji |f(xk)|zaczyna rosnąć, należy
x11 1.89546
przerwać obliczenia i ponownie wyznaczyć
punkty startowe zawężając przedział izolacji.
x12 1.89548
Przykład. szukamy dodatniego pierwiastka
x13 1.89549
równania
1
f(x) = sin(x) Ą x
2
x2 = ź
x1 = ź=2
9
Metoda Newtona (metoda stycznych)
Algorytm:
1) z końca przedziału [a,b] w którym funkcja ma
ten sam znak co druga pochodna należy
poprowadzić styczną do wykresu funkcji y=f(x)
2) styczna przecina oś 0X w punkcie x1 który
stanowi pierwsze przybliżenie rozwiązania
3) sprawdzamy czy f(x1)=0, jeśli nie to z tego
punktu prowadzimy kolejną styczną
4) druga styczna przecina oś 0X w punkcie x2
ktróry stanowi drugie przybliżenie
5) kroki 3-4 powtarzamy iteracyjne aż spełniony
będzie warunek
jxk+1 Ą xkj � "
Równanie stycznej poprowadzonej z punktu B:
0
y Ą f(b) = f (b)(x Ą b)
i dla y=0, otrzymujemy pierwsze przybliżenie:
f(b)
x1 = b Ą
0
f (b)
10
Równanie stycznej w k-tym przybliżeniu
Korzystamy z rozwinięcia Taylora:
0
0 00
1
y Ą f(xk) = f (xk)(x Ą xk)
f(�) = f(b) + f (b)(� Ą b) + f (c)(� Ą b)2
2
Równanie rekurencyjne na położenie k-tego
c 2 [�; b]
Gdzie
przybliżenia pierwiastka równania nieliniowego w
metodzie Newtona jest następujące
Wiemy że f(a�)=0 , więc po przekształceniu wzoru
Taylora otrzymujemy
f(xk)
xk+1 = xk Ą (k = 1; 2; : : :)
00
0
f (xk)
f(b) 1 f (c)
� = b Ą Ą (� Ą b)2
0 0
f (b) 2 f (b)
Metoda Newtona jest więc metodą
jednopunktową.
Korzystając ze wzoru na pierwsze przybliżenie,
możemy oszacować odległość nowego przybliżenia
od dokładnego rozwiązania:
Oszacowanie błędu przybliżenia w metodzie
00
Newtona
1 f (c)
� Ą x1 = Ą (� Ą b)2 < 0
0
2 f (b)
00
f ()
czyli punkt x1 leży na prawo od pierwiastka
"i+1 = Ą "2
0
i
Natomiast z tw. Lagrange'a wynika że
2f (xi)
f(b)
x1 2 [�; b]
x1 Ą b = Ą < 0
0
f (b)
Rząd zbieżności metody wynosi p=2.
czyli punkt x1 leży po lewej stronie punktu B.
Powyższe warunki pokazują, że kolejne iteracje
przybliżają nas do rozwiązania dokładnego
11
Przykład. Zastosować metodę Newtona do Poszukiwanie pierwiastków wielokrotnych
znalezienia pierwiastka kwadratowego równania nieliniowego
dodatniej liczby c
def. Liczbę a� nazywamy r-krotnym (re" 2)
x2 Ą c = 0
pierwiastkiem równania f(x)=0 wtedy i tylko
wtedy, gdy jest (r-1) -krotnym pierwiastkiem
Szukamy miejsca zerowego funkcji
równania:
0
f (x) = 0
f(x) = x2 Ą c
0
Metody: połowienia, RF, siecznych nadają się do
f (x) = 2x
poszukiwania pierwiastków tylko o nieparzystej
krotności. Rząd metody siecznych obniża się
Wykorzystujemy relację rekurencyjną
(wolniejsza zbieżność). Metoda Newtona pozwala
znalez
ć pierwiastki o parzystej i nieparzystej
x2 Ą c
k
krotności.
xk+1 = xk Ą
2xk
Aby utrzymać rząd metody (przyśpieszyć zbieżność)
co poprzekształceniu daje
stosuje się modyfikacje wzorów rekurencyjnych.
� ś
1 c
a) Znamy krotność r pierwiastka równania.
xk+1 = xk +
2 xk
Wówczas możemy wykorzystać tę informację w
Rozwiązania szukamy w takim przedziale [a,b],
metodzie Newtona
w którym spełnione są warunki
f(xk)
xk+1 = xk Ą r
0
f (xk)
0 < a < c1=2
(w praktyce bardzo rzadko znamy wartość r przez co
zastosowanie powyższego wzoru jest mocno
1
b > (a + c=a)
ograniczone)
2
12
Obliczmy różnicę pomiędzy rozwiązaniem Kombinacja dwóch ostatnich zależności prowadzi do
dokładnym a k+1 przybliżeniem związku pomiędzy błędami w k i w k+1 iteracji
f(xk)
a Ą xk+1 = a Ą xk + r
0
G(xk)
f (xk)
"k+1 = (a Ą xk+1) =
0
f (xk)
0
(a Ą xk+1)f (xk) = G(xk)
1 G(r+1)(1)
"k+1 = "2
k
0
r(r + 1)
Gdzie f(r)(2)
G(x) = (a Ą x)f (x) + rf(x)
Ponieważ
Różniczkujemy G(x) j-krotnie
G(j)(x) = (a Ą x)f(j+1)(x) Ą jf(j)(x)
+ rf(j)(x)
f(r)(2) = 0
6
Wykorzystujemy fakt że a jest pierwiastkiem r-
G(r+1)(a) = 0
6
krotnym
G(j)(a) = 0 (j = 0; 1; : : : ; r)
j"k+1j
� C
G(r+1)(a) = 0
6
j"kj2
Z rozwinięcia Taylora w punkcie x=a dostajemy
Więc metoda Newtona dla pierwiastka krotności r ma
(x Ą a)r+1
rząd zbieżności p=2.
G(x) = G(r+1)(1)
(r + 1)!
oraz
0
(x Ą a)rĄ1
f (x) = f(r)(2) 13
(r Ą 1)!
b) Jeśli wiemy że pierwiastek jest wielokrotny Przykład. Wyznaczyć dodatni pierwiastek
ale nie znamy jego krotności r wówczas równania
możemy badać zera funkcji
� ś2
f(x) 1
1
u(x) = x1 =
0 sin(x) Ą x = 0
f (x) 2
2
Funkcja u(x) ma zero krotności 1 w punkcie
m. Newtona m. Newtona - r m. Newtona - u(x)
x=a. We wzorach iteracyjnych dokonujmey
podstawienia u(x) za f(x)
x 1.78540 2.00000 1.80175
2
x 1.84456 1.90100 1.88963
3
a) w metodzie siecznych
x 1.87083 1.89551 1.89547
4
x 1.88335 1.89549 1.89549
5
xk Ą xkĄ1
xk+1 = xk Ą u(xk)
x 1.88946
6
u(xk) Ą u(xkĄ1)
x 1.89249
7
x 1.89399
8
x 1.89475
9
b) w metodzie Newtona
x 1.89512
10
x 1.89531
11
u(xk)
xk+1 = xk Ą
0
x 1.89540
12
u (xk)
x 1.89545
13
gdzie:
x 1.89547
14
x 1.89548
15
00
0
f (xk) x 1.89549
16
u (xk) = 1 Ą u(xk)
0
f (xk)
14
Proces d�2 Aitkena
Jeśli metoda jest zbieżna liniowo to można ją w
prosty sposób przyśpieszyć
a Ą xi+1 = Ci(a Ą xi) (jCij < 1)
gdzie |Ci| dąży do stałej asymptotycznej błędu. Po
wielu iteracjach powinniśmy otrzymać przybliżenie
ą ą
a Ą xi+1 ź C(a Ą xi); jCj = C
Zwiększamy indeks i o 1 i eliminujemy stałą
a Ą xi+2 a Ą xi+1
ź
a Ą xi+1 a Ą xi
Następnie obliczamy a
xixi+2 Ą x2
i+1
a ź
xi+2 Ą 2xi+1 + xi
Procedurę tę można stosować jedynie dla metod
zbieżnych liniowo, gdy kolejne 3 przybliżenia są
bliskie poszukiwanemu rozwiązaniu.
15
Układy równań nieliniowych To można funkcję g(y) rozwinąć w szereg Taylora w
otoczeniu punktu yi
Układ równań nieliniowych
m+1
X
1
x g y g y g y y y
x = g y) = g y + djg y y Ą yi)
x g(y g(yi) g(yi; y y
fj(x(1); x(2); : : : ; x(n)) = 0; (j = 1; 2; : : : ; n)
j!
j=1
zapisujemy w postaci wektorowej
1
g y y
+ dm+2g y Ą yi)
g(;y y
f x
f x) = 0
f(x
(m + 2)!
f y y
f = (f1; f2; : : : ; fn) 2 [y yi]
f y; y
x
x = (x(1); x(2); ; : : : ; x(n); )
x
x s
djh(x s =
x; s)
Dla takiej postaci układu wyprowadza się wzory
iteracyjne. Ogólny wzór iteracyjny
n n n
X X X
(wielokrokowy)
1 2 j
x
: : : Di ;i2;:::;ij h(x si : : : si
x)si
1
x F x x x
xi+1 = F (xi; xiĄ1; : : : ; xiĄn+1)
x F x x x
i1=1 i2=1 ij =1
F
F = (F1; F2; : : : ; Fn)
F
x
Di ;i2;:::;ij h(x
x)
Zakladamy że funkcja wektorowa f ma w 1
Gdzie: jest pochodną
otoczeniu rozwiązania
cząstkową funkcji h względem zmiennych
�
� = (�1; �2; : : : ; �n) 1 2 n
�
x(i ); x(i ); : : : ; x(i )
funkcję odwrotną
w punkcie x
g
g = (g1; g2; : : : ; gn)
g
1 2 j
s
s
wektor s: s = (si ; si ; : : : ; si )
y
y = (y(1); y(2); : : : ; y(n); )
y
Jeśli punkt
jest odwrotny do punktu x (wektora
16
przybliżonych rozwiązań)
Szukane rozwiązanie ma postać Problem poszukiwania rozwiązań układu równań
nieliniowych można sformułować jako problem
� g 0 y 0
� = g 0) ) y = 0
� g(0 y 0
poszukiwania minimum poniższej fukcji
n
Po odrzuceniu reszty w rozwinięciu Taylora i
X
2
uwzględnieniu powyższego warunku otrzymujemy
x x
�(x = fi (x
x) x)
n-wymiarowy odpowiednik metody Newtona.
i=1
Dla m=0 (metoda jednokrokowa)
Funkcja osiąga minimum globalne dla dokładnego
rozwiązania x. Do jego znalezienia można użyć
x x g y y
xi+1 = xi + dg y Ąyi) =
x x g(yi; y
metody największego spadku (minimalizacja
n
X wartości funkcji).
g y
@g y
g(yi)
(j)
x
= xi Ą yi
x
@yj
j=1
Pochodne funkcji g można wyrazic poprzez
pochodne funkcji f. Dla n=2 otrzymujemy
2 3 2 3
@f2 @f1
f1 5
1
@x(2) @x(2)
4 5 4
x x
xi+1 = xi Ą
x x
@f1
2
J
Ą@@f f2 x x
x(1) @x(1)
x x
x=xi
2 3
@f1 @f1
@x(1) @x(2)
4 5
J =
@f2 @f2
@x(1) @x(2)
Rząd zbieżności metody wynosi 2. Zazwyczaj
zbieżność uzyskujemy tylko jeśli startujemy już z
17
dobrym przybliżeniem rozwązania.
Wyznaczanie zer wielomianów Operator T działając na f(z) obniża stopień
wielomianu o 1. Działając nim wielokrotnie na f(z)
Ł ń
j jĄ1
Szukamy zer rzeczywistych i zespolonych
T [f(z)] = T T [f(z)]
wielomianu
otrzymamy ciąg wielomianów corza niższego
f(z) = anzn + anĄ1znĄ1 + : : : + a0 = 0 stopnia.
z 2 C
f(0) = 0
6
Tw. Jeśli dla
ai 2 R; (i = 0; 1; : : : ; n)
istnieje takie h, że
h
Metoda Lehmera-Schura T [f(0)] < 0
0 < h < k; h; k 2 Z
Dla pierwotnego wielomianu f(z) definiujemy
k
wielomian
k = minf1; 2; : : : ; ng $ T [f(0)] = 0
ą
fń(z) = znf(zĄ1) = an + anĄ1z + : : : + a0z0 to f(z) ma co najmniej jedno zero wewnątrz
ą ą ą ą
koła jednostkowego.
Jeśli
(kreska pozioma  sprzężenie zespolone)
i
T [f(0)] > 0; 1 � i < k
i wprowadzamy operator T
kĄ1
T [f(z)] = const
T [f(z)] = a0f(z) Ą anfń(z)
ą
dla z=0 to wewnątrz koła jednostkowego nie leży
żadne zero f(z).
T [f(0)] = a0a0 Ą anan = ja0j2 Ą janj2 2 R
ą ą
18
Jeśli f(z) ma zero wewnątrz koła 4. Jeśli wewnątrz koła jednostkowego nie ma
zera to sprawdzamy funkcję g(2z) (wewnątrz
jz Ą cj = �
koła jednostkowego)
5. Zgodnie z punktami 3 i 4 lokalizujemy zero w
to wielomian � ś pierścieniu
z Ą c
R = 2j � jzj < 2j+1 = 2R
g(z) = f
�
(jeśli zero jest w kole to połowimy jego
ma zero wewnątrz koła jednostkowego. promień tak długo aż zero znajdzie się w
pierścieniu).
Algorytm lokalizacji zer metodą LS: 6. Znaleziony pierścień można pokryć 8 kołami
1. Jeśli f(0)=0 to z=0 jest zerem. Jeśli nie to
4
przechodzimy do 2.
r = R (promien)
5
2. Obliczamy T[f(z)]. Jeśli
3R ź
T [f(0)] < 0 ik
4
Ci = e ; k = 0; 1; : : : ; 7
2cos(ź=8)
to wewnątrz koła jednostkowego leży
pierwiastek. Jeśli nie to przechodzimy do 3.
3. Obliczamy badając każde koło znajdziemy na pewno
j
zero w jednym z nich.
T [f(z)](j = 1; 2; : : :)
7. W wybranym kole (Cj) stosujemy kroki 3-4
aż do uzyskania
(stosując połowienie promienia) i
lokalizujemy zero w pierścieniu
j
T [f(0)] < 0 (j < k)
4 4
1 1
R1 = R2Ąj � jz Ą Cjj < R2Ą(j Ą1) = 2R1
(w kole jednostkowym leży pierwiastek)
5 5
lub
k
T [f(0)] = 0
8. Następnie powtarzamy kroki 6-7
(jeśli Tk-1[f(0)]=const to w kole nie ma
19
pierwiastka)
Inne zero leżące blisko
pierwotnego koła
Rys. Lokalizacja zer w metodzie Lehmera-Schura.
20
Po k krokach zero leży w kole o promieniu 2Rk Metoda A
obaczewskiego (Graeffego)
� śk
2
Dla wielomianu n-tego stopnia w postaci
Rk � R
5
f0(z) = (z Ą �1)(z Ą �2) : : : (z Ą �n)
Własności metody Lehmera-Schura:
można zdefiniować wielomian stopnia 2n
1) Szybkość zbieżności metody jest niewielka
ale nie zależy od krotności pierwiastka
f1(w) = (Ą1)nf0(z)f0(Ąz) =
równania
2) Pozwala lokalizować zera rzeczywiste i
= (w Ą �2)(w Ą �2) : : : (w Ą �2 )
1 2 n
zespolone z zadaną dokładnością
w = z2
3) Po znalezieniu pierwiastka można go
wyrugować z równania dzieląc wielomian
przez odpowiedni dwumian i szukać jego
Zera wielomianu f1 są kwadratami zer f0
kolejne zera
(rozdzielamy zera). Ogólnie można to zapisać
fr+1(w) = (Ą1)nfr(z)fr(Ąz); (r = 0; 1; : : :)
Pomiędzy współczynnikami wielomianów fr+1 oraz fr
zachodzi związek
0 1
minfnĄj;jg
ł �2
X
a(r+1) = (Ą1)nĄj @ a(r) + 2 (Ą1)karĄka(r) A
j
j j j+k
k=1
W metodzie A
obaczewskiego współczynniki
wielomianu fr wykorzystujemy do obliczenia jego
zer. 21
Związek współczynników wielomianu z jego I w granicy
zerami:
r
r r r
lim ja(r) j1=2 = j�1j
nĄ1
ar = (Ą1)nĄjSnĄj(�2 ; �2 ; : : : ; �2 ; )
r!1
j 1 2 n
j = 0; 1; : : : ; n Ą 1
Dla dostatecznie dużego r możemy oszacować
moduł zera (a�1)
gdzie Sk(x1,x2,...,xn) jest k-tą funkcją
r
�1 ź ja(r) j1=2
symetryczną zmiennych x1,x2,...,xn
nĄ1
Dla j=n-2 mamy
Sk(x1; x2; : : : ; xn) =
X
X
r r
= xr xr : : : xr
a(r) = �2 �2 =
1 2 k
nĄ2 r1 r2
1�r11�r12 3
np.: dla j=n-1, k=n-j=1 r
� ś2
X
r r �r �r
7
1 2
= �2 �2 61 +
4 5
1 2
n
ł �
X �1�2
r r r r
1�r1a(r) = ĄS1 �2 ; �2 ; : : : ; �2 = Ą �2
(r1;r2)6=(1;2)
nĄ1 1 2 n k
k=1
r
Ż Ż1=2
Ż
r a(r) Ż
1
Ż Ż
nĄ2
Zera wielomianu możemy zapisać w postaci
�2 ź ja(r) j1=2 ź
Ż Ż
�1 nĄ2 Ż
a(r) Ż
k
nĄ1
�k = �kei' ; k = 1; 2; : : : ; n
i analogicznie dla pozostałych modułów
i załóżmy, że pierwiastki mają różne moduły
�1 > �2 > : : : �n >
r
Ż Ż1=2
Ż
a(r) Ż
Wówczas dla j=n-1 otrzymujemy Ż Ż
nĄk
�k ź ; k = 2; 3; : : : ; n
Ż
"
r
� ś2 #
n
Ża(r) Ż
Ż
X
r
�k
nĄk+1
22
a(r) = Ą�2 1 +
nĄ1 1
�1
k=2
Wartość r określa się empirycznie badając a) Metodę modyfikuje się dla zer zespolonych
stabilizację cyfr znaczących wyznaczanych oraz przypadku gdy pierwiastki równania mają
modułów. identyczne moduły.
b) Szybki wzrost wartości współczynników
Znaki zer wyznacza się określają znak wartości eliminuje się normalizując współczynniki.
wielomianu po podstawieniu do niego
odpowiedniego modułu.
Do wyznaczania zer wielomianów stosuje się też
Przykład. Wyznaczyć zera wielomianu metody Bernoulliego oraz Laguerre'a.
Metoda Laguerre'a jest zbieżna dla zer
z3 Ą 5z2 Ą 17z + 21 = 0
rzeczywistych i wielokrotnych, a rząd zbieżności
wynosi 2. W przypadku pojedynczych zer
r
zespolonych rząd metody wynosi 3.
a(r) a(r) a(r) a(r)
3 2 1 0
1 1 -59 499 -441
2 1 -2483 196963 -194481
Metody dzielenia wielomianów
3 1 -5771363 37828630723 -37822859361
Aby wyznaczyć zera zespolone konieczne jest
przeprowadzenie dzielenia wielomianów
a) przez czynniki liniowe (dwumian)
�1 �2 �3
r
b) przez czynniki kwadratowe (trójmian)
1 7.68 2.91 0.94
Dzielenie wielomianu przez czynnik liniowy
2 7.06 2.98 0.997
3 7.001 2.999 0.99998
Wielomian
Dokładne wartości:
f(z) = anzn + anĄ1znĄ1 + : : : + a0 = 0
�1 = 7
�2 = Ą3 (z Ą zj)
dzielimy przez dwumian:
23
�3 = 1
Wynikiem dzielenia jest Dzieląc jeszcze raz wielomian otrzymamy
Ą
f(z) = (z Ą zj) bnĄ1znĄ1 + bnĄ2znĄ2 Ą
f(z) = (z Ą zj)2 cnĄ2znĄ2 + cnĄ3znĄ3
+ : : : + b0) + Rj
0
+ : : : + c0) + Rj(z Ą zj) + Rj
Z porównania współczynników przy jednakowych
potęgach otrzymujemy zależności Wartości współczynników ci wyznaczamy
analogicznie jak w poprzednim przypadku.
an = bnĄ1
anĄ1 = bnĄ2 Ą zjbnĄ1
Obliczanie zer za pomocą iterowanego
dzielenia
.
.
.
Zera wielomianu możemy wyznaczyć
iteracyjnie stosując zmodyfikowane wzory
a1 = b0 Ą zjb1
jednokrokowe np.. metodę siecznych czy
a0 = Rj Ą zjb0
Newtona.
Zatem współczynnki nowego wielomianu można
Kolejne przybliżenia w metodzie siecznych
obliczać rekurencyjnie
wyznaczamy ze wzoru
bn = 0
Rj(zj Ą zjĄ1)
zj+1 = zj Ą
bk = ak+1 + zjbk+1
Rj Ą RjĄ1
k = n Ą 1; n Ą 2; : : : ; 0
oraz w metodzie Newtona
Rj = a0 + zjb0
Rj
zj+1 = zj Ą
0
Rj
24
�n = ąn = 0
Metodę Newtona można jeszcze zmodyfikować
jeśli zauważymy, że Rj=0 gdy zj jest
�k = ak+1 + xj�k+1 Ą yjąk+1;
pierwiastkiem równania. Wtedy kolejne
przybliżenie ma postać
(k = n Ą 1; n Ą 2; : : : ; 0)
a0 a0
zj+1 = Ą = zj Ą zj Ą =
b0 b0
ąnĄ1 = "nĄ1 = �nĄ1 = 0
b0zj + a0 Rj
= zj Ą = zj Ą ąk = xjąk+1 + yj�k+1;
b0 b0
(k = n Ą 2; n Ą 3; : : : ; 0)
Wzór
"k = �k+1 + xj"k+1 Ą yj�k+1
Rj
zj+1 = zj Ą
b0
�nĄ2 = 0
określa metodę Lina, która jest wolniej
zbieżna od metody Newtona (rząd zbieżności
�k = ąk+1 + xj�k+1 + yj"k+1;
p=1). W jednym kroku wymaga ona wykonania
mniej działań niż metoda Newtona. Może być
(k = n Ą 3; n Ą 4; : : : ; 0)
tez rozbieżna.
Rj = bĄ1 = �Ą1 + iąĄ1
Chcąc wyznaczyć pierwiastek zespolony należy
0
wykonywać działana na liczbach zespolonych.
Rj = cĄ1 = "Ą1 + i�Ą1
Ponadto pierwotne przybliżenie pierwiastka
powinno być zespolone.
"Ą1�Ą1 + �Ą1ąĄ1
Postępowanie w przypadku zer
xj+1 = xj Ą
2
zespolonych
"2 + �Ą1
Ą1
zj = xj + iyj
ąĄ1"Ą1 Ą �Ą1�Ą1
yj+1 = yj Ą
bk = �k + iąk 2
"2 + �Ą1
Ą1
25
ck = "k + i�k
Wpływ błędów współczynników
wielomianu podczas wyznaczania zer Okazuje się, że istnieją wielomiany (wysokiego
wielomianów. stopnia) dla których nawet niewielkie zaburzenie
współczynników powoduje duże zmiany wartości zer
Dokładny wielomian (współczynniki bez błędów) (np.. zera rzeczywiste staja się zespolonymi).
Przykład: wielomian Wilkinsona.
F (z) = Anzn + AnĄ1znĄ1 + : : : + A0
oraz wielomian ze współczynnikami Wielomiany takie nazywamy z
le uwarunkowanymi.
zaburzonymi Uzyskanie dokładniejszych przybliżeń zer wielomianu
mozliwe jest wówczas tylko jeśli obliczenia
f(z) = anzn + anĄ1znĄ1 + : : : + a0
wykonywane przy użyciu silniejszej arytmetyki.
błędy współczynników
ąi = Ai Ą ai (i = 0; 1; : : : ; n)
Z0 (dokładne zero) i z0 (obliczone zero) łączy
zależność
Z0 = z0 + "
Po podstawieniu d�i oraz Z0 do F(z) otrzymujemy
n
X
0
i
ąiz0 + "f (z0) ź 0
i=1
Ż Ż
i
ŻPn ąiz0Ż
i=1
" =
0
jf (z0)j
26
Oszacowanie traci sens gdy pochodna jest
bliska 0.