Алгоритм решения уравнения методом простой итерации. Метод простых итераций в общем виде

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть известно начальное приближение к корню х = х 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 скорость сходимости падает и постепенно сходящийся процесс сначала зацикливается, потом становится расходящимся.

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

Билет№29

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

Метод Зейделя (иногда называемый методом Гаусса-Зейделя) является модификацией метода простой итерации, заключающейся в том, что при вычислении очередного приближения x (k+1) (см. формулы (1.13),(1.14)) его уже полученные компоненты x 1 (k+1) , ...,x i - 1 (k+1) сразу же используются для вычисления x i (k+1) .

В координатной форме записи метод Зейделя имеет вид:

X 1 (k+1) = c 11 x 1 (k) + c 12 x 2 (k) + ... + c 1n-1 x n-1 (k) + c 1n x n (k) + d 1
x 2 (k+1) = c 21 x 1 (k+1) + c 22 x 2 (k) + ... + c 2n-1 x n-1 (k) + c 2n x n (k) + d 2
...
x n (k+1) = c n1 x 1 (k+1) + c n2 x 2 (k+1) + ... + c nn-1 x n-1 (k+1) + c nn x n (k) + d n
где x (0) - некоторое начальное приближение к решению.

Таким образом i-тая компонента (k+1)-го приближения вычисляется по формуле

Условие окончания итерационного процесса Зейделя при достижении точности ε в упрощенной форме имеет вид:

|| x (k+1) - x (k) || ≤ ε.

Билет№30

Метод прогонки

Для решения систем A x = b с трехдиагональной матрицей наиболее часто применяется метод прогонки, являющийся адаптацией метода Гаусса к этому случаю.

Запишем систему уравнений

d 1 x 1 + e 1 x 2 = b 1
c 2 x 1 + d 2 x 2 + e 2 x 3 = b 2
c 3 x 2 + d 3 x 3 + e 3 x 4 = b 3
... ... ...
c n-1 x n-2 + d n-1 x n-1 + e n-1 x n = b n-1
c n x n-1 + d n x n = b n

в матричном виде: A x = b где

A=

Выпишем формулы метода прогонки в порядке их применения.

1. Прямой ход метода прогонки (вычисление вспомогательных величин):

2. Обратный ход метода прогонки (нахождение решения):

Билет№31

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

Суть метода простых итераций состоит в переходе от уравнения

f(x) = 0 (*)

к эквивалентному уравнению

x =φ(x) . (**)

Этот переход можно осуществить разными способами, в зависимости от вида f(x) . Например, можно положить

φ(x) =x +bf(x) ,(***)

где b = const, при этом корни исходного уравнения не изменятся.

Если известно начальное приближение к корню x 0 , то новое приближение

x 1 =φx(0) ,

т.е. общая схема итерационного процесса:

x k+1 =φ(x k) .(****)

Наиболее простой критерий окончания процесса

|x k +1 -x k |<ε.

Критерий сходимости метода простых итераций:

если вблизи корня |φ / (x) | < 1, то итерации сходятся. Если указанное условие справедливо для любого x , то итерации сходятся при любом начальном приближении.

Исследуем выбор константы b с точки зрения обеспечения максимальной скорости сходимости. В соответствии с критерием сходимости наибольшая скорость сходимости обеспечивается при |φ / (x)| = 0 . При этом, исходя из (***), b = –1/f / (x), и итерационная формула (****) переходит в х i =х i-1 -f(x i-1)/f/ (x i-1).- т.е. в формулу метода Ньютона. Таким образом, метод Ньютона является частным случаем метода простых итераций, обеспечивающим самую высокую скорость сходимости из всех возможных вариантов выбора функции φ(x ).

Билет№32

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

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

Пусть - определённая на отрезке и дифференцируемая на нём вещественнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:

где α - угол наклона касательной в точке .

Следовательно искомое выражение для имеет вид:

Билет№33

Метод золотого сечения
Метод золотого сечения позволяет исключать интервалы, вычисляя только одно значение функции на каждой итерации. В результате двух рассмотренных значений функции определяется интервал, который должен использоваться в дальнейшем. Этот интервал будет содержать одну из предыдущих точек и следующую точку, помещаемую симметрично ей. Точка делит интервал на две части так, что отношение целого к большей части равно отношению большей части к меньшей, т. е. равно так называемому «золотому сечению».

