- •Таганрогский государственный радиотехнический университет
- •Введение
- •1 Численное интегрирование
- •1.1 Основные методы численного интегрирования
- •1.2 Пример выполнения лабораторной работы №1
- •1.3 Варианты заданий к лабораторной работе №1
- •2 Методы решения нелинейных уравнений
- •2.1 Метод половинного деления
- •2.2 Метод хорд (метод линейной интерполяции)
- •2.3 Метод секущих
- •2.4 Метод Ньютона
- •2.5 Пример выполнения лабораторной работы №2
- •2.6 Варианты заданий к лабораторной работе №2
- •3 Прямые методы решения систем линейных алгебраических уравнений
- •3.1 Метод Гаусса для решения систем линейных алгебраических уравнений.
- •3.2. Алгоритм lu-разложения.
- •3.3. Метод прогонки.
- •3.4 Пример выполнения лабораторной работы №3
- •Вводим функцию, реализующую алгоритм прогонки
- •3.5 Варианты заданий к лабораторной работе №3
- •4 Итерационные методы решения систем линейных алгебраических уравнений
- •4.1. Итерационные методы Якоби и Зейделя.
- •4.2. Каноническая форма итерационных методов.
- •4.3. Вариационно-итерационные методы решения слау.
- •4.4 Пример выполнения лабораторной работы №4
- •Задаем матрицу коэффициентов и столбец свободных членов
- •Вводим функцию, реализующую алгоритм метода Зейделя
- •4.5 Варианты заданий к лабораторной работе №4
- •5 Методы решения задачи Коши
- •5.1. Метод Эйлера.
- •5.2. Метод Рунге-Кутта.
- •Пример выполнения лабораторной работы №5
- •5.4 Варианты заданий к лабораторной работе №5
- •6 Методы приближения функций
- •6.1. Интерполяционный полином Лагранжа и Ньютона.
- •6.2 Интерполяционный кубический сплайн.
- •6.3 Понятие о методе наименьших квадратов.
- •6.4 Интерполяционный тригонометрический полином
- •6.5 Пример выполнения лабораторной работы №6
- •Интерполяционный полином Лагранжа.
- •6.6 Варианты заданий к лабораторной работе №6
2.4 Метод Ньютона
Рассмотрим эффективный метод решения нелинейных уравнений, носящий имя Ньютона. Вначале приведем некоторые наводящие рассуждения. Пусть функция y = F(x), корень которой ищется, имеет производные до 2-го порядка в окрестности корня - точки . Пусть уже найдено приближение номера n к корню (n-ая итерация) и требуется найти приближение номера n+1. По формуле Тейлора имеем
F(xn+1) = F(xn) + F’(xn) (xn+1 – xn) + O(xn+1 – xn)2.
Пренебрежем остаточным членом порядка O(xn+1 – xn)2 в правой части формулы и, будем считать, что xn+1 , т.е. приближение номера n+1 найдено столь точно, что F(xn+1) 0.
Тогда имеем приближенное равенство
0 F(xn) + F'(xn) (xn+1 – xn).
Выражая отсюда xn+1 при условии F'(xn) 0, и, переходя от приближенного равенства к точному, получим
Конечно, данные рассуждения не претендуют на роль строгого вывода и не могут служить обоснованием метода Ньютона. Перейдем к обоснованию метода Ньютона. Будем рассматривать лишь случай поиска вещественных корней.
Предположим, что уравнение
F(x) = 0 |
(2.1) |
имеет простой вещественный корень x* , т.е.
F(x*) = 0,
Будем предполагать, что F(x) дважды дифференцируема в некоторой окрестности точки x*, т.е. для всех х принадлежащих некоторому интервалу (x* - r1, x* + r1), где r1 > 0, причем F"(x) непрерывна на отрезке [x* - r, x* + r], 0 < r r1.
Исследуем сходимость метода Ньютона
|
(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.5 Пример выполнения лабораторной работы №2
Найдите корни уравнения используя методы решения нелинейных уравнений.
Вводим функцию в исходном уравнении F(x)=0
Строим график данной функции
Из графика видно, что корень находится на интервале (0,1). Вводим концы интервала.
Задаем погрешность вычисления уравнения
Метод половинного деления.
Вводим функцию расчета нелинейных уравнений методом половинного деления
Вызываем данную функцию
Выводим найденное при помощи метода половинного деления приближенное значение корня и количество итераций
Считаем значение функции в данной точке (оно должно быть близким к нулю)
На графике функции отмечаем значение корня уравнения
Метод хорд.
Вводим функцию расчета нелинейных уравнений методом хорд
Вызываем данную функцию
Выводим найденное при помощи метода хорд приближенное значение корня и количество итераций
Считаем значение функции в данной точке
Метод секущих.
Вводим функцию расчета нелинейных уравнений методом секущих
Вызываем данную функцию
Выводим найденное при помощи метода секущих приближенное значение корня и количество итераций
Считаем значение функции в данной точке
Метод Ньютона.
Считаем производную функции F(x)
Вводим функцию расчета нелинейных уравнений методом Ньютона
Вызываем данную функцию
Выводим найденное при помощи метода Ньютона приближенное значение корня и количество итераций
Считаем значение функции в данной точке