Metody numeryczne
skrót wykładu
dr inż. Anna Barcz
Zakład Matematyki Stosowanej
kontakt: pokój 28
[e-mail]
konsultacje: środa 12.15 - 14.00
1
Zagadnienia
Przedział izolacji pierwiatków.
Twierdzenie Bolzano.
Metoda połowienia.
Metoda stycznych.
Metoda siecznych.
Metoda regula falsi.
Metody iteracyjne.
Zbieżnośc metod.
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
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  warunki zatrzymania algorytmów
#" f śą xźą#""Ä…ÏÄ…
#"xkƒÄ…1-xk#""Ä…ºÄ…
wykonanie przewidzianej liczby iteracji
6
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
7
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
8
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)
9
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
10
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
11
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
12
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]
13
Równania nieliniowe  metoda regula falsi
Punkt stały xs  punkt, w którym f(x) i f''(x) mają ten sam znak.
xs=a Śą x0=b xs=b Śą x0=a
f śą xkźą
xkƒÄ…1=xk- Å"śą xs-xkźą
f śą xsźą- f śąxkźą
Ciąg {x1,x2, ... , xn, ...} jest rosnący i ograniczony, a więc jest
zbieżny. Jego granicą jest szukany pierwiastek.
zbieżność liniowa.
14
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)
15
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)
16
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],
17
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)
18
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)
19
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
20
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]
21
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)
22
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.
23
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
24
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
25
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.
26
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,
27
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.
28
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ą.
29
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.
30
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)
31
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.
32
Metoda Newtona w dziedzinie zespolonej
z12-1=0
z5-1=0
33