Метод половинного деления

Его ещё называют методом дихотомии. Этот метод решения уравнений отличается от выше рассмотренных методов тем, что для него не требуется выполнения условия, что первая и вторая производная сохраняют знак на интервале [a, b]. Метод половинного деления сходится для любых непрерывных функций f(x) в том числе не дифференцируемых.

Разделим отрезок [a, b] пополам точкой. Если (что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке [a, c] (Рис. 3.8), либо на отрезке [c, b] (Рис. 3.9)

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

Пример 4. Уравнение 5x - 6x -3 = 0 имеет единственный корень на отрезке [1;2]. Решить это уравнение методом половинного деления.

Решение: Программа на языке Паскаль может быть такой:

program mdp;

function f(x: real): real;

begin

f:=exp(x*ln(5))-6*x-3;

end;

var

a, b, e, c, x: real;

begin

a:=1;

b:=2;

write ('e=');

read(e);

c:=(a+b)/2;

while abs(b-a)>e do

begin

if f(a)*f(c)<0 then

b:=c

else

a:=c;

c:=(a+b)/2;

end;

x:=(a+b)/2;

writeln ('x=',x:3:3,' f(x)=',f(x):4:4);

end.

Результат выполнения программы:

e=0.001 x=1.562 f(x)=-0.0047

20.Алгоритм метода половинного деления.

1.Определить новое приближение корня х в середине отрезка [а,b]: х=(а+b)/2.

2.Найти значения функции в точках а и х: F(a) и F(x).

3.Проверить условие F(a)*F(x) < 0. Если условие выполнено, то корень расположен на отрезке [а,х]. В этом случае необходимо точку b переместить в точку х (b=х). Если условие не выполнено, то корень расположен на отрезке [х,b]. В этом случае необходимо точку а переместить в точку х (а=х).

4.Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до того времени, пока не будет выполнено условие /F(x)/ < e (заданная точность).

21.Метод простой итерации для поиска корней. Геометрическая интерпретация.

Исходное уравнение f(x)=0 эквивалентными преобразованиями приводится к виду с выделением неизвестного в левой части, то есть x=φ(x),где φ(x) – некоторая функция, связанная с исходной функцией f(x). Такая форма записи уравнения позволяет, задаваясь начальным приближением x_0, получить следующее, первое приближение x₁=φ(x₀), далее получают второе приближение x₂=φ(x₁) и так далее x_n+1=φ(x_n)…. Последовательность {x_n}= x_0, x_1, x_2, …, x_n,… называется последовательностью итераций или приближений с начальным значением x_0. Если функция φ(x) на [a,b] непрерывна и существует предел ξ = lim x_n при n→∞, то, переходя к пределу в равенстве x_n+1=φ(x_n), найдем, что при n→ ∞: lim x_n+1=lim φ(x_n)=φ(lim x_n), то есть ξ=φ(ξ).Следовательно, если последовательность приближений сходится, то она сходится к корню уравнения (2), а значит и уравнения (1). В силу сходимости итерационного процесса этот корень можно вычислить при достаточно большом n с любой заданной точностью. Однако необходимо определить при каких условиях последовательность {x_n}будет сходящейся. Получим связь между погрешностями двух соседних приближений - ε_n и ε _n+1: x_n=ξ+ε_n, x_n+1=ξ+ε _n+1. Подставим эти представления в x_n+1=φ(x_n) и разложим функцию в ряд Тейлора в окрестности корня:ξ+ε_n+1=φ(ξ+ε_n)=φ(ξ)+ε_nφ’(ξ)+(ε_n²/2!)φ’’(η), где η Î [ξ; ξ+ε_n] Ì [a;b].Поскольку ξ - корень, то ξ=φ(ξ)_, то получаем: ε_n+1=ε_n φ’(ξ)+(φ’’(η)/2)ε_n².Так как ε<1, то ε_n²<<ε_{n .} Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε_n² можно пренебречь, то есть ε_{n+1 »} ε_n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n |ε_n+1|<|ε_n|. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.

Теорема о сходимости метода простых итераций.Пусть ξ - корень уравнения x=φ(x), функция φ(x) определена и дифференцируема на отрезке [a,b], причем для x Î[a,b] все значения функции φ (x) Î [a,b]. Тогда, если существует такое положительное число q<1, что при x Î [a,b] выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке [a,b] уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x_n+1=φ(x_n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x₀ Î [a,b].Таким образом, последовательность {x_n},начинающаяся с любого x₀ Î [a;b], сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ’(х)>-1, то соседние приближения лежат по разную сторону от корня – такую сходимость называют двусторонней (или спиралевидной) – рис.2. Поскольку в этом случае корень заключен в интервале, концами которого являются соседние приближения – ξÎ(x_n,x_n+1), то выполнение условия |x_n+1-x_n|<ε обеспечивает выполнение условия |ξ-x _n+1|<ε.

Чтобы можно было сравнивать итерационные методы по скорости сходимости, вводят следующие понятия:

Определение 1: Сходимость последовательности {x_n} к ξ называется линейной (соответственно, итерационный процесс - линейно сходящимся), если существует такая постоянная CÎ(0,1) и такой номер n₀, что выполняются неравенства |ξ-x_n+1|≤C|ξ-x_n| для n≥n_0.

Для введенных ранее погрешностей это означает |ε _n+1|≤C|ε_n|. В методе простой итерации в роли постоянной C выступает значение q, то есть метод сходится линейно.

Определение 2: Последовательность приближений {x_n} сходится к ξ по меньшей мере с р-ым порядком (соответственно, итерационный процесс имеет по меньшей мере p-ый порядок), если найдутся такие константы C>0, p≥1 и n₀, что для всех n≥n₀ выполняются условия |ξ-x_n+1|≤C|ξ-x_n |^р (или в других обозначениях |ε _n+1|≤C|ε_n|^p).