АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. A) Зам.директора по УР, методист, тренера по вилам спорта
  2. A) Метод опроса
  3. A) Устойчивая система средств, методов и приемов общения тренера с спортсменами
  4. B) подготовка, системно построенная с помощью методов-упражнений, представляющая по сути педагогический организованный процесс управления развитием спортсмена
  5. I. ГОСУДАРСТВЕННАЯ ВЛАСТЬ — ПРОСТОЙ ФАКТ
  6. I. Карта методической обеспеченности учебной дисциплины
  7. I. Метод стандартизации
  8. I. Методы выбора инновационной политики
  9. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  10. I. Основные характеристики и проблемы философской методологии.
  11. I. ПРОБЛЕМА И МЕТОДИКА ИССЛЕДОВАНИЯ
  12. I.1.3. Организационно-методический раздел

Для применения метода простых итераций уравнение (4.1) предварительно представляют в виде (4.28):

 

. (4.28)

 

Очевидно, что корнем данного уравнения является абсцисса точки пересечения кривых и (смотрите рисунок 4).

 

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

На отрезке выбирают нулевое приближение корня , и все последующие значения строят по правилу:

 

, , …, , …. (4.29)

 

Если последовательность, построенная по правилу (4.29), сходится к числу , то для непрерывной функции , переход к пределу в равенстве (4.30)

 

(4.30)

 

приводит к равенству

 

, (4.31)

 

что означает, что - корень уравнения (4.28).

 

Геометрически данный процесс выглядит следующим образом (смотрите рисунок 4).

 

 

 

Рисунок 4 – Геометрическая интерпретация метода простых итераций

 

 

Точке на графике функции соответствует точка , через точку проводим прямую до пересечения с прямой в точке , из точки опускаем перпендикуляр на ось ОХ, абсцисса точки пересечения данного перпендикуляра с осью ОХ – приближение . Нетрудно заметить, что .

Точке на графике функции соответствует точка , через точку проводим прямую до пересечения с прямой в точке , из точки опускаем перпендикуляр на ось ОХ, абсцисса точки пересечения данного перпендикуляра с осью ОХ – приближение . Нетрудно заметить, что .

Продолжая этот процесс, замечаем, что для получения n -го приближения необходимо через точку провести прямую до пересечения с прямой в точке , из точки опустить перпендикуляр на ось ОХ, абсцисса точки пересечения данного перпендикуляра с осью ОХ – приближение . Нетрудно заметить, что .

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

 

Очевидно, что поведение итерационного процесса, задаваемого, по правилу (4.29) зависит от свойств функции . На рисунке 5 представлена геометрическая иллюстрация поведения итерационного процесса в четырех простейших случаях взаимного расположения прямой y = x и кривой .

 

 

Рисунок 5

 

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

Нетрудно заметить, что для ситуаций а и б (модуль тангенса угла наклона кривой к оси абсцисс меньше единицы). А на рисунках в и г, - . Это дает возможность предположить, что сходимость метода простой итерации связана с выполнением условия ([3], стр. 99).

Справедливость этого предположения подтверждается следующей теоремой, с доказательством которой можно ознакомиться в [3], стр. 100.

 

Теорема. Если в некоторой s-окрестности корня функция дифференцируема и удовлетворяет неравенству

 

, (4.32)

 

где q - постоянная, удовлетворяющая условию , то независимо от выбора начального приближения из указанной s-окрестности корня итерационная последовательность, построенная по правилу (4.29), не выходит из этой окрестности, метод сходится со скоростью геометрической прогрессии и справедлива следующая оценка погрешности:

 

. (4.33)

 

 

Оценка (4.33) является априорной и на практике практически не используется, однако позволяет сделать вывод, что ([3], стр. 101):

· чем меньше q, тем выше скорость сходимости;

· чем меньше погрешность начального приближения, тем меньше итераций потребуется сделать для достижения заданной точности.

 

 