Деление интервала на неравные части позволяет найти еще более эффективный метод. Вычислим функцию на концах отрезка [a ,b ] и положим a =x 1 , b =x 2 . Вычислим также функцию в двух внутренних точках x 3 , x 4 . Сравним все четыре значения функции и выберем среди них наименьшее. Пусть, например, наименьшим оказалось f (x 3 ). Очевидно, минимум находиться в одном из прилегающих к нему отрезков. Поэтому отрезок [x 4 ,b ] можно отбросить и оставить отрезок .

Первый шаг сделан. На отрезке снова надо выбрать две внутренние точки, вычислив в них и на концах значения функции и сделать следующий шаг. Но на предыдущем шаге вычислений мы уже нашли функцию на концах нового отрезка и в одной его внутренней точке x 4 . Потому достаточно выбрать внутри еще одну точку x 5 определить в ней значение функции и провести необходимые сравнения. Это вчетверо уменьшает объем вычислений на одном шаге процесса. Как выгодно размещать точки? Каждый раз оставшийся отрезок делиться на три части и затем отбрасывается один из крайних отрезков.
Обозначим первоначальный интервал неопределенности через D .

Так как в общем случае может быть отброшен любой из отрезков Х 1 ,Х 3 или Х 4 ,Х 2 то выберем точки Х 3 и Х 4 так, чтобы длины этих отрезков были одинаковы:

x 3 -x 1 =x 4 -x 2 .

После отбрасывания получится новый интервал неопределенности длины D′ .
Обозначим отношение D /D′ буквой φ:

то есть положим , где - следующий интервал неопределенности. Но

по длине равен отрезку, отброшенному на предыдущем этапе, то есть

Поэтому получим:

.
Это приводит к уравнению или, что то же
.

Положительный корень этого уравнения дает

.

Билет№34

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

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

Рассмотрим, как данный метод реализуется при решении СЛАУ. Метод простой итерации имеет следующий алгоритм:

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

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

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

3. Преобразование полученной системы к нормальному виду:

x - =β - +α*x -

Это можно сделать множеством способов, например, так: из первого уравнения выразить х 1 через другие неизвестные, из второго- х 2 , из третьего- х 3 и т.д. При этом используем формулы:

α ij = -(a ij / a ii)

i = b i /a ii
Следует снова убедиться, что полученная система нормального вида соответствует условию сходимости:

∑ (j=1) |α ij |≤ 1, при этом i= 1,2,...n

4. Начинаем применять, собственно, сам метод последовательных приближений.

x (0) - начальное приближение, выразим через него х (1) , далее через х (1) выразим х (2) . Общая формула а матричном виде выглядит так:

x (n) = β - +α*x (n-1)

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

max |x i (k)-x i (k+1) ≤ ε

Итак, давайте разберем на практике метод простой итерации. Пример:
Решить СЛАУ:

4,5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 с точностью ε=10 -3

Посмотрим, преобладают ли по модулю диагональные элементы.

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

7,6x1+0.6x2+2.4x3=3

Из третьего вычтем первое:

2,7x1+4.2x2+1.2x3=2

Мы преобразовали исходную систему в равноценную:

7,6x1+0.6x2+2.4x3=3
-2,7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4

Теперь приведем систему к нормальному виду:

x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3= 0.8511-0.383x1-0.5319x2

Проверяем сходимость итерационного процесса:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383+ 0.5319= 0.9149 ≤ 1 , т.е. условие выполняется.

0,3947
Начальное приближение х (0) = 0,4762
0,8511

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

0,08835
x (1) = 0,486793
0,446639

Подставляем новые значения, получаем:

0,215243
x (2) = 0,405396
0,558336

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

x (7) = 0,441091

Проверим правильность полученных результатов:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0,1880+2.3*0,441-1.1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

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

Как мы видим, метод простой итерации дает довольно точные результаты, однако для решения этого уравнения нам пришлось потратить много времени и проделать громоздкие вычисления.