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

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

Правила ввода функции

2. Примеры
   ≡ x^2/(1+x)
   cos 2 (2x+π) ≡ (cos(2*x+pi))^2
   ≡ x+(x-1)^(2/3)

На рис.1а, 1б в окрестности корня |φ′(x)| 1, то процесс итерации может быть расходящимся (см. рис.2).

Достаточные условия сходимости метода итерации

Процесс нахождения нулей функции методом итераций состоит из следующих этапов:

1. Получить шаблон с омощью этого сервиса.
2. Уточнить интервалы в ячейках B2 , B3 .
3. Копировать строки итераций до требуемой точности (столбец 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 ) .

1 Численный метод решения нелинейных уравнений

1.1 Область локализации корней

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

Например , для уравнения выполним преобразование и приведем его к виду f(x)= 0 т.е. . График этой функции представлен на рисунке 1. Очевидно, что данное уравнение имеет два действительных корня – один на отрезке [-1, 0] , а второй – [1, 2].

Рисунок 1. График функции

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

Некоторые виды уравнений допускают аналитическое решение. Например, степенные алгебраические уравнения степени n при n ≤ 4. Однако, в общем виде, аналитическое решение, как правило, отсутствует. В этом случае, применяются численные методы. Все численные методы решения уравнений представляют собой итерационные алгоритмы последовательного приближения к корню уравнения. То есть, выбирается начальное приближение к корню x ₀ и затем с помощью итерационной формулы генерируется последовательность x ₁, x ₂, …, x_k сходящаяся к корню уравнения .

1.2 Критерии сходимости при решении уравнений

Ø Абсолютная погрешность — абсолютное изменение приближения на соседних шагах итерации

Ø Относительная погрешность — относительное изменение приближения на соседних шагах итерации

Ø Близость к нулю вычисленного значения левой части уравнения (иногда это значение называют невязкой уравнения, так как для корня невязка равна нулю)

1.3 Метод половинного деления (метод дихотомии)

Метод половинного деления основан на последовательном делении отрезка локализации корня пополам.

Для этого выбирается начальное приближение к отрезку [ a , b ], такое, что f ( a ) × f ( b ) — середине отрезка [ a , b ]. Если он противоположен знаку функции в точке a, то корень локализован на отрезке [ a , c ], если же нет – то на отрезке [ c , b ]. Схема метода дихотомии приведен на рис у нке 2.

Рисунок 2. Последовательное деление отрезка пополам и приближение к корню

Алгоритм метода дихотомии можно записать так:

1. представить решаемое уравнение в виде

2. выбрать a, b и вычислить

3. если f(a) × f( с ) то a=a; b = c иначе a = c; b=b

4. если критерий сходимости не выполнен, то перейти к п. 2

Пример решения уравнения методом дихотомии

Найти решение заданного уравнения методом дихотомии с точностью до 10 -5 .

Пример создания расчетной схемы на основе метода дихотомии на примере уравнения: на отрезке [1, 2]

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

если f ( a ) × f (с) и выбор соответствующего отрезка для следующей итерации.

Рисунок 3. Последовательность итераций метода дихотомии при поиске корня уравнения на отрезке [1, 2]

a ) схема расчета (зависимые ячейки); b) режим отображения формул;

Для нашего примера итерационная последовательность для нахождения решения принимает вид:

Точность до пятой значащей цифры достигается за 20 итераций.

Скорость сходимости этого метода является линейной.

При выполнении начального условия он сходится к решению всегда.

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

2 Решение уравнений , используя “Подбор параметра ”

Используя возможности Excel можно находить корни нелинейного уравнения вида f(x)=0 в допустимой области определения переменной. Последовательность операций нахождения корней следующая:

1. Производится табулирование функции в диапазоне вероятного существования корней;

2. По таблице фиксируются ближайшие приближения к значениям корней;

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

При подборе параметра Excel использует итерационный (циклический) процесс. Количество итераций и точность устанавливаются в меню Сервис/Параметры/вкладка Вычисления. Если Excel выполняет сложную задачу подбора параметра, можно нажать кнопку Пауза в окне диалога Результат подбора параметра и прервать вычисление, а затем нажать кнопку Шаг, чтобы выполнить очередную итерацию и просмотреть результат. При решении задачи в пошаговом режиме появляется кнопка П родолжить — для возврата в обычный режим подбора параметра.

2.1 Пример решения уравнения, используя “Подбор параметра”

Например , найдем все корни уравнения 2x 3 -15sin(x)+0,5x-5=0 на отрезке [-3 ; 3].

