Метод итераций
Правила ввода функции
- Примеры
≡ x^2/(1+x)
cos 2 (2x+π) ≡ (cos(2*x+pi))^2
≡ x+(x-1)^(2/3)
На рис.1а, 1б в окрестности корня |φ′(x)| 1, то процесс итерации может быть расходящимся (см. рис.2).
Достаточные условия сходимости метода итерации
Процесс нахождения нулей функции методом итераций состоит из следующих этапов:
- Получить шаблон с омощью этого сервиса.
- Уточнить интервалы в ячейках B2 , B3 .
- Копировать строки итераций до требуемой точности (столбец D ).
Примечание: столбец A — номер итерации, столбец B — корень уравнения X , столбец C — значение функции F(X) , столбец D — точность eps .
Итерационные методы решения системы линейных алгебраических уравнений
В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.
Общие сведения об итерационных методах или методе простой итерации
Метод итерации — это численный и приближенный метод решения СЛАУ.
Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x 0 .
Рассмотрим систему A x = b .
Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду x = B x + d . Затем выбираем начальное приближение к решению СЛАУ x ( 0 ) = ( x 1 0 , x 2 0 , . . . x m 0 ) и находим последовательность приближений к корню.
Для сходимости итерационного процесса является достаточным заданное условие В 1 . Окончание итерации зависит от того, какой итерационный метод применили.
Метод Якоби
Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 1-го уравнения матрицы выражаем неизвестное x 1 , из 2-го выражаем неизвестное x 2 и т.д.
Результатом служит матрица В , в которой на главной диагонали находятся нулевые элементы, а все остальные вычисляются по формуле:
b i j = — a i j / a i i , i , j = 1 , 2 . . . , n
Элементы (компоненты) вектора d вычисляются по следующей формуле:
d i = b i / a i i , i = 1 , 2 , . . . , n
Расчетная формула метода простой итерации:
x ( n + 1 ) = B x ( x ) + d
Матричная запись (координатная):
x i ( n + 1 ) = b i 1 x n 1 + b i 2 x ( n ) 2 + . . . + b
Критерий окончания в методе Якоби:
x ( n + 1 ) — x ( n ) ε 1 , где ε 1 = 1 — B B ε
В случае если B 1 / 2 , то можно применить более простой критерий окончания итераций:
x ( n + 1 ) — x ( n ) ε
Решить СЛАУ методом Якоби:
10 x 1 + x 2 — x 3 = 11 x 1 + 10 x 2 — x 3 = 10 — x 1 + x 2 + 10 x 3 = 10
Необходимо решить систему с показателем точности ε = 10 — 3 .
Приводим СЛАУ к удобному виду для итерации:
x 1 = — 0 , 1 x 2 + 0 , 1 x 3 + 1 , 1 x 2 = — 0 , 1 x 1 + 0 , 1 x 3 + 1 x 3 = 0 , 1 x 1 — 0 , 1 x 2 + 1
Выбираем начальное приближение, например: x ( 0 ) = 1 , 1 1 1 — вектор правой части.
В таком случае, первая итерация имеет следующий внешний вид:
x 1 ( 1 ) = — 0 , 1 × 1 + 0 , 1 × 1 + 1 , 1 = 1 , 1 x 2 ( 1 ) = — 0 , 1 × 1 , 1 + 0 , 1 + 1 = 0 , 99 x 3 ( 1 ) = 0 , 1 × 1 , 1 — 0 , 1 × 1 + 1 = 1 , 01
Аналогичным способом вычисляются приближения к решению:
x ( 2 ) = 1 , 102 0 , 991 1 , 011 , x ( 3 ) = 1 , 102 0 , 9909 1 , 0111 , x ( 4 ) = 1 , 10202 0 , 99091 1 , 01111
Находим норму матрицы В , для этого используем норму B ∞ .
Поскольку сумма модулей элементов в каждой строке равна 0,2, то B ∞ = 0 , 2 1 / 2 , поэтому можно вычислить критерий окончания итерации:
x ( n + 1 ) — x ( n ) ε
Далее вычисляем нормы разности векторов:
x ( 3 ) — x ( 2 ) ∞ = 0 , 002 , x ( 4 ) — x ( 3 ) ∞ = 0 , 00002 .
Поскольку x ( 4 ) — x ( 3 ) ∞ ε , то можно считать, что мы достигли заданной точности на 4-ой итерации.
x 1 = 1 , 102 ; x 2 = 0 , 991 ; x 3 = 1 ,01 1 .
Метод Зейделя
Метод Зейделя — метод является модификацией метода Якоби.
Суть: при вычислении очередного ( n + 1 ) — г о приближения к неизвестному x i при i > 1 используют уже найденные ( n + 1 ) — е приближения к неизвестным x 1 , x 2 , . . . , x i — 1 , а не n — о е приближение, как в методе Якоби.
x i ( n + 1 ) = b i 1 x 1 ( n + 1 ) + b i 2 x 2 ( n + 1 ) + . . . + b i , i — 1 x i — 2 ( n + 1 ) + b i , i + 1 x i + 1 ( n ) +
+ . . . + b i m x m ( n ) + d i
За условия сходимости и критерий окончания итераций можно принять такие же значения, как и в методе Якоби.
Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.
Решим 3 системы уравнений:
2 x 1 + x 2 = 3 x 1 — 2 x 2 = 1 , x 1 + 2 x 2 = 3 2 x 1 — x 2 = 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1
Приведем системы к удобному для итерации виду:
x 1 ( n + 1 ) = — 0 , 5 x 2 ( n ) + 1 , 5 x 2 ( n + 1 ) = 0 , 5 x 1 ( n + 1 ) + 0 , 5 , x 1 ( n + 1 ) = — 2 x 2 ( n ) + 3 x 2 ( n + 1 ) = 2 x 1 ( n + 1 ) — 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1 .
Отличительная особенность, условие сходимости выполнено только для первой системы:
Вычисляем 3 первых приближения к каждому решению:
1-ая система: x ( 0 ) = 1 , 5 — 0 , 5 , x ( 1 ) = 1 , 75 0 , 375 , x ( 2 ) = 1 , 3125 0 , 1563 , x ( 3 ) = 1 , 4219 0 , 2109
Решение: x 1 = 1 , 4 , x 2 = 0 , 2 . Итерационный процесс сходится.
2-ая система: x ( 0 ) = 3 — 1 , x ( 1 ) = 5 9 , x ( 2 ) = — 15 — 31 , x ( 3 ) = 65 129
Итерационный процесс разошелся.
Решение: x 1 = 1 , x 2 = 2
3-я система: x ( 0 ) = 1 , 5 2 , x ( 1 ) = 2 — 6 , x ( 2 ) = 0 2 , x ( 3 ) = 0 2
Итерационный процесс зациклился.
Решение: x 1 = 1 , x 1 = 2
Метод простой итерации
Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:
x = x — τ ( A x — b ) , τ — итерационный параметр.
Расчетная формула имеет следующий внешний вид:
x ( n + 1 ) = x ( n ) — τ ( A x n — b ) .
Здесь B = E — τ A и параметр τ > 0 выбирают таким образом, чтобы по возможности сделать максимальной величину B 2 .
Пусть λ m i n и λ m a x — максимальные и минимальные собственные значения матрицы А .
τ = 2 / ( λ m i n + λ m a x ) — оптимальный выбор параметра. В этом случае B 2 принимает минимальное значение, которое равняется ( λ m i n + λ m a x ) / ( λ m i n — λ m a x ) .
3.2.1. Метод простых итераций (метод последовательных приближений)
Метод реализует стратегию постепенного уточнения значения корня.
Постановка задачи. Дано нелинейное уравнение (3.1). Корень отделен x* Î [a;b]. Требуется уточнить корень с точностью ε.
Уравнение ( 3.1) преобразуем к эквивалентному виду x=φ(x), (3.7)
Что можно сделать всегда и притом множеством способов.
Выберем начальное приближение x0Î [a;b].
Вычислим новые приближения:
Xi=φ(xi-1) , i=1,2,… где i − номер итерации. (3.8)
Последовательное вычисление значений xi по формуле (3.8) называется итерационным процессом метода простых итераций, а сама формула — формулой итерационного процесса метода.
Если , то итерационный процесс Сходящийся .
Условие сходимости (3.9)
Точное решение x* получить невозможно, так как требуется Бесконечный Итерационный процесс.
Можно получить Приближенное Решение, прервав итерационный (3.8) при достижении условия
, (3.10)
Где ε — заданная точность; i — номер последней итерации.
В большинстве случаев условие завершения итерационного процесса (3.10) обеспечивает близость значения xi к точному решению:
Рассмотрим геометрическую иллюстрацию метода простых итераций.
Уравнение (3.7) представим на графике в виде двух функций: y1 = x и y2= φ(x).
Возможные случаи взаимного расположения графиков функций, и соответственно, видов итерационного процесса показаны на рис. 3.7 – 3.10.
Рис. 3.7 Итерационный процесс для случая 0 1 xÎ[a, b].
Рис. 3.10 Итерационный процесс для случая £ — 1 xÎ[a, b].
Из анализа графиков следует, что скорость сходимости растет при уменьшении значения
Метод достаточно прост, обобщается на системы уравнений, устойчив к погрешности округления (она не накапливается).
При разработке алгоритма решения нелинейного уравнения методом простых итераций следует предусмотреть защиту итерационного процесса от зацикливания: использовать в качестве дополнительного условия завершения итерационного процесса превышение заданного максимального числа итераций.
Рис 3.11. Алгоритм решения нелинейного уравнения методом
простых итераций:
Основной проблемой применения метода является обеспечение сходимости итерационного процесса: нужно найти такое эквивалентное преобразование (3.1) в (3.7), чтобы обеспечивалось условие сходимости (3.9) .
Простейшие эквивалентные преобразования, например:
F(x) = 0 => x+f(x) = x, т. е. φ(x) = x + f(x)
Или выразить явно x из (3.1)
F(x) = 0 => x — φ(x) = 0 => x = φ(x)
Не гарантируют сходимость.
Рекомендуется следующий способ получения формулы Сходящегося итерационного процесса.
Пусть .
Если это не так, переписать уравнение (3.1) в виде
Умножить обе части уравнения на и к обеим частям прибавить x:
Константу l вычислить по формуле:
(3.11)
Такое значение λ гарантирует сходящийся итерационный процесс по формуле
Xi = xi+1− λ f(x) (3.12)
Где i=1,2,… — номер итерации, x0Î[a, b] – начальное приближение.
Методом простых итераций уточнить корень уравнения x3=1-2 x с точностью ε=0,001. Корень отделен ранее (см. пример 3.1), x* Î [0;1].
Сначала нужно получить формулу сходящегося итерационного процесса.
Из уравнения выразим явно x:
Проверим условия сходимости для полученной формулы:
, ,
для x Î (0;1].
Условие сходимости не соблюдается, полученная формула не позволит уточнить корень.
Воспользуемся описанным выше способом получения формулы итерационного процесса (формулы 3.11, 3.12).
, , для всех x Î [0;1].
Наибольшее значение принимает при x = 1, т. е.
Следовательно .
Формула Сходящегося итерационного процесса
Уточним корень с помощью данной формулы.
Выберем начальное приближение на [0;1], например x0=0,5 (середина отрезка).
Вычислим первое приближение
Проверим условие завершения итерационного процесса
Расчет следует продолжить.
X6 = 0,453917 − ответ, т. к.
Проверим полученное значение, подставив в исходное уравнение:
Значение f(x) близко к 0 с точностью, близкой к ε, следовательно, корень уточнен правильно.
http://zaochnik.com/spravochnik/matematika/issledovanie-slau/iteratsionnye-metody-reshenija-slau/
http://matica.org.ua/metodichki-i-knigi-po-matematike/vychislitelnaia-matematika/3-2-1-metod-prostykh-iteratcii-metod-posledovatelnykh-priblizhenii