1. Пусть известен отрезок , который содержит один корень уравнения f(x) = 0. Функция f является непрерывно дифференцируемой функцией на этом отрезке (f(x)ÎC 1 ). При выполнении этих условий можно применять метод простой итерации.

2. По функции f(x) строится функция j(x), удовлетворяющая трём условиям: она должна быть непрерывно дифференцируемой (j(x)ÎC 1 ), такая, что уравнение x = j(x) равносильно уравнению f(x)=0; должна также переводить отрезок в себя .

Будем говорить, что функция j(x) переводит отрезок [ a, b] в себя, если для любого x Î [ a, b], y = j(x) также принадлежит [ a, b] (y Î [ a, b]).

На функцию j(x) накладывается третье условие:

Формула метода: x n +1 = j(x n).

3. При выполнении этих трех условий для любого начального приближения x 0 Î последовательность итераций x n +1 = j(x n) сходится к корню уравнения: x = j(x) на отрезке ().

Как правило, в качестве x 0 выбирается один из концов .

,

где e – заданная точность

Число x n +1 при выполнении условия остановки итерационного процесса является приближенным значением корня уравнения f(x) = 0 на отрезке , найденным методом простой итерации с точностью e.

Построить алгоритм для уточнения корня уравнения: x 3 + 5x – 1 = 0 на отрезке методом простой итерации с точностью e.

1. Функция f(x) = x 3 +5x-1 является непрерывно дифференцируемой на отрезке , содержащем один корень уравнения.

2. Наибольшую трудность в методе простой итерации представляет построение функции j(x), удовлетворяющей всем условиям:

Рассмотрим: .

Уравнение x = j 1 (x) эквивалентно уравнению f(x) = 0, но функция j 1 (x) не является непрерывно дифференцируемой на отрезке .

Рис. 2.4. График функции j 2 (x)

С другой стороны, , следовательно, . Отсюда: – непрерывно дифференцируемая функция. Отметим, что уравнение:x = j 2 (x) эквивалентно уравнению f(x) = 0. Из графика (рис. 2.4) видно, что функция j 2 (x) переводит отрезок в себя.

Условие, что функция j(x) переводит отрезок в себя, можно переформулировать следующим образом: пусть – область определения функции j(x), а – область изменения j(x).

, .

Все условия для функции j(x) выполнены.

Формула итерационного процесса: x n +1 = j 2 (x n).

3. Начальное приближение: x 0 = 0.

4. Условие остановки итерационного процесса:

Рис. 2.5. Геометрический смысл метода простой итерации

.

При выполнении этого условия x n +1 – приближенное значение корня на отрезке , найденное методом простой итерации с точностью e . На рис. 2.5. иллюстрируется применение метода простой итерации.

Теорема о сходимости и оценка погрешности

Пусть отрезок содержит один корень уравнения x = j(x), функция j(x) является непрерывно дифференцируемой на отрезке , переводит отрезок в себя, и выполнено условие :

.

Тогда для любого начального приближения x 0 Î последовательность сходится к корню уравнения y = j(x) на отрезке и справедлива оценка погрешности :

.

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

Сложность метода простой итерации . Объем памяти ЭВМ, необходимый для реализации метода простой итерации, незначителен. На каждом шаге нужно хранить x n , x n +1 , q и e.

Оценим число арифметических действий, необходимых для реализации метода простой итерации. Запишем оценку для числа n 0 = n 0 (e) такого что, для всех n ³ n 0 выполняется неравенство:

Из этой оценки вытекает, что чем ближе q к единице, тем медленнее сходится метод.

Замечание. Не существует общего правила построения j(x) по f(x) так, чтобы выполнялись все условия теоремы о сходимости. Часто используется следующий подход: в качестве функции j выбирается функция j(x) = x + k× f(x), где k – константа.

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

и .

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

Пусть дана система n алгебраических уравнений с n неизвестными:

Алгоритм метода простой итерации:

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

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

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

12. Основная итерационная формула, применяемая в методе простой итерации, для решения нелинейного уравнения:

