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

(или метод вилки) хорошо знаком по доказательству теоремы о промежуточном значении в курсе математического анализа. Его суть заключается в построении последовательности вложенных отрезков, содержащих корень. При этом на каждом шаге очередной отрезок делится пополам и в качестве следующего отрезка берется та половина, на которой значения функции в концах имеют разные знаки. Процесс продолжают до тех пор, пока длина очередного отрезка не станет меньше, чем величина 2e. Тогда его середина и будет приближенным значением корня с точностью e.

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

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

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

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

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

5.Иди к п.2.

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

Упражнение 1.5 Перевести данный алгоритм на один из языков программирования.

Метод хорд и касательных

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

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

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

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

Формулы, употребляемые в методе Ньютона, хорошо известны из аналитической геометрии:

Уравнение хорды, проходящей через точки (a,f(a)) и (b,f(b)): y = f(a)+(x-a)*(f(b)-f(a))/(b-a),

откуда точка пересечения с осью ОХ: Х= a - f(a) *(b-a)/(f(b)-f(a)).

Уравнение касательной, проходящей через точку (b,f(b)): -y=f(b)+f'(b)(x-b),

откуда точка пересечения с осью ОХ: Х= b - f(b)/f'(b).

При составлении алгоритма снова естественно использовать для концов отрезка только две переменные a и b и писать: a= a - f(a) *(b-a)/(f(b)-f(a)) и (1.1)

b= b - f(b)/f'(b) (1.2)

Однако, в этом случае важен порядок формул (1.1) и (1.2).

Вопрос 2:В каком порядке следует писать формулы (1) и (2) при составлении алгоритма метода Ньютона и почему?

Упражнение 1.6.Составить алгоритм и программу на одном из языков для решения уравнений методом Ньютона.

Метод итераций

применяется к уравнению вида Х= u(x) на отрезке [a,b], где:

а) модуль производной функции u(x) невелик: | u'(x) | <= q < 1 (xÎ[a,b])

б) значения u(x) лежат на [a,b],т.е. a <= u(x) <= b при xÎ[a,b].

Если заранее известно, что на отрезке [a,b] расположен ровно один корень уравнения Х=u(x), то достаточно проверить выполнение условия а).

Упражнения: определить, применим ли метод итераций для уравнений:

1.7 Х=ln(3X+2) на отрезке [0,5]. А на отрезке [1,5]?

1.8 Х=е ^х-9 на отрезке [10,12]. А на отрезке [0,1]?

Сведение исходного уравнения к виду, пригодному для применения метода итераций.

Сведение уравнения f(x)=0 к нужному виду обычно осуществляют одним из двух способов:

1) Выражают один из Х, входящих в уравнение, например уравнение е^х - х-=0 приводят к виду:

Х=е^х или Х = ln(х)

2) Подбирают множитель и производят преобразования: f(х)=0 => k*f(x)=0 => х=х + k*f(x), т.е. u(x)=х+ k*f(x). Например, если 0 < m < f'(x) <= M при ХÎ[a,b], то можно в качестве k взять величину - 1/М, и тогда 0 <= u'(x) = 1 +к* f'(x)= 1- 1/M * f' (x) <= 1- m/M

Упражнения. Свести к виду, пригодному для применения метода итераций уравнения:

1.9 х³- 3 х² + 1 =0 на отрезке [ 2,3 ].

1.10 x * tg(x/2)- sin(x/2) =0 на отрезке [-1,1 ].

1.11 9-x²-e^x= 0 на отрезке [1,2].