На практике, как правило, используют апостериорные оценки погрешностей, наличие и формулы для которых отражены в следующих теоремах.

 

Теорема. Пусть функция определена и дифференцируема на отрезке . Тогда, если выполняются условия:

1) ;

2) ,

 

то уравнение (4.28) имеет и притом единственный на отрезке корень ; к этому корню сходится последовательность , определяемая по формулам (4.29), начиная с любого ; при этом для любого справедливы следующие оценки погрешности:

 

, (4.34)

 

. (4.35)

 

Доказательство данной теоремы имеется в [5], стр. 248 – 250.

 

Условие , является в данном случае не необходимым, а достаточным, и в [5], стр. 251 имеется и другой признак сходимости последовательности, построенной по правилу (4.49), к корню уравнения (4.28).

 

Теорема. Пусть на отрезке функция определена, дифференцируема и её производная удовлетворяет неравенству . Тогда, если величина r такова, что

 

, (4.36)

 

то на найдется единственный корень уравнения (4.28), и к нему сходится начатый с метод простых итераций (4.29) с оценками погрешности (4.34) и (4.35).

 

 

Оценку (4.34) используют в практических вычислениях в качестве критерия окончания вычислительного процесса. Если требуется вычислить корень с точностью , расчет ведется до тех пор, пока ([5], стр. 251):

 

. (4.37)

 

Как только условие (4.36) перестает выполняться, расчет прекращают и полагают .

 

Из (4.35) легко получается приблизительная оценка (4.38) для числа итераций ([5], стр. 251):

 

. (4.38)

 

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

Теорема. Если - корень уравнения (4.28) и , где , тогда последовательность , построенная по правилу (4.29), где в качестве взято любое число из отрезка , для которого не выходит за пределы отрезка , сходится к указанному значению . При этом:

 

a) если , то

 

; (4.39)

 

b) если , то

 

. (4.40)

 

 

Доказательство сходимости последовательности, построенной по правилу (4.29), при данных ограничениях на функцию и вывод формулы (4.40) для оценки погрешности можно найти в [7], стр. 391 – 393; вывод формулы (4.39) имеется в [12], стр. 177-181.

 

В [3], стр. 104 дополнительно отмечается, что:

1) если , то сходится к , монотонно возрастая при , и монотонно убывая при ;

2) если , то сходимость к носит колебательный характер, то есть при всех значения и расположены по разные стороны от , причем последовательности приближений с четными и нечетными номерами сходятся к монотонно.

Геометрическая иллюстрация данного факта представлена на рисунках 5а и 5б.

 

Используя оценки (4.39) и (4.40), можно находить приближенное значение корня уравнения (4.28) с заданной степенью точности .

 

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

 

· , если ; (4.41)

 

· , если е . (4.42)

 

Как только данные неравенства перестанут выполняться, расчет прекращают и полагают .

 

Ключевой момент в методе итераций – приведение уравнения (4.1) к виду (4.28) так, чтобы выполнялось требование .

В тех случаях, когда простой перенос слагаемых не дает нужно результата, можно воспользоваться следующим искусственным приемом ([3], стр. 105).

 

Если производная на непрерывна и положительна, то исходное уравнение (4.1) представляют в виде:

 

, (4.43)

 

т.е. полагают

 

, (4.44)

 

где - некоторое положительное число.

 

Выбор конкретного значения параметра a осуществляют таким образом, чтобы выполнялись условия сходимости итерационного процесса.

Так как производная непрерывна и положительна, то она достигает на этом отрезке свои наименьшее и наибольшее значения, т.е. существуют положительные постоянные m и M, такие что

 

. (4.45)

 

В этом случае,

 

(4.46)

 

и, следовательно,

 

. (4.47)

 

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

 

 

Если производная на непрерывна и отрицательна, то обе части исходного уравнения (4.1) следует умножить на -1, что приведет к рассмотренному выше алгоритму.

 

 

 


1 | 2 | 3 | 4 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.019 сек.)