Metody numeryczne
dr inż. Anna Barcz
Zakład Metod Matematycznych
kontakt: pokój 28
[e-mail]
1
Równania nieliniowe
Dla danej funkcji rzeczywistej jednej zmiennej znalez
ć wartości x,
dla której
f śąxźą=0
w praktyce:
dopuszczamy pewną tolerancję, uwzględniając precyzję
arytmetyki, np. dla µ =2-24
#" f śą xźą#""ą10-5
2
Równania nieliniowe
Metody:
połowienia (bisekcji),
regula falsi,
siecznych (ulepszenie metody regula falsi),
stycznych (metoda Newtona),
iteracyjne.
3
Równania nieliniowe
Przedział izolacji pierwiastka - jeżeli funkcja f(x) jest ciągła i ma na
końcach przedziału [a, b] przeciwne znaki, to w przedziale [a, b] leży
co najmniej jeden jej pierwiastek.
f śąaźąÅ"f śąbźą"Ä…0
w praktyce:
rezygnujemy z mnożenia z powodu możliwości wystąpienia
nadmiaru albo niedomiaru i sprawdzamy
sgnśąaźą`"sgnśąbźą
4
Równania nieliniowe
Twierdzenie Bolzano
Jeśli funkcja f(x) jest ciągłą i oznaczoną w przedziale [a, b] i jej wartości na
końcach przedziału mają różne znaki, to istnieje co najmniej jeden punkt c,
dla którego f(c)=0,
f śącźą=0 i a"ąc"ąb
Twierdzenie Bolzano  Cauchy'ego
Jeśli funkcja f(x,y) ciągła i oznaczona w obszarze spójnym przyjmuje w
dwóch jego punktach (x1, y1) i (x2, y2) wartości o przeciwnych znakach, to
istnieje taki jeden punkt (x3, y3) w tym obszarze, dla którego f(x3, y3)=0,
f śąx3 , y3źą=0, jeśli f śąx1 , y1źąą0 i f śąx2 , y2źą"ą0
5
Równania nieliniowe  przedział izolacji
Y Y
f(b)
f(b)
a
b a b
X X
f(a)
f(a)
6
Równania nieliniowe  warunki zatrzymania algorytmów
#"f śą xźą#""Ä…ÏÄ…
#"xkƒÄ…1-xk#""Ä…ºÄ…
wykonanie przewidzianej liczby iteracji
7
Równania nieliniowe  metoda połowienia (bisekcji)
Metoda połowienia  założenia:
funkcja f(x) ciągła w przedziale [a,b],
przedział [a,b] jest przedziałem izolacji pierwiastka
8
Równania nieliniowe  metoda połowienia (bisekcji)
Metoda polega na dzieleniu przedziału izolacji pierwiastka na połowę
i sprawdzaniu znaku iloczynu wartości funkcji na końcach dwóch
nowo powstałych podprzedziałów.
aƒÄ…b
x=
2
Wybierany jest ten, w którym znajduje się pierwiastek. Czynność ta
powtarzana jest aż do znalezienia rozwiązania.
w praktyce:
b-a
x=aƒÄ…
2
9
Równania nieliniowe  metoda połowienia (bisekcji)
Y
f(b)
f(x)
f(x1)
a x1
b
X
aƒÄ…b
x1=
f śąaźąÅ"f śą x1źą"Ä…0 b=x1
2
f(a)
10
Równania nieliniowe  metoda połowienia (bisekcji)
Y
f(x)
f(b)
x2
a
b
X
f(x2)
f(a)
aƒÄ…b
x2=
f śąx2źąÅ"f śąbźą"Ä…0 a=x2
2
11
Równania nieliniowe  metoda połowienia (bisekcji)
Y
f(x)
f(b)
f(x3)
a x3 b
X
f(a)
aƒÄ…b
x3=
f śąaźąÅ"f śą x3źą"Ä…0 b=x3
2
12
Równania nieliniowe  metoda połowienia (bisekcji)
Y
f(b)
f(x)
f(x1)
f(x3)
x2
a x3 x1
b
X
f(x2)
aƒÄ…b
x1=
f śąaźąÅ"f śą x1źą"Ä…0 b=x1
2
f(a)
aƒÄ…b
x2=
f śąx2źąÅ"f śąbźą"Ä…0 a=x2
2
aƒÄ…b
x3=
f śąaźąÅ"f śą x3źą"Ä…0 b=x3
2
13
Równania nieliniowe  zbieżność metody połowienia
[a0,b0], [a1,b1], ... - kolejne otrzymywane przedziały
a0Ä…Ä…a1Ä…Ä…a2Ä…Ä…‹Ä…Ä…Ä…b0
b0‡Ä…b1‡Ä…b2‡Ä…‹Ä…‡Ä…a0
1
bkƒÄ…1-ak ƒÄ…1= śąbk-akźą , k‡Ä…0
2
bk-ak=2-k śąb0-a0źą
Ciągi {ak} i {bk} jako niemalejące i ograniczone z góry są zbieżne.
14
Równania nieliniowe  zbieżność metody połowienia
bk-ak=2-k śąb0-a0źą
lim bk-lim ak=lim 2-k śąb0-a0źą=0
k Śą" k Śą" k Śą"
r=lim bk=lim ak
k Śą " k Śą"
15
Równania nieliniowe  zbieżność metody połowienia
Twierdzenie
Jeśli przedziały [a0,b0], [a1,b1] ... są tworzone metodą połowienia, to
granice
lim bk i lim ak
k Śą" k Śą"
istnieją, są identyczne i równe zeru funkcji f.
1
ck= śąakƒÄ…bkźą
Jeśli , gdzie to
r=lim ck
2
k Śą "
#"r-ck#"‡Ä…2-śąkƒÄ…1źąśąb0-a0źą
16
Równania nieliniowe  zbieżność metody połowienia
w każdym kroku zyskujemy jedną dokładną cyfrę dwójkową,
jedną cyfrę dziesiętną zyskuje się średnio co 3,3 kroków,
szybkość zbieżności nie zależy od funkcji f.
17
Równania nieliniowe  metoda połowienia (bisekcji)
Przykład
Niech metoda połowienia startuje od przedziału [50, 63]. Ile najwyżej kroków
trzeba wykonać, aby otrzymać pierwiastek z błędem względnym 10-12?
#"r-ck#"
błąd względny
Ä…Ä…10-12
#"r#"
#"r-ck#"
wiemy, że re" 50
‡Ä…10-12
50
na podstawie twierdzenia, wystarczy aby było
2-śąk ƒÄ…1źąÅ"63-50 ‡Ä…10-12
50
Warunek jest spełniony dla ke"37.
18
Równania nieliniowe  metoda połowienia (bisekcji)
Inne zastosowanie
przeszukiwanie uporzÄ…dkowanego wykazu (listy)
uporzÄ…dkowanie alfabetyczne,
uporządkowanie według numerów  przeszukiwanie
logarytmiczne
'
n-tÄ… liczbÄ™ w wykazie oznaczamy jako f(n),
'
f jest funkcją rosnącą i nieciągłą,
'
poszukiwanie w wykazie pewnej liczby a oznacza rozwiÄ…zanie
równania f(n)=a
19
Równania nieliniowe  metoda regula falsi
Metoda fałszywego założenia liniowości funkcji.
Założenia:

w przedziale [a,b] równanie ma dokładnie jeden pierwiastek
pojedynczy,

f(a)f(b)<0

f(x) na przedziale [a,b] jest funkcjÄ… klasy C2,

pierwsza i druga pochodna mają stały znak na przedziale [a,b]
20
Równania nieliniowe  zbieżność metody regula falsi
Punkt stały xs  punkt, w którym f(x) i f''(x) mają ten sam znak.
xs=b Śą x0=a xs=a Śą x0=b
x =b Śą x0=a
s
Ciąg {x1,x2, ... , xn, ...} jest rosnący i ograniczony, a więc jest
zbieżny. Jego granicą jest szukany pierwiastek.
zbieżność liniowa.
21
Równania nieliniowe  metoda regula falsi
Y
f ' śąxźą"ą0, f ' ' śąxźą"ą0 f ' śąxźą"ą0, f ' ' śąxźąą0
Y
f(a)
f(a)
a b
X
a b
X
f(b)
f(b)
f ' śąxźąą0, f ' ' śąxźą"ą0 f ' śąxźąą0, f ' ' śąxźąą0
Y
Y
f(b)
f(b)
a b
X
a b
X
f(a)
f(a)
22
Równania nieliniowe  metoda regula falsi
punkt stały
Y
f(b)
f(x)
a (x0) x2 x3 b
x1
X
f(x3)
f(x2)
f(x1)
f(a)
f(x0)
23
Równania nieliniowe  metoda regula falsi
punkt stały
Y
f(b)
f(x)
x1 x2 x3
x4
a b
X
f(x1) f(x2) f(x3)
f(x4)
f(a)
24
Równania nieliniowe  zbieżność metody regula falsi
Błąd n-tego przybliżenia na podstawie twierdzenia Lagrange'a
(o przyrostach)
f śąxnźą- f śąrźą= f ' śącźąśąxn-rźą
c jest zawarte w przedziale [xn, r],
r  pierwiastek równania
Ponieważ f(r)=0, więc
#" f śą xnźą#"
#"xn-r#"ąą , m= inf #" f ' śąxźą#"
m
x")# a , b*#
25
Równania nieliniowe  metoda siecznych
Założenia:

w przedziale [a,b] równanie ma dokładnie jeden pierwiastek
pojedynczy,

f(a)f(b)<0

f(x) na przedziale [a,b] jest funkcjÄ… klasy C2,

pierwsza i druga pochodna mają stały znak na przedziale [a,b],
26
Równania nieliniowe  metoda siecznych
punkt stały w 1 kroku
Y
f(b)
f(x)
f(x2)
x3
a x2 b
(x0)
x1
X
f(x3)
f(x1)
f(a)=f(x0)
27
Równania nieliniowe  metoda siecznych
punkt stały w 1 kroku
Y
f(b)
a
(x0)
b
x1
X
f(x)
f(x1)
f(a)=f(x0)
28
Równania nieliniowe  zbieżność metody siecznych
Pierwszy krok obliczamy na podstawie metody regula falsi.
f śą xkźą
xkƒÄ…1=xk- Å"śą xk-1-xkźą , k=1,2 ,‹Ä…, n
f śą xkźą- f śą xk-1źą
Ciąg {x1,x2, ... , xn, ...} jest rosnący i ograniczony, a więc jest
zbieżny. Jego granicą jest szukany pierwiastek.
zbieżność nadliniowa
29
Równania nieliniowe  metoda stycznych (Newtona)
Założenia:

w przedziale [a,b] równanie ma dokładnie jeden pierwiastek
pojedynczy,

f(a)f(b)<0

f(x) na przedziale [a,b] jest funkcjÄ… klasy C2,

pierwsza pochodna różna od zera na przedziale [a,b],

druga pochodna ma stały znak na przedziale [a,b]
30
Równania nieliniowe  metoda stycznych
Y
f(b)
f(x0)
f(x)
f(x1)
f(x2)
f(x3)
a
x3 x2
x1
b=x0
X
f(a)
31
Równania nieliniowe  metoda stycznych
32
Równania nieliniowe  zbieżność metody stycznych
f śą xkźą
xkƒÄ…1=xk- , k =1,2 ,‹Ä… , n
f ' śą xkźą
x0  punkt, w którym f(x) i f ''(x) mają ten sam znak.
zbieżność kwadratowa
Twierdzenie
Jeśli f należy do C2(R), jest rosnąca, wypukła i ma zero, to jest ono
jedyne, a metoda Newtona daje ciąg do niego zbieżny dla dowolnego
punktu poczÄ…tkowego.
33
Równania nieliniowe  zbieżność metody stycznych
Twierdzenie
Niech r będzie zerem pojedynczym funkcji f i niech jej druga
pochodna f '' będzie ciągła. Wtedy istnieje takie otoczenie punktu r i
taka stała C, że jeśli metoda Newtona startuje z tego otoczenia, to
kolejne punkty są coraz bliższe r i takie, że
#"xkƒÄ…1-r#"Ä…Ä…#"C śą xk-rźą2#", k‡Ä…0
34
Równania nieliniowe  metoda stycznych
Przykład
Znajdz
wzór na obliczanie pierwiastka kwadratowego z dowolnej dodatniej liczby c.
x= c Śą x2=c Śą x2-c=0
ćą
f śąxźą=x2-c , f ' śąxźą=2Å"x
1
c
xkƒÄ…1= xkƒÄ…
śą źą
2 xk
wzór Herona, greckiego inżyniera i architekta, żył między 100 rokiem p.n.e i
100 rokiem n.e
35
Równania nieliniowe  metody iteracyjne
Niech xk+1 wyraża się przez wartość funkcji f(x) i jej pochodnych w m
punktach, wtedy
xkƒÄ…1=Ôąśą xk , xk-1 ,‹Ä… , xk -mƒÄ…1źą
ÔÄ…
i nazywamy funkcjÄ… iteracyjnÄ….
Szczególne przypadki metod iteracyjnych:
metoda Newtona, m=1
metoda siecznych, m=2
36
Obliczanie pierwiastków wielomianów
pśą zźą=an znƒÄ…an-1 an-1ƒÄ…‹Ä…ƒÄ…a1 zƒÄ…a0
ak i zmienna z mogą być zespolone
Twierdzenie
Każdy wielomian różny od stałej ma co najmniej jeden pierwiastek w
ciele C liczb zespolonych.
37
Obliczanie pierwiastków wielomianów
CiÄ…g Sturma
f śą xźąa" f śą xźą
0
f śąxźą= f ' śą xźą
1
f śą xźą
reszta z dzielenia f0(x) przez f1(x) wzięta ze znakiem przeciwnym
2
reszta z dzielenia f1(x) przez f2(x) wzięta ze znakiem przeciwnym
f śąxźą
3
...........................................................................................................
f śą xźąa"0
pƒÄ…1
fp (x) ostatnia reszta z dzielenia różna od zera,
38
Obliczanie pierwiastków wielomianów
Twierdzenie Sturma
Jeżeli ciąg fi(x) jest ciągiem Sturma na przedziale [a,b] i f0(x)f0(b)`"0,
to liczba różnych zer rzeczywistych wielomianu f0(x) leżących w tym
przedziale jest równa N(a)-N(b).
N(x0)  liczba zmian znaku w ciągu Sturma, w punkcie x=x0, w którym opuszczamy
zera.
Inne twierdzenia o istnieniu pierwiastków rzeczywistych
twierdzenie Fouriera,
twierdzenie Laguerr'a,
reguła Kartezjusza.
39
Obliczanie pierwiastków wielomianów
Przykład - twierdzenie Sturma
Wyznaczyć w przedziale <0,2> liczbę pierwiastków podanego równania.
x4-5 x2ƒÄ…8 x-8=0
Podstawiamy x=0 i otrzymujemy ciÄ…g:
Obliczamy funkcje Sturma:
-8,ƒÄ…8,ƒÄ…16,ƒÄ…284,-1
P śą xźą=P0śą xźą=x4-5 x2ƒÄ…8 x-8
Podstawiamy x=2 i otrzymujemy ciÄ…g:
P ' śą xźą=P1śą xźą=4 x3-10 xƒÄ…8
ƒÄ…4,ƒÄ…20,ƒÄ…12,ƒÄ…278,-1
P2śą xźą=5 x2-12 xƒÄ…16
Liczba zmian znaku: A=2, B=1
P3śą xźą=-3 xƒÄ…284
P4śą xźą=-1
Liczba pierwiastków = A-B =1
40
Obliczanie pierwiastków wielomianów
Deflacja
obniżanie stopnia wielomianu,
zmniejszenie liczby operacji arytmetycznych,
nie wyznaczamy ponownie tego samego pierwiastka (chyba, że
jest wielokrotny)
Zalecenia
pierwiastki wyznacza się w kolejności rosnących modułów,
każdy pierwiastek wyznacza się z graniczną dokładnością.
41
Metoda Newtona w dziedzinie zespolonej
Niech p będzie wielomianem stopnia co najmniej drugiego i niech e
będzie jednym z jego pierwiastków. Metoda Newtona startująca z
punktu z płaszczyzny zespolonej tworzy ciąg
pśą znźą
z0=z , znƒÄ…1=zn- , n‡Ä…0
p ' śą znźą
lim zn=e
Jeśli to punkt początkowy z jest przyciągany przez e.
n Śą"
Zbiór wszystkich punktów z przyciąganych przez e nazywamy
zbiorem przyciÄ…gania dla e.
42
Metoda Newtona w dziedzinie zespolonej
każdy pierwiastek ma swój zbiór przyciągania,
zbiory są parami rozłączne,
pewne liczby zespolone nie należą do żadnego zbioru
przyciągania  punkty początkowe, dla których metoda Newtona
nie jest zbieżna,
punkty początkowe tworzą zbiór Julii wielomianu p
(Gaston Julia, francuski matematyk)
43
Metoda Newtona w dziedzinie zespolonej
Ogólny schemat postępowania
generujemy dużą liczbę punktów siatki pokrywającej pewien
kwadratowy obszar na płaszczyz
nie zespolonej,
określamy do którego zbioru przyciągania należy każdy z
wygenerowanych punktów
obliczamy np. 20 początkowych przybliżeń w metodzie Newtona
i sprawdzamy, czy któreś z nich leży w odległości nie większej
od 0,25 od jednego z pierwiastków.
44
Metoda Newtona w dziedzinie zespolonej
z12-1=0
z5-1=0
45