1. Metoda połowienia i jej własności

Załóżmy, że poszukujemy rozwiązania równania f(x)=0 na przedziale *a, b+. Załóżmy ponadto,
że funkcja jest ciągła na tym przedziale oraz istnieje w nim dokładnie jeden pierwiastek.
Punkty a oraz b (a<b), wybieramy tak, aby był spełniony warunek f(a)f(b)<0. Spełnienie
tej nierówności przy założeniu ciągłości funkcji gwarantuje nam, że w przedziale (a, b)
znajduje się co najmniej jeden pierwiastek równania f(x)=0. W kolejnych krokach
połowimy nasz przedział i sprawdzamy, w której części przedziału znajduje się nasz
pierwiastek.
Algorytm metody połowienia
1. Wyznaczamy punkt c=(a+b)/2 i obliczmy wartośd f(c) Jeśli f(c)=0, to znaleźliśmy
rozwiązanie. W przeciwnym przypadku przechodzimy do punktu 2.
2. Jeśli f(a)f(c)<0, to podstawiamy b=c i przechodzimy do punktu 3. W przeciwnym
razie podstawiamy a=c i przechodzimy do punktu 3.
3. Sprawdzamy, czy b-a<ε, gdzie ε jest zadaną dokładnością obliczeo. Jeśli ten warunek jest
spełniony, to kooczymy obliczenia. Jeśli nie, to wracamy do punktu 1.

2. Metoda siecznych i jej własności

W tej metodzie wyznaczamy kolejne przybliżenie wykorzystując dwa wcześniejsze.

Metoda ta nie zawsze jest zbieżna. Punkty, od których zaczynamy iteracje musza byd

odpowiednio blisko rozwiązania. Zauważmy, że wyrażenie:

jest przybliżeniem odwrotności pochodnej w punkcie x

n-1

. Wzór na kolejne przybliżenia dla

tej metody można łatwo wyprowadzid samemu. W tym celu przybliżamy wartośd funkcji
w rozwiązaniu:

Następnie przybliżamy pochodną ilorazem różnicowym:

Łącząc powyższe wzory uzyskujemy:

Wyznaczając z powyższego równania x

n

otrzymujemy poszukiwany wzór.

Jako kryterium zakooczenia iteracji można tutaj przyjmowad różnice dwóch kolejnych
przybliżeo |x

n

- x

n-1

| lub |f(x

n

)|. Jednakże oba kryteria zatrzymania iteracji mogą

prowadzid do fałszywych wyników. Można zmodyfikowad kryterium z modułem różnicy

kolejnych przybliżeo dodając warunek |x

n

- x

n-1

| >= |x

n-1

- x

n-2

| . Wtedy będziemy przerywad

iteracje jeśli |x

n

- x

n-1

| < ε (ten składnik zapobiega zbyt szybkiemu przerwaniu iteracji) i

|x

n

- x

n-1

| >= |x

n-1

- x

n-2

| (spełnienie tej nierówności oznacza dominowanie błędów

zaokrągleo).

3. Metoda Newtona dla pojedynczego równania i układu równao (w tym jej własności)

a) dla pojedynczego równania

Rozważmy rozwinięcie funkcji f(x) w szereg Taylora w punkcie x

0

+ ε, gdzie f(x

0

)=0.

Jeśli pominiemy czynniki rzędu drugiego i wyższe to:

Korzystając z f(x

0

+ε)=0 możemy wyznaczyd poprawkę:

Stąd otrzymamy wzór iteracyjny postaci:

Jest to metoda Newtona nazywana także metodą stycznych.
Warunkiem koniecznym zbieżności jest, aby f’(x) ≠0, a warunkiem wystarczającym, aby

W tej metodzie ważny jest dobór punktu startowego.
W przypadku złego doboru punktu startowego metoda będzie rozbieżna (jest to metoda
zbieżna lokalnie!)
Konstrukcja warunku przerwania iteracji jest analogiczna jak w metodzie siecznych.
Metoda ta jest szybciej zbieżna niż opisywane dotąd metody (rząd 2 dla pierwiastków
pojedynczych i 1 dla pierwiastków wielokrotnych).

b) dla układu równao

