Итерационные методы и общий подход к оптимизации стационарных итерационных методов

х₀, x₁ =f(x₀), х₂ = f(x_l), ..., х_n =f(х_n-1), ... (6.7)

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

Предположим, что существует отрезок [а; b], содержащий все члены последовательности (6.7). Нетрудно видеть, что если на отрезке [а;b] функция f(x) возрастает, то итерационная последовательность является монотонной. Если же f(x) убывает, то она является колеблющейся.

Если существует такая окрестность корня уравнения, в которой отображение любой точки функцией f(x) не выходит за пределы этой окрестности и отображение f(х) является сжимающим, то в силу принципа сжимающих отображений итерационная последовательность (6.7) будет сходиться к корню уравнения (6.6). Условие того, что функция f(х) является сжимающий функцией на отрезке [a; b], приобретает в данном случае следующий вид: f(x)[а; b] для всех х [a; b], а также существует такое число б, О < б < 1, что для любых х, у [а; b] выполняется соотношение

. (6.8)

Отметим, что условие (6.8) имеет в математической литературе собственное название: условие Липшица; константа б называется константой Липшица.

Рисунок 6.3--Итерационная последовательность: а -- сходящаяся последовательность; б -- расходящаяся

Однако практически проверить выполнимость условия Липшица весьма затруднительно. Для этого следовало бы перебрать все возможные пары значений (x, у) из отрезка [а; b], что практически невозможно. Для дифференцируемых функций условие (6.8) можно заменить гораздо более удобным для практического использования условием. Для этого применим теорему Лагранжа. Она гласит, что если функция f(x) дифференцируема на отрезке [а; b], то на нем найдется такая точка с, что будет иметь место формула

f(b)-f(a) = f'(c)(b-a), (6.9)

называемая формулой Лагранжа (или формулой конечных приращении).

Сравнивая (6.8) и (6.9), приходим к очевидному выводу: если существует такое число q, 0 < q < 1, что для любых х [а; b]

(6.10)

то функция f(х) является сжимающей на отрезке [а; b]. При этом роль константы Липшица б играет число . Проверить выполнимость условия (6.10) гораздо проще, чем (6.8).

Графической иллюстрацией сходящегося итерационного процесса при выполнении условия (6.10) в случае, когда f'(x) > 0 на отрезке [а; b], является рисунок 6.3, а.

Заметим, что условия (6.8), (6.10) (наряду с требованием о том, что значения функции f(x) не выходят за пределы отрезка [а; b]) являются достаточными, но не необходимыми для сходимости итерационной последовательности (6.6). Это означает, что итерационная последовательность может оказаться сходящейся и при невыполнении этих условий.

Итак, общая схема решения уравнения (6.5) методом итераций такова.

Выполнить, полностью или частично, отделение корней. Выбрать тот корень, который подлежит уточнению, и соответствующий ему отрезок [а; b], содержащий этот корень и не содержащий иных корней данного уравнения.

Преобразовать уравнение (6.5) к равносильному ему уравнению вида (6.6).

Найти и проверить, является ли функция f(х) сжимающей на отрезке [а; b].

4. Если сжимаемость имеет место, то:

задаться точностью е нахождения приближенного значения корня;

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

построить следующий член итерационной последовательности (6.6);

всякий раз, получив очередной член итерационной последовательности, проверять, выполняется ли условие, следующее из (1.13):

(6.11)

4.5) если условие (6.11) выполняется, то принять х_п за результат, иначе вновь выполнить пункт 4.3.

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

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

Рассмотрим простейший из них. Преобразуем уравнение (6.5) к равносильному уравнению

x=x-µ F(x), (6.12)

где µ -- отличная от нуля константа.

Таким образом,f(х)= x-µF(x). Условие приобретает вид |1-µF'(x)| < 1, или, иначе,

-1<1-µF'(x);1-µF'(x)<1. (6.13)

Если удастся подобрать значение у, так, чтобы условие (6.13) выполнялось, то метод итераций применим.

Пусть на [а; b] существует единственный корень уравнения F(x) = 0. Будем считать функцию F(х) дифференцируемой на отрезке [а; b] и сохраняющей на этом отрезке свой знак (фактически предполагается, что отрезок достаточно мал).

Рассмотрим вначале случай, когда F'(x) > 0. Второе из неравенств (6.13) тогда сводится к условию µ> 0, а первое -- к уcловию µ < . Полагая

, (6.14)

получим из (6.12) итерационную формулу

. (6.15)

Обсудим вопрос о критерии выхода из итерационного процесса (6.15).

В условие (6.11) входит . Имеем:

.

Поскольку считается, что F'(x) > 0,то ,где

