Итерационные методы решения нелинейных уравнений - OXFORDST.RU

Итерационные методы решения нелинейных уравнений

Итерационные методы решения нелинейных уравнений

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

Представим уравнение через и многократным применением формулы до тех пор, пока не даст , где – заданная погрешность вычисления.

б). Метод деления отрезка пополам (Дихотомии).

Для :

1. находим ;

2. вычисляем ;

3. если , задаем , иначе .

4. Проверяем условие : если оно выполняется, идем к п.1., если не выполняется, заканчиваем вычисление и считаем, что приблизительно равен искомому решению исходного уравнения с заданной точностью .

Число итераций при использовании этого метода

.

Пусть имеем уравнение , где — непрерывная функция на , имеющая непрерывные и .

Корень считается отделенным и находится на отрезке , т.е.

Уравнение хорды проходящей через точку А и В (см. рис.5.1, рис.5.2)

Рис. 5.1

Рис. 5.2

.

Найдем х = х1, для которого y = 0

.

Если корень нас не устраивает, то мы находим

;

;

.

Рассмотрим случай, когда первая и вторая производные имеют разные знаки. (рис.5.3):

, .

Рис. 5.3

,

,

.

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

Г). Метод Ньютона.

Пусть корень уравнения f(x) = 0 отделен на отрезке [a, b], причем и непрерывны и сохраняют постоянные значения на всем отрезке [a, b].

Геометрический смысл метода Ньютона в том, что дуга кривой y = f(x) заменяется касательной к этой кривой.

Первый случай (рис.5.4):

f(a) 0 , > 0 , > 0(основная линия)

f(a) > 0 , f(b) .

Второй случай (рис. 5.5):

f(a) 0 , > 0 , 0 , f(b) 0(пунктирная линия),

.

Рис. 5.5

Полагая y = 0 , х = х1, получим

, , . . . , .

При выборе начального приближения корня необходимо руководствоваться правилом: за исходную точку следует выбирать тот конец [a, b], в котором знак функции совпадает со знаком , т.е.

, a = x .

д). Модифицированный метод Ньютона.

Заключается в том, что вместо вычисления производной на каждом шаге итераций находится ее приближенное значение

, .

Следовательно, итерационная формула имеет вид

.

Значение не обязательно должно быть постоянно. Равенство позволяет уменьшить число исходных данных при вводе.

Метод Рыбакова

Можно рассматривать этот метод как модификацию метода Ньютона. При замене некоторым числом , где – значение х на [a, b] , при котором производная максимальна.

При сходимость не нарушается, но замедляется.

Метод Рыбакова удобен для поиска всех корней уравнения f(x) = 0 на [a,b] .

1. Задаем начальные значения х = х = а .

2. Для каждой последовательной итерации ( n = 0, 1, 2, …) вычисляем

и проверяем условие xn

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

Метод половинного деления

Дано нелинейное уравнение:

( 4.1)

Найти корень уравнения, принадлежащий интервалу [a,b] , с заданной точностью .

Для уточнения корня методом половинного деления последовательно осуществляем следующие операции :

  1. Делим интервал пополам:

a) Вычисляем значение функции f(x) в точках a и t .

b) Проверяем: если f(a)f(t) , то корень находится в левой половине интервала [a,b] (рис.4.4.а). Тогда отбрасываем правую половину интервала и делаем переприсвоение b=t .

c) Если f(a)f(t) не выполняется, то корень находится в правой половине интервала [a,b] (рис.4.4.б). Тогда отбрасываем левую половину и делаем переприсвоение a=t . В обоих случаях мы получим новый интервал [a,b] в 2 раза меньший предыдущего.

Схема алгоритма уточнения корней по методу половинного деления представлена на рис. 4.5.

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

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

Пусть с точностью необходимо найти корень уравнения f(x)=0 , принадлежащий интервалу изоляции [a,b] . Функция f(x) и ее первая производная непрерывны на этом отрезке.

Для применения этого метода исходное уравнение f(x)=0 должно быть приведено к виду

( 4.2)

В качестве начального приближения 0 выбираем любую точку интервала [a,b] .

Далее итерационный процесс поиска корня строится по схеме:

( 4.3)

В результате итерационный процесс поиска реализуется рекуррентной формулой (4.3). Процесс поиска прекращается, как только выполняется условие

( 4.4)

или число итераций превысит заданное число N .

Для того, чтобы последовательность х1, х2,…, хn приближалась к искомому корню, необходимо, чтобы выполнялось условие сходимости:

( 4.5)

Переходим к построению схемы алгоритма (рис. 4.7). Вычисление функции оформим в виде подпрограммы.

Итерационные методы решения нелинейных уравнений

