Interested Article - Численное решение уравнений

Численное решение уравнений и их систем состоит в приближённом определении корней уравнения или системы уравнений и применяется в случаях, когда точный метод решения неизвестен или трудоёмок.

Постановка задачи

Рассмотрим методы численного решения уравнений и систем уравнений :

или

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

Численные методы решения уравнений

Покажем, как можно решить изначальную систему уравнений , не прибегая к оптимизационным методам . В случае, если наша система представляет собой СЛАУ , целесообразно прибегнуть к таким методам, как метод Гаусса или . Однако мы всё же будем исходить из предположения, что вид функции нам неизвестен, и воспользуемся одним из итерационных методов численного решения . Среди большого разнообразия таковых выберем один из наиболее известных — метод Ньютона . Этот метод в свою очередь основывается на принципе сжимающего отображения. Поэтому сначала будет изложена суть последнего.

Сжимающее отображение

Определим терминологию:

Говорят, что функция осуществляет сжимающее отображение на , если

Тогда справедлива следующая основная теорема:

Теорема Банаха (принцип сжимающих отображений).
Если — сжимающее отображение на , то:
  1. Уравнение имеет единственный корень в ;
  2. Итерационная последовательность сходится к этому корню;
  3. Для очередного члена справедливо .

Из последнего пункта теоремы вытекает, что скорость сходимости любого метода на основе сжимающих отображений не менее линейной.

Поясним смысл параметра для случая одной переменной. Согласно теореме Лагранжа имеем:

Отсюда следует, что . Таким образом, для сходимости метода достаточно, чтобы

Общий алгоритм последовательных приближений

  1. Уравнение преобразуется к уравнению с тем же корнем вида , где — сжимающее отображение.
  2. Задаётся начальное приближение и точность
  3. Вычисляется очередная итерация
    • Если , то и возврат к шагу 3.
    • Иначе и остановка.

Применительно к общему случаю операторных уравнений этот метод называется методом последовательных приближений или методом простой итерации . Однако уравнение можно преобразовывать к сжимающему отображению , имеющему тот же корень, разными способами. Это порождает ряд частных методов, имеющих как линейную, так и более высокие скорости сходимости.

Применительно к СЛАУ

Рассмотрим систему:

Для неё итерационное вычисление будет выглядеть так:

Метод будет сходится с линейной скоростью, если

Двойные вертикальные черты означают некоторую норму матрицы .

Решение уравнения cos(x)=x по методу простой итерации, очередная итерация: x n+1 =cos x n , начальное приближение: x 1 = −1
Решение уравнения f(x)=0 по методу Ньютона, начальное приближение: x 1 =a.

Метод Ньютона (метод касательных)

Одномерный случай

Оптимизация преобразования исходного уравнения в сжимающее отображение позволяет получить метод с квадратичной скоростью сходимости.

Чтобы отображение было наиболее эффективно, необходимо, чтобы в точке очередной итерации выполнялось . Будем искать решение данного уравнения в виде , тогда:

Воспользуемся тем, что , и получим окончательную формулу для :

С учётом этого сжимающая функция примет вид:

Тогда алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

Многомерный случай

Обобщим полученный результат на многомерный случай.

Выбирая некоторое начальное приближение , находят последовательные приближения путём решения систем уравнений:

,

где .

См. также

Литература

  1. Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М. : Мир, 1998.
  2. Бахвалов Н. С., Жидков Н. П. , Кобельков Г. Г. Численные методы. — 8-е изд. — М. : Лаборатория Базовых Знаний, 2000.
  3. Волков Е. А. Численные методы. — М. : Физматлит, 2003.
  4. Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — М. : Энергоатомиздат, 1972.
  5. Калиткин Н. Н. Численные методы. — М. : Наука, 1978.

Ссылки

Источник —

Same as Численное решение уравнений