Решение методом простых итераций для расходящихся. Метод простой итерации

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

Билет№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

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

По аналогии с (2.1) систему (5.1) можно представить в следующей эквивалентной форме:

где g(x) - итерационная вектор-функция векторного аргумента. Системы нелинейных уравнений часто возникают непосредственно в виде (5.2) (например, в численных схемах для дифференциальных уравнений), в этом случае никаких дополнительных усилий для преобразования уравнений (5.1) в систему (5.2) не требуется. Если продолжить аналогию с методом простой итерации для одного уравнения, то итерационный процесс, основанный на уравнении (5.2), можно организовать следующим образом:

• 1) выбирается некоторый начальный вектор х ((,) е 5 о (х 0 , а) (предполагается, что х* е 5„(х 0 , а));
• 2) последующие приближения вычисляются по формуле

то итерационный процесс завершен и

Как и раньше, нам необходимо выяснить, при каких условиях

Обсудим этот вопрос, выполнив простой анализ. Вначале мы введем ошибку /г-го приближения как е (^ = x (i) - х*. Тогда мы можем записать

Подставим эти выражения в (5.3) и разложим g(x* + e (/i)) по степеням е (к> в окрестности х* как функцию векторного аргумента (предполагая, что все частные производные функции g(x) непрерывны). Учитывая также, что х* = g(x*), мы получим

или в матричной форме

В = {b nm } = I (х*)1 - итерационная матрица.

Если норма ошибки ||е®|| достаточно мала, то вторым слагаемым в правой части выражения (5.4) можно пренебречь, и тогда оно совпадает с выражением (2.16). Следовательно, условие сходимости итерационного процесса (5.3) вблизи точного решения описывается теоремой 3.1.

Сходимость метода простой итерации. Необходимое и достаточное условие для сходимости итерационного процесса (5.3):

и достаточное условие:

Эти условия имеют скорее теоретическое, чем практическое значение, так как мы не знаем х‘. По аналогии с (1.11) получим условие, которое может быть полезным. Пусть х* е 5 о (х 0 , а) и матрица Якоби для функции g(x)

существует для всех x e S n (x 0 , a ) (заметим, что C(x*) = В). Если элементы матрицы С(х) удовлетворяют неравенству

для всех х е 5„(х 0 , а), тогда достаточное условие (5.5) также выполняется для любой матричной нормы.

Пример 5.1 (метод простой итерации) Рассмотрим следующую систему уравнений:

Одна из возможностей представить эту систему в эквивалентной форме (5.2) - выразить Х из первого уравнения и х 2 из второго уравнения:

Тогда итерационная схема имеет вид

Точное решение х* е 5„((2, 2), 1). Выберем начальный вектор х (0) = (2,2) и ? р = КТ 5 . Результаты вычислений представлены в табл. 5.1.

Таблица 5.1

Эти результаты показывают, что сходимость довольно медленная. Для того чтобы получить количественную характеристику сходимости, проведем простой анализ, считая х (1/) точным решением. Матрица Якоби С(х) для нашей итерационной функции имеет вид

тогда матрица В приближенно оценивается как

Легко проверить, что ни условие (5.5), ни условие (5.6) не удовлетворяются, но сходимость имеет место, так как 5(B) ~ 0.8.

Часто можно ускорить сходимость метода простой итерации, слегка изменив процесс вычислений. Идея такой модификации очень проста: для вычисления п -й компоненты вектора х (А+1) можно использовать не только (т = п ,..., N ), но также уже вычисленные компоненты вектора следующего приближения х к ^ (/= 1,п - 1). Таким образом, модифицированный метод простой итерации может быть представлен в виде следующей итерационной схемы:

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

Пример 5.2 (модифицированный метод простой итерации) Модифицированная простая итерация для системы (5.7) представляется в виде

Как и прежде, выберем начальный вектор х (0) = (2, 2) и г р = = 10 -5 . Результаты вычислений представлены в табл. 5.2.

Таблица 5.2

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

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

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

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

{ 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 } для случая одной переменной. Согласно теореме Лагранжа имеем: