7. Численное решение уравнения методом половинного деления (дихотомии). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Метод дихотомии заключается в последовательном делении отрезка. Выберется промежуток функции, при этом, отделив корни, например, графическим способом. Получив интервал функции вычисляется его середина и определяется какой отрезок функции, разделенный серединой, больше или меньше нуля, это необходимо для выбора дальнейшего сужения интервала. Процесс сужения продолжается до определенной погрешности, которая задается пользователем.

К плюсам данного метода, конечно, стоит отнести его простоту. Им легко вычислять как аналитически, так и программно. К минусам нужно отнести затраты на приведенные итерации, по сравнению с методом хорд и касательных, например.

Алгоритм данного метода можно записать так:

1. Ввести данные (a, b, ε).

2. Если нужная точность достигнута (|b-a|<2ε) то идти к п.6

3. Взять середину очередного отрезка (c=(a+b)/2).

4. Если значения функции в точках а и c одного знака (f(a)*f(с)>0), то в качестве следующего отрезка взять правую половину (а=c), иначе — левую (b=c).

5. Идти к п.2.

6. Напечатать ответ ((a+b)/2)

double l=a, r=b; // границы отрезка

const double EPS = 1E-9; // точность

while (r-l > EPS) {

double m = (l + r) / 2;

if (f (m)*f (r) > 0)

r = m;

else

l = m;

}

8. Численное решение уравнения методом хорд. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Идея метода хорд состоит в том, что можно с известным приближением допустить, что функция на достаточно малом участке [а, b] изменяется линейно. Тогда кривую у = f(х) на участке [а, b] можно заменить хордой и в качестве приближенного значения корня принять точку пересечения хорды с осью абсцисс.

Для применения метода функция у = f(х) должна обладать следующими свойствами:

1. Быть непрерывной на [а, b] и f(a)f(b)<0.

2. На [а, b] существуют f/(x) и f//(x) отличные от нуля, непрерывные и сохраняющие знак на данном отрезке.

double func(double x)

{

return pow(x, 3) - 2 * pow(x, 2) - 6 * x - 1;

}

double find(double infinum, double supremum, double epsilon)

{

while (fabs(supremum - infinum) > epsilon)

{

infinum = supremum - (supremum - infinum) * func(supremum) / (func(supremum) - func(infinum));

supremum = infinum - (infinum - supremum) * func(infinum) / (func(infinum) - func(supremum));

}

return supremum;

}

int main()

{

double a = -5, b = 5;

std::cout << find(a, b, 0.0001) << std::endl;

return 0;

}

9. Численное решение уравнения методом Ньютона (касательных). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Этот метод применяется только в том случае, когда f’(x) и f(x) не изменяют знака на отрезке [a,b], т.е. функция f(x) на отрезке [a,b] монотонна и не имеет точек перегиба.

Суть метода — построение последовательности вложенных отрезков, содержащих корень, однако отрезки строятся по-другому. На каждом шаге через концы дуги графика функции f(x) на очередном отрезке проводят хорду и из одного конца проводят касательную. Точки пересечения этих прямых с осью ОХ и образуют следующий отрезок.

Для того, чтобы отрезки получались вложенными, нужно проводить ту касательную из конца, которая пересекает ось ОХ на отрезке [a,b]. Перебрав четыре возможных случая (разные знаки f’(x) и f(x)), можно увидеть, что касательную следует проводить из того конца, где знак функции совпадает со знаком второй производной. Также можно заметить, что касательная проводится либо все время из правого, либо все время из левого конца. Будем считать для определенности, что этот конец — b.

const double a = 0.0;

const double b = 1.0;

const double x0 = 0.5;

const double epsilon = 0.000001;

double f(double x)

{

return (x-0.25)*(x-0.25);

}

double df(double x)

{

return 2*x;

}

int main(int argc , char *argv[])

{

double x = x0;

while (abs(f(x)) > epsilon) {

x = x - f(x)/df(x);

}

std::cout << x << std::endl;

}