13. Критерий останова итерационного процесса в методе простой итерации для решения нелинейного уравнения:

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

14. Критерий выбора вспомогательной функции F(x) для итерационного отрезка интервала :

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

Недостатком итерационных методов является это достаточно жесткое условие сходимости, которое выполняется далеко не для всех систем уравнений.

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

15. Метод Гаусса, применяемый для решения систем линейных уравнений, предусматривает:

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

Итерационные методы

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

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

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

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

В методе простой итерации система (2.1) линейных алгебраических уравнений Ax = b приводится к эквивалентной системе вида

Решение системы (2.9) и, следовательно, решение исходной системы (2.1) ищется как предел последовательности векторов при :

k = 0, 1, 2,…, (2.10)

где - начальное приближение для вектора решения.

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

ТЕОРЕМА 1. Если какая-либо норма матрицы , согласованная с рассматриваемой нормой вектора , меньше единицы (), то последовательность в методе простой итерации сходится к точному решению системы (2.9) со скоростью, не меньшей скорости геометрической прогрессии со знаменателем при любом начальном приближении .

ДОКАЗАТЕЛЬСТВО. Для доказательства теоремы введем погрешность . Вычитая из соотношения равенство (2.10), получаем . Переходя к нормам, имеем

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

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

, i =1,2, …, n,

, j = 1, 2, …, n. (2.11)

Простейшим и распространенным способом приведения системы Ax= b к виду (2.9), удобному для итераций, является выделение диагональных элементов, при этом каждое i-е уравнение разрешается относительно i-го неизвестного:

, i = 1, 2, …, n, (2.12)

и метод простой итерации запишется в виде

Матрица при этом имеет вид

.

Элемент этой матрицы можно записать в виде где - символ Кронекера. В этом случае достаточное условие сходимости метода простой итерации может быть сформулировано как условие преобладания диагональных элементов матрицы А , что следует из (2.11) и записи матрицы , т. е.

i = 1, 2, …, n.

Еще раз подчеркнем, что рассмотренные формы условия сходимости метода итерации являются лишь достаточными. Их выполнение гарантирует сходимость метода, но их невыполнение в общем случае не означает, что метод простой итерации расходится. Необходимым и достаточным условием сходимости метода простой итерации является условие того, что целая часть (где -максимальное по модулю собственное значение матрицы А ); это условие редко используется в практике вычислений.

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

ТЕОРЕМА 2. Если какая-либо норма матрицы , согласованная с рассматриваемой нормой вектора х

. (2.13)

ДОКАЗАТЕЛЬСТВО. Вычтем из равенства равенство (2.10):

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

Перейдя к нормам, получим

Так как по условию теоремы , то

Используя соотношение из которого следует, что окончательно получим:

ТЕОРЕМА 3. Если какая-либо норма матрица , согласованная с рассматриваемой нормой вектора х , меньше единицы (), то имеет место следующая оценка погрешности:

Сделаем два замечания. Во-первых, соотношение (2.13) может быть записано в виде

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

Погрешности последовательных итераций связаны соотношением

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

Итак, на примере метода простой итерации продемонстрированы три этапа итерационных методов: построение последовательности векторов, порождаемой формулой (1.10); определение условия сходимости по теореме 1 и оценка скорости сходимости с помощью теорем 2 и 3.

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

В методе простой итерации не используется кажущаяся очевидной возможность улучшения сходимости итерационного процесса – немедленное введение в расчет вновь вычисленных компонент вектора . Эта возможность используется в итерационном методе Зейделя. Итерационный процесс для системы (2.9) выполняется при этом по соотношению

i = 1, 2, …, n (2.14)

или для системы (1.1)

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

Отметим, что метод Зейделя сходится, если матрица А положительно определенная и симметричная.

Покажем, что метод итераций Зейделя эквивалентен некоторому методу простой итерации со специальным образом построенной матрицей и вектором в соотношении (2.10). Для этого запишем систему (2.14) в виде где F-верхняя треугольная матрица из коэффициентов матрицы , а Перепишем систему в виде где E-единичная матрица. Матрица (Е-Н) - нижняя треугольная матрица с диагональными элементами, равными единице. Следовательно, определитель этой матрицы отличен от нуля (равен единице) и она имеет обратную матрицу . Тогда

