- •Часть 1
- •Оглавление
- •Введение
- •1. Источники и причины погрешностей математической модели
- •Погрешность математической модели
- •Погрешность исходных данных
- •Погрешность численного метода
- •Погрешность проведения расчетов на вычислительных машинах
- •Погрешности округления чисел в эвм
- •Погрешность результатов вычисления арифметических операций
- •“Потеря порядка” и “переполнение” при проведении вычислений на эвм
- •Машинная реализация вычислений
- •Контрольные вопросы и задания
- •2. Системы линейных алгебраических уравнений
- •Прямые методы решения
- •Метод Гаусса
- •Определение числа операций алгоритма метода Гаусса
- •Вычисление определителя матрицы
- •Построение обратной матрицы
- •Метод квадратного корня
- •Определение числа операций алгоритма метода квадратного корня
- •Устойчивость системы линейных алгебраических уравнений
- •Итерационные методы решения
- •Метод Якоби1
- •Метод Зейделя1
- •Сходимость итерационных методов
- •Скорость сходимости
- •Полиномы Чебышёва1
- •Итерационный метод с чебышёвским набором параметров
- •Неявный метод с чебышёвским набором параметров
- •Метод минимальных невязок
- •Метод минимальных поправок
- •Метод скорейшего спуска
- •Неявный метод скорейшего спуска
- •Контрольные вопросы и задания
- •3.НелинейныЕ уравнения
- •Методы вычисления корней нелинейного уравнения1 Метод половинного деления2
- •Метод простых итераций
- •Метод Ньютона2
- •Модификации метода Ньютона
- •Системы нелинейных уравнений
- •Метод простых итераций
- •Метод релаксации
- •Метод Ньютона
- •Нелинейный вариант метода Якоби
- •Нелинейный вариант метода Зейделя
- •Контрольные вопросы и задания
- •Интерполяция степенными функциями
- •Интерполяционный многочлен Ньютона
- •Интерполяционная формула Лагранжа
- •Погрешность полинома Ньютона (Лагранжа)
- •Сходимость интерполяционного процесса
- •Интерполяционный многочлен Эрмита1
- •Интерполяция сплайнами
- •Построение кубического сплайна
- •Сходимость процесса интерполяции кубическими сплайнами
- •Наилучшее приближение в гильбертовом пространстве
- •Метод наименьших квадратов
- •Контрольные вопросы и задания
- •5. Алгебраическая проблема собственных значений
- •Устойчивость собственных значений и векторов
- •Определение собственных значений и векторов Метод интерполяции
- •Трехдиагональные матрицы
- •Поиск собственных векторов
- •Частичная проблема собственных значений
- •Метод линеаризации
- •Степенной метод
- •Метод обратных итераций
- •Контрольные вопросы и задания
- •6.Численное дифференцирование Конечно-разностная аппроксимация
- •Применение интерполяционных формул
- •Контрольные вопросы и задания
- •7.Численное интегрирование
- •Формула прямоугольников
- •Формула трапеций
- •Формула Симпсона1
- •Формула Эйлера1
- •Оценка погрешности методом Рунге2
3.НелинейныЕ уравнения
Пусть известна некоторая нелинейная зависимость вида y = f(x). Требуется определить все те значения аргумента , которые обращают функцию в нуль:
. (3.1)
Для поиска корней нелинейных уравнений, как правило (за небольшим исключением: квадратные, кубические, некоторые трансцендентные уравнения) используются итерационные методы.
Первоначально рассматриваются методы решения одного нелинейного уравнения, а затем - системы нелинейных уравнений.
Методы вычисления корней нелинейного уравнения1 Метод половинного деления2
Метод основан на одной из теорем математического анализа. Согласно [10], функция, непрерывная в замкнутом интервале и принимающая на концах этого интервала значения разных знаков, хотя бы один раз обращается в нуль внутри интервала.
Пусть функция f(x) непрерывна на отрезке . Процедура метода заключается в последовательном сокращении длины отрезка для локализации корня уравнения (3.1). Первоначально проверяются значения заданной функции на концах отрезка. В случае, если
,
один из концов отрезка является искомым корнем уравнения.
Пусть на концах отрезка значения функции имеют разные знаки, то есть имеет место соотношение
.
Вычисляется значение аргумента в середине отрезка, , и вычисляется значение функции в этой точке. Далее сравниваются знаки функции в точке и, например, в левой точке отрезка.
Если имеет место соотношение (рис. 3.1), то корень следует искать на отрезке . В противном случае - корень разыскивается на отрезке . В результате выполненной операции исходный отрезок сократился вдвое.
f(x1)
f(x3)
f(x2)
f(x4)
x0
x3
x2
x1
x4
f(x0)
Рис. 3.1. Схема метода половинного деления
Далее, в зависимости от ситуации, отрезок вновь делится пополам,
и так далее.
Для прекращения вычислительной процедуры применяются различные критерии:
- если функция достаточно “пологая”, имеет смысл использовать условие (рис.3.2a)
;
- если функция “круто” меняет свое значение, целесообразно применять условие (рис.3.2b)
.
a
b
Рис. 3.2. Частные случаи поиска корня нелинейного уравнения
В случае, если заранее неизвестен характер “поведения” функции, имеет смысл использовать одновременно оба условия для прекращения итерационного процесса.
Метод простых итераций
Этот метод заключается в замене уравнения (3.1) эквивалентным ему уравнением вида
. (3.2)
После этого строится итерационный процесс
(3.3)
при некотором заданном значении . Для приведения выражения (3.1) к требуемому виду (3.2) можно воспользоваться простейшим приемом:
Если в выражении (3.2) положить , можно получить стандартный вид итерационного процесса для поиска корней нелинейного уравнения:
.
Пример 3.1. Решим уравнение cos(x) - x = 0. Представим это уравнение в виде
.
Результаты расчетов приведены в табл. 3.1. Ход итерационного процесса отражен на рис. 3.3.
Таблица 3.1
Результаты итерационного вычисления корня уравнения cos(x) - x = 0
-
Номер итерации
Аргумент x
1
0
2
1,0
3
0,540302306
4
0,857553216
5
0,654289791
6
0,793480359
7
0,701368774
8
0,763959683
9
0,722102425
10
0,750417762
...
...
30
0,739078886
31
0,739089341
Корень уравнения (с абсолютной погрешностью не более ) равен 0,739085133.
Рис. 3.3. Поиск корня нелинейного уравнения cos(x) - x = 0
Рассмотрим отрезок длиной 2r с центром в точке a: .
Теорема 3.1. Если функция на отрезке А удовлетворяет условию Липшица1 с константой 0 < С < 1, причем
, (3.4)
то уравнение (3.2) имеет на отрезке А единственное решение , метод простой итерации сходится к при любом и имеет место оценка
. (3.5)
Доказательство.
Докажем “по индукции”, что определяемые в соответствии с формулой (3.2) величины .
по условию теоремы.
Пусть ; покажем, что и .
В силу имеем
то есть .
Теперь оценим разность получаемых решений для произвольного n:
.
Отсюда получаем
.
Для двух произвольных значений (для определенности положим p > q) на основании этого соотношения имеем
При выводе последнего соотношения использована формула для суммы членов геометрической прогрессии со знаменателем С, а также условие, что 0 < C < 1, и тем более .
Очевидно, что при имеет место
,
и в соответствии с признаком Больцано - Коши1
.
Переходя к пределу в соотношении , в силу непрерывности функции получаем:
,
то есть - решение уравнения (3.2).
Теперь покажем, что получаемое решение единственно. В самом деле, пусть - два различных решения уравнения (3.2). Тогда
,
что может иметь место при условии 0 < C < 1 лишь в случае .
Оценим погрешность метода простой итерации после выполнения N итераций:
,
откуда получаем:
.
Что и требовалось доказать.
Следствие 1. Если , а также имеет место соотношение
,
то уравнение (3.2) имеет единственное решение, метод простых итераций сходится и имеет место оценка (3.5).
Действительно, согласно теореме Лагранжа1,
,
то есть в качестве константы условия Липшица можно принять
.
В этом случае условия теоремы (3.1) выполняются и все ее утверждения имеют место.