Ëåêöèÿ 7.

Çàäà÷è ÷èñëåííîãî àíàëèçà

Ïîèñê êîðíÿ ôóíêöèè ìåòîäîì äåëåíèÿ îòðåçêà ïîïîëàì

Óñëîâèå íà ôóíêöèþ

f(a)*f(b) <= 0

Áèíàðíûé ïîèñê, èñïîëüçîâàííûé äëÿ ïîèñêà â îòñîðòèðîâàííîì ìàññèâå, — óíèâåðñàëüíûé ìåòîä, ïðèìåíÿåìûé â ðàçíûõ îáëàñòÿõ.

Òàê, åãî ìîæíî ïðèìåíÿòü äëÿ íàõîæäåíèÿ êîðíåé ôóíêöèè íà îòðåçêå, åñëè ôóíêöèÿ ïðèíèìàåò íà êîíöàõ îòðåçêà çíà÷åíèÿ ðàçíîãî çíàêà. Ðàññìîòðèì çíà÷åíèå ôóíêöèè â ñåðåäèíå äàííîãî îòðåçêà. Åñëè ýòî çíà÷åíèå èìååò ðàçíûé çíàê ñî çíà÷åíèåì ôóíêöèè íà ëåâîé ãðàíèöå îòðåçêà, òî èìååò ñìûñë èñêàòü êîðåíü ôóíêöèè â ëåâîé ïîëîâèíå îòðåçêà.  ïðîòèâíîì ñëó÷àå èìååò ñìûñë èñêàòü êîðåíü ôóíêöèè â ïðàâîé ïîëîâèíå îòðåçêà. Êàæäàÿ òàêàÿ èòåðàöèÿ ñîêðàùàåò äèàïàçîí ïîèñêà êîðíåé âäâîå, ÷òî âåäåò ê áûñòðîìó óìåíüøåíèþ äëèíû ðàññìàòðèâàåìîãî îòðåçêà. Êàê òîëüêî äëèíà ðàññìàòðèâàåìîãî îòðåçêà ñòàíîâèòñÿ ìåíüøå íåêîåãî ýïñèëîí, çàäàííîãî ïîëüçîâàòåëåì, ïîèñê ìîæíî ñ÷èòàòü çàêîí÷åííûì, òàê êàê ëþáàÿ òî÷êà ýòîãî îòðåçêà ïðèáëèæàåò êîðåíü ôóíêöèè ñ çàäàííîé òî÷íîñòüþ ýïñèëîí.




Ïðîãðàììà ïîèñêà êîðíÿ ôóíêöèè f(x) íà îòðåçêå [a, b] ñ òî÷íîñòüþ eps:

#include <stdio.h>

double f(double x);

int main(void) {

double a, b, c, eps;

printf("Input interval (a, b) and epsilon\n");

scanf("%lf%lf%lf", &a, &b, &eps);

if (f(a)*f(b) > 0) {

printf("Function values at the interval ends are the same sign\n");

return -1;

}

while ((b-a) >= eps) {

c = (a + b) / 2;

if (f(a)*f(c) <=0 ) {

b = c;

} else {

a = c;

}

}

printf("Function root: %lf\n", (a + b)/2);

return 0;

}

double f(double x) {

return x*x – 5;

}


Ïîèñê êîðíÿ ôóíêöèè ìåòîäîì Íüþòîíà (êàñàòåëüíûõ)

Ìåòîä Íüþòîíà ïîèñêà êîðíåé ôóíêöèè îñíîâàí íà ïîñòðîåíèè ðåêóððåíòíîé ïîñëåäîâàòåëüíîñòè òî÷åê, âñå áîëåå òî÷íî ïðèáëèæàþùèõ èñêîìûé êîðåíü ôóíêöèè.

Îí íå ÿâëÿåòñÿ àáñîëþòíî íàäåæíûì, êàê ìåòîä äåëåíèÿ îòðåçêà ïîïîëàì, òàê êàê ìîæåò îêàçàòüñÿ, ÷òî ïîñëåäîâàòåëüíîñòü ðàñõîäèòñÿ.

Îäíàêî â íåêîòîðûõ ñëó÷àÿõ îí îêàçûâàåòñÿ ïîëåçíûì.

Êàæäàÿ òî÷êà â ïîñëåäîâàòåëüíîñòè x0x1x2x3→… (êðîìå òî÷êè x0, çàäàâàåìîé ïîëüçîâàòåëåì) íàõîäèòñÿ èç ïðåäûäóùåé ñëåäóþùèì îáðàçîì: â òî÷êå xi ïðîâîäèòñÿ êàñàòåëüíàÿ ê ôóíêöèè è ìåñòî ïåðåñå÷åíèÿ ýòîé êàñàòåëüíîé è îñè X âûáèðàåòñÿ â êà÷åñòâå òî÷êè xi+1.

























Ïðîãðàììà ïîèñêà êîðíÿ ôóíêöèè f(x) ìåòîäîì Íüþòîíà:

#include <stdio.h>

#include <math.h>

double f(double x);

double df(double x);

int main(void) {

double a, eps;

printf("Input starting point a and epsilon\n");

scanf("%lf%lf", &a, &eps);

while (fabs(f(a)) > eps) {

/* if (N>1000) { … } */

if (df(a) == 0) {

printf("The method is inappropriate\n");

return -1;

}

a = a – f(a)/df(a);

}

printf("Function root: %lf\n", a);

return 0;

}

double f(double x) {

return x*x - 5;

}

double df(double x) {

return 2*x;

}


Ïîèñê êîðíÿ ôóíêöèè ìåòîäîì õîðä (ñåêóùèõ)

Ìåòîä õîðä ïîèñêà êîðíåé ôóíêöèè òàêæå îñíîâàí íà ïîñòðîåíèè ðåêóððåíòíîé ïîñëåäîâàòåëüíîñòè òî÷åê, âñå áîëåå òî÷íî ïðèáëèæàþùèõ èñêîìûé êîðåíü ôóíêöèè.

Îí òàêæå íå ÿâëÿåòñÿ àáñîëþòíî íàäåæíûì, êàê ìåòîä äåëåíèÿ îòðåçêà ïîïîëàì, òàê êàê ìîæåò îêàçàòüñÿ, ÷òî ïîñëåäîâàòåëüíîñòü ðàñõîäèòñÿ.

Îäíàêî â íåêîòîðûõ ñëó÷àÿõ îí òàêæå îêàçûâàåòñÿ ïîëåçíûì.

Êàæäàÿ òî÷êà â ïîñëåäîâàòåëüíîñòè x0x1x2x3→… (êðîìå òî÷åê x0 è x1, çàäàâàåìûõ ïîëüçîâàòåëåì) íàõîäèòñÿ èç äâóõ ïðåäûäóùåé ñëåäóþùèì îáðàçîì: ÷åðåç òî÷êè (xi ,f(xi)) è (xi+1,f(xi+1)) ïðîâîäèòñÿ ïðÿìàÿ (ñåêóùàÿ) è ìåñòî ïåðåñå÷åíèÿ ýòîé ïðÿìîé è îñè X âûáèðàåòñÿ â êà÷åñòâå òî÷êè xi+2.

Ñîñòàâèì óðàâíåíèå äëÿ ïîèñêà òî÷êè c ïåðåñå÷åíèÿ õîðäû, ïðîõîäÿùåé ÷åðåç òî÷êè (a,f(a)) è (b,f(b)):

f(b)/f(a) = (b-c)/(a-c)

Îòñþäà íàõîäèì òî÷êó ñ = (f(a)*b-f(b)*a)/(f(a)-f(b)).




Ïðîãðàììà ïîèñêà êîðíÿ ôóíêöèè f(x) ìåòîäîì õîðä:

#include <stdio.h>

#include <math.h>

double f(double x);

int main(void) {

double a, b, c, eps;

printf("Input starting points a and b and epsilon\n");

scanf("%lf%lf%lf", &a, &b, &eps);

while (fabs(f(a)) > eps) {

if (f(a) == f(b)) {

printf("The method is inappropriate\n");

return -1;

}

c = (f(a)*b-f(b)*a)/(f(a)-f(b));

a = b;

b = c;

}

printf("Function root: %lf\n", b);

return 0;

}

double f(double x) {

return x*x – 4;

}


Ïîèñê ìàøèííîãî ýïñèëîí

Öåëîå ÷èñëî ïðåäñòàâëÿåòñÿ â ïàìÿòè êîìïüþòåðà â äâîè÷íîì âèäå:

Íàïðèìåð, ÷èñëî 13:

31

30

29

28

27

26

25

...

7

6

5

4

3

2

1

0

0 (çíàê)

0

0

0

0

0

0


0

0

0

0

1

1

0

1



Íàïðèìåð, ÷èñëî -13:

Ïðÿìîå ïðåäñòàâëåíèå:

31

30

29

28

27

26

25

...

7

6

5

4

3

2

1

0

1 (çíàê)

0

0

0

0

0

0


0

0

0

0

1

1

0

1



Äîïîëíèòåëüíûé êîä (èñïîëüçóåòñÿ ÷àùå âñåãî):

31

30

29

28

27

26

25

...

7

6

5

4

3

2

1

0

1 (çíàê)

1

1

1

1

1

1


1

1

1

1

0

0

1

1

+

0 (çíàê)

0

0

0

0

0

0


0

0

0

0

1

1

0

1


=

0 (çíàê)

0

0

0

0

0

0


0

0

0

0

0

0

0

0


1+1 = 0 (1 â óìå)

1+0 (+1) = 0 (1 â óìå)

1+0 (+1) = 0 (1 â óìå — èäåò â áèò ïðîöåññîðà (ARM áèò Overflow))