^.

Если F' (x)< 0 для x[a;b], то, рассуждая аналогично, получим и итерационную формулу

^. (6.16)

Отметим одно важное свойство итерационных методов решения уравнений, называемое самоисправляемостью. Поскольку начальное приближение х₀ выбирается произвольно, то отсюда следует, что полученное в итерационном процессе n-е приближение при желании можно считать начальным. Это означает, что если в процессе вычисления приближений допускались ошибки, то они не влияют на окончательный результат (при условии, что запрашиваемая точность результата существенно ниже реализуемого в процессе счета уровня точности представления числовых данных). Указанное свойство метода итераций делает его одним из самых надежных методов решения уравнений.

6.3 Методы Ньютона

Рассмотрим два метода Ньютона - метод касательных и метод хорд. Оба метода основаны на следующем приеме. Пусть уравнение (6.5) имеет единственный корень на отрезке [a;b]. Преобразуем его к равносильному уравнению

x = x-ц(x)F(x), (6.17)

где ц(x)--любая функция, определенная на отрезке [a;b] и не обращающаяся на нем в нуль. Осуществляя различными способами выбор ц(х), можно получить, в частности, и указанные методы. [6, c. 256]

Метод касательных.

Пусть в (6.17) ц(х) =

Таким образом, итерационная последовательность строится с помощью рекуррентного соотношения

(n=0,1,2,…) (6.18)

Вопрос о выборе начального приближения х₀ и гарантированной сходимости итераций решается просто, если функция F(x) удовлетворяет следующим условиям:

является дважды дифференцируемой на отрезке [a;b];

обе производные -- первая и вторая -- не меняют знак на этом отрезке, т.е. функция F(х) монотонна и не меняет характера выпуклости; ситуация иллюстрируется одним из вариантов на рисунок 6.4.

В такой ситуации за x₀ берется тот конец отрезка [а; b], на котором функция F(x) и ее вторая производная имеют одинаковые знаки, т.е. выполняется условие F(x₀) * F"(x₀) > 0. Очевидно, что это левый конец [а;b] на рисунке 6.4, а и г и правый конец [а; b] на рисунке 6.4, б и в.

Допустим в дополнение к сделанным ранее предположениям, что F"(x) также непрерывна на [а; b]. Докажем, что отображение соответствующее формуле (6.18), является сжимающим в некоторой окрестности корня уравнения F(x)=0. Для этого, как показано выше, достаточно, чтобы существовало такое число q (0 < q < 1), чтобы в указанной окрестности имело место неравенство |ц'(х)| q < 1. Вычислим производную

.

а б в г

Рисунок 6.4--Четыре возможности поведения функции F(x) в окрестности корня:

а -- функция F(x) убывает и выпукла; б -- функция F(x) убывает и вогнута; в -- функция F(x) возрастает и вогнута; г -- функция F(x) возрастает и выпукла.

Непосредственно в корне имеем

,

поскольку . Далее рассуждаем так: раз непрерывная функция ц^'(x) обращается в нуль в некоторой точке, то существует такая окрестность этой точки, в которой |ц'(x)|<1, что и требовалось доказать.

Для оценки расстояния oт очередного приближения х_n до корня можно использовать как общее соотношение (6.11), так и следующий прием. По формуле Лагранжа

.

Отсюда получаем

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

(6.19)

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

Можно показать, что если F(x) имеет на [а; b] непрерывную вторую производную F"(х), то погрешности на n-м и (n+1)-м шагах связаны неравенством

(6.20)

Таким образом, вычислительный алгоритм, заданный формулой (6.17), имеет квадратичную скорость сходимости.

Рисунок 6.5-- Геометрический смысл метода касательных

Рассмотренный метод называется методом касательных потому, что если обратиться к графической иллюстрации (рисунок 6.5), то точка x₁, определяемая по формуле (6.18) при n=0, есть точка пересечения касательной, проведенной к графику функции у = F(x) в точке с абсциссой x₀, с осью абсцисс.

Каждому следующему члену итерационной последовательности (6.18) соответствует точка пересечения касательной, проведенной к графику функции F(x) в точке с абсциссой, определяемой предыдущим членом последовательности, с осью абсцисс.

Метод хорд. Реализуя метод касательных, при каждой итерации необходимо вычислять значение не только функции F(х), но и ее производной F'(x), Однако есть вариант метода Ньютона, в котором можно ограничиться вычислением только значений F(х), что иногда упрощает вычислительный алгоритм. [5, c. 49]

Если положить в (6.17) , а в качестве с взять тот конец промежутка [a;b], на котором , то приходим к итерационному методу:

, (6.21)

