marcinka all, 20021015, SZUKANIE ZER W FUNKCJACH NIELINIOWYCH


SZUKANIE ZER W FUNKCJACH NIELINIOWYCH

  1. METODA POŁOWIENIA

0x08 graphic

0x01 graphic

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

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 0x01 graphic
.

  1. METODA NEWTONA

0x08 graphic
0x01 graphic

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 0x01 graphic
w następujący sposób:

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

0x01 graphic

0x01 graphic
(1a)

Przerywamy, gdy: 0x01 graphic

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

Szybkość zbieżności metody:

Założenia:

0x01 graphic
- błąd przybliżenia 0x01 graphic

0x01 graphic
- jakie są zależności

Rozwijamy w szereg Taylore'a:

0x01 graphic
, gdzie 0x01 graphic

0x08 graphic
0x01 graphic

0x01 graphic

(patrz 1a) 0x01 graphic

0x08 graphic

0x08 graphic
0x01 graphic

0x01 graphic

0x01 graphic
(2)

0x08 graphic
0x01 graphic
const.

Jeśli 0x01 graphic
:

0x08 graphic
0x01 graphic

0x08 graphic

p c

im większy

wykładnik

tym metoda

szybciej zbieżna

DEFINICJA:

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

Jeśli istnieją takie dwie liczby p, c ,gdzie 0x01 graphic
, że 0x01 graphic
, 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 0x01 graphic
i że w tym otoczeniu zachodzi własność:

0x01 graphic
0x01 graphic
0x01 graphic

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

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

0x01 graphic

A teraz praktyczny wzór:

0x08 graphic
0x01 graphic

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

  1. METODA SIECZNYCH

Otrzymujemy z metody Newtona, aproksymując 0x01 graphic
ilorazem 0x01 graphic
.

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

Tworzy się rekurencyjnie ciąg 0x01 graphic

0x08 graphic
0x01 graphic

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ść:

0x01 graphic
gdzie 0x01 graphic

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

0x01 graphic

0x01 graphic

0x01 graphic
to 0x01 graphic
i 0x01 graphic

0x01 graphic

0x01 graphic
to 0x01 graphic
i 0x01 graphic

Założenia:

Twierdzenie:

Założenia:

0x01 graphic

0x01 graphic
ma stały znak w [a,b]

0x01 graphic

Jeśli 0x01 graphic

oraz 0x01 graphic



Wyszukiwarka

Podobne podstrony:
marcinka all, 20021008
marcinka all, 20021112, INTERPOLACJA FUNKCJAMI SKLEJANYMI:
Funkcje nieliniowe?z ograniczeń
marcinka all, 20030107
marcinka all, 20021203, Ciąg dalszy:
marcinka all, 20021119
Funkcje nieliniowe
marcinka all, 20030121
Przykładowe transformacje liniowe funkcji nieliniowych
marcinka all, 20021126, (RYSUNEK)
Funkcje internetu w życiu rodziny, wrzut na chomika listopad, Informatyka -all, INFORMATYKA-all, Inf
Wybrane funkcje programu graficznego GIMP do obróbki zdjęć c, wrzut na chomika listopad, Informatyka
Wójcik, Marcin Funkcjonalizm w geograficznych badaniach wsi (2013)
biernacki,algorytmy przetwarzania sygnałów L, wpływ rozmieszczebnia zer i biegunów na funkcję transm
BANK CENTRALNY I JEGO FUNKCJE
Zaburzenia funkcji zwieraczy
Genetyka regulacja funkcji genow

więcej podobnych podstron