Метод половинного деления 2 (стр. 2 из 3)

Уравнение хорды, проходящей через точки А₀ и В, имеет вид

Найдем значение х = х₁, для которого у = 0:

Эта формула носит название формулы метода хорд. Теперь корень ξ находится внутри отрезка [x₁, b]. Если значение корня х₁ нас не устраивает, то его можно уточнить, применяя метод хорд к отрезку [х₁, b].

Рис

Соединим точку А₁ (x₁; f (x₁) с точкой В (b; f (b)) и найдем х₂ – точку пересечения хорды А₁В с осью Ох:

Продолжая этот процесс, находим

и вообще

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

По приведенным выше формулам вычисляются корни и для случая, когда f(а) > 0, f(b) < 0, f'(x) < 0, f''(x) < 0 (рис. 3.18, б).

Теперь рассмотрим случаи, когда первая и вторая производные имею разные знаки, т.е. f'(x) ∙ f'(x) < 0.

Пусть, например, f(a) > 0, f(b) < 0, f'(х) < 0, f''(х) > 0 (рис. 3.19, а). Соединим точки A (a; f (а)) и В₀ (b; f (b)) и запишем уравнение хорды, проходящей через А и B₀:

Найдем х₁, как точку пересечения хорды с осью Ох, полагая у = 0:

Корень ξ теперь заключен внутри отрезка [a, x₁]. Применяя меч од хорд к отрезку [а, x₁], получим

и вообще

По этим же формулам находится приближенное значение корня и для случая, когда f(а) < 0, f(b)>0, f'(х) > 0, f''(х) < 0 (рис. 3.19, б).

Итак, если f'(х) ∙ f"(х) > 0, то приближенный корень вычисляется по формулам (1) и (2); если же f(х) ∙ f"(x) < 0, то – по формулам (3) и (4).

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

Если f(b) ∙ f'' (х) > 0, то неподвижен конец b, а все приближения к корню ξ лежат со стороны конца а [формулы (1) и (2)]. Если f(а)×f''(x) > 0. то неподвижен конец а, а все приближения к корню ξ лежат со стороны конца b [формулы (3) и (4).

2.3. МЕТОД НЬЮТОНА (МЕТОД КАСАТЕЛЬНЫХ)

Пусть корень уравнения f (х) = 0 отделен на отрезке [а, b], причем f'(х) и f"(x) непрерывны и сохраняют постоянные знаки на всем отрезке [а, b].

Геометрический смысл метода Ньютона состоит в том, что дуга кривой у = f(х) заменяется касательной к этой кривой (отсюда и второе название: метод касательных).

Первый случай. Пусть f(a) < 0, f(b) > 0, f’(х) > 0, f”(х) > 0 (рис. 1, а) или f(а) > 0, f(b) < 0, f’(х) < 0, f''(х) < 0 (рис. 1, б). Проведем касательную к кривой у = f(x) в точке B₀(b; f(b)) и найдем абсциссу точки пересечения касательной с осью Oх. Известно, что уравнение касательной в точке В₀(b; f(b)) имеет вид

Полагая у = 0, х = х1, получим

(1)

Теперь корень уравнения находится на отрезке [а, х₁]. Применяя снова метод Ньютона, проведем касательную к кривой в точке B₁ (x₁; f(x₁)) и полечим

и вообще

(2)

Получаем последовательность приближенных значений x₁, х₂, …, x_n, …, каждый последующий член которой ближе к корню ξ, чем предыдущий. Однако все х_n, остаются больше истинного корня ξ, т.е. х_n – приближенное значение корня ξ с избытком.

Второй случай. Пусть f(а) < 0, f (b) > 0, f'(х) > 0, f''(х) < 0 (рис. 2, а) или f(а)> 0, f(b) < 0, f '(х) < 0, f ''(x) > 0 (рис. 2, б). Если снова провести касательную к кривой у= f (x) в точке В, то она пересечет ось абсцисс в точке, не принадлежащей отрезку [a, b]. Поэтому проведем касательную в точке A₀(a; f(а)) и запишем ее уравнение для данного случая:

Полагая у = 0, x = x1 находим

(3)

Корень ξ находится теперь на отрезке [х₁, b]. Применяя снова метод Ньютона, проведем касательную в точке A₁ (x₁; f(x₁)) и получим

и вообще

(4)

Получаем последовательность приближенных значений х₁, х₂, … ,х_n,…, каждый последующий член которой ближе к истинному корню ξ, чем предыдущий, т.е. х_n– приближенное значение корня ξ с недостатком.

Сравнивая эти формулы с ранее выведенными, замечаем, что они отличаются друг от друга только выбором начального приближения: в первом случае за х₀ принимался конец b отрезка, во втором – конец а.

При выборе начального приближения корня необходимо руководствоваться следующим правилом: за исходную точку следует выбирать тот конец отрезка [а, b], в котором знак функции совпадает со знаком второй производной. В первом случае f(b) ∙ f ''(х) > 0 и начальная точка b = x₀, во втором f(a) ∙ f "(x) > 0 и в качестве начального приближения берем а = х₀.

3 .СООТВЕТСТВИЕ МЕЖДУ ПЕРЕМЕННЫМИ, ПРИНЯТЫМИ ПРИ ОПИСАНИИ ЗАДАЧИ И В ПРОГРАМЕ

Соответствие между переменными, используемыми в блок-схеме и в программном коде главной программы приведено в Таблице 1.

Соответствие между переменными, используемыми в блок-схеме и в программном коде процедуры Save приведено в Таблице 2.

Таблица 1

Соответствие между переменными, используемыми в блок-схеме и в программном коде главной программы

Обозначения принятые при описании задачи	Обозначения в программе	Наименование
а	а	Левая граница интервала
b	b	Правая граница интервала
е	е	Точность
х	х	Корень
Key	Key	Содержит символ нажатой клавиши

Таблица 2

Соответствие между переменными, принятыми при описании задачи и в процедуре Save

Обозначения принятые при описании задачи	Обозначения в программе	Наименование
f	f	Файловая переменная
S	S	Название файла

4. СТРУКТУРНАЯ СХЕМА ПРОГРАММ И ЕЕ ОПИСАНИЕ

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

Блок 1: ввод клавиши выбора пункта меню;

Блок 2: если выполняется условие Key=’1’ то выполнить блок, 3 иначе выполнить блок 4;

Блок 3: обращение к процедуре ввода исходных данных Vvod;

Блок 4: если выполняется условие Key=’2’ то выполнить блок 5, иначе выполнить блок 6;

Блок 5: обращение к процедуре поиска корня и вывода его на экранVivRez;

Блок 6: если выполняется условие Key=’3’ то выполнить блок 7, иначе выполнить блок 8;

Блок 7: обращение к процедуре поиска корня и сохранения его в файл;

Блок 8: если выполняется условие Key=’0’ то выйти из программы, иначе вернуться к блоку 1.

Структурная схема подпрограммы функции f изображена на Рис. 4.2.

Блок 1: присваивание заголовку функции заданного варианта.

Структурная схема подпрограммы процедуры PolDelизображена на Рис. 4.3.

Блок 1: вычисление начального значения х;

Блок 2: если значение функции в точке х отстоит от 0 на величину превышающую заданную точность е то выполнить цикл уточнения – перейти к блоку 3, иначе выйти из подпрограммы;

Блок 3: если функция в точке а и в точке х имеет одинаковый знак то выполнить блок 4, иначе выполнить блок 5;

Блок 4: левая граница перемещается в точку х;

Блок 5: правая граница перемещается в точку х;

Блок 6: вычисление нового значения х.

Структурная схема подпрограммы процедуры Vvodизображена на Рис. 4.4.

Блок 1: вывод запроса на ввод левой границы интервала;

Блок 2: ввод а – левой границы интервала;

Блок 3: вывод запроса на ввод правой границы интервала;

Блок 4: ввод b– правой границы интервала;

Блок 5: вывод запроса на ввод точности вычисления корня уравнения;

Блок 6: ввод е – точности вычисления корня уравнения.

Структурная схема подпрограммы процедуры Vivrezизображена на Рис. 4.5.

Блок 1: обращение к процедуре вычисления корня уравнения PolDel;