Metoda równego podziału

Metoda równego podziału

Metoda równego podziału

Metoda równego podziału

(

(

metoda połowienia

metoda połowienia

,

,

metoda bisekcji

metoda bisekcji

) -- jedna z metod

) -- jedna z metod

rozwiązywania równań nieliniowych. Opiera się

rozwiązywania równań nieliniowych. Opiera się

ona na twierdzeniu Bolzano-Cauchy`ego:

ona na twierdzeniu Bolzano-Cauchy`ego:

Jeżeli funkcja ciągła f(x) ma na końcach przedziału

Jeżeli funkcja ciągła f(x) ma na końcach przedziału

domkniętego wartości różnych znaków, to

domkniętego wartości różnych znaków, to

wewnątrz tego przedziału, istnieje co najmniej

wewnątrz tego przedziału, istnieje co najmniej

jeden pierwiastek równania f(x) = 0.

jeden pierwiastek równania f(x) = 0.

Aby można było zastosować metodę równego

Aby można było zastosować metodę równego

podziału, muszą być spełnione założenia:

podziału, muszą być spełnione założenia:

funkcja

funkcja

f

f

(

(

x

x

) jest ciągła w przedziale domkniętym

) jest ciągła w przedziale domkniętym

[

[

a

a

;

;

b

b

]

]

funkcja przyjmuje różne znaki na końcach

funkcja przyjmuje różne znaki na końcach

przedziału:

przedziału:

f

f

(

(

a

a

)

)

f

f

(

(

b

b

) < 0

) < 0

Przebieg algorytmu :

Przebieg algorytmu :



Sprawdzamy, czy pierwiastkiem równania jest

Sprawdzamy, czy pierwiastkiem równania jest

punkt , czyli czy

punkt , czyli czy

f

f

(

(

x

x

1) = 0.

1) = 0.



Jeżeli tak jest, algorytm kończy się. W

Jeżeli tak jest, algorytm kończy się. W

przeciwnym razie

przeciwnym razie

x

x

1 dzieli przedział [

1 dzieli przedział [

a

a

,

,

b

b

] na

] na

dwa mniejsze przedziały [

dwa mniejsze przedziały [

a

a

,

,

x

x

1] i [

1] i [

x

x

1,

1,

b

b

].

].



Następnie wybierany jest ten przedział, dla

Następnie wybierany jest ten przedział, dla

którego spełnione jest drugie założenie, tzn.

którego spełnione jest drugie założenie, tzn.

albo

albo

f

f

(

(

x

x

1)

1)

f

f

(

(

a

a

) < 0 albo

) < 0 albo

f

f

(

(

x

x

1)

1)

f

f

(

(

b

b

) < 0. Cały

) < 0. Cały

proces powtarzany jest dla wybranego

proces powtarzany jest dla wybranego

przedziału.

przedziału.



Algorytm kończy się albo w punkcie 2, albo jest

Algorytm kończy się albo w punkcie 2, albo jest

przerywany, gdy przedział będzie dostatecznie

przerywany, gdy przedział będzie dostatecznie

wąski.

wąski.

Przykład

Przykład



Wyznaczyć pierwiastek równania:

Wyznaczyć pierwiastek równania:

x

x

3 −

3 −

x

x

+ 1 = 0

+ 1 = 0

w przedziale [ − 2;2].

w przedziale [ − 2;2].



Rozwiązanie:

Rozwiązanie:



Obliczamy wartości funkcji na końcach przedziału:

Obliczamy wartości funkcji na końcach przedziału:

f

f

( − 2) = − 5, a

( − 2) = − 5, a

f

f

(2) = 7.

(2) = 7.



Dzielimy przedział na połowy: i obliczamy

Dzielimy przedział na połowy: i obliczamy

wartość

wartość

f

f

(

(

x

x

1) = 1.

1) = 1.



Ponieważ wartość funkcji dla

Ponieważ wartość funkcji dla

x

x

1 jest różna od

1 jest różna od

zera, algorytm jest kontynuowany. Mamy teraz

zera, algorytm jest kontynuowany. Mamy teraz

dwa przedziały [ − 2,0] i [0,2]. Wybieramy ten, na

dwa przedziały [ − 2,0] i [0,2]. Wybieramy ten, na

którego końcach znaki funkcji są różne: (prawda)

którego końcach znaki funkcji są różne: (prawda)

lub (nieprawda). Zatem wybieramy przedział [ −

lub (nieprawda). Zatem wybieramy przedział [ −

2,0]

2,0]

Przykład c.d.

Przykład c.d.



Dzielimy przedział na połowy: i obliczamy

Dzielimy przedział na połowy: i obliczamy

wartość funkcji

wartość funkcji

f

f

( − 1) = 1 -- liczba

( − 1) = 1 -- liczba

x

x

2 nie jest

2 nie jest

zatem pierwiastkiem.

zatem pierwiastkiem.



Znowu dzielimy przedział na dwa podprzedziały,

Znowu dzielimy przedział na dwa podprzedziały,

wybieramy jeden z nich itd.

wybieramy jeden z nich itd.



UWAGA

UWAGA

: teoretycznie można uzyskać dokładne

: teoretycznie można uzyskać dokładne

rozwiązanie, jednak w praktycznych

rozwiązanie, jednak w praktycznych

zastosowaniach uzyskuje się tylko przybliżone

zastosowaniach uzyskuje się tylko przybliżone

rozwiazanie równania, a jego dokładność zależy

rozwiazanie równania, a jego dokładność zależy

od tego, ile razy zastosujemy powyższą metodę.

od tego, ile razy zastosujemy powyższą metodę.

Metoda połowienia – kod

Metoda połowienia – kod

programu (1-1)

programu (1-1)



#include <stdio.h>

#include <stdio.h>



#include <math.h>

#include <math.h>



#include <conio.h>

#include <conio.h>



#include <stdlib.h>

#include <stdlib.h>



int main (void)

int main (void)



{

{



int i, j;

int i, j;



float a, f_a;

float a, f_a;



float b, f_b;

float b, f_b;



float x, y;

float x, y;



float epsilon;

float epsilon;



printf( "\na = ");

printf( "\na = ");



scanf( "%f", &a);

scanf( "%f", &a);



printf( "\nb = ");

printf( "\nb = ");



scanf( "%f", &b);

scanf( "%f", &b);



epsilon = 1e-5;

epsilon = 1e-5;



f_a = 3 * a * a * a + 2 * a * a - 40 * a + 10;

f_a = 3 * a * a * a + 2 * a * a - 40 * a + 10;



f_b = 3 * b * b * b + 2 * b * b - 40 * b + 10;

f_b = 3 * b * b * b + 2 * b * b - 40 * b + 10;

Metoda połowienia – kod

Metoda połowienia – kod

programu (1-2)

programu (1-2)



if ( f_a * f_b < 0 )

if ( f_a * f_b < 0 )



{

{



i = 0;

i = 0;



x = a;

x = a;



y = f_a;

y = f_a;



while ( fabs( a-b ) > epsilon )

while ( fabs( a-b ) > epsilon )



{

{



x = (a+b) * 0.5;

x = (a+b) * 0.5;



y = 3 * x * x * x + 2 * x * x - 40 * x + 10;

y = 3 * x * x * x + 2 * x * x - 40 * x + 10;



if ( f_a * y > 0 )

if ( f_a * y > 0 )



{

{

Metoda połowienia – kod

Metoda połowienia – kod

programu (1-2) c.d.

programu (1-2) c.d.



a = x;

a = x;



f_a = y;

f_a = y;



}

}



else

else



{

{



b = x;

b = x;



f_b = y;

f_b = y;



}

}



i = i + 1;

i = i + 1;



}

}



printf( "Wynik x = %f, y(x) = %f po %d krokach. \n", x, y, i );

printf( "Wynik x = %f, y(x) = %f po %d krokach. \n", x, y, i );



}

}



else

else



{

{



printf( "Nie ma miejsca zerowego w podanym przedziale.\n" );

printf( "Nie ma miejsca zerowego w podanym przedziale.\n" );



}

}



}

}

Metoda połowienia - kod

Metoda połowienia - kod

programu (2-1)

programu (2-1)



#include <stdio.h>

#include <stdio.h>



#include <math.h>

#include <math.h>



#include <conio.h>

#include <conio.h>



#include <stdlib.h>

#include <stdlib.h>



float funkcja( float w_x )

float funkcja( float w_x )



{

{



float w_y;

float w_y;



w_y = 3 * w_x * w_x * w_x + 2 * w_x * w_x - 40 * w_x + 10;

w_y = 3 * w_x * w_x * w_x + 2 * w_x * w_x - 40 * w_x + 10;



return( w_y );

return( w_y );



}

}



int main (void)

int main (void)



{

{

Metoda połowienia - kod

Metoda połowienia - kod

programu (2-1) c.d

programu (2-1) c.d



int i, j;

int i, j;



float a, f_a;

float a, f_a;



float b, f_b;

float b, f_b;



float x, y;

float x, y;



float epsilon;

float epsilon;



printf( "\na = ");

printf( "\na = ");



scanf( "%f", &a);

scanf( "%f", &a);



printf( "\nb = ");

printf( "\nb = ");



scanf( "%f", &b);

scanf( "%f", &b);



epsilon = 1e-5;

epsilon = 1e-5;



f_a = funkcja( a );

f_a = funkcja( a );



f_b = funkcja( b );

f_b = funkcja( b );

Metoda połowienia - kod

Metoda połowienia - kod

programu (2-2)

programu (2-2)



if ( f_a * f_b < 0 )

if ( f_a * f_b < 0 )



{

{



i = 0;

i = 0;



x = a;

x = a;



y = f_a;

y = f_a;



while ( fabs( a-b ) > epsilon )

while ( fabs( a-b ) > epsilon )



{

{



x = (a + b )/2;

x = (a + b )/2;



y = funkcja( x );

y = funkcja( x );



if ( f_a * y > 0 )

if ( f_a * y > 0 )



{

{

Metoda połowienia - kod

Metoda połowienia - kod

programu (2-2) c.d.

programu (2-2) c.d.



a = x;

a = x;



f_a = y;

f_a = y;



}

}



else

else



{

{



b = x;

b = x;



f_b = y;

f_b = y;



}

}



i = i + 1;

i = i + 1;



}

}



printf( "Wynik x = %f, y(x) = %f po %d krokach. \n", x, y, i );

printf( "Wynik x = %f, y(x) = %f po %d krokach. \n", x, y, i );



}

}



else

else



{

{



printf( "Nie ma miejsca zerowego w podanym przedziale.\n" );

printf( "Nie ma miejsca zerowego w podanym przedziale.\n" );



}

}



}

}