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" );
}
}
}
}
Document Outline