Rozważamy jak poprzednio układ równao (nieliniowych) F(x)=0. Możemy ją w analogiczny
sposób jak w przypadku pojedynczego równania korzystając z rozwinięcia w szereg
Taylora funkcji wielu zmiennych F(x) i obcięciu go na składniku liniowym. Zakładając, że
pochodna F’(x) jest ciągła w x* (gdzie F(x*)=0) a pochodna F’(x*) jest nieosobliwa)
otrzymujemy metodę

która jest lokalnie zbieżna. Wadą tej metody jest koniecznośd odwracania macierzy w
każdym kroku.

4. Metoda iteracji prostych dla pojedynczego równania i układu równao (w tym jej
własności)

a) dla pojedynczego równania

Zapiszmy równanie f(x)=0 w następującej postaci: f(x)+x=0+x.
Stąd otrzymujemy równanie f(x) + x = ϕ(x) = x
z nową funkcją ϕ(x). Oczywiście funkcję ϕ(x) można wyznaczyd przekształcając odpowiednio
funkcję f(x) np. równanie

f(x) = 2x

3

+3x

2

+x -5 = 0

przekształcamy do postaci

W ten sposób otrzymujemy metodę iteracyjną x

n+1

= ϕ(x

n

).

Jeśli funkcja ϕ(x) jest różniczkowalna to metoda ta jest zbieżna, gdy spełniony jest warunek:
|ϕ'(x)|<1.
Jeśli funkcja ϕ(x) nie jest różniczkowalna to metoda ta jest zbieżna, gdy:

gdzie x* jest rozwiązaniem równania f(x)=0. Im wypisany wyżej ułamek (pochodna dla
funkcji różniczkowalnej) jest mniejsza, tym metoda jest szybciej zbieżna.
Jako kryterium zakooczenia iteracji można tutaj przyjmowad różnice dwóch kolejnych
przybliżeo |x

n

- x

n-1

| lub |f(x

n

)|, podobnie jak w przypadku metody siecznych.

b) dla układu równao

Przekształcamy układ równao F(x)=0 analogicznie jak dla pojedynczego równania do postaci

Warunkiem wystarczającym zbieżności jest

gdzie elementy macierzy D wyznaczamy ze wzoru

dla i, j=1,…,n.

Metoda jest zbieżna, jeżeli promieo spektralny macierzy D(x*) jest mniejszy od 1, gdzie

5. Podobieostwa i różnice pomiędzy metodami omawianymi na wykładzie

a) kryterium stopu

* bisekcja: b-a< ε

* inne metody - różnica dwóch kolejnych przybliżeo |x

n

- x

n-1

| lub |f(x

n

)|

b) zbieżnośd

*metoda siecznych - nie zawsze zbieżna

*Newtona - Warunkiem koniecznym zbieżności jest, aby f’(x) ≠0, a warunkiem

wystarczającym, aby

Metoda ta jest szybciej zbieżna niż inne.

*iteracji - Jeśli funkcja ϕ(x) jest różniczkowalna to metoda ta jest zbieżna, gdy

spełniony jest warunek: |ϕ'(x)|<1.
Jeśli funkcja ϕ(x) nie jest różniczkowalna to metoda ta jest zbieżna, gdy:

c) inne

*metoda Newtona i siecznych - ważny dobór punktu startowego

*bisekcja wymaga przedziału

*metoda Newtona i iteracji używana do rozwiązywania układów równao

nieliniowych

6. Kryteria stopu w poznanych metodach - ich wady i zalety

a) bisekcji
- Sprawdzamy b-a< ε jeśli warunek zachodzi to mamy rozwiązanie
- błędne jest sprawdzanie warunek |f(c)|< ε bo może generowad błędy
b) metoda siecznych, Newtona i iteracji prostych :
- różnica dwóch kolejnych przybliżeo |x

n

- x

n-1

| lub |f(x

n

)|

-> może generowad błędy dlatego wprowadza się modyfikacje.

- |x

n

- x

n-1

| ε - zapobiega zbyt szybkiemu przerwaniu iteracji

- |x

n

- x

n-1

| ≥ |x

n-1

- x

n-2

| - spełnione -> dominowanie błędów zaokrągleo

- Metoda Newtona szybciej zbieżna od innych


7. Kwadratura Newtona-Cotesa i jej własności

Założenia:
x

i

= a+ h

i

, h>0, i=0, 1,…, n, gdzie n wyznaczone jest z zależności b-a=nh.

Funkcję f(x) przybliżamy wielomianem interpolacyjnym Lagrange’a opartym na węzłach x

i

.

f (x)dx=

L(x)dx +r[ f ], gdzie r[f+ oznacza błąd metody

Uzyskujemy :

f (x)dx=

r[ f ]

Jeśli p(x)=1

*metoda trapezów - wielomian pierwszego stopnia

A 0=

A1=

f (x)dx=

* metoda Simsona - wielomian drugiego stopnia

A 0=

A1=

A 2 =

f (x)dx=

- Kwadratur wyższych rzędów nie muszą dawad dokładniejszych wyników.
W oparciu o pochodną wysokiego rzędu możemy szacowad błędy.
W praktyce stosuje się kwadratury złożone niższych rzędów, bo pozwalają zredukowad błąd
kwadratury, który jest zależny od odległości pomiędzy kolejnymi węzłami.

Cechy:
- przedział *a, b+ podzielony na podprzedziały
-kwadratury niskich rzędów lepsze
-przybliżenie całki to suma przybliżeo na podprzedziałach.

- W przypadku kwadratur Newtona-Cotesa punkty, w których dana jest wartośd funkcji są
zadane (na nich budowany jest wielomian interpolacyjny).
- Kwadratura jest rzędu n, jeśli jest dokładna dla wszystkich wielomianów stopnia
mniejszego od n oraz istnieje wielomian stopnia n, dla którego nie jest dokładna.
-Kwadratury Newtona-Cotesa oparte na n+1 są rzędu n+2 dla n parzystych i rzędu n+1 dla n
nieparzystych.

8. Metoda Romberga i jej własności

Wykorzystuje ekstrapolacje Richardsona do eliminacji w błędzie kwadratury składników przy
najwyższych potęgach w oparciu o wyniki dla niższych potęg
Idea metody
Dzielimy przedział *a, b] na

równych części. Niech

Wzór złożony trapezów :

Błąd :

Kwadratura

-Ze zbieżności T

0,m

wynika ze zbieżnośd T

m,0

, który na większości przypadków zbiega szybciej.

- Trudno wskazad, która kwadratura jest najlepsza. To będzie zależało od tego, co nas
najbardziej interesuje(minimalizacja błędu, nakład obliczeo)


9. Kwadratury Gaussa i ich własności



10. Podobieostwa i różnice pomiędzy kwadraturami Newtona-Cotesa i Gaussa

Podobieostwa

- Mamy przedziały *a,b+
- Całki przybliżany z tego samego wzoru

f (x)dx=

Różnice
- W Newtonie-Cotesie są metody trapezów i Simsona w Gaussie np. kwadratura Gaussa-
Jacobiego/Czybyszewa
- W Newtonie-Cotesie funkcje przybliżamy wielomianem interpolacyjnym Lagrange'a, a w
Gaussie wielomianem ortogonalnym.
- W N-C błąd zależny od odległości między kolejnymi węzłami w Gaussie błąd ze wzrostem
liczby węzłów
- Różnica w stosunku do kwadratur Newtona-Cotesa polega na tym, że w Gaussie dobieramy
współczynniki Ai, i węzły xi.
- Różne rzędy kwadratur n+1 węzłów daje rząd n+2, a w Gaussie n+1 daje rząd 2n+1


11. Kryteria wyboru kwadratury

- Trudno wskazad, która kwadratura jest najlepsza. To będzie zależało od tego, co nas
najbardziej interesuje (minimalizacja błędu, nakład obliczeo, itp.).

- Różnica w stosunku do kwadratur Newtona-Cotesa polega na tym, że w Gaussie dobieramy
współczynniki A

i

, i węzły x

i

.

- Funkcja p(x) - w zależności czy chcemy zminimalizowad błąd czy go zupełnie wyeliminowad / czy
chcemy międ dużo do liczenia czy nie/ jak bardzo chcemy mied dokładny wynik. W zależności czy
granice całkowania należą do przedziału czy nie.