Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Математика » Математические методы в экономике

Метод простых итераций

Полезная статья? Пожалуйста, поставьте "+"

Пусть задана нелинейная непрерывная функция действительного переменного f(x) на отрезке [a,b]?R. Требуется решить уравнение

f(x)=0 (1)

Метод простой итерации состоит в том, что уравнение (1) заменяем на основе равносильных преобразований уравнением вида

x=j(x) (2)

а затем строим последовательность приближений рис2 к корню уравнения x*по правилу

рис4 (3)

Здесь k-номер итерации. Приближенное значение корня с нулевым индексом, т.е. рис6 называют начальным приближением. Это значение выбирается из каких-либо условий конкретной задачи или берется произвольно. Подставляем это значение в правую часть соотношения (3) и получаем рис8, затем вычисленное таким образом каждое очередное приближение подставляем в правую часть и получаем рис10

В итоге получаем числовую последовательность рис2 ,которая называется последовательностью приближений или итерационной последовательностью. В этой последовательности каждое новое приближение корня рис12 уравнения (1) находится на основании только одного известного предыдущего значения рис14, т.е за один шаг (итерацию). Поэтому метод простой итерации относят к классу одношаговых методов.

Корень уравнения (1) или (2) x=x* вычисляют приближенно с относительной погрешностью e?0 так, чтобы для всех k?k0(e) стало верным неравенство

рис16 (4)

Число k0(e) - это минимальное количество итераций, при котором выполняется условие сходимости. Последовательность рис2 будет сходящейся, если при неограниченном росте числа итераций существует ее предел и этим пределом является корень уравнения x*, т.е. если при k®? $ lim{xk}=x*. Следовательно всегда можно прекратить процесс поиска корня методом простой итерации, если число итерации будет равно k0(e).

Т.о. необходимо подчеркнуть, что основным вопросом применения метода простой итерации является вопрос о его сходимости и скорости этой сходимости. Скорость сходимости характеризует изменение значений приближений к корню на двух соседних итерациях по отношению к истинному значению корня. Если для погрешности какого-либо итерационного метода выполняется неравенство

рис18 (5)

где число М не зависит от номера итерации k, а 0<q<1, то говорят, что метод сходится линейно со скоростью геометрической прогрессии со знаменателем q.

Проблемы сходимости и единственности численного решения для метода простой итерации решаются и исследуются с помощью понятия о сжимающем отображении и теоремы о достаточном условии сходимости метода. Если x=x* является корнем функции f(x), то и итерируемая функция j(x) должна обладать следующим свойством x*=j(x*), а значение x* называется неподвижной точкой функции j(x).

Дадим геометрическую интерпретацию метода простой итерации. Будем предполагать, что функции j(x) и j?(x) являются непрерывными. На плоскости X0Y построим графики функции Y=x и Y=j(x). Каждый вещественный корень x* уравнения (2) является абсциссой точки пересечения кривойY=j(x) с прямой Y=x. Начиная с некоторой точки A0(x0, j(x0)), строим ломаные линии A0B1A1B2A2…(лестница), звенья которой попеременно параллельны оси 0X и оси 0Y, причем вершины A0,A1,A2… лежат на кривой Y=j(x) . Общие абсциссы точек A1 и B1, A2 и B2 … представляют собой последовательные приближения рис20корня x*, которые сходятся к нему монотонно и односторонне.

рис22

На рисунке представлен случай, когда 0<j?(x)<1, т.е. угол касательной к графику функцииY=j(x) меньше 450, т.е.a< 450. Функция Y=j(x) является возрастающей и вогнутой. Если -1<j?(x)<0, то ломаная A0B1A1B2A2… будет иметь вид спирали. В этом случае сходимость является двусторонней, т.е. искомый корень всегда принадлежит отрезку рис24. Функция Y=j(x) является убывающей и вогнутой.

рис26

Если |j?(x)|>1, т.е. угол наклона касательной к кривой j(x) превышает 450, то в этом случае итерации сходиться не будут

рис28

Если же |j?(x)|<1 в некоторой окрестности корня, а вдали от него это неравенство не выполняется, то итерационный процесс будет сходящимся только в том случае, если начальное приближение рис6 выбрано достаточно близко к корню.

рис31

При произвольном выборе начального приближения сходимости может не быть.

рис33

Прежде, чем исследовать условия сходимости метода простой итерации, напомним понятие Липшиц-функции.

Говорят, что непрерывная на отрезке [a,b] функция f(x) удовлетворяет на этом отрезке условию Липшица, если рис35существует такая константа q, что для любых двух значениях аргумента из этого отрезка имеет место неравенство

рис37 (6)

Величину q в этом случае называют постоянной Липшица.

Доказывается, что если функция f(x) на отрезке [a,b] имеет ограниченную производнуюрис39, то она удовлетворяет условию Липшица с постоянной q=m,

Теорема о сходимости итерационной последовательности метода простой итерации имеет несколько эквивалентных формулировок. Одна из них такова.

Пусть функция j(x) из уравнения (2) на некотором отрезке рис41где x*- корень этого уравнения, удовлетворяет условию Липшица с постоянной 0<q<1. Т.е. выполняется условие |j(x1)-j(x2)| ?q |x1-x2|. Тогда при любом выборе начального приближения из окрестности корня, т.е. рис43 существует бесконечная итерационная последовательность{xk}, линейно сходящаяся к корню x*, который является единственным решением уравнения (2) на отрезке рис41. Для погрешности будет справедлива оценка

рис46 k=0,1,2,… (7)

(Доказательство теоремы - см.Самарский ЧМ с.196)

