Zagadnienia - równania nieliniowe

Sformułowanie zadania poszukiwania pierwiastków.

Przedział izolacji.

Twierdzenia o istnieniu pierwiastków.

Warunki zatrzymywania algorytmów.

Metoda połowienia: założenia, algorytm, ilustracja graficzna, zbieżność.

Metoda regula falsi: założenia, algorytm, ilustracja graficzna, zbieżność.

Metoda siecznych: założenia, algorytm, ilustracja graficzna, zbieżność.

Metoda Newtona: założenia, algorytm, ilustracja graficzna, zbieżność.

Zastosowanie wzoru Newtona.

Szacowanie liczby pierwiastków w zadanym przedziale. Zastosowanie ciągu
Sturma.

Deflacja.
1
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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źą
3
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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
4
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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
5
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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
6
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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źą
7
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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]
8
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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.
9
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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)
10
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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)
11
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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],
12
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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)
13
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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
14
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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]
15
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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)
16
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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.
17
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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
18
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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
19
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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,
20
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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.
21
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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
22
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz
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ą.
23
Metody numeryczne, 2 INF, Szczecin WI, Anna Barcz