Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ИНЖИНЕРНО – ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ
ЮЖНОГО ФЕДЕРАЛЬНОГО УНИВЕРСИТЕТА
Кафедра Высшей Математики
Лабораторная работа № 2
МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.
Выполнил: Власенко И.Е.
Группа: Э-32
Номер варианта: 4
Проверила: Фоменко Н.А.
ТАГАНРОГ 2013
Теорема Больцано–Коши.
Если непрерывная на отрезке функция на концах имеет противоположные знаки, т.е.
,
то на интервале она хотя бы один раз обращается в ноль.
Метод половинного деления
Предположим, что существует корень на отрезке и знаки и различны (функция меняет знак при переходе через корень ).
Положим и и вычислим значения функции в левом конце отрезка, , и в его середине :. Сравним знаки чисел и . Если эти знаки различны, то корень лежит в интервале ; если же одинаковы, то тогда различны знаки и , и корень лежит в интервале . (Возможен ещё случай ; тогда корень уже найден). В обоих случаях смены знака корень оказывается отделён на отрезке либо , длина которого ровно в два раза меньше длины исходного отрезка . Обозначим этот отрезок половинной длины через (то есть положим в случае, когда и разных знаков, и в случае, когда и одного знака).
Далее повторим процесс для отрезка : снова отыщем его середину , найдём значение функции и сравним знак этого числа со знаком ; если знаки разные, то корень отделён на , если одинаковые, то на (или же оказывается, что ; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.
Рис.2.1. Последовательное деление отрезка пополам и приближение к корню
Поступая тем же образом и далее, получаем, что после делений длина отрезка, на котором лежит корень, сокращается в раз и становится равной (если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с при некотором ). Пусть – заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство . Очевидно, что если при этом положить в качестве корня
,
то расстояние от корня , лежащего где-то в интервале , до середины этого интервала будет не больше , то есть приближённое равенство будет выполнено с нужной точностью.
Метод хорд (метод линейной интерполяции)
Идея метода хорд состоит в том, что по двум точкам и построить прямую (то есть хорду, соединяющую две точки графика ) и взять в качестве следующего приближения абсциссу точки пересечения этой прямой с осью . Иными словами, приближённо заменить на этом шаге функцию её линейной интерполяцией, найденной по двум значениям и . (Линейной интерполяцией функции назовём такую линейную функцию , значения которой совпадают со значениями в двух фиксированных точках, в данном случае – в точках и .)
Рис 2.2. Построение последовательного приближения по методу хорд
Итак, очередное последовательное приближение будет зависеть от двух предыдущих: . Найдём выражение для функции .
Интерполяционную линейную функцию будем искать как функцию с угловым коэффициентом, равным разностному отношению
,
построенному для отрезка между и , график которой проходит через точку :
Решая уравнение , находим
,
то есть
.
Заметим, что величина может рассматриваться как разностное приближение для производной в точке . Тем самым полученная формула – это разностный аналог итерационной формулы метода Ньютона.
Вычисления ведутся непосредственно по данной формуле при , начиная с двух приближений и , взятых, по возможности, поближе к корню . При этом не предполагается, что лежит между и (и что значения функции в точках и , имеют разные знаки). При этом не гарантируется, что корень попадёт на отрезок между и на каком-либо следующем шаге (хотя это и не исключено). В таком случае затруднительно дать оценку погрешности, с которой приближает истинное значение корня , и поэтому довольствуются таким эмпирическим правилом: вычисления прекращают, когда будет выполнено неравенство , где – желаемая точность нахождения корня. При этом полагают приближённое значение корня равным .
Метод секущих
Идея метода секущих состоит в том, выбирают любую постоянную , знак которой совпадает со знаком производной в окрестности (и, в частности, на отрезке, соединяющем и ). Постоянная не зависит также и от номера шага . Тогда формула итераций оказывается очень проста:
и на каждой итерации нужно один раз вычислить значение функции .
Выясним смысл этой формулы, а также смысл условия о совпадении знаков и . Рассмотрим прямую, проходящую через точку на графике с угловым коэффициентом . Тогда уравнением этой прямой будет
Найдём точку пересечения этой прямой с осью из уравнения
откуда . Следовательно, эта прямая пересекает ось как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки , через соответствующие точки графика проводятся секущие с угловым коэффициентом того же знака, что производная . (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция или возрастает; во-вторых, что прямые, проводимые при разных , имеют один и тот же угловой коэффициент и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью .
Рис.2.3 Последовательные итерации метода секущих
На чертеже изображены итерации. Мы видим, что последовательные точки приближаются к корню, оставаясь всё время с одной стороны от него.
Метод Ньютона
Рассмотрим эффективный метод решения нелинейных уравнений, носящий имя Ньютона. Вначале приведем некоторые наводящие рассуждения. Пусть функция , корень которой ищется, имеет производные до 2-го порядка в окрестности корня - точки . Пусть уже найдено приближение номера к корню (-ая итерация) и требуется найти приближение номера . По формуле Тейлора имеем
.
Пренебрежем остаточным членом порядка в правой части формулы и будем считать, что , т.е. приближение номера найдено столь точно, что .
Тогда имеем приближенное равенство
.
Выражая отсюда при условии и переходя от приближенного равенства к точному, получим
Конечно, данные рассуждения не претендуют на роль строгого вывода и не могут служить обоснованием метода Ньютона. Перейдем к обоснованию метода Ньютона. Будем рассматривать лишь случай поиска вещественных корней.
Предположим, что уравнение
|
(2.1) |
имеет простой вещественный корень , т.е.
,
Будем предполагать, что дважды дифференцируема в некоторой окрестности точки , т.е. для всех , принадлежащих некоторому интервалу , где , причем непрерывна на отрезке , .
Исследуем сходимость метода Ньютона
|
(2.2) |
Теорема 1. Пусть - простой вещественный корень уравнения (4.1) и пусть в окрестности точки
.
Пусть непрерывна на отрезке , причем
|
(2.3) |
Тогда, если и
|
(2.4) |
то метод Ньютона (2.2) сходится, и для погрешности справедлива оценка
|
(2.5) |
Метод половинного деления.
Метод хорд.
Метод секущих.
Метод Ньютона.
Проведя данную лабораторную работу, я нашёл корень данного уравнения различными методами решения нелинейных уравнений. И, по-моему мнению самый быстрый метод – это метод Ньютона, а самый медленный – половинного деления.