Pers.narod.ru. Обучение. Лекции по численным методам. Приближённое решение нелинейных алгебраических уравнений

1. Приближенное решение нелинейных алгебраических уравнений

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

Дано нелинейное алгебраическое уравнение

f(x)=0 (1)

Нелинейность уравнения означает, что график функции не есть прямая линия, т.е. в f(x) входит x в некоторой степени или под знаком функции.

Решить уравнение – это найти такое x* ∈ R: f(x*)=0. Значение x* называют корнем уравнения. Нелинейное уравнение может иметь несколько корней. Геометрическая интерпретация корней уравнения представлена на рис. 1. Корнями уравнения (1) являются точки x1*, x2*, x3*, в которых функция f(x) пересекает ось x.

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

В приближенных методах процесс нахождения решения, вообще говоря, бесконечен. Решение получается в виде бесконечной последовательности <xn>, такой, что . По определению предела, для любого (сколь угодно малого) ε, найдется такое N, что при n>N, |xn x*| / (x) не меняет знак на отрезке [a, b], т.е. f(x) – монотонная функция, в этом случае отрезок [a,b] будет интервалом изоляции.

Если корней несколько, то для каждого нужно найти интервал изоляции.

Существуют различные способы исследования функции: аналитический, табличный, графический.

Аналитический способ состоит в нахождении экстремумов функции f(x), исследование ее поведения при и нахождение участков возрастания и убывания функции.

Графический способ – это построение графика функции f(x) и определение числа корней по количеству пересечений графика с осью x.

Табличный способ это построение таблицы, состоящей из столбца аргумента x и столбца значений функции f(x). О наличии корней свидетельствуют перемены знака функции. Чтобы не произошла потеря корней, шаг изменения аргумента должен быть достаточно мелким, а интервал изменения достаточно широким.

Решить уравнение x 3 ‑ 6x 2 +3x+11=0, т.е. f(x)= x 3 ‑ 6x 2 +3x+11.

Найдем производную f / (x)=3x 2 -12x+3.

Найдем нули производной f / (x)=3x 2 -12x+3=0; D=144-4*3*3=108;

X1== 0.268;

X2== 3.732;

Так как f / ()>0, то f / (x)>0 при , f / (x) / (x)>0 при . Кроме того, f()= 0. Следовательно, на интервале возрастает от до f(x1)= 3x1 2 -12x1+3=11.39; на интервале — убывает до f(x2)= 3x2 2 -12x2+3=-9.39 и на интервале возрастает до , т.е. уравнение имеет три корня.

Найдем интервалы изоляции для каждого из корней.

Рассмотрим для первого корня отрезок [-2, -1]:

f(-2)= -27 0, f / (x)>0 при т.е. этот отрезок является интервалом изоляции корня.

Рассмотрим для второго корня отрезок [1, 3]:

f(1)= 9>0, f(3)= -7 / (x) 0, f / (x)>0 при т.е. этот отрезок является интервалом изоляции корня.

Лабораторная — Итерационные методы решения нелинейных уравнений

ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

Цель работы: научиться решать нелинейные уравнения методом простых итераций, методом Ньютона и модифицированным методом Ньютона с помощью ЭВМ.

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

Читайте также  Груша и ее переработка

2. На конкретном примере усвоить порядок решения нелинейных уравнений с помощью ЭВМ указанными методами.

3. Составить программу (программы) на любом языке программирования и с ее помощью решить уравнение с точностью и . Сделать вывод о скорости сходимости всех трех методов.

4. Изменить и снова решить задачу. Сделать вывод о точности полученных результатов.

5. Составить отчет о проделанной работе.

ПРИМЕР ВЫПОЛНЕНИЯ РАБОТЫ

1. Доказать графическим и аналитическим методами существование единственного корня нелинейного уравнения

(1)

на отрезке .

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

3. Составить программу (программы) на любом языке программирования, реализующие построенные итерационные процессы.

1. Докажем графическим методом единственность корня нелинейного уравнения (1). Из графика функции на Рис.1 видно, что функция пересекает ось в одной точке, являющейся приближенным значением корня нелинейного уравнения (1). Но так как данная функция имеет сложный аналитический вид, то преобразуем уравнение (1) к виду и построим два графика и , имеющих более простой аналитический вид (Рис.2). Абсцисса точки пересечения графиков является приближенным значением корня. Заметим, что графический метод показывает количество корней исходного уравнения, но не доказывает единственность корня на отрезке.

Рис.1

Аналитический метод. Функция непрерывна на отрезке , имеет на концах отрезка разные знаки ( ), а производная функции не меняет знак на отрезке ( ). Следовательно, нелинейное уравнение (1) имеет на указанном отрезке единственный корень.

