Задание

ЗАДАНИЕ

Контрольная работа №1 по вычислительной математике

Темы 1. Решение нелинейных уравнений методом половинного деления (дихотомии) и методом касательных (Ньютона)

Номер	Вид уравнения	Интервал
1.8	2x=cosx	[0;1]

МАТОДИЧКА ПРИМЕРЫ ИСПОЛНЕНИЯ

1.2.2.1 Метод деления отрезка пополам

Он состоит в следующем. Допустим, что мы нашли отрезок [a, b], на котором имеется корень с уравнения F(x)=0, причем единственный. В качестве начального приближения корня с0 берем середину этого отрезка, т. е. с0=(a+b)/2. Далее исследуем значения функции F(x) на концах отрезков [a, c0] и [c0,b], т. е. в точках a, c0,b. Тот из них, на концах которого функция принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового отрезка. Вторую половину отрезка [a, b], на котором знак функции не меняется, отбрасываем.

Пусть для определенности F(a)<0, F(b)>0 (см. рис.3). В рассматриваемом случае F(с0)<0, поэтому далее рассматриваем отрезок [c0,b]. Следующее приближение: с1=(с0+b)/2. Далее отбрасываем отрезок [c1,b], поскольку F(c1)>0 и F(b)>0. Аналогично находим другие приближения: с2=(с0+с1)/2 и т. д.

Процесс уточнения корня продолжаем до тех пор, пока значение функции F(x) в найденной точке не станет меньшим по модулю некоторого заданного числа E, т. е. |F(cn)|<E. Можно также оценивать длину полученного отрезка: если она становится меньше допустимой погрешности, то счет прекращается.

y

F(b)

y=F(x)

a c0 c2 b

x

c1

F(a)

Рис 3. Метод деления отрезка пополам

Этот итерационный процесс продолжается до тех пор, пока не будет достигнута требуемая точность; например

| f (cn) | < e или | cn-1 — cn | < e

Недостаток метода – медленная сходимость. Для достижения требуемой точности e необходимо совершить N итераций :

N » log 2 ((b—a)/e)

Это означает, что для получения каждых трех верных значащих цифр необходимо совершить около 10 итераций.

Достоинство — сходится всегда, для любых непрерывных функций, в том числе и недифференцируемых.

Ниже представлена блок-схема алгоритма уточнения корня методом деления отрезка пополам. Здесь сужение отрезка производится путем замены границы a или b на текущее значение корня c.

начало

ввод a, b,E

 

c:=(a + b)/2

 

Нет Да

a := c F(a)•F(c)<0 b := c

Нет Да

| F(c)|>E

вывод

c, F(c) конец

Рис. 4. Блок-схема метода деления отрезка пополам

Реализуем теперь рассмотренный метод в виде программы на Borland C++. При этом в программе предусмотрим сначала отделение корня, а затем и уточнение методом деления отрезка пополам.

Пример 1.1

Найти решения уравнения cos(x)– x2=0 на отрезке [- π/2, π/2]

// отделение корня и метод бисекций

#include <iostream>

#include <math>

float f(float x);

float kor(float a, float b, float e);

main()

{ float a, b,h, e,x1,x2,y1,y2,x; int k=0;

cout<<"\n вводи a, b,h, e "; cin>>a>>b>>h>>e;

x1=a;

m1: x2=x1+h; y1=f(x1);

if (x2<b) { y2=f(x2);

if (y1*y2<0) {x=kor(x1,x2,e); k++; cout<<"\n x["<<k<<"]="<<x;

cout<<" f(x)="<<f(x);}

x1=x2; } else goto mm1;

goto m1;

mm1: return 0;}

//функция – левая часть уравнения

float f(float x)

{ float fun=cos(x)-x*x; return fun;}

// функция, реализующая метод бисекций

float kor(float a, float b, float e)

{ float c;

m2: c=(a+b)/2; if (f(a)*f(c)<0) b=c; else a=c;

if (fabs(f(c))>e) goto m2; return c; }

В результате на заданном отрезке при h=0.1, E=0.00001 получим результаты:

1.2.2.2 МЕТОД НЬЮТОНА (метод касательных)

В методе касательных (другое название – метод Ньютона) проводят касательную к кривой y=F(x) в одной из точек a или b отрезка, где имеется корень. Затем находят точку пересечения касательной с осью OX — см. рис.5 (там эта точка обозначена за x). Эта точка будет первым приближением для искомого корня.

Например, проведем касательную в точке а. Пусть она пересекает ось ОХ в некоторой точке х. Рассмотрим полученный треугольник Aax. Для него :

A F(a)

a b

a x

(1)

 

Рис.5 Метод касательных

Как известно, производная в точке есть тангенс угла наклона этой касательной к оси ОХ. Угол наклона касательной — дополнительный к углу a, т. е. равный значению p–a. Тогда F' (a) = tg(p–a)= –tg(a). Значит, формула (1) примет вид:

(2)

Откуда получаем

Это и есть начальная формула метода Ньютона. Затем проводим касательную к графику в точке (x, F(x)), которая нас еще приблизит к корню и т. д. Обобщив формулу (2), можем записать:

Процесс уточнения корня следует продолжать, пока не будет достигнута требуемая точность. Например, как в методе деления отрезка пополам — пока не станет |F(xn) |< E (заданная точность).

Однако чтобы обеспечить сходимость метода Ньютона, требуется правильно выбрать начальную точку (взять a или b для построения касательной). В курсе математического анализа доказывается следующее: чтобы начальная точка х не оказалась вне отрезка [a, b], где находится корень, следует выбирать ту крайнюю точку, где F(x) и F''(х) (вторая производная) имеют одинаковый знак.

Достоинство метода – быстрая сходимость. Если выполняется условие: F''(х) (вторая производная) сохраняет знак и при этом F(x) и F''(х) имеют одинаковый знак, то процесс сходится так, что на каждой итерации число верных значащих цифр удваивается.

Недостаток – на каждой итерации велик объём вычислений (нужно, в частности, знать выражения для производной и так далее).

Приведем для полной ясности блок-схему метода Ньютона (см.рис.6).

начало

ввод a, b,E

 

Нет Да

c := b F(a)•F''(a)>0 c := a

c:=c–F(c)/F'(c)

 

Нет Да

| F(c)|>E

вывод

c, F(c) конец

Рис. 6. Блок-схема метода Ньютона