называемому методом хорд (или методом секущих).

В качестве x₀ в этом случае следует принять тот конец промежутка [а ;b], который остался после выбора с (т. е. если с=а, то x₀=b или наоборот). Далее последовательность строится по формуле (6.21). Оценка степени приближения к корню возможна с помощью неравенства (6.19) (оно было получено с помощью формулы Лагранжа, не зависящей от рассматриваемых методов).

Геометрический смысл метода (благодаря которому он и получил название) проиллюстрирован на рисунке 6.6. В данном случае с=b, x₀ = а, x₁ соответствует точке пересечения хорды, соединяющей концы кривой, с осью абсцисс. Далее находится точка на кривой с абсциссой x₁ проводится следующая хорда и т.д.

Рисунок 6.6-- Геометрический смысл метода хорд

7. Итерационные методы линейных алгебраических уравнений

Итерационные методы используют для решения уравнений и систем уравнений любой природы. Рассмотрим, как это делается применительно к системам линейных алгебраических уравнений.[7, c 197]

7.1 Метод простой итерации для системы линейных алгебраических уравнений

Представим систему х=Ах в развернутом виде:

(7.1)

или в сокращенной записи . О системе со структурой (7.1) говорят, что она «приведена к нормальному виду».

Правая часть системы (7.1) определяет отображение (обозначим его F):

(7.2)

преобразующее точку n-мерного векторного пространства в точку у того же пространства. Используя отображение (7.2) и выбрав начальную точку можно построить итерационную последовательность точек n-мерного пространства (аналогично методу простой итерации для скалярного уравнения х =f(х)):

 (7.3)

Например, пусть дана система уравнений

Перепишем эту систему в виде (7.1) простейшим образом:

Ах=b => (х + Ах)=х +b. Равносильность такого преобразования очевидна. Получим

(7.4)

Примем за начальное приближение, например, точку (0; 0; 0) трехмерного пространства, подставим ее координаты в правую часть системы (2.4) и произведем вычисления. Получим координаты. новой точки (-1; -2; -3). Используя теперь эту точку как
начальную, можно получить следующую точку (1; -2; -2) и т.д.
Тем самым будет получена последовательность точек: (0; 0; 0)
(-1; -2; -3), (1; -2;-2),… .

Если отображение F является сжимающим отображением, то эта последовательность сходится и ее предел является решением системы (7.4) и тем самым исходной системы.

Рассмотрим условия, при которых отображение (7.2) будет сжимающим. Решение этого вопроса зависит от способа метризации пространства (т.е. определения расстояния между n-мерными векторами). В отличие от пространства действительных чисел в данном случае существует несколько способов метризации.

Пусть (x₁ ,х₂ ,..., х_n) и (у₁ ,у₂,...,у_n) -- две точки n-мерно го пространства. Для применения метода итерации систему линейных уравнений удобно «погрузить» в пространство с одной из трех следующих метрик:

а) ; (7.5)

б) (7.6)

в); (7.7)

Сформулируем условия, при которых отображение (7.2) в пространствах с метриками ,, будет сжимающим. Эти условия выражаются через коэффициенты при неизвестных системы (7.1):

а) в пространстве с метрикой :

(7.8)

т. е. максимальная из сумм модулей коэффициентов при неизвестных в правой части системы (7,2), взятых по строкам, должна быть меньше единицы;

б) в пространстве с метрикой :

(7.9)

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

в) в пространстве с метрикой :

(7.10)

т.е. сумма квадратов всех коэффициентов при неизвестных в правой части системы (7.2) должна быть меньше единицы.

Условия (7.8) --(7.10) легко вывести. Рассмотрим, например, получение условия (7.8).Напомним, что отображение F называется сжимающим, если существует такое число : 0 < < 1, что для любых двух точек и выполняется условие:

. (7.11)

(т.е. расстояние между образами меньше, чем расстояние между исходными точками).

Для точек и в соответствии с (7.5) имеем:

(7.12)

По свойству абсолютной величины имеем:

Это неравенство лишь усилится, если заменить каждый модуль значением :

Подставляя это в (7.12), получим

(7.13)

Сравнивая (7.13) с (7.11), получаем условие (7.8).

Заметим, что каждое из условий (7.8) --(7.10) является достаточным для того, чтобы отображение (7.1) было сжимающим. Условие (7.9) является также и необходимым для сжимаемости отображения (7.1) (в смысле метрики ), но ни одно из условий (7.8) -- (7.10) не является необходимым для результативности метода итераций.

7.2 Метод Зейделя