Для локализации начальных приближений необходимо определить интервалы значений Х, внутри которых значение функции пересекает ось абсцисс, т.е. функция меняет знак. С этой целью табулируем функцию на отрезке [–3; 3] с шагом 0,2, получим табличные значения функции. Из полученной таблицы находим, что значение функции трижды пересекает ось Х, следовательно, исходное уравнение имеет на заданном отрезке все три корня.

Рисунок 4. Поиск приближенных значений корней уравнения

Выполните команду меню Сервис/Параметры, во вкладке Вычисления установите относительную погрешность вычислений E=0,00001, а число итераций N=1000, установите флажок Итерации.

Выполните команду меню Сервис/Подбор параметра. В диалоговом окне (рисунок 9) заполните следующие поля:

þ Установить в ячейке : в поле указывается адрес ячейки, в которой записана формула правой части функции;

þ Значение : в поле указывается значение, которое должен получить полином в результате вычислений, т.е. правая часть уравнения (в нашем случае 0);

þ Изменяя значение : в поле указывается адрес ячейки (где записано начальное приближение), в которой будет вычисляться корень уравнения и на которую ссылается формула.

Рисунок 5. Диалоговое окно Подбор параметра для поиска первого корня

После щелчка на ОК получим значение первого корня -1,65793685 .

Выполняя последовательно операции аналогичные предыдущим, вычислим значения остальных корней: -0,35913476 и 2,05170101 .

3 Решение уравнений и систем уравнений, используя надстройку “Поиск решения”

Для решения уравнений можно также использовать команду Поиск решения, доступ к которой реализуется через пункт меню Сервис/Поиск решения.

Последовательность операций нахождения корней следующая:

1. Найти приближенное значение корня уравнения

2. Открыть диалог Поиск решения и установить следующие параметры (рисунок 10):

þ в поле У становить целевую ячейку ввести адрес ячейки, содержащей формулу (левую часть уравнения);

þ установить переключатель в положение ‘ значению’ и ввести значение 0 (правая часть уравнения);

þ в поле Изменяя ячейки ввести адреса изменяемых ячеек, т.е. аргумента x целевой функции,;

þ в поле Ограничения с помощью кнопки Д обавить ввести все ограничения, которым должен отвечать результат поиска (область поиска корня уравнения);

þ для запуска процесса поиска решения нажать кнопку В ыполнить.

þ Для сохранения полученного решения необходимо использовать переключатель С охранить найденное решение в открывшемся окне диалога Результаты поиска решения.

Рисунок 6. Диалоговое окно Поиск решения

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

Рассмотрим некоторые Опции, управляющие работой Поиска решения, задаваемые в окне Параметры (окно появляется, если нажать на кнопку Параметры окна Поиск решения):

þ Максимальное время — ограничивает время, отведенное на процесс поиска решения (по умолчанию задано 100 секунд, что достаточно для задач, имеющих около 10 ограничений, если задача большой размерности, то время необходимо увеличить).

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

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

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

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

Рисунок 7. Вкладка Параметры окна Поиск решения

3.1 Пример решения уравнения, используя надстройку “Поиск решения”

Например , найдем все корни уравнения 2x 3 -15sin(x)+0,5x-5=0 на отрезке [-3 ; 3]. Для локализации начальных приближений необходимо определить интервалы значений Х, внутри которых значение функции пересекает ось абсцисс, т.е. функция меняет знак. С этой целью табулируем функцию на отрезке [–3;3] с шагом 0,2, получим табличные значения функции. Из полученной таблицы находим, что значение функции трижды пересекает ось Х, следовательно, исходное уравнение имеет на заданном отрезке все три корня. На рисунке 12 представлен пример заполнения окна Поиск решения для нахождения первого корня на отрезке [-2; -1].

Рисунок 8. Пример решения уравнения при помощи надстройки Поиск решения

Задание 1. Решение уравнений численным методом

На листе 1 (название листа: Численные методы) для заданного уравнения вида f(x)=0 (Таблица 1. Индивидуальные задания ) реализовать итерационные расчетные схемы методов, указанных в Таблице 1 для нахождения хотя бы одного корня на заданном интервале. Количество итераций просчитать, оценивая , .

Задания 2. Решение уравнений встроенными средствами “Подбор параметра” и “Поиск решения”

На листе 2 (название листа: Подбор Поиск) для заданного уравнения вида f(x)=0 (Таблица 1. Индивидуальные задания) на заданном интервале и с некоторым шагом (шаг выбрать самостоятельно) построить таблицу значений функции f(x) и определить количество корней уравнения и выделить интервалы, на которых находятся корни. Построить график функции. Уточнить на заданных интервалах с точностью до 10 -6 корни уравнения с помощью встроенных средств: Подбор параметра, Поиск решения