Краткие теоретические сведения. Метод половинного деления (бисекций)

Метод половинного деления (бисекций)

Пусть требуется определить с точностью e>0 приближенное значение корня уравнения f(x)=0 (1) методом половинного деления. Сначала найдем (подберем) такие значения x=a и x=b, чтобы f(a)×f(b)<0. Если при этом функция y=f(x) является непрерывной при всех значениях xÎ[a; b], то, по крайней мере, один из корней, обозначим его x^*, уравнения (1) содержится в (a; b). Метод половинного деления состоит из конечного числа одинаковых шагов (действий). Первый шаг метода состоит в следующем: промежуток [a; b] делится точкой c=(a+b)/2 – середина отрезка [a; b], на два одинаковых по длине отрезка [a; с] и [с; b]. Если f(a)×f(с)<0, то x^*Î(a; с) и для уточнения корня x^* на следующем шаге полагают b=c. В противном случае, т.е. f(a)×f(с)>0 или f(c)×f(b)<0, полагают a=c.

Таким образом, описанным способом получают новый интервал [a; b], содержащий корень x^* уравнения (1), и на этом заканчивают первый шаг метода половинного деления. На втором и последующих шагах повторяют те же действия, что и на первом шаге, до тех пор пока не будет выполнено одно из условий: 1) b-a<e; 2) b-a<e и |f(c)|<e. При выполнении условия 1) или 2) полагают x^*=(a+b)/2.

Метод Ньютона (касательных)

При решении уравнения (1) (см. выше метод половинного деления) методом Ньютона сначала находят (подбирают) значения x=a и x=b такие, чтобы f(a)×f(b)<0 и проверяют:

1) является ли функция y=f(x) непрерывной в [a, b];

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

Если условия 1), 2) выполнены, а это означает, что в (a; b) содержится один корень x^* уравнения (1), то из двух точек A(a; f(a)) и B(b; f(b), лежащих на кривой y=f(x), выбирают ту, для которой значение функции и второй производной одного знака. Пусть, например, это будет точка В, т.е. f(b)×f''(b)>0.

Первый шаг метода Ньютона состоит в том, что в точке В проводят касательную к графику функции y=f(x) и определяют точку, обозначим её x₁, пересечения касательной с осью ОX по формуле

, (2)

где для удобства обозначим x₀=b.

На втором и последующих шагах выполняют те же действия, что и на первом шаге, т.е. по формуле, аналогичной формуле (2)

, где n=2,3,…, определяют точки (числа) x₂, x₃, … x_n, являющиеся приближенными значениями корня x^*. Процесс уточнения корня можно закончить, например, при выполнении условия |x_n-x_n-1|<e и |f(x_n)|<e и положить x^*»x_n.