- Численное решение уравнений
-
Численное решение уравнений и их систем состоит в приближённом определении корня или корней уравнения или системы уравнений и применяется в случаях, когда точное значение вычислить невозможно или очень трудоёмко.
Содержание
Постановка задачи
Рассмотрим методы численного решения уравнений и систем уравнений:
или
Численное решение задачи можно проводить как непосредственно (используя одноимённые методы), так и с применением оптимизационных методов, приведя задачу к соответствующему виду. Последним посвящена статья Градиентные методы.
Численные методы решения уравнений
Покажем, как можно решить изначальную систему уравнений, не прибегая к оптимизационным методам. В случае, если наша система представляет собой СЛАУ, целесообразно прибегнуть к таким методам, как метод Гаусса или метод Ричардсона. Однако мы всё же будем исходить из предположения, что вид функции нам неизвестен и воспользуемся одним из итерационных методов численного решения. Среди большого разнообразия таковых выберем один из наиболее известных — метод Ньютона. Этот метод в свою очередь основывается на принципах метода простой итерации. Поэтому сначала будет изложена суть последнего.
Метод простой итерации
В основе метода заложено понятие сжимающего отображения. Определим терминологию:
Говорят, что функция осуществляет сжимающее отображение на , если
Тогда основная теорема будет выглядеть так:
Теорема Банаха (принцип сжимающих отображений).
Если — сжимающее отображение на , то:- — корень;
- итерационная последовательность сходится к этому корню;
- для очередного члена справедливо .
Поясним смысл параметра . Согласно теореме Лагранжа имеем:
Отсюда следует, что . Таким образом, для сходимости метода достаточно, чтобы
.........
и так далее, пока
Применительно к СЛАУ
Рассмотрим систему:
Для неё итерационное вычисление будет выглядеть так:
Сходимость метода будет осуществлять
Следует отметить, что для оценки сходимости вычисляется не определитель матрицы, а норма матрицы. Поэтому в данном случае поставлены двойные вертикальные черты, а не одинарные.
Алгоритм
- Условие преобразуется к виду , где — сжимающая
- Задаётся начальное приближение и точность
- Вычисляется очередная итерация
- Если , то и возврат к шагу 3.
- Иначе и остановка.
Метод Ньютона (метод касательных)
Одномерный случай
Для того, чтобы решить уравнение , пользуясь методом простой итерации, необходимо привести его к виду , где — сжимающее отображение. Чтобы отображение было наиболее эффективно, необходимо, чтобы в точке очередной итерации выполнялось . Будем искать решение данного уравнения в виде , тогда:
Воспользуемся тем, что , и получим окончательную формулу для :
С учётом этого сжимающая функция примет вид:
Тогда алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:
Многомерный случай
Обобщим полученный результат на многомерный случай.
Выбирая некоторое начальное приближение , находят последовательные приближения путем решения систем уравнений:
- ,
где .
Литература
- Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
- Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
- Волков Е. А. Численные методы. — М.: Физматлит, 2003.
- Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
- Калиткин Н. Н. Численные методы. — М.: Наука, 1978.
См. также
- Метод Крамера
- Система уравнений и экстремальные задачи
- Градиентные методы
- Метод секущих
- Комбинированный метод
- Метод итераций
Категория:- Численные методы
Wikimedia Foundation. 2010.