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

2.7). При решении уравнения необходимо отыскатьточкупересечения кривой у = f (х) ипрямойу = х.НаРис. 2.7, аизображена некоторая кривая у = f (х), котораяможетпредставлять собой любую функцию, но сейчас для нас важно то обстоятельство, что производная этой функции в окрестности корня положительна и меньше 1. Пусть х = х*- корень уравнения, который, естественно, предполагается неизвестным. Выберем начальное приближение в точке х0. Следующее приближении х1, в соответствии с, будет равно f (x0).Для того, чтобы отобразить х1 на графике, можно провести через точку прямую, параллельную оси ОХ, до пересечения с прямой у = х, а затем в точке пересечения этих прямых опустить перпендикуляр на ось ОХ, который и отметит положение точки x1. Аналогично получаются все последующие приближения. Из рисунка видно, что они сходятся к корню. Напомним, что для рассмотрения мы взяли функцию, производная которой положительна и меньше 1. Рассмотрим теперь другую функцию у = f (х), производная которойотрицательна, но меньше 1 по абсолютному значению. Этот случай изображен на Рис.

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

В обоих случаях каждое последующее приближение отстоит дальше от корня, т. е. итерационный процесс расходится. Из сказанного выше можно предположить, что итерационный процесс, определяемый формулой, сходится при условии, что производная f (х) меньше 1 по абсолютной величине. Математически условие сходимости можно установить следующим образом [7]. Представим k-е и (k+1)-е приближения в форме:

где ek и ek+1- отклонения приближений от корня. Функцию f (х) вблизи точки х* приближенно заменим первыми двумя членами ряда Тейлора. Тогда итерационная формула примет вид:

но, поскольку х* является корнем уравнения, то первые слагаемые в правой и левой частях этого выражения тождественно равны и, следовательно, Для сходимости итерационного процесса необходимо, чтобы погрешность на каждом шаге убывала:

откуда следует, что в окрестности корня должно выполняться условие:

Таким образом, для того чтобы итерационный процесс был сходящимся, необходимо, чтобы абсолютная величина производной f'(х) в окрестности корня была меньше единицы. Если это условие выполняется на отрезке [а, b], на котором локализован корень, то в качестве начального приближения можно взять любую точку из этого отрезка. Скорость сходимости зависит от абсолютной величины производнойf'(х)-: чем меньшеf'(х) — вблизи корня, тем быстрее сходится процесс. Преобразование уравнения к итерационному виду

Переход от уравнения к уравнению в итерационной форме можно осуществить различными способами в зависимости от вида функции f (х) [8]. При таком переходе необходимо построить функцию f (х) так, чтобы выполнялось условие сходимости .В качестве примера рассмотрим уравнение х3-х-1 = 0, один из корней которого расположен в интервале [1,2]. Преобразуем это уравнение квиду следующим образом: х = х3−1. Проверим условие сходимости для средней точки интервала локализации х = 1,5:Очевидно, что условие сходимости не выполнено. Преобразуемуравнение к итерационному виду другим способом:, и вновь проверим условие сходимости:

Видно, что в этом случае условие сходимости выполнено. Теперь рассмотрим один из общих алгоритмов перехода от уравнения f (х) = 0 к уравнению х = f (х). Умножим левую и правую части уравнения f (х) = 0 на произвольную константу и добавим к обеим частям неизвестное х. При этом корни исходного уравнения не изменятся, или

Уравнениеэквивалентноуравнению с функцией. Произвольный выбор константы позволяет обеспечить выполнение условия сходимости. Поскольку в данном случае, значение следует выбирать, так чтобы в окрестности корня выполнялось условие:

Желательно выбрать величину t такой, чтобы -1 < f'(х) < 0, тогда сходимость будет двухсторонней (Рис. 2.7,в). В этом случае в качестве критерия окончания итерационного процесса можно использовать соотношение.Замечание. При сходимости последовательных приближений к корню с разных сторон, что имеет место при f'(х) < 0 в окрестности корня (Рис. 2.7, в), величина превосходит истинную погрешность, т. е. и критерий окончания итерационного процессаявляется вполне объективным. Если же f'(х) > 0, то сходимость ккорню носит односторонний характер (Рис. 2.7, а), и условиеможет выполниться гораздо раньше нужного требования. В этом случае контроль достигнутой точности лучше осуществлять по проверке неравенствагде Наибольшую скорость сходимости в методе простых итераций получим при f'(х) = 0. Этого можно добиться, если выбрать параметр tзависящимотхв виде

При этом итерационная формула переходит в формулу Ньютона:

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

Идея метода Мюллера состоит в приближенной замене функции f (х)интерполяционным полиномом второй степени (параболой), построенным по трем точкам хk-2, хk-1, хk, и нахождением абсциссы точки пересеченияэтой параболы с осью ОХ, т. е. решением квадратного уравнения. Иными словами, в методе Мюллера используется не линейная аппроксимация, как в методах хорд, секущих и Ньютона, а квадратичная. Расчетные формулы метода следующие:

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

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

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

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

Все рассмотренные выше методы уточнения корней нелинейных уравнений одинаково пригодны как для трансцендентных, так и для алгебраических уравнений. В то же время существуют методы, учитывающие специфику решаемой задачи. Рассмотрим кратко два таких метода[8]. Метод Лаггера

Метод Лагерра основывается на следующих соотношениях для полиномов:

Предполагают, что корень х1, который мы ищем, находится на расстоянии, а от текущего приближения, в то время как все другие корни находятся на расстоянии b: х-х1 = а; х-хi = b, I = 2,3,…, п. Тогда с учетом рассмотренных соотношений для полиномов можно записать: и Выражая из этих соотношений а, получим:

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

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

Список литературы

Турчак Л. И. Основы численных методов: Учеб.

пособие. — М.: Наука; Гл. ред. физ.-мат. лит., 2008. — 320 с. Тынкевич М. А. Численные методы анализа: Учеб.

пособие. — Кемерово, 2007. — 123 с. Бахвалов Н. С., Лапин А. В., Чижонков Е. В. «Численные методы в задачах и упражнениях». М.: Высшая школа, 2010

Амосов А.А., Дубинский Ю. А., Копченова Н. В. «Вычислительные методы для инженеров». М.: Высшая школа, 2014

Самарский А.А., Гулин А. В. «Численные методы». М.: Наука, 2009

Бахвалов Н. и др. Численные методы. — М.: Лаборатория базовых знаний. 2005. -

624с.Вержбицкий В. М. Численные методы. Математический анализ и ОДУ.-М.: Высшая школа. 2006. — 382 с. Вержбицкий В. М. Численные методы. Линейная алгебра и нелинейные уравнения.-М.: Высшая школа. 2010. -266 с.