1
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
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 Łobaczewskiego
c) dzielenie wielomianów
d) metoda iterowanego dzielenia
2
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 fx
1
; x
2
; : : : ; x
k
g; x 2 R
3
Uwagi:
1) Nie istnieją wzory pozwalające obliczyć
dokładnie pierwiastki równania – trzeba
używać
schematów iteracyjnych
. Często
w obliczeniach inżynierskich nie jest znana
postać równania nieliniowego.
2) Rozwiązanie problemu uzyskane metodą
iteracyjną będzie przybliżone
(z zadaną dokładnością)
3) Jak w każdej metodzie iteracyjnej, o tym
jak szybko znajdziemy zadowalające
przybliżenie pierwiastka zależeć będzie od
samej metody, od przybliżenia założonego
na starcie oraz od postaci funkcyjnej
równania.
Metoda połowienia (bisekcji)
Rozwiązania szukamy w przedziale, w którym
znajduje się miejsce zerowe funkcji, w tzw.
przedziale izolacji pierwiastka
(wewnątrz
tego przedziału pierwsza pochodna funkcji nie
zmienia znaku). Przedział wyznacza się na
podstawie wykresu funkcji lub w przypadku
wielomianów algebraicznych – analitycznie.
Założenia:
1) w przedziale [a,b] znajduje się dokładnie
jeden pierwiastek
2) Na końcach przedziału wartosci funkcji
mają różne znaki tj.
Algorytm
1. Dzielimy przdział izolacji na pół
2. Sprawdzamy czy spełniony jest warunek
jeśli tak to mamy rozwiązanie, jeśli nie to
przechodzimy do kolejnego puntu
3. z dwóch przedziałów [a,x
1
] oraz [x
1
,b]
wybieramy ten, w którym wartości funkcji
na krańcach przedziałów mają różne znaki
4. Powtarzamy kroki 1-3, co powduje że
długości kolejnych przedziałów maleją
f (a)
¢ f(b) < 0
x
1
=
b + a
2
f (x
1
) = 0
f (x
i
)
¢ f(x
i+1
) < 0
jx
i
¡ x
i+1
j =
1
2
i
(b
¡ a)
4
Lewe krańce przedziałów tworzą ciąg niemalejący
ograniczony z góry. Natomiast prawe tworzą ciąg nie
rosnący ograniczony z dołu. Istnieje ich wspólna
granica w punkcie
. Punkt ten jest poszukiwanym
rozwiązaniem równania nieliniowego.
Przykład. Znaleźć w przedziale [1,2] metodą
połowienia pierwiastek równania
Wewnątrz przedziału wartość pierwszej pochodnej
funkcji jest dodatnia (nie zmienia znaku) – więc jest to
przedział izolacji pierwiastka.
x
3
+ x
2
¡ 3x ¡ 3 = 0
f (x) = x
3
+ x
2
¡ 3x ¡ 3
f (1) =
¡4
f (2) = 3
f (a)
¢ f(b) = f (1)f(2) = ¡12 < 0
x
f(x)
1.0
-4
2.0
3
1.5
-1.874
1.75
0.17187
1.625
-0.94335
1.6875
-0.40942
1.71875
-0.12487
1.73437
0.02198
..............
.............
1.73205
0.0000000
Wyniki kolejnych przybliżeń rozwiązania
Wadą metody wolna zbieżność w otoczeniu
punktu stanowiącego rozwiązanie. Zaletą jest
natomiast niezawodność metody.
5
Wzór iteracyjny.
Jeżeli g(y) stanowi funkcję odwrotną do f(x)
to dla zbioru punktów
funkcję g(y) można przybliżyć (aproksymować)
wielomianem Lagrange'a
Oznaczmy
Jeśli x=a jest rozwiązaniem (pierwiastkiem)
to wówczas y=0
(x
i+1-j
– to wcześniej wyznaczone przybliżenia)
gdzie wielomian l
j
ma postać
Wzór na x
i+1
określa metodę iteracyjną rozwiązywania
równania nieliniowego.
fy
1
; y
2
; : : : ; y
n
g
g(y)
¼
n
X
j=1
l
j
(y)g(y
j
)
x
i+1
¡j
= g(y
j
)
x
i+1
=
n
X
j=1
l
j
(0)x
i+1
¡j
Wzór ten można zapisać w bardziej ogólnej
postaci
który jest
n-punktowym wzorem
iteracyjnym
.
Szczególnym przypadkiem są metody
jednopunktowe wykorzystujące do
znalezienia przybliżenia w i+1 iteracji przy
znajomości przybliżenia wyznaczonego w i-
tym kroku
Zbieżność metody iteracyjnej
Ciąg przybliżeń jest zbieżny gdy
Błąd rozwiązania w i-tej iteracji
W punkcie x=a metoda jest rzędu p, jeśli
istnieje liczba rzeczywista
x
i+1
= F (x
i
; x
i
¡1
; : : : ; x
i
¡n+1
)
x
i+1
= F (x
i
)
"
i+1
= a
¡ x
i+1
lim
i
!1
x
i
= a
p
¸ 1
l
j
=
(y
¡ y
1
) : : : (y
¡ y
j
¡1
)(y
¡ y
j+1
) : : : (y
¡ y
n
)
(y
j
¡ y
1
) : : : (y
j
¡ y
j
¡1
)(y
j
¡ y
j+1
) : : : (y
j
¡ y
n
)
6
lim
i
!1
jx
i+1
¡ aj
jx
i
¡ aj
p
= lim
i
!1
j"
i+1
j
j"
i
j
p
= C
6= 0
dla której zachodzi
Liczbę C nazywamy
stałą asymptotyczną
błędu
Metoda Regula Falsi
W metodzie tej wykorzystuje się założenie
istnienia lokalnej liniowości funkcji (fałszywe,
stąd nazwa). Zakładamy ponadto:
1) w przedziale [a,b] funkcja ma tylko jeden
pierwiastek pojedynczy
2) f(a)f(b)<0
3) funkcja jest klasy C
2
4) pierwsza i druga pochodna nie zmieniają
znaku w przedziale [a,b]
Rys. Idea metody Regula Falsi dla funkcji wypukłej
j"
i+1
j = Cj"
i
j
p
j"j < 1 ) j"
i+1
j << j"
i
j
p
7
Sposób postępowania:
1. przez punkty A i B prowadzimy prostą o
równaniu:
2. punkt x
1
w którym prosta przecina oś 0x
przyjmuje się za pierwsze przybliżenie
szukanego pierwiastka równania:
3. sprawdzamy warunek, czy: f(x
1
)=0, jeśli tak
to przerywamy oblicznia
4. jeśli to sprawdzamy na końcach
którego przedziału ([A,x
1
], [x
1
,B]) wartości
funkcji mają różne znaki – przez te punkty
prowadzimy kolejną prostą powtarzając kroki
1-4
Jeśli w przedziale [A,B]
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
stacjonarnym
Metoda generuje ciąg przybliżeń. Elementy ciągu
można wyznaczyć rekurencyjnie
y
¡ f(a) =
f (b)
¡ f(a)
b
¡ a
(x
¡ a)
x
1
= a
¡
f (a)
f (b)
¡ f(a)
(b
¡ a)
f (x
1
)
6= 0
x
k+1
= x
k
¡
f (x
k
)
f (b)
¡ f(x
k
)
(b
¡ x
k
)
k = 1; 2; 3; : : :
x
0
= a
Błąd przybliżenia szacujemy korzystając z tw.
Lagrange'a o przyrostach:
gdzie:
Ponieważ
więc dostajemy oszacowanie
gdzie
m -oznacza kres dolny pierwszej pochodnej
Błąd bezwzględny można oszacować znając
wartości dwóch kolejnych przybliżeń x
k
i x
k+1
.
Przekształcając wzór rekurencyjny otrzymujemy:
I dodajemy z lewej strony wyraz
f (®) = 0
m = inf
x
2[a;b]
jf
0
(x)
j
¡f(x
k
) =
f (x
k
)
¡ f(b)
x
k
¡ b
(x
k+1
¡ x
k
)
f (®) = 0
f (®)
¡ f(x
k
) =
f (x
k
)
¡ f (b)
x
k
¡ b
(x
k+1
¡ x
k
)
f (x
k
)
¡ f(®) = f
0
(c)(x
k
¡ ®)
c
2 [x
k
; ®]
jx
k
¡ ®j ·
jf(x
k
)
j
m
8
Po zastosowaniu tw. Lagrange'a otrzymujemy:
Następnie przekształcamy do postaci
Dla
gdzie:
kres dolny
kres górny
oszacowanie błędu bezwględnego ma postać
»
k
2 (x
k
; ®)
¹
x
k
2 (x
k
; b)
(®
¡ x
k
)f
0
(»
k
) = (x
k+1
¡ x
k
)f
0
(¹
x
k
)
j® ¡ x
k+1
j =
jf
0
(¹
x
k
)
¡ f
0
(»
k
)
j
jf
0
(»
k
)
j
jx
k+1
¡ x
k
j
jf
0
(x
k
)
¡ f
0
(»
k
)
j · M ¡ m
m = inf
x
2[a;b]
jf
0
(x)
j
M = sup
x
2[a;b]
jf
0
(x)
j
j® ¡ x
k+1
j ·
M
¡ m
m
jx
k+1
¡ x
k
j
Nie znamy wartości m i M. W niewielkim otoczeniu
pierwiastka można pochodną można zastąpić
ilorazem różnicowym:
Metoda Regula Falsi jest zbieżna do dowolnej funkcji
ciągłej w przedziale [a,b] jeśli wartość pierwszej
pochodnej jest ograniczona i różna od zera w
otoczeniu pierwiastka. Obliczenia przerywa się jeśli
dwa kolejne przybliżenia różnią się o mniej niż
założone
. Wadą jest wolna zbieżność ciągu
przybliżeń –
rząd metody p=1
.
j® ¡ x
k+1
j »
¯
¯
¯
¯
f (x
k+1
)
f
0
(x
k+1
)
¯
¯
¯
¯
»
¯
¯
¯
¯
x
k+1
¡ x
k
f (x
k+1
)
¡ f (x
k
)
¯
¯
¯
¯jf(x
k+1
)
j
9
Metoda siecznych
Jest modyfikacją metody Regula Falsi. Prostą
przeprowadza się przez dwa ostatnie
przybliżenia x
k
i x
k-1
(
metoda dwupunktowa
).
Kolejne przybliżenia w metodzie siecznych
wyznacza się według relacji rekurencyjnej:
Zbieżność metody jest znacznie szybsza niż w
metodzie RF. Rząd metody
Należy dodatkowo przyjąć, że |f(x
k
)| mają
tworzyć ciąg wartości malejących. Jeśli w
kolejnej iteracji |f(x
k
)|zaczyna rosnąć, należy
przerwać obliczenia i ponownie wyznaczyć
punkty startowe zawężając przedział izolacji.
Przykład. szukamy dodatniego pierwiastka
równania
p =
1
2
(1 +
p
5)
¼ 1:618
x
k+1
= x
k
¡
f (x
k
)(x
k
¡ x
k
¡1
)
f (x
k
)
¡ f(x
k
¡1
)
f (x) = sin(x)
¡
1
2
x
Regula Falsi
Metoda
siecznych
x
3
1.75960
1.75960
x
4
1.84420
1.93200
x
5
1.87701
1.89242
x
6
1.88895
1.89543
x
7
1.89320
1.89549
x
8
1.89469
x
9
1.89521
x
10
1.89540
x
11
1.89546
x
12
1.89548
x
13
1.89549
x
1
= ¼=2
x
2
= ¼
10
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 x
1
który
stanowi pierwsze przybliżenie rozwiązania
3) sprawdzamy czy f(x
1
)=0, jeśli nie to z tego
punktu prowadzimy kolejną styczną
4) druga styczna przecina oś 0X w punkcie x
2
ktróry stanowi drugie przybliżenie
5) kroki 3-4 powtarzamy iteracyjne aż spełniony
będzie warunek
Równanie stycznej poprowadzonej z punktu B:
i dla y=0, otrzymujemy pierwsze przybliżenie:
y
¡ f(b) = f
0
(b)(x
¡ b)
x
1
= b
¡
f (b)
f
0
(b)
jx
k+1
¡ x
k
j · "
11
Korzystamy z rozwinięcia Taylora:
Gdzie
Wiemy że f(
)=0 , więc po przekształceniu wzoru
Taylora otrzymujemy
Korzystając ze wzoru na pierwsze przybliżenie,
możemy oszacować odległość nowego przybliżenia
od dokładnego rozwiązania:
czyli punkt x
1
leży na prawo od pierwiastka
Natomiast z tw. Lagrange'a wynika że
czyli punkt x
1
leży po lewej stronie punktu B.
Powyższe warunki pokazują, że kolejne iteracje
przybliżają nas do rozwiązania dokładnego
f (®) = f (b) + f
0
(b)(®
¡ b) +
1
2
f
00
(c)(®
¡ b)
2
c
2 [®; b]
® = b
¡
f (b)
f
0
(b)
¡
1
2
f
00
(c)
f
0
(b)
(®
¡ b)
2
®
¡ x
1
=
¡
1
2
f
00
(c)
f
0
(b)
(®
¡ b)
2
< 0
x
1
¡ b = ¡
f (b)
f
0
(b)
< 0
x
1
2 [®; b]
Równanie stycznej w k-tym przybliżeniu
Równanie rekurencyjne na położenie k-tego
przybliżenia pierwiastka równania nieliniowego w
metodzie Newtona jest następujące
Metoda Newtona jest więc
metodą
jednopunktową
.
Oszacowanie błędu przybliżenia w metodzie
Newtona
Rząd zbieżności metody wynosi
p=2
.
y
¡ f(x
k
) = f
0
(x
k
)(x
¡ x
k
)
x
k+1
= x
k
¡
f (x
k
)
f
0
(x
k
)
(k = 1; 2; : : :)
"
i+1
=
¡
f
00
(»)
2f
0
(x
i
)
"
2
i
12
Przykład. Zastosować metodę Newtona do
znalezienia pierwiastka kwadratowego
dodatniej liczby c
Szukamy miejsca zerowego funkcji
Wykorzystujemy relację rekurencyjną
co poprzekształceniu daje
Rozwiązania szukamy w takim przedziale [a,b],
w którym spełnione są warunki
x
2
¡ c = 0
f (x) = x
2
¡ c
f
0
(x) = 2x
x
k+1
= x
k
¡
x
2
k
¡ c
2x
k
0 < a < c
1=2
b >
1
2
(a + c=a)
x
k+1
=
1
2
µ
x
k
+
c
x
k
¶
Poszukiwanie pierwiastków wielokrotnych
równania nieliniowego
def. Liczbę
nazywamy r-krotnym (r
≥ 2 )
pierwiastkiem równania f(x)=0 wtedy i tylko
wtedy, gdy jest (r-1) -krotnym pierwiastkiem
równania:
Metody: połowienia, RF, siecznych nadają się do
poszukiwania pierwiastków tylko o
nieparzystej
krotności
. Rząd metody siecznych obniża się
(wolniejsza zbieżność). Metoda Newtona pozwala
znaleźć pierwiastki o parzystej i nieparzystej
krotności.
Aby utrzymać rząd metody (przyśpieszyć zbieżność)
stosuje się modyfikacje wzorów rekurencyjnych.
a) Znamy krotność r pierwiastka równania.
Wówczas możemy wykorzystać tę informację w
metodzie Newtona
(w praktyce bardzo rzadko znamy wartość r przez co
zastosowanie powyższego wzoru jest mocno
ograniczone)
f
0
(x) = 0
x
k+1
= x
k
¡ r
f (x
k
)
f
0
(x
k
)
13
a
¡ x
k+1
= a
¡ x
k
+ r
f (x
k
)
f
0
(x
k
)
(a
¡ x
k+1
)f
0
(x
k
) = G(x
k
)
Obliczmy różnicę pomiędzy rozwiązaniem
dokładnym a k+1 przybliżeniem
Gdzie
Różniczkujemy G(x) j-krotnie
Wykorzystujemy fakt że a jest pierwiastkiem r-
krotnym
Z rozwinięcia Taylora w punkcie x=a dostajemy
oraz
G(x) = (a
¡ x)f
0
(x) + rf (x)
G
(j)
(x)
=
(a
¡ x)f
(j+1)
(x)
¡ jf
(j)
(x)
+
rf
(j)
(x)
G
(j)
(a)
=
0
(j = 0; 1; : : : ; r)
G
(r+1)
(a)
6= 0
G(x) =
(x
¡ a)
r+1
(r + 1)!
G
(r+1)
(»
1
)
f
0
(x) =
(x
¡ a)
r
¡1
(r
¡ 1)!
f
(r)
(»
2
)
Kombinacja dwóch ostatnich zależności prowadzi do
związku pomiędzy błędami w k i w k+1 iteracji
Ponieważ
Więc metoda Newtona dla pierwiastka krotności r ma
rząd zbieżności
p=2
.
f
(r)
(»
2
)
6= 0
G
(r+1)
(a)
6= 0
"
k+1
=
1
r(r + 1)
G
(r+1)
(»
1
)
f
(r)
(»
2
)
"
2
k
j"
k+1
j
j"
k
j
2
· C
"
k+1
= (a
¡ x
k+1
) =
G(x
k
)
f
0
(x
k
)
14
x
k+1
= x
k
¡ u(x
k
)
x
k
¡ x
k
¡1
u(x
k
)
¡ u(x
k
¡1
)
x
k+1
= x
k
¡
u(x
k
)
u
0
(x
k
)
u
0
(x
k
) = 1
¡
f
00
(x
k
)
f
0
(x
k
)
u(x
k
)
u(x) =
f (x)
f
0
(x)
b) Jeśli wiemy że pierwiastek jest wielokrotny
ale nie znamy jego krotności r wówczas
możemy badać zera funkcji
Funkcja u(x) ma zero krotności 1 w punkcie
x=a. We wzorach iteracyjnych dokonujmey
podstawienia u(x) za f(x)
a) w metodzie siecznych
b) w metodzie Newtona
gdzie:
Przykład. Wyznaczyć dodatni pierwiastek
równania
µ
sin(x)
¡
1
2
x
¶
2
= 0
m. Newtona
m. Newtona - r
m. Newtona - u(x)
x
2
1.78540
2.00000
1.80175
x
3
1.84456
1.90100
1.88963
x
4
1.87083
1.89551
1.89547
x
5
1.88335
1.89549
1.89549
x
6
1.88946
x
7
1.89249
x
8
1.89399
x
9
1.89475
x
10
1.89512
x
11
1.89531
x
12
1.89540
x
13
1.89545
x
14
1.89547
x
15
1.89548
x
16
1.89549
x
1
=
1
2
15
Proces
2
Aitkena
Jeśli metoda jest zbieżna liniowo to można ją w
prosty sposób przyśpieszyć
gdzie |C
i
| dąży do stałej asymptotycznej błędu. Po
wielu iteracjach powinniśmy otrzymać przybliżenie
Zwiększamy indeks i o 1 i eliminujemy stałą
Następnie obliczamy a
Procedurę tę można stosować jedynie dla metod
zbieżnych liniowo, gdy kolejne 3 przybliżenia są
bliskie poszukiwanemu rozwiązaniu.
a
¡ x
i+1
= C
i
(a
¡ x
i
)
(
jC
i
j < 1)
a
¡ x
i+1
¼ ¹
C(a
¡ x
i
);
j ¹
C
j = C
a
¡ x
i+2
a
¡ x
i+1
¼
a
¡ x
i+1
a
¡ x
i
a
¼
x
i
x
i+2
¡ x
2
i+1
x
i+2
¡ 2x
i+1
+ x
i
16
Układy równań nieliniowych
Układ równań nieliniowych
zapisujemy w postaci wektorowej
Dla takiej postaci układu wyprowadza się wzory
iteracyjne. Ogólny wzór iteracyjny
(
wielokrokowy
)
Zakladamy że funkcja wektorowa f ma w
otoczeniu rozwiązania
funkcję odwrotną
Jeśli punkt
jest odwrotny do punktu x (wektora
przybliżonych rozwiązań)
f
j
(x
(1)
; x
(2)
; : : : ; x
(n)
) = 0; (j = 1; 2; : : : ; n)
To można funkcję g(y) rozwinąć w szereg Taylora w
otoczeniu punktu y
i
Gdzie: jest pochodną
cząstkową funkcji h względem zmiennych
w punkcie x
wektor s:
x
(i
1
)
; x
(i
2
)
; : : : ; x
(i
n
)
fff (x
x
x)
=
0
fff
=
(f
1
; f
2
; : : : ; f
n
)
x
x
x
=
(x
(1)
; x
(2)
; ; : : : ; x
(n)
; )
F
F
F = (F
1
; F
2
; : : : ; F
n
)
®
®
® = (®
1
; ®
2
; : : : ; ®
n
)
ggg = (g
1
; g
2
; : : : ; g
n
)
yyy = (y
(1)
; y
(2)
; : : : ; y
(n)
; )
x
x
x = ggg(yyy) = ggg(yyy
i
) +
m+1
X
j=1
1
j!
d
j
ggg(yyy
i
; yyy
¡ yyy
i
)
+
1
(m + 2)!
d
m+2
ggg(»»»; yyy
¡ yyy
i
)
»»»
2 [yyy; yyy
i
]
d
j
h(x
x
x; sss) =
n
X
i
1
=1
n
X
i
2
=1
: : :
n
X
i
j
=1
D
i
1
;i
2
;:::;i
j
h(x
x
x)s
i
1
s
i
2
: : : s
i
j
D
i
1
;i
2
;:::;i
j
h(x
x
x)
sss = (s
i
1
; s
i
2
; : : : ; s
i
j
)
x
x
x
i+1
= F
F
F (x
x
x
i
; x
x
x
i
¡1
; : : : ; x
x
x
i
¡n+1
)
17
Szukane rozwiązanie ma postać
Po odrzuceniu reszty w rozwinięciu Taylora i
uwzględnieniu powyższego warunku otrzymujemy
n-wymiarowy odpowiednik metody Newtona.
Dla m=0 (
metoda jednokrokowa
)
Pochodne funkcji g można wyrazic poprzez
pochodne funkcji f. Dla n=2 otrzymujemy
Rząd zbieżności metody wynosi 2. Zazwyczaj
zbieżność uzyskujemy tylko jeśli startujemy już z
dobrym przybliżeniem rozwązania.
®
®
® = ggg(000)
) yyy = 000
Problem poszukiwania rozwiązań układu równań
nieliniowych można sformułować jako problem
poszukiwania minimum poniższej fukcji
Funkcja osiąga minimum globalne dla dokładnego
rozwiązania x. Do jego znalezienia można użyć
metody największego spadku (minimalizacja
wartości funkcji)
.
©(x
x
x) =
n
X
i=1
f
2
i
(x
x
x)
x
x
x
i+1
= x
x
x
i
¡
1
J
2
4
@f
2
@x
(2)
@f
1
@x
(2)
¡
@f
2
@x
(1)
@f
1
@x
(1)
3
5
2
4
f
1
f
2
3
5
x
x
x=x
x
x
i
J =
2
4
@f
1
@x
(1)
@f
1
@x
(2)
@f
2
@x
(1)
@f
2
@x
(2)
3
5
x
x
x
i+1
= x
x
x
i
+ dggg(yyy
i
;
¡yyy
i
) =
= x
x
x
i
¡
n
X
j=1
@ggg(yyy
i
)
@y
j
y
(j)
i
18
Wyznaczanie zer wielomianów
Szukamy zer rzeczywistych i zespolonych
wielomianu
Metoda Lehmera-Schura
Dla pierwotnego wielomianu f(z) definiujemy
wielomian
(kreska pozioma – sprzężenie zespolone)
i wprowadzamy operator T
dla z=0
f (z) = a
n
z
n
+ a
n
¡1
z
n
¡1
+ : : : + a
0
= 0
z
2 C
a
i
2 R; (i = 0; 1; : : : ; n)
f
¤
(z) = z
n
¹
f (¹
z
¡1
) = ¹
a
n
+ ¹
a
n
¡1
z + : : : + ¹
a
0
z
0
T [f (z)] = ¹
a
0
f (z)
¡ a
n
f
¤
(z)
T [f (0)] = ¹
a
0
a
0
¡ ¹a
n
a
n
=
ja
0
j
2
¡ ja
n
j
2
2 R
Operator T działając na f(z) obniża stopień
wielomianu o 1. Działając nim wielokrotnie na f(z)
otrzymamy ciąg wielomianów corza niższego
stopnia.
Tw. Jeśli dla
istnieje takie h, że
to f(z) ma co najmniej jedno zero wewnątrz
koła jednostkowego.
Jeśli
to wewnątrz koła jednostkowego nie leży
żadne zero f(z).
T
j
[f (z)] = T
£
T
j
¡1
[f (z)]
¤
f (0)
6= 0
T
h
[f (0)] < 0
0 < h < k; h; k
2 Z
k = min
f1; 2; : : : ; ng $ T
k
[f (0)] = 0
T
i
[f (0)] > 0; 1
· i < k
T
k
¡1
[f (z)] = const
19
T [f (0)] < 0
T
j
[f (z)](j = 1; 2; : : :)
T
j
[f (0)] < 0 (j < k)
T
k
[f (0)] = 0
Jeśli f(z) ma zero wewnątrz koła
to wielomian
ma zero wewnątrz koła jednostkowego.
Algorytm lokalizacji zer metodą LS:
1. Jeśli f(0)=0 to z=0 jest zerem. Jeśli nie to
przechodzimy do 2.
2. Obliczamy T[f(z)]. Jeśli
to wewnątrz koła jednostkowego leży
pierwiastek. Jeśli nie to przechodzimy do 3.
3. Obliczamy
aż do uzyskania
(w kole jednostkowym leży pierwiastek)
lub
(jeśli T
k-1
[f(0)]=const to w kole nie ma
pierwiastka)
jz ¡ cj = ½
4. Jeśli wewnątrz koła jednostkowego nie ma
zera to sprawdzamy funkcję g(2z) (wewnątrz
koła jednostkowego)
5. Zgodnie z punktami 3 i 4 lokalizujemy zero w
pierścieniu
(jeśli zero jest w kole to połowimy jego
promień tak długo aż zero znajdzie się w
pierścieniu).
6. Znaleziony pierścień można pokryć 8 kołami
badając każde koło znajdziemy na pewno
zero w jednym z nich.
7. W wybranym kole (C
j
) stosujemy kroki 3-4
(stosując połowienie promienia) i
lokalizujemy zero w pierścieniu
8. Następnie powtarzamy kroki 6-7
R = 2
j
· jzj < 2
j+1
= 2R
r =
4
5
R
(promien)
C
i
=
3R
2cos(¼=8)
e
¼
4
ik
; k = 0; 1; : : : ; 7
R
1
=
4
5
R2
¡j
1
· jz ¡ C
j
j <
4
5
R2
¡(j
1
¡1)
= 2R
1
g(z) = f
µ
z
¡ c
½
¶
20
Rys. Lokalizacja zer w metodzie Lehmera-Schura.
Inne zero leżące blisko
pierwotnego koła
21
Po k krokach zero leży w kole o promieniu 2R
k
Własności metody Lehmera-Schura:
1) Szybkość zbieżności metody jest niewielka
ale nie zależy od krotności pierwiastka
równania
2) Pozwala lokalizować zera rzeczywiste i
zespolone z zadaną dokładnością
3) Po znalezieniu pierwiastka można go
wyrugować z równania dzieląc wielomian
przez odpowiedni dwumian i szukać jego
kolejne zera
R
k
·
µ
2
5
¶
k
R
Metoda Łobaczewskiego (Graeffego)
Dla wielomianu n-tego stopnia w postaci
można zdefiniować wielomian stopnia 2n
Zera wielomianu f
1
są kwadratami zer f
0
(
rozdzielamy zera
). Ogólnie można to zapisać
Pomiędzy współczynnikami wielomianów f
r+1
oraz f
r
zachodzi związek
W metodzie Łobaczewskiego współczynniki
wielomianu f
r
wykorzystujemy do obliczenia jego
zer.
f
0
(z) = (z
¡ ®
1
)(z
¡ ®
2
) : : : (z
¡ ®
n
)
f
1
(w) = (
¡1)
n
f
0
(z)f
0
(
¡z) =
= (w
¡ ®
2
1
)(w
¡ ®
2
2
) : : : (w
¡ ®
2
n
)
w = z
2
f
r+1
(w) = (
¡1)
n
f
r
(z)f
r
(
¡z); (r = 0; 1; : : :)
a
(r+1)
j
= (
¡1)
n
¡j
0
@
³
a
(r)
j
´
2
+ 2
min
fn¡j;jg
X
k=1
(
¡1)
k
a
r
j
¡k
a
(r)
j+k
1
A
22
Związek współczynników wielomianu z jego
zerami:
gdzie S
k
(x
1
,x
2
,...,x
n
) jest k-tą funkcją
symetryczną zmiennych x
1
,x
2
,...,x
n
np.: dla j=n-1, k=n-j=1
Zera wielomianu możemy zapisać w postaci
i załóżmy, że pierwiastki mają różne moduły
Wówczas dla j=n-1 otrzymujemy
a
r
j
= (
¡1)
n
¡j
S
n
¡j
(®
2
r
1
; ®
2
r
2
; : : : ; ®
2
r
n
; )
j = 0; 1; : : : ; n
¡ 1
S
k
(x
1
; x
2
; : : : ; x
n
) =
=
X
1
·r
1
<r
2
<:::<r
k
·n
x
r
1
x
r
2
: : : x
r
k
a
(r)
n
¡1
=
¡S
1
³
®
2
r
1
; ®
2
r
2
; : : : ; ®
2
r
n
´
=
¡
n
X
k=1
®
2
r
k
®
k
= ½
k
e
i'
k
; k = 1; 2; : : : ; n
½
1
> ½
2
> : : : ½
n
>
a
(r)
n
¡1
=
¡®
2
r
1
"
1 +
n
X
k=2
µ
®
k
®
1
¶
2
r
#
I w granicy
Dla dostatecznie dużego r możemy oszacować
moduł zera (
1
)
Dla j=n-2 mamy
i analogicznie dla pozostałych modułów
lim
r
!1
ja
(r)
n
¡1
j
1=2
r
=
j®
1
j
½
1
¼ ja
(r)
n
¡1
j
1=2
r
a
(r)
n
¡2
=
X
1
·r
1
<r
2
·n
®
2
r
r
1
®
2
r
r
2
=
= ®
2
r
1
®
2
r
2
2
6
41 +
X
1
·r1<r2·n
(r1;r2)6=(1;2)
µ
®
r
1
®
r
2
®
1
®
2
¶
2
r
3
7
5
½
2
¼
1
½
1
ja
(r)
n
¡2
j
1=2
r
¼
¯
¯
¯
¯
¯
a
(r)
n
¡2
a
(r)
n
¡1
¯
¯
¯
¯
¯
1=2
r
½
k
¼
¯
¯
¯
¯
¯
a
(r)
n
¡k
a
(r)
n
¡k+1
¯
¯
¯
¯
¯
1=2
r
; k = 2; 3; : : : ; n
23
Wartość r określa się empirycznie badając
stabilizację cyfr znaczących wyznaczanych
modułów.
Znaki zer wyznacza się określają znak wartości
wielomianu po podstawieniu do niego
odpowiedniego modułu.
Przykład. Wyznaczyć zera wielomianu
z
3
¡ 5z
2
¡ 17z + 21 = 0
r
1
1
-59
499
-441
2
1
-2483
196963
-194481
3
1
-5771363 37828630723
-37822859361
a
(r)
3
a
(r)
2
a
(r)
1
a
(r)
0
r
1
7.68
2.91
0.94
2
7.06
2.98
0.997
3
7.001
2.999
0.99998
½
1
½
2
½
3
Dokładne wartości:
®
1
= 7
®
2
=
¡3
®
3
= 1
a) Metodę modyfikuje się dla zer zespolonych
oraz przypadku gdy pierwiastki równania mają
identyczne moduły.
b) Szybki wzrost wartości współczynników
eliminuje się normalizując współczynniki.
Do wyznaczania zer wielomianów stosuje się też
metody Bernoulliego oraz Laguerre'a.
Metoda Laguerre'a jest zbieżna dla zer
rzeczywistych i wielokrotnych, a rząd zbieżności
wynosi 2. W przypadku pojedynczych zer
zespolonych rząd metody wynosi 3.
Metody dzielenia wielomianów
Aby wyznaczyć zera zespolone konieczne jest
przeprowadzenie dzielenia wielomianów
a) przez czynniki liniowe (dwumian)
b) przez czynniki kwadratowe (trójmian)
Dzielenie wielomianu przez czynnik liniowy
Wielomian
dzielimy przez dwumian:
f (z) = a
n
z
n
+ a
n
¡1
z
n
¡1
+ : : : + a
0
= 0
(z
¡ z
j
)
24
Wynikiem dzielenia jest
Z porównania współczynników przy jednakowych
potęgach otrzymujemy zależności
Zatem współczynnki nowego wielomianu można
obliczać rekurencyjnie
a
n
=
b
n
¡1
a
n
¡1
=
b
n
¡2
¡ z
j
b
n
¡1
..
.
a
1
=
b
0
¡ z
j
b
1
a
0
=
R
j
¡ z
j
b
0
b
n
=
0
b
k
=
a
k+1
+ z
j
b
k+1
k
=
n
¡ 1; n ¡ 2; : : : ; 0
R
j
=
a
0
+ z
j
b
0
Dzieląc jeszcze raz wielomian otrzymamy
Wartości współczynników c
i
wyznaczamy
analogicznie jak w poprzednim przypadku.
Obliczanie zer za pomocą iterowanego
dzielenia
Zera wielomianu możemy wyznaczyć
iteracyjnie stosując zmodyfikowane wzory
jednokrokowe np.. metodę siecznych czy
Newtona.
Kolejne przybliżenia w metodzie siecznych
wyznaczamy ze wzoru
oraz w metodzie Newtona
z
j+1
= z
j
¡
R
j
(z
j
¡ z
j
¡1
)
R
j
¡ R
j
¡1
z
j+1
= z
j
¡
R
j
R
0
j
f (z)
=
(z
¡ z
j
)
¡
b
n
¡1
z
n
¡1
+ b
n
¡2
z
n
¡2
+
: : : + b
0
) + R
j
f (z)
=
(z
¡ z
j
)
2
¡
c
n
¡2
z
n
¡2
+ c
n
¡3
z
n
¡3
+
: : : + c
0
) + R
0
j
(z
¡ z
j
) + R
j
25
Metodę Newtona można jeszcze zmodyfikować
jeśli zauważymy, że R
j
=0 gdy z
j
jest
pierwiastkiem równania. Wtedy kolejne
przybliżenie ma postać
Wzór
określa
metodę Lina
, która jest wolniej
zbieżna od metody Newtona (rząd zbieżności
p=1). W jednym kroku wymaga ona wykonania
mniej działań niż metoda Newtona. Może być
tez rozbieżna.
Chcąc wyznaczyć pierwiastek zespolony należy
wykonywać działana na liczbach zespolonych.
Ponadto pierwotne przybliżenie pierwiastka
powinno być zespolone
.
Postępowanie w przypadku zer
zespolonych
z
j+1
=
¡
a
0
b
0
= z
j
¡ z
j
¡
a
0
b
0
=
=
z
j
¡
b
0
z
j
+ a
0
b
0
= z
j
¡
R
j
b
0
z
j+1
= z
j
¡
R
j
b
0
z
j
= x
j
+ iy
j
b
k
= °
k
+ i±
k
c
k
= "
k
+ i´
k
°
n
=
±
n
= 0
°
k
=
a
k+1
+ x
j
°
k+1
¡ y
j
±
k+1
;
(k = n
¡ 1; n ¡ 2; : : : ; 0)
±
n
¡1
=
"
n
¡1
= ´
n
¡1
= 0
±
k
=
x
j
±
k+1
+ y
j
°
k+1
;
(k = n
¡ 2; n ¡ 3; : : : ; 0)
"
k
=
°
k+1
+ x
j
"
k+1
¡ y
j
´
k+1
´
n
¡2
=
0
´
k
=
±
k+1
+ x
j
´
k+1
+ y
j
"
k+1
;
(k = n
¡ 3; n ¡ 4; : : : ; 0)
R
j
= b
¡1
= °
¡1
+ i±
¡1
R
0
j
= c
¡1
= "
¡1
+ i´
¡1
x
j+1
= x
j
¡
"
¡1
°
¡1
+ ´
¡1
±
¡1
"
2
¡1
+ ´
2
¡1
y
j+1
= y
j
¡
±
¡1
"
¡1
¡ °
¡1
´
¡1
"
2
¡1
+ ´
2
¡1
26
Wpływ błędów współczynników
wielomianu podczas wyznaczania zer
wielomianów.
Dokładny wielomian (współczynniki bez błędów)
oraz wielomian ze współczynnikami
zaburzonymi
błędy współczynników
Z
0
(dokładne zero) i z
0
(obliczone zero) łączy
zależność
Po podstawieniu
i
oraz Z
0
do F(z) otrzymujemy
Oszacowanie traci sens gdy pochodna jest
bliska 0.
F (z) = A
n
z
n
+ A
n
¡1
z
n
¡1
+ : : : + A
0
Z
0
= z
0
+ "
±
i
= A
i
¡ a
i
(i = 0; 1; : : : ; n)
Okazuje się, że istnieją wielomiany (wysokiego
stopnia) dla których nawet niewielkie zaburzenie
współczynników powoduje duże zmiany wartości zer
(np.. zera rzeczywiste staja się zespolonymi).
Przykład: wielomian Wilkinsona.
Wielomiany takie nazywamy źle uwarunkowanymi.
Uzyskanie dokładniejszych przybliżeń zer wielomianu
mozliwe jest wówczas tylko jeśli obliczenia
wykonywane przy użyciu silniejszej arytmetyki.
f (z) = a
n
z
n
+ a
n
¡1
z
n
¡1
+ : : : + a
0
n
X
i=1
±
i
z
i
0
+ "f
0
(z
0
)
¼ 0
" =
¯
¯P
n
i=1
±
i
z
i
0
¯
¯
jf
0
(z
0
)
j
Document Outline