Численное решение уравнений. метод итераций
ЦЕЛЬ ЛЕКЦИИ: Для уравнения ввести постановки задач отделения и уточнения корней, сформулировать лемму об оценке погрешности приближенного решения, построить метод простой итерации, получить для него оценку точности, доказать его сходимость.
Пусть требуется решить уравнение
,
т. е. найти все корни , удовлетворяющие этому уравнению на отрезке .
Задача численного решения уравнения сводится, во-первых, к отделению корней, во-вторых, к последующему уточнению корней.
Отделение корней.
Отделить корни уравнения значит заключить каждый корень в интервал
,
для которого выполняются условия:
1. ;
2. – знакопостоянная функция для .
Первое неравенство обеспечивает наличие в интервале хотя бы одного корня, второе условие гарантирует единственность корня (см. рис. 4.1).
Для отделения корней можно использовать аналитический и табличный способы.
Аналитический предполагает исследование функции методами математического анализа, последующее построение графика функции, из которого и определяются интервалы, содержащие единственный корень. Недостаток аналитического способа – неалгоритмизуемость.
Табличный метод предполагает составление таблицы значений , причем . Из таблицы на основании условий
алгоритмически определяются искомые интервалы . Чтобы не потерять корни, интервал отделения h должен быть достаточно малым.
Уточнение корней.
Пусть - корень уравнения
.
В дальнейшем – интервал, содержащий единственный корень.
Уточнить корень с заданной точностью значит найти приближенное значение такое, что
.
Для решения сформулированной задачи необходимо уметь производить оценку абсолютной погрешности метода, т. е. величины .
Лемма об оценке погрешности приближенного решения уравнения .
Лемма. Пусть уравнение на отрезке имеет корень . Пусть найдено некоторое его приближенное значение . Тогда
,
где
.
Доказательство. Вычислим по теореме о конечных приращениях:
.
Очевидно, что
.
Отсюда
,
или
.
Лемма доказана.
Величину называют невязкой. Из леммы следует, что судить о величине погрешности приближенного решения только по величине невязки нельзя. Необходимо учитывать и значение первой производной. Обратимся к рис. 4.2. Из этого рисунка следует, что одна и та же невязка приводит к существенно разным погрешностям приближенного решения, если производная в окрестности решения сильно отличается.
Метод итераций.
Для построения метода итераций преобразуем уравнение
к виду
.
Это можно сделать в общем случае так:
,
или , где
.
Постоянный множитель h выбирается при этом из условия сходимости метода (установим его позже).
Пусть известно начальное приближение . Тогда
Приведенный способ построения числовой последовательности реализуется в методе итераций:
.
Рассмотрим, как ведет себя погрешность решения на итерациях метода. Обозначим , где - погрешности приближенного решения на двух соседних итерациях. Подставим представленные таким образом и в итерационное правило:
.
Разложим функцию в ряд Тейлора в окрестности точки :
.
Пренебрегая остаточным членом , получим соотношение, связывающее погрешность решения метода на двух соседних итерациях:
.
Сделаем некоторые выводы на основании этого приближенного равенства.
· Если , то можно ожидать, что и последовательность будет сходиться к решению, когда начальное приближение выбрано достаточно близким к .
· Если , то скорее всего и метод будет расходиться, так как каждое последующее приближение будет отстоять от
решения дальше, чем предыдущее.
· При и погрешности и имеют одинаковые знаки. Сходимость будет монотонной.
· При и погрешности и имеют разные знаки. Сходимость является немонотонной.
Проиллюстрируем характер сходимости метода итераций графически. Образуем функции . В решении задачи значения этих функций совпадают. Первый пример (см. рис. 7.3,а) соответствует условиям
и, следовательно, в этом случае наблюдается монотонная сходимость метода итераций. В следующем примере (см. рис. 4.3,б)
,
поэтому имеет место немонотонная сходимость. В последнем примере (см. рис. 4.3,в)
.
При таких значениях производной метод итераций расходится.
Рис. 4.3. Иллюстрация сходимости метода итераций