Сопоставляя это соотношение с решением (2.10), можем заключить, что действительно метод итераций Зейделя эквивалентен методу простой итерации в том смысле, что для установления условия и критерия сходимости метода итераций Зейделя можно воспользоваться теоремами, приведенными для метода простой итерации, если положить Итерационный процесс для системы (2.12) записывают и в более общей форме, а именно

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

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

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

{ f 1 (x 1 , x 2 , … , x n) = 0 … f n (x 1 , x 2 , … , x n) = 0 {\displaystyle \left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_{n}(x_{1},x_{2},\ldots ,x_{n})&=&0\end{array}}\right.}

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

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

Сжимающее отображение [ | ]

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

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

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

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

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

φ (x) ∈ C 1 [ a , b ] . ∀ x 1 , x 2 ∈ (a , b) , x 1 < x 2 ∃ ξ ∈ (x 1 , x 2) : φ ′ (ξ) (x 2 − x 1) = φ (x 2) − φ (x 1) {\displaystyle \varphi (x)\in C^{1}.\quad \forall x_{1},x_{2}\in (a,\;b),\quad x_{1}

Отсюда следует, что α ≈ | φ ′ (ξ) | {\displaystyle \alpha \approx |\varphi "(\xi)|} . Таким образом, для сходимости метода достаточно, чтобы ∀ x ∈ [ a , b ] | φ ′ (x) | ≤ 1. {\displaystyle \forall x\in \quad |\varphi "(x)|\leq 1.}

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

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

Применительно к СЛАУ [ | ]

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

{ a 11 x 1 + … + a 1 n x n = b 1 … a n 1 x 1 + … + a n n x n = b n {\displaystyle \left\{{\begin{array}{ccc}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\\ldots &&\\a_{n1}x_{1}+\ldots +a_{nn}x_{n}&=&b_{n}\end{array}}\right.}

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

(x 1 x 2 ⋮ x n) i + 1 = (a 11 + 1 a 12 … a 1 n a 21 a 22 + 1 … a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 … a n n + 1) (x 1 x 2 ⋮ x n) i − (b 1 b 2 ⋮ b n) {\displaystyle \left({\begin{array}{c}x_{1}\\x_{2}\\\vdots \\x_{n}\end{array}}\right)^{i+1}=\left({\begin{array}{cccc}a_{11}+1&a_{12}&\ldots &a_{1n}\\a_{21}&a_{22}+1&\ldots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\ldots &a_{nn}+1\end{array}}\right)\left({\begin{array}{c}x_{1}\\x_{2}\\\vdots \\x_{n}\end{array}}\right)^{i}-\left({\begin{array}{c}b_{1}\\b_{2}\\\vdots \\b_{n}\end{array}}\right)}

Метод будет сходится с линейной скоростью, если ‖ a 11 + 1 … a 1 n ⋮ ⋱ ⋮ a n 1 … a n n + 1 ‖ < 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}

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

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

Метод Ньютона (метод касательных) [ | ]

Одномерный случай [ | ]

Оптимизация преобразования исходного уравнения f (x) = 0 {\displaystyle f(x)=0} в сжимающее отображение x = φ (x) {\displaystyle x=\varphi (x)} позволяет получить метод с квадратичной скоростью сходимости.

Чтобы отображение было наиболее эффективно, необходимо, чтобы в точке очередной итерации x ∗ {\displaystyle x^{*}} выполнялось φ ′ (x ∗) = 0 {\displaystyle \varphi "(x^{*})=0} . Будем искать решение данного уравнения в виде φ (x) = x + α (x) f (x) {\displaystyle \varphi (x)=x+\alpha (x)f(x)} , тогда:

φ ′ (x ∗) = 1 + α ′ (x ∗) f (x ∗) + α (x ∗) f ′ (x ∗) = 0 {\displaystyle \varphi "(x^{*})=1+\alpha "(x^{*})f(x^{*})+\alpha (x^{*})f"(x^{*})=0}

Воспользуемся тем, что f (x) = 0 {\displaystyle f(x)=0} , и получим окончательную формулу для α (x) {\displaystyle \alpha (x)} :

α (x) = − 1 f ′ (x) {\displaystyle \alpha (x)=-{\frac {1}{f"(x)}}}

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

φ (x) = x − f (x) f ′ (x) {\displaystyle \varphi (x)=x-{\frac {f(x)}{f"(x)}}}

Тогда алгоритм нахождения численного решения уравнения f (x) = 0 {\displaystyle f(x)=0} сводится к итерационной процедуре вычисления:

x i + 1 = x i − f (x i) f ′ (x i) {\displaystyle x_{i+1}=x_{i}-{\frac {f(x_{i})}{f"(x_{i})}}}

Метод простых итераций основан на замене исходного уравнения эквивалентным уравнением:

Пусть известно начальное приближение к корню х = х 0 . Подставив его в правую часть уравнения (2.7), получим новое приближение , затем аналогичным образом получим и т. д.:

. (2.8)

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

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

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

Следовательно, чем меньше вблизи корня, тем быстрее сходится процесс.

Для того чтобы итерационный процесс был сходящимся, необходимо в окрестности корня выполнение следующего неравенства:

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

Рассмотрим один из общих алгоритмов перехода от уравнения (2.1) к уравнению (2.7).

Умножим левую и правую части уравнения (2.1) на произвольную константу b и добавим к обеим частям неизвестное х. При этом корни исходного уравнения не изменятся:

Введем обозначение и перейдем от соотношения (2.10) к уравнению (2.8).

Произвольный выбор константы b позволит обеспечить выполнение условия сходимости (2.9). Критерием окончания итерационного процесса будет условие (2.2). На рис.2.8 приведена графическая интерпретация метода простых итераций при описанном способе представления (масштабы по осям X и Y различны).

Если функция выбрана в виде , то производная от этой функции будет . Наибольшая скорость сходимости будет при , тогда и итерационная формула (2.11) переходит в формулу Ньютона . Таким образом, метод Ньютона имеет самую высокую степень сходимости из всех итерационных процессов.

Программная реализация метода простых итераций выполнена в виде процедуры-подпрограммы Iteras (ПРОГРАММА 2.1).

Вся процедура практически состоит из одного цикла Repeat ... Until, реализующего формулу (2.11) с учетом условия прекращения итерационного процесса (формула (2.2)).

В процедуру встроена защита от зацикливания путем подсчета числа циклов с помощью переменной Niter. На практических занятиях необходимо убедиться путем прогона программы в том, как сказывается выбор коэффициента b и начального приближения на процессе поиска корня. При изменении коэффициента b характер итерационного процесса для исследуемой функции меняется. Он становится сначала двухсторонним, а потом зацикливается (рис.2.9). Масштабы по осям X и Y различны. Еще большее значение модуля b приводит к расходящемуся процессу.

Сравнение методов приближенного решения уравнений

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

Рис. 2.3-2.5, 2.8, 2.9 являются копиями экрана ПЭВМ при окончании итерационного процесса.

В качестве исследуемой функции во всех случаях было взято квадратное уравнение x 2 -x-6 = 0, имеющее аналитическое решение х 1 = -2 и х 2 = 3. Погрешность и начальные приближения принимались для всех методов равными. Результаты поиска корня х= 3, представленные на рисунках, таковы. Наиболее медленно сходится метод дихотомии - 22 итерации, самый быстрый - метод простых итераций при b = -0.2 - 5 итераций. Здесь нет противоречия с утверждением, что метод Ньютона является самым быстрым.

Производная исследуемой функции в точке х = 3 равна -0.2, то есть расчет в данном случае велся практически методом Ньютона с величиной производной в точке корня уравнения. При изменении коэффициента b скорость сходимости падает и постепенно сходящийся процесс сначала зацикливается, потом становится расходящимся.