Будем снова рассматривать исходную систему линейных уравнений (7.1). При решении системы (7.1) методом простой итерации каждый шаг итерационного процесса состоит в переходе от уже имеющегося приближения значений неизвестных к новому (очередному) приближению. Обозначим элементы имеющегося приближения через x₁, x₂ ,..., x_n , а элементы очередного (вычисляемого) приближения через y₁ ,у₂ ,..., у_n . Вычислительные формулы имеют вид:

Основная идея метода Зейделя состоит в том, что на каждом шаге итерационного процесса при вычислении значения y_i учитываются уже полученные значения y₁,y₂,…,y_i-1. Выпишем соответствующие вычислительные формулы:

……………….. (7.14)

Справедливо следующее утверждение: если для матрицы коэффициентов системы (7.1) выполняется хотя бы одно из условий (7.8) --(7.10), то итерационный процесс метода Зейделя сходится к решению системы при любом выборе начального приближения x₁⁽⁰⁾,x₂⁽⁰⁾,…,x_n⁽⁰⁾.

Таким образом, каждое из условий (7.8) --(7.10) является достаточным для сходимости итерационного процесса метода Зейделя. Преимущество этого метода состоит в том, что он обычно обеспечивает более быструю сходимость, чем метод простой итерации.

8. Приближенные методы решения систем нелинейных уравнений

Решение систем нелинейных трансцендентных уравнений является в общем случае задачей несравненно более сложной, нежели решение систем линейных уравнений. Не существует методов, которые гарантировали бы успех решения любой такой задачи.[8, c. 190]

Как и для отдельных уравнений, наибольшую проблему представляет задача отделения решений (корней). Для системы уравнений с n неизвестными необходимо, во-первых, понять, сколько у нее решений, а во-вторых, выделить области n-мерного пространства, в каждой из которых есть одно и только одно решение. Лишь после этого можно говорить о нахождении решений с заданной точностью (оцениваемой в соответствии с используемой метрикой).

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

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

8.1 Метод простой итерации для нелинейных уравнений

Запишем систему n нелинейных уравнений с п неизвестными в следующем виде:

(7.15)

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

(7.16)

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

(7.17)

Если отображение, задаваемое системой (7.16), является сжимающим в некоторой окрестности корня, начальное приближение лежит в той же окрестности и итерации (7.17) не выходят за ее пределы, то последовательность сходится к вектору , являющемуся решением системы (7.15).

Указанное выше требование сходимости итерационного процесса требует конкретизации, придания ему реально проверяемого вида. Допустим, что все функции , входящие в (7.16), дифференцируемы. Обозначим где G -- область n-мерного пространства, содержащая искомое решение. В таких обозначениях достаточные условия сжимаемости отображения (7.16) можно сформулировать точно так же, как сформулированы условия (7.8) -- (7.10) (соответственно для метрик (7.5) -- (7.7)). Однако в конкретных случаях исследование сходимости может оказаться значительно сложнее, чем для систем линейных уравнений. Основные трудности при этом -- нахождение области G и затем чисел .

Критерий достижения заданной точности итерационного процесса выражен условием, позволяющим устанавливать момент прекращения итерационного процесса при достижении заданной точности результата :

(7.18)

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

8.2 Метод Ньютона

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

При решении систем нелинейных уравнений часто используют метод Ньютона, являющийся обобщением метода. Существенную роль в этом методе играет специальная матрица -- так называемая матрица Якоби (или якобиан):

 (7.19)

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

Напомним, что метод касательных применительно к одному уравнению f(х)= 0 заключается в построении итерационной последовательности

Обобщением этой формулы на системы уравнений является следующая формула:

(7.20)

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

Отметим, что метод Ньютона весьма трудоемок, поскольку на каждом шаге итерационного процесса необходимо найти матрицу, обратную матрице Якоби. Чаще всего для этого используют описанный выше метод Гаусса. Тем не менее, для системы, состоящей из двух-трех уравнений, можно найти обратную матрицу аналитическим методом, известным из курса алгебры. В частности, при решении системы двух уравнений

(7.21)

для матрицы Якоби второго порядка обратная матрица имеет вид

(7.72)

(7.23)

Итерационные формулы (7.20) в этом случае примут вид, непосредственно пригодный для вычислений:

(7.24)

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

Отметим одно важное свойство итерационных методов решения уравнений, называемое самоисправляемостью. Поскольку начальное приближение х₀ выбирается произвольно, то отсюда следует, что полученное в итерационном процессе n-е приближение при желании можно считать начальным. Это означает, что если в процессе вычисления приближений допускались ошибки, то они не влияют на окончательный результат (при условии, что запрашиваемая точность результата существенно ниже реализуемого в процессе счета уровня точности представления числовых данных). Указанное свойство метода итераций делает его одним из самых надежных методов решения уравнений.

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Трубников Ю.В. Экстремальные конструкции в негладком анализе и операторные уравнения с аккретивными нелинейностями.--Москва, 2002. -256 с.