Ñòàðøèé áèò — ïðîïàäàåò èç ïðåäñòàâëåíèÿ ÷èñëà (íî íå èç ïðîöåññîðà)


Âåùåñòâåííûå ÷èñëà:


1000000000 = 0.1 * 10^10

0.00000000000001 = 0.1 * 10^(-13)

1000000000.00000000000001 = 0.100000000000000000000001 * 10^10


31

30

29

28

27

26

25

...

7

6

5

4

3

2

1

0

0 (çíàê)

0

0

0

0

0

0


0

0

0

0

1

1

0

1


Ìàíòèññà (âûäåëåíî êðàñíûì) — çíà÷àùèå öèôðû

Îðäèíàòà (ïîðÿäîê) (âûäåëåíî ñèíèì) — ñòåïåíü 10


Åñëè ìàíòèññà íå ïîìåùàåòñÿ â îòâåäåíííûå ïîä íåå áèòû, òî ìëàäøèå çíà÷àùèå öèôðû ïðîïàäàþò (îêðóãëÿþòñÿ)


Ïðèìåð 1.
1+x = 1

x = 0.1 * 10*^(-22)

1 + 0.00000000000000000000001 = 1.00000000000000000000001 = 0.100000000000000000000001 * 10^(-1) =

= 0.10000000000000000000000 * 10^(-1)


Åñëè âñÿ ìàíòèññà ñóììû íå ïîìåñòèòñÿ â îòâåäåííûå ïîä íåå áèòû, òî ìëàäøèå öèôðà îòáðîñÿòñÿ =>

ðåçóëüòàò áóäåò ðàâåí 1



Ìàøèííûì ýïñèëîí äëÿ äàííîé âû÷èñëèòåëüíîé ñèñòåìû ÿâëÿåòñÿ íàèáîëüøåå ñðåäè âåùåñòâåíííûõ ÷èñåë x, ïðåäñòàâèìûõ â ýòîé ñèñòåìå è óäîâëåòâîðÿþùèõ â íåé ñîîòíîøåíèþ 1+x=1. Òàêîå ñîîòíîøåíèå ÿâëÿåòñÿ âîçìîæíûì äëÿ íåêîòîðûõ î÷åíü ìàëåíüêèõ ÷èñåë, òàê êàê â âû÷èñëèòåëüíîé ñèñòåìå çíà÷àùèå öèôðû ÷èñëà (ìàíòèññà) õðàíÿòñÿ ñ íåêîòîðîé òî÷íîñòüþ, òî åñòü îêðóãëÿþòñÿ òàê, ÷òîáû ïîìåñòèòüñÿ â ÿ÷åéêå ïàìÿòè íåêîòîðîãî ðàçìåðà, îïðåäåëåííîãî äëÿ äàííîé âû÷èñëèòåëüíîé ñèñòåìû. Ïðè ïðèáàâëåíèè òàêîãî î÷åíü ìàëåíüêîãî ÷èñëà ê åäèíèöå êîëè÷åñòâî çíà÷àùèõ öèôð óâåëè÷èâàåòñÿ çà ñ÷åò ïîÿâëåíèÿ áîëüøîãî êîëè÷åñòâà íóëåé ïîñëå ñòàðøåé 1. Íàïðèìåð, ó ñóììû 1 + 0.000001 = 1.000001 êîëè÷åñòâî çíà÷àùèõ öèôð 7, â òî âðåìÿ êàê ó èñõîäíûõ ÷èñåë áûëî ïî îäíîé çíà÷àùåé öèôðå.

Ïðè ïîìåùåíèè ðåçóëüòàòà ñóììèðîâàíèÿ â ïàìÿòè âû÷èñëèòåëüíîé ñèñòåìû ïîñëåäíèå çíà÷àùèå öèôðû ìîãóò óðåçàòüñÿ, ÷òîáû ðåçóëüòàò ïîìåñòèëñÿ â ÿ÷åéêå ïàìÿòè. Åñëè òàêèì îáðàçîì óðåçàþòñÿ âñå çíà÷àùèå öèôðû ìàëåíüêîãî ÷èñëà, òî ðåçóëüòàòîì, ïîìåùåííûì â ÿ÷åéêó ïàìÿòè, áóäåò 1.


Ïðîãðàììà ïîèñêà ìàøèííîãî ýïñèëîí

#include <stdio.h>

int main(void) {

double x = 1;

while (1 + x > 1) {

x /= 2;

}

printf("Mach epsilon: %lf\n", x);

return 0;

}


Çàäà÷à: Íàéòè 1000 ÷èñåë, êîòîðûå ïðè ñëîæåíèè â ïðîãðàììå â ïðÿìîì è îáðàòíîì ïîðÿäêå äàþò ðàçíûé ðåçóëüòàò (ïîäñêàçêà — èñïîëüçîâàòü ìàøèííîå ýïñèëîí)