Сформулированная теорема имеет простой смысл. Будем говорить, что функция j осуществляет отображение точки x на точку y=j(x). Тогда условие Липшица с постоянной q<1 означает, что отображение j является сжимающим: расстояние между точками рис48больше, чем расстояние между их изображениями рис50. Корень x* является неподвижной точкой отображения j, он преобразуется сам в себя x*=j(x*). Поэтому каждый шаг в итерационном процессе (3), сжимая расстояния, должен приближать члены последовательности рис2 к неподвижной точке x*.

Для практического применения теорема неудобна, поэтому обычно используют следствие из этой теоремы, которое звучит следующим образом. Если функция j(x) непрерывно дифференцируема на отрезке рис41, то условие Липшица можно записать как

рис52 (8).

Если начальное приближение выбирается из этого же отрезка, то метод простой итерации сходится линейно, т.к. погрешность сходимости имеет вид рис54.

Число итераций, при котором выполняется условие сходимости рис16 (4) получаем из условия рис46 (7). На основании этих соотношений можно записать рис57 и рис59.Минимальное число итераций, при котором выполняется условие сходимости равно

рис61 (9).

Здесь [а] означают ближайшее к а сверху целое число.

Рассмотрим пример

Решить уравнение рис63 с точностью e=0.01.

Отделим корни, найдем, что существует 3 корня на отрезках [-3;-2], [-1,0] и [0;1]. Будем последовательно искать приближение на каждом отрезке.

  1. На отрезке [-3;-2] выполняется условие рис65, следовательно, можем разделить обе части уравнения f(x)=0 на рис67. Получаем

рис69 Преобразуем это уравнение рис71, которое имеет вид x=j(x) (2).

Можем записать, что рис73. Проверим условие сходимости рис75 должно выполняться неравенство рис52 на этом отрезке. Производная функции имеет вид рис77. И ее максимальное значение на отрезке [-3;-2] : max рис79=1/4, Следовательно рис81. Для проверки условия сходимости можно построить график функции рис79 на отрезке [-3;-2]. Далее следует убедиться, что на указанном отрезке максимальные по модулю значения на графике не превышают 1.

рис84

В качестве первого приближения возьмем рис86, тогда рис88

рис90

рис92 рис94

рис96

2. Рассмотрим отрезок [-1;0] . На этом отрезке не выполняется условие рис65, следовательно, мы не можем разделить обе части уравнения f(x)=0 на рис67. Приведем уравнение к виду

рис98рис100, т.е. рис102 ,

и условие сходимости выполняется

рис104 В качестве начального приближения возьмем рис106 и начнем процесс итерирования для поиска приближения с заданной точностью.

3. На отрезке [0;1] поступаем аналогично предыдущему случаю, только возьмем функцию с положительным знаком. Имеем рис108, для которой выполнение условия сходимости определим из графика

рис110Возьмем рис112 начнем процесс итерирования для поиска приближения с заданной точностью.

Так как для реализации решения уравнения f(x)=0 (1) методом простых итераций необходимо преобразовать его к виду x=j(x) (2) и выбор функции j(x) имеет большое значение для сходимости, то укажем достаточно общий прием такого преобразования.

Умножим уравнение вида (1) f(x)=0 на функцию s(x)?0, т.е. эта функция не имеет корней на отрезке [a,b], и значит функция s(x) не меняет знак на этом отрезке (в частности s(x) может быть const). Сложим полученное уравнение с тождеством x?x, получим x=x+s(x)?f(x) . Обозначим правую часть j(x)=x+s(x)?f(x). Имеем x=j(x). Подбором функции s(x)?0 добиваемся, чтобы в окрестности корня для функции j(x)=x+s(x)?f(x) выполнялось условие сжатия, т.е. рис52. При этом необходимо получить как можно меньшие значения параметра q.

В некоторых случаях после преобразования получаем, что рис114 в окрестности корня. Чтобы использовать метод простой итерации в этом случае следует представить уравнение в виде x=S(x), где рис116- функция, обратная для j(x). В этом случае будет выполняться условие сходимости для функции S(x).

Практическая схема решения нелинейного уравнения методом простой итерации состоит в следующем.

- Отделить корни уравнения (1) f(x)=0, т.е. выделить интервалы, на которых f(x) имеет один корень.

- Выбрать один из найденных интервалов и преобразовать уравнение (1) к виду (2) x=j(x).

- Для выбранной формы записи уравнения проверить выполнение теоремы о сходимости метода простой итерации. Если условие не выполняется, выбрать другой вид уравнения (2).

- Задать начальное приближение и начать итерационный процесс.

- Итерации можно закончить, если число итераций достигнет величины рис61, т.е минимального числа итераций для процесса сходимости. На практике часто условием окончания итерационного процесса служит выполнение неравенства рис118. Однако выполнение этого условия не гарантирует близости к точному решению. На рисунке достигается область, где условие окончания итерационного процесса выполняется, но корень уравнения x* расположен достаточно далеко от этой области.

рис120

Категория: Математические методы в экономике | Добавил: Ni-Cd (15 Декабрь 2011)
Просмотров: 3499 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

В нашем каталоге файлов можно найти много полезной информации. Также советуем заглянуть в каталог статей: в нем есть полезные статьи по темам: Экономика предприятия, Общая экономика, Финансы и Кредит, также Словарь терминов по экономике, Маркетинг, Бухучет и Мировая экономика
Также есть полезная страница Факультеты МИФИ, которая расскажет о том, какие есть в МИФИ факультеты.
Меню
 

Навигация
Теория вероятностей и математическая статистика (ТерВер и МатСтат) [17]
Математический анализ (МатАн) [67]
Математические методы в экономике [24]
 

Поиск
 

Онлайн
Онлайн всего: 1
Гостей: 1
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2017 © Ni-Cd. All Rights Reserved