2. Марчук Г.И. Методы вычислительной математики. М.: Наука, 1977, 456 стр.

3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы.-- М.: Лаборатория базовых знаний, 2001.--632 с.

4. Коллац Л. Функциональный анализ и вычислительная математика. М.: Мир, 1969-- 448 c.

5. Исаков, В.Б. Элементы численных методов: Учебное пособие для студентов, обучающихся по специальности Математика группы Педагогические специал. - М.: Академия, 2003.- 192 с.

6. Калиткин Н.Н. Численные методы. - М.:Наука. Гл.ред. физ.-мат. Лит-ры, 1978. - 512с.

7. Самарский А.А., Гулин А.В. Численные методы: Учеб. Пособие для вузов. - М.:Наука. Гл.ред физ.-мат. Лит-ры, 1989. - 432с.

8. Демидович Б.П.,Марон И.А., Шувалова Э.З. Численные методы анализа.--М.:Наука,1967.--368 с.

ПРИЛОЖЕНИЕ А

Задание.

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

(1)

на отрезке .

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

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

Решение.

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



Рисунок 1

Рисунок 2

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

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

(2)

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

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

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

(3)

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

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

(4)

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

для данной задачи запишется так:

(5)

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

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

(6)

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

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

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

Рисунок 3--Блок схема

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

ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ ПАСКАЛЬ

Program Pr_iter;

Uses Crt;

var n:integer;

x0,x,eps,d,y,z,c:real;

begin

clrscr;

n:=0;x0:=-1;c:=-0.1;x:=x0;eps:=0.001;d:=0.01;

repeat

y:=x+c*(exp(x)+x);z:=x;

n:=n+1;

writeln(n:3,x:9:5,y:9:5,abs(y-x):9:5,abs(exp(y)+y):9:5);

x:=y;

until (abs(z-x)<=eps) and (abs(exp(x)+x)<=d);

end.

ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ С

#include <stdio.h>

#include <math.h>

main()

{

int n=0;

float x,y,z,x0=-1,c=-0.1,eps=0.001;d=0.01;

x=x0;

clrscr();

do

{

y=x+c*(exp(x)+x);z=x;

printf(“%d %.4f %.4f %.4f %.4f\n”,n++,x,y,fabs(y-x),

fabs(exp(y)+y));

x=y;

}

while(fabs(z-x)>e || fabs(exp(x)+x)>d;

getch();

}

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

ПРИЛОЖЕНИЕ Б

Решение системы линейных уравнений методом Якоби.

Пусть дана система уравнений:

Требуется найти решение системы с точностью

Приведем систему к виду удобному для итерации:

Выберем начальное приближение, например,

- вектор правой части.

Тогда первая итерация получается так:

Аналогично получаются следующие приближения к решению.

, ,

Найдем норму матрицы . Будем использовать норму .

Так как сумма модулей элементов в каждой строке равна 0.2, то = 0.2 < 1/2, поэтому критерий окончания итераций в этой задаче .

Вычислим нормы разностей векторов:

, .

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

Ответ: x ₁ = 1.102, x ₂ = 0.991, x ₃ = 1.101

ПРИЛОЖЕНИЕ В

Решение дифференциального уравнения.

Условие:,

> X2:=x->int((sin(t-s)+cos(t-s)*1)*(exp(3*s)/(1-exp(6*Pi))-exp(2*s)/(1-exp(4*Pi))),s=0..Pi*2);

> X2(t);

> X3:=x->int((sin(t-s)+cos(t-s)*(cos(t-s)/5)^2)*(exp(3*s)/(1-exp(6*Pi))-exp(2*s)/(1-exp(4*Pi))),s=0..Pi*2);

> X3(t);

> X4:=x->int((sin(t-s)+cos(t-s)*(-(cos(t-s))^3/1950-(cos(t-s)^2)*sin(t-s)/390+168*cos(t-s)/1625+476*sin(t-s)/4875)^2)*(exp(3*s)/(1-exp(6*Pi))-exp(2*s)/(1-exp(4*Pi))),s=0..Pi*2);

> X4(t);

> plot([X2(t),X3(t),X4(t)],t=0..2*Pi,color=[RED,NAVY,BLACK],linestyle=[SOLID,SOLID,SOLID],thickness=2,titlefont=[TIMES,BOLD,5],legend=["график Х2","график Х3","график Х4"]);

Размещено на Allbest.ru

...