Методы решения нелинейных уравнений

Будем рассматривать задачу приближенного нахождения нулей функции одного переменного, иначе, задачу нахождения корней уравнения вида

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

Теорема Больцано–Коши.

Если непрерывная на отрезке функция на концах имеет противоположные знаки, т.е.

то на интервале она хотя бы один раз обращается в ноль.

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

Предположим, что существует корень на отрезке и знаки и различны (функция меняет знак при переходе через корень ).

Положим и и вычислим значения функции в левом конце отрезка, , и в его середине : . Сравним знаки чисел и . Если эти знаки различны, то корень лежит в интервале ; если же одинаковы, то тогда различны знаки и , и корень лежит в интервале . (Возможен ещё случай ; тогда корень уже найден.) В обоих случаях смены знака корень оказывается отделён на отрезке либо , длина которого ровно в два раза меньше длины исходного отрезка . Обозначим этот отрезок половинной длины через (то есть положим в случае, когда и разных знаков, и в случае, когда и одного знака).

Далее повторим процесс для отрезка : снова отыщем его середину , найдём значение функции и сравним знак этого числа со знаком ; если знаки разные, то корень отделён на , если одинаковые, то на (или же оказывается, что ; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.

Рис.2.1. Последовательное деление отрезка пополам и приближение к корню

Поступая тем же образом и далее, получаем, что после делений длина отрезка, на котором лежит корень, сокращается в раз и становится равной (если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с при некотором ). Пусть – заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство . Очевидно, что если при этом положить в качестве корня

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

Метод хорд (метод линейной интерполяции)

Идея метода хорд состоит в том, что по двум точкам и построить прямую (то есть хорду, соединяющую две точки графика ) и взять в качестве следующего приближения абсциссу точки пересечения этой прямой с осью . Иными словами, приближённо заменить на этом шаге функцию её линейной интерполяцией, найденной по двум значениям и . (Линейной интерполяцией функции назовём такую линейную функцию , значения которой совпадают со значениями в двух фиксированных точках, в данном случае – в точках и .)

Рис 2.2. Построение последовательного приближения по методу хорд

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

Интерполяционную линейную функцию будем искать как функцию с угловым коэффициентом, равным разностному отношению

построенному для отрезка между и , график которой проходит через точку :

Решая уравнение , находим

то есть

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

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

Метод секущих

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

и на каждой итерации нужно один раз вычислить значение функции .

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

Найдём точку пересечения этой прямой с осью из уравнения

откуда . Следовательно, эта прямая пересекает ось как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки , через соответствующие точки графика проводятся секущие с угловым коэффициентом того же знака, что производная . (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция или возрастает; во-вторых, что прямые, проводимые при разных , имеют один и тот же угловой коэффициент и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью .

Рис.2.3 Последовательные итерации метода секущих

На чертеже изображены итерации. Мы видим, что последовательные точки приближаются к корню, оставаясь всё время с одной стороны от него.

Метод Ньютона

Рассмотрим эффективный метод решения нелинейных уравнений, носящий имя Ньютона. Вначале приведем некоторые наводящие рассуждения. Пусть функция y = F(x), корень которой ищется, имеет производные до 2-го порядка в окрестности корня - точки . Пусть уже найдено приближение номера n к корню (n-ая итерация) и требуется найти приближение номера n+1. По формуле Тейлора имеем

F(x_n+1) = F(x_n) + F’(x_n) × (x_n+1 – x_n) + O(x_n+1 – x_n)².

Пренебрежем остаточным членом порядка O(x_n+1 – x_n)² в правой части формулы и, будем считать, что x_n+1 » , т.е. приближение номера n+1 найдено столь точно, что F(x_n+1) » 0.

Тогда имеем приближенное равенство

0 » F(x_n) + F'(x_n) (x_n+1 – x_n).

Выражая отсюда x_n+1 при условии F'(x_n) ¹ 0, и, переходя от приближенного равенства к точному, получим

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

Предположим, что уравнение

F(x) = 0

(2.1)

имеет простой вещественный корень x_*, т.е.

F(x_*) = 0,

Будем предполагать, что F(x) дважды дифференцируема в некоторой окрестности точки x_*, т.е. для всех х принадлежащих некоторому интервалу (x_* - r₁, x_* + r₁), где r₁ > 0, причем F" (x) непрерывна на отрезке [x_* - r, x_* + r], 0 < r £ r₁.

Исследуем сходимость метода Ньютона

(2.2)

Теорема 1. Пусть x_* - простой вещественный корень уравнения (4.1) и пусть F'(x) ¹ 0 в окрестности точки. x_*

= {x: ½ x - x_*½ < r}.

Пусть, что F" (x) непрерывна на отрезке [x_*-r, x_*+r] Ì Ì , причем

(2.3)

Тогда, если и

(2.4)

то метод Ньютона (2.2) сходится, и для погрешности справедлива оценка

(2.5)

Замечания.

Метод Ньютона имеет квадратичную сходимость, т.е. он сходится быстрее метода простой итерации, который имеет линейную сходимость. Однако, метод Ньютона требует задания достаточно близкого к корню x_* начального приближения, удовлетворяющего неравенству (2.4) при соблюдении соотношений (2.3).

Пример выполнения лабораторной работы №2

Найдите корни уравнения используя методы решения нелинейных уравнений.

Вводим функцию в исходном уравнении F(x)=0

Строим график данной функции

Из графика видно, что корень находится на интервале (0, 1). Вводим концы интервала.

Задаем погрешность вычисления уравнения

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

Вводим функцию расчета нелинейных уравнений методом половинного деления

Вызываем данную функцию

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

Считаем значение функции в данной точке (оно должно быть близким к нулю)

На графике функции отмечаем значение корня уравнения

Метод хорд.

Вводим функцию расчета нелинейных уравнений методом хорд

Вызываем данную функцию

Выводим найденное при помощи метода хорд приближенное значение корня и количество итераций

Считаем значение функции в данной точке

Метод секущих.

Вводим функцию расчета нелинейных уравнений методом секущих

Вызываем данную функцию

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

Считаем значение функции в данной точке

Метод Ньютона.

Считаем производную функции F(x)

Вводим функцию расчета нелинейных уравнений методом Ньютона

Вызываем данную функцию

Выводим найденное при помощи метода Ньютона приближенное значение корня и количество итераций

Считаем значение функции в данной точке

Варианты заданий к лабораторной работе №2

Найдите корни уравнения используя методы решения нелинейных уравнений.

1. 6.

2. 7.

3. 8.

4. 9.

5. 10.

Содержание отчета

Отчет должен содержать:

1. титульный лист;

2. постановку задачи (согласно варианту);

3. краткое описание методов расчета нелинейных уравнений;

4. программную реализацию данных методов;

5. выводы о проделанной работе.

Контрольные вопросы и задания

1. Какие методы решения нелинейных уравнений вы знаете?

2. Какой из методов решения нелинейных уравнений, в вашем случае, оказался наиболее быстрым и медленным?

3. Дайте описание метода половинного деления.

4. Запишите расчетную формулу метода хорд.

5. Запишите расчетную формулу метода секущих.

6. Запишите расчетную формулу метода Ньютона.

7. Сформулируйте теорему Больцано–Коши.

8. Решите нелинейное уравнение.

9. Запишите формулу для расчета погрешности метода половинного деления.

10. Запишите формулу для расчета погрешности метода Ньютона.

123 4 5 6