Локализация и отделение корня

ЛЕКЦИЯ 3

Постановка задачи

Пусть требуется решить уравнение .

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

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

Приближенное решение уравнения распадается на несколько задач:

·Локализация и отделение корня.

·Вычисление корня уравнения с заданной точностью .

Локализация и отделение корня

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

Отделение корня ¾ нужно указать отрезок , внутри которого лежит один и только один корень данного уравнения.

Оба шага выполняются с помощью исследования функции методами математического анализа. Обычно строится схема графика функции и на основании первой теоремы Больцано–Коши и признака монотонности функции делается вывод.

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

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

Т.о. первая теорема обеспечивает существование корня на отрезке, а вторая его единственность.

Пример 1.

Дано уравнение . Отделить корень уравнения.

Перепишем уравнение в виде и построим графики функций.

Из рисунка видно, что корень принадлежит отрезку . Обоснуем это аналитически.

непрерывная.

, по теореме 1.1 на отрезке существует корень.

на , значит функция возрастает. Это обеспечивает единственность корня.

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

Пусть имеется отрезок , содержащий единственный корень уравнения .

Ограничения. Никаких ограничений для функции нет.

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

Теорема 3. Для любой последовательности вложенных отрезков существует единственная точка, принадлежащая всем отрезкам этой последовательности.

Эта точка и есть корень уравнения.

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

Скорость сходимости.

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

Достоинства метода.

· Метод очень прост.

· Не имеет ограничений

· Легко программируется.

Недостатки метода.

· Если есть проблемы с отделением корня и в отрезке их несколько, то не понятно к какому сходимся.

· Метод не применим к корням четной кратности.

· Не обобщается на системы уравнений.

Пример 2.

Вычислим корень уравнения с точностью .

			-1	1,718
	0,5		-0,101	1,718	0,5
	0,5	0,75	-0,101	0,68	0,25
	0,5	0,625	-0,101	0,259	0,125
	0,5	0,563	-0,101	0,071	0,063
	0,531	0,563	-0,016	0,071	0,032
	0,531	0,547	-0,016	0,027	0,016
	0,531	0,539	-0,016	0,005	0,008<

Метод хорд

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

Алгоритм. Через точки кривой проведем хорду: или после преобразований .

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

т.е.

или .

Эту точку будем считать первым приближением корня, т.е. .

Теперь вместо отрезка можно использовать . При этом получим точку и т.д.

Таким образом, получим последовательность значений : если , то .

На следующем рисунке

, тогда .

Теорема 4. Если функция непрерывна и выпукла на отрезке и , то уравнение имеет на отрезке единственный корень, и последовательность монотонно сходится к нему.

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

При выборе нулевого приближения следует руководствоваться рисунком или следующим правилом: .

Правило остановки.

Если , то вычисления можно прекратить, когда выполнено условие . Это правило универсальное и может быть использовано для любого метода. Причем в силу выпуклости функции можно утверждать, что .

Пример 3.

Вычислим корень уравнения с точностью .

Ранее установлено, что корень принадлежит отрезку .

, для всех .

Т.к. , возьмем , .

Будем использовать правило остановки 1, для этого вычислим и и возьмем .

		-1
	0,368	-0,42
	0,492	-0,122
	0,526	-0,032
	0,534	-0,008<

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

Ограничения. Те же что и для метода хорд.

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

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

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

Правило остановки.

Можно использовать правила из предыдущего метода.

Скорость сходимости. При выборе начального приближения из достаточно малой окрестности корня метод сходится квадратично, т.е. скорость сходимости велика. Для кратного корня скорость геометрической прогрессии.

Пример 4.

Вычислим корень уравнения с точностью .

Возьмем , т.к. .

Будем использовать правило остановки 4, для этого вычислим и . Тогда

	0,636	0,364
	0,543	0,093
	0,537	0,006<

Поскольку методы касательных и хорд дают приближения один с избытком, а другой с недостатком их часто используют совместно - комбинированный метод. В этом случае получаем систему вложенных отрезков содержащих корень уравнения.

В этом случае можно использовать следующее правило остановки: .

Пример 5.

	0,368	0,636	0,268
	0,492	0,543	0,051
	0,526	0,537	0,011
	0,534	0,537	0,003<

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

Ограничения. Метод итераций применяется при решении уравнений вида .

Отметим, что любое уравнение, записанное в стандартной форме , может быть записано в виде .

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

Можно доказать теорему.

Теорема 5. Если дифференцируема на отрезке , причем , то она является сжимающей, и в качестве можно взять .

В основе метода итераций лежит теорема.

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

Алгоритм. Последовательные приближения вычисляем по формуле .

Правило остановки.

Правило 1. Число итераций, необходимое для достижения заданной точности определяется из неравенства . Достоинство этого способа в возможности нахождения числа итераций заранее.

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

Пример 6.

Запишем уравнение в виде , тогда и . Производная монотонна на отрезке . Но , поэтому сузим отрезок до . Тогда

	0,5
	0,56	0,06
	0,523	0,037
	0,546	0,023
	0,532	0,015
	0,541	0,009
	0,535	0,006
	0,539	0,004
	0,536	0,002<

Скорость сходимости. Определяется значением .

Методы обеспечивающие сходимость итераций.

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

Достоинства метода.

· Не накапливается ошибка вычислений. Ухудшение очередного приближения отразится лишь на числе итераций.

Недостатки метода.

· Подбор сжимающей функции с небольшим значением .

Пример 7.

Воспользуемся этим приемом для решения уравнения . . .

и . , .