2. Метод простых итераций. Для построения рабочей формулы перепишем уравнение (1) в виде: . Проверим, выполняется ли достаточное условие сходимости на отрезке:

(2)

Если условие выполняется, то итерационный процесс строится по формуле

Заметим, что в точке из отрезка , значение .

Построим функцию . Константа выбирается из условия (2). Если производная , то значение выбирается из интервала , если производная , то – из интервала . Так как всюду положительна на отрезке, то, конкретизируя значение производной в любой точке отрезка (например ), значение определяется из интервала . Выбрав значение , запишем рабочую формулу метода простых итераций:

(3)

Итерационный процесс (3) можно начать, задав произвольное начальное приближение . Процесс (3) заканчивается при одновременном выполнении двух условий: и . В этом случае значение является приближенным значением корня нелинейного уравнения (1) на отрезке .

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

(4)

Заметим, что в точке условие (4) не выполняется, а в точке — выполняется. Следовательно в качестве начального приближения выбирается точка . Рабочая формула метода Ньютона для данной задачи запишется так:

(5)

Условия выхода итерационного процесса (5) аналогичны условиям метода простых итераций.

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

(6)

Условия выхода итерационного процесса (6) аналогичны условиям метода простых итераций.

Замечание: для того, чтобы сделать вывод о скорости сходимости методов, необходимо в каждом методе выбирать одинаковое начальное приближение.

3. Блок-схема метода простых итераций, метода Ньютона и модифицированного метода Ньютона приведена на рисунке 3.

2. Итерационные методы решения нелинейных уравнений.

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

Расчетная формула метода Ньютона имеет вид:

, ( 1 )

Геометрически метод Ньютона означает, что следующее приближение к корню есть точка пересечения с осью ОХ. касательной, проведенной к графику функцииy=f(x) в точке .

Теорема о сходимости метода Ньютона.

Пусть — простой корень уравнения, в некоторой окрестности которого функция дважды непрерывно дифференцируема.

Тогда найдется такая малая — окрестность корня, что при произвольном выборе начального приближенияиз этой окрестности итерационная последовательность метода Ньютона не выходит за пределы окрестности и справедлива оценка

, ( 2 )

где ,.

Метода Ньютона ( 1 ) чувствителен к выбору начального приближения x .

На практике для монотонной сходимости метода необходимо :

1-ая производная f(x) должна быть знакопостоянна на интервале локализации [ a , b ] изолированного корня ;

2-ая производная f(x) должна быть знакопостоянна на интервале локализации [ a , b ] изолированного корня ;

за начальное приближение x выбирается та граница интервала локализации , на которой произведение функции на ее 2-ю производную больше нуля ( f( c)f ’’ (c) > 0 , где с – одна из границ интервала ) .

Критерий окончания итерационного процесса. При заданной точности >0 вычисления следует вести до тех пор пока не окажется выполненным неравенство

. ( 3 )

Как указано в теореме, метод Ньютона обладает локальной сходимостью, то есть областью его сходимости является малая окрестность корня .

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

Метод простой итерации (метод последовательных повторений).

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

Это преобразование можно выполнить различными способами.

Функция называется итерационной функцией.

Расчетная формула метода простой итерации имеет вид:

. ( 4 )

Теорема о сходимости метода простой итерации.

Пусть в некоторой — окрестности корняфункциянепрерывно дифференцируема и удовлетворяет неравенству

, ( 5 )

где 0 вычисления следует вести до тех пор пока не окажется выполненным неравенство

. ( 7 )

Если величина , то можно использовать более простой критерий окончания итераций:

. ( 8 )

Если в неравенстве ( 5 ) q > 1 , то итерационный метод ( 4 ) расходится .

Если в неравенстве ( 5 ) q = 1 , то итерационный метод ( 4 ) может как сходится так и расходится .

В том случае , если q > = 1 , то итерационный метод ( 4 ) расходится и

применяется метод простой итерации с итерационным параметром .

Ключевой момент в применении метода простой итерации с итерационным параметром состоит в эквивалентном преобразовании уравнения :

x = x+αf(x) , ( 9 )

где α – итерационный параметр (вещественная константа ).

Расчетная формула метода простой итерации с итерационным параметром имеет вид:

x (n+1) = x (n) + αf(x (n) ) , ( 10 )

Итерационный процесс , построенный по форме ( 10) сходится , если :

1-ая производная функции f(x)знакопостоянна и ограничена на интервале локализации изолированного корня [a,b] ;

знак итерационного параметра α противоположен знаку 1-ой производной функции f(x) на интервале локализации изолированного корня [a,b] ;

модуль значения итерационного параметра α оценивается из неравенства

Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: