Открыть главное меню

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

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

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

 

или

 

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

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

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

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

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

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

  1.  
  2.  

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

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

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

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

 

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

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

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

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

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

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

 

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

 

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

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

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

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

Основная статья: Метод Ньютона

Одномерный случайПравить

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

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

 

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

 

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

 

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

 

Многомерный случайПравить

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

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

 ,

где  .

ЛитератураПравить

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

СсылкиПравить

См. такжеПравить