Sprawozdanie

Metody numeryczne

Temat: numeryczne rozwiązywanie równań i układów równań nieliniowych

Sprawozdanie wykonali:

Bartłomiej Łaszek 152133

Adam Tondel 153019

Pierwsza część ćwiczenia polegała na napisaniu funkcji realizującej rozwiązywanie równań nieliniowych za pomocą następujących metod: bisekcji, siecznych oraz Newtona. Napisane przez nas funkcje miały za zadanie znalezienie nam pierwiastków wielomianu podanych nam przez prowadzącego.

Funkcja naszych rozważań miała następującą postać:

f(x)= x²  2

Nasz pierwszy plik realizuje metodę bisekcji. Aby metoda ta była realizowalna musi być spełniony warunek różnych znaków na końcach przedziału w którym szukamy pierwiastków. Jest to warunek konieczny stosowalności tej metody. Funkcja ta musi być też ciągła na tym przedziale oraz krańce przedziału nie mogą wynosić 0.

Funkcja jaką udało nam się napisać ma następującą postać:

x=[-2:0.01:6];

y=[(x.^2)-2];

plot(x,y),grid;

b=(4);

a=(-1);

xi=a;

for i=1:1:20

err(i,:)=[sqrt(2)-xi];

hold on

plot(a,0,'r*',b,0,'b^')

if (((b^2 - 2)*(xi^2 -2)) < 0)

a=xi;

xi=(b+a)/2

else

b=xi;

xi=(b+a)/2

end

end

figure

hold on

plot(xi,0,'b*'),grid

figure

zak_x=[1:20];

plot(zak_x,err)

Poprawny wynik z 4 miejscami po przecinku otrzymaliśmy po 16 iteracji. Nie jest wiec to metoda szybka ani efektywna pozwala jednak ona na proste obliczenie iteracyjne miejsca zerowego wielomianu. Na 2 wykresie pokazany jest wynik ostatniej 20 iteracji. Wykres trzeci to wykres błędu jaki popełniony został podczas kolejnych przybliżeń. Można na nim zauważyć, że w początkowej fazie obliczeń błąd jest niestabilny, waha się i dopiero po 3 iteracji zaczyna on zbiegać do wartości prawdziwej. Zjawisko to może być spowodowane złym doborem punktów startowych. Po 10 iteracji na wykresie błędu zdaje się, że jest on już równy 0 jednak nie jest to wartość prawdziwa.

2 funkcja realizuje nam metodę siecznych. Metoda ta polega na założeniu, że funkcja na małym przedziale zmienia się w sposób liniowy. Pozwala nam to na to, aby krzywą zastąpić prostą, a za przybliżoną wartość pierwiastka przyjmujemy punkt przecięcia się prostej z osią OX. Zaletą tej metody jest fakt, że nie musimy obliczać pochodnej tej funkcji, jednak podczas wybrania zbyt małego przedziału metoda ta może nie być zbieżna.

Plik funkcyjny ma postać:

x(1)=-1;

x(2)= 2;

for i=2:1:10

fxi=x(i)^2 -2;

fxi_1=x(i-1)^2 -2;

x(i+1)=x(i) - (fxi * (x(i) - x(i-1)))/(fxi - fxi_1)

end

plot(x,'b*'),grid,xlabel('numer przyblizenia')

Wyniki podane przez matlaba:

-1.0000 2.0000 0 1.0000 2.0000 1.3333 1.4000 1.4146

1.4142 1.4142 1.4142

W przypadku tej metody widać, że jest ona szybsza niż poprzednia. Wynik prawdziwy do 4 miejsca po przecinku udało nam się uzyskać już w 9 iteracji.

Nasz trzeci plik będzie realizował metodę Newtona. Metoda ta ma następujące założenia – funkcja na przedziale [a,b] musi mieć dokładnie jeden pierwiastek, musi mieć różne znaki na końcach przedziału oraz pierwsza i druga pochodna muszą mieć stałe znaki na tym przedziale.

Plik realizujący naszą funkcję ma postać:

x(1)=2;

for i=1:1:4

fx=x(i)^2 - 2;

fxx=2*x(i);

x(i+1)=([x(i)]-[fx/fxx])

end

x =

2.0000 1.5000

x =

2.0000 1.5000 1.4167

x =

2.0000 1.5000 1.4167 1.4142

x =

2.0000 1.5000 1.4167 1.4142 1.4142

Jak widać plik realizujący tą funkcję jest bardzo prosty, oraz pierwszy poprawny wynik do 4 miejsca po przecinku pojawia się dość szybko (już w 4 przybliżeniu). Metoda ta jak widac jest najszybszą spośród wszystkich rozpatrywanych, lecz przy niektórych funkcjach trudność może pojawić się przy obliczaniu 1 i 2 pochodnej. Podsumowując metoda newtona jest najszybsza, za nią znajduje się metoda siecznych a później metoda bisekcji.

W drugiej części ćwiczenia naszym zadaniem było przeanalizowanie metod wbudowanych w matlaba. Pierwszą z nich była metoda Laguerre’a następnie Bairstow’a oraz Lehmer’a. Tok naszego postępowania był następujący: najpierw wybieraliśmy pierwiastki (wielokrotne, zespolone, rzeczywiste) a następnie przy pomocy funkcji poly układaliśmy wielomian który przechodził przez te punkty. Później wyliczaliśmy pierwiastki uzyskanego wielomianu i porównywaliśmy z wypisanymi na początku.

Plik ma postać:

u=[1e-3, 1e-5, 1e-9];

pier=[-2,2+i,2-i,2,4,4,0];

p=poly([-2,2+i,2-i,2,4,4,0]);

for i=1:3

n=u(i);

[pierw_bair,Literacji]=bairstow(p,n);

bair_pier_Liter(:,:,i)=[sort(pierw_bair),Literacji];

[pier_lag]=sort(laguerre(p,n));

lag_pier(:,i)=pier_lag;

[pier_leh]=sort(lehmer(p,n));

leh_pier(:,i)=pier_leh;

end

lag_pier

leh_pier

bair_pier_Liter

0 0 0
-2.0000 + 0.0000i -2.0000 + 0.0000i -2.0000 -0.0000i
2.0000 2.0000 2.0000
2.0000 + 1.0000i 2.0000 - 1.0000i 2.0000 +0.0000i
2.0000 - 1.0000i 2.0000 + 1.0000i 2.0000 - 1.0000i
3.9993 + 0.0000i 4.0000 + 0.0000i 4.0000+0.0000i
4.0007 - 0.0000i 4.0000 - 0.0000i 4.0000 - 0.0000i
leh_pier =
0 0 0
1.9999 + 0.0000i 2.0000 + 0.0000i -2.0000 -0.0000i
-1.9999 + 0.0000i -2.0000 + 0.0000i 2.0000+0.0000i
2.0006 - 0.9994i 2.0000 - 1.0000i 2.0000-1.0000i
2.0006 + 0.9994i 2.0000 + 1.0000i 2.0000+1.0000i
3.9635 + 0.0000i 3.9965 + 0.0000i 4.0000+0.0000i
4.0353 + 0.0000i 4.0035 + 0.0000i 4.0000-0.0000i
bair_pier_Liter(:,:,1) =
0 0
2.0000 12.0000
-2.0241 12.0000
2.0123 - 1.0468i 2.0000
2.0123 + 1.0468i 2.0000
3.9994 0
4.0000 0
bair_pier_Liter(:,:,2) =
0 0
2.0000 19.0000
-2.0002 19.0000
2.0001 - 1.0004i 2.0000
2.0001 + 1.0004i 2.0000
4.0000 0
4.0000 0
bair_pier_Liter(:,:,3) =
-1.7321 0
0 32.0000
1.7321 32.0000
2.0000 1.0000
2.0000 1.0000
4.0000 0

Jak widać pierwsze 2 metody dały dobre rezultaty. Ostatnia metoda jednak nie wygląda zbyt korzystnie w stosunku do pozostałych. Może to być spowodowane złym obliczeniem przez matlaba wielomianu, jak także złym uwarunkowaniem przedziałów w którym szukaliśmy pierwiastków. Możliwe też, że potrzeba by większej ilości iteracji aby wyniki otrzymane były stosunkowo dobre.

Wnioski:

Obliczanie miejsc zerowych wielomianów nie jest rzeczą prostą. Można korzystać z metod iteracyjnych takich jak pokazane powyżej, jednak niektóre z nich nie są łatwymi do stosowania. Pewnymi ograniczeniami mogą być np. przy metodzie Newtona obliczenie pochodnej. Nie ma z nią problemu jeżeli funkcja jaką analizujemy jest wielomianowa, jednak w przypadku funkcji w której występują bardziej skomplikowane wyrażenia, obliczenie pochodnej nie jest już rzeczą prostą. Widać, że każda z powyższych metod różni się od siebie szybkością zbieżności do wartości prawdziwej jednak ta najwolniejsza metoda nakłada na nas najmniejsza znajomość funkcji – nie musimy znać jej pochodnej, więc poradzimy sobie praktycznie z każdą funkcją – należy tylko wyznaczyć przedział w którym funkcja ma różne znaki na krańcach.