SZUKANIE ZER W FUNKCJACH NIELINIOWYCH

1. METODA POŁOWIENIA

Po n -krokach mamy przedział
o długości
.

Szybkość zbieżności nie zależy od funkcji. W algorytmie tym, nie wykorzystuje się żadnej własności funkcji, oprócz informacji, że posiada tylko jedno 0 w przedziale
.

2. METODA NEWTONA

Startuję z tego końca przedziału, w którym f(x) ma ten sam znak co f''(x). Tworzę ciąg przybliżeń pierwiastka
w następujący sposób:

funkcję f(x) aproksymuję styczną w punkcie
, styczna przecina oś x w punkcie
bliższym pierwiastkowi
. W punkcie
wyznaczam następną styczną - przecina ona oś x w punkcie
, i tak dalej...

(1a)

Przerywamy, gdy:

maleje dość szybko do momentu, aż dominują błędy zaokrągleń

Szybkość zbieżności metody:

Założenia:

• 
  ciągła

• 
  - pierwiastek pojedynczy

• 
  

• 
  w otoczeniu
  

- błąd przybliżenia

- jakie są zależności

Rozwijamy w szereg Taylore'a:

, gdzie

(patrz 1a)

(2)

const.

Jeśli
:

p c

im większy

wykładnik

tym metoda

szybciej zbieżna

DEFINICJA:

Niech
będzie ciągiem zbieżnym do
;

Jeśli istnieją takie dwie liczby p, c ,gdzie
, że
, to p nazywamy wykładnikiem zbieżności ciągu, a c - stałą asymptotyczną błędu.

Dla p = 1, lub 2 lub 3, mówimy o zbieżności odpowiednio, liniowej, kwadratowej i sześciennej.

Załóżmy, że I jest otoczeniem pierwiastka
i że w tym otoczeniu zachodzi własność:

Można udowodnić, że jeśli
i przedział
, to każde
, wyznaczone metodą Newtona, należy do przedziału I oraz

Zatem metoda Newtona jest zbieżna do pojedynczego pierwiastka, jeśli tylko
jest dostatecznie blisko pierwiastka
, ściślej jeśli:

A teraz praktyczny wzór:

To metoda jest zbieżna dla dowolnego przybliżenia początkowego
należącego do [a,b].

3. METODA SIECZNYCH

Otrzymujemy z metody Newtona, aproksymując
ilorazem
.

Startujemy z dwóch przybliżeń początkowych:

Tworzy się rekurencyjnie ciąg

Pierwsza iteracja musi zaczynać się od punktów, w których funkcja ma różne znaki - inaczej może być wykryte fałszywe 0 (ta metoda nie jest dobra w pobliżu 0).

Można wyprowadzić zależność:

gdzie

Metoda siecznych nie jest zbieżna kwadratowo (jest wolniejsza od metody Newtona).

Można wykazać, że nie istnieje metoda iteracyjna, rzędu II, używając tylko jednej nowej wartości w każdym kroku.

f(x) = 0

to
i

to
i

Założenia:

• I i II pochodna funkcji mają stały znak w
  

• istnieje tylko jedno zero w
  

Twierdzenie:

Założenia:

ma stały znak w [a,b]

Jeśli

oraz