- •Раздел 6.
- •Раздел 6. Модели и алгоритмы решения задач численными методами с использованием математических пакетов Рекомендации по использованию учебного пособия
- •Тема 6.1. Элементы теории погрешностей
- •6.1.1. Точные и приближенные числа
- •6.1.2. Абсолютная и относительная погрешность
- •Тема 6.2. Методы решения нелинейных уравнений
- •6.2.1. Постановка задачи
- •Отделение корней (локализация корней);
- •Итерационное уточнение корней.
- •6.2.2. Отделение корней
- •6.2.2.1. Графическое отделение корней
- •6.2.2.2. Аналитическое отделение корней
- •6.2.3. Уточнение корней
- •6.2.3.1. Метод половинного деления
- •6.2.3.2. Метод итерации
- •6.2.3.3. Метод Ньютона (метод касательных)
- •6.2.3.4. Метод хорд
- •6.2.3.5. Сравнение методов решения нелинейных уравнений
- •6.2.4. Технология решения нелинейных уравнений средствами MathCad
- •Тема 6.3. Интерполяция функций
- •6.3.1. Постановка задачи
- •6.3.2. Интерполяционная формула Лагранжа
- •6.3.3. Интерполяционные формулы Ньютона
- •6.3.3.1. Конечные разности
- •6.3.3.2. Первая интерполяционная формула Ньютона
- •6.3.3.3. Вторая интерполяционная формула Ньютона
- •6.3.4. Сплайн – интерполяция
- •6.3.5. Сравнение интерполяционных многочленов по применению
- •6.3.6. Технология интерполяции функций в среде математических пакетов
- •Тема 6.4. Численное интегрирование
- •6.4.1. Постановка задачи
- •6.4.2. Метод прямоугольников
- •6.4.3. Формула трапеций
- •6.4.4. Формула Симпсона
- •6.4.5. Оценка погрешности численного интегрирования
- •6.4.6. Технология вычисления интегралов в среде математических пакетов
- •Тема 6.5. Методы решения обыкновенных дифференциальных уравнений
- •6.5.1. Постановка задачи
- •6.5.2. Метод Эйлера
- •6.5.3. Методы Рунге-Кутты
- •6.5.4. Решение оду n-го порядка
- •6.5.5. Сравнение методов решения оду
- •6.5.6. Технология решения обыкновенных дифференциальных уравнений средствами математических пакетов
- •6.6.2. Метод дихотомии
- •6.6.3. Метод золотого сечения
- •6.6.4. Сравнение методов
- •6.6.5. Технология решения задач одномерной оптимизации средствами математических пакетов
- •Тема 6.7. Аппроксимация функций
- •6.7.1. Постановка задачи аппроксимации
- •6.7.2. Метод наименьших квадратов
- •6.7.3. Технология решения задач аппроксимации функций средствами математических пакетов
- •Тема 6.8. Многомерная оптимизация
- •6.8.1. Постановка задачи и основные определения
- •6.8.2. Методы спуска
- •6.8.3. Метод градиентного спуска с дроблением шага
- •6.8.4. Метод наискорейшего спуска
- •6.8.5. Проблема оврагов. Метод покоординатного спуска
- •6.8.6. Технология решения задач многомерной оптимизации средствами математических пакетов
- •Список литературы
- •Тема 6.4. Численное интегрирование................................................71
- •Тема 6.5. Методы решения обыкновенных дифференциальных Уравнений............................................................................. 92
- •Тема 6.6. Одномерная оптимизация................................................ 115
- •Тема 6.7. Аппроксимация функций....................................................132
- •Тема 6.8. Методы многомерной оптимизации............................... 149
- •Список литературы.................................................................... 204
6.2.3.2. Метод итерации
Метод итераций предполагает замену уравнения f(x)=0 равносильным уравнением x=j(x). Если корень уравнения отделен на отрезке [a;b], то исходя из начального приближения x0Î[a;b], можно получить последовательность приближений к корню
x1 = j(x0), x2 = j(x1), …, , (6.2.3-3)
где функция j(x) называется итерирующей функцией.
Условие сходимости метода простой итерации определяется следующей теоремой.
Пусть корень х* уравнения x=j(x) отделен на отрезке [a;b] и построена последовательность приближений по правилу xn=j(xn-1). Тогда, если все члены последовательности xn=j(xn-1) Î [a;b] и существует такое q (0<q<1), что для всех х Î [a; b] выполняется |j’(x)| = q<1, то эта последовательность является сходящейся и пределом последовательности является значение корня x*, т.е. процесс итерации сходится к корню уравнения независимо от начального приближения.
Таким образом, если выполняется условие сходимости метода итераций, то последовательность x0, x1, x2, …, xn,…, полученная с помощью формулы xn+1 = j(xn), сходится к точному значению корня :
если
Условие j(x)Î[a;b] при xÎ[a;b] означает, что все приближения x1, x2, …, xn,…, полученные по итерационной формуле, должны принадлежать отрезку [a;b], на котором отделен корень.
Для оценки погрешности метода итерации справедливо условие
(6.2.3-4)
За число q можно принимать наибольшее значение |j'(x)|, а процесс итераций следует продолжать до тех пор, пока не выполнится неравенство
(6.2.3-5)
На практике часто используется упрощенная формула оценки погрешности. Например, если 0<q½ то |xn-1 - xn| £ .
Геометрическая иллюстрация метода итераций. Построим на плоскости X0Y графики функций y=x и y=j(x). Корень уравнения х=j(x) является абсциссой точки пересечения графиков функции y = j(x) и прямой y=x. Возьмем некоторое начальное приближение x0 Î [a;b]. На кривой y = j(x) ему соответствует точка А0 = j(x0). Чтобы найти очередное приближение, проведем через точку А0 прямую горизонтальную линию до пересечения с прямой y = x (точка В1) и опустим перпендикуляр до пересечения с кривой (точка А1), то есть х1=j(x0). Продолжив построение аналогичным образом, имеем ломаную линию А0, В1, А1, В2, А2…, для которой общие абсциссы точек представляют собой последовательное приближение х1, х2, …, хn («лестницу») к корню х*. Из рис. 6.2.3-3а видно, что процесс сходится к корню уравнения.
Рассмотрим теперь другой вид кривой y = j(x) (рис. 6.2.6b). В данном случае ломаная линия А0, В1, А1, В2, А2…имеет вид “спирали”, и в этом случае наблюдается сходимость.
a) b)
Рис. 6.2.3-3
Нетрудно видеть, что в первом случае для производной выполняется условие 0< j’(x)< 1, а во втором случае производная j’(x)<0 и j’(x)>-1. Таким образом, очевидно, что если |j’(x)|<1, то процесс итераций сходится к корню.
Теперь рассмотрим случаи, когда |j’(x) |> 1. На рис. 6.2.3-4а показан случай, когда j’(x) >1, а на рис. 6.2.3-4b – когда j’(x) < -1. В обоих случаях процесс итерации расходится, то есть, полученное на очередной итерации значение х все дальше удаляется от истинного значения корня.
b)
Рис. 6.2.3-4
Способы улучшения сходимости процесса итераций. Рассмотрим два варианта представления функции j(x) при переходе от уравнения f(x) к x=j(x).
Пусть функция j(x) дифференцируема и монотонна в окрестностях корня и существует число k £ |j‘(x)|, где k ³ 1 (т.е. процесс расходится). Заменим уравнение х=j(x) эквивалентным ему уравнением х=Y(х), где Y(х) = 1/j(x) (перейдем к обратной функции). Тогда
а значит q=1/k < 1 и процесс будет сходиться.
Представим функцию j(x) как j(x) = х - lf(x), где l - коэффициент, не равный
нулю. Для того чтобы процесс сходился, необходимо, чтобы 0<|j¢(x)| = |1 - lf¢(x)| < 1. Возьмем l= 2/(m1+M1), где m1 и M1 – минимальное и максимальное значения f’(x) (m1=min|f’(x)|, M1=max|f’(x)|) для хÎ[a;b], т.е. 0£ m1 £ f¢(x) £ M1£1. Тогда
и процесс будет сходящимся, рекуррентная формула имеет вид
Если f¢(x) < 0, то в рекуррентной формуле f(x) следует умножить на -1.
Параметр λ может быть также определен по правилу:
Если , то , а если , то , где .
Пример 6.2.3-2. Уточнить корень уравнения 5x – 8∙ln(x) – 8 =0 с точностью 0.1, который локализован на отрезке [3;4].
Приведем уравнение к виду, удобному для итераций:
Следовательно, за приближенное значение корня уравнения принимаем значение x3=3.6892, обеспечивающее требуемую точность вычислений. В этой точке f